Locks and What They Cost
A lock turns a gap into a queue. Only one thread at a time may run the code between acquiring the lock and releasing it, so the lost update of the previous topic cannot happen: the second worker's read waits until the first worker's write is done. The idea is that simple, and it is correct.
The cost is where engineers go wrong. An uncontended lock costs tens of nanoseconds. A heavily contended one can cost a context switch per acquisition and make 16 cores behave like one. The price of a lock is set by two numbers, how many threads want it at the same moment and how long each one holds it, and neither of them is visible where the lock is written.
Mutual Exclusion
A critical section is the stretch of code that touches shared state. A lock, also called a mutex, for mutual exclusion, guarantees that at most one thread is inside it at a time. The others wait at the entrance. Edsger Dijkstra published the first general solution in 1965, built from ordinary reads and writes of shared memory alone. Today's locks rest instead on an atomic instruction the processor provides, the subject of the fifth topic in this chapter, which makes the check and the claim of the lock one indivisible step.
A Lock Protects an Invariant, by Agreement
The lock does not know what data it guards. It is a flag with a queue, and it works only if every piece of code that touches the data takes the same lock first. One unlocked read or write anywhere in the program reopens the race, and nothing will warn you.
What a lock really protects is an invariant, a rule that must hold whenever anyone looks: "the balance equals the sum of the history", "the count equals the number of items in the list". The critical section is the stretch of code during which the invariant is temporarily false, while one of the two has changed and the other has not. Holding the lock is the promise that nobody else will look during that stretch.
The Cost Curve
Uncontended, acquiring a lock is one atomic operation, about 20 nanoseconds, less than one trip to RAM. Contended across cores, the lock's cache line, the 64-byte unit of Chapter 4, moves from one core's cache to another's on every acquisition, around 100 nanoseconds a move. Contended long enough that waiters give up the core and sleep, each handoff goes through the kernel and a context switch, from Chapter 10, and costs microseconds.
So the lock itself is cheap and the waiting is not. Between the first regime and the third, the cost per acquisition rises by a factor of a hundred or more, while the code has not changed at all. Only the number of threads arriving at the same moment has.
Spinning vs Sleeping
A waiter has two choices. It can spin, looping on the lock until it comes free, which wins when the holder will release it sooner than a context switch would take. It wastes a whole core otherwise, and wastes an entire time slice when the holder has itself been switched out and is not even running. Or it can sleep, handing its core to other work and paying a context switch to wake up.
The mutexes of many runtimes do both: they spin briefly and then sleep, betting that most critical sections are short. On Linux the sleeping half rests on a kernel mechanism called a futex, named here and not taught. The standard mutex of your language has already made this trade for you, which is one reason not to write your own.
Granularity
One lock around everything is simple, correct and serial. It is the serial fraction of Amdahl's law from the first topic of this chapter: every thread passes through it one at a time. One lock per hash bucket or per record lets unrelated work run in parallel, at the price of more locks to reason about and the deadlocks of the next topic.
A readers-writer lock lets many readers in at once and gives a writer exclusive access. It costs more per acquisition than a plain mutex, because it has to count readers, and it wins only when reads dominate and each read holds the lock long enough for the sharing to matter.
The Cost in a System You Run
A global lock around an in-process cache caps a web service at one critical section at a time, whatever the number of cores. A lock held across a network call or a disk read makes every other thread wait for the slowest input or output on Chapter 4's ladder. Hold a lock across a 5-millisecond database call and that lock admits at most 200 holders a second, however many threads are waiting.
Python's global interpreter lock is the coarsest lock there is, one per interpreter, and the last topic of this chapter gives it its own section. The rule that falls out of all of this is short: hold locks briefly, take them rarely and never hold one across input or output.
- "Locks are slow, so avoid them." An uncontended lock costs less than one trip to RAM. The expensive thing is contention, and the fix is shorter or rarer holds, not a hand-built replacement without locks.
- "Reads do not need a lock." A read of state that spans two fields, or of a value another core is writing, can see a half-updated invariant or a stale value. If the write needs the lock, the read of the same invariant needs it too.
- "Finer-grained locking is always faster." Each extra lock adds an acquisition, a cache line and one more ordering to get wrong. At low contention one coarse lock is faster and far easier to keep correct.
- "A spinlock is the fast kind of lock." Spinning wins only for holds shorter than a context switch on a machine with idle cores. With more threads than cores, a spinner can burn its whole time slice waiting for a holder that is not even running.
- "Holding a lock during a call out is harmless if the call is quick." The call is quick until the dependency is slow. Then every thread that needs the lock waits on the slowest call, and one stalled request stalls the service.
- Hold a lock for the shortest stretch that keeps the invariant, and never across input or output. Copy what you need, release, then do the slow work.
- Put every access to a piece of shared state behind the same lock, and write down which lock guards which invariant. The agreement is the only thing that makes the lock work.
- Start with one coarse lock, and split it only when measurement shows contention on it. Fine-grained locking is a cost you pay in correctness.
- Use the language's standard mutex rather than a hand-written spin loop. It already makes the spin-or-sleep trade, and in many runtimes it spins briefly before it sleeps.
Knowledge Check
A service holds one lock while it makes a 5 ms database call. How many requests per second can pass through that lock, whatever the thread count?
- About 5,000, since each thread holds the lock for only a few microseconds
- At most about 200 a second, because each holder keeps it for 5 ms
- It scales with the number of threads, as each thread adds its own lock
- At most about 20, because each database call also takes a context switch
A critical section holds a lock for about 50 nanoseconds, on a machine with idle cores. Should waiters spin or sleep?
- Spin, since the hold is much shorter than a context switch
- Sleep, since spinning always wastes a core that other work needs
- Sleep, since the kernel wakes the waiter the moment the lock is free
- Neither, since a 50 ns section cannot be contended by two threads
When does one coarse lock beat many fine-grained ones?
- When there are more cores than threads, so that nothing needs to wait
- Never, since fine-grained locking always lets more work run in parallel
- When contention is low, so the extra locks cost more than they save
- When the data is read far more often than it is ever written
A class keeps a balance and a list of transactions, and writes both under a lock. A reporting method reads both without the lock. What can it observe?
- Nothing wrong, since the reads do not change the data they see
- An exception, because the lock blocks any unlocked reads of the two fields
- Only stale values, never values that contradict each other
- A balance that does not match the list, caught between two updates
Why does the cost of a lock depend more on contention than on the lock itself?
- Waiting moves cache lines or sleeps, and costs far more than the grab
- Contended locks are larger in memory, so they no longer fit in the cache
- Contended locks fall back to a slow path that checks every waiter in turn
- The kernel inspects every lock on each timer tick, more often when busy
You got correct