Course contentsShow
← Computer Science
Lesson 2584 of 2,87257. Concurrency FundamentalsFree lesson

Concurrent Lists: Hand-Over-Hand Locking

Implementing fine-grained locking in linked lists by locking adjacent nodes during traversal.

Concurrent Lists: Hand-Over-Hand Locking

What You'll Learn

You'll learn how to implement fine-grained locking in linked lists by locking adjacent nodes during traversal, enabling higher concurrency than a single global lock.

The Problem with Coarse-Grained Locking

When using a single lock for an entire linked list, only one thread can traverse or modify the list at any time—even if threads are working on completely different parts of the list. This severely limits concurrent access.

The Hand-Over-Hand Approach

Hand-over-hand locking (also called lock coupling) works like a cautious climber on a rope bridge: you never let go of one handhold until you've firmly grasped the next.

During list traversal:

  1. Lock the head node
  2. Lock the next node
  3. Unlock the previous node
  4. Repeat until you reach your target

This creates a "traveling window" of two locked nodes moving through the list.

Why This Works

Multiple threads can traverse different parts of the list simultaneously. Thread A working near the head and Thread B working near the tail hold different locks, so they don't block each other. You only need to wait if another thread is working on the exact same adjacent nodes.

Trade-offs

Benefits: Much better concurrency than a single global lock, especially for long lists with operations spread throughout.

Costs: More complex implementation with higher overhead (acquiring/releasing many locks during traversal), and potential for deadlock if not implemented carefully (always lock in traversal order).

Key Takeaway: Hand-over-hand locking enables fine-grained concurrency in linked lists by maintaining locks on only adjacent node pairs during traversal, allowing multiple threads to work on different list regions simultaneously.