Browse Prior Art Database

Management of FIFO Queues With Backlinking Done by the Dequeuer

IP.com Disclosure Number: IPCOM000099831D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 2 page(s) / 63K

Publishing Venue

IBM

Related People

Brown, PJ: AUTHOR [+2]

Abstract

Disclosed is an algorithm for managing doubly-linked FIFO queues using Compare and Swap against the queue header as the only serialization interlock.

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

Management of FIFO Queues With Backlinking Done by the Dequeuer

       Disclosed is an algorithm for managing doubly-linked FIFO
queues using Compare and Swap against the queue header as the only
serialization interlock.

      The algorithm permits multiple enqueuers but only one dequeuer
to simultaneously manipulate the queue.  The users of the queue may
be executing on separate processors and may be executing with
interrupts enabled.  Previous algorithms require at least either a
lock separate from the queue header or the use of higher level
interlocks.  See the System/370 and System/370 XA Principles of
Operation section titled Multiprogramming and Multiprocessing
examples.

      Some previous algorithms required additional interlocks because
enqueuing an element changed two disjoint storage locations:  the
queue header and a pointer in a queue element.  While one but not
both of the storage elements were changed, the queue was not properly
linked.  Other previous algorithms used a higher level interlock to
avoid the need to change more than one storage location.  The
disclosed algorithm, as shown in the figure, allows the enqueuers to
change only one storage location by delegating the change of the
second location to the dequeuer.

      The enqueuer adds an element by storing the contents of Newest
into the new element's ForeChain and then using Compare and Swap to
store the element's address into Newest.

      If, when attempting to remo...