Concurrent Data Structures:Linked Lists

Linked Lists

Consider implementations of concurrent search structures supporting insert, delete, and search operations. If these operations deal only with a key value, then the resulting data structure is a set ; if a data value is associated with each key, we have a dictionary [24]. These are closely related data structures, and a concurrent set implementation can often be adapted to implement a dictionary. In the next three sections, we concentrate on implementing sets using different structures: linked lists, hash tables, and trees.

Suppose we use a linked list to implement a set. Apart from globally locking the linked list to prevent concurrent manipulation, the most popular approach to concurrent lock- based linked lists is hand-over-hand locking (sometimes called lock coupling) [14, 89]. In this approach, each node has an associated lock. A thread traversing the linked list releases a node’s lock only after acquiring the lock of the next node in the list, thus preventing overtaking which may cause unnoticed removal of a node. This approach reduces lock granularity but significantly limits concurrency because insertions and deletions at disjoint list locations may delay each other.

One way to overcome this problem is to design lock-free linked lists. The difficulty in implementing a lock-free ordered linked list is ensuring that during an insertion or deletion, the adjacent nodes are still valid, i.e., they are still in the list and are still adjacent. As Figure 47.6 shows, designing such lock-free linked lists is not a straightforward matter.

The first CAS-based lock-free linked list is due to Valois [135], who uses a special auxiliary node in front of every regular node to prevent the undesired phenomena depicted in Figure 47.6. Valois’s algorithm is correct when combined with a memory management solution due to Michael and Scott [101], but this solution is not practical. Harris [42] presents a lock-free list that uses a special “deleted” bit that is accessed atomically with node pointers in order to signify that a node has been deleted; this scheme is applicable only in garbage collected environments. Michael [99] overcomes this disadvantage by modifying Harris’s algorithm to make it compatible with memory reclamation methods [52, 100].