SICP 読書ノート#34 - 3.4 並列性：時が本質的 (pp.175-187)
前節までに局所状態を持つオブジェクトを取り入れたけれど、局所状態とは即ち「時」を意識することになる。ここでは異なるタイミングで複数のプロセスから共有オブジェクトの状態を参照したり変更したりする場合に、どういった課題があるかといったことを検証して行く。
並列プログラムの正しい振る舞い
問題 3.38
(a)
残高(balance)の遷移は次の6パターン。
- パターン1 (★a)
100 -> (Peter) -> 110 -> (Paul) -> 90 -> (Mary) -> 45- パターン2
100 -> (Peter) -> 110 -> (Mary) -> 55 -> (Paul) -> 35- パターン3 (★a)
100 -> (Paul) -> 80 -> (Peter) -> 90 -> (Mary) -> 45- パターン4
100 -> (Paul) -> 80 -> (Mary) -> 40 -> (Peter) -> 50- パターン5 (★b)
100 -> (Mary) -> 50 -> (Peter) -> 60 -> (Paul) -> 40- パターン6 (★b)
100 -> (Mary) -> 50 -> (Paul) -> 30 -> (Peter) -> 40
★a,bのようにPaulとPeterが続く場合は最終の残高が同じになる。これはPaulとPeterは残高に対して単純に差し引きしているため。
一方でMaryは前の残高を半分に減らす、つまり前の状態に依存して次の状態が決まるため、どこに来るかで最終の状態が変わってくる。
(b)
(a)当初の残高100に対してPaul、Peter、Maryの3者が同時に、または2者だけが同時にアクセスする場合のパターンが起こり得る。
すなわち最終残高が(a)の６パターンの遷移の途中の値でとどまってしまうことが想定されるので、起こり得る値としては110、80、50、90、55、40、60、30、45、35、45の11通り。
共有状態へのアクセスの直列化
前節の「2つ以上のプロセスが全く同時にアクセス」といったことを避けるために、処理の直列化(シリアライズ)を検討する。
問題 3.39
例で示されている並列処理を分解すると、
- プロセスP1
- (1) 引数1のxをread
- (2) 引数2のxをread
- (3) それらを乗算
(4) 結果をxへ代入
プロセスP2
- (a) 引数1のxをread
- (b) それに1を加算
- (c) 結果をxへ代入
となる。これらが並列で実行されるパターンは、
- パターンA
(1)->(2)->(3)->(4)->(a)->(b)->(c)：x=101- パターンB
(a)->(b)->(c)->(1)->(2)->(3)->(4)：x=121- パターンC：
(1)->(a)->(b)->(c)->(2)->(3)->(4)：x=110- パターンD：
(a)->(1)->(2)->(3)->(4)->(b)->(c)：x=11- パターンE：
(1)->(2)->(3)->(a)->(b)->(c)->(4)：x=100
となる。シリアライザを適用したコードを見ると
(define x 10) (define s (make-serializer)) (parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (* x x x)))))
上記の処理(1)->(2)->(3)および(a)->(b)->(c)が直列化されるので、起こり得るパターンは上記のA、B、Eとなる。
問題 3.40
問題3.39と同じ要領で考える。
プロセスP1
- (1) 引数1のxをread
- (2) 引数2のxをread
- (3) これらを乗算
- (4) 結果をxへ代入
プロセスP2
- (v) 引数1のxをread
- (w) 引数2のxをread
- (x) 引数3のxをread
- (y) これらを乗算
- (z) 結果をxへ代入
手続きがシリアライズされた場合は、
- パターンA
(1)->(2)->(3)->(4)->(v)->(w)->(x)->(y)->(z)：10^6- パターンB
(v)->(w)->(x)->(y)->(z)->(1)->(2)->(3)->(4)：10^9
の2通りが起こり得る。
問題 3.41
Benの心配には及ばない。(dispatch 'balance)はbalanceの値を取り出すだけなので直列化は不要。
でも確かに現場でついついこういうコードを書いてしまいがち…
問題 3.42
安全な変更ではあるが、2つの版のmake-accountの並行性に違いなないと思う。コードを動かせないのでわからないけど。
複数の共有資源を使う複雑さ
問題 3.43
例えば口座A,B,Cの残高が10,20,30として、AとBをexchangeし、BとCをexchangeした場合のタイミングチャートは以下のようになる。
(w) : withdraw (d) : deposit A 10-------->10-->(d)-->20-------->20-------->20 B 20-->(w)-->10-------->10-------->10-->(d)-->30 C 30-------->30-------->30-->(w)-->10-------->10
直列化を行わない場合は上記の処理順序が崩れる可能性でてくるので、その時は破綻してしまう。
問題 3.44
transfer手続きの場合、予め決められた口座からの差し引き額が引数amountで与えられるので、問題3.43のような順序崩れによる問題は発生しない。
問題 3.45
serialized-exchangeがそのままなら、直列処理の中でさらに直列処理を行うことになりデッドロックする。
直列変換器の実装
問題 3.46
プロセスA --> #f ---------> #t --------------> #t ---------> #f
acquire (処理の実行) release
プロセスB --> #f ---------> #t --------------> #t ---------> #f
acquire (処理の実行) release
において、mutexの獲得がatomicに実行される保証がなければ、2つのプロセスが同時にmutexにアクセスするとタイミングによってはどちらもそれを獲得できてしまい、処理が同時に走って破綻する。
問題 3.47
(a)のmutex版。動作確認はしてないけどこんな感じかな。
(define (mutex-semaphore counter) (let (mutex (make-mutex)) (define (acquire) (mutex 'acquire) (if (> counter 0) (begin (set! counter (- counter 1)) (mutex 'release)) (begin (mutex 'release) (acquire)))) (define (release) (mutex 'acquire) (set! counter (+ counter 1)) (mutex 'release)) (define (dispatch m) (cond ((eq? m 'acquire) acquire) ((eq? m 'release) release) (else (error "unknown requeset -- make-semaphore" m)))) dispatch))
(b)のtest-and-set!版も同様と思うので略。
デッドロック
問題 3.48
2つのプロセスが以下の順でmutexを獲得するケースにおいて、
プロセスA ---> m1 #t -----> m1 #t --->
m2 #f m2 #t
★
プロセスB ---> m1 #f -----> m1 #t --->
m2 #t m2 #t
★のタイミング（プロセスAがm1を獲得、プロセスBがm2を獲得している）で、相互にコンテキストスイッチが発生すると、
- プロセスAがm1を獲得している間に、プロセスBもm1を
- プロセスBがm2を獲得している間に、プロセスAもm2を
獲得しに行くためデッドロックする。
口座番号方式ではプロセスがmutexの獲得順序が (m1) ---> (m2) か (m2) ---> (m1) のどちらかになるため、★のタイミングでコンテキストスイッチが発生してもデッドロックしない。
問題 3.49
(serializer1 (serializer2 proc))
という処理procの中で同様の直列処理があると、mutexの入れ子になってデッドロックする。
複数の共有資源を扱う場合、mutexでは本質的にデッドロックは完全に防げないということだと思う。難しい問題ですね。
次は「§3.5 ストリーム」から。
