Is “releases mutexes in reverse order” required to make this deadlock-prevention method work

concurrencydeadlinesmutexsemaphoresynchronization

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.

Best Answer

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 ≤ k ≤ n, 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 — 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.