Non-blocking concurrent queues with direct node access by threads

• US 20030196010A1
• Filed: 05/05/2003
• Published: 10/16/2003
• Est. Priority Date: 09/09/1998
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Forin, Alessandro, Raffman, Andrew
• Granted Patent: US 6,889,269 B2
• Time in Patent Office: Days
• US Class Current: 710/52
• CPC Class Codes: G06F 2205/064 Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation
• CPC Class Codes: G06F 2205/106 Details of pointers, i.e. structure of the address generators
• CPC Class Codes: G06F 5/065 Partitioned buffers, e.g. allowing multiple independent queues, bidirectional FIFO's

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.

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.

2. The method of claim 1 wherein the step of determining whether another one of said threads has preempted said one thread comprises:

making a local copy of the tail pointer of the selected queue;

determining whether the next pointer of said tail node of said selected queue no longer points to said queue-specific number of said selected queue;

if said next pointer no longer points to said queue-specific number, determining whether said tail pointer of said selected queue has not changed since the local copy of said tail pointer was made.

3. The method of claim 2 wherein the step of updating said tail pointer if needed comprises:

if said tail pointer has not changed since said local copy was made, changing said tail pointer to the equal the next pointer of said tail node of said selected queue.

4. The method of claim 3 wherein the stem of setting said tail pointer to said new node if it has not been updated by another thread comprises:

determining whether the tail pointer of said selected queue has not change since the making of said local copy; and

if said tail pointer has not changed since the making of said local copy, setting said tail pointer to point to said new node.

5. The method of claim 1 wherein said next pointer of said tail node of said queue initially points to said queue-specific number.

6. The method of claim 1 wherein said queue-specific number is one of:

(a) the address of the head pointer of the queue;

(b) the address of the tail pointer of said queue;

(c) a pointer having its low bit set to one.

(d) a system-wide unique identifier assigned at queue creation time.

7. The method of claim 1 further comprising:

maintaining a dummy node in said queue having a next pointer, wherein said next pointer of said dummy node can point to a next node in the queue if said dummy is not currently the tail node and can point to said queue-specific number if said queue is empty, whereby said queue always contains at least one node.

8. The method of claim 7 wherein, prior to any nodes being enqueued in said queue by any of said threads, said queue is constructed by the method of:

setting said head pointer to point to said dummy node;

setting said tail pointer to pointer to said dummy node;

determining said queue-specific number of said queue; and

setting said next pointer of said dummy node to point to said queue-specific number.

9. The method of claim 3 wherein the step of determining whether the next pointer of said tail node no longer points to said queue-specific number prevents said one thread from enqueueing said new node on a queue other than said selected queue in the event said tail node has been re-enqueued on another queue.

10. The method of claim 1 wherein each of said nodes is a memory location which stores said next pointer and data of said node.

26. A computer-readable medium storing computer-executable instructions for performing the steps of claim 1.

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.

12. The method of claim 11 wherein the step of determining in the event said queue appears to be empty whether another thread has preempted said one thread is preceded by the steps of:

obtaining from said queue a queue-specific number unique to said queue relative to said plurality of queues, the next pointer of said tail node being said queue-specific number in the general case;

determining whether said queue appears to be empty by determining whether the head pointer and the tail pointer point to the same node, and, if so, determining whether the queue is actually empty by determining whether the next pointer of the head node points to said queue-specific number, and so, terminating said method.

13. The method of claim 12 wherein the step of determining whether another thread has preempted said one thread and dequeued a node is preceded by the step of making a local copy of said head pointer, said tail pointer and the next pointer of said head node, and wherein:

the step of determining whether another thread has preempted said one thread and dequeued a node comprises determining whether said head pointer has changed since the making of said local copy;

the step of determining whether another thread has preempted said one thread and enqueued a new node comprises determining whether said tail pointer has changed since the making of said local copy; and

the step of determining whether said queue is empty comprises determining whether said next pointer of said head node is said queue-specific number.

14. The method of claim 13 wherein the step of updating said tail pointer comprises changing the tail pointer to equal the next pointer of the tail node.

15. The method of claim 12 wherein said queue-specific number comprises one of:

(a) a memory address of said head pointer;

(b) a memory address of said tail pointer;

(c) a pointer having its low bit set to one.

(d) a system-wide unique identifier assigned at queue creation time.

16. The method of claim 11 wherein:

said next pointer of said dummy node points to a next node in the queue if said dummy is not currently the tail node and points to said queue-specific number if said queue is empty, whereby said queue always contains at least one node.

17. The method of claim 16 wherein said queue is constructed by the method of:

initializing said queue to contain only said dummy node;

setting said head pointer to point to said dummy node;

setting said tail pointer to pointer to said dummy node;

determining said queue-specific number; and

setting said next pointer of said dummy node to point to said queue-specific number.

18. The method of claim 11 wherein said one thread is given possession of the dequeued node.

23. The data structure of claim 12 wherein said dequeue method comprises:

(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 dequeueing 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 dequeueing method,

(3) 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 dequeueing 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.

27. A computer-readable medium storing computer-executable instructions for performing the steps of claim 11.

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.

20. The method of claim 19 wherein said queue-specific number comprises one of:

(a) an address of said tail pointer;

(b) an address of said head pointer;

(c) a pointer having its low bit set to one.

(d) a system-wide unique identifier assigned at queue creation time.

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.

22. The data structure of claim 21 wherein said enqueue method comprises:

(1) setting the next pointer of a new node to be enqueued to the queue-specific number of said queue,

(2) determining whether another thread 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 enqueueing 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 said queue to point to said new node if it has not been updated by another thread during the performance of said method.

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.

25. The method of claim 24 further comprising:

after performing the dequeueing step, if the dequeued node is not a desired node, re-enqueueing the dequeued node by performing the enqueueing step, and dequeueing a next node from the queue;

repeating the steps of re-enqueueing the dequeued node and the dequeueing a next node until a desired node has been dequeued.

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.

29. The apparatus of claim 28 wherein the processor determines whether another one of said threads has preempted said one thread in that said processor:

makes a local copy of the tail pointer of the selected queue;

determines whether the next pointer of said tail node of said selected queue no longer points to said queue-specific number of said selected queue;

if said next pointer no longer points to said queue-specific number, determines whether said tail pointer of said selected queue has not changed since the local copy of said tail pointer was made.

30. The apparatus of claim 29 wherein the processor updates said tail pointer if needed in that said processor:

changes said tail pointer to the equal the next pointer of said tail node of said selected queue, if said tail pointer has not changed since said local copy was made.

31. The apparatus of claim 30 wherein-the processor sets said tail pointer to said new node if it has not been updated by another thread in that said processor:

determines whether the tail pointer of said selected queue has not change since the making of said local copy; and

if said tail pointer has not changed since the making of said local copy, sets said tail pointer to point to said new node.

32. The apparatus of claim 28 wherein said next pointer of said tail node of said queue initially points to said queue-specific number.

33. The apparatus of claim 28 wherein said queue-specific number is one of:

(a) the address of the head pointer of the queue;

(b) the address of the tail pointer of said queue;

(c) a pointer having its low bit set to one;

(d) a system-wide unique identifier assigned at queue creation time.

34. The apparatus of claim 28 wherein the processor, in further response to the instructions stored in the memory:

maintains a dummy node in said queue having a next pointer, wherein said next pointer of said dummy node can point to a next node in the queue if said dummy is not currently the tail node and can point to said queue-specific number if said queue is empty, whereby said queue always contains at least one node.

36. The apparatus of claim 28 wherein each of said nodes is a memory location which stores said next pointer and data of said node.

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.

38. The apparatus of claim 37 wherein the processor determines in the event said queue appears to be empty whether another thread has preempted said one thread is preceded in that said processor:

obtains from said queue a queue-specific number unique to said queue relative to said plurality of queues;

determines whether said queue appears to be empty by determining whether the head pointer and the tail pointer point to the same node, and, if so, determines whether the queue is actually empty by determining whether the next pointer of the head node points to said queue-specific number.

39. The apparatus of claim 38 wherein the processor, before determining whether another thread has preempted said one thread and dequeued a node, first makes a local copy of said head pointer, said tail pointer and the next pointer of said head node, and wherein:

the processor determines whether another thread has preempted said one thread and dequeued a node in that said processor determines whether said head pointer has changed since the making of said local copy;

the processor determines whether another thread has preempted said one thread and enqueued a new node in that said processor determines whether said tail pointer has changed since the making of said local copy; and

the processor determines whether said queue is empty in that said processor determining whether said next pointer of said head node is said queue-specific number.

40. The apparatus of claim 39 wherein the processor updates said tail pointer in that said processor changes the tail pointer to equal the next pointer of the tail node.

41. The apparatus of claim 38 wherein said queue-specific number comprises one of:

(a) a memory address of said head pointer;

(b) a memory address of said tail pointer;

(c) a pointer having its low bit set to one.

(d) a system-wide unique identifier assigned at queue creation time.

42. The apparatus of claim 37 wherein:

said next pointer of said dummy node points to a next node in the queue if said dummy is not currently the tail node and points to said queue-specific number if said queue is empty, whereby said queue always contains at least one node.