SICP Section 3.4 Concurrency: Time Is of the Essence

Exercise 3.38. Suppose that Peter, Paul, and Mary share a joint bank account that initially contains $100. Concurrently, Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in the account, by executing the following commands:
Peter: (set! balance (+ balance 10)) Paul: (set! balance (- balance 20)) Mary: (set! balance (- balance (/ balance 2)))
a. List all the different possible values for balance after these three transactions have been completed, assuming that the banking system forces the three processes to run sequentially in some order.

b. What are some other values that could be produced if the system allows the processes to be interleaved? Draw timing diagrams like the one in figure 3.29 to explain how these values can occur.

Answer: a. Processes run sequentially in some order
45 (Peter, Paul, Mary)
35 (Peter, Mary, Paul)
45 (Paul, Peter, Mary)
50 (Paul, Mary, Peter)
40 (Mary, Peter, Paul)
40 (Mary, Paul, Peter)

Exercise 3.40. Give all possible values of x that can result from executing
(define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (* x x x))))
Which of these possibilities remain if we instead use serialized procedures:
(define x 10) (define s (make-serializer)) (parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (* x x x)))))
Answer: Possible values are 10^4, 10^5, 10^6. If serialized procedures are used only 10^6 remains.

Exercise 3.41. Ben Bitdiddle worries that it would be better to implement the bank account as follows (where the commented line has been changed):
(define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) ;; continued on next page (let ((protected (make-serializer))) (define (dispatch m) (cond ((eq? m 'withdraw) (protected withdraw)) ((eq? m 'deposit) (protected deposit)) ((eq? m 'balance) ((protected (lambda () balance)))) ; serialized (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch))
because allowing unserialized access to the bank balance can result in anomalous behavior. Do you agree? Is there any scenario that demonstrates Ben's concern?

Answer: There are no scenarios that call for Ben's changes. The set! command is the only one that affects balance. Anyone trying to view the balance will see the value before or after setting and nothing else.

Exercise 3.42. Ben Bitdiddle suggests that it's a waste of time to create a new serialized procedure in response to every withdraw and deposit message. He says that make-account could be changed so that the calls to protected are done outside the dispatch procedure. That is, an account would return the same serialized procedure (which was created at the same time as the account) each time it is asked for a withdrawal procedure.
(define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (let ((protected (make-serializer))) (let ((protected-withdraw (protected withdraw)) (protected-deposit (protected deposit))) (define (dispatch m) (cond ((eq? m 'withdraw) protected-withdraw) ((eq? m 'deposit) protected-deposit) ((eq? m 'balance) balance) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)))
Is this a safe change to make? In particular, is there any difference in what concurrency is allowed by these two versions of make-account ?

Answer: This is a safe change to make. Serialization is not affected by whether the procedure is serialized inside dispatch or outside it.

Exercise 3.44. Consider the problem of transferring an amount from one account to another. Ben Bitdiddle claims that this can be accomplished with the following procedure, even if there are multiple people concurrently transferring money among multiple accounts, using any account mechanism that serializes deposit and withdrawal transactions, for example, the version of make-account in the text above.
(define (transfer from-account to-account amount) ((from-account 'withdraw) amount) ((to-account 'deposit) amount))
Louis Reasoner claims that there is a problem here, and that we need to use a more sophisticated method, such as the one required for dealing with the exchange problem. Is Louis right? If not, what is the essential difference between the transfer problem and the exchange problem? (You should assume that the balance in from-account is at least amount.)

Answer: ouis is wrong. Ben's procedure is sufficient to handle the requirement.

The difference between the transfer and exchange problems is that the latter calculates the difference in account balances before withdrawing/depositing. There is no way to guarantee that the account balances do not change between the calculation of the difference and the subsequent actions.

Exercise 3.45. Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that make-account-and-serializer should have exported the serializer (for use by such procedures as serialized-exchange) in addition to (rather than instead of) using it to serialize accounts and deposits as make-account did. He proposes to redefine accounts as follows:
(define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (let ((balance-serializer (make-serializer))) (define (dispatch m) (cond ((eq? m 'withdraw) (balance-serializer withdraw)) ((eq? m 'deposit) (balance-serializer deposit)) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch))
Then deposits are handled as with the original make-account:
(define (deposit account amount) ((account 'deposit) amount))
Explain what is wrong with Louis's reasoning. In particular, consider what happens when serialized-exchange is called.

Answer: Louis's logic will lead to a deadlock situation when serialized-exchange is called. This procedure invokes a (doubly) serialized version of exchange. Exchange in turn invokes the serialized versions of withdraw and deposit. Exchange cannot finish until both these are completed; due to serializing neither withdraw nor deposit can start until exchange is over. This leads to a deadlock.

Exercise 3.47. A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations. Give implementations of semaphores

a. in terms of mutexes

b. in terms of atomic test-and-set! operations.

Answer: a. Semaphore in terms of mutexes
(define (make-semaphore n) (let ((mutex (make-mutex)) (count 0)) (define (the-semaphore m) (cond ((eq? m 'acquire) (mutex 'acquire) (if (< count n) (set! count (+ count 1))) (mutex 'release)) ((eq? m 'release) (mutex 'acquire) (if (> count 0) (set! count (- count 1))) (mutex 'release)))) the-semaphore))
b. Semaphore in terms of atomic test-and-set! operations
(define (make-semaphore n) (let ((cell (list false)) (count 0)) (define (the-semaphore m) (cond ((eq? m 'acquire) (test-and-set! cell) (if (< count n) (set! count (+ count 1))) (clear! cell)) ((eq? m 'release) (test-and-set! cell) (if (> count 0) (set! count (- count 1))) (clear! cell)))) the-semaphore))