System and method for generating a lock-free dual queue
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
58 Citations
15 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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11)
-
-
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. - View Dependent Claims (13)
-
-
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. - View Dependent Claims (15)
-
Specification