Concurrent, non-blocking, lock-free queue and method, apparatus, and computer program product for implementing same
First Claim
1. A method of implementing a queue, comprising the steps of:
- (a) enqueueing a user node to the end of a queue, wherein prior to the enqueueing step (a), the queue comprises at least a dummy node having a next pointer to a next node, and wherein the user node has a next pointer to a next node, and wherein the enqueueing step (a) includes the steps of;
linking the user node to the end of the queue by setting the next pointer of a tail node to point to the user node;
updating a tail pointer of the queue to point to the user node, wherein the updating step is not completed during the enqueueing step (a) but is completed during a subsequent enqueue operation or a subsequent dequeue operation;
(b) after the enqueueing step (a), dequeueing the dummy node from the queue;
(c) after the dequeueing step (b), conditionally dequeueing a head node from the queue;
(d) during the conditional dequeueing step (c), enqueueing another dummy node to the end of the queue but only if the queue contains one and no more than one user node.
1 Assignment
0 Petitions
Accused Products
Abstract
A dummy node is enqueued to a concurrent, non-blocking, lock-free FIFO queue only when necessary to prevent the queue from becoming empty. The dummy node is only enqueued during a dequeue operation and only when the queue contains a single user node during the dequeue operation. This reduces overhead relative to conventional mechanisms that always keep a dummy node in the queue. User nodes are enqueued directly to the queue and can be immediately dequeued on-demand by any thread. Preferably, the enqueueing and dequeueing operations include the use of load-linked/store conditional (LL/SC) synchronization primitives. This solves the ABA problem without requiring the use a unique number, such as a queue-specific number, and contrasts with conventional mechanisms that include the use of compare-and-swap (CAS) synchronization primitives and address the ABA problem through the use of a unique number. In addition, storage ordering fences are preferably inserted to allow the algorithm to run on weakly consistent processors.
15 Citations
8 Claims
-
1. A method of implementing a queue, comprising the steps of:
-
(a) enqueueing a user node to the end of a queue, wherein prior to the enqueueing step (a), the queue comprises at least a dummy node having a next pointer to a next node, and wherein the user node has a next pointer to a next node, and wherein the enqueueing step (a) includes the steps of; linking the user node to the end of the queue by setting the next pointer of a tail node to point to the user node; updating a tail pointer of the queue to point to the user node, wherein the updating step is not completed during the enqueueing step (a) but is completed during a subsequent enqueue operation or a subsequent dequeue operation; (b) after the enqueueing step (a), dequeueing the dummy node from the queue; (c) after the dequeueing step (b), conditionally dequeueing a head node from the queue; (d) during the conditional dequeueing step (c), enqueueing another dummy node to the end of the queue but only if the queue contains one and no more than one user node. - View Dependent Claims (2, 3, 4)
-
-
5. A computer program product for implementing a queue in a digital computing device having at least one processor, comprising:
-
a plurality of executable instructions provided on computer readable recordable media, wherein the executable instructions, when executed by the at least one processor, cause the digital computing device to perform the steps of; (a) enqueueing a user node to the end of a queue, wherein prior to the enqueueing step (a), the queue comprises at least a dummy node having a next pointer to a next node, and wherein the user node has a next pointer to a next node, and wherein the enqueueing step (a) includes the steps of; linking the user node to the end of the queue by setting the next pointer of a tail node to point to the user node; updating a tail pointer of the queue to point to the user node, wherein the updating step is not completed during the enqueueing step (a) but is completed during a subsequent enqueue operation or a subsequent dequeue operation; (b) after the enqueueing step (a), dequeueing the dummy node from the queue; (c) after the dequeueing step (b), conditionally dequeueing a head node from the queue; (d) during the conditional dequeueing step (c), enqueueing another dummy node to the end of the queue only if the queue contains one and no more than one user node. - View Dependent Claims (6, 7, 8)
-
Specification