Single Lock Performance Issues in Linked Lists

What is Coarse-Grained Locking?

Imagine you have a standard linked list and you want to make it thread-safe. The most straightforward way is to associate a single pthread_mutex_t with the entire list. Before any thread can perform an operation—whether it's inserting a node, deleting a node, or just searching for a value—it must first acquire this single lock.

This approach guarantees correctness and prevents race conditions, but it serializes all operations. Only one thread can be inside the list's code at any given time, completely eliminating the possibility of concurrent work.

Let's get a formal definition of this concept and its primary problem.

As the reading highlights, the core issue is the sequential bottleneck. The section of code protected by the lock can only be executed by one thread at a time, turning a parallel program into a sequential one for that portion of its execution.

The Three Barriers to Scalability

The "sequential bottleneck" manifests as three distinct but related problems that prevent our data structure from scaling with an increasing number of threads.

1. Limited Parallelism & Amdahl's Law: Concurrent operations that should be possible are prevented. For example, one thread inserting a node at the head of a list and another thread deleting a node at the tail are logically independent. They don't conflict. Yet, a coarse-grained lock forces one to wait for the other.
2. Lock Contention: As more threads try to access the list, they "contend" for the single lock. This doesn't just mean threads have to wait their turn. The process of competing for the lock itself creates system overhead, as the CPU and memory subsystem work to manage the competing requests from different processor cores.
3. Blocking: If a thread holding the lock is preempted by the operating system (e.g., its time slice expires, or it has to wait for I/O), all other threads waiting for that lock are also forced to wait. The progress of many threads becomes dependent on the unpredictable scheduling of a single thread.

Given your background in computer science and mathematics, we can formalize the impact of the sequential bottleneck using Amdahl's Law.

As the text explains, Amdahl's Law gives us an equation for the maximum theoretical speedup of a program:

$\text{Speedup}\le \frac{1}{b+\frac{1-b}{P}}$

Where:

• $P$ is the number of processors (or threads).
• $b$ is the fraction of the program that is inherently sequential.

In our coarse-grained linked list, any time spent manipulating the list is part of the sequential fraction $b$. If threads spend 25% of their time working on the list ($b=0.25$), even with an infinite number of processors, the maximum speedup you can ever achieve is $1/0.25=4\times$. The coarse-grained lock puts a hard, low ceiling on scalability.

Visualizing the Performance Collapse

What does this look like in practice? Ideally, as we add more threads, the total time to complete a fixed amount of work should decrease, or the throughput (operations per second) should increase. With a coarse-grained lock, we often see the opposite.

This graph clearly illustrates the problem. Adding more threads to a coarse-grained data structure can make performance worse because the cost of contention and context-switching outweighs the benefit of any parallel work being done outside the critical section.

The following graphs from the ETH Zurich resource provide another view, plotting throughput (operations per second).

The flat line for the coarse-grained implementation is the signature of a sequential bottleneck. The data structure is saturated; it simply cannot process more operations per second, no matter how many threads you throw at it.

Conclusion

In this lesson, we dissected the performance limitations of using a single, coarse-grained lock, with a linked list as our primary case study. While simple and correct, this approach is a major barrier to building scalable concurrent programs.

Key Takeaways:

• Coarse-grained locking uses one lock to protect an entire data structure, serializing all operations.
• This creates a sequential bottleneck, which can be quantified by Amdahl's Law, placing a hard limit on performance improvements from adding more threads.
• The bottleneck manifests as poor scalability due to limited parallelism, high lock contention, and vulnerability to thread blocking.
• In practice, this often leads to performance that stays flat or even degrades as more threads are added.

Preview of the Next Lesson:
Now that we've thoroughly diagnosed the problem, we can start working on the solution. To break the sequential bottleneck, we need to allow more than one thread to work on the list at a time. This requires a more sophisticated locking strategy. In the next lesson, we will design a fine-grained locking strategy for a linked list using 'hand-over-hand' locking (also known as lock coupling), where each node in the list has its own lock.