Almost non-blocking linked stack implementation

• US 7,451,146 B2
• Filed: 06/30/2004
• Issued: 11/11/2008
• Est. Priority Date: 06/30/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Boehm, Hans-Juergen K. H.
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): Wong; Joseph D
• Application Number:
  US10/883,118
• Publication Number:
  US 20060005191A1
• Time in Patent Office: 1,595 Days
• Field of Search: 707/8
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method and computer system for implementing, in a multithreaded environment, an almost non-blocking linked list allow a lock-free access provided that certain conditions are met. The approach involves: associating a pointer and an auxiliary data structure with each linked list, using a compare-and-swap (CAS) operation, and making a slight modification of values associated with nodes under certain conditions. The CAS operation guards against setting the pointers incorrectly during insertion and removal operations. The auxiliary data structure, also referred to as the ‘black list,’ holds a dynamic list of values, typically pointer values, associated with nodes that are in the process of being removed by a thread.

Claims

1. A method for implementing, in a multithreaded environment, an almost non-blocking linked list, comprising:

providing a black list associated with a linked list, the black list for holding pointer values each being associated with a node that is in the process of being removed from the linked list, wherein the linked list is lock-free as long as the black list is not full and is blocking when the black list is overflowing so as to implement the linked list as an almost non-blocking linked list;

modifying the pointer value for each node being inserted to the linked list, using a predetermined variation in the pointer value associated with such node to prevent blocking the insertion of such node when its associated pointer value is present in the black list, whereby this predetermined variation facilitates distinguishing the pointer value in the black list from its modified value; and

upon also finding the modified value in the black list, repeating the modifying step until, lastly, the modified value is no longer found in the black list.

2. A method for implementing, in a multithreaded environment, an almost non-blocking linked list, comprising:

providing a first pointer associated with a linked list, the first pointer pointing to the front of the linked list;

providing a black list associated with the linked list and containing one or more slots, each slot for holding a value associated with a node that is in the process of being removed from the linked list;

modifying the value associated with a node if a thread attempts insertion of the node to the linked list but the value is found in the black list, the value being held in the black list for as long as removal of the node is ongoing, wherein the first pointer receives the value only if it is not in the black list, otherwise the first pointer receives the modified value provided, however, that the modified value is also not found in the black list;

upon also finding the modified value in the black list, repeating the modifying step until, lastly, the modified value is no longer found in the black list; and

using a compare-and-swap (CAS) operation in each insertion, and removal, to determine if an intervening thread has modified the first pointer after a copy of the first pointer has been made but before it is to receive the value or modified value, whereby access to the linked list by multiple concurrent threads is almost non-blocking.

3. The method of claim 2, wherein access to the linked list is lock-free provided that the black list is not full when removal is attempted.

4. The method of claim 2, wherein the value associated with the node in the process of being removed is a pointer value of a pointer to the node.

5. The method as in claim 2, wherein each thread is a signal handler run in response to a user-level signal.

6. The method as in claim 2, wherein the black list is an array.

7. The method as in claim 2, wherein the linked list is a LTFO (last-in-first-out) and it is employed as a stack.

8. The method of claim 2, wherein the first pointer has a current pointer value, and wherein the CAS operation compares the copy against the first pointer and if they are equal it swaps the current pointer value with a new pointer value that points to a new first node in the linked list.

9. The method of claim 2, wherein during removal of the node the CAS operation is used in two instances, if in the first instance that CAS operation fails the corresponding black list slot remains occupied with another value otherwise it receives the value associated with the node, and if in the second instance the CAS operation fails the first pointer remains unchanged until, by being repeated, the CAS operation succeeds.

10. The method of claim 9, wherein, the CAS operation in the first instance is repeated after its failure until an empty slot is found which is ready to receive the value associated with the node.

11. The method of claim 2, wherein a single black list is associated with one of more than one linked list.

12. The method of claim 2, wherein the CAS operation is a single-word operation.

13. A computer system for implementing, in a multithreaded environment, an almost non-blocking linked list, comprising:

a processor;

a memory the space in which is being allocated for computer program code, a first pointer, a linked list to which the first pointer is pointing, and a black list associated with the linked list and containing one or more slots, each slot for holding a value associated with a node that is in the process of being removed from the linked list, the program code having instructions that cause the processor to perform the steps of;

providing a first pointer associated with a linked list, the first pointer pointing to the front of the linked list;

providing a black list associated with the linked list and containing one or more slots, each slot for holding a value associated with a node that is in the process of being removed from the linked list;

modifying the value associate with a node if a thread attempts insertion of the node to the linked list but the value is found in the black list, the value being held in the black list for as long as removal of the node is ongoing, wherein the first pointer receives the value only if it is not in the black list, otherwise the first pointer receives the modified value provided, however, that the modified value is also not found in the black list;

upon also finding the modified value in the black list, repeating the modifying step until, lastly, the modified value is no longer found in the black list; and

using a compare-and-swap (CAS) operation in each insertion, and removal, to determine if an intervening thread has modified the first pointer after a copy of the first pointer has been

made but before it is to receive the value or modified value, whereby access to the linked list by multiple concurrent threads is almost non-blocking.

14. The computer system of claim 13, wherein access to the linked list is lock-free provided that the black list is not full when removal is attempted.

15. The computer system of claim 13, wherein the value associated with the node in the process of being removed is a pointer value of a pointer to the node.

16. The computer system of claim 13, wherein each thread is a signal handler run in response to a user-level signal.

17. The computer system of claim 13, wherein the black list is an array.

18. The computer system of claim 13, wherein the linked list is a LIFO (last-in-first-out) and it is employed as a stack.

19. The computer system of claim 13, wherein the first pointer has a current pointer value, and wherein the CAS operation compares the copy against the first pointer and if they are equal it swaps the current pointer value with a new pointer value that points to a new first node in the linked list.

20. The computer system of claim 13, wherein during removal of the node the CAS operation is used in two instances, if in the first instance that CAS operation fails the corresponding black list slot remains occupied with another value otherwise it receives the value associated with the node, and if in the second instance the CAS operation fails the first pointer remains unchanged until, by being repeated, the CAS operation succeeds.

21. The computer system of claim 20, wherein, the CAS operation in the first instance is repeated after its failure until an empty slot is found which is ready to receive the value associated with the node.

22. The computer system of claim 13, wherein a single black list is associated with one of more than one linked list.

23. The computer system of claim 13, wherein the CAS operation is a single-word operation.

24. A method for implementing, in a multithreaded environment, an almost non-blocking concurrently accessed data structure, the method comprising:

providing a black list associated with a field, the black list identifying field values that might be in the process of being replaced, wherein the data structure is lock-free as long as the black list is not full and is blocking when the black list is overflowing so as to implement the data structure as an almost non-blocking concurrently accessed data structure;

modifying a field value for each value being assigned to the field, using a predetermined variation in the field value to prevent blocking the assignment of a new field value when the intended new field value is present in the black list, whereby this predetermined variation facilitates distinguishing the field value in the black list from its modified value; and

upon also finding the modified value in the black list, repeating the modifying step until, the modified field value is no longer found in the black list.