<< Previous exercise (3.42) | Index | Next exercise (3.44) >>


Disagree that sum of balances must remain the same in the first exchange program.

If we have three accounts A B, C with balances 10,20,30 respectively:

by running P1: (exchange C A) and P2:(exchange C A) concurrently this may happen:

1. the difference is set to 20 on both P1 and P2.

2. 20 is withdrawn from C and 20 is deposited to A in P1 Now the balances are C->10 A->30 B->20

3. 20 is withdrawn from C again, giving the Insufficient funds message with no money taken. 20 is deposited to A again Now the balances are C->10 A->50 B->20

the total has increased from 60 to 80. Forgive me if I have missed something.


Double serializing the exchange procedure, using both accounts' serializers, protects the exchange operations from being interleaved with other account operations from either account. This makes exchange atomic. So its behavior will be as expected.

With the original definition of exchange, the exchange operation will not be atomic, but it will be composed of exactly four atomic operations, namely read the two account balances, make an atomic withdrawal from the larger account, and make an atomic deposit into the smaller account.

To see how the original exchange definition might not preserve the three balances, consider the following three exchanges:

The original exchange allows us to interleave P3 between reads of P1 and P2:

Final balances:

However the sum of all three balances cannot change. This is because each exchange adds and removes an equal amount between accounts. So total deposits will always equal total withdrawals.


You can perform the following simulation to verify´╝Ü

 (define (count-demo . arrays) 
     (let ((demo-result '())) 
         (define (rec result arrays) 
             (let ((arys (filter 
                             (lambda (ary) (not (null? ary))) 
                 (if (null? arys) 
                     (set! demo-result (cons result demo-result)) 
                         (lambda (ary) 
                                 (append result (list (car ary))) 
                                     (lambda (other) 
                                         (if (eq? other ary) 
                                             (cdr other) 
         (rec '() arrays) 
 (define (make-account name balance) 
     (put 'balance name balance) 
     (lambda (m) 
         (cond ((eq? m 'set-balance!) 
                 (lambda (new) (put 'balance name new))) 
             ((eq? m 'get-balance) 
                 (get 'balance name)) 
             (else (error "Unknown operation -- MAKE-ACCOUNT" m))))) 
 (define (set-balance! acc new) 
     ((acc 'set-balance!) new)) 
 (define (get-balance acc) 
     (acc 'get-balance)) 
 (define a1 (make-account 'a1 10)) 
 (define a2 (make-account 'a2 20)) 
 (define a3 (make-account 'a3 30)) 
 (define (reset-accounts) 
     (set-balance! a1 10) 
     (set-balance! a2 20) 
     (set-balance! a3 30)) 
 (define (get-balances-all) 
     (let ((a1 (get-balance a1)) 
           (a2 (get-balance a2)) 
           (a3 (get-balance a3))) 
                 (string a1) 
                 (string a2) 
                 (string a3) 
                 (string (+ a1 a2 a3)) 
 (define (make-exchange name acc1 acc2) 
     (put name 'read_acc1 
         (lambda ()           
             (put name 'acc1 (get-balance acc1)))) 
     (put name 'read_acc2 
         (lambda () 
             (put name 'acc2 (get-balance acc2)))) 
     (put name 'write_acc1 
         (lambda () 
                 (-  (get-balance acc1) 
                     (-  (get name 'acc1) 
                         (get name 'acc2)))))) 
     (put name 'write_acc2 
         (lambda () 
                 (+  (get-balance acc2) 
                     (-  (get name 'acc1) 
                         (get name 'acc2)))))) 
     (list (cons name 'read_acc1) (cons name 'read_acc2) (cons name 'write_acc1) (cons name 'write_acc2))) 
 (define (make-possibility demo) 
     (define (get-proc k-v) 
         (get (car k-v) (cdr k-v))) 
     (define (make-info k-v) 
             (symbol->string (car k-v)) 
             (symbol->string (cdr k-v)))) 
     (define (add-info info1 info2) 
     (let ((proc-list (map get-proc demo)) 
           (result '())) 
         (for-each (lambda (proc) (proc)) proc-list) 
         (set! result (get-balances-all)) 
         (lambda (m) 
             (cond ((eq? m 'result) result) 
                 ((eq? m 'info) 
                     (accumulate add-info "\b\b\t" (map make-info demo))) 
                 (else (error "Unknown operation -- MAKE-RESULT" m)))))) 
 (define (make-statistician demos) 
     (let ((possibility-list (map make-possibility demos)) 
           (result-list '())) 
         (define (iter possibility-list) 
             (if (null? possibility-list) 
                 (let ((possibility (car possibility-list))) 
                     (let ((result (possibility 'result)) 
                           (info (possibility 'info))) 
                         (if (memq result result-list) 
                             (put 'result result (cons info (get 'result result))) 
                                 (set! result-list (cons result result-list)) 
                                 (put 'result result (list info)))) 
                         (iter (cdr possibility-list)))))) 
         (iter possibility-list) 
         (lambda (m) 
             (cond ((eq? m 'all) result-list) 
                 ((eq? m 'one) 
                     (lambda (result) 
                         (get 'result result))) 
                 (else (error "Unknown operation -- MAKE-STATISTICIAN" m)))))) 
 (define (one-poss statistician result) 
     (let ((count 0)) 
             (lambda (info) 
                 (display info) 
                 (set! count (+ 1 count))) 
             ((statistician 'one) result)) 
 (define (all-poss statistician) 
     (statistician 'all)) 
 (define Peter (make-exchange 'Peter a1 a2)) 
 (define Paul (make-exchange 'Paul a1 a3)) 
 (define S (make-statistician (count-demo Peter Paul))) 
 ; Run the following statement to prove the middle two questions 
 (all-poss S) 
 ; Possible results 
 ; "(30)+(10)+(20)=(60)"  "(40)+(10)+(10)=(60)"  "(20)+(30)+(10)=(60)" 
 ; The ratio of their occurrence times 5:60:5 
 ; ============================================================================== 
 ; If you want to answer the last question 
 ; The following changes are required 
 ; The rest of the code remains the same 
 (define (make-exchange name acc1 acc2) 
     (put name 'read_acc1 
         (lambda ()           
             (put name 'acc1 (get-balance acc1)))) 
     (put name 'read_acc2 
         (lambda () 
             (put name 'acc2 (get-balance acc2)))) 
     (put name 'write_r_acc1 
         (lambda () 
             (put name 'write_r_d_acc1 (get-balance acc1)))) 
     (put name 'write_w_acc1 
         (lambda () 
                 (-  (get name 'write_r_d_acc1) 
                     (-  (get name 'acc1) 
                         (get name 'acc2)))))) 
     (put name 'write_r_acc2 
         (lambda () 
             (put name 'write_r_d_acc2 (get-balance acc2)))) 
     (put name 'write_w_acc2 
         (lambda () 
                 (+  (get name 'write_r_d_acc2) 
                     (-  (get name 'acc1) 
                         (get name 'acc2)))))) 
         (cons name 'read_acc1) 
         (cons name 'read_acc2) 
         (cons name 'write_r_acc1) 
         (cons name 'write_w_acc1) 
         (cons name 'write_r_acc2) 
         (cons name 'write_w_acc2))) 
 ; Possible results 
 ; "(30)+(10)+(20)=(60)" "(30)+(10)+(10)=(50)"  "(20)+(10)+(10)=(40)"  "(40)+(10)+(10)=(60)"  "(20)+(30)+(10)=(60)" 
 ; The ratio of their occurrence times 28:200:200:468:28