multithreading – What is a “lock ordering inversion”?

When multiple threads acquire multiple locks, the only way to guarantee progress in certain cases is to ensure that the locks are always taken in the same order.

In the basic case of two locks and two threads, one lock may be designated Lock A, and one lock designated Lock B.

If Thread 1 seizes lock A, then Thread 2 will wait at Lock A until thread 1 releases it. Whilst Thread 2 waits at Lock A, Thread 1 is free to proceed and also seize Lock B. At some point Thread 1 will release Lock A (either before or after releasing B, it doesn’t matter), and Thread 2 will then proceed. If Thread 1 wanted to retake Lock A for whatever reason, then it would only do so after first releasing Lock B. This is the correct ordering, in the sense that it involves no risk of deadlock. A is always taken before B.

In the case of inverted ordering, Thread 1 proposes to seize A before B, whilst Thread 2 proposes to seize B before A. With suitable timing, a situation can come about in which each have seized the first of the locks they proposed to take, yet each also needs access to the other lock in order to proceed. This is a deadlock situation.

A railway analogy may be easiest for anyone who knows anything about signalling principles. If trains only ever go one way along a track, they can never enter deadlock with one another. But if a train is allowed to enter a single-track section from either end, even when another has already entered from the other end, then eventually one of them is going to have to reverse out to let the other go by. In practice, such single-track sections are treated as an indivisible whole – if a train enters from either end, then a lock is taken on the whole section, and the whole section is covered by just one lock.

When concurrent programming is approached as a science, and where locks can be held in a conflicting fashion, then an ordering (or hierarchy) of locks is defined, and all code must seize locks in a way that is consistent with that order or hierarchy. Going against the order is something that is only possible if you are prepared to deal with an ensuing deadlock.

“Priority inversion” in scheduling, meanwhile, is another thing entirely. Again to fall back on a railway analogy, it is holding the fast train in the sidings, to let the slow train go by, which is against the order of the fast/slow priority.