| (a,b,c,x,y,z) | (a,x,b,y,c,z) | (x,a,b,c,y,z) | (x,a,y,z,b,c) |
| (a,b,x,c,y,z) | (a,x,b,y,z,c) | (x,a,b,y,c,z) | (x,y,a,b,c,z) |
| (a,b,x,y,c,z) | (a,x,y,b,c,z) | (x,a,b,y,z,c) | (x,y,a,b,z,c) |
| (a,b,x,y,z,c) | (a,x,y,b,z,c) | (x,a,y,b,c,z) | (x,y,a,z,b,c) |
| (a,x,b,c,y,z) | (a,x,y,z,b,c) | (x,a,y,b,z,c) | (x,y,z,a,b,c) |
もっと実用的な並列システムの設計法は, プログラムの振舞いが正しいことが保証出来るように, 並列プロセスの混ざり合いを制約する一般的な機構を考え出すことである. この目的のために多くの機構が開発された. 本節では, その一つ, 直列変換器(serializer)を説明する.
共有変数へのアクセスの制御に直列化を使うことが出来る. 例えば共有変数を, その変数の前の値に基づいて更新しようと思えば, その変数の前の値へのアクセスと, その変数への新しい値の代入とを, 同一の手続きの中に置く. そうすれば, その変数に代入する他の手続きは, これらの手続きを同一の直列変換器で直列化することで, この手続きと並列的には走れないことが保証出来る. そしてこの変数の値はアクセスと対応する代入の間に変更されないことが保証出来る.
この使い方の例として
(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
(lambda () (set! x (+ x 1))))
を考えよう. これは並列プロセスを二つ---xをx掛けるxに設定するP1と, xを増加させるP2---を作り出す. 実行が完了した時, xはP1とP2の事象の混ざり合いに依存して五つの可能な値の一つになっている:| 101: | P1がxを100に設定し, 次にP2がxを101に増加する. | |
| 121: | P2がxを11に増加し, 次にP1がxをx掛けるxに設定する. | |
| 110: | P1が(* x x)の評価でxの値に二度アクセスする間にP2がxを10から11に変える. | |
| 11: | P2がxにアクセスし, P1がxを100に設定, P2がxを設定する. | |
| 100: | P1がxに(二回)アクセスし, P2がxを11に設定し, P1がxを設定する. | |
直列変換器(serializer)で作り出された直列化手続きを使い, 並列性を制約することが出来る. 直列変換器はmake- serializerにより構成する. その実装は下に示す. 直列変換器は引数として手続きをとり, 元々の手続きと同様に振舞う直列化した手続きを返す. 与えられた直列変換器への呼出しはすべて同一の集合の直列化手続きを返す.
そこで上の例とは対照的に
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
(s (lambda () (set! x (+ x 1)))))
ではxの可能な値として101と121の二つしか生じない. P1とP2は混ざり合うことは出来ないので, 他の可能性は排除される.
次は3.1.1節のmake-account手続きで, 預入れと払出しが直列化された版である:
(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 "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
この実装では, 二つのプロセスは, 一つの口座で並列的に払い出したり預け入れたりは出来ない. そして図3.29に示した, Paulが新しい値を計算するため残高にアクセスした時と, Paulが実際に残高に代入した時との間にPeterが残高を更新するというエラーの源は排除された. 他方, 各口座は自分の直列変換器を持ち, 異る口座の預入れと払出しは並列的に進めることが出来る.
(define x 10)
(define s (make-serializer))
(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))
(s (lambda () (set! x (+ x 1)))))
(define x 10)
(parallel-execute (lambda () (set! x (* x x)))
(lambda () (set! x (* x x x))))
の実行の結果となり得るxの可能性をすべて述べよ. 直列化した手続き:
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () (set! x (* x x))))
(s (lambda () (set! x (* x x x)))))
を使うと, これらの可能性のうち, どれが残るか.
(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)
((protected (lambda () balance)))) ; 直列化した.
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
賛成するか. Benの心配を示すシナリオはあるだろうか.
(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)))
(let ((protected-withdraw (protected withdraw))
(protected-deposit (protected deposit)))
(define (dispatch m)
(cond ((eq? m 'withdraw) protected-withdraw)
((eq? m 'deposit) protected-deposit)
((eq? m 'balance) balance)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch)))
これは安全な変更か. 特に二つのmake-accountの版で許される並列性の間には何か違いがあるだろうか.
起きそうな困難の一つを例示すれば, 二つの銀行口座の残高を交換したかったとしよう. それぞれの口座にアクセスし, 残高の差を計算し, 一方の口座から差を払い出し, それをもう一方の口座に預け入れる. これは次のように実装出来よう:41
(define (exchange account1 account2)
(let ((difference (- (account1 'balance)
(account2 'balance))))
((account1 'withdraw) difference)
((account2 'deposit) difference)))
この手続きは一つのプロセスだけが交換しようと試みる時はうまく働く. しかしPeterとPaulが口座a1, a2とa3にアクセス出来, Peterがa1とa2を交換し, Paulがa1とa3を並列的に交換するとしよう. 個々の口座について預入れと払出しが(本節で示したmake-accountのようにして)直列化された口座でも, exchangeは正しくない結果を生じ得る. 例えばPeterがa1とa2の残高の差を計算しようとするが, Peterが交換を完了する前にPaulがa1の残高を変更するかも知れない.42 正しい振舞いにはexchange手続きのために, 変換の全時間にわたって, その口座に並列的にアクセスするのを排除する配慮が必要である.
これを達成する一つの方法は, 両方の口座の直列変換器を使い, 全体のexchange手続きを直列化することである. それには口座の直列変換器にアクセスする方法を作る. 直列変換器を露出させ, 銀行口座オブジェクトの部品化力をわざと壊したことに注意しよう. make-accountの次の版は3.1.1節にあった元々の版とは, 直列変換器が残高変数を守るために用意してあることと, メッセージパッシングを経由して直列変化器が輸出されていること以外は同じである:
(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 "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
これを使って預入れと払出しが直列化出来る. しかし以前の直列化した口座と違い, 今度は次の例のように, 直列化を明示的に管理するのは銀行口座オブジェクトの各利用者の責任である:43
(define (deposit account amount)
(let ((s (account 'serializer))
(d (account 'deposit)))
((s d) amount)))
直列変換器をこのように輸出すると, 直列化した変換プログラムの実装に十分な自由度が得られる. 元々のexchange手続きを両口座の直列変換器で直列化する.
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
((serializer1 (serializer2 exchange))
account1
account2)))
(define (transfer from-account to-account amount) ((from-account 'withdraw) amount) ((to-account 'deposit) amount))Louis Reasonerは, ここに問題があり, 交換の問題を扱うのに必要だったような,より巧妙な方法を使う必要があると主張する. Louisは正しいか. そうでなければ, 移動の問題と交換の問題の間にはどういう本質的な違いがあるか. (from-accountの残高は, 少なくてもamountであると仮定せよ.)
(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) (balance-serializer withdraw))
((eq? m 'deposit) (balance-serializer deposit))
((eq? m 'balance) balance)
((eq? m 'serializer) balance-serializer)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
そして預入れは元々のmake-accountでやったように扱う:
(define (deposit account amount) ((account 'deposit) amount))Louisの考えで何が悪いか説明せよ. 特にserialized-exchangeを呼び出した時, 何が起きるか考えよ.
(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))
相互排除器は真か偽の値を保持する可変オブジェクトである. (ここでは一要素のリストを使う. これを セル(cell)と呼ぶことにする.) 値が偽の時, 相互排除器を獲得することが出来る. 値が真の時, 相互排除器は獲得出来ず, 相互排除器を獲得しようとするプロセスは待たされる.
相互排除器構成子make-mutexはまずセルの内容を偽に初期化する. 相互排除器を獲得するにはセルをテストする. 相互排除器が獲得出来るなら, セルの内容を真に設定して先へ進む. そうでなければ獲得しようと何度も試みながら, 相互排除器が獲得出来るようになるまで, ループして待つ.45 相互排除器を解放するには, セルの内容を偽に設定する.
(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))
(define (clear! cell)
(set-car! cell false))
test-and-set!はセルをテストし, テストの結果を返す. その上, テストが偽なら, test-and-set!は偽を返す前にセルの内容を真に設定する. この振舞いを次の手続きで表すことが出来る:
(define (test-and-set! cell)
(if (car cell)
true
(begin (set-car! cell true)
false)))
しかしtest-and-set!のこの実装は見たほどには十分ではない. ここには重要な微妙さがあり, それは並列性制御がシステムに登場する本質的な場所である: test-and-set!は 不可分に(atomically)実行しなければならない. つまりあるプロセスがセルをテストし, 偽であることを見つけたら, 他のプロセスがセルをテストする前にセルの内容は実際に真に設定されるということを保証しなければならない. この保証がないと図3.29で銀行口座が破綻したのと同じように相互排除器は破綻する. (問題3.46参照)
test-and-set!の実際の実装はシステムが並列プロセスを走らせる方法の細部に依存する. 例えば並列プロセスを逐次プロセスで, 各プロセスを短時間走らせては中断し,次のプロセスへ進むという
時間切片プロセス循環機構を使って実装しているかも知れない. こういう場合はtest-and-set!はテストと設定の間で時間切片が変らないようにすることでうまくいく.46
またマルチプロセスの計算機は, 不可分の演算をハードウェアで直接支援する命令を用意している:
47
問題 3.46
test-and-set!を演算を不可分にしようとは試みず, 本文に示したような通常の手続きを使って実装したとしよう. 図3.29のようなタイミング図を描き, 二つのプロセスが同時に相互排除器を獲得するのを許すと, 相互排除の実装が破綻することを示せ.
問題 3.47
(大きさnの)セマフォは相互排除器の一般化である. 相互排除器と同様に,
セマフォは獲得と解放の操作を提供するが, 最大n個のプロセスまで, それを並列的に獲得出来るという点で, より一般的である. そのセマフォを獲得しようとするそれ以上のプロセスは解放操作を待たなければならない. セマフォを
a. 相互排除器を使って
b. test-and-set!を使って
実装せよ.
この状態でデッドロックを回避する一つの方法は, 各口座に独自の識別番号をつけ, 少ない番号の口座を保護する手続きの方が, 先に入ろうとするよう,
serialized-exchangeを書き直すことである. この方法は, 交換問題ではうまく働くが,より巧妙なデッドロック回避技法を必要とする状況や, デッドロックが全く回避出来ない状況も存在する. (問題3.48と3.49参照)
48
問題 3.48
上に述べたデッドロック回避法(つまり口座に番号をつけ, プロセスはより小さい番号の方の口座を先に獲得しようとする.)が交換問題でデッドロックを回避する理由を詳しく説明せよ. この方法を採用するようserialized-exchangeを書き直せ. (make-accountも書き直し, 各口座は番号と共に作り出され, その番号は適切なメッセージを送ってアクセス出来るようにしなければならない.)
問題 3.49
上に述べたデッドロック回避機構が働かないようなシナリオを考えよ. (ヒント: 交換問題では, 各プロセスはどの口座にアクセスしなければならないか,
前もって知っている. プロセスが, 次にどの共有資源が必要になるか知る前にある共有資源にアクセスしなければならない状況を考えよ.)
test-and-set!のような機構は, プロセスが大域的共有フラグを任意の時刻に調べることを必要とする. これは問題であり, 最新の高速プロセッサに実装するのに効率的でない. そこではパイプラインやキャッシュメモリーのような最適化手法のため, メモリーの内容がすべての時点で首尾一貫した状態にあるとは限らない. そのため最近のマルチプロセッシングシステムでは, 直列変換器パラダイムは, 並列制御の新しい解決法に代られつつある.49
共有状態の問題点は巨大分散システムにもある. 例えば各支店が地域の銀行口座の値を維持しており, 周期的にこれを他の支店が維持している値と比べているところを想像しよう. こういうシステムでは「口座の残高」という値は, 同期直後以外には決められない. Peterがお金をPaulと共同で持っている口座に預け入れたら, いつの時点で口座の残高が変ったというべきか. ---地域の支店の残高が変った時か, 同期が済むまでだめなのか. Paulが別の支店から口座にアクセスしたら, 振舞いが「正しく」なるためにおくべき正当な制約は何か. 正しいことに関係するのはただPeterとPaulが個別に見た振舞いと, 同期の直後の口座の「状態」である. 「真」の口座残高や同期間の事象の順序に関する質問は不適切か無意味である.50
基本的現象は, 異るプロセスを同期させ, 共有状態を確定させ, 事象の順を強制するには, プロセス間の通信が必要だということである. 本質的には, 並列制御における時の概念は何でも通信に深く結びついている.51
時と通信の間の似たような関係が, (事象の同期をとるのに使える最速信号である)光の速度が時と空間に関連する基本的定数である
相対論にもあるのは面白い. 計算モデルで時と状態の扱いで出会った複雑性は,
実は物理的宇宙の基本的複雑性を反映している.
40
parallel-executeは標準Schemeの一部ではないが, MIT Schemeに実装することが出来る. われわれの実装では, 新しい並列プロセスも, 元々のSchemeのプロセスと並列的に走る. またわれわれの実装ではparallel-executeが返す値は新しく作り出されたプロセスを停止させるのに使える特別な制御オブジェクトである.
41
depositメッセージが負の値も受けつけるという事実を利用すれば, exchangeは単純化出来た. (これは銀行システムの重大な虫である.)
42
口座の残高が初めに10ドル,
20ドルおよび30ドルなら, 並列的な交換を繰り返した結果, 残高は相変らず,
ある順序で10ドル, 20ドルおよび30ドルであるべきだ. 個々の口座の預入れを直列化しただけでは, これを保証するのに不十分である. 問題3.43参照
43
問題3.45は預入れと払出しが最早口座によって自動的には直列化されない理由を検討する.
44
「mutex」という用語は,
相互排除(mutual exclusion)の短縮形である. 並列プロセスに資源を安全に共有させる機構を整える一般的問題を相互排除問題という. 相互排除器は
セマフォ (semaphore 腕木信号機)機構(問題3.47参照)の単純な変形である. セマフォは
アイントホーフェン工科大学で開発され, 同大学のオランダ語のイニシアルで名づけられた
"THE" マルチプログラミングシステムで紹介された
(Dijkstra 1968a). 獲得と解放の演算は元々は
Pと
Vという. それは鉄道システムに使う腕木信号機との関係で, オランダ語passeren (通過する)とvrijgeven(解放する)からとられた. Dijkstraの古典的解説(1968b)は並列制御の論点を明確に示した最初のもので, いろいろな並列システムを扱うセマフォの使い方を示した.
45
殆んどの時分割の操作システムでは, 相互排除器で停止させられた
プロセスは, 上のような
「ビジーウエイト」で時間を浪費はしない. そうではなく, 初めのプロセスが待つ間, システムは他のプロセスをスケジュールして走らせる. 停止させられたプロセスは, 相互排除器が獲得出来るようになると起こされる.
46
単一プロセッサ用の
MIT Schemeは時間切片モデルを使っていて, test-and-set!は次のように実装出来る:
(define (test-and-set! cell)
(without-interrupts
(lambda ()
(if (car cell)
true
(begin (set-car! cell true)
false)))))
without-interruptsは, その手続きの引数の実行中, 時間切片が変らないようにする.