US 6,292,860 B1Grant
Method for preventing deadlock by suspending operation of processors, bridges, and devices
Issue Date:2001-09-18
•13 Claims
•4 Drawing Sheets
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.
Metadata
Assignee
- NCR Corporation
Inventors
- Arthur F. Cochcroft, Jr.
- Edward A. McDonald
- Byron L. Reams
- Harry W. Scrivener
- Bobby W. Batchler
Application Information
Application Number:US 08/991,697
Filing Date:1997-12-16
Priority Date:1997-12-16
Art Unit:7
Classifications
IPC:
G06F 1300
Field of Search:
710101710108710200710129710113710126709210711151
Patent Drawings (4 sheets)
Description
[0002] The invention concerns a system for preventing deadlocks in computers. Deadlocks can occur when a first agent, such as a processor, locks a resource needed by a second agent, and the second agent locks a resource, such as a bridge, needed by the first agent.
BACKGROUND OF THE INVENTION
[0003] FIG. 1 illustrates a bus 3 in a computer (not shown). Processors P1-P4 have access to the bus 3. A memory controller C1 is connected to the bus 3, and controls traffic to, and from, memory M1. Bridges B1-BN are also connected to the bus 3. Each bridge, in effect, acts as an adaptor circuit which allows the bus 3 to communicate with another type of bus (not shown), which can connect to a source or repository of data, such as memory, or a peripheral.
[0004] Sometimes a processor P, such as processor P1, will impose a “lock” on the bus 3, by activating lock line L. The lock prevents all other agents, such as the other processors P2-P4, and the bridges B, from gaining access to the bus 3. The lock allows the processor P1 to perform a sequence of operations on memory, without interference by the other processors or the bridges.
[0005] As a simple example, processor P1 may (1) impose the lock, (2) read the data stored at memory address X, (3) modify the data read, (4) write the modified data to address X, and (5) release the lock.
[0006] If the lock were not imposed in step (1), then, immediately after processor P1 read the data at address X, another processor, such as P2, may read the same data. Then, after the processor P1 replaced the data with the modified data in step (4), the replaced data may be inconsistent with that held by processor P2. A data coherency problem would arise: the data held by processor P2 would not be an accurate copy of data at address X. The lock prevents this problem from occurring.
[0007] In a multi-bus system, the situation becomes more complex. FIG. 2 illustrates busses BA, BB, and BC. Processors P1-P4 are connected to bus BA. Processors PS-P8 are connected to bus BC. Bridges B1-BN are connected to bus BB. Controllers C1 and C2 control traffic to, and from, memories M1 and M2, respectively.
[0008] One problem which can arise in this system is that a program may run on processor P1 which writes words outside memory M1, such as to memory M2, through bus BC. However, processor P1 has no effective way to issue a lock on bus BC. This inability to lock bus BC can create the data coherency problem described in the Background of the Invention, because another agent can read, or write, data at an address in memory M2 which is being altered by processor P1.
[0009] Another problem can arise. Assume that processor P1 issues a lock, and that P1's operations, which follow the lock, involve writing a word through bridge B1, to a memory address on the “other side” 6 of bridge B1.
[0010] Assume also that, independent of processor P1's activities, (1) an agent A1 posts a write operation which requires involvement of bridge B1 for completion, and that (2) this write operation involves a data address which processor P1 had previously cached. Consequently, for this posted write operation to proceed, the cached data must be merged with the data posted by the agent, and then returned to memory. Then the posted write operation can proceed.
[0011] Now, a deadlock has occurred. Under the rules of operation, once processor P1 has issued the lock, processor P1 must be allowed to finish its intended steps. It cannot be disrupted by the merging operation of the cached data, described immediately above. Thus, the request of agent A1 is blocked.
[0012] However, processor P1 needs bridge B1. But, under other rules of operation, bridge B1 has become irrevocably involved in the write operation posted by agent A1. In effect, bridge B1 has become a “one-way street” running in the direction of the write operation of agent A1. This direction is opposite the direction required by processor P1.
[0013] P1 has blocked the merging needed by A1, and A1 has blocked the bridge needed by P1. No further action can be taken, and the system has become stalled, or deadlocked.
OBJECTS OF THE INVENTION
[0014] An object of the invention is to provide an improved multi-bus computer system.
[0015] A further object of the invention is to provide a system for preventing deadlocks in a multi-bus computer system.
SUMMARY OF THE INVENTION
[0016] In one form of the invention, when a processor calls for a locked cycle, activity of other processors and bridges within the computer is halted. Queues in memory controllers are emptied. The locked cycle is then attempted. If the attempt is blocked by a bridge which is pre-occupied, then the queue in that bridge, perhaps together with queues in other bridges, are emptied. The locked cycle is again attempted, and now should succeed.
BRIEF DESCRIPTION OF THE DRAWINGS
[0017] FIG. 1 illustrates a simplified computer architecture, known in the prior art.
[0018] FIG. 2 illustrates a multi-processor, multi-bus computer architecture.
[0019] FIG. 3 is a flow chart illustrating logic implemented by the invention.
[0020] FIG. 4 illustrates one form of the invention.
DETAILED DESCRIPTION OF THE INVENTION
[0021] FIG. 3 is a flow chart of logic implemented by the invention. In block 30, a processor, assumed to be processor P1 in FIG. 2, requests a lock which involves a remote access to address Y, such as through bridge B1. The lock can be requested in connection with a forthcoming locked cycle. The Background of the Invention illustrated a simplified locked cycle.
[0022] In decision block 35 in FIG. 3, inquiry is made whether the data at address Y has been cached by another processor. If so, block 40 is reached, and an implicit write-back, IWB, is undertaken, wherein the data within the cache is copied into address Y. (No IWB is undertaken if address Y is located on the “other side” 6 in FIG. 2). Now address Y is consistent with the cache.
[0023] If the data at address Y has not been cached by another processor, decision block 45 is reached. Arbitration is imposed, because processor P1 can not necessarily be granted the lock request at this time. One reason why the lock may be denied is that address Y may already be locked in another process, involving another processor.
[0024] If processor P1 loses the arbitration, then block 50 is reached. Processor P1 is informed of the denial, and will make the lock request again later.
[0025] If processor 1 wins the arbitration, then block 55 is reached. No further requests for memory operations are accepted by the memory controllers, C1 and C2 in FIG. 2. Alternately, since requests for memory operations are queued within the controllers, a marker may be placed at the current end of the queue of every controller. Additional requests are accepted but, as will be seen, their processing will be delayed.
[0026] Block 60 is reached in FIG. 3: operation of all processors P and bridges B in FIG. 2 is suspended.
[0027] Next, in block 65 in FIG. 3, all presently queued memory requests are processed, in the usual manner, thereby emptying the queues in the memory controllers. If a marker was used, all requests ahead of the marker are emptied.
[0028] Block 70 is reached, and the locked cycle is attempted. If, in decision block 75, the locked cycle is found to involve a memory address in another memory controller, the locked cycle executes, as indicated by block 80. The reason is that all queues in the memory controllers were emptied in block 65. After this emptying step, no requests stand in a memory controller which would block the locked cycle.
[0029] If, in block 75, it was found that the locked cycle is not intended for another memory controller, decision block 85 is reached, which inquires whether a bridge is blocking the locked cycle. Such blocking can occur if the bridge needed by processor P1 to reach a memory location involved in the locked cycle has already posted a request for another agent, as explained in the Background of the invention.
[0030] If no bridge blocks the locked cycle, then block 90 is reached, and the locked cycle executes. If a bridge does block the locked cycle, then, in block 95, all queues in the bridges are emptied of their requests, by processing these requests. Then, in block 100 and 105, the locked cycle is attempted, and succeeds.
Significant Features
[0031] 1. The Background of the Invention provided an example of a deadlock situation. If a similar situation were to occur during operation of the invention, it would be resolved, and blocks 85 and 95 in FIG. 3 become particularly interesting. The resolution is attained by, in effect, giving precedence to the blocking cycle, which occupies the bridge needed by processor P1.
[0032] 2. Applicants point out that, if block 80, 90, or 105 is reached, the “locked” cycle executes, but without exerting a true lock. In these three cases, the locked cycle extends beyond the bus BA in FIG. 2 which is lockable by processor P1. Processor cannot lock the busses involved in these three blocks.
[0033] For example, if block 80 is reached, memory M2 in FIG. 2 will become involved. However, processor P1 has no access to the lock line L2. But the absence of a true lock does not cause a problem, because all processors and bridges were suspended, in block 60 of FIG. 3. Thus, no agents are operative at the time of P1's locked cycle, to create coherency problems.
[0034] In one embodiment, suspension of all processors and bridges may not be required. Suspension of only those which may interfere with the locked cycle can be undertaken.
[0035] 3. FIG. 4 illustrates one form of the invention. A computer contains module 155, which contains software, hardware, or both, which executes the logic illustrated in FIG. 3, and the other steps described herein.
[0036] Pseudo-code which can be used to write code which implements the invention follows. In the pseudo-code, acronyms are used, which are defined as follows:
[0037] PBR—Pending Buffer Remote;
[0038] IWB—Implicit Writeback;
[0039] P6—CPU—Processor 6 CPU (corresponds to P1 in the discussion above);
[0040] ALF—Arbitration, Lock, and Flush;
[0041] PBE—Processor Bus Engine;
[0042] BPRI—High Priority Bus Request;
[0043] CPU—Central Processing Unit;
[0044] AMC—Memory Controller;
[0045] PIRQ—Processor Inbound Request Queue;
[0046] IIRQ—I/O Inbound Request Queue;
[0047] IOBE—I/O Bus Engine;
[0048] IODB—I/O Data Buffer;
[0049] PIDB—Processor Inbound Data Buffer;
[0050] IrStatus—Inbound Request Status; and
[0051] OrStatus—Outbound Request Status.
Pseudo-Code
[0052] =Upon detecting a locked remote access, the Pending Buffer Remote (PBR) retries the lock cycle, but captures the cycle being requested.
[0053] =If an implicit writeback (IWB) occurs while attempting to retry the lock cycle, the PBR performs the IWB as it would any other IWB and aborts the delayed lock read. According to the P6 bus protocol the P6—CPU will retry the locked sequence even though the initial cycle had an IWB.
[0054] =The PBR begins the delayed lock read process by issuing a split lock request to the Arbitration, Lock, and Flush (ALF) logic and requesting the Processor Bus Engine (PBE) to assert BPRI. All delayed lock read accesses use the split lock arbitration logic. The BPRI is asserted to hold off CPU requests until the PBR is ready to allow the CPU to reissue the locked cycle.
[0055] =The PBR begins waiting for a split lock arbitration win or lose indication from the ALF logic.
[0056] =LOSE: If the ALF signals the PBR lost split lock arbitration, the PBR aborts the delayed lock read. This results in the PBR dropping its split lock arbitration request and signalling the PBE to negate BPRI. Also note that the ALF logic has some fairness logic built in to ensure each AMC would win its fair share of split locks even though the PBR drops its split lock arbitration request when it loses split lock arbitration.
[0057] =WIN: If the ALF signals the PBR won split lock arbitration, the PBR begins waiting for the QDRAINED signal from the ALF. While it is waiting, cycles may be pushed into the PIRQ; however, these can be handled normally since the CPU bus is not locked.
[0058] =QDRAINED: Once this is detected, all queues in both AMC's are empty and all 10 BUS BRIDGEs are blocked from issuing cycles to the P6_I/O bus. Now the PBR can push the captured lock cycle request into the IIRQ and the cycle is issued to the P6_I/O bus and the IO BUS BRIDGE will respond with either a retry or completion of the cycle.
[0059] =IO BUS BRIDGE RETRY: If the IO BUS BRIDGE retries the cycle, the ALF must begin allowing the IO BUS BRIDGEs to access the P6_I/O bus to allow the targeted IO BUS BRIDGE to complete any necessary cycles prior to being able to accept the locked access.
[0060] Also the I/O Bus Engine (IOBE) must disable its normal IO BUS BRIDGE retry limit counter and retry indefinitely. Timeout protection may be provided. The targeted IO BUS BRIDGE that retries the lock cycle will disable posting. Note that the ALF must allow all IO BUS BRIDGEs access to the P6_I/O bus since the AMC can not determine the targeted IO BUS BRIDGE. This could greatly lengthen the time it takes for the lock cycle to be accepted especially since posting is not disabled in the nontargeted IO BUS BRIDGES. There are no plans to use the MEMREQ/FLUSHREQ signals to force them to disable posting.
[0061] =AMC COMPLETE: If the cycle is to the other AMC, it will accept and complete the cycle (it never has to retry the cycle since QDRAINED indicates it has nothing it could collide with). The AMC would then continue handling this the same way as described below in the IO BUS BRIDGE COMPLETE bullet.
[0062] =IO BUS BRIDGE COMPLETE: Once the IO BUS BRIDGE completes the cycle the read data is put into the appropriate IODB and the IOBE gives the PBR IrStatus to signal cycle completion. The PBR now signals to negate BPRI to “sync” up with the previously retried lock cycle.
[0063] =BPRI NEGATED: The PBR now begins looking for the reissued lock cycle. It will retry all remote cycles (including local cycles requiring MICS) except IWB's which are processed normally.
[0064] =ABORT CASES: Aborts cause the PBR to stop processing the delayed locked read and essentially return to “idle” (i.e. signal ALF split lock arbitration is done, release LOCK on the P6_I/O bus, throw away the locked read data, etc.) The following are abort cases:
[0065] 1) If the original CPU comes back with a different address or a non-lock cycle,
[0066] (2) If the original CPU does not issue a cycle within Z1 clocks,
[0067] (3) Z2 abort cases in case this algorithm modified to support non deferred cycles
[0068] =LOCK REISSUED: PBR returns the normal OrStatus, must NOTpush the cycle into the IIRQ, issues the bus transfer command to move the data from the IODB to the appropriate PIDB. This allows the original lock to complete, finally locking the path from the CPU all the way to the device behind the IO BUS BRIDGE.
[0069] =LOCK SEQUENCE: The PBR processes other remote cycles in the locked sequence. Note that unlike the initial remotes access, it does not wait for the IrStatus from the IOBE before providing OrStatus to the PBE. If local accesses occur during this locked sequence, they are handled normally.
[0070] Numerous substitutions and modifications can be undertaken without departing from the true spirit and scope of the invention. What is desired to be secured by Letters Patent is the invention as defined in the following claims.
Claims
What is claimed is:
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.
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.
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.
Patent Citations (11)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US4965719 | 1990-10-01 | Shoens et al. | Applicant |
| US4984153 | 1991-01-01 | Kregness et al. | Applicant |
| US5339427 | 1994-08-01 | Elko et al. | Applicant |
| US5408629 | 1995-04-01 | Tsuchiva et al. | Applicant |
| US5535365 | 1996-07-01 | Barriuso et al. | Applicant |
| US5625779 | 1997-04-01 | Solomon et al. | Examiner |
| US5717876 | 1998-02-01 | Robertson | Examiner |
| US5734846 | 1998-03-01 | Robertson | Examiner |
| US5778235 | 1998-07-01 | Robertson | Examiner |
| US5787486 | 1998-07-01 | Chin et al. | Examiner |
| US6047316 | 2000-04-01 | Barton et al. | Examiner |