sicp-ex-3.49



<< Previous exercise (3.48) | Index | Next exercise (3.50) >>


leafac

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.


xdavidliu

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).