Arbitration methods to avoid deadlock and livelock when...

Details Arbitration methods to avoid deadlock and livelock when... Arbitration methods to avoid deadlock and livelock when...

1998-12-03

2001-03-13

Myers, Paul R. (Department: 2781)

Electrical computers and digital data processing systems: input/

Intrasystem connection

Bus access regulation

C710S112000, C710S120000

Reexamination Certificate

active

06202112

ABSTRACT:

BACKGROUND INFORMATION
This invention is generally related to computer systems and more particularly to techniques for avoiding deadlock and livelock when performing bus transactions across a bridge.
Computer systems use a bridge between two buses to allow devices on one bus to communicate with devices on the other bus.
FIG. 1
shows such a conventional computer system
102
. The system
102
has one or more processors
104
coupled to a host bus
105
. The host bus
105
and the processor
104
may be pipelined. A main memory
112
normally comprising Dynamic Random Access Memory (DRAM) is provided for storing programs and data used by the processor
104
and by peripheral devices. The memory
112
can be accessed by the processor
104
and by other devices via a host bridge
108
. To speed program execution by minimizing accesses to the memory
112
, a cache
114
(which may be internal to the processor
104
) is coupled to the host bus
105
.
The host bridge
108
also handles transactions between devices on the host bus
105
and those on a system bus
116
. The system bus
116
may be one which complies with the currently popular Peripheral Components Interconnect (PCI) Specification, Rev. 2.1, Jun. 1, 1995. A number of slots are provided on the system bus
116
to receive PCI devices such as mass storage controller cards and network interface cards. The host bridge
108
also supports transactions between a graphics device
122
and a device on the system bus
116
.
The PCI-based example in
FIG. 2
, will be used to demonstrate some problems with the conventional system
102
. Read and write transactions across the bridge
108
consist of several access cycles. For instance, posted write transactions involve at least two access cycles. The first cycle is on the initiating side of the bridge (e.g., on the host bus
105
) during which a transaction request packet is accepted by the bridge and placed in an in-order queue (IOQ)
222
. Thereafter, the first cycle may be completed by transferring the request packet and its associated data to a host bridge PCI outbound pipe
226
(PCI
0_OUT) that operates in a first in first out (FIFO) manner. Once the first access cycle is completed, a second access cycle may begin on the system (PCI compliant) bus 116 once the packet reaches the head of PCI
0_OUT, to transfer the associated data to a target on the system bus 116. Accesses to the main memory 112 have the additional requirement that the cache 114 be checked for the most recent copy of the data being accessed. For instance, a write to a line in main memory 112 requires invalidating or updating the corresponding line in the cache 114. These data coherency operations require the host bus to be available to check the cache 114.
Modern computer systems operating as network servers or workstations featuring the architecture of FIG.
1
and
FIG. 2
are expected to handle a large number of transactions that cross a bridge. When one side of the bridge is subjected to a relatively greater number of transactions than another side, the large number of transactions have the potential to create a deadlock. This is a very serious and usually fatal condition in that the system must normally be shut down if deadlock occurs.
In
FIG. 2
, deadlock may occur when the cache
114
must be checked as part of an upstream transaction PMW-4 which is at the head of a host bridge PCI inbound pipe (PCI
0_IN) which is full. The host bus 105 is not available due to an already pending access cycle for a downstream transaction PW-
3. The pending access cycle for PW-3 is stalled and cannot be completed until there is space in PCI
0_OUT to accept the transaction request and associated data packets. However, PCI
0_OUT has also become full, perhaps because target devices on the PCI bus 116 cannot drain PCI
0_OUT as quickly as transactions from the IOQ 222 and a host bridge PCI inbound pipe PCI
1_IN are enqueued. This may be because a downstream transaction PW-
1 directed at the device
232
on the PCI bus
116
cannot be completed until an upstream memory transaction PMW-2 in the same device has completed. This is an example of an outbound-inbound dependency that certain older peripheral devices such as legacy devices exhibit, where an inbound request cannot be accepted (even though the inbound pipe PCI
2_IN is empty) until an existing transaction PMW-
2 at the head of its outbound pipe PCI
2_OUT has been completed. There are various other situations that pose the inbound/outbound dependency. In all of these situations, since the host bus 105 is not available, PCI
0_IN in the bridge 108 cannot be drained and remains full, such that PMW-
2 is refused service. Therefore, there is a deadlock as the PW-3 cycle is stuck on the host bus
105
with no data transfer occurring.
One way to avoid the above-described deadlock condition is to reconfigure the peripheral device
232
to eliminate its inbound-outbound dependency to allow PW-1 to proceed before PMW-2 has completed. However, such a technique would require manufacturers to significantly modify current and older peripheral devices, thus substantially increasing the cost of the computer system. Therefore, there is a need for a technique of avoiding deadlocks that does not require expensive modifications in peripheral devices.
SUMMARY
Accordingly, an embodiment of the invention is directed at a bridge having an outbound pipe for buffering transaction information and data being transported from various devices to a bus. The bridge has an arbiter for granting requests associated with these devices to access the outbound pipe for transferring the transaction information and data into the pipe. The bridge generates a reject signal in response to an initial request associated with an initial transaction from a first one of the devices if the outbound pipe is unavailable to accept further transaction information or data. The bridge has response control logic for generating a retry response for the initial transaction in response to the reject signal. The bridge is able to assert a stamp signal in response to the reject signal. The arbiter in response to the stamp being asserted waits, without granting any other requests from devices having lower priority than the first device to access the outbound pipe, until a subsequent transaction from the first device makes progress.
These and other features and advantages of the different embodiments of the invention will be apparent by referring to the drawings, detailed description and claims below.


REFERENCES:
patent: 4796022 (1989-01-01), Schenkel et al.
patent: 4975829 (1990-12-01), Clarey et al.
patent: 5278828 (1994-01-01), Chao
patent: 5535340 (1996-07-01), Bell et al.
patent: 5611058 (1997-03-01), Moore et al.
patent: 5754802 (1998-05-01), Okazawa et al.
patent: 5949980 (1999-09-01), Lee et al.
patent: 5961623 (1999-10-01), James et al.
patent: 5974465 (1999-10-01), Wong
patent: 5999969 (1999-12-01), Holmes et al.

Affiliated with

Also associated with

Rating

Arbitration methods to avoid deadlock and livelock when... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitration methods to avoid deadlock and livelock when..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration methods to avoid deadlock and livelock when... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2449897