adrianwong programmer · retired coal miner

SICP section 3.4 - concurrency: time is of the essence

Selected exercises

Exercise 3.38

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

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:

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:

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:

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

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:

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):

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.