System and method for generating a lock-free dual queue

• US 20070157200A1
• Filed: 12/30/2005
• Published: 07/05/2007
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Hopkins, William
• Granted Patent: US 7,962,923 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method of supporting condition synchronization for a shared data structure so as to provide concurrent access. A protocol is provided between a thread creating a request as part of a remove operation and a thread fulfilling a request as part of an add operation. The protocol provides for the thread making such a request to check the request_value field of the request node and then wait on its own condition variable. A requesting thread sets a requestor_id field of a request node with a value that identifies the thread. A fulfilling thread sets a request_value field of a request node with the address of the data node with the value, and then signals the requesting thread as identified by the requestor_id field. Upon receiving the signal, the requesting thread wakes up and retrieves the value from the data node pointed to it by the request_value field of the request node. If a wait times out, the requesting thread attempts to signal that the wait timed out by performing a CAS operation on the request_value field to modify it from zero to non-zero. If the CAS operation succeeds, the request timed out and the remove operation return failure. If the CAS operation fails, the request was fulfilled since the fulfilling thread set the request_value field with the address of the data node.

Claims

1. A method of supporting condition synchronization for a shared data structure so as to provide simultaneous access, the method comprising:

providing a protocol between a thread creating a request as part of a remove operation and a thread fulfilling a request as part of an add operation, wherein

a requesting thread sets a requestor_id field of a data node with a value that identifies the requesting thread,

a fulfilling thread sets a request_value field of a request node via a CAS operation with the address of the data node with the value, and then signals the requesting thread that the request_value field of the request node has been set, and

upon receiving the signal, the requesting thread wakes up and retrieves the value from the data node pointed to by the request_value field of the request node.

2. A method as in claim 1, wherein the protocol further comprises:

if a wait-for-signal call returns with an indication that a specified timeout interval has elapsed, the requesting thread sets the request_value field of the request node to a non-zero value via a CAS operation.

3. A method as in claim 2, further comprising:

if the CAS operation is successful, the remove operation returns that the operation timed out; and

if the CAS operation fails, the fulfilling thread had previously set the request_value field of the request node with the address of the data node.

4. A method of supporting condition synchronization for a shared data structure so as to provide concurrent access, the method comprising:

providing a linked list of nodes representing the data structure and having corresponding addresses, including a head pointer pointing to a first node and a tail pointer pointing to a last node in a list, and all nodes therebetween pointing to the next successive node, the data structure having add and remove operations defined on it depending on the state of the structure;

providing a first dummy node as the last node when the data structure has one or more entries representing a thread waiting for a data element to be added;

transforming the first dummy node to a request node when a thread performs a remove operation that results in the creation of a request due to the state of the data structure;

providing a second dummy node as the last node;

setting the tail pointer to the address of the second dummy node; and

assigning a selected field of the request node the address of the second dummy node.

5. A method as in claim 4, wherein the selected field of the request node is a next field.

6. A method as in claim 4, wherein the first dummy node is transformed to a request node by setting a request field of the node to TRUE and placing a value in a requestor_id field of the node that uniquely identifies the thread.

7. A method as in claim 6, wherein the tail pointer is set to the address of the second dummy node using a CAS instruction with the expected value being the address of the first dummy node.

8. A method of supporting condition synchronization for a shared data structure so as to provide concurrent access, the method comprising:

providing a linked list of nodes representing the data structure and having corresponding addresses, including a head pointer pointing to a first node and a tail pointer pointing to a last node in a list, and all nodes therebetween pointing to the next successive node, the data structure having add and remove operations defined on it depending on the state of the structure;

setting a requestor_id field of a dummy node with a value that identifies a request thread, setting the request field to TRUE, and setting the next field to a new node, so as to transform the dummy node to a request node and alert the fulfilling thread to signal the request thread;

setting a request_value field of the request node with an address of a data node using a CAS instruction;

signaling the requestor_id thread of the dummy node that the request_value field of the request node has been set; and

retrieving the value of the data node pointed to by the request_value field of the request node.

9. A method as in claim 8, wherein the request thread sets the requestor_id field of the dummy node and retrieves the value from the data node pointed to by the request_value field of the request node.

10. A method as in claim 8, wherein a fulfilling thread sets the request_value field of the request node, signals the requesting field of the dummy node that the request_value field of the request field has been set.

11. A method as in claim 8, further comprising:

setting the request_value field of the request node to a non-zero value using a CAS instruction if a wait-for-signal call returns with an indication that a specified timeout interval has elapsed.

12. A method of supporting condition synchronization for a shared data structure so as to provide concurrent access, comprising:

defining add and remove operations depending on the state of the data structure, the states comprising EMPTY when the structure has no data, DATA when the structure has one or more entries each containing a data element added by an add operation, and REQUESTS when the structure has one or more entries representing a thread waiting for a data element to be added

adding a first data element and changing the state of the data structure to a DATA state when an add operation is performed on a data structure in the EMPTY state;

adding a supplemental data element to the end of the data structure when an add operation is performed on a data structure in the DATA state;

when an add operation is performed by a thread on a data structure in a REQUESTS state, adding a data element to a request at the head of the data structure, removing the request from the data structure while a thread waiting on the request wakes up and returns from a remove operation that created the request and returns the data element, and changing the data structure to the EMPTY state if there was only one request pending;

when a remove operation is performed by a thread on a data structure in the EMPTY state, adding a request to the structure and placing the thread in a wait condition until the request is fulfilled by another thread performing an add operation, and changing the state of the data structure to REQUESTS;

when a remove operation is performed by a thread on a data structure in the REQUESTS state, creating a request, adding it to the end of the data structure, and placing the thread in a wait condition;

when a remove operation is performed by a thread on a data structure in the DATA state, removing the data entry at the head of the structure, returning the data value, and changing the state of the structure to the EMPTY state if there is only one data entry in the structure.

13. A method as in claim 12, further comprising:

providing a time out value when a remove operation is invoked.

14. A shared data structure having condition synchronization for concurrent access, comprising:

a linked list of nodes representing the data structure and having corresponding addresses, including a head pointer pointing to a first node and a tail pointer pointing to a last node in a list, and all nodes therebetween pointing to the next successive node, the data structure having add and remove operations defined on it depending on the state of the structure, the states comprising EMPTY when the structure has no data, DATA when the structure has one or more entries each containing a data element added by an add operation, and REQUESTS when the structure has one or more entries representing a thread waiting for a data element to be added, the nodes comprising;

a request node representing a request of a thread that executed a remove operation on a data structure in either the EMPTY or REQUESTS state;

a data node containing a data value passed in via the add operation; and

a dummy node operative as a place holder;

wherein a first dummy node may be transformed to a request node when a thread performs a remove operation that results in the creation of a request due to the state of the data structure, and a second dummy node may be positioned as the last node in the list with both the tail pointer and a selected field of the transformed request node set to the corresponding address of the second dummy node.

15. A shared data structure as in claim 14, wherein the first dummy node may be transformed to a request node by setting a request field of the node to TRUE and placing a value in a requestor_id field of the node that uniquely identifies the thread.