Lock free data structure maintenance

• US 6,615,216 B1
• Filed: 06/29/2000
• Issued: 09/02/2003
• Est. Priority Date: 06/29/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hu, Carl
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): FILIPCZYK, MARCIN R
• Application Number:
  US09/606,258
• Time in Patent Office: 1,160 Days
• Field of Search: 707/206, 707/6, 707/100-104, 707/9, 709/100, 709/101, 709/104
• US Class Current: 1/1
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Method and apparatus for maintaining a queue structure having data nodes within a computer memory. The queue is maintained by the steps of maintaining a pool of available data nodes for use in maintaining the queue structure. Data is added to the queue structure by adding a nodes to the queue structure. Each data node includes a data portion, a link for addressing other data nodes in the queue structure, and an identifier. Data within the queue is accessed and then removed from the queue but the data nodes are preserved in memory by adding them to the pool of available data nodes. New data nodes are added to the queue by first checking the data pool, which in an exemplary embodiment is in the form of a stack, to determine if there are any nodes available in the pool before creating a new data node.

Claims

1. A method for maintaining a list structure having data nodes in a computer memory accessible by multiple processors, said method comprising the steps of:

a) maintaining a pool of available data nodes for use in maintaining the list structure;

wherein each data node includes i) a data portion ii) a link for addressing other data nodes in the list structure and iii) a unique identifier for said data node;

b) adding a data node to the list structure from the pool of data nodes and if there is no such available data node in said pool, creating a new data node from available computer memory that includes i) a data portion ii) a link for addressing other data nodes in the list structure and iii) a unique identifier for said data node, and adding the new data node to the list structure;

said adding step comprising a lock free step which checks the identifier of a data node of the list before adding a node to said list structure; and

c) accessing data from the list structure by determining the contents of a specified data node, removing the specified data node from the list structure and adding the specified data node from the list structure to the pool of available data nodes.

2. The method of claim 1 wherein the pool of available data nodes is a stack structure that is created contemporaneously with the list structure.

3. The method of claim 2 wherein the stack structure is maintained by use of a compare and swap instruction.

4. The method of claim 1 wherein the pool is maintained as a stack structure wherein data nodes are pushed onto the stack when they are removed from the list and wherein data nodes are popped off the stack for addition to said list structure.

5. The method of claim 1 wherein the list is a queue structure and wherein new nodes are added at one end of the queue structure and data is accessed from the queue by getting data from another end of the queue structure.

6. The method of claim 1 wherein each of the multiple processors adds nodes to the list structure and assigns a unique pointer/counter combination to each data node added to the list structure.

7. A method for maintaining a queue structure having data nodes in a computer memory accessible by multiple processors, said method comprising the steps of:

a) maintaining a pool of available data nodes for use in maintaining the queue structure;

wherein each data node includes i) a data portion ii) a link for addressing other data nodes in the queue structure and iii) a unique identifier for said data node assigned by one of the multiple processors;

b) adding data to the queue structure by adding a data node from the pool of available data nodes at a rear of the queue structure and if there are no such available data node creating a new data node from available computer memory that includes i) a data portion ii) a link for addressing other data nodes in the queue structure and iii) a unique identifier for said data node assigned a processor, and adding the new data node to the queue structure;

said adding step comprising a lock free step which checks the identifier of data nodes of the queue structure before adding a node; and

c) accessing data from the queue structure by determining the contents of an front data node, removing the front data node from the queue structure and adding the data node removed from the queue structure to the pool of available data nodes.

8. The method of claim 7 wherein the pool of available data nodes is a stack structure.

9. The method of claim 8 wherein the step of adding data to the queue structure is performed by determining if an available data node is contained in the stack and popping said available data node from the stack, and adding data to said available data node for insertion into the queue structure.

10. Computer apparatus comprising:

a) a plurality of processors wherein each processor executes a stored program for performing one or more tasks including a task of adding to and deleting data from a data structure made up of a plurality of data nodes; and

b) a shared memory accessible to the plurality of processors for maintaining said data structure wherein each of the plurality of processors has access to the shared memory to allow said processor to add or delete data nodes from the data structure;

c) wherein the stored programs executing on each of the plurality of processors assigns a unique pointer/counter combination to each data node and includes a lock free procedure for updating the data structure by maintaining an available pool of data nodes for use in updating the data structure.

11. The computer apparatus of claim 10 wherein each time one of the plurality of processors writes data to a data node in either the data structure or in the available pool it updates the counter.

12. The computer apparatus of claim 10 wherein the data structure is a list structure.

13. A computer readable medium having computer executable instructions for performing steps on a computer having a computer memory of:

a) maintaining a pool of available data nodes for use by multiple processors in maintaining a list structure;

wherein each data node includes i) a data portion ii) a link for addressing other data nodes in the list structure and iii) a unique identifier for the node;

b) adding a data node to the list structure from the pool of data nodes and if there is no such available data node in said pool, creating a new data node from available computer memory that includes i) a data portion ii) a link for addressing other data nodes in the list structure and iii) a unique identifier for said data node, and adding the new data node to the list structure;

said adding step comprising a lock See step which checks the identifier of the data node of the list before adding a node; and

c) accessing data from the list structure by determining the contents of an endmost data node, removing the endmost data node from the list structure and adding the endmost data node from the list structure to the pool of available data nodes.

14. The computer readable medium of claim 13 wherein the list structure is a queue structure.

15. The computer readable medium of claim 13 wherein the pool of available data nodes is a stack structure that is created at the time the list is first created.

16. The computer readable medium of claim 15 the stack structure and the list structure are maintained by a plurality of processors which execute a compare and swap instruction to avoid inaccurate updating of said stack and list structures.

17. The computer readable medium of claim 15 wherein data nodes are pushed onto the stack when they are removed from the list and wherein they are popped off the stack for addition to said queue.