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.
- Acquire A; acquire B; release B; release A.
- Acquire A; acquire B; release A; release B.
and so are both of the following:
- Acquire A; acquire B; release B; acquire B; release B; release A.
- Acquire A; acquire B; release B; acquire B; release A; release B.
but the following sequence is not:
- 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.