22

Operating System Concepts says

7.4.4 Circular Wait

The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration.

Computers Systems: a Programmer's Perspective says

Programs deadlock for many reasons, and preventing them is a difficult problem in general. However, when binary semaphores are used for mutual exclusion, as in Figure 12.44, then you can apply the following simple and effective rule to prevent deadlocks:

Mutex lock ordering rule: Given a total ordering of all mutexes, a program is deadlock-free if each thread acquires its mutexes in order and releases them in reverse order.

Is it correct that both describe the same deadlock-prevention method?

If yes, in this deadlock-prevention method:

  • Is "releases mutexes in reverse order" required to make this deadlock-prevention method work? (It appears in the second book, but not in the first book.)

  • Does the order between releases of the mutexes matter to existence of deadlock? (For example, for two semaphores s and t, order P(s), P(t), V(t), V(s), and order P(s), P(t), V(s), V(t))

Thanks.

1
  • 6
    Both texts correctly say that lock ordering is a method that guarantees success, but not the only method. It is sufficient but not necessary for preventing deadlocks. – Kilian Foth Nov 2 '20 at 5:59
31

For a deadlock (more specifically, a circular wait) to occur, there needs to be a circular chain of n ≥ 2 mutexes (or other exclusively lockable resources) R1, R2, …, Rn such that, for each k from 1 to n−1, the current owner of Rk is waiting for Rk+1, while the current owner of Rn is waiting for R1.

To prevent such a circular wait situation from occurring, it is sufficient to define some total order on the mutexes and require that no thread ever tries to acquire a mutex while holding another mutex further up in the order.

This requirement guarantees that, while it's possible to have a chain of n mutexes Rk, 1 ≤ kn, with each mutex Rk other than the last being held by a thread waiting for mutex Rk+1, any such chain of mutexes must necessarily be ascending in the total order, and thus the holder of the last mutex Rn in such an ascending chain may not attempt to acquire any earlier mutex in the chain.


This requirement is slightly weaker than the one given in the books you quote. In particular, while it still requires threads to acquire mutexes in ascending order, it does not quite require them to always release them in the reverse order.

For example, let the mutexes A and B be ordered such that A < B. Now, under the requirement given above, both of the following sequences of operations are permissible.

  1. Acquire A; acquire B; release B; release A.
  2. Acquire A; acquire B; release A; release B.

and so are both of the following:

  1. Acquire A; acquire B; release B; acquire B; release B; release A.
  2. Acquire A; acquire B; release B; acquire B; release A; release B.

but the following sequence is not:

  1. Acquire A; acquire B; release A; acquire A; …

The problematic event that can trigger a deadlock here is not the release of A before B, but rather trying to acquire A while holding B. This is because another thread might have grabbed the mutex A when it was released, and trying to reacquire it while still holding B could deadlock if the new owner of A was waiting for B to be released.

Of course, requiring threads to always release mutexes in reverse order of acquisition would also forbid the problematic sequence #5 above, since the thread would have to release B before releasing A, and thus couldn't hold B any more when it tried to reacquire A. But this stronger requirement would also forbid the perfectly safe and harmless sequences #2 and #4.


Now, at this point, all of this might seem like needless pedantry: after all, if you're going to release both A and B anyway, isn't it kind of obvious that the order doesn't really matter, and wouldn't it be perfectly reasonable to always release B first anyway, thus sticking to the simple "release in reverse order" rule?

Well, no, not really.

First of all, the order of consequent mutex releases can actually matter for performance, even if it doesn't matter for correctness. For example, consider the following variant of sequence #2 above, where the thread is performing some slow processing that initially requires both A and B, but where A is only used at the start of the processing:

Acquire A; acquire B; (start processing); release A; (continue slow processing while holding only B); release B.

Now, any other thread that only needs mutex A can execute concurrently during most of the slow processing, which wouldn't be possible if the slow thread had to keep holding A until it can release B.

Also, with more mutexes, the weaker condition ("never acquire an earlier mutex while holding a later one") can actually permit qualitatively distinct access patterns that the stronger condition ("always acquire in ascending and release in descending order") would forbid. For example, the weaker condition allows a thread to "climb" an ascending chain of mutexes while always holding only a subset of them, as in:

Acquire A; acquire B; (do something with A and B); release A; acquire C; (do something with B and C); release B; acquire D; (do something with C and D); …

In particular, two or more such threads can safely and efficiently run concurrently, with the second thread starting to process resources A and B as soon as the first one has released them both, while the first thread is now working on C and D.

If mutexes had to always be released in reverse order of acquisition, however, this sequence of operations would be forbidden, and would have to be replaced ether with something like this:

Acquire A; acquire B; (do something with A and B); acquire C; (do something with B and C); acquire D; (do something with C and D); …; release D; release C; release B; release A.

which prevents any concurrent execution of such threads, since the mutex A isn't released until the whole "climb" is finished, or possibly with something like this:

Acquire A; acquire B; (do something with A and B); release B; release A; acquire B; acquire C; (do something with B and C); release C; release B; …

which may not be feasible if the resource protected by mutex B cannot be safely accessed by other threads between the two processing steps.


That said, neither of your books presents the "acquire in ascending and release in descending order" rule as anything but a sufficient requirement to prevent deadlocks, which it is. It's just not a necessary requirement for deadlock prevention (and, indeed, neither is the weaker requirement I gave above).

And, in something like 99% of all cases, "acquire in ascending and release in descending order" is perfectly practical and suitable. Indeed, the difficult part of implementing this rule isn't usually the "release in descending order" part, which is easily accomplished e.g. by storing acquired locks on a stack, but ensuring that the mutexes get acquired in a consistent order in the first place.

And that part of the requirement is necessary: if one thread tries to first acquire A and then B, while another thread tries to first acquire B and the A, then those threads are vulnerable to deadlocks regardless of the order in which they might be planning to later release those mutexes.

14
  • 3
    I really appreciate the counterexample here with the AB-BC-CD processing showing how reverse release order is not required, and in fact can be counterproductive as far as performance goes. – Mr.Mindor Nov 2 '20 at 20:12
  • 2
    +1 for the "sliding window of locks" example; may be useful for workflow processing, or dataflow-like graphs, or similar situations. – Pablo H Nov 2 '20 at 20:45
  • 1
    One concrete example of the "climb an ascending chain of mutexes" would be a thread that walks along a linked list of items, where each item has a mutex that covers both the data in that item and the pointer to the next item in the list. – psmears Nov 3 '20 at 14:28
  • 1
    Release in "the reverse order" allows the change to be undone if there is an error etc. Hence I can see way books recommend it, as otherwise transactions may be left half done. – Ian Nov 3 '20 at 23:49
  • 2
    @DemonCode: I assume Ian's saying that releasing mutexes in reverse order would allow reverting changes to resources without having to release and reacquire the mutexes for those resources. My example "climber" thread indeed cannot do that: if it runs into an error while processing resources B & C (or C & D, or D & E…), it cannot revert changes made to resource A without first releasing and reacquiring all mutexes. But releasing in reverse order doesn't actually guarantee the ability to safely revert transactions, either, if the thread ever releases a mutex before the end of a transaction. – Ilmari Karonen Nov 4 '20 at 12:07
11

For a deadlock to occur a system has to have several properties simultaneously. Wikipedia has some more details on this but for short:

  1. Mutual Exclusion
  2. Incremental Acquisition
  3. No preemption
  4. Circular Waits

A system that can dead-lock must have all of these properties. If even one of them has been removed, then dead-lock is impossible even if the system is extraordinarily slow to execute.

The first approach you highlighted attacks the 4th property. By enforcing a global order of acquiring locks no process can block another while waiting for a lock.

The "and release in reverse order" is neither here nor there in this scheme. What it is probably referring to is the simplest way to manage such a scheme: A stack. Which naturally would release locks in reverse order.

2
  • Well, releasing in reverse order is certainly naturally if the order for the locks are manually ordered. But what if they aren't? Their addresses induce an arbitrary total order, but following that for releasing is generally useless overhead. – Deduplicator Nov 2 '20 at 23:28
  • @Deduplicator Kinda my point there. – Kain0_0 Nov 3 '20 at 4:47
8

Let's have a look at the simplest form of deadlock: the kiss of death of two processes trying to acquire 2 mutexes:

       (1)                 |        (2)
  Lock mutex A   (success) |    Lock mutex B   (success)
  Lock mutex B   (wait)    |    Lock mutex A   (wait) 
                           X
                OUCH! DEADLOCK OCCURED

This simple example shows that you can have a deadlock regardless of the order of release.

To avoid this situation, the advice is to always acquire the mutexes in the same order ("if each thread acquires its mutexes in order")

       (1)                 |        (2)
  Lock mutex A   (success) |   Lock mutex A   (wait)
  Lock mutex B   (success) |    
  ....                     |
  Unlock mutex A           |                  (success)
  Relock mutex A (wait)    |   Lock mutex B   (wait)
                           X
                OOPS! I DEADLOCK AGAIN

In this second example, I acquired new mutexes in the same order, but releasing mutexes in an unsuitable order might create a deadlock. Here I chose the lazy example with a relock, but I could obtain the same situation without the ugly relock with a couple more processes and mutexes. This is why you need to release mutexes in the reverse order of acquisition. Like with parenthesis in an expression.

Edit: With these simple examples, you can see that not respecting the rule for ordered acquisition and reverse ordered release easily leads to deadlocks. So for robust coding, apply this rule. Of course, with more than two mutexes and complex algorithms, you can sometimes demonstrate that some combination of locks can never happen. But this leaves a lot of constraints on all the programs sharing the mutexes, and it's easy to forget about those constraints in the maintenance. So for the sake of the future, still apply this rule.

15
  • 1
    @DemonCode that is a reasonable approach in many cases. Locking is quite tricky to get right in complex applications, as not all locks are always visible on the same level of abstraction - once upon a time I managed to deadlock one of my threads with a lock in the entrails of tomcat (I had not read the docs of the event handling code I was extending carefully enough). Of course, such things can be hard to track down later, as they don't necessarily deadlock always (or even very often). And even then, it may take a while until anyone notices the server slowly running out of threads. – Hulk Nov 2 '20 at 10:19
  • 2
    @DemonCode I edited the conclusion which contained a logical error. Indeed, it is possible to have deadlock free code without the rule. Withtout the relock in my second example, my code would be deadlock free under the condition. But this imposes constraints on the code, and the deadlock is only avoided if all the programs sharing the same mutexes fulfil the constraints. FIFO lock/unlock may well work with your code base, but it might fail with some arbitrary code using the same mutexes. – Christophe Nov 2 '20 at 10:19
  • 1
    @Hulk I've actually abandoned event-driven programming a number of years ago. If APIs require it, I tend to build a miniature ecosystem for it. What I've come to favor in place are data structures that are very quick to sort of diff as we can in version control, where things like UI updates can occur by just diffing their copy of the data with incoming data that's newer, and update the relevant parts (and some threads woken up by condition variables). Mostly I've designed architectures around the fact that I suck at reasoning about thread safety in cases where it's not blatantly obvious. :-D – user377672 Nov 2 '20 at 10:37
  • 8
    I'd view the example where (1) has a lock on B and then is trying to acquire A then deadlocks as violating the acquire in order rule rather violating the release in reverse order rule, as it's not the releasing of A that is the problem but acquiring it at while holding the lock on B. But I do suspect that it might be the sort of thing the OP's quote is talking about. – Pete Kirkham Nov 2 '20 at 15:17
  • 7
    For me your second example is also violating the first part of the rule, since thread 1 is not respecting the order of locking by trying to lock A while holding a lock on B (exactly like thread 2 on in the first example). The fact that it previously had a lock on A does not make any difference. – Didier L Nov 2 '20 at 17:44
1

Mutex lock ordering rule: Given a total ordering of all mutexes, a program is deadlock-free if each thread acquires its mutexes in order and releases them in reverse order.

As written, this is wrong. If thread X acquires its mutexes in the order A, B and releases in reverse order B, A, but thread Y aquires its mutexes in the order B, A and releases in reverse order A, B, then you are in danger of deadlocks. That will happen if X aquires A, and Y aquires B before X does.

Here's a correct criterion: Divide the mutexes into groups 0, 1, 2, 3, ... If every thread only locks mutexes that belong to a higher group than any mutex it currently holds, and releases all mutexes at some point in arbitrary order, then you are deadlock free.

Alternative: Arrange all mutexes in a total order. If every thread only locks mutexes that are higher than any mutex it currently holds, and releases all mutexes at some point in arbitrary order, then you are deadlock free.

The first can be easier to check. Mutexes in group 0 can be locked if you don't hold any other mutex in group 0. Mutexes in group 1 can be locked if you don't hold any other mutex in group 0 or group 1. Mutexes in group 2 can be locked if you don't hold any other mutex in group 0, 1 or 2. And so on.

In practice, you can create a wrapper around “mutex” which contains which group your mutex belongs to, and during any lock checks that no mutex in the same or lower group is held. If that rule is violated, you have a potential deadlock, that is your code might deadlock with some bad luck. You fix this either by changing your locking code, or by assigning mutexes to different groups.

0

No, only the order of acquisition is important. As long as you hold them, you can release Mutexes in any order. It may be more "efficient" if work can be done somewhere else with only one of the Mutexes to have a specific order of release, but it's still deadlock-free.

This changes if you re-acquire the Mutex of course, but you are not doing that.

To be clear, this assumes that you DO indeed release all Mutexes. If one of them fails to be released, all bets are of, obviously.

Having the release order be the reverse of the acquisition order is nice for readability, but if you are literally just doing "Get A and B, Do X, Release A,B" the order of release doesn't matter.

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.