src/sicp/ex3_43.rkt

   1 #lang racket
   2
   3 #|
   4
   5 ;; Argue that if the processes are run sequentially, after any number of
   6 ;; concurrent exchanges, the account balances should be $10, $20, and $30
   7 ;; in some order.
   8
   9 Support a1, a2 and a3 are the 3 accounts with the balances $10, $20 and $30
  10 respectively. Now the operations involved in the serialized exchange are:
  11 (in order)
  12
  13 (serialized-exchange a1 a2)
  14
  15 1. acquire serializer s1 for a1
  16 2. acquire serializer s2 for a2
  17 3. create serialized exchange procedure using s2
  18 4. create serialized exchange procedure using s1
  19 5. apply the resulting procedure of step 4 to a1 and a2.
  20
  21 Now, if we have two concurrent serialized exchange procedure running, one
  22 of them is (serialized-exchange a1 a2) and the other is
  23 (serialized-exchange a1 a3), then the following is one possibility.
  24
  25 1. procedure 1 (called p1 from here after) acquires s1.
  26 2. p2 also tries to acquire s1 but since p1 has already acquired it, it waits.
  27 3. p1 proceeds with the exchange. resulting in a swapped exchange of balance
  28    with a1 having 20 and a2 having 10.
  29 4. At this point, s1 is released and p2 acquires s1. It proceeds to do the
  30    exchange, resulting in exchange of 20 and 30.
  31 5. End result is: a1 = 30, a2 = 10, a3 = 20.
  32
  33 ;; Draw a timing diagram like the one in figure 3.29 to show how this
  34 ;; condition can be violated if the exchanges are implemented using the
  35 ;; first version of the account-exchange program in this section.
  36
  37 Without serializer, the exchange procedure involves the following steps.
  38
  39 1. get balance of account1
  40 2. get balance of account2
  41 3. find difference between 1 and 2.
  42 4. withdraw the difference from account1
  43 5. deposit the difference to account2
  44
  45 When two concurrent exchange procedures (exchange a1 a2) and (exchange a1 a3)
  46 are running, the following can happen.
  47
  48 1. p1 gets balance of a1 (10).
  49 2. p2 gets balance of a1 (10).
  50 3. p1 gets balance of a2 (20).
  51 4. p2 gets balance of a3 (30).
  52 5. p1 calculates difference (-10).
  53 6. p2 calculates difference (-20).
  54 7. p1 withdraws -10 from a1 (20).
  55 8. p2 withdraws -20 from a1 (40).
  56 9. p1 deposits -10 to a2 (10)
  57 10. p2 deposits -20 to a3 (10)
  58
  59 At the end, a1 = 40, a2 = 10, a3 = 10
  60
  61 ;; On the other hand, argue that even with this exchange program, the sum of
  62 ;; the balances in the accounts will be preserved.
  63
  64 (see above. We can try with different interspersing of operations. Note that
  65 the above steps assume that withdrawals and deposits and balance operations
  66 are 'atomic')
  67
  68 ;; Draw a timing diagram to show how even this condition would be violated
  69 ;; if we did not serialize the transactions on individual accounts.
  70
  71 It is obvious that this will be violated. For example, withdraw operation
  72 involves (set! balance (- balance amount)) and deposit operation involves
  73 (set! balance (+ balance amount)). It could be that, after the target
  74 balance is calculated for an account, a new balance amount is set which
  75 is reset by the previously calculated value of balance. This is a non-linear
  76 operation and not a composition.
  77
  78 |#