Almost non-blocking linked stack implementation
First Claim
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;
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
if the modified value is also found in the black list, repeating the modifying step until, lastly, the modified value is no longer found in the black list.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
24 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;
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
if the modified value is also found 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;
if the modified value is also found 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. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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;
if the modified value is also found in the black list, repeating the modifing 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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
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;
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
if the modified value is also found in the black list, repeating the modifying step until, the modified field value is no longer found in the black list.
-
Specification