US 2003/0196010 A1 · Non-blocking concurrent queues with direct node access by threads

Abstract

Multiple non-blocking FIFO queues are concurrently maintained using atomic compare-and-swap (CAS) operations. In accordance with the invention, each queue provides direct access to the nodes stored therein to an application or thread, so that each thread may enqueue and dequeue nodes that it may choose. The prior art merely provided access to the values stored in the node. In order to avoid anomalies, the queue is never allowed to become empty by requiring the presence of at least a dummy node in the queue. The ABA problem is solved by requiring that the next pointer of the tail node in each queue point to a “magic number” unique to the particular queue, such as the pointer to the queue head or the address of the queue head, for example. This obviates any need to maintain a separate count for each node.

Claims41

Dependent claims

A method for one thread in a system capable of running plural threads to enqueue a new node onto a selected FIFO queue, said system capable of supporting plural FIFO queues, each queue comprising a succession of enqueued nodes and having a head pointer pointing to a head node of said succession of nodes and a tail pointer pointing to a tail node of said succession of nodes, each of said nodes having a next pointer, the next pointer of each of said enqueued nodes pointing to the next node in said succession from said head node to said tail node, said method comprising:

obtaining a queue-specific number unique to said selected queue relative to said plural queues;
setting the next pointer of said new node to the queue-specific number of said selected queue;
determining whether another one of said threads has preempted said one thread in said selected queue and, if so, updating said tail pointer of said selected queue if needed and then re-starting said method;
otherwise, setting said next pointer of said tail node of said selected queue to point to said new node;
and
setting said tail pointer of said selected queue to point to said new node if it has not been updated by another thread during the performance of said method.

3 more elements

A method for one thread in a system running plural threads to dequeue a node from a selected FIFO queue, said system having plural FIFO queues, each queue comprising a succession of enqueued nodes and having a head pointer pointing to a head node of said succession of nodes and a tail pointer pointing to a tail node of said succession of nodes, each of said nodes having a next pointer, the next pointer of each of said enqueued nodes pointing to the next node in said succession from said head node to said tail node, said method comprising:

determining whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, re-starting said method;
determining in the event said queue appears to be empty whether another thread has preempted said one thread by enqueueing a new node at the tail of said queue, and if the other thread did not update said tail pointer, updating said tail pointer, and re-starting said method;
if said queue is not empty, determining whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, re-starting said method;
otherwise, dequeueing the head node by changing said head pointer to equal the next printer of said head node;
if the dequeued node is a dummy node, re-enqueuing said dummy node onto said queue.

2 more elements

A method of constructing and operating a FIFO queue in a system running plural threads and supporting plural FIFO queues, comprising:

(A) constructing said FIFO queue by the steps of:
(1) providing a head pointer, a tail pointer and a dummy node,
(2) initializing said queue to contain only said dummy node,
(3) setting said head pointer to point to said dummy node,
(4) setting said tail pointer to pointer to said dummy node,
(5) determining a queue-specific number of said queue unique to said queue relative to said plurality of queues, and
(6) setting said next pointer of said dummy node to point to said queue-specific number;
(B) enqueueing a new node onto said queue by the steps of:
(1) setting the next pointer of said new node to the queue-specific number of said queue,
(2) determining whether another one of said threads has preempted said one thread in said queue and, if so, updating said tail pointer of said selected queue if needed and then re-starting said method,
(3) otherwise, setting said next pointer of said tail node of said queue to point to said new node, and
(4) setting said tail pointer of said queue to point to said new node if it has not been updated by another thread during the performance of said method;
and
(C) dequeueing a node from said queue by the steps of:
(1) determining whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, re-starting said method,
(2) determining in the event said queue appears to be empty whether another thread has preempted said one thread by enqueueing a new node at the tail of said queue, and if the other thread did not update said tail pointer, updating said tail pointer, and re-starting said method,
(3) if said queue is not empty, determining again whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, re-starting said method,
(4) otherwise, dequeueing the head node by changing said head pointer to equal the next pointer of said head node,
(5) if the dequeued node is a dummy node, re-enqueuing said dummy node onto said queue.

16 more elements

Apparatus capable of running plural threads in which one of the plural threads can enqueue a new node onto a selected FIFO queue, said apparatus capable of supporting plural FIFO queues, each queue comprising a succession of enqueued nodes and having a head pointer pointing to a head node of said succession of nodes and a tail pointer pointing to a tail node of said succession of nodes, each of said nodes having a next pointer, the next pointer of each of said enqueued nodes pointing to the next node in said succession from said head node to said tail node, said apparatus comprising:

a processor;
a memory having executable instructions stored therein;
and
wherein the processor, in response to the instructions stored in the memory:
obtains a queue-specific number unique to said selected queue relative to said plural queues;
sets the next pointer of said new node to the queue-specific number of said selected queue;
determines whether another one of said threads has preempted said one thread in said selected queue and, if so, updates said tail pointer of said selected queue if needed;
otherwise, sets said next pointer of said tail node of said selected queue to point to said new node;
and
sets said tail pointer of said selected queue to point to said new node if it has not been updated by another thread.

7 more elements

Apparatus capable of running plural threads in which one of said plural threads can dequeue a node from a selected FIFO queue, said apparatus capable of supporting plural FIFO queues, each queue comprising a succession of enqueued nodes and having a head pointer pointing to a head node of said succession of nodes and a tail pointer pointing to a tail node of said succession of nodes, each of said nodes having a next pointer, the next pointer of each of said enqueued nodes pointing to the next node in said succession from said head node to said tail node,

said apparatus further comprising:
a processor;
a memory having computer-executable instructions stored therein;
and
wherein the processor, in response to the instructions stored in the memory:
determines whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, resets;
determines in the event said queue appears to be empty whether another thread has preempted said one thread by enqueueing a new node at the tail of said queue, and if the other thread did not update said tail pointer, updates said tail pointer, and resets;
if said queue is not empty, determines whether another thread has preempted said one thread and dequeued a node from the head of said queue and, if so, resets;
otherwise, dequeues the head node by changing said head pointer to equal the next pointer of said head node;
if the dequeued node is a dummy node, re-enqueues said dummy node onto said queue.

7 more elements

Dependencies are inferred from the claim text.

Non-blocking concurrent queues with direct node access by threads

Life of this patent

Non-blocking concurrent queues with direct node access by threads

Life of this patent

Abstract

Claims41