Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-03-08
2003-06-03
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S036000, C710S112000, C711S119000
Reexamination Certificate
active
06574689
ABSTRACT:
FIELD
The present invention is generally related to queuing systems for microprocessors and other environments. More specifically, an embodiment of the present invention includes a method for queuing and servicing requests that prevents the occurrence of live-lock conditions.
BACKGROUND
Computer processors maintain queues for various purposes. These queues are managed using a range of different strategies, depending on the queue's intended uses. First-In-First-Out (FIFO) queues, for example, are used where queued items must be serviced in the order in which they are received. Find-First-One (FF1) queues are a slightly different example. FF1 queues are used where queue items may be served without regard to the order in which they arrive. The entity that services an FF1 queue is free to retrieve any queue item that is ready for service. Typically, this means that the servicing entity simply retrieves the first queue item that is located and is ready for service. This is true even if that item was just added to the queue.
For many applications, queues are maintained using fixed register sets. Thus, an exemplary queue might be maintained in a set of eight, ten or some other number of registers. In the typical case, each register has an associated valid bit. Each bit is turned on to indicate that its associated register contains a queue item that is ready for servicing. The servicing entity toggles these valid bits when it removes items from the queue.
A representative queue of this type is designated
100
in FIG.
1
. Queuing system
100
includes a series of registers, of which registers
102
a
through
102
e
are representative. Each register
102
has an associated valid bit
104
. For a typical FF1 strategy, register
102
d
would be the first register to be serviced in queuing system
100
(since it is the first register
102
having a set valid bit
104
). The servicing entity would clear valid bit
104
d
to indicate the servicing of register
102
d
. Assuming no other changes to queuing system
100
, register
102
e
would be the next register to be serviced.
FF1 queues provide a simple, effective and relatively inexpensive queuing strategy. FF1 queuing may be used wherever there is no absolute requirement that queued items be serviced in a particular order. Unfortunately, FF1 queuing can also lead to the creation of a condition known as live-locking where queued items may wait for extended or even indefinite periods for servicing.
Live-locking can be explained by reference to queuing system
100
of FIG.
1
. As noted previously, queuing system
100
includes at least two registers (
102
d
and
102
e
) that are ready for servicing. The FF1 strategy services register
102
d
first. It is possible that a new item will be added to the queue while register
102
d
is being serviced. This new item may be placed in any register
102
including now available register
102
d
. In fact, if new items arrive at a fast enough rate it is possible that register
102
d
(or a preceding register
102
) will always be valid when the servicing entity inspects queuing system
100
. If this is the case, the probability of selecting following registers
102
(such as register
102
e
) becomes diminished. In some cases, the repeated availability of preceding registers
102
will entirely prevent the servicing of subsequent registers
102
. This is a live-lock condition.
The potential for live-lock conditions is a major drawback to existing FF1 queuing systems. Within these systems, it is possible for valid items to remain queued indefinitely. In most cases, this means that requested work is not getting done or service is being delayed.
Based on the foregoing, it may be appreciated that there is a need for methods that prevent live-lock conditions in queuing systems. This need is especially acute where FF1 and similar queuing strategies are employed.
SUMMARY
An embodiment of the present invention provides a queuing system that avoids live-locking. A representative implementation of this system 1) selects a first queue item pointed to by a rotating pointer if the first queue item is ready to be serviced, 2) selects a second queue item pointed to by a find-first-pointer if the first queue item is not ready to be serviced, and 3) updates the rotating pointer so that the rotating pointer points to a third queue item.
Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.
REFERENCES:
patent: 5060154 (1991-10-01), Duncan, IV.
patent: 5150463 (1992-09-01), Ward et al.
patent: 5426750 (1995-06-01), Becker et al.
patent: 5490280 (1996-02-01), Gupta et al.
patent: 5625800 (1997-04-01), Brayton et al.
patent: 5892957 (1999-04-01), Normoyle et al.
patent: 6145054 (2000-11-01), Mehrotra et al.
Miin Jeen
Zaidi Nazar A.
Gaffin Jeffrey
Intel Corporation
Mai Rijue
Pillsbury & Winthrop LLP
LandOfFree
Method and apparatus for live-lock prevention 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 and apparatus for live-lock prevention, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for live-lock prevention will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124689