Is "releases mutexes in reverse order" required to make this deadlock-prevention method work?

Question

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.

Answer 1

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) R₁, R₂, …, R_n such that, for each k from 1 to n−1, the current owner of R_k is waiting for R_k+1, while the current owner of R_n is waiting for R₁.

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 R_k, 1 ≤ k ≤ n, with each mutex R_k other than the last being held by a thread waiting for mutex R_k+1, any such chain of mutexes must necessarily be ascending in the total order, and thus the holder of the last mutex R_n 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:

3. Acquire A; acquire B; release B; acquire B; release B; release A.
4. Acquire A; acquire B; release B; acquire B; release A; release B.

but the following sequence is not:

5. 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 — ensuring that threads competing for mutexes attempt to acquire them in a consistent same order — is necessary to avoid deadlocks. In particular, 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.