Browse Prior Art Database

Double-Threaded Enqueue Without Serialization

IP.com Disclosure Number: IPCOM000049494D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 68K

Publishing Venue

IBM

Related People

Goldstein, BC: AUTHOR [+2]

Abstract

A mechanism is provided, as shown in Figs. 1 and 2, that avoids serialization of concurrent ENQ'ers while on ENQ is in progress.

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 100% of the total text.

Page 1 of 2

Double-Threaded Enqueue Without Serialization

A mechanism is provided, as shown in Figs. 1 and 2, that avoids serialization of concurrent ENQ'ers while on ENQ is in progress.

Before describing this, some definitions and assumption are in order.

A "double-threaded queue" 1) assumes FIFO discipline,

2) each item on queue has a forward (FWD) and backward

BKWD) pointer, and

3) the Queue Anchor has a TAIL pointer (pointer to latest

item on queue).

"Atomically" refers to the ability to set (or assign) to some set of variables a new set of values based upon the previous values of the variables (e.g., CS (Compare and Swap) or CDS (Compare Double and Swap) in the IBM System/370). This is illustrated pictorially in Fig. 1.

The algorithm is set forth in the flow chart of Fig. 2.

Acronyms: QI (identical to) item to be placed on queue.

QA (identical to) Queue Anchor.

FSQI (identical to) first item on Spill Queue.

SQI (identical to) oldest item on Spill Queue.

SQI is used as a working variable in the

algorithm.

1

Page 2 of 2

2

[This page contains 6 pictures or other non-text objects]