SICP 3.4.2 Mechanisms for Controlling Concurrency
ノート
３つのステップを２つのプロセスが行うだけで、各ステップの順番は２０通り。
その数は全部で６つのステップがあるので、その順列が6!通り。但し、(a, b, c)、(x, y, z)それぞれの中では順番は入れ替わらない。6!通りの中には(x, y, z)の位置と順序は全く同じで、(a, b, c)の順番だけ入れ替わっている順列がそれぞれ3!通りある筈だが、それらのうちa→b→cの順番の一つしか存在し得ないのでその組み合わせは1/3!になる。(x, y, z)についても同様。従って全体の組み合わせは通り。
Serializing access to shared state
同時には実行出来ない手続きを定義する。あるプロセスがその手続きを実行中に他のプロセスがその手続きを実行しようとした場合には待たされる。
Serializers in Scheme
Racketでスレッドを使って
(define (parallel-execute . procs) (map thread-wait (map (lambda (proc) (thread proc)) procs)))
と定義して実行してみる。繰り返して実行する為に以下の定義。
(define (parallel-test) (let ((x 10)) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (+ x 1)))) x)) (define (iterate-test x result) (if (= x 0) result (let ((v (parallel-test))) (if (memq v result) (iterate-test (- x 1) result) (iterate-test (- x 1) (cons v result))))))
実行してみると
> (iterate-test 100 '()) '(121) > (iterate-test 1000 '()) '(101 121) >
二つのパターンしか出現しない。
そこで、関数内のあちこちでコンテキストスイッチが起りランダムなタイミングで復帰する様に以下のコードに変更する。
(define (dummy-sleep) (define (loop x) (if (< 0 x) (begin (sleep 0) (loop (- x 1))) 'done)) (loop (random 10))) (define (parallel-test) (let ((x 10)) ; (parallel-execute (lambda () (set! x (* x x))) ; (lambda () (set! x (+ x 1)))) (parallel-execute (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second))))) (lambda () (let ((first (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (+ first 1)))))) x))
実行すると
> (iterate-test 100 '()) '(101 121 11 110 100) >
100回の実行でも５種類のパターンがちゃんと出現する。
この二つのプロセスをシリアライザで保護すればP1、P2のどちらが先に走り始めるかによって結果は２通りしか発生しない。
make-serializerがこの先に出て来るので、Exerciseがあるが先に進む。
Complexity of using multiple shared resources
共有リソースが一つの場合にはシリアライザで比較的素直に実装出来るが、リソースが複数ある場合には非常に複雑になる。
例えば二つの口座の残高を入れ替える作業。一つのやり方はmake-accountでその口座用のシリアライザを外部に提供するメソッドも提供する事。このシリアライザを使って二つの口座を同時にロックして残高を交換するアプリケーションを作る事が出来る。
Implementing serializers
シリアライザの実装。
make-serializerはmake-mutexでmutexを作ってクロージャを返す。シリアライザは手続きpを引数に取るクロージャで、シリアライザを使って手続きpを呼び出そうとすると、手続きserialized-pが定義されて返される。serialized-pは可変引数を取る手続きで、mutexに'aquireを送ってmutexを取ってから、引数に手続きpを適用して、返り値をvalに保存、mutexに'releaseを送って解放してから保存しておいたvalを返す。
make-mutexはメッセージ'aquire、'releaseを受け取るクロージャを返す。cellはtrueあるいはfalseをcarに持つリスト。単に変数でない理由はtest-and-set!とclear!に変数の参照として渡して再代入させる必要がある為。
'aquireが送られるとcellをチェックして、trueである間無限に再帰する。falseが返って来て初めて返る。
'releaseが送られるとclear!を呼んでcellにfalseを設定する。
test-and-set!はcellのcarがtrueであればtrueを返す。即ちmutexは取られている事を意味する。一方、falseの時には単にfalseを返すのではなくcellをtrueにしてからfalseを返す。
test-and-set!とclear!をmake-mutexの内部関数にしてしまえばリストである必要は無い気がする。
(define (make-mutex) (let ((cell false)) (define (clear!) (set! cell false)) (define (test-and-set!) (if cell true (begin (set! cell true) false))) (define (the-mutex m) (cond ((eq? m 'acquire) (if (test-and-set!) (the-mutex 'acquire))) ((eq? m 'release) (clear!)))) the-mutex))
テストドライバーを少し書き換えて、３つのparallel-testを使い分けられる様にする。
(define (parallel-test) (let ((x 10)) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (+ x 1)))) x)) (define (parallel-test2) (let ((x 10)) (parallel-execute (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second))))) (lambda () (let ((first (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (+ first 1)))))) x)) (define (parallel-test3) (let ((x 10)) (parallel-execute (s (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second)))))) (s (lambda () (let ((first (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (+ first 1))))))) x)) (define (iterate-test test count result) (if (= count 0) result (let ((v (test))) (if (memq v result) (iterate-test test (- count 1) result) (iterate-test test (- count 1) (cons v result))))))
parallel-testは何も細工をしないバージョン。parallel-test2は間にdummy-sleepを入れて５種類全ての結果を出やすくしたもの。parallel-test3はparallel-test2と同じ状態のものをmutexを使って制御したバージョン。
実行結果
> (iterate-test parallel-test 100 '()) {121} > (iterate-test parallel-test 100 '()) {121} > (iterate-test parallel-test 1000 '()) {101 121} > (iterate-test parallel-test2 100 '()) {101 121 11 110 100} > (iterate-test parallel-test3 100 '()) {121 101} >
mutexできちんと制御出来ている。
Exercise 3.39
101、121はP1、P2間で割り込みは発生していない。
110は(* x x)の最初のxと二番目のxの値を取る間にxが10から11に変わるパターン。ここの部分はserializerで保護されているので、このパターンは起きない。
11はP2が11を計算して、P1が100を代入してからP2が11を上書きしてしまうパターン。P2が最初のxにアクセスしてからXに11を書き込むまでP1はブロックされるので、このパターンは起きない。
100はP1が100を計算して、P2が11を代入してからP1が100を上書きしてしまうパターン。P1が最初にxにアクセスしてからxに100を書き込む間にP2が11を代入する可能性はあるので、このパターンは起きる。
従って、101、121、100の可能性がある。
この状況を色んなタイミングでコンテキストスイッチが入る様に加工して実行する。
(define (parallel-test2) (let ((x 10)) (parallel-execute (begin (dummy-sleep) (lambda () (set! x (let ((v ((s (lambda () (* x x)))))) (dummy-sleep) v)))) (begin (dummy-sleep) (let ((v (s (lambda () (set! x (+ x 1)))))) (dummy-sleep) v))) x))
P1、P2が開始されるタイミングと(* x x)を計算してそれを代入する直前に割り込まれるタイミングを設ける。実行結果
> (iterate-test parallel-test2 100 '()) {101 121} > (iterate-test parallel-test2 100 '()) {121} > (iterate-test parallel-test2 100 '()) {100 121}
なかなかうまく３種類の結果は再現出来ないが、回数を重ねると３つ出現する事が確認出来る。
Exercise 3.40
シリアライズ無しで、２回参照して代入するプロセスP1と３回参照して代入するプロセスP2を並行させるとして、P1が３ステップ、P2が４ステップあるので、その組み合わせは通り。
| P1 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 reads 100 | P2 reads 100 | P2 writes 1000000 |
| P1 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 reads 100 | P2 reads 100 | P2 writes 100000 |
| P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P1 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 reads 100 | P2 writes 100000 |
| P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 writes 1000 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 writes 1000 | P1 writes 100 |
| P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 reads 1000 | P1 writes 10000 |
| P2 reads 10 | P1 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 reads 100 | P2 writes 100000 |
| P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 reads 1000 | P1 writes 10000 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 reads 10 | P1 writes 100 | P2 reads 100 | P2 writes 10000 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P1 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 reads 10 | P2 writes 1000 | P1 reads 1000 | P1 writes 10000 |
| P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 reads 10 | P1 writes 100 | P2 writes 1000 |
| P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P1 reads 10 | P2 writes 1000 | P1 writes 100 |
| P2 reads 10 | P2 reads 10 | P2 reads 10 | P1 reads 10 | P2 writes 1000 | P1 reads 1000 | P1 writes 10000 |
| P2 reads 10 | P2 reads 10 | P2 reads 10 | P2 writes 1000 | P1 reads 1000 | P1 reads 1000 | P1 writes 1000000 |
結果のxは100、1000、10000、100000、1000000の５通り。
シリアライザを使うとと計算するか
と計算するかのどちらか。何れにしても1000000。
実験。
シリアライザ無し
(define (parallel-test) (let ((x 10)) (parallel-execute (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second))))) (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x)) (third (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second third)))))) x))
結果
> (iterate-test parallel-test 100 '()) {1000000 10000 100 100000 1000} >
シリアライザあり
(define (parallel-test) (let ((x 10)) (parallel-execute (s (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second)))))) (s (lambda () (let ((first (begin (dummy-sleep) x)) (second (begin (dummy-sleep) x)) (third (begin (dummy-sleep) x))) (dummy-sleep) (set! x (begin (dummy-sleep) (* first second third))))))) x))
結果
> (iterate-test parallel-test 100 '()) {1000000} >
Exercise 3.41
Schemeのインストラクションのレベルで考えれば１回の変数へのアクセスなのでアトミックと考えて良い。
けど、例えば16ビットマイコンとかで32ビットの整数を使っていたり、float/doubleを扱っている様な場合にはCPUの一つのインストラクションではコピー出来ないのでインストラクションによっては保護しないと変な値を読んでしまう可能性は残る。
Exercise 3.42
シリアライザは手続きを渡された時には、新しい手続きserialized-pを作るだけでまだ呼び出さない。このserialized-pを引数に適用した時に始めてmutexを取りに行くので、dispatchが呼ばれた時にserialized-pを作って直ぐに呼んでも、予めserialized-pを作っておいてdispatchが呼ばれた時に呼んでも結果は同じ。
Exercise 3.43
各プロセスが逐次的に動けば、残高の交換は他のプロセスに干渉される事は無いので適切に交換される。
各アカウントへのアクセスはシリアライズ化されているが、exchangeは同時に動いてしまう場合
「$10引き出す」「$20入金する」と言う操作が正確に行われる限り、二つの口座間を移動する金額は正確に保たれるので、３つの口座の残高の合計は変化しない。ただ残高が正確に「交換」されている保証は無い。
「出金」「入金」がシリアライズされない場合、残高を決める為に参照した時の金額と、残高を設定する時の金額が一致する保証は無いので、残高を誤って設定してしまう可能性がある。
Exercise 3.44
Exchangeは少なくとの操作が完了した瞬間には二つの口座の残高が入れ替わっている必要がある一方、transferは正確にfrom-accountから引き出された金額がto-accountに入金されれば良く、from-accountから引き出す直前からto-accountに入金した直後までの間にこの二つの口座に入出金がある場合には、それぞれの残高は入れ替わる訳ではない。
なのでLouisは間違いで、Benのtransferは安全に動作する。
Exercise 3.45
serialized-exchangeはそれぞれのアカウントをロックしてからexchangeを呼ぶので、それぞれのアカウントのwithdraw、depositeを呼ばれた時には既にロックされていて、その呼び出しはブロックされてしまう。従ってデッドロックに陥る。
Exercise 3.46
test-and-set!はtrueが失敗を意味してリトライする事になっている。二つのプロセスにfalseを返してしまうとmutexとして機能しない事になる。
P1が(car cell)がfalseである事を知りtrueを設定するまでの間に、P2が(car cell)を取ってしまうと両方のプロセスにfalseを返してしまう。
Exchange 3.47
例示されているmake-mutexがtest-and-set!を使っているので混乱するが、
a.mutexを使ってセマフォのカウンタに同時にアクセスしない様に実装
b.test-and-set!でカウンタそのものをチェックして変更する様に実装
と解釈する。ここでのtest-and-set!はmutexではないので代入する値はtrue/falseではないが、成功・失敗を表す為にtrue/falseを返す。
テストコード
(define (tester name n) (if (> n 0) (begin (display name)(display ":")(display n)(newline) (sleep 1) (tester name (- n 1))) 'done)) (define s (make-serializer)) (parallel-execute (s (lambda () (tester "a" 5))) (s (lambda () (tester "b" 5))) (s (lambda () (tester "c" 5))) (s (lambda () (tester "d" 5))) (s (lambda () (tester "e" 5))) (s (lambda () (tester "f" 5))))
a.
(define (make-serializer) (let ((semaphore (make-semaphore 2))) (lambda (p) (define (serialized-p . args) (semaphore 'acquire) (let ((val (apply p args))) (semaphore 'release) val)) serialized-p))) (define (make-semaphore n) (let ((count 0) (mutex (make-mutex))) (define (the-semaphore m) (cond ((eq? m 'acquire) (begin (mutex 'aquire) (if (< count n) (begin (set! count (+ count 1)) (mutex 'release)) (begin (mutex 'release) (the-semaphore 'acquire)) ; retry ))) ((eq? m 'release) (begin (mutex 'aquire) (set! count (- count 1)) (mutex 'release))))) the-semaphore))
セマフォ二つでの、実行結果
e:b:5 5 b:4 e:4 b:3 e:3 b:2 e:2 b:1 e:1 d:5 c:5 d:4 c:4 d:3 c:3 d:2 c:2 d:1 c:1 a:5 f:5 f:a:4 4 a:f:3 3 f:a2 :2 f:a:1 1 '(#<void> #<void> #<void> #<void> #<void> #<void>) >
最初にeとb、次にdとc、最後にfとaと常に二つずつ実行された。
b.
(define (make-semaphore n) (let ((count 0)) (define (test-and-set!) (if (< count n) (begin (set! count (+ count 1)) false) true)) ; occumpied (define (the-semaphore m) (cond ((eq? m 'acquire) (if (test-and-set!) (the-semaphore 'acquire) ; retry 'done)) ((eq? m 'release) (set! count (- count 1))))) the-semaphore))
本当はcountを変更する所でmutexが必要だが、取り敢えずこれで動いたのでそのままとする。
セマフォ３つでの実行結果
e:b:5 f:5 5 b:4 f:4 e:4 b:3 f:3 e:3 b:2 f:2 e:2 b:1 f:1 e:1 c:5 d:5 a:5 d:a:4c:4 4 d:c:3a:3 3 c:d:a:2 2 2 d:1 c:a:1 1 '(#<void> #<void> #<void> #<void> #<void> #<void>) >
最初にeとbとf、次にcとdとaが実行されている。
Deadlock
二つのアカウントa1とa2の残高を、PeterとPaulが同時に入れ替えようとする。Peterがまずa1をロックして、a2をロックする前にPaulがa2をロックして、その後a1をロックしようとする。PeterとPaulのプロセスはどちらもそこから先には進めない。
Exercise 3.48
アカウントに番号を振り、手続きexchangeでは常に番号が若い方からロックするルールにするとPeterもPaulも（例えば）a1からロックしようとする。仮にPeterが先にa1をロックするとPaulはその手前で待たされる。a2はPaulにロックされる事は無くPeterは安全にa2をロック出来る。a2を別のプロセスがロックする可能性はあるがa1との間でexchangeしようとしてデッドロックに陥る可能性は無い。
make-accountの変更
(define make-account-and-serializer (let ((next-id 0)) (lambda (balance) (set! next-id (+ next-id 1)) (let ((id next-id)) (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) ((eq? m 'id) id) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)))))
動作確認
> (define a (make-account-and-serializer 10)) > (define b (make-account-and-serializer 20)) > (a 'id) 1 > (b 'id) 2 >
(define (serialized-exchange account1 account2) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) ((if (< (account1 'id) (account2 'id)) (serializer2 (serializer1 exchange)) (serializer1 (serializer2 exchange))) account1 account2)))
exchangeとしての動作確認
> (define a1 (make-account-and-serializer 12)) > (define a2 (make-account-and-serializer 34)) > (serialized-exchange a1 a2) 12 > (a1 'balance) 34 > (a2 'balance) 12 >
元々簡単にはデッドロックは起きないので、serializerにsleepを入れて簡単にデッドロックを起こす状況を作る。
(define (make-serializer) (let ((mutex (make-mutex))) (lambda (p) (define (serialized-p . args) (mutex 'acquire) (sleep 1) (let ((val (apply p args))) (mutex 'release) val)) serialized-p)))
この状態で元のserialized-exchangeを呼ぶ。
> (define a1 (make-account-and-serializer 12)) > (define a2 (make-account-and-serializer 34)) > (parallel-execute (lambda () (serialized-exchange a1 a2)) (lambda () (serialized-exchange a2 a1))) . . user break >
デッドロックに陥って戻って来ない。新しいserialized-exchangeを試す。
> (define a1 (make-account-and-serializer 12)) > (define a2 (make-account-and-serializer 34)) > (parallel-execute (lambda () (serialized-exchange a1 a2)) (lambda () (serialized-exchange a2 a1))) '(#<void> #<void>) > (a1 'balance) 12 > (a2 'balance) 34 >
２回exchangeが呼ばれるので残高は元の通り。
Exercise 3.49
Give a scenario where the deadlock-avoidance mechanism described above does not work.
はリソースにアクセスする順番を揃えても回避出来ない例を挙げよとも読めるが、ヒントを読むとこの方法が取れない例を挙げれば良さそう。
リソースの順番が付けられない例は「哲学者の食卓」の様に各リソース間の参照が循環してしまっているケース。
Concurrency, time, and communication
In contemporary multiprocessing systems, therefore, the serializer paradigm is being supplanted by new approaches to concurrency control.
mutexやsemaphoreの様なアクセスの順番を制御する様な方法は別のものに取って代わられつつある。
分散環境ではどの時点のどのデータが正しいのかを決めるのは簡単な話ではない。
It is intriguing that a similar connection between time and communication also arises in the Theory of Relativity
似た様な時間と通信の関係は相対性理論の中にも見られる。
