2 days ago
my attempt to do the exercises in sicp.
Thursday, March 18, 2010
sicp exercise 3.43
;; Exercise 3.43. Suppose that the balances in three accounts start out as $10, $20, and $30, and that multiple processes run, exchanging the balances in the accounts. Argue that if the processes are run sequentially, after any number of concurrent exchanges, the account balances should be $10, $20, and $30 in some order. Draw a timing diagram like the one in figure 3.29 to show how this condition can be violated if the exchanges are implemented using the first version of the account-exchange program in this section. On the other hand, argue that even with this exchange program, the sum of the balances in the accounts will be preserved. Draw a timing diagram to show how even this condition would be violated if we did not serialize the transactions on individual accounts.
;; Assume that accounts a1 and a2 are being exchanged, and simulaneously a2 and a3 are being exchanged. since a2 is being locked by both processes, a2 will take part in only one exchange at a time. The exchange procedure releases the serializer only after the exchange has completed. So both exchage processes will be serialzed, and the account balances will be $10,$20 or $30 in whatever order.
;; Similar reasoning applies to the sum of the account balances.