Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1997-12-16
2001-09-18
Dharia, Rupal (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S108000, C710S120000, C710S113000, C710S120000, C710S200000, C709S210000, C711S151000
Reexamination Certificate
active
06292860
ABSTRACT:
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
FIG. 1
illustrates a bus
3
in a computer (not shown). Processors P
1
-P
4
have access to the bus
3
. A memory controller C
1
is connected to the bus
3
, and controls traffic to, and from, memory M
1
. Bridges B
1
-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.
Sometimes a processor P, such as processor P
1
, will impose a “lock” on the bus
3
, by activating lock line L. The lock prevents all other agents, such as the other processors P
2
-P
4
, and the bridges B, from gaining access to the bus
3
. The lock allows the processor P
1
to perform a sequence of operations on memory, without interference by the other processors or the bridges.
As a simple example, processor P
1
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.
If the lock were not imposed in step (1), then, immediately after processor P
1
read the data at address X, another processor, such as P
2
, may read the same data. Then, after the processor P
1
replaced the data with the modified data in step (4), the replaced data may be inconsistent with that held by processor P
2
. A data coherency problem would arise: the data held by processor P
2
would not be an accurate copy of data at address X. The lock prevents this problem from occurring.
In a multi-bus system, the situation becomes more complex.
FIG. 2
illustrates busses BA, BB, and BC. Processors P
1
-P
4
are connected to bus BA. Processors PS-P
8
are connected to bus BC. Bridges B
1
-BN are connected to bus BB. Controllers C
1
and C
2
control traffic to, and from, memories M
1
and M
2
, respectively.
One problem which can arise in this system is that a program may run on processor P
1
which writes words outside memory M
1
, such as to memory M
2
, through bus BC. However, processor P
1
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 M
2
which is being altered by processor P
1
.
Another problem can arise. Assume that processor P
1
issues a lock, and that P
1
's operations, which follow the lock, involve writing a word through bridge B
1
, to a memory address on the “other side”
6
of bridge B
1
.
Assume also that, independent of processor P
1
's activities, (1) an agent A
1
posts a write operation which requires involvement of bridge B
1
for completion, and that (2) this write operation involves a data address which processor P
1
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.
Now, a deadlock has occurred. Under the rules of operation, once processor P
1
has issued the lock, processor P
1
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 A
1
is blocked.
However, processor P
1
needs bridge B
1
. But, under other rules of operation, bridge B
1
has become irrevocably involved in the write operation posted by agent A
1
. In effect, bridge B
1
has become a “one-way street” running in the direction of the write operation of agent A
1
. This direction is opposite the direction required by processor P
1
.
P
1
has blocked the merging needed by A
1
, and A
1
has blocked the bridge needed by P
1
. No further action can be taken, and the system has become stalled, or deadlocked.
OBJECTS OF THE INVENTION
An object of the invention is to provide an improved multi-bus computer system.
A further object of the invention is to provide a system for preventing deadlocks in a multi-bus computer system.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 4965719 (1990-10-01), Shoens et al.
patent: 4984153 (1991-01-01), Kregness et al.
patent: 5339427 (1994-08-01), Elko et al.
patent: 5408629 (1995-04-01), Tsuchiva et al.
patent: 5535365 (1996-07-01), Barriuso et al.
patent: 5625779 (1997-04-01), Solomon et al.
patent: 5717876 (1998-02-01), Robertson
patent: 5734846 (1998-03-01), Robertson
patent: 5778235 (1998-07-01), Robertson
patent: 5787486 (1998-07-01), Chin et al.
patent: 6047316 (2000-04-01), Barton et al.
Batchler Bobby W.
Cochcroft, Jr. Arthur F.
McDonald Edward A.
Reams Byron L.
Scrivener Harry W.
Dharia Rupal
NCR Corporation
Welte Gregory A.
LandOfFree
Method for preventing deadlock by suspending operation of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for preventing deadlock by suspending operation of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for preventing deadlock by suspending operation of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2508496