1,2 Summary.md

1 Introduction

この本のイントロダクション。

• CPU はクロック数を上げるのではなく、マルチプロセッサにすることで高速化する傾向
  • マルチプロセッサに適したプログラミングをしないとソフトウェアが高速化されない時代
    • 複数のプロセッサは共有メモリでやりとりする
  • マルチプロセッサのプログラミングは難しい
    • 最近のコンピュータシステムは非同期なので、予測できない中断や遅延が発生しうる

• この本では、マルチプロセッサにおける計算の原理と実践を扱う
  • パート1の原理では、主に計算可能性の観点から
  • パート2で実践では、主にパフォーマンスの観点から

言語は Java のスタイルを使う。

1.1 Shared Objects and Synchronization

• 10^10 までの素数判定を10プロセッサで計算する題材を使って、並列化がそう単純でないことを説明。
  • Figure 1.1: 10 スレッドで 10^9 個ずつ担当
    • スレッド間で計算する量に偏りが出る
  • Figure 1.2: カウンタを共有
    • 簡単なカウンタの実装はダメ（Figure 1.3）
    • 共有メモリの同期を取る必要がある（read-modify-write命令や、相互排除）

1.2 A Fable

アリスとボブの話をもとに、相互排除の問題を紹介。

• 問題設定（Mutual Exclusion）

  • アリスとボブはご近所さんで庭を共有している
  • アリスが猫、ボブが犬を飼っている
  • 犬と猫を両方庭に放してはいけない
  • 庭は広いので庭を見て状況を確認することはできない

• どうやって解決するか

  • 相手の家に行ったり、電話ではコミュニケーションそのものが成立しない場合があるのでダメ
  • 缶プロトコル（Figure 1.4）は、数の制限があるのでダメ
  • フラグプロトコルでは可能
    • ペットが両方とも庭にいると仮定して背理法で証明

1.2.1 Properties of Mutual Exclusion

• Mutual Exclusion の性質

  • mutual-exclusion
    • 同時に実行されない
  • deadlock-free
    • 同時に実行しようとしている時に少なくともどれか一つが実行できる
  • starvation-free
    • 同時に実行しようとした、一部の処理が長期間実行されないことが起きない
  • waiting
    • 調整中に応答が返ってこなくなり身動きがとれない

• フラグプロトコル

  • mutual-exclusion である
  • deadlock-free である
  • starvation-freedom ではない（衝突したらアリスが優先されるため）
  • waiting は発生する

1.2.2 The Moral

• コミュニケーションには 2 種類ある

  • Transient communication （電話のように同時に参加）
  • Persistent communication （メールのように時間がずれてもよい）

• 相互排他を解決するには

  • Transient communication は通信が確立できな場合があるのでダメ（電話）
  • Interrupt でもダメ（缶プロトコル）
  • 自分で書けて、相手が読める 1 bit 変数 2 個あれば可能（フラグプロトコル）

1.3 The Producer–Consumer Problem

さっきの寓話の続き

• アリスとボブが結婚し離婚

• アリスが両方のペットを飼う

• ボブがペットに餌を提供する

• 問題設定の変更（Producer-Consumer Problem）

  • ペットは同時にいても大丈夫になった
  • ボブとペットは同時に庭にいてはいけない
  • ボブが餌を庭に置く
  • 餌が無い時にアリスはペットを放さない
  • 餌があるうちはボブは餌を置かない

• Producer-Consumer Problem の性質

  • Mutual Exclusion
  • Starvation-freedom
  • Producer-Consumer

Deadlock-freedom を満たさないので（順番に実行すればいい）、1.2 の問題には使えない。

• どうやって解決するか
  • 缶プロトコル
    • Mutual Exclusion できている（一つ一つの状態を検証すれば良い）
    • Starvation-freedom できている（餌を追加できない状態を仮定して、背理法で証明）
    • Producer-Consumer できている
    • Waiting あり

1.4 The Readers–Writers Problem

寓話の続き

• ボブとアリスは billboard でペットのメッセージのやり取りをするようになった

• Billboard の設定

  • ボブは 1 文字ずつしか変更できない
  • アリスは 1 文字ずつしか読めない

• アリスが読んでいる途中で、ボブがメッセージを変えると、メッセージが混ざる

  • 缶プロトコルで Mutual Exclusion すればいい
  • Waiting は起こる

Readers–Writers Problem の Waiting なしの解決法は後で紹介。

1.5 The Harsh Realities of Parallelization

• Amdahl’s Law
  • プロセッサの数が N 倍にしても、処理速度は N 倍にならない
  • Speedup = 1 / ((1 - p) + p/n))
    • n = CPU の数
    • p = 全体の中で並行で実行できる割合

例1 小部屋 4、大部屋 1 を 5 人でペイント（大部屋は 2 倍の大きさ）

• S = 1 / (1/6 + 1/6) = 3倍 （理想は 5 倍）

例2 小部屋 9、大部屋 1 を 10 人でペイント

• S = 1 / (1/11 + 1/11) = 5.5倍 （理想は 10 倍）

• 10% の部分が並列化できないだけで、スピードアップは半分くらいに制限される

  • 直列にしか処理できない部分が少しだけでも問題

1.6 Parallel Programming

• アプリケーションの並列化
  • 簡単に並列化できる部分も多い
  • 残りの難しい部分の並列化も無視できない（Amdahl’s Law）
  • そのための手法や構造を学ぶのがこの本のゴール

2 Mutual Exclusion

• 相互排除は、マルチプロセッサプログラミングで最も普及している調整手段
• この章は、共有メモリを用いた古典的な相互排除アルゴリズムを取り扱う
  • 現実では使われていない。しかし、
    • 相互排除アルゴリズムや正確性問題、同期について考える際の入り口としては理想的
  • 不可能性の証明も導入する
    • 共有メモリを用いた相互排除では何が実現できないか、を教えてくれる

2.1 Time

• スレッド群は同じ(外部からは独立した独自の)時間を共有する

• スレッドは__ステートマシン__であり、そのステート(状態)の遷移は__イベント__と呼ばれる

  • イベントは瞬間的
  • 同じ瞬間には複数のイベントが同時に発生することはない

• 定義

  • スレッド A は、イベント列 a₀,a₁,... を生成する
  • イベント a_i の j 番目の出現は a_i^j
  • イベント b に先行するイベント a は a → b (total order)
  • a₀ → a₁ の時
    • 区間 I_A = (a₀, a₁) は a₀ から a₁ までの期間
    • 区間 I_B に先行する区間 I_A は (a₁ → b₀) I_A → I_B (partial order)
    • 区間 I_A の j 番目の実行は I_A^j

2.2 Critical Sections

1章に出て来た Counter を、Critical Sections (Lock) を使って実装 (Figure 2.3)

• Critical Sections

  • 同時に 1 スレッドしか実行できないブロック
  • CS_A^j はスレッド A による、j 回目の実行

• 良い Lock が満たすべき性質

  • Mutual Exclusion
    • safety property: 正しさを保証
  • Freedom from Deadlock
    • liveness property: フリーズしないことを保証
  • Freedom from Starvation
    • starvation freedom なら deadlock freedom

2.3 2-Thread Solutions

2.3.1 The LockOne Class

• LockOne アルゴリズム（Figure 2.4）

  • 相手が unlock するまで待つ
  • 同時に flag を true にするとデッドロックだが、並列でなければ大丈夫

• 表記

  • write__A(x = v)_: A がフィールド x に 値 v を書く
  • read__A(v == x)_: A がフィールド x の 値 v を読む

Lemma 2.3.1. LockOne は mutual exclusion

背理法で証明。両方が CS に入っていると仮定して、
flag[A] に true を write しているのに false が read されることを導く。

2.3.2 The LockTwo Class

• LockTwo アルゴリズム (Figure 2.5)
  • 別のスレッドが来るまで待つ
  • 1 スレッドしかないとデッドロックするが、並列なら大丈夫

Lemma 2.3.2. LockTwo は mutual exclusion

背理法で証明。両方が CS に入っていると仮定して、
write が連続で起きるため、片方しか read できないことを導く

LockOne と LockTwo はデッドロックの条件が正反対。

2.3.3 The Peterson Lock

• Peterson Lock アルゴリズム（Figure 2.6）
  • LockOne + LockTwo
  • starvation-free （なので deadlock-free）

Lemma 2.3.3. Peterson lock は mutual exclusion

背理法で証明。両方が CS に入っていると仮定して、
flag[B] に true を write しているのに false が read されることを導く。

Lemma 2.3.4. Peterson lock は starvation-free

背理法で証明。A が lock で止まっていると仮定して、
B が再度 lock に来た場合と、lock の中にいた場合の矛盾を示す。

Corollary 2.3.1. Peterson lock は deadlock-free

2.4 The Filter Lock

• N スレッド対応の相互排除プロトコル

  • Filter lock
    • Peterson lock の発展
    • もちろん starvation-free
  • Bakery lock
    • 最も簡単で有名

• Filter Lock (Figure 2.7)

  • n - 1 レベルの階層作る
    • レベル n - 1 が CS
    • 少なくとも 1 スレッドは階層 l に入れる
    • 同時に入ろうとすると、1 スレッドはブロックされる
    • 自分よりレベルが大きいスレッドがいたら進めない

Lemma 2.4.1. レベル j (0 <= j <= n-1) には多くても n - j スレッドしかいない

帰納法で示す。レベル j - 1 の時に成立する場合、レベル j で成立しない
（レベル j - 1 のスレッドが全部レベル j に行く）と仮定して背理法で示す。
最後にレベル j に到着したスレッド A が進めないことを導けばいい。

Corollary 2.4.1. Filter lock は mutual exclusion

Lemma 2.4.2. Filter lock は starvation-free
帰納法で示す。レベル j + 1 以上で成立する場合に、レベル j で成立しない
（レベル j のスレッド A が止まり続ける）と仮定して背理法で示す。
スレッド A がいるので、レベル j は増えないし、j より上のスレッドはいなくなるので A も上がってしまう

Corollary 2.4.2. Filter lock は deadlock-free

2.5 Fairness

• starvation-freedom は CS に入る時間や順番を保証しない

  • lock を呼んだ順番に入るのが理想

• Lock を 2 つにわける

  • Doorway (D_A): 有限ステップで終わる処理
  • Waiting (W_A): ステップ数が決まっていない処理

• bounded wait-free progress property

  • Doorway が常に一定の処理ステップで終わる

• Definition 2.5.1.

  • D_A^{j → D_Bk} の時 CS_A^{j → CS_Bk} であれば first-come-first-served

2.6 Lamport’s Bakery Algorithm

• Bakery lock (Figure 2.9)

  • first-come-first-served
    • doorway で番号を受け取り、自分より先の人がいなくなるまで待つ
  • flag[A] は A が CS に入ろうとしているかどうか
  • label[A] は A の順番

• 同時に入ると label が一緒になるので lexicographical order で順番を決める

  • (label[i], i) << (label[j], j)
  • label[i] < label[j] or (label[i] = label[j] and i < j)

Lemma 2.6.1. Bakery lock は deadlock-free

順序づけられているので明らか

Lemma 2.6.2. Bakery lock は first-come-first-served

label の番号で順序づけられているので明らか

deadlock-free で first-come-first-served なら starvation-free。

Lemma 2.6.3. Bakery algorithm は mutual exclusion

背理法で示す。同時に CS に入っていると仮定し、label の矛盾を導く。

2.7 Bounded Timestamps

• Bakery lock の label は上限がないのでオーバーフローの問題あり。

  • label は実質 timestamp
  • 他のスレッドの timestamp を読んで（scan）して
  • 最新の timestamp を割り当てれば（label）できればいい

• Wait-free で Concurrent な Timestamping system は構築可能だが大変

  • シーケンシャルな Timestamping system にフォーカ
    • atomic な操作（mutual exclusion）が必要
  • 先行グラフ（precedence graph）で順序を表現
  • 他の全てのスレッドと直接比較すればいいので、推移的である必要はない

• Precedence graph Tⁿ は n-thread bounded であるシーケンシャルな Timestamping system

• Figure 2.12 に 3 スレッドまでの例がある

2.8 Lower Bounds on the Number of Locations

• Bakery Lock は簡潔、エレガント、公平だけど、実用的ではないのはなぜ？

  • スレッド数に比例した n 個のメモリ領域を読み書きするオーバーヘッドが欠点
  • deadlock-free ロックアルゴリズムであることの制限事項なので回避できない

• メモリの特性として

  • read か write を単独でしか実行できない
  • あるスレッドにより書き込みされた情報が、他のスレッドに参照されることなく上書きされる可能性がある

• メモリの状態

  • object's state
    • そのオブジェクトのフィールドの状態
  • thread's local state
    • プログラムカウンタとローカル変数の状態
  • global state (system state)
    • all object's states + all thread's local states

Definition 2.8.1.

• Lock オブジェクトの状態 s が inconsistent とは、いくつかのスレッドが CS に入っているけど、 ロックの状態は CS に誰もいない、入ろうとしていない状態と一致していること

Lemma 2.8.1. deadlock-free ロックアルゴリズムでは inconsistent state にならない

背理法で示す。inconsistent であると仮定して、deadlock-free であることと矛盾を導く。

deadlock-free アルゴリズム n 個の異なるメモリ領域が必要であるが、3 スレッドで議論する。 （同じやり方で n スレッド版もできる）

• Definition 2.8.2.
  • Lock オブジェクトの状態 s が covering state とは、少なくとも 1 スレッドが、 各共有メモリ領域にまさに書き込もうとしている状態であるがメモリ領域上は CS にはどのスレッドも入っていない状態のことである

Theorem 2.8.1. 3 スレッドの deadlock-free な相互排除を提供するロックは 3 つのメモリ領域が必要

背理法で示す。2 個のメモリ領域で 3 スレッドの deadlock-free ロックができると仮定して矛盾を導く。
1. 各スレッドが CS に入る前には、どこか 1 箇所に情報を書かないといけないが（inconsistent になる）
   領域は 2 個しかないので、メモリを共有しないといけない
2. 2 スレッドの covering state になれると仮定すると、共有メモリの上書きにより
   CS に複数入れることが導かれる（Figure 2.13）
3. 最後に 2 スレッドの covering state になれることを証明する (Figure 2.14)

• 結局 Peterson と Bakery は理論上最適な実装ではあるが実用的ではない
  • そもそも read と write が同時にできない制限があるため、上書きを考慮しないといけないのが問題
  • もっと強力な命令（compareAndSet とか）があれば、定数領域で実現可能