Fine-Grained Locking for Linked Lists

The Core Idea: From One Lock to Many

The fundamental problem with coarse-grained locking is the single point of contention. The solution, therefore, is to distribute the locking mechanism across the data structure itself.

Fine-grained locking for a linked list means we associate a dedicated mutex with each individual node. This immediately opens up the possibility for concurrent operations. For example, one thread could be working on nodes at the beginning of the list, while another thread works on nodes near the end, each holding different locks.

Let's begin by reading a short introduction to this concept and the specific protocol we'll be using.

As the text states, the strategy we need is hand-over-hand locking. Simply having a lock per node is not enough; we need a strict protocol for acquiring and releasing these locks to prevent race conditions and ensure correctness.

The first step in our design is to modify the data structure itself. Each node must contain its own mutex.

typedef struct node {
    pthread_mutex_t m;  // The mutex protecting this specific node
    int             data;
    struct node*    next;
} node_t;

With this structure, we have the building blocks for our fine-grained strategy. Now, we must define the rules for using these locks.

The "Hand-Over-Hand" Locking Protocol

Imagine climbing a ladder or crossing monkey bars. To move forward safely, you grab the next rung before letting go of the one you are currently holding. Hand-over-hand locking in a linked list works on the exact same principle.

To traverse from a predecessor node (pred) to a current node (curr), a thread must:

1. First, hold the lock on pred.
2. Then, acquire the lock on curr.
3. Only after successfully acquiring the lock on curr, release the lock on pred.

This protocol ensures that the link between pred and curr (pred->next) is always protected during traversal. A thread always holds at least one lock, and for the brief moment of transition, it holds two. This prevents another thread from, for example, deleting curr while our traversing thread is trying to move to it.

Let's see a visual walkthrough of how this enables concurrent operations.

Designing the Traversal Algorithm

Now let's translate this protocol into a concrete algorithm. The logic for traversing a list using hand-over-hand locking forms the basis for all other operations like search, insert, and delete.

The following resource provides a C implementation of a list traversal using this protocol. We will focus on the logic inside the for loop, which is the heart of the design.

Let's break down the logic from the hoh function's loop. We use two pointers, p (previous) and n (next).

// Simplified for clarity
node_t *p, *n;

// 1. Start by locking the head node
p = &head;
LOCK(p);

// Loop as long as there's a next node to visit
while ((n = p->next) != NULL) {
    
    // 2. The "Hand-Over": Lock the next node 'n'
    // We are now holding locks on both 'p' and 'n'.
    LOCK(n);

    // This is the critical moment. With both nodes locked, we can
    // safely perform operations that involve both, like deleting 'n'.

    // 3. The "Let-Go": Release the previous node 'p'
    // We now hold the lock only on 'n'.
    UNLK(p);

    // This is the safe place to read or modify the contents of 'n',
    // since we hold its lock exclusively. Other threads can now
    // acquire the lock on 'p' or nodes before it.
    
    // 4. Advance the pointer for the next iteration
    p = n;
}

// 5. Release the final lock after the loop
UNLK(p);

This sequence—lock p, lock n, unlock p—is the fundamental pattern of hand-over-hand locking.

Properties of the Hand-Over-Hand Design

This design isn't just a clever trick; it has important formal properties that make it both correct and efficient.

1. Concurrency: It achieves high concurrency. Multiple threads can be active in the list simultaneously, as long as they are in different sections (i.e., not trying to lock the same node). This directly solves the sequential bottleneck of the coarse-grained approach.
2. Deadlock-Free: This is a critical feature. Since every thread acquires locks in the same, strict order (from head to tail), a circular wait condition—one of the four necessary conditions for deadlock—is impossible. A thread at node C might have to wait for a thread at node D to release its lock, but the reverse will never happen.
3. Limitation: The primary limitation is that traversal is strictly one-directional. This makes some algorithms, like moving a node from the middle of the list to the front, more complex to implement efficiently, as you can't easily go "backward."

Conclusion

In this lesson, we have designed a robust, fine-grained locking strategy for a linked list. We've moved beyond the theory of why coarse-grained locking is slow and have laid out the architectural blueprint for a high-performance, concurrent solution.

Key Takeaways:

• Fine-Grained Locking Design: The core design involves embedding a pthread_mutex_t within each node of the linked list.
• Hand-Over-Hand Protocol: Correctness is ensured by the "lock-next, then-unlock-previous" protocol, which is analogous to climbing a ladder. A thread holds locks on two adjacent nodes (p and n) during the critical transition period.
• Benefits: This design allows for a high degree of concurrency, enabling multiple threads to work on different parts of the list simultaneously.
• Deadlock Prevention: By enforcing a strict lock acquisition order (list traversal order), the design is inherently free from deadlocks.

Preview of the Next Lesson:
With the design firmly in place, it's time to put it into practice. In our next lesson, we will implement the insertion operation for a linked list using fine-grained locking. We'll write the C code to traverse the list using the hand-over-hand protocol to find the correct insertion point and safely modify the list structure.