Back to results
US 8,543,743 B2Granted
Lock free queue
AssigneeMicrosoft Corporation
InventorEric L. Eilebrecht
Life of this patent
Estimating the term…
Abstract
A first in, first out queue uses a sequence of arrays to store elements in the queue. The arrays are constructed using a lock free queue, and within each array, a lock free mechanism may be used to enqueue and dequeue elements. Many embodiments may use atomic operations to ensure successful placement of elements in the queue, as well as remove elements from the queue. The atomic operations may be used within a loop until successful.
Claims20
A method executed by at least one processor comprising:
- identifying a queue comprising a sequence of arrays, each of said arrays having a head pointer, a tail pointer, a head index, and a tail index;
- in each of said arrays, said head pointer containing a pointer to one of said arrays ahead of said array, except when said array is a head array, said head pointer contains null;
- in each of said arrays, said tail pointer containing a pointer to one of said arrays behind said array, except when said array is a tail array, said tail pointer contains null;
- said head index being a pointer to a head element within said array;
- said tail index being a pointer to a tail element within said array;
- determining that said head array is a first of said sequence of arrays;
- determining that said head index in said head array is pointing to an element within said head array;
- retrieving said element from said head array;
- attempting to change said head index to point to a next element in said head array;
- failing to change said head index;
- retrieving a new head index;
- and
- attempting to change said new head index to point to said next element in said head array.
10 more elements
A method executed by at least one processor comprising:
- identifying a queue comprising a sequence of arrays, each of said arrays having a head pointer, a tail pointer, a head index, and a tail index;
- in each of said arrays, said head pointer containing a pointer to one of said arrays ahead of said array, except when said array is a head array, said head pointer contains null;
- in each of said arrays, said tail pointer containing a pointer to one of said arrays behind said array, except when said array is a tail array, said tail pointer contains null;
- said head index being a pointer to a head element within said array;
- said tail index being a pointer to a tail element within said array;
- receiving data to store in said queue;
- determining that said tail array is a last of said sequence of arrays;
- determining that said tail index in said tail array is pointing to an element within said tail array;
- attempting to change said tail index to point to a next element in said tail array;
- failing when attempting to change said tail index;
- retrieving a new tail index;
- attempting to change said new tail index to point to said next element in said tail array;
- and
- storing said data in said next element from said tail array.
11 more elements
A method executed by at least one processor comprising:
- identifying a queue comprising a sequence of arrays, each of said arrays having a head pointer, a tail pointer, a head index, and a tail index;
- in each of said arrays, said head pointer containing a pointer to one of said arrays ahead of said array, except when said array is a head array, said head pointer contains null;
- in each of said arrays, said tail pointer containing a pointer to one of said arrays behind said array, except when said array is a tail array, said tail pointer contains null;
- said head index being a pointer to a head element within said array;
- said tail index being a pointer to a tail element within said array;
- receiving data to store in said queue;
- determining that said tail array is a last array of said sequence of arrays;
- determining that said tail index in said tail array is pointing to an element within said tail array;
- attempting to change said tail index to point to a next element in said tail array;
- storing said data in said next element in said tail array from said tail array;
- determining that said head array is a first array of said sequence of arrays;
- determining that said head index in said head array is pointing to an element within said head array;
- retrieving said element in said head array from said head array, said element comprising said data;
- and
- attempting to change said head index to point to a next element in said head array;
- and
- wherein when either attempting to change said tail index or attempting to change said head index fails further;
- retrieving a new head index or new tail index;
- attempting to change said new head index to point to said next element in said head array when said change said head index fails;
- and
- attempting to change said new tail index to point to said next element in said tail array when said change said tail index fails.
18 more elements
Dependencies are inferred from the claim text.