# 3.4 Concurrency: Time Is of the Essence
# 3.4.1 The Nature of Time in Concurrent Systems
# Exercise 3.38
(define balance 100)
(define (peter) (set! balance (+ balance 10)))
(define (paul) (set! balance (- balance 20)))
(define (mary) (set! balance (- balance (/ balance 2))))Out of six permutations, there are four possible values: 35, 40, 45, 50.
(set! balance 100) (peter) (paul) (mary) balance => 45 (set! balance 100) (peter) (mary) (paul) balance => 35 (set! balance 100) (paul) (peter) (mary) balance => 45 (set! balance 100) (paul) (mary) (peter) balance => 50 (set! balance 100) (mary) (peter) (paul) balance => 40 (set! balance 100) (mary) (paul) (peter) balance => 40If the system allows the processes to be interleaved, you could also get results equivalent to leaving out one or more of the assignments, where the new value is overwritten before being read. In
mary, the value divided by 2 could also be different from the value being subtracted from.(set! balance 100) (parallel-execute peter paul mary) balance =?> [25 30 35 40 45 50 55 60 80 90 110]
# 3.4.2 Mechanisms for Controlling Concurrency
# 3.4.2.1 Serializing access to shared state
Without serialization, there are five possible values:
(define x 10)
(parallel-execute
(lambda () (set! x (* x x)))
(lambda () (set! x (+ x 1))))
x =?> [11 100 101 110 121]With serialization, it narrows to two possible values:
(define x 10)
(let ((s (make-serializer)))
(parallel-execute
(s (lambda () (set! x (* x x))))
(s (lambda () (set! x (+ x 1))))))
x =?> [101 121]
(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)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (protected withdraw))
((eq? m 'deposit) (protected deposit))
((eq? m 'balance) balance)
(else (error 'make-account "unknown request" m))))
dispatch))# Exercise 3.39
(define x 10)
(let ((s (make-serializer)))
(parallel-execute
(lambda () (set! x ((s (lambda () (* x x))))))
(s (lambda () (set! x (+ x 1))))))Three of the five values are still possible:
x =?> [101 ; squared, then incremented
121 ; incremented, then squared
100] ; incremented between squarer read and write# Exercise 3.40
(define x 10)
(parallel-execute
; process S: 3 1 2
(lambda () (set! x (* x x)))
; process C: 7 4 5 6
(lambda () (set! x (* x x x))))There are five possible values:
x =?> [100 1000 10000 100000 1000000]We will now demonstrate how the steps can interleave to produce these values. There are seven relevant steps: three in S, four in C. Steps 1, 2, 4, 5, and 6 are reads; steps 3 and 7 are writes.
(define steps-s-read '(1 2))
(define steps-s-write '(3))
(define steps-c-read '(4 5 6))
(define steps-c-write '(7))
(define steps-s (append steps-s-read steps-s-write))
(define steps-c (append steps-c-read steps-c-write))
(define steps (append steps-s steps-c))Only certain permutations of steps are valid orderings:
(define (in? x xs)
(and (not (null? xs))
(or (= (car xs) x) (in? x (cdr xs)))))
(define (good-interleave? p)
(define (iter latest-s latest-c p)
(or (null? p)
(and (in? (car p) steps-s)
(> (car p) latest-s)
(iter (car p) latest-c (cdr p)))
(and (in? (car p) steps-c)
(> (car p) latest-c)
(iter latest-s (car p) (cdr p)))))
(iter 0 0 p))
(define possible-orders
(filter good-interleave? (permutations steps)))
(length possible-orders) => 35For a given ordering of steps, we can simulate the execution:
(define (execute-steps steps x)
(define (iter s-reads c-reads steps x)
(cond ((null? steps) x)
((in? (car steps) steps-s-read)
(iter (cons x s-reads) c-reads (cdr steps) x))
((in? (car steps) steps-c-read)
(iter s-reads (cons x c-reads) (cdr steps) x))
((in? (car steps) steps-s-write)
(iter s-reads c-reads (cdr steps) (apply * s-reads)))
((in? (car steps) steps-c-write)
(iter s-reads c-reads (cdr steps) (apply * c-reads)))
(else (error 'execute-steps "unknown step number" (car steps)))))
(iter '() '() steps x))
(define final-values
(map (lambda (ss) (execute-steps ss 10)) possible-orders))
final-values
=> '(1000000 100000 10000 1000 100 100000 10000
1000 100 10000 1000 100 1000 100
10000 100000 10000 1000 100 10000 1000
100 1000 100 10000 10000 1000 100
1000 100 10000 1000 100 10000 1000000)There are many duplicates, so let’s count the occurrences.
(define (group xs)
(let ((occurence-table (make-table)))
(define (iter xs)
(if (null? xs)
occurence-table
(let ((n (lookup (car xs) occurence-table)))
(insert! (car xs)
(if n (+ n 1) 1)
occurence-table)
(iter (cdr xs)))))
(iter xs)))
(group final-values)
=> '(*table* (100 . 10)
(1000 . 10)
(10000 . 10)
(100000 . 3)
(1000000 . 2))The largest value, 1000000, can be obtained in two ways:
(execute-steps '(1 2 3 4 5 6 7) 10) => 1000000 ; squared, then cubed
(execute-steps '(4 5 6 7 1 2 3) 10) => 1000000 ; cubed, then squaredIf we serialize the procedures, we always get that value:
(define x 10)
(let ((s (make-serializer)))
(parallel-execute
(s (lambda () (set! x (* x x))))
(s (lambda () (set! x (* x x x))))))
x => 1000000# Exercise 3.41
Ben Bitdiddle is wrong. It is unnecessary to serialize access to the bank balance because it would make no difference. If we serialize it, then the value will be read either before or after (in sequence) it is written, assuming someone is withdrawing or depositing concurrently. However, if we don’t serialize it, we still get one value or the other. There is nothing that can be interleaved because reading the balance takes only one step, assuming the Scheme implementation considers this a thread-safe operation.
# Exercise 3.42
This is a safe change to make. Each bank account still has one serializer and the deposit and withdraw procedures returned from the dispatcher are always protected by it. It makes no difference in what concurrency is allowed. If it did, then the specification of make-serializer must be incorrect.
# 3.4.2.2 Complexity of using multiple shared resources
(define (exchange account1 account2)
(let ((difference (- (account1 'balance)
(account2 'balance))))
((account1 'withdraw) difference)
((account2 'deposit) difference)))
(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) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'balance) balance)
((eq? m 'serializer) balance-serializer)
(else (error 'make-account "unknown request" m))))
dispatch))
(define (deposit account amount)
(let ((s (account 'serializer))
(d (account 'deposit)))
((s d) amount)))
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
((serializer1 (serializer2 exchange))
account1
account2)))# Exercise 3.43
The balances in the accounts start out as $10, $20, and $30. Exchanging balances A and B works by taking D = A - B, and then withdrawing to get A’ = A - D = B and depositing to get B’ = B + D = A. Going from {A, B} to {B, A}, we can see that any sequence of exchanges preserves the set {A, B}, and in this particular case {10, 20, 30}.
Using the first version of exchange, where only individual deposits and withdrawals are serialized (by account), the {10, 20, 30} set will not be preserved. For example, let us refer to concurrent processes P and Q:
(define (exchange acc1 acc2)
(let ((diff (- (acc1 'balance) ; (1)
(acc2 'balance)))) ; (2)
((acc1 'withdraw) diff) ; (3)
((acc2 'deposit) diff))) ; (4)Suppose accounts A, B, C begin with $10, $20, $30. Process P exchanges A and B, process Q exchanges A and C. We interleave steps as P1, Q1, Q2, Q3, Q4, P2, P3, P4. P finds the balance of A to be $10. Then Q carries out all its steps: A and C are exchanged, and P’s read operation does not affect this. Therefore A, B, C now have balances $30, $20, $10. Now P carries out its three remaining steps. It finds B to have $20. It calculates 10 - 20 = -10. It withdraws -10 from A, leaving A with a balance of 30 - (-10) = 40. It deposits this in B, leaving B with a balance of 20 + (-10) = 10. Now the balances of A, B, C are $40, $10, $10. Thus {10, 20, 30} is not preserved. But it does preserve the sum 10 + 20 + 30 = 40 + 10 + 10 = 60. This would be the case even if diff was a random number, because deposits and withdrawals are serialized, and we deposit and withdraw the same diff.
If we used the original implementation but changed make-account so that it did no serializing, the sum would not be preserved. This is because the steps of the deposits and withdrawals of concurrent processes will interleave, and we have already seen the issues this produces earlier.
# Exercise 3.44
(define (transfer from-acc to-acc amount)
((from-acc 'withdraw) amount) ; (1)
((to-acc 'deposit) amount)) ; (2)Ben Bitdiddle is correct. This procedure will behave correctly, even with multiple concurrent transfers involving the same accounts. Suppose we transfer $10 between A and B (process P), and concurrently transfer $20 between A and C (process Q). P1 and Q1 will be in the same serialization set, because they both withdraw from A. P2 and Q2 will neither be in that set nor in each other’s set. One deposits to B, and the other deposits to C. They cannot interfere with each other.
The essential difference between the transfer problem and the exchange problem is that the exchange amount depends on the current balances, and so it must include steps that read the balance, introducing a hole into which a concurrent step can be interleaved, unless the whole exchange is serialized.
# Exercise 3.45
Louis Reasoner is wrong. The problem with automatically serializing all deposits and withdrawals is that, when we create our own multi-step operations such as the exchange or the transfer, and we serialize them, we end up with nested serialization, i.e. deadlock.
# 3.4.2.3 Implementing serializers
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(lambda args
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val)))))We cannot use this implementation because not all the Schemes we’re targeting support atomics for a proper implementation of test-and-set!. Instead, we define make-mutex in src/compat to use the Scheme’s own threading library.
(define (make-mutex-from-scratch)
(let ((cell (list #f)))
(lambda (m)
(cond ((eq? m 'acquire)
(let retry () (when (test-and-set! cell) (retry))))
((eq? m 'release) (clear! cell))))))
(define (clear! cell)
(set-car! cell #f))
(define (test-and-set! cell)
(if (car cell)
#t
(begin (set-car! cell #t)
#f)))# Exercise 3.46
(define make-mutex make-mutex-from-scratch)
(paste (:3.4.2.3 make-serializer))Suppose we execute this using the non-atomic test-and-set!:
(define x 100)
(let ((s (make-serializer)))
(parallel-execute
;; 2 1
(s (lambda () (set! x (+ 100 x)))) ; process P
;; 2 1
(s (lambda () (set! x (/ x 2)))))) ; process QThere are four possible values:
x =?> [100 ; P1, P2, Q1, Q2 (serial)
150 ; Q1, Q2, P1, P2 (serial)
200 ; P1, Q1, Q2, P2 (interleaved)
50] ; Q1, P1, P2, Q2 (interleaved)The interleaved results can happen since with the non-atomic test-and-set!, both processes can acquire the mutex at the same time. Both check if the cell is set, find it is #f, and then both set it to #t.
# Exercise 3.47
- Sempahore in terms of mutexes
Note: This assumes that any thread can acquire/release the mutex. It does not work with mutex implementations that only allow the owner to release it.
(define (make-semaphore n)
(let ((count n)
(count-mutex (make-mutex))
(queue-mutex (make-mutex)))
(queue-mutex 'acquire) ; starts out locked
(lambda (m)
(cond ((eq? m 'acquire)
(count-mutex 'acquire)
(set! count (- count 1))
(when (< count 0)
(count-mutex 'release)
(queue-mutex 'acquire))
(count-mutex 'release))
((eq? m 'release)
(count-mutex 'acquire)
(set! count (+ count 1))
(if (<= count 0)
(queue-mutex 'release)
(count-mutex 'release)))
(else (error 'make-semaphore "unexpected message" m))))))We can’t test this because not all Schemes we support have the required property of allowing any thread to release another’s mutex.
Semaphore in terms of atomic
test-and-set!operations(define (make-semaphore-from-scratch n) (let ((count n) (cell (list #f))) (define (the-semaphore m) (cond ((eq? m 'acquire) (let retry () (when (test-and-set! cell) (retry))) (cond ((> count 0) (set! count (- count 1)) (clear! cell)) (else (clear! cell) (the-semaphore 'acquire)))) ; busy wait ((eq? m 'release) (let retry () (when (test-and-set! cell) (retry))) (set! count (+ 1 count)) (clear! cell)) (else (error 'make-semaphore-from-scratch "unexpected message" m)))) the-semaphore))
We can’t test this because our test-and-set! is not actually atomic.
# 3.4.2.4 Deadlock
One way to avoid deadlock is to give each account a unique identification number, and write procedures like exchange so that they always try to acquire the mutex for the lower-numbered account first.
# Exercise 3.48
Before we locked the exchange operation using the serializers of both accounts. This can lead to deadlock if lock sequences A, B and B, A are interleaved such that both processes are trying to acquire the mutex that the other has already acquired. They wait forever, and neither is released. This problem is solved when we lock accounts in a particular order because that interleaving wouldn’t work. Both processes would have the lock sequence A, B, and the second process cannot acquire A after the first already has. The first is then free to acquire B, perform its operations, and release both.
(define *uuid* 0)
(define (gen-uuid)
(set! *uuid* (+ *uuid* 1))
*uuid*)
(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 ((id (gen-uuid))
(s (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'balance) balance)
((eq? m 'serializer) s)
((eq? m 'identifier) id)
(else (error 'make-account "unknown request" m))))
dispatch))
(define (serialized-exchange a1 a2)
(let ((s1 (a1 'serializer))
(s2 (a2 'serializer)))
((if (< (a1 'identifier) (a2 'identifier))
(s1 (s2 exchange))
(s2 (s1 exchange)))
a1
a2)))This is safe from deadlocks:
(define a1 (make-account 10))
(define a2 (make-account 20))
(parallel-execute
(lambda () (serialized-exchange a1 a2))
(lambda () (serialized-exchange a2 a1)))
(a1 'balance) => 10
(a2 'balance) => 20# Exercise 3.49
The deadlock avoidance mechanism used in Exercise 3.48 would not work with (contrived-exchange acc), which exchanges the balance of acc with that of the account whose balance is closest to the balance of acc. We must either always lock acc first (without the ordering mechanism of 3.48, allowing deadlocks), or we must lock after accessing acc, creating a hole into which other operations can be interleaved.
# 3.4.2.5 Concurrency, time, and communication
Concurrency is hard. It is intimately tied to communication. There may be cases where the “real” value (e.g. account balance) are irrelevant or meaningless except at special synchronization points.