Lock-free double-ended queue based on a dynamic ring

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for popping a value from a lock-free double-ended queue (deque), the method comprising:

• receiving a command to pop a value from a selected end of the deque,
• wherein the deque is implemented as a doubly-linked list of nodes formed into a ring, so that node pointers in one direction form an inner ring, and node pointers in the other direction form an outer ring, and
• wherein the deque has an inner hat, which points to a node next to the last occupied node along the inner ring,
• wherein the deque has an outer hat, which points to a node next to the last occupied node along the outer ring;
• and
• in response to the command, attempting to perform a double compare-and-swap (DCAS) operation;
• wherein the DCAS operation predicts that the hat for the selected end of the deque remains unchanged and that the value in a node-to-be-popped located in a closest node to the hat in a popping direction remains unchanged, is not null and is not a special value;
• wherein if this DCAS operation succeeds, the value is returned, the corresponding value field in the node-to-be-popped is set to null, and the hat is updated to point to the node that was popped from.

An apparatus that supports popping a value from a lock-free double-ended queue (deque), the method comprising:

• a shared-memory multiprocessor system;
• a command-processing mechanism within the shared-memory multiprocessor system configured to receive a command to pop a value from a selected end of the deque,
• wherein the deque is implemented as a doubly-linked list of nodes formed into a ring, so that node pointers in one direction form an inner ring, and node pointers in the other direction form an outer ring, and
• wherein the deque has an inner hat, which points to a node next to the last occupied node along the inner ring,
• wherein the deque has an outer hat, which points to a node next to the last occupied node along the outer ring;
• and
• wherein in response to the pop command, the command-processing mechanism is configured to attempt to perform a double compare-and-swap (DCAS) operation;
• wherein the DCAS operation predicts that the hat for the selected end of the deque remains unchanged and that the value in a node-to-be-popped located in a closest node to the hat in a popping direction remains unchanged, is not null and is not a special value;
• wherein if this DCAS operation succeeds, the value is returned, the corresponding value field in the node-to-be-popped is set to null, and the hat is updated to point to the node that was popped from.