Locking Granularity and Performance Trade-offs

1. What is Locking Granularity?

Locking granularity refers to the amount of data protected by a single lock. At one extreme, you could use a single lock for all shared data in your program. At the other, you could have a separate lock for every single element in a large data structure.

• Coarse-Grained Locking: Using one lock to protect a large amount of data (e.g., a single lock for an entire hash table or a whole array of bank accounts).
• Fine-Grained Locking: Using many locks to protect small, independent pieces of data (e.g., a lock for each bucket in a hash table, or a lock for each individual bank account).

The image below illustrates this concept. A lock could be applied at the database level (very coarse), at the level of a functional unit, or down to the level of an individual record (very fine).

Choosing the right granularity is a crucial design decision that balances simplicity against performance.

2. The Core Trade-Off: Contention vs. Complexity

The choice between coarse- and fine-grained locking boils down to a trade-off between two competing concerns:

1. Contention: This occurs when multiple threads are blocked, waiting to acquire the same lock. High contention serializes your code, destroying parallelism and performance.
2. Complexity: This relates to the difficulty of implementing and debugging the locking strategy. Managing many locks is harder than managing one and introduces risks like deadlock.

Let's explore this trade-off in detail by reading a key section from a university guide on concurrency.

As the reading suggests, a common and wise strategy is to start with a simple, coarse-grained lock. If and only if profiling reveals that lock contention is a performance bottleneck, you should then invest the effort to refactor your code to use a more complex, fine-grained approach.

3. Granularity in Practice with OpenMP

This theoretical trade-off has direct, practical consequences when using OpenMP. Let's look at two examples.

3.1 atomic vs. critical

You've already used both atomic and critical. You can think of this as a choice of granularity:

• #pragma omp atomic: This is a highly specialized, very fine-grained construct. It is restricted to protecting a single memory location during a simple update (like x++ or sum += val). Because its scope is so limited, hardware can often implement it with extremely efficient, low-overhead instructions.
• #pragma omp critical: This is a more general-purpose, coarser-grained construct. It protects an entire block of code, which could modify multiple variables. An unnamed critical section uses a single global lock, making it very coarse. Named critical sections (critical(my_name)) are finer, but still typically have higher overhead than an atomic operation.

Using critical when atomic would suffice is a common performance mistake.

3.2 Minimizing Time in Critical Sections

The main drawback of coarse-grained locking is that threads hold the lock for longer than necessary, blocking other threads. A key optimization principle is to hold locks for the minimum time required for correctness.

This often means refactoring code to pull as much work as possible out of the critical section.

The final, most optimized version in that reading should look familiar. Each thread finds a local maximum (priv_max) in its own chunk of the array, and only then enters a single critical section at the very end to update the global maximum. This is essentially a manual implementation of what the OpenMP reduction clause does for you automatically! It's a powerful pattern: perform work locally in parallel, then synchronize only when you need to combine the final results.

4. The Danger of Fine-Grained Locking: Deadlock

While fine-grained locking reduces contention, it increases complexity and introduces a severe risk: deadlock. A deadlock occurs when two or more threads are stuck in a circular wait, where each thread is waiting for a lock held by the next thread in the circle. The program grinds to a halt.

This risk arises when an operation needs to acquire multiple locks. For example, transferring money between two bank accounts might require locking both accounts to ensure the transaction is atomic. If Thread A locks account X and tries to lock Y, while Thread B locks account Y and tries to lock X, they will deadlock.

A classic and robust solution to this problem is lock ordering. If all threads are required to acquire locks in the same global order (e.g., by their memory address or a unique ID), circular waits become impossible.

5. A Deeper Look at Lock Performance

Finally, it's useful to understand that the "cost" of a lock isn't just about the time spent waiting. The lock/unlock operations themselves consume CPU cycles. When a thread tries to acquire a lock that is already held, it has two options:

1. Spinning: Enter a tight loop, repeatedly checking if the lock is free. This consumes CPU cycles but can acquire the lock very quickly once it's released. It's efficient if the wait time is expected to be very short.
2. Yielding (or Blocking): Tell the OS to put the thread to sleep and wake it up when the lock is available. This frees up the CPU for other threads but incurs the high cost of a context switch (typically millions of CPU cycles). It's efficient if the wait time is expected to be long.

Modern systems often use a competitive strategy: spin for a short time, and if the lock is still not free, then yield. This provides a balance that performs well in most cases.

Conclusion

You've now explored the critical trade-offs involved in choosing a locking strategy. This is less about finding a single "right" answer and more about making an informed engineering decision based on the specific needs of your application.

Key Takeaways:

• Coarse-Grained Locking: One lock for many data items. It's simple to implement and less prone to deadlocks but can cause high contention, limiting parallelism.
• Fine-Grained Locking: Many locks for individual data items. It allows for high parallelism but is more complex to implement and carries a significant risk of deadlock.
• The Strategy: Start with coarse-grained locking. Use a profiler to measure contention. Only move to a finer-grained strategy if contention is a proven performance bottleneck.
• Optimization: Always aim to minimize the time spent holding a lock. Refactor code to perform expensive computations outside of critical sections.
• Deadlock Prevention: When using multiple locks, prevent deadlock by enforcing a strict global lock acquisition order.

Preview of the Next Lesson

In this lesson, we saw how threads can compete for locks. But what if threads, operating on completely separate and independent data, still slow each other down? This can and does happen due to a subtle interaction with the CPU cache system known as false sharing. In our next lesson, you will learn to diagnose and mitigate false sharing to improve cache performance in OpenMP applications.