Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1998-12-03
2001-05-22
Lefkowitz, Sumati (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S120000, C710S120000, C710S241000
Reexamination Certificate
active
06237055
ABSTRACT:
BACKGROUND INFORMATION
1. Field of the Invention
This invention is generally related to computer bus transactions, and more particularly to techniques for avoiding livelock when performing a relatively long stream of transactions across a bridge.
2. Description of Related Art
Peripheral devices such as disk controllers or network interface cards often generate a long stream of read or write transactions. The transactions are often directed at a main memory of the computer system. In certain architectures, the transactions must cross a bridge between a system bus to which the peripheral devices are coupled and the memory. The bridge has an inbound pipe for temporarily holding the data and request packets of multiple transactions before they are forwarded to the memory.
Sometimes the pipe becomes full before the stream can be completed. This may occur because the depth of the pipe is relatively small with respect to the number of transactions in the stream, and/or because the memory is relatively slow in emptying the pipe. When this happens, the peripheral device is refused access to the bridge and its inbound pipe. According to some bus arbitration protocols, the device must then relinquish the system bus to give a different device or agent a chance to own the bus. This is known as fair arbitration.
In certain situations, the pipe may still be full when a second agent is granted ownership of the bus. Thus, if the second agent also needs to access the pipe, then the bridge will refuse access. As required by fair arbitration, the second agent must now relinquish the bus so that other agents may then be granted ownership of the bus.
Eventually, the first agent being the peripheral device regains ownership of the bus. By now, however, assume that the pipe has emptied some, such that the first agent can resume its transaction stream. But since the stream is relatively long, the pipe once again becomes full and the first agent must relinquish the bus. Although arbitration may now move to the second agent, the pipe may still be full and the bridge must again refuse access to the second agent. The cycle of the previous paragraph may repeat several times, thereby starving the second agent while allowing the first agent to progress with its long transaction stream.
The undesirable condition described above is known as livelock, where the second agent cannot progress even though it is granted ownership of the bus. In addition to reducing the performance of the second agent, livelock wastes valuable bus cycles when the second agent requests and is granted the bus only to be refused access to the bridge, with no data being transferred over the bus.
One possible solution for dealing with the livelock problem is configuring the bridge with a larger pipe so that the entire stream can be accepted by the bridge. This may be prohibitively expensive, because the transaction streams described above may be very long such that no practical pipe could hold the entire stream. Alternatively, the memory and peripheral devices may be reconfigured to split the transaction stream into smaller portions, allowing ownership of the bus to pass to another agent between portions. This solution, however, requires altering many different types of memory and peripheral devices, all of which may be developed by different manufacturers and according to different standards. This may also undesirably increase the overall cost of ownership of the system by requiring many components of the system to be redesigned.
Therefore, there is a need to remedy the livelock condition described above using a relatively low-cost technique that does not require extensive reconfiguration of existing peripheral devices.
SUMMARY
What is disclosed is an arbiter comprising logic circuitry configured to delay granting bus ownership to an agent X in response to receiving a first signal which indicates that a device coupled to the bus is not available to service transactions directed at the device over the bus.
These as well as features and advantages of other embodiments of the invention will be more apparent by referring to the claims, the written description, and the drawings below.
REFERENCES:
patent: 5146564 (1992-09-01), Evans et al.
patent: 5239651 (1993-08-01), Sodos
patent: 5469435 (1995-11-01), Krein et al.
patent: 5511165 (1996-04-01), Brady et al.
patent: 5546546 (1996-08-01), Bell et al.
patent: 5625779 (1997-04-01), Solomon et al.
patent: 5721839 (1998-02-01), Callison et al.
patent: 5764929 (1998-06-01), Kelley et al.
patent: 5850530 (1998-12-01), Chen et al.
patent: 5915104 (1999-06-01), Miller
patent: 5933616 (1999-08-01), Pecone et al.
patent: 6026460 (2000-02-01), David et al.
Solaris, E. & Willse, G., “PCI Platform Hardware Architecture,” PCI Hardware and Software Architecture & Design, 3rd Edition, Annabooks (1996), pp. 21-23.
Bogin Zohar
Gadagkar Ashish
Lent David D.
Trieu Tuong
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Lefkowitz Sumati
LandOfFree
Avoiding livelock when performing a long stream of transactions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Avoiding livelock when performing a long stream of transactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Avoiding livelock when performing a long stream of transactions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2547206