Non-blocking concurrent queues with direct node access by threads
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
42 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 26)
-
-
11. 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 23, 27)
-
-
19. A method of constructing a FIFO queue data structure, comprising:
-
providing a head pointer, a tail pointer and a dummy node;
initializing said queue to contain only said dummy node;
setting said head pointer to point to said dummy node;
setting said tail pointer to point to said dummy node;
determining a queue-specific number of said queue unique to said queue relative to said plurality of queues; and
setting said next pointer of said dummy node to point to said queue-specific number. - View Dependent Claims (20)
-
-
21. An IQueue object data structure, comprising:
-
a queue object comprising;
a dummy node, a head pointer initially pointing to said dummy node, a tail pointer initially pointing to said dummy node, a next pointer of said dummy node initially being said queue-specific number;
a set of methods executable by any one of plural threads, comprising;
an enqueue method, a dequeue method. - View Dependent Claims (22)
-
-
24. 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. - View Dependent Claims (25)
-
-
28. 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. - View Dependent Claims (29, 30, 31, 32, 33, 34, 36)
-
-
37. 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. - View Dependent Claims (38, 39, 40, 41, 42)
-
Specification