# US 8,543,743 B2 · Lock free queue > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,743 B2 - Document ID: US8543743B2 - Status: Granted - Kind: B2 - Application number: 12/360,301 - Filed: 2009-01-27 - Published: 2010-07-29 - Granted: 2013-09-24 - Earliest claimed: 2009-01-27 - Assignees: Microsoft Corporation - Applicants: Eric L. Eilebrecht - Inventors: Eric L. Eilebrecht - Web page: https://patentgrep.com/patent/US8543743B2 ## CPC - G06F 9/546: {Message passing systems or structures, e.g. queues} - G06F 2209/548: Queue - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, said attempting to change said head index being comprised in an atomic operation. ### Claim 3 (depends on 1) The method of claim 1 wherein said attempting to change said new head index to point to said next element in said head array is successful. ### Claim 4 (depends on 1) The method of claim 1 wherein said steps of retrieving and attempting are performed within a loop until successful. ### Claim 5 (depends on 4) The method of claim 4, said loop further comprising: determining that said new head index is not within said head array; identifying a new head array being one of said arrays pointed to by said head pointer for said head array; setting said head array as old head array; and setting said new head array as said head array. ### Claim 6 (depends on 5) The method of claim 5, said loop further comprising setting said head pointer of said new head array to null. ### Claim 7 (depends on 5) The method of claim 5, said loop further comprising: performing garbage collection on said old head array. ### Claim 8 (depends on 1) The method of claim 1, said method being performed by a plurality of different processes against said queue. ### Claim 9 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. ### Claim 10 (depends on 9) The method of claim 9, said changing said tail index being comprised in an atomic operation. ### Claim 11 (depends on 9) The method of claim 9 wherein the step of attempting to change said new tail index to point to said tail element in said tail array was successful. ### Claim 12 (depends on 9) The method of claim 9 wherein said steps of retrieving and attempting are performed in a loop until successful. ### Claim 13 (depends on 12) The method of claim 12, said loop further comprising: determining that said new tail index is not within said tail array; creating a new tail array; setting said tail pointer for said tail array to said new tail array; and setting said new tail array as said tail array. ### Claim 14 (depends on 13) The method of claim 13, said loop further comprising setting said tail pointer of said new tail array to null. ### Claim 15 (depends on 13) The method of claim 13, said setting said tail pointer being an atomic operation. ### Claim 16 (depends on 9) The method of claim 9 being performed by a plurality of processes. ### Claim 17 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. ### Claim 18 (depends on 17) The method of claim 17, said changing said tail index being an atomic operation. ### Claim 19 (depends on 17) The method of claim 17, said changing said head index being an atomic operation. ### Claim 20 (depends on 17) The method of claim 17, said data being received by a first process and said element being transferred to a second process.