Method for preventing deadlock by suspending operation of processors, bridges, and devices

• US 6,292,860 B1
• Filed: 12/16/1997
• Issued: 09/18/2001
• Est. Priority Date: 12/16/1997
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Scrivener, Harry W., Cochcroft, Arthur F. Jr., Batchler, Bobby W., Reams, Byron L., McDonald, Edward A.
• Primary Examiner(s): Dharia, Rupal
• Application Number:
  US08/991,697
• Time in Patent Office: 1,372 Days
• Field of Search: 710/101, 710/108, 710/200, 710/129, 710/113, 710/126, 709/210, 711/151
• US Class Current: 710/108
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 13/4036 and deadlock prevention
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A deadlock-avoidance system for a computer. In a multi-bus, multi-processor computer, one processor may request a lock on a bus, to execute a locked cycle, thereby blocking all other processors, and other agents, from access to the bus. In addition, a conflicting agent may, in effect, lock a resource which is needed by the processor to complete the cycle for which the lock was requested. These two locks can create a deadlock situation which stalls the computer: the processor and the conflicting agent have each locked a resource needed by the other. Under the invention, when a locked cycle is requested by a processor, all other operations are suspended in the computer. Then queues standing in memory controllers are emptied. If a process requested by an agent occupies a resource, such as a bridge, required by the requested locked cycle, that resource is freed. Then the locked cycle is executed.

Claims

1. A method comprising the following steps:

a) maintaining a multi-bus. multi-processor computer;

b) ascertaining whether a locked cycle of a predetermined type has been requested by a processor and, if so,

c) suspending operation of all processors.

2. Method according to claim 1, and further comprising the step of draining queues in memory controllers after suspending operation of the processors.

3. Method according to claim 2, in which all queues in all memory controllers are drained.

4. Method according to claim 2, and further comprising the step of attempting to execute the locked cycle, after draining the queues.

5. Method according to claim 1, wherein bridges connect busses in the computer with other busses, and further comprising the step of suspending operation of all bridges, in response to the request.

6. Method according to claim 5, and further comprising the step of draining queues in memory controllers after suspending operation of the processors.

12. Method according to claim 2, wherein the queues which are drained are drained fully.

13. Method according to claim 3, wherein the queues which are drained are drained fully.

7. A method of operating a multi-bus, multi-processor computer, wherein bridges connect busses in the computer with other busses, comprising the following steps:

a) ascertaining whether a locked cycle of a predetermined type has been requested by a processor and, if so,

b) suspending operation of all processors,

c) suspending operation of all bridges, in response to the request

d) draining queues in memory controllers after suspending operation of the processors;

e) attempting to execute the requested locked cycle after draining the queues; and

f) if the requested locked cycle requires use of a bridge having a non-empty input queue, then

i) emptying input queues in all bridges, and then

ii) executing the locked cycle with assistance of said bridge.

8. A method of operating a multi-bus, multi-processor computer, comprising the following steps:

a) ascertaining whether a locked cycle of a predetermined type has been requested by a processor and, if so,

b) suspending operation of all processors and all bridges;

c) after step (b), emptying queues of memory controllers;

d) after step (c), ascertaining

i) whether the requested locked cycle will require involvement of a bridge and, if so,

ii) whether said bridge is available;

e) after step (d),

i) if said bridge is available, executing said requested lock cycle;

ii) if said bridge is not available, emptying the input queue in said bridge, and then executing said requested locked cycle.

9. In a multi-bus, multi-processor computer, the improvement comprising the following steps:

a) detecting a request from a requesting processor for a locked cycle which extends beyond a bus lockable by the requesting processor; and

b) in response to the request, suspending operation of all other processors which can interfere with the locked cycle, while the requesting processor executes to the locked cycle.

10. Improvement according to claim 9, and further comprising the step of terminating suspension of said other processors, after the locked cycle completes.

11. In a multi-bus, multi-processor computer, the improvement comprising:

a) means for detecting a request for a locked cycle which requires involvement of a bridge; and

b) means for responding to said request by

i) suspending operation of other agents in the computer;

ii) emptying queues in memory controllers; and

iii) if said bridge is occupied, de-occupying said bridge, for use by said locked cycle.