Browse Prior Art Database

Concurrent Algorithm for Managing a First-In, First-Out Queue With Two-Way Pointers

IP.com Disclosure Number: IPCOM000122141D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 9 page(s) / 357K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

This article shows how to use compare-and-swap to implement a first- in, first-out (FIFO) queue with two-way pointers. Treiber 1 describes a number of ways of using the Compare-and-Swap instruction to implement concurrent data structures. Although [1] discusses FIFO queues, it does not show a general implementation of FIFO queues either with one-way pointers or with two-way pointers. The existing literature and [1] seem to hold the point of view that a general FIFO queue cannot be implemented efficiently with Compare-and-Swap. In [2, 3] it is suggested that one-way FIFO queues are possible to implement with Compare-and-Swap but it does not show the implementation.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 18% of the total text.

Concurrent Algorithm for Managing a First-In, First-Out Queue With
Two-Way Pointers

      This article shows how to use compare-and-swap to
implement a first- in, first-out (FIFO) queue with two-way pointers.
Treiber 1 describes a number of ways of using the Compare-and-Swap
instruction to implement concurrent data structures.  Although [1]
discusses FIFO queues, it does not show a general implementation of
FIFO queues either with one-way pointers or with two-way pointers.
The existing literature and [1] seem to hold the point of view that a
general FIFO queue cannot be implemented efficiently with
Compare-and-Swap.  In [2, 3] it is suggested that one-way FIFO queues
are possible to implement with Compare-and-Swap but it does not show
the implementation.  A means for implementing a general FIFO queue
with one-way pointers that permits a multiplicity of processors to
enqueue and dequeue concurrently is discussed in [4].

      The preferred implementation of FIFO queues is with two-way
pointers.  The pointer in the reverse direction is redundant and is
not useful under normal conditions, but is required for recovery in
error states when the forward pointer contains an incorrect value.
Prior to this writing no algorithm has been published for concurrent
two-way FIFO queues implemented with Compare-and-Swap.  Here we give
an implementation of such an algorithm.  The algorithm is unusual in
that no process waits for another.  If a condition exists in which
process A is blocked from progress because it must await an action by
process B, process A hands over its task to process B and continues
with other tasks.  When B performs the enabling action, B carries on
by executing the outstanding task of process A.  This approach
enhances both performance and reliability of operation because
process A does not expend idle cycles while waiting for process B,
and is not blocked indefinitely if process B fails.  In this sense,
the algorithm is of a type called nonwaiting.  However, the algorithm
can be blocked for an indefinite time if a processor fails when the
queue is in a particular state.  The 2-way links provide a means for
recovery from the blocked state in this case.
THE ALGORITHM

      The data structure is shown in Fig. 1.  Each cell in the queue
has two pointers, Predecessor and Successor, which point to the prior
and next items on the queue.  The queue has a unique header cell
called Head.  The empty queue is shown in Fig. 1a.  This queue has
Head.  Predecessor = Head and Head.Successor = Head.

      A queue with two elements is shown in Fig. 1b.  Head is the
predecessor of the first element and the successor of the last
element.  To find the first element of the queue, access Head and
read the value of Head.Successor.  This action is performed by a
Dequeue process.  To find the last element of the queue, access Head
and read the value of Head.Predecessor.  This action is performed by
an Enqueue process.
B...