Implementing optimistic concurrent data structures
View Patent ↗A concurrent FIFO queue is implemented as an “optimistic” doubly-linked list. Nodes of the optimistic doubly-linked list are allocated dynamically and links between the nodes are updated optimistically, i.e., assuming that threads concurrently accessing the FIFO queue will not interfere with each other, using a simple store operation. Concurrent, linearizable, and non-blocking enqueue and dequeue operations on the two ends of the doubly-linked list proceed independently, i.e., disjointly. These operations require only one successful single-word synchronization operation on the tail pointer and the head pointer of the doubly-linked list. If a bad ordering of operations on the optimistic FIFO queue by concurrently executing threads creates inconsistencies in the links between the nodes of the doubly-linked list, a fix-up process is invoked to correct the inconsistencies.
1. A method for performing computer system operations, comprising:
implementing a concurrent first-in-first-out (FIFO) queue as a dynamically-sized doubly-linked list in a memory of a computer system;
enqueuing a node in the concurrent FIFO queue, wherein the enqueuing comprises:
performing an enqueue operation until a single-word synchronization operation is successful, the enqueue operation comprising:
using a store operation to store a pointer to another node in a next field of the node, wherein the another node is pointed to by a tail pointer;
using the single-word synchronization operation to attempt to store a pointer to the node in the tail pointer; and
using a store operation to store a pointer to the node in a previous field of the another node when the single-word synchronization operation is successful,
wherein the single-word synchronization operation is the only synchronization operation used during the enqueuing; and
dequeuing an enqueued node, wherein the dequeueing comprises:
performing a dequeue operation until one selected from a group consisting of the single-word synchronization operation is successful and the queue is empty, the dequeue operation comprising:
determining whether a previous pointer of the enqueued node is inconsistent;
traversing a plurality of next pointers in the doubly-linked list to correct inconsistent previous pointers in the doubly-linked list when the previous pointer is inconsistent; and
using the single-word synchronization operation to attempt to store a pointer to another node in a head pointer, wherein the another node is pointed to by a previous pointer of the enqueued node,
wherein the single-word synchronization operation is the only synchronization operation used during the dequeuing.
2. The method of claim 1 , wherein the previous pointer is inconsistent when a tag value of the previous pointer is not equal to a tag value of a head pointer.
3. The method of claim 1 , wherein the previous pointer is inconsistent when the previous pointer has a null value.
4. A concurrent first-in-first-out (FIFO) queue in a memory of a computer system comprising:
a doubly-linked list comprising a plurality of nodes, wherein each node of the plurality of nodes comprises a value, a next pointer, and a previous pointer;
a head pointer, wherein the head pointer points to an oldest node of the plurality of nodes; and
a tail pointer, wherein the tail pointer points to a youngest node of the plurality of nodes, wherein:
when a node is added to the doubly-linked list,
a single-word synchronization operation is used to change the tail pointer, wherein the single-word synchronization operation is the only synchronization operation used in adding the node, and
a store operation is used to store a pointer to the node as a previous pointer of the youngest node when the single-word synchronization operation is successful, and
when the node is removed from the doubly-linked list and a previous pointer of the node is inconsistent, a fix-up process is executed, wherein the fix-up process comprises traversing a plurality of next pointers in the plurality of nodes to correct inconsistent previous pointers in the plurality of nodes.
5. The concurrent FIFO queue of claim 4 , wherein the previous pointer is inconsistent when a tag value of the head pointer is not equal to a tag value of the previous pointer.
6. The concurrent FIFO queue of claim 4 , wherein the previous pointer is inconsistent when the previous pointer has a null value.
7. A computer system comprising:
a memory comprising a first-in-first-out (FIFO) queue, wherein the FIFO queue comprises at least one node, and wherein the FIFO queue is implemented as a dynamically-sized doubly-linked list; and
a plurality of concurrent threads, wherein each thread of the plurality of concurrent threads comprises instructions to:
enqueue a node in the FIFO queue, wherein the instructions to enqueue perform:
using a store operation to store a pointer to another node in a next field of the node, wherein the another node is pointed to by a tail pointer;
using a single-word synchronization operation to attempt to store a pointer to the node in the tail pointer; and
using a store operation to store a pointer to the node in a previous field of the another node when the single-word synchronization operation is successful,
wherein the single-word synchronization operation is the only synchronization operation used to enqueue the node; and
dequeue an enqueued node, wherein the instructions to dequeue comprise instructions to perform a deque operation until at least one selected from a group consisting of the single-word synchronization operation is successful and the queue is empty occurs, the dequeue operation comprising instructions to:
determine whether a previous pointer of the enqueued node is inconsistent;
traverse a plurality of next pointers in the doubly-linked list to correct inconsistent previous pointers in the doubly-linked list when the previous pointer is inconsistent; and
use the single-word synchronization operation to attempt to store a pointer to another node in a head pointer, wherein the another node is pointed to by a previous pointer of the enqueued node,
wherein the single-word synchronization operation is the only synchronization operation used to dequeue the enqueued node.
8. The computer system of claim 7 , wherein the previous pointer is inconsistent when a tag value of the previous pointer is not equal to a tag value of a head pointer.
9. The computer system of claim 7 , wherein the previous pointer is inconsistent when the previous pointer has a null value.