Browse Prior Art Database

Multiple-Producer, Single-Consumer Queue using Compare-and-Snap

IP.com Disclosure Number: IPCOM000106873D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 95K

Publishing Venue

IBM

Related People

Armstrong, WJ: AUTHOR [+3]

Abstract

In multi-processing and multi-programming computer systems, it is frequently necessary for one or more "processes" (the producers) to enqueue messages to be handled by another process (the consumer). These messages typically need to be kept in FIFO (First-In, First-Out) order. Additionally, a mechanism is needed for knowing when to "wake up" the consumer process after enqueueing a new message, in the case where it has "gone to sleep" due to the queue having been empty.

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

Multiple-Producer, Single-Consumer Queue using Compare-and-Snap

      In multi-processing and multi-programming computer systems, it
is frequently necessary for one or more "processes" (the producers)
to enqueue messages to be handled by another process (the consumer).
These messages typically need to be kept in FIFO (First-In,
First-Out) order.  Additionally, a mechanism is needed for knowing
when to "wake up" the consumer process after enqueueing a new
message, in the case where it has "gone to sleep" due to the queue
having been empty.

      The basic queue is represented as a linked list of queue
elements in memory, anchored from a pointer also in memory.  Each
element is assumed to contain a link pointer, called NEXT, which is
located at the same place in each element (e.g., in the first word of
each element).  There are two distinguished values, called EMPTY and
FENCE, which are selected such that no queue element will ever have
one of these values as its address (e.g., one could pick the values 0
and 1).  An empty queue is represented by having the value EMPTY
stored in the queue anchor pointer.

      To enqueue an element, the element is simply
compared-and-swapped onto the linked list; if the previous value of
the anchor point was EMPTY, then the consumer process is "awakened"
using whatever means are appropriate for the operating environment.

      Whenever it is "awakened", the consumer process simply
compares-and-swaps the FENCE value with the queue anchor, thereby
dequeueing the entire queue.  It then proceeds to process the queue
elements at its leisure.  Note that, since the queue anchor now has
the value FENCE rather than EMPTY, subsequent enqueue operations will
not erroneously attempt to awaken the (already awake) consumer
process.  After processing the elements that it acquired from the
queue, the consumer inspects the queue anchor.  If it still contains
the FENCE value, the consumer compares-and-swaps it with the EMPTY
value; if this is successful, the consumer "goes to sleep".  If this
compare-and-swap is not successful, or if the queue anchor does not
contain the FENCE value, then additional elements have been enqueued,
and the consumer proceeds as if it had just been awakened.

      The following variations ("embellishments") are also disclosed:

o   Extending the queue anchor to include the address of the consumer
    process and the method used to "wake up" the process.  This
    permits common enqueueing and dequeueing code to be used for
    diverse queues with different...