7

I am looking into Eric Lippert's answer to this Stack Overflow question.

In his answer, he uses the phrase "lock ordering inversions" in regard to deadlocks. I've searched the web and have come across priority inversion. Is this the same concept? If not, what exactly is lock ordering inversion?

0
5

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.

8
  • Great answer @Steve, I understood that. I'm curious why when searching for this term on the web I get so few results. Is there a resource you could recommend to further research fundamental principles in this area?
    – fractor
    Apr 1 '21 at 12:15
  • 1
    @fractor, I'm not sure myself to be honest. I've encountered the problem purely in database contexts. It seems to be something that is often an afterthought in design - where people ask "how do I solve all these deadlocks?" rather than "how do I plan to coordinate locks being taken concurrently on multiple tables?". It'll be very interesting to me if anyone else can contribute quality resources on this problem area.
    – Steve
    Apr 1 '21 at 13:13
  • @Steve kinda makes sense - since the database is capable of detecting deadlocks and reverting one side and letting your code restart that side - instead of just waiting forever - the occasional deadlock is no problem
    – user253751
    Apr 1 '21 at 14:54
  • I often wonder how much of the science around concurrency was developed in the transportation industries. I know it was a large part of the development of telecommunication e.g. for synchronizing clocks.
    – JimmyJames
    Apr 1 '21 at 15:12
  • 1
    Right but I wonder how much of the math that we associate with computing was initially developed for these purposes. I've found bits of this history because Einstein was involved in the review of a lot of patents around this and they were relevant to his later work. It's sort of a niche subject though. I know this is OT but I appreciate any resources on this topic if you know them.
    – JimmyJames
    Apr 1 '21 at 16:16
1

No, these are not the same.

Priority inversion does not cause deadlock. Priority inversion makes a process with lower priority executing, while process of higher priority is blocked, since another process of lower priority took the lock. This is not a deadlock, not all participant processes are locked, and there's a forward progress.

Lock ordering inversion may cause deadlocks, when two or more processes try to acquire locks in different order, so that each holding a lock which another is trying to acquire.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.