Managing bus transaction dependencies

Details Managing bus transaction dependencies Managing bus transaction dependencies

2000-09-11

2004-02-17

Vo, Tim (Department: 2189)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S057000, C710S025000, C710S200000, C710S220000

Reexamination Certificate

active

06694390

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains generally to computer systems. In particular, it pertains to avoiding deadlocks and livelocks in the dispatching and execution of bus transactions.
2. Description of the Related Art
In a continuing attempt to increase performance, many computer systems send bus transactions to a centralized input/output (I/O) controller, which uses multiple queues to dispatch each transaction to one of several different interfaces in the system, and which coordinates execution of various stages of the transaction.
FIG. 1
shows a portion of a conventional computer system containing such a centralized I/O controller
10
, which controls the transfer of commands and data between processors
11
,
12
, graphics controller
13
, memory controller
14
, and peripheral bus controller
15
. Each is connected to I/O controller
10
over a separate interface
21
,
23
,
24
and
25
, respectively, each of which may be a bus.
FIG. 2
shows a more detailed view of I/O controller
10
. A request from one of the CPU's
11
,
12
to initiate a transaction is decoded by request decoder
111
, which loads the request into In-Order Queue (IOQ)
112
. IOQ
112
keeps the various phases of multiple transactions executing in the correct order, so that a given phase of a subsequent transaction will not be executed before the same phase of a preceding transaction. This is done by placing the request for the transaction into dispatch queue
113
and response queue
115
, and for memory requests, into snoop queue
117
and snoop response queue
119
. Although shown and discussed as four separate queues, these may actually be a single queue with four separate pointers indicating which location is considered to be the exit of the queue for each function.
When an indicator exits dispatch queue
113
, it triggers dispatcher
114
to send the transaction to the correct interface
23
,
24
or
25
, through the associated command queue
130
,
140
, or
150
, which queues up the transaction before it is presented to the respective interface. The transactions are “drained” from the command queues as the transactions are serviced by the receiving circuitry. When the target device responds, that response clears the associated request from the exit of response queue
115
. If the request is to a memory system with cache, a snoop function and its response are also processed through queues
117
,
119
. Thus a transaction is completed only when the relevant request has been cleared from all queues in IOQ
112
.
Memory transactions through queue
150
are typically guaranteed to complete within a specified time, and occupy processor bus
21
until the transaction is complete. However, transactions through downstream queues
130
and
140
(“downstream transactions”) have no guaranteed completion time, and time to complete can vary greatly. Since a target device may not always be ready to accept a command, alternative responses are available to prevent this condition from clogging up the queues. A retry response is a response from the I/O controller to the requestor that tells the requester to abort the request and try again later. This response clears that particular request from all queues in IOQ
112
. When the request is retried at a later time, it enters IOQ
112
as a new request. A delayed transaction response includes a retry response, but the I/O controller
10
and the target interface also commit resources to the eventual retry, thus blocking those resources from other transactions and potentially forcing those other transactions to be reattempted. Only one transaction may be delayed at a time. A deferred response does not require a reattempt by the initiator—the I/O controller notifies the initiator that the target device will provide the requested data when it is ready, and the I/O controller will pass the data on to the initiator using a special transaction called a deferred reply. Although the transaction is complete when the request is deferred, the operation continues until the deferred reply, and various resources may remain committed until the deferred reply. In all these cases, the request is cleared from the queues in IOQ
112
when the retry/delay/defer status is created by the response from the I/O controller to the requester. A request can be initially assigned an identifier, so that if it is reattempted with the same identifier, all affected devices can correlate the reattempt with the original request.
The interactive nature of the various queues and associated resources can cause both deadlocks and livelocks to occur, based on conflicting resource dependencies. As applied to the queue structure, a deadlock occurs when the output of two or more queues cannot be cleared because the data to initiate a clearing action in each is blocked within the other queue. A livelock occurs when a requested transaction cannot make progress in one queue because it depends on another queue which, although moving, is always full and thereby repeatedly forcing some type of reattempt. In brief, a livelock creates an ongoing bottleneck in the system, which may eventually go away in normal operation after an unacceptably long time, while a deadlock causes a blockage in the system that will not go away without some type of overt corrective action.
Some deadlocks and livelocks are generic to a system and can be avoided through proper overall system design. Others are only seen during specific, unusual circumstances and must be addressed with a customized solution on a case-by-case basis.


REFERENCES:
patent: 5467295 (1995-11-01), Young et al.
patent: 5887194 (1999-03-01), Carson et al.
patent: 5930485 (1999-07-01), Kelly

Affiliated with

Also associated with

Rating

Managing bus transaction dependencies does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Managing bus transaction dependencies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Managing bus transaction dependencies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3336387