Browse Prior Art Database

Single Thread ENQ/Double Thread DEQ of FIFO Queue

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

Publishing Venue

IBM

Related People

Goldstein, BC: AUTHOR [+3]

Abstract

The basic premise set forth is to single thread ENQ's (without the usage of locks) and perform the double threading on DEQ. Thus, if ENQ's arrive faster than they are initially taken off, the ENQ paths are fast and without serialization, while the double chaining only occurs on the first DEQ (optimal case).

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

Single Thread ENQ/Double Thread DEQ of FIFO Queue

The basic premise set forth is to single thread ENQ's (without the usage of locks) and perform the double threading on DEQ. Thus, if ENQ's arrive faster than they are initially taken off, the ENQ paths are fast and without serialization, while the double chaining only occurs on the first DEQ (optimal case).

Before describing this, certain definitions and assumptions are given. A double-threaded queue: 1) assumes FIFO (first-in, first-out) discipline, and

2) each item on queue anchor has a

HEAD pointer (pointer to oldest item on queues) and TAIL pointer (pointer to latest item on queue).

A pictorial representation of a double-threaded queue is set forth in Fig. 1.

The algorithms, as shown in Figs. 1 and 2 for ENQ of queue item and DEQ of a queue item, are: QI (identical to) item to be placed on queue

NQI (identical to) next older item on queue

ENQ:

FWD(QI) TAIL (QA)

Atomically

Count (QA) Count (QA) + 1

and

Tail (QA) @ QI

1

Page 2 of 2

2

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