Implementing optimistic concurrent data structures

• US 7,389,291 B1
• Filed: 06/15/2004
• Issued: 06/17/2008
• Est. Priority Date: 06/15/2004
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ladan-Mozes, Edya, Shavit, Nir N.
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Tang; Jieying
• Application Number:
  US10/867,843
• Time in Patent Office: 1,463 Days
• Field of Search: 707/103, 707/8, 707/103.R, 711/147, 710/54
• US Class Current: 1/1
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

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.

Claims

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.