Lock-Free Dual Queue with Condition Synchronization and Time-Outs

A lock-free method of adding elements to a queue accessible by one or more producer threads and one or more consumer threads, the method comprising:

• accessing a tail pointer indicating a last node;
• reading a value from a next field of the last node indicated by the tail pointer;
• allocating memory to represent a new node;
• and
• storing data from one of the one or more producer threads on the new node.

A lock-free method of processing a remove operation of a dual queue that can enter a data state, an empty state and a request state, the method comprising:

• if the dual queue is in the data state:
• accessing a head pointer indicating a dummy node and reading a value from the next field of the dummy node, wherein the value from the next field of the dummy node points to a data node;
• using a conditional synchronization primitive to change the head pointer to point to the data node if the head pointer has not been modified since the head pointer was accessed by the consumer thread;
• and
• copying data stored in the data node to local memory associated with the consumer thread if the conditional synchronization primitive succeeded in modifying the head pointer;
• if the dual queue is in the empty state or request state:
• creating a new request node with a next field and request_value field initialized to an unasserted value, the requestor_id field set to a value identifying a consumer thread executing the operation;
• reading the next field of the node pointed to by a tail pointer, and if the next field does not equal an unasserted value, performing a conditional synchronization primitive instruction on the tail pointer to change the tail pointer from the tail pointer's current value to the address in the next field of the node pointed to by the tail pointer, and reading new values of the shared head and tail pointer;
• and
• performing a conditional synchronization instruction on a next field of a last node in the dual queue to change a value in the next field from an unasserted value to the address of the request node;
• if the conditional synchronization instruction fails, reading new values of the shared head and tail pointers;
• executing a wait operation on a condition variable of the consumer thread;
• and
• copying into local memory the value in the data node addressed by the request node's request_value field when the wait operation is finished.

A computer-readable storage medium containing a set of instructions capable of causing one or more processors to manage a dual queue that can enter a data state, an empty state, and a request state, the instructions to cause the dual queue to:

• initially enter the empty state;
• in response to receiving an add operation while in the empty state, add specified data to the queue and transitioning to the data state;
• in response to receiving a remove operation while in the empty state, add a request to the queue and transitioning to the request state;
• in response to receiving an add operation while in the data state, add specified data to the queue and remaining in the data state;
• in response to receiving a remove operation while in the data state, remove data from the queue and transition to the empty state if no more data exists on the queue after removing the data from the queue, or remain in the data state if data exists on the queue after removing the data from the queue;
• in response to receiving a remove instruction while in the request state, add a request to the queue and remain in the request state, and
• in response to receiving an add operation while in the request state, fulfill the request with data specified in the add operation and transition to the empty state if no additional requests exist on the queue after removing the request from the queue, or remain in the requests state if one or more additional requests exist on the queue after removing the request from the queue.