<< Previous exercise (3.48)
| Index |
Next exercise (3.50) >>
If the process can't know all the locks it's going to need prior to
requesting the first lock, there's no way for it to enforce the ordering.
The reason why the scheme from the previous exercise works to prevent deadlocks is that exchanging account balances is a symmetric operation, e.g. exchanging account A with account B is equivalent to exchanging account B with account A.
However, we can conceive of an operation that is *not* symmetric. For example, suppose every account has a list-of-transfer-amounts, and we wanted an operation (serialized-list-transfer account-from account-to), which transfers the amount (car (account-from 'list-of-transfer-amounts)) from account-from to account-to, and then updates the pointer of (account-from 'list-of-transfer-amounts) to the next amount.
In this case, the transfer *must* be serialized with account-to's serialized first (on the inside), and then serialized with account-from's serializer (on the outside); the order is *not* allowed to be permuted to our convenience, e.g. using id numbers or whatever. Hence, suppose one user calls (serialized-list-transfer account-a account-b) and another user calls (serialized-list-transfer account-b account-a), there is a possibility for deadlock that *cannot* be fixed using an id number to determine the other of serialization (since, again, the operation is not symmetric and hence the order of serialization is not freely determined).
I think in this example we could still use account-from and account-to's serializers in any order.
It wouldn't work for procedures that operate on a shared resource
before determining some otherly shared resource to operate on.
Suppose accounts have an internal list of pairs consisting
of an account and an amount and we invent a procedure
that can take one account, and look at the first pair in
its list and make a deposit accordingly.
Than if account A has account B first in its list and vice versa,
concurrently calling our invented procedure on both could result
in a deadlock.