問題3.38-3.49
代入を導入したことでプログラムに時の概念を与えることができるようになりましたが、並列システムでは少し問題があります。
ということで、問題3.38以降は並列システムでの時に対する正しいプログラムの振る舞いについてです。
3.38
Peter: (set! balance (+ balance 10)) ---->a1 Paul: (set! balance (- balance 20)) ---->a2 Mary: (set! balance (- balance (/ balance 2))) ---->a3
a.
balanceの初期値は100。
a1,a2,a3が同時に実行される時の可能な実行順序は3!通りで、f(x,y,z)をx,y,zの順に実行したときのbalanceを返す関数とすると、
f(a1,a2,a3)=45, f(a1,a3,a2)=35, f(a2,a1,a3)=45, f(a2,a3,a1)=50, f(a3,a1,a2)=40, f(a3,a2,a1)=40
なので、可能な値は35,40,45,50の4つ。
b.
図を書かなきゃいけないらしいので省略
3.39
とりあえず直列変換器とparallel-executeの機能を自分用にメモ。
- 直列変換器s
- (s procedure)は直列変換器sで直列化されたprocedureを返す。
- つまり、(parallel-execute (s p1) (s p2))ではp1とp2が混ざり合うことはなく、p1->p2かp2->p1のどちらかの順序の実行しかあり得なくなる。
- parallel-execute
- (parallel-execute p1 p2 ... pn)は、p1, p2, ..., pnが混ざりあって実行される時の考えられる全ての順序のプロセスを生成する。
- これはp1, p2, ..., pnのなかの実行手順も混ざり合うことを意味するので、n!通りではなくもっと多いということに注意。
parallel-executeはMIT Schemeでは実装可能らしいけど、どうやってやるのかちょっと気になる。
3.39を考え易くするために、
(define x 10) (define s (make-serializer)) (parallel-execute (lambda () (set! x ((s (lambda () (* x x)))))) (s (lambda () (set! x (+ x 1)))))
のうち、parallel-executeに渡された手続き中の操作を次のようにおく。
p1:xに2乗したものをset!する。 p2:xを2乗する。(ただしxはまだ変化していない) p2-x:p2がxにアクセスする。 p3:xをインクリメントする。 p3-x:p3がxにアクセスする。
この時、schemeの制約でp1=>p2,p1=>p2-x,p2=>p2-x,p3->p3-xの順序はないことと、直列変換器によりp2-x=>p2とp3-x=>p3は同時に起こらないことをふまえ、可能なプロセスの順序の全てとその時のxの値を以下に示す。なおa,b,c,d,eはabcdeの順に実行されることを表す。
p2-x,p2,p1,p3-x,p3 => x = 101 p3-x,p3,p2-x,p2,p1 => x = 121 p2-x,p2,p3-x,p3,p1 => x = 100
分かり易くとか言って余計分かりにくくなったような気もするけど、とりあえずxの可能な値は3つになります。
3.40
(define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (* x x x))))
3.40も面倒です。次も考え易くするため、各手順を次のようにおきます。
p1:xに2乗を代入。 p2:xに3乗を代入。 p1-x1:1回目のxへのアクセス。 p1-x2:2回目のxへのアクセス。 p2-x1,p2-x2,p2-x3も同様。
この時の手順の全ての組み合わせを列挙すると結構大変なので、手順の順序に関する以下の規則を使います。
- xへのアクセスは、set!の後でなければ順不同でも等価
- ただしp1-x2,p1-x1などはあり得ないことに注意
- 代入pi(i=1,2)は、必ずpiのxへのアクセスが全て終わった後に実行される
すると、p1とp2の順序、及び実行タイミングによって場合分けすることができます。
p1-x1,p1-x2,p1,p2-x1,p2-x2,p2-x3,p2 => x = 1000000 a1 p1-x1,p1-x2,p2-x1,p1,p2-x2,p2-x3,p2 => x = 100000 a2 p1-x1,p1-x2,p2-x1,p2-x2,p1,p2-x3,p2 => x = 10000 a3 p1-x1,p1-x2,p2-x1,p2-x2,p2-x3,p1,p2 => x = 1000 a4 p2-x1,p2-x2,p2-x3,p2,p1-x1,p1-x2,p1 => x = 1000000 a5 p2-x1,p2-x2,p2-x3,p1-x1,p2,p1-x2,p1 => x = 10000 a6 p2-x1,p2-x2,p2-x3,p1-x1,p1-x2,p2,p1 => x = 1000 a7
手順の最後には、規則3から必ず代入のどちらか(p1 or p2)がきます。規則1から、初めの代入より前(つまり左側)は規則2の範囲内で順不同です。また、代入と代入の間は規則2により動かすことができません。
よって上記で全てのxの可能な値を出せたことになります。
が、心配なので本当に全てなのか確かめることにします。
8つの空欄に規則を守りつつ各手順に対応した文字を入れる組み合わせの数として考えてみます。
まず、一番後ろはp1 or p2なので場合分けします。
- 一番後ろがp1のとき
- 前6マスのうち、p2-x1,p2-x2,p2-x3,p2と並んでいる状態で、p1-x1,p1-x2をこの順に入れる問題なので、数え上げて5+4+3+2+1=15通り。
- 一番後ろがp2のとき
- 前6マスのうち、p1-x1,p1-x2,p1と並んでいる状態で、p2-x1,p2-x2,p2-x3をこの順に入れる問題なので、数え上げて(4+3+2+1)+(3+2+1)+(2+1)+(1)=10+6+3+1=20通り。
よって、全部で15+20=35通りあるはず。…(*)
一方、上記a1, ..., a7の各々の等価な並べ方の数を調べると、
- a1 : 1
- a2 : 3
- a3 : 3+2+1=6
- a4 : 4+3+2+1=10
- a5 : 1
- a6 : 4
- a7 : 4+3+2+1=10
なので、全部で1+3+6+10+1+4+10=35通りとなり、(*)と一致します。ということで、ちゃんと全部調べているようです。xの可能な値は1000,10000,100000,1000000ということになります。
parallel-executeの作り方も、変数へのアクセスと変数の代入を列として表現すると案外できたりするような気がします。ちょっと考えてみたら大変そうだったのでやりません。
次に、
(define s (make-serializer)) (parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (* x x x)))))
での可能な値を考えます。これは、a1からa7のうち、p1とp2の代入、アクセスの手順が混ざっていないものを選べばよいです。
そのようなものはa1とa5のみなので、xの可能な値は1000000のみであると分かります。
3.41
balanceは値の参照をするだけなので、直列化は必要ないんじゃないかな。
3.42
Ben版のmake-accountとそれまでのmake-accountの違いは、直列変換器の生成の時点。
それまでのmake-accountは、withdrawやdepositが呼び出される度に、直列変換器で新しく直列化手続きを生成する。
Ben版のmake-accountはdispatchの外で局所変数として直列化手続きを既に作るので、withdrawやdepositが呼び出されても、同じ直列化手続き(ここでの同じとは、使いまわしという意味)を使う。
しかし、呼び出しの度に新しく直列化手続きを生成しても、結局のところ毎回同じ(ここでの同じは機能的な意味)ものを生成しているだけなので、Ben版のようにあらかじめ作っておいて、それを何度も使う方法でも機能は変わらない。つまり安全な変更となる。
この二つの間の違いは、Ben版の方が直列化手続きを作る回数が少ない(一回でよい)分コストが低い(といっても微々たるもののような気がする)という点のみで、並列性については違いはない。
(SICPを勉強するのに、同じ本を使いまわすのと、次々に新しいSICPを買ってきて勉強するのとで、勉強に違いはあるか、みたいな問いです。お金的には大変違いますが。)
3.43
図は描けないので言葉で解答します。
ある順序というのは、口座a1=10,a2=20,a3=30がある場合のa1,a2,a3の全ての並びのうちの一つということかな。
プロセスが逐次的に走るなら、aiとaj(i≠j)は交換が完了するまで他のどのプロセスからも変更されないので、aiのbalanceがajに、ajのbalanceがaiになる。これを任意回数繰り返しても、全ての口座のbalanceは初期の残高のいずれかになっているので、a1,a2,a3をある順序で並べればそれは必ず10,20,30ドルとなるはず。
exchangeを並列実行する場合、例えばa1,a2とa1,a3が並列実行される時において前者のプロセスをP1、後者をP2とすると、P1でa1のbalanceにアクセスした後、P2がa1,a3のexchangeを実行すると、a1=30,a3=10となる。しかしP1はa1が10の時にアクセスしたので、differenceは-10であり、exchangeによってa1=40,a2=10となる。するとa1=40,a2=10,a3=10で"交換"した後の値としてはおかしい。
一方、各accountは直列変換器によってその払い出しと振り込みを直列化しているので、同時実行はない。したがって、exchangeの手続きでは、exchangeに渡されるaccount1, account2について、exchange終了時にaccount1 => account1 - difference, account2 => account2 + differenceとなっている。両辺を足すと、account1 + account2 => account1 + account2で、残高の和は各accountが直列化されていればexchange完了時に変化しないことが分かる。
各accountが直列化されていないならば、a1=10,a2=20,a3=30というaccountについて、a1とa2及びa1とa3が交換される場面において前者のプロセスをP1、後者をP2とすると、P1がa1とa2にアクセスしてa1をwithdrawしてset!する直前に、P2がa1(=10)とa3にアクセスしa1をwithdraw(a1=30)し、さらにa3をdeposit(a3=10)して、そのあとP1がa1に値をset!(a1=20)、a2をdeposit(a2=10)したとする。
このとき、a1=20,a2=10,a3=10となり、残高の合計も保持されなくなる。
3.44
Louisは正しくない。
口座a1,a2,a3がそれぞれ100ドル持っていたと仮定する。
(define (transfer from-account to-account amount) ((from-account 'withdraw) amount) ((to-account 'deposit) amount))
transferによりa1からa2に50ドル(P1)、a2からa3に30ドル(P2)の移動が並列に行われる場合を考える。
各accountは直列化されており、可能なプロセス順序のパターンは
- P1がa1をwithdrawした後、P2がwithdraw、P1がa2にdepositし、P2がa3にdeposit
- P1がa1をwithdrawした後、P2がtransferして、P1がdeposit
- P1がtransferして、その後P2がtransfer
- P2がa2をwithdrawした後、P1がwithdraw、P2がa3にdepositし、P1がa2にdeposit
- P2がa2をwithdrawした後、P1がtransferして、P2がdeposit
- P2がtransferして、その後P1がtransfer
これらの全てについて、最終的にa1=50,a2=120,a3=130が成り立つ。
交換では、exchange手続き中に局所変数differenceを計算する必要があったので、exchangeを直列化せずに並列実行するとdifferenceが様々な値をとる可能性があるため、問題だった。
移動では、transfer手続き中で直列化された手続きwithdrawとdepositしか使わないので、並列計算での一意性を保つことができる。
3.45
Louisって男だったんだ…。
まあそれはいいとして、serialized-exchangeを呼び出すと、exchange中の((account1 'withdraw) difference)や((account2 'deposit) difference)で直列化した手続きを作用させてるけど、serialized-exchangeで((serializer1 (serializer2 exchange)) account1 account2)ってやっちゃってるから、serialized-exchangeを呼び出すと中の((account! 'withdraw) difference)や((account2 'deposit) difference)を作用させることができなくて止まっちゃうと思います。
ということでこれは大変まずいです。
3.46
図は描かずに文章で書く。
何かのプロセスP1とP2がほぼ同時にtest-and-set!にアクセスし、どちらかのプロセスがcellのcarをtrueにset-car!する前に両方共ifのalternativeに到達してしまったとする。
するとP1とP2は本来逐次実行されなければならないのに、並列実行されてしまうので、3.43などのような問題が生じてしまう。
3.47
a.
(define (make-semaphore-a n) (let ((n n) (mutex (make-mutex))) (define (semaphore m) (mutex 'acquire) (cond ((eq? m 'acquire) (if (= n 0) (begin (mutex 'release) (semaphore 'acquire)) (begin (set! n (- n 1)) (mutex 'release)))) ((eq? m 'release) (set! n (+ n 1)) (mutex 'release)))) semaphore))
b.
(define (make-semaphore-b n) (let ((n n) (cell (list false))) (define (semaphore m) (cond ((eq? m 'acquire) (if (or (= n 0) (test-and-set! cell)) (semaphore 'acquire)) (begin (set! n (- n 1)) (clear! cell))) ((eq? m 'release) (set! n (+ n 1)) (clear! cell)))) semaphore))
こんな感じだろうか。動かせないからあまり自信がない。
3.48
識別番号をつけて数字の小さい方から優先して保護するようにすることは、機能的に見て直列化と等しい。
今回のデッドロックが生じた原因は、直列化を行う手続き自身が並列的に処理された(a1とa2に同時にアクセスした)ためおこったので、直列的に処理することでデッドロックを回避できる。
(define (make-account balance number) (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 'number) number) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)) (define (serialized-exchange account1 account2) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) (cond ((<= (account1 'number) (account2 'number)) ((serializer1 (serializer2 exchange)) account1 account2)) ((> (account1 'number) (account2 'number)) ((serializer2 (serializer1 exchange)) account1 account2)))))
この辺あんまりおもしろくないです。
3.49
めんどい。省略。
今日はここまで。動かせないプログラミングと説明ばっかりであまり楽しくなかったです。
明日からストリームに入ります。まだ読んでない部分が少しあるのでペースが若干落ちるかもしれませんが、まあがんばります。
