Browse Prior Art Database

Serialization of Queue Access without Locks

IP.com Disclosure Number: IPCOM000108047D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 4 page(s) / 113K

Publishing Venue

IBM

Related People

Fakhouri, S: AUTHOR [+4]

Abstract

The scenario is as follows: o queues are singly linked. The last entry in the queue is "NULL" terminated. o entries are always added to the tail of a queue. o entries are always removed from the head of the queue. o there is a SINGLE "writer" for all the queues. o there is only ONE "reader" for a specific queue. o the "readers" have lower priority than the "writer" o the "writer" can NEVER be blocked by a "reader".

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

Serialization of Queue Access without Locks

       The scenario is as follows:
      o   queues are singly linked. The last entry in the queue is
"NULL" terminated.
      o   entries are always added to the tail of a queue.
      o   entries are always removed from the head of the queue.
      o   there is a SINGLE "writer" for all the queues.
      o   there is only ONE "reader" for a specific queue.
      o   the "readers" have lower priority than the "writer"
      o   the "writer" can NEVER be blocked by a "reader".

      The algorithm described herein provides a solution whereby the
"writer" is NEVER blocked by a "reader" and the "reader" always
defers to the "writer".

      Both the "writer" and "reader" have one critical section,
namely adding to an empty queue, and removing the last entry. This is
the only time that the writer and reader can collide. The reader
needs to know when the "writer" has entered its critical section so
the reader can defer processing until the writer is finished. A
semaphore solution is not viable since this may cause the writer to
be blocked by the reader.  The writer, therefore, becomes dependent
on readers dispatching priority, which is unacceptable.

      The algorithm presented herein has the following
characteristics:
      o   the reader never blocks the writer.
      o   the reader knows when the writer has entered its critical
section and defers processing until the writer is finished.

      In order to implement this algorithm an atomic operation to
update a storage location is required. The operation must be similar
to "compare and swap" 370/Assembler instruction or the "cs" system
routine on AIX*.  Essentially, the "compare and swap" operation
compares the content of a storage location with a "compare value", if
they are equal then the storage location is set to the new value.

      The queue structure is as follows:

                            (Image Omitted)

TAIL      pointer to the tail of the queue. Both the "reader" and
"writer" update this location. The updates are serialized via the
"compare and swap" operation.
HEAD      "readers" pointer to the head of the queue. Only the
"reader" updates this field, and only ONE "reader" is allowed to
remove an entry.
NEW HEAD  when an entry is being added to an empty queue, the
"writer" updates this field to the entry being added. This allows a
"reader" to determine the "head" of the queue.
ALGORITHM FOR ADDED AN NEW ENTRY (i.e., NEW_ENTRY)
NOTE:  Only the "writer" adds entries to to the queue.
         do {
              old_tail = tail
              if (old_tail != NULL )
                  /*
                   * queue is not empty
                   */
                  new_entry->next = NULL
            ...