Part 6 of 7 · 5 min read
Practice
Using mutexes well
Think of it this way. A kitchen can have one knife for everyone, or one for each cook. One knife is simple and creates a queue. Many knives are fast, but cooks must remember which knife is for what. The analogy stops in one place: a knife is not harmed by being forgotten, while a forgotten mutex is a bug.
In plain words: The size of the data that one mutex protects is its granularity. A coarse lock protects a large structure with one mutex: simple, correct and often slow, since all threads queue on it. A fine lock protects each small part with its own mutex: more parallel, harder to get right, with more locks to take and a risk of deadlock when a thread needs two of them.
Rules that experience supports:
- Keep the critical section short. Compute outside the lock, and enter it only to read or change the shared data. Do not hold a mutex across a slow call such as
read,sleepor a network request, since every other thread waits too. The sleeping holder of the test above kept the waiter for 280 ms. - Start coarse, measure, and refine. A single mutex per data structure is a sound start. Split it only when a measurement shows contention (page 9).
- Protect invariants, not just variables. If two fields must always agree (a count and a list length), one mutex must cover both.
- Lock in a fixed order when a thread needs two mutexes. A transfer between two accounts locks both, and if one thread locks account 1 then 2 while another locks 2 then 1, each may hold one lock and wait for the other for ever. This is a deadlock, studied in Level 5. The usual cure is a global order, for example by the address or number of the account.
- Do not call unknown code with a lock held: a callback might take another lock in the wrong order, or call back into your code.
void transfer(account *a, account *b, int amount) {
account *first = a < b ? a : b; /* order by address */
account *second = a < b ? b : a;
pthread_mutex_lock(&first->mu);
pthread_mutex_lock(&second->mu);
a->balance -= amount; b->balance += amount;
pthread_mutex_unlock(&second->mu);
pthread_mutex_unlock(&first->mu);
}
Lock granularity
Lock granularity is the amount of data protected by one lock: a coarse-grained design uses few locks that each cover much data, and a fine-grained design uses many locks that each cover little.
Example: one mutex for a whole hash table is coarse, and one mutex for each bucket is fine.
Common mistake
Locking only the writers. A reader that does not lock can see half-updated data, such as a count that has been changed while the list has not yet been. Readers need the lock too, or a design made for them (page 7).
Interview angle
Answer in your head first, then open it.
What is a mutex?
A lock with one holder at a time. Waiters sleep, and only the holder unlocks.
What is the difference between a mutex and a spinlock?
A waiting mutex sleeps and uses no processor. A spinlock loops, and wastes processor time if the wait is long.
What is a futex?
A user-space integer with kernel wait and wake, so that uncontended locks need no system call.
What is a recursive mutex?
A mutex that its owner can lock several times, with a count.
How do you avoid deadlock with two mutexes?
Always lock them in the same global order.
Check yourself:
1. Why is holding a mutex across sleep harmful?
2. What is the order rule for two locks?
3. Give one example each of coarse and fine locking.
Words you will meet
| Word | Meaning |
|---|---|
| Mutex | A lock held by at most one thread |
| Contention | A thread tries to take a lock that another holds |
| Futex | User-space integer plus kernel wait and wake |
| Fast path | The case that needs no system call |
| Recursive mutex | A mutex the owner can lock again, with a count |
| Error-checking mutex | A mutex that reports wrong use as an error |
| Robust mutex | A mutex that tells the next owner that its holder died |
| Granularity | How much data one lock covers |
| Deadlock | Threads waiting for each other for ever (Level 5) |
Quick notes
- A mutex is a synchronisation object that can be held by at most one thread at a time: a thread that locks it gains exclusive entry to a critical section.
- Lock contention is the situation in which a thread tries to acquire a lock that another thread currently holds, so that it must wait; a lock with frequent contention is a bottleneck.
- A futex is a Linux mechanism consisting of an integer in user memory and two kernel operations on it, wait (sleep if the integer still holds a given value) and.
- A recursive mutex is a mutex that its owning thread may lock several times, keeping a count of the locks, and which becomes free only when the owner has unlocked it as many times as it locked it.
- Lock granularity is the amount of data protected by one lock: a coarse-grained design uses few locks that each cover much data, and a fine-grained design uses many locks that each cover little.