Scheme - 並列性の制御機構(複数の共有資源を使う複雑さ(口座残高の交換))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.4(並列性)、3.4.2(並列性の制御機構)、複数の共有資源を使う複雑さ、問題 3.43を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題3.43

逐次的に走った場合。

1回の並列交換後。

1. 1. a1とa2を交換。(a1:20, a2:10, a3:30)
   2. a1とa3を交換。(a1:30, a2:10, a3:20)
2. 1. a1とa3を交換。(a1:30, a2:20, a3:10)
   2. a1とa2を交換。(a1:20, a2:30, a3:10)

いずれの場合も口座の残高は10ドル、20ドル、30ドルの順になっている。

n回の並列交換で口座の残高が10ドル、20ドル、30ドルになっていると仮定してとき、n + 1回の交換の場合。

1. n回の交換でa1が10ドル、a2が10ドル、a3が30ドルの場合は1かの並列交換後から口座の残高はある順序で10ドル、20ドルおよび30ドルになっている。
2. n回の交換でa1が20ドル、a2が30ドル、a3が10ドルの場合。
   1. 1. a1とa2を交換。(a1:30, a2:20, a3:10)
      2. a1とa3を交換。(a1:10, a2:20, a3:30)
   2. 1. a1とa3を交換。(a1:10, a2:30, a3:20)
      2. a1とa2を交換。(a1:30, a2:10, a3:20)
3. n回の交換でa1が30ドル、a2が10ドル、a3が20ドルの場合。
   1. 1. a1とa2を交換。(a1:10, a2:30, a3:20)
      2. a1とa3を交換。(a1:20, a2:30, a3:10)
   2. 1. a1とa3を交換。(a1:20, a2:10, a3:30)
      2. a1とa2を交換。(a1:10, a2:20, a3:30)

よって任意の回数の並列交換後で、口座の残高はある順序で10ドル、20ドルおよび30ドルである。

本節の口座交換プログラムの最初の番で、条件が破られるタイミング図。

ということで、口座a1の残高は40ドル、口座a2の残高は10ドル、口座a3の残高は10ドルになっているので、順序が10ドル、20ドル、30ドルとなる条件は破られている。

他方、問題のexchangeプログラムを使っても、各口座の払い出し、預け入れのための手続きは口座ごとに直列化されていて、account1からPeterとPaulのそれぞれのexchangeのdifferenceが払い出され、Peterのdifferenceはaccount2に、Paulのdifferenceはaccount3に預け入れられるから残高の合計(10 + 20 + 30 = 60)は保存される。

各講座の取引を直列かしなかった場合のあるタイミング図。

よって、合計は20 + 10 + 10 = 40となり、直列化した場合の残高の合計は保存されるという条件さえも破られている。(上記の場合はPeterとPaulの払い出しの手続き(withdraw)がaccount1の残高(10)に並列にアクセスしてる。)