Browse Prior Art Database

First In/First Out Queuing Technique Using Compare and Swap

IP.com Disclosure Number: IPCOM000084303D
Original Publication Date: 1975-Oct-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 29K

Publishing Venue

IBM

Related People

Taradalsky, M: AUTHOR

Abstract

Described is a method for performing first in/first out (FIFO) queuing without the use of a software lock beyond the synchronization provided by the IBM S/370 compare and swap instruction. The method provides: A. FIFO dispatching. B. Quick cell storage management. C. Quick element management (example: Save Areas).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 89% of the total text.

Page 1 of 3

First In/First Out Queuing Technique Using Compare and Swap

Described is a method for performing first in/first out (FIFO) queuing without the use of a software lock beyond the synchronization provided by the IBM S/370 compare and swap instruction. The method provides: A. FIFO dispatching.

B. Quick cell storage management.

C. Quick element management (example: Save Areas).

The example in the drawing depicts the technique as it applies to dispatching elements in a system control programming system.

The following method places elements on the queue shown in the drawing:
TOP: IF QUEUE(NA) not = EMPTY THEN

GO TO OVERFLOW;

ELSE

DO;

A=NA-1;

B=NA;

IF A < 0

THEN

NA=TL*; * The IBM S/370 compare and

ELSE swap Instruction used.

NA=A*;

IF COMPARE AND SWAP FAILED

THEN GO TO TOP;

QUEUE(B)= ELEMENT*;

IF COMPARE AND SWAP FAILED

THEN GO TO TOP;

END;

The queue overflow control is not a feature of this method. There are various methods that can be employed.

The following method removes elements from the queue: TOP: IF QUEUE(ND)=EMPTY THEN

GO TO EMPTYQ:

ELSE

DO;

A=ND-1;

B=ND;

IF A < 0

THEN

ND=TL*;

ELSE

ND=A*;

IF COMPARE AND SWAP FAILED

1

Page 2 of 3

THEN GO TO TOP;

TABLE(B)=EMPTY*;

IF COMPARE AND SWAP FAILED

THEN GO TO TOP:

END.

The EMPTYQ logic is not included. Various methods are available.

In a quick cell management technique, the ND field indicates the next cell given to the next requestor; the NA field indicates the element given to the next cell to be returned. An advantage of...