Concurrent and simple data structure

We know how a linked list data structure works. Don’t you? Please, check here out. We can perform operations on the linked list, such as adding an element, removing an element, and checking if an element exists. When we add the element into a linked list, we are sure that it’s there. So far so good until we work on a single processor. In a multiprocessor environment, which nowadays is quite common (I guess, it was normal even 10 years ago) simple operations can behave unexpectedly if a programmer (or a system) doesn’t handle it correctly.

How can we be sure that we handle it properly? Reasoning about concurrent data is difficult, but we must be able to do that. The key to understanding a concurrent data structure is to understand its invariants: properties that always hold. The property holds when the object is created and once the property holds, then no thread can take a step that makes the property false. Assuming that methods insert(), remove(), and contains() are the only ones that change the state of nodes, we can check that each invariant is preserved by each of these invocations and provide correctness of the implementation.

This post is based on the book “The Art of Multiprocessor Programming” by Nir Shavit. So, I definitely recommend you check it out if you need more details.

There are many algorithms with different progress guarantees. Some of them use locks and for them, we must ensure that they are deadlock-free and starvation-free (from “The Art of Multiprocessor Programming” by Nir Shavit):

1. A method is wait-free if it guarantees that every call finishes in a finite number of steps.
2. A method is lock-free if it guarantees that some call always finishes in a finite number of steps.

Others don’t use locks at all. Here, non-blocking properties must be held. There are some algorithms that combine two previous approaches using locks only for some methods.

In this post, we look at the two implementations: coarse-grained synchronization and fine-grained synchronization that use locks for all methods. Other implementations don’t use locks for some or all methods. We will look at one of the non-blocking implementations in the upcoming post.

We implement standard methods of linked list: insert(), remove() and contains().

Coarse-Grained Linked List

Let’s start with a coarse-grained linked list. The idea is straightforward: we must acquire a single lock before accessing a data structure in methods (insert, remove, contains) and release it when we are done. I’ll describe only the general schema of an operation for this list:

function someOperation(T value) {
 try { 
  // acquire the lock 
  // perform operations like remove, delete or add 
  } finally { 
    // release the lock 
  } 
}

There is a try-catch-finally mechanism in Java that helps to release the lock despite raising runtime errors in code before unlocking. The enormous advantage of a coarse-grained linked list is that it is easy to show the correctness of the algorithm. All methods act on the list only while holding a single lock, thus, the execution is sequential. It’s worth noting that coarse-grained linked list has the same progress condition as its lock, which means if the used lock is starvation-free, so is the implementation.

Of course, the big issue of this implementation is dealing with contention. When two threads try to access either the same resource or related resources in such a way that at least one of the contending threads runs more slowly than it would if the other threads were not running. So, the thread will still be delayed waiting for another.

Fine-grained Linked List

A fine-grained linked list can improve concurrency by locking individual nodes, rather than locking the whole method.

The idea of a fine-grained linked list is to lock each node when visiting and release it later when we finish working with this node. It helps to traverse the list in a pipelined fashion, that is, multiple threads can work with the same linked list, but with different nodes.

How can we implement this? The first idea that comes to mind is to lock the current node, process it (or whatever) release lock in this node, and go to the next node. This implementation is not safe because another thread could remove or add another node to the list in the interval between unlocking the first node and locking the second node. Let’s look at the picture that shows the issue during traversing:

Each node has an associated lock (fine-grained) that enables locking specific nodes, instead of locking down the entire list for all method calls. Traversing the list is done in a hand-holding manner, as children do with an overhead ladder. Initially, two nodes are locked. While moving to the next node, we unlock the first node, and lock the third node, and so on. This prevents any thread from adding or removing threads in between, allowing them to execute in a pipelined fashion.

This locking protocol is sometimes called “hand-over-hand” locking.

Figure 1.

Figure 1 demonstrates why it is important to perform remove operations in the “hand-over-hand” manner. Thread A is about to remove node a, the first node in the list, while thread B is about to remove node b, where a points to b. Suppose A locks head, and B locks a. A then sets head.next to b, while B sets a.next to c. The net effect is to remove a, but not b.

Before considering the implementation of add and remove operations I’ll show the auxiliary methods that perform some additional work. As you can see, I added comments that explain the idea of each line:

private void lockPair(Node<T> node) { 
   node.lock(); // acquiring the lock of the current node
   node.next.lock(); // acquiring the lock of the next node 
} 
private void unlockPair(Node<T> prevNode, Node<T> currNode) {
   prevNode.unlock(); // releasing the lock of the current node
   currNode.unlock(); // releasing the lock of the next node 
} 
private Node<T> find(int key) { 
   // lock first node pair.
   Node<T> currNode = head; lockPair(currNode); 
   while (currNode.next.key < key) 
      // traverse in hand-over-hand fashion.
      currNode = nextNode(currNode); 
   return currNode; 
}

Full implementation of all three operations you can find on my GitHub account.

As this linked list uses fine-grained locks (per node), it performs well when contention is medium. The major disadvantage of this implementation is that it still uses locks.

These are the last days of 2021. I’m finishing this post peeling another tangerine and slowly chewing each piece. It was a great year. Happy New Year!