CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 6 of 8 · 3 min read

Lock ordering

In plain words: The fourth method is the one used most in practice. Give every lock a number, and require every thread to take locks in increasing order of number. A thread that holds lock 3 may ask for lock 5, but not for lock 2.

In the transfer program, the account numbers can act as the lock numbers. The function takes the lower-numbered account first, whichever way the money flows:

int lo = a < b ? a : b,  hi = a < b ? b : a;      /* a != b is assumed */
pthread_mutex_lock(&acc[lo].m);
pthread_mutex_lock(&acc[hi].m);
acc[a].bal--; acc[b].bal++;
pthread_mutex_unlock(&acc[hi].m);
pthread_mutex_unlock(&acc[lo].m);

Here is why the rule works. Suppose a cycle existed among threads. Look at the lock with the highest number among all the locks held in the cycle. The thread holding it can only ask for locks with a higher number, and none of those is held by a thread of the cycle, since this one is the highest. So that thread is not waiting for anyone in the cycle, and it will finish. That contradicts the cycle. No cycle can form.

Measured with 4 accounts and 4 threads, the earlier program without the rule got stuck in all 5 runs, after 9 to 703 transfers. With the rule, two runs of 5 s each performed about 53 and 55 million transfers with no stuck lock, and the total money stayed at 4,000.

Two details need care. First, the rule needs distinct locks: if a and b are the same account, the code would lock it twice, so it must be tested first. Second, the order must be chosen when the number of locks is large or changes. A common choice is the address of the lock, or an id stored in the object, since the program cannot know in advance which two accounts a call will use. Large programs also write the order down in a comment or document, for example "inode lock before page lock", and review every new lock against it.

Lock ordering

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 circular wait, since a cycle would need some thread to take a lock that comes before one it already holds.

Example: every transfer locks the account with the smaller number first, so two opposite transfers between accounts 1 and 2 both lock account 1 first.

Common mistake

Lock ordering fails if even one code path breaks the order, and the break may be far from where the lock is declared. A callback that takes a lock while the caller holds a higher-numbered one is enough. One wrong path is a deadlock waiting for its timing.

Check yourself: 1. In the proof, why can the thread holding the highest-numbered lock not be part of a cycle? 2. Why does the code need to handle a == b separately? 3. Why can two transfers in opposite directions between the same two accounts no longer deadlock?