Browse Prior Art Database

Atomic Head and Tail Pointer Manipulation on Double Threaded Queues

IP.com Disclosure Number: IPCOM000052476D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 46K

Publishing Venue

IBM

Related People

Goldstein, BC: AUTHOR [+2]

Abstract

This article describes a mechanism for placing the initial item onto a Queue without special case logic on ENQ or serialization of DEQ'ers.

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

Page 1 of 2

Atomic Head and Tail Pointer Manipulation on Double Threaded Queues

This article describes a mechanism for placing the initial item onto a Queue without special case logic on ENQ or serialization of DEQ'ers.

The following definitions and assumptions are made for a double threaded que 1) Assumes FIFO (first in, first out) discipline. 2) Each item on queue has a forward and backward pointer. 3) The queue anchor has a _ HEAD pointer (pointer to oldest item on queue)

_ TAIL pointer (pointer to latest item on queue).

Given the representation in the above figure, the question arises on how to place the first item onto the queue.

The following allows one not to treat this ENQ as a special case (as it requires both the HEAD and TAIL Pointers to point to this item), thus providing better performance (no in-line test), and no serialization against concurrent DEQ's is necessary.

The Queue Anchor is initialized as follows (when there are no items on the queue): Using the following acronyms:

QI = Queue item to be placed on Queue

QA = Queue Anchor

NQI = next older item on Queue, the logic then for ENQ of the first item is as follows: 1) BKWD (QI) <- @ QA

2) FWD (QI) <- TAIL (QA)

Note Tail (QA) = to NQI

3) Atomically

Get ENQ-Lock

and Tail (QA) <- @ QI

4) BKWD (NQI) = BKWD (FWD(QI)) <- @ QI

5) Release ENQ-Lock

For the special case of placing the first item onto the queue, BKWD (NQI) is really the HEAD pointer field in the queue anchor. Thus the same logic as would be used to pla...