CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 7 of 8 · 4 min read

Lock ranks

Checking the order at run time

In plain words: A rule that exists only in a document will be broken. A cheap check can enforce it: give each lock a rank, record in each thread the highest rank it holds, and stop the program the moment a thread asks for a rank that is not higher.

typedef struct { pthread_mutex_t m; int rank; const char *name; } RLock;
static __thread int top = 0;                        /* highest rank held by this thread */
static __thread int saved[16], depth;

void rlock(RLock *l) {
    if (l->rank <= top) { fprintf(stderr, "lock order violation: taking %s (rank %d) while holding rank %d\n",
                                  l->name, l->rank, top); abort(); }
    pthread_mutex_lock(&l->m); saved[depth++] = top; top = l->rank;
}
void runlock(RLock *l) { top = saved[--depth]; pthread_mutex_unlock(&l->m); }

The keyword __thread gives each thread its own copy of top. With A at rank 1 and B at rank 2, taking A then B printed "A then B: fine". Taking B and then A printed:

lock order violation: taking A (rank 1) while holding rank 2

and the program aborted. The error appears on the first wrong call, in a single thread, even if no other thread is running. That is the key advantage: a deadlock needs bad timing, but the order check needs no timing at all.

Real tools do the same without ranks. ThreadSanitizer and Helgrind (page 7 shows both) learn the order from the program's own behaviour, and report "lock-order-inversion" when two threads use opposite orders. On the test machine, TSan reported the inversion in a run of the two-lock program that finished normally. The Linux kernel's lockdep does this for the whole kernel (OSC, chapter 8).

To summarise, the four methods cost different things. Which one is the best depends on what the program does:

Method Best used when Weakness
Share or spool The data is read-only, or output can be queued Not for resources that need exclusive writing
All at once There are few resources and short critical sections Less concurrency, and needs early knowledge
Try and give back The order cannot be fixed Needs back-off; wasted attempts; livelock risk
Lock ordering There are many locks Every code path must follow the order

Lock rank

A lock rank is a number attached to a lock to define its place in the global order; a thread may take a lock only if its rank is higher than every rank the thread already holds.

Example: with A at rank 1 and B at rank 2, a thread holding B that calls lock(A) has broken the rule.

Interview angle

"How do you prevent deadlocks in code?" The answer expected is lock ordering: number the locks, always take them in increasing order. Add that when the order cannot be fixed, trylock with release and back-off is the second choice, and that tools such as ThreadSanitizer can find order inversions even in runs that do not deadlock.

Check yourself: 1. Why can the rank check find a bug in a run with only one thread? 2. What does __thread do to the variable top? 3. Name one tool that finds lock-order mistakes without using ranks.

Words you will meet

Word Meaning
Prevention Designing so that one of the four conditions can never hold
Spooling Queueing output on disk so a single daemon uses the device
All-or-nothing Taking every needed resource in one step, or none
trylock A lock call that returns at once if the lock is busy
Back-off A short, often random, wait before a retry
Lock ordering A global order in which all threads take locks
Lock rank The number of a lock in that order
Livelock Threads that keep running but make no progress (page 6)

Quick notes

  • Deadlock prevention is the design of a system or program so that at least one of the four necessary conditions can never hold, which makes a deadlock impossible by construction.
  • Spooling is a technique in which jobs write their output to a queue on disk, and a single helper process later sends it to a device that cannot be shared, so that only the helper ever holds the device.
  • All-or-nothing acquisition is a rule that a thread obtains every resource it needs in a single step, or none of them, so that it never holds one resource while waiting for another.
  • Resource preemption is the taking back of a resource from a thread that holds it, before the thread has finished using it; in a program it is done by the.
  • Lock ordering is a rule that gives every lock a place in one global order, and requires every thread to take the locks it needs in that order; it removes.
  • A lock rank is a number attached to a lock to define its place in the global order; a thread may take a lock only if its rank is higher than every rank the thread already holds.