Scheme - 標準部品化力、オブジェクトおよび状態(並列性: 時が本質的(並列性の制御機構(複数の共有資源を使う複雑さ(直列化と条件))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: 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
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 3.43.

複数のプロセスが地区時的に走る場合は、最初の状態がそれぞれ10ドル、20ドル、30ドルのばあい、ある口座とある口座の残高を入れ替えると、20ドルと10ドルと30ドル、30ドルと20ドルと10ドル、10ドルと30ドルと20ドルのいずれかになり、この交換を任意の回数繰り返すことになるので、交換後の口座の残高はある順序で10ドル、20ドルおよび30ドルになる。

account1、account2、account3のそれぞれの口座残高を10ドル、20ドル、30ドルとする。

　　
1. account2(20ドル)とaccount1(10ドル)の口座残高の交換、account3(30ドル)とaccount2(20ドル)の口座残高の交換を同時に行う。
2. exchangeがaccount2とaccount1にアクセス、exchangeがaccount3とaccount2にアクセスする。
3. 最初のexchangeがaccount2とaccount1の口座残高の差(10ドル)を取得。この間もう一方のexchangeはaccount2の残高にアクセス出来ない。
4. もう一方のexchnangeがaccount3とaccount2の口座残高にアクセスし、口座残高の差(10ドル)を取得。
5. 最初のexchangeがaccount2から10ドル引き出し、account2の残高は10ドルになる。
6. もう一方のexchangeがaccount3から10ドル引き出し、account3の残高は20ドルになる。
7. もう一方のexchangeがaccount2に10ドル預け入れ、account2の残高が20ドルになる。
8. 最初のexchangeがaccount1にドル預け入れ、account1の残高は20ドルになる。
9. 最終結果、account1の残高は20ドル、account2の口座残高は20ドル、account3の口座残高は20ドルとなる。

よって、口座の残高はある順序で10ドル、20ドル、30ドルであるという条件が破られた。他方、残高の合計は60ドルと保存されている。

各口座の取引を直列しなかった場合。

account1、account2、account3のそれぞれの口座残高を10ドル、20ドル、30ドルとする。

1. account2(20ドル)とaccount1(10ドル)の口座残高の交換、account3(30ドル)とaccount2(20ドル)の口座残高の交換を同時に行う。
2. exchangeがaccount2とaccount1にアクセス、exchangeがaccount3とaccount2にアクセスする
3. 最初のexchangeがaccount2とaccount1の口座残高の差(10ドル)を取得、もう一方のexchangeがaccount3とaccount2の口座残高の差(10ドル)を取得。
4. もう一方のexchangeがaccount3から10ドル引き出し、account3の口座残高が20ドルとなる。
5. もう一方のexchangeがaccount2に10ドル預け入れるのと、最初のexchangeがaccount2から10ドル引き出すのが同時に発生し、それぞれaccount2の口座残高が20ドル、10ドルとなる。
6. 最初のexchangeがaccount1に10ドル預け入れ、account1の口座残高が20ドルになる。
7. 最終結果、account1の口座残高20ドル、account2の口座残高が10ドル、account3の口座残高が20ドルとなる。

よって、残高の合計は50ドルとなり、各講座の取引を直列かしなければ、残高の合計は保存されるという条件さえも破られる。