CSE Roadmap

Core tier · about 5 hours · 7 parts

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:

  1. 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, sleep or a network request, since every other thread waits too. The sleeping holder of the test above kept the waiter for 280 ms.
  2. 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).
  3. Protect invariants, not just variables. If two fields must always agree (a count and a list length), one mutex must cover both.
  4. 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.
  5. 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.