8. Locking
Keywords: perfbook_html

#
8. Locking

The role of villain in much of the past few decades' concurrency research literature is played by locking, which stands accused of promoting deadlocks, convoying, starvation, unfairness, data races, and all manner of other concurrency sins. Interestingly enough, the role of workhorse in shared-memory parallel software is played by, you guessed it, locking.

There are a number of reasons behind this dichotomy:

1. Many of locking's sins have pragmatic design solutions that work well in most cases, for example:
   1. Lock hierarchies to avoid deadlock.
   2. Deadlock-detection tools, for example, the Linux kernel's lockdep facility [Cor06].
   3. Locking-friendly data structures, such as arrays, hash tables, and radix trees, which will be covered in Chapter .
2. Some of locking's sins are problems only at high levels of contention, levels reached only by poorly designed programs.
3. Some of locking's sins are avoided by using other synchronization mechanisms in concert with locking. These other mechanisms include reference counters, statistical counters, simple non-blocking data structures, and RCU.
4. Until quite recently, almost all large shared-memory parallel programs were developed in secret, so that it was difficult for most researchers to learn of these pragmatic solutions.
5. All good stories need a villain, and locking has a long and honorable history serving as a research-paper whipping boy.

This chapter will give an overview of a number of ways to avoid locking's more serious sins.

Figure: Locking: Villain or Slob?

Figure: Locking: Workhorse or Hero?

Subsections

- 8.1 Staying Alive
  - 8.1.1 Deadlock
  - 8.1.2 Livelock
  - 8.1.3 Unfairness
  - 8.1.4 Inefficiency
- 8.2 Types of Locks
  - 8.2.1 Exclusive Locks
  - 8.2.2 Reader-Writer Locks
  - 8.2.3 Beyond Reader-Writer Locks
- 8.3 Lock-Based Existence Guarantees