Exercise 3.48.  Explain in detail why the deadlock-avoidance method 
described above, (i.e., the accounts are numbered, and each process 
attempts to acquire the smaller-numbered account first) avoids deadlock 
in the exchange problem. Rewrite serialized-exchange to incorporate this 
idea. (You will also need to modify make-account so that each account is 
created with a number, which can be accessed by sending an appropriate 
message.)

————————————————————————————————————————————————————————————————————————

In the exchange-accounts problem, there are only two accounts being 
accessed at a time by each process.  There can be any number of such 
processes running, and deadlock can occur between any number of them.

For example, it is possible that one process has a lock on account A and 
is waiting for a lock on B, while another has a lock on B and is waiting 
for a lock on C, and a third has a lock on C and is waiting for A.  So 
it is not sufficient to prove that any two processes cannot deadlock; we 
must prove that there cannot be any set of exchange-account processes 
that can deadlock.

Since exchange-account only accesses two accounts, for there to be a 
deadlock there must be some exchange-account process P1 running which 
has a lock on an account A and is waiting for a lock on some other 
account B, and there must be some other process P2 which holds a lock on 
account B, and requires the lock on A to be freed before it can proceed, 
either because it is waiting for A directly, or because it is waiting on 
some other process which is waiting on A (either directly or 
indirectly).

Given that the lock on the lower-numbered account is always acquired 
first, the locked account A must be lower-numbered than the account B.  
It is impossible that process P2, which holds a lock on B, would be 
waiting for a lock on A directly, since, because A is lower-numbered 
than B, it would not have requested the locks in that order.  By 
transitivity, we can see that any process we can reach by any chain of 
processes that is ultimately waiting on A can only possibly hold locks 
on lower-numbered accounts.  So it is impossible for P2 to be blocked by 
any chain of processes waiting on A, and as long as only 
exchange-account processes are considered there can be no deadlocks.

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    (if (< (account1 'account-number)
           (account2 'account-number))
        ((serializer1 (serializer2 exchange)) account1 account2)
        ((serializer2 (serializer1 exchange)) account1 account2))))

Corresponding change to make-account skipped.