# SICP section 3.4 - concurrency: time is of the essence

## Exercise 3.38

Part (a): all possible values for balance after the three transactions have been completed:

• Peter → Paul → Mary = $45. • Peter → Mary → Paul =$35.
• Paul → Peter → Mary = $45. • Paul → Mary → Peter =$50.
• Mary → Peter → Paul = $40. • Mary → Paul → Peter =$40.

Part (b): asks us to list some other values that can be produced if the system allows the processes to be interleaved. One possible value is $80, i.e. all three processes access the initial value of balance, but Paul’s process sets the balance last. ## Exercise 3.39 11 and 100. Note: 110 is not possible. $$P_2$$ can no longer change the value of x from 10 → 11 between the two times that $$P_1$$ accesses the value of x, as $$P_1$$ will not relinquish the mutex until it has finished evaluating (* x x). ## Exercise 3.40 Without serialisation: • 100. • 1,000. • 10,000. • 100,000. • 1,000,000. With serialisation: 1,000,000. ## Exercise 3.41 Two scenarios that Ben’s change prohibits are: 1. Having another process access the value of balance mid-deposit. 2. Having another process access the value of balance mid-withdraw. However, in these scenarios it can be argued that the value of balance is correct at the time it is accessed, as the transaction is not yet complete. Therefore, Ben’s change doesn’t prevent anomalous behaviour, as there is none to prevent. ## Exercise 3.42 Ben’s change seems like a safe one to make. There aren’t any apparent differences in concurrency between the two versions. ## Exercise 3.43 If the processes are run sequentially, there will be no interleaving of account operations. Hence, after any number of concurrent exchanges, the account balances should still be$10, $20 and$30 in some order.

An example of what could go wrong if we were to use the first version of the account-exchange program:

• Let a1 = $10, a2 =$20 and a3 = $30. • Attempt to concurrently exchange a1a2, and a2a3. • $$P_1$$ computes the difference between a1 and a2 to be$10.
• $$P_2$$ computes the difference between a2 and a3 to be $10. • $$P_2$$ exchanges the values of a2 and a3 (i.e. $$P_2$$ withdraws$10 from a3 and deposits $10 into a2. a2 is now$30; a3 is now $20. • $$P_1$$ withdraws$10 from a2 and deposits $10 into a1. • Final balances: a1 =$20, a2 = $20 and a3 =$20.

The sum of the balances will remain the same, as each exchange adds and subtracts an equal amount between accounts.

If we don’t serialise transactions on individual accounts, even the “same sum of balances” condition can be violated. Using the above example, let’s trace what happens when the deposit and withdraw operations on a2 are interleaved:

• $$P_1$$ withdraw: get balance ($20). • $$P_2$$ deposit: get balance ($20).
• $$P_2$$ deposit: add $10 to balance ($20 + $10 =$30).
• $$P_1$$ withdraw: subtract $10 from balance ($20 - $10 =$10).
• Final balances: a1 = $20, a2 =$10 and a3 = \$20.

## Exercise 3.44

Ben is correct. The transfer procedure avoids any issues that can occur from computing difference when two exchange operations are interleaved.

## Exercise 3.45

When calling serialized-exchange, the serialisers on both accounts are acquired. When calling deposit and withdraw, the accounts attempt to acquire the serialisers again, and will continue waiting indefinitely as the serialisers will never be released. This is covered in the “Deadlock” subsection several pages ahead.

## Exercise 3.46

• $$P_1$$ tests the cell; value is false.
• $$P_2$$ tests the cell; value is also false.
• Both processes end up acquiring the lock.

## Exercise 3.47

Part (a): given:

(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-mutex 'acquire))) ; Retry
((eq? m 'release) (clear! cell))))
the-mutex))


…we have to define a semaphore in terms of mutexes:

(define (make-semaphore max)
(let ((lock (make-mutex))
(acquired 0))
(define (the-semaphore m)
(cond ((eq? m 'acquire)
(lock 'acquire)
(if (< acquired max)
(begin (set! acquired (+ acquired 1))
(lock 'release))
(begin (lock 'release)
(the-semaphore 'acquire))))
((eq? m 'release)
(lock 'acquire)
(set! acquired (- acquired 1))
(lock 'release))
(else (error "Unknown request: MAKE-SEMAPHORE" m))))
the-semaphore))


Procedure flow:

• (the-semaphore 'acquire) → acquire lock → acquired < max → increment acquired → release lock.
• (the-semaphore 'acquire) → acquire lock → acquired = max → release lock → recursively call (the-semaphore 'acquire).
• (the-semaphore 'release) → acquire lock → decrement acquired → release lock.

Part (b): we have to define a semaphore in terms of atomic test-and-set! operations:

(define (make-semaphore max)
(let ((cell (list false))
(acquired 0))
(define (the-semaphore m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-semaphore 'acquire))
(if (< acquired max)
(begin (set! acquired (+ acquired 1))
(clear! cell))
(begin (clear! cell)
(the-semaphore 'acquire))))
((eq? m 'release)
(if (test-and-set! cell)
(the-semaphore 'release))
(set! acquired (- acquired 1))
(clear! cell))
(else (error "Unknown request: MAKE-SEMAPHORE" m))))
the-semaphore))


Very similar to (a), except we now wait on cell. An example using (the-semaphore 'release):

• cell is truetest-and-set! returns true → recursively call (the-semaphore 'release).
• cell is falsetest-and-set! sets cell to true and returns false → decrement acquired → set cell to false.

## Exercise 3.48

Given two accounts a1 and a2, if a1 is the smaller-numbered of the two accounts, both processes will first attempt to lock a1. a2 can only be locked after a1 is, therefore the deadlock is avoided.

Rewriting serialized-exchange to incorporate the deadlock-avoidance method:

(define (make-account id 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 'id) id)
((eq? m 'withdraw) protected-withdraw)
((eq? m 'deposit) protected-deposit)
((eq? m 'balance) balance)
(else
(error "Unknown request: MAKE-ACCOUNT"
m))))
dispatch)))

(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
(if (< (account1 'id) (account2 'id))
((serializer2 (serializer1 exchange))
account1
account2)
((serializer1 (serializer2 exchange))
account1
account2))))


## Exercise 3.49

If a process needs to first acquire a shared resource in order to discover which additional shared resources it will require, there is no way to enforce the ordering of resources.