Browse Prior Art Database

Last-In-First-Out and First-In-First-Out Process Server Queue

IP.com Disclosure Number: IPCOM000116903D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 67K

Publishing Venue

IBM

Related People

Matsakis, NC: AUTHOR

Abstract

Disclosed is a computer program that uses single threaded queue techniques for adding to a queue and double threaded queue techniques for processing the queue. The result is a First-In-First-Out (FIFO) server work queue that has high performance, high integrity, and uses a minimal amount of storage (memory).

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

Last-In-First-Out and First-In-First-Out Process Server Queue

      Disclosed is a computer program that uses single threaded queue
techniques for adding to a queue and double threaded queue techniques
for processing the queue.  The result is a First-In-First-Out (FIFO)
server work queue that has high performance, high integrity, and uses
a minimal amount of storage (memory).

      Since a server work queue contains critical work related data,
is it essential that it be rebuildable in the event of an error.
Since managing the queue impacts server and client performance, it is
critical that adding to and processing of the queue is done in a high
performance manor.  In cases where many queues are required, it is
also essential that as little storage as possible be used for the
queue header(s).

      Single Headed/Single Threaded (SHST) queues have a header
pointer with each element having a single forward pointer.  Double
Threaded/Double Headed (DTDH) queues have a header pointer to the
first element, one to the last element, and each element has a
forward and backward pointer.  Because DTDH queues can be traversed
in either direction, they are more re-buildable then SHST queues.
However, adding to DHDT requires the use of a lock to serialize the
update of the two headers and the backward pointer of the old first
element.  Obtaining and holding the lock impacts clients and the
server who may also be trying to update the queue.  The Compare and
Swap (CS) instruction can be used to serialize the addition of
elements to the end of a SHST queue with good performance.  Since a
double threaded queue can be processed...