Browse Prior Art Database

Multi-Access First-In-First-Out Queue Using 370 Compare and Swap

IP.com Disclosure Number: IPCOM000103919D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 4 page(s) / 193K

Publishing Venue

IBM

Related People

Cadden, WS: AUTHOR [+2]

Abstract

A method for providing an efficient First-In-First-Out FIFO queueing model which supports concurrent adding and deleting from a queue in a tightly coupled processor environment is disclosed. All queue manipulation is implemented using IBM 370* Compare and Swap instructions (equivalent instructions could be used on other architectures). The algorithm being disclosed provides the FIFO queue without requiring any task to spin, or be blocked, to complete an update to the queue structure. Also to address multiple concurrent deletes, the queue manages when there is a surplus of data elements, or a surplus of requestor elements, as well as the transition between the two states.

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

Multi-Access First-In-First-Out Queue Using 370 Compare and Swap

      A method for providing an efficient First-In-First-Out FIFO
queueing model which supports concurrent adding and deleting from a
queue in a tightly coupled processor environment is disclosed.  All
queue manipulation is implemented using IBM 370* Compare and Swap
instructions (equivalent instructions could be used on other
architectures).  The algorithm being disclosed provides the FIFO
queue without requiring any task to spin, or be blocked, to complete
an update to the queue structure.  Also to address multiple
concurrent deletes, the queue manages when there is a surplus of data
elements, or a surplus of requestor elements, as well as the
transition between the two states.

      The implementation of a single logical queue involves two queue
headers; a primary and a secondary.  The primary queue header is a
double word, and the secondary, is a full word.  The compare and swap
instructions will be used to update both headers (CDS and CS,
respectively).  The primary header will be in either of two states,
depending upon which there is an excess of, at any point in time,
data receivers (more senders than receivers) or requestor elements
(more receivers than senders).  Data elements represent messages that
have been queued, and are ready for retrieval by subsequent requestor
tasks.  Requestor elements define requestor tasks that are currently
suspended, waiting for messages to arrive.

      Adding a data element to the queue will consist of first
attempting to access the primary header.  If the primary header is
unavailable, the data element will be added to the temporary
secondary queue.  The primary data queue will be maintained in a
first-in-first-out (FIFO) basis.  Maintenance in this case means that
entries will be added to the end of the list, and removed from the
front of the list.

      Removing a data element from the queue will consist of
attempting to remove the first data element from the primary queue.
If none are available, a requestor element will be added describing
the suspended task.  The requestor queue will be maintained in a
last-in-first-out (LIFO) basis.  The secondary header plays only a
minor roll when removing a data element.

      In the following descriptions, data elements contain pointers
to the application specific message that is being passed from one
task to another, and requestor elements define how to activate/assign
work to those tasks that are waiting to arrive.  The format of the
primary double word header is shown in Fig. 1.

      The State field indicates which there is more of at any given
time, data elements or requestor elements.  When the state field is
zero no-wait state), then there are more data elements than requestor
element.  When it is one (wait-state), there are more tasks
requesting elements than there are data elements to satisfy them.
The meaning of the field located in bit po...