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:
- Many of locking's sins have pragmatic design solutions that
work well in most cases, for example:
- Lock hierarchies to avoid deadlock.
- Deadlock-detection tools, for example, the Linux kernel's
lockdep facility [Cor06].
- Locking-friendly data structures, such as
arrays, hash tables, and radix trees, which will
be covered in Chapter
.
- Some of locking's sins are problems only at high levels of
contention, levels reached only by poorly designed programs.
- 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.
- 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.
- 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
Paul E. McKenney
2011-12-16