]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex3_43.rkt
rewrite `quote->cons' using `match'.
[sicp.git] / 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 |#