sile/AMP-CH2.md

## AMP-CH2.md

      
    Raw
  

              AMP-CH2.md
            
          
    二章 Mutual Exclustion - 相互排除


相互排除は、マルチプロセッサプログラミングで最も普及している調整手段
この章は、共有メモリを用いた古典的な相互排除アルゴリズムを取り扱う

現実では使われていない。しかし、

相互排除アルゴリズムや正確性問題、同期について考える際の入り口としては理想的


不可能性の証明も導入する

共有メモリを用いた相互排除では何が実現できないか、を教えてくれる


アルゴリズムの証明を行っているまれな章でもある

2.1 Time - 時間


並列プログラミングについて推論する、ということは、ほとんど時間について推論する、ということ

複数の物事が同時に起こったり、あるいは別々に起こったり
複数の時間が重なることができたり、あるいはできなかったり


自然言語では、曖昧すぎて、このような複雑な条件のもとでの推論を行うには弱い

並列スレッド群が時間時間でどのように振る舞うかを記述するための、独自の語彙と記法を導入する


語彙と記法:

スレッド群は同じ(外部からは独立した独自の)時間を共有する
スレッドは__ステートマシン__であり、そのステート(状態)の遷移は__イベント__と呼ばれる
イベントは瞬間的

時間軸の一つの瞬間に発生する
同じ瞬間には複数のイベントが同時に発生することはない (その方が思考の際に便利)

もし複数のイベントの発生時間が近すぎて、どれが先かが分からないようなケースでは、任意の順序が起こりうる、と考える


スレッド_A_ は、イベント列   a₀,a₁,...  を生成する
イベント a_i の j 番目の出現は a_i^j と記述する
イベント_b_ に先行するイベント_a_ は a→b と表記する (total order)
二つのイベント_a₀_ と a₁ は a₀→a₁ という関係を持つ
区間_(a₀,a₁)_ は a₀ から a₁ までの期間を表す
区間_I_B = (b₀,b₁)_ に先行する 区間_I_A = (a₀,a₁)_ は a₁→b₀ が成り立つなら I_A→I_B と表記する

区間に対する_→_ 関係は、二つの区間同士のpartial orderを定義する
→ 関係を持たない区間同士は、並列である、と云われる


区間_I_A_ の_j_ 番目の実行は_I_A^j_ と表記する

2.2 Critical Sections - クリティカルセクション


クリティカルセクション

一度に一つのスレッドのみが実行可能なコードブロック
相互排除プロパティを備える
相互排除を達成する標準的な方法はロックを使うこと

__Lock__オブジェクト(Figure 2.2): lock と unlock メソッド備える


__Lock__を使用するスレッドは一定の形式に従う必要がある

各クリティカルセクションは、ユニークな__Lock__オブジェクトに結びついている
スレッドはクリティカルセクションに入る(入るのを試みる)前に__lock()__を呼び出す
スレッドはクリティカルセクションを出るときには__unlock()__を呼び出す


良いロックアルゴリズムが満たすべき性質:

※ CS_A^j  はスレッド__A__による、__j__回目のクリティカルセクション(区間)の実行を表す

Mutual Exclusion(相互排除):

異なるスレッド間のクリティカルセクションはオーバラップしない
スレッド A 及び B、任意の整数 j 及び k に対して、__CS_A^k→__CS_B^j あるいは __CS_B^j→__CS_A^k が成り立つ


Freedom from Deadlock(デッドロックフリー):

ロック獲得を試みたスレッドが一つ以上ある場合、その内のどれかは(いつかは)獲得できる
もしあるスレッドがいつまでもロックを獲得できないとしたら、それは別のスレッドが延々とロックの獲得・解放およびクリティカルセクションの実行を繰り返している場合のみ


Freedom from Starvation(飢餓フリー):   ※ aka. lockout freedom

ロック獲得を試みたスレッドは全て、いつかロックを獲得できる
deadlock freedom を包含する


__相互排除__は safety property。これを備えていないと、計算の正しさが保証できない
__デッドロックフリー__は liveness property。システムが(全体として)フリーズしないために重要

特定のスレッドがフリーズする可能性はある(starvation)
複数のロックを使用する場合、それぞれがデッドロックフリーの性質を備えている場合でもデッドロックが発生する可能性がある (『食事する哲学者』が有名)


__飢餓フリー__は望ましいのは明らかだけど、三つの中で一番実現されることが少ない

後続の章で飢餓フリーを備えることができなかった実用の相互排除アルゴリズムを見ていく

それらの大抵は、飢餓が理論的には発生しうるけど、通常の用途ではほとんど起こらない環境で用いられる


飢餓フリー属性は、クリティカルセクションに入るまでの待ち時間の長さを保証しない

後続の章で、スレッドの最大待ち時間に上限を設けたアルゴリズムについても見ていく


2.3 2-Thread Solutions - 二スレッドの排他方法

まず、二つの能力不足ではあるが興味深いロックアルゴリズムについて見ていく。
スレッド数は二つに限定する。
新たな記法:

write_A(x = v): スレッド__A__が__x__フィールドに、値__v__を割り当てるイベント
read_A(x == v): スレッド__A__が__x__フィールドから、値__v__を読み取るイベント
値が重要ではないときは__v__は省略するかも


2.3.1 The LockOne Class


図 2.4
相手がロック獲得を試みている(or クリティカルセクションにいる間)は待機する

一人の時だけ使用する
両方が(ドアの前に)居合わせた場合はデッドロックに!


命題 2.3.1:  LockOneアルゴリズムは相互排除プロパティを満たす
証明(背理法):

前提

クリティカルセクションに入るには「自分のフラグをonにした」後に「相手のフラグがoff」であることを確認する必要がある
クリティカルセクションに入る前に一度onになったフラグがoffに戻ることはない


両方のスレッドがクリティカルセクションに入るには以下のイベントの遷移をたどる必要がある

__A__がフラグをonにする
__A__が__B__のフラグがoffであることを確認する => __A__はクリティカルセクションに
__B__がフラグをonにする
__B__が__A__のフラグがoffであることを確認する => __B__がクリティカルセクションに

ここで矛盾発生! (__A__のフラグが on かつ off に)


面白い性質:

二つのスレッドが別々に走って入れば上手く行く


2.3.2 The LockTwo Class


図 2.5
別のスレッドが来るまで待ち続け、来たら交代する

バトンタッチ方式
一つのスレッドしか動いていなかった場合はデッドロックに!


命題 2.3.2: LockTwo アルゴリズムは相互排除プロパティを満たす
証明(背理法):

__A__が自分を犠牲者に設定
__B__が自分を(__A__の代わりに)犠牲者に設定
__A__は__B__が犠牲者になっているのを確認 => クリティカルセクションに
__B__は__A__が犠牲者になっているのを確認 => クリティカルセクションに

ここで矛盾発生! (__A__を犠牲者に設定するイベントが存在しない)


面白い性質:

二つスレッドが並列に走っていると上手く行く
LockOneとLockTwoは相補的

片方がデッドロックになる状況が、もう片方には好ましい


2.3.3 The Peterson Lock - ピーターソンロック

LockOneとLockTwoを組み合わせた__飢餓フリー__なロックアルゴリズム。
おそらく二つのスレッドでの相互排除アルゴリズムの中では、最も簡潔でエレガント。

図 2.6
一人しかいないなら勝手に使って(LockOne)、競合時はバトンタッチ方式(LockTwo)で所有者を決める

命題 2.3.3: Peterson ロックアルゴリズムは相互排除プロパティを満たす
証明(背理法):


命題 2.3.4: Peterson ロックアルゴリズムは飢餓フリー
証明:

一言で云ってしまえば、競合解消にバトンタッチ方式を採用しているので、片方のスレッドが毎回所有権を得つづけることはない

帰結 2.3.1: Peterson ロックアルゴリズムはデッドロックフリー

2.4 The Filter Lock - フィルターロック

二個以上のスレッドに対応するロックアルゴリズムを二つ取り上げる。

Filterロック: Petersonロックをそのまま一般化したもの
Bakeryロック: おそらく最も簡単で一番良く知られている複数スレッドロックアルゴリズム

Filterロック:

図2.7
Levels

クリティカルセクションに通る前に通過しなければならないn-1個の待ち部屋 (nはスレッド数)
あるレベル(部屋)に入ろうとするスレッドがある場合、

少なくとも一つは入ることに成功する
複数スレッドが入ろうとした場合は、最低一つはブロックされる


スレッドは最初はレベル0に居て、レベルn-1に到達したらクリティカルセクションに入る

レベル_j_ にいるスレッドは、それより下の全てのスレッドにもいるものとみなされる


各レベルごとに犠牲者が一人いる
スレッドは、以下の条件を満たした場合に、目的のレベルに入れる

自分と同じかより上のレベルにいる(or 入ろうとしている)スレッドがいない  (LockOne)
自分が目的のレベルでの犠牲者になっていない (LockTwo)


全nスレッドが一度にクリティカルセクションに入ろうとした場合は、各レベルに付き一人が犠牲者となって留まるので、最後のレベル(クリティカルセクション)まで残るのは一スレッドだけ、となる


命題 2.4.1: 0からn-1の数値jに対して、レベルjには多くてもn-jのスレッドしかいない
証明:

要はレベルが一つ上がると、そこに同時に居られるスレッド数が一つ減ることを示したい
背理法

複数スレッドがレベル_j_ に入ろうとしている
__A__を最後に来たスレッドとする

レベル_j_ の犠牲者は__A__ に設定される


_A__以外のスレッドは__A__が犠牲者になっているのでレベル_j に入れる

ということは__A__がいるところ以上のレベルにいるスレッドが最低一つはあることになる


犠牲者__A__は同等以上のレベルにいるスレッドが存在しないため、スレッド_j_ に入れる

ここで矛盾発生！


クリティカルセクションに入るということは、レベルn-1に入る、ということに等しい。
帰結: Filterロックアルゴリズムは相互排除プロパティを満たす
命題 2.4.2: Filterロックアルゴリズムは飢餓フリー
証明(背理法):

レベル_j_ の前にスレッド__A__ が留まり続ける(ブロックされ続ける)ケースがあることを示す
帰納的仮定

レベル_j_ == レベル_n-1_ のケース: __A__が留まり続けることはありえない(既にクリティカルセクション)
レベル_j_ < レベル_n-1_ のケース: レベル_j+1_ かそれ以上にいるスレッドは、いつかはクリティカルセクションに到達する (仮定)


以下、

仮定により、__A__より上のレベルにいるスレッドはいつかはいなくなる

レベル_j_ に入ろうとしているスレッドが__A__ しかいないなら、A はレベル_j+1_ へと進めてしまう


A__より後にレベル_j に入ろうとする全てのスレッドは、既に__A_ がいるため、そこに留まることになる(留まる瞬間が発生し得る)

この時点で犠牲者の値は__A__以外になる (その後 -一周せずに- __A__に戻ることはない)


犠牲者以外のスレッドは、レベル_j+1_ へと進む

__A__も進むことになってしまうので、最初の条件が成り立たない！


帰結 2.4.2: Filterロックアルゴリズムはデッドロックフリー
2.5 Fairness - 公正


飢餓フリー性は、スレッドがロックを獲得できることは保証するが、それにどのくらい時間が掛かるかに関しては何の保証もしない。
A が B より先に__lock()__メソッド呼んだなら、__A__の方が先にクリティカルセクションに入るべき

どのスレッドが先に__lock()__を呼び出したかを決定(表現)できるようにするためのツールが必要
__lock()__メソッドを以下の二つの部分に分割する

__doorway__セクション: 実行区間__D_A__は有限ステップから構成される
__waiting__セクション: 実行区間__W_A__は非有限(かもしれない)ステップから構成される


doorwayセクションが常に有限ステップで終了するというには強い要求

bounded wait-free progress property
この性質を満たすためのシステマティックな方法を後続の章で議論する


定義 2.5.1: doorwayセクションの実行順序と、クリティカルセクションの実行順序が常に一致するようなロックは__first-come-first-served__といえる
2.6 Lamport's Bakery Algorithm - ランポートのパン屋のアルゴリズム


図2.9


__first-come-first-servedプロパティ__を各スレッドへの(パン屋でよく見かける)整理券の配布によって満たしている

各スレッドへの到着順による番号割り当てと、その番号順に従ったクリティカルセクションへの入場


doorwayセクション: 13行目と14行目

ロックを取得したい旨の宣言
番号(ラベル)取得

一番最後の番号 + 1
他のスレッドと同じ番号を取得してしまうことがあるが、その場合はスレッドIDで優先度付け


waitingセクション: 15行目

自分より若い番号のスレッドがいなくなるまでループして待機


命題 2.6.1: Bakeryロックアルゴリズムはデッドロックフリー
証明:
必ずユニークかつ最小の__(ラベル,スレッドID)__を持つスレッドが存在し、そのスレッドは他のスレッドを待ち合わせることはない
命題 2.6.2: Bakeryロックアルゴリズムは first-com-first-served
証明:

__A__のdoorwayセクション(番号割当)が__B__のそれより先行しているなら、番号が若いので、常に先にクリティカルセクションに入る
__deadlock-free__と__first-come-first-served__の両方を満たすアルゴリズムは__starvation-free__でもある。

命題 2.6.3: Bakeryアルゴリズムは相互排除である
証明(背理法):

仮定: __A__と__B__の両方がクリティカルセクションに入っている

__Aの番号__は__Bの番号__より若いとする => __A__はクリティカルセクションに入る
__B__は、__flag_A__の値が__false__であることを確認する => __B__もクリティカルセクションに入る

__flag_A__の値が__false__であるためには、__B__が__A__よりも先に番号割当されている必要がある
矛盾! (__B__の方が先に整理券を受け取ったのに、番号は後から来た__A__より大きい)


2.7 Bounded Timestamps - 有限タイムスタンプ


Bakeryロックで使ったラベル(番号)は際限なく増加していく

寿命の長いシステムだとオーバフローするかも
ラベルが0に戻ってしまうことがあるなら__first-come-first-servedプロパティ__が保持されなくなる
オーバーフローが許容できないかどうかはシステムによる


Bakeryロックではラベルは__タイムスタンプ__として扱われている

__タイムスタンプ__は競合するスレッド同士の順序付けを行う
あるスレッドが別のスレッドより後にラベルを取得したなら、その値はより大きくなければならない
Bakeryロックでは、スレッドは以下の二つを行う必要がある: (図 2.10)

scan:  他のスレッドのタイムスタンプを読む
label: 自分により大きいタイムスタンプを割り当てる


ここで扱う__タイムスタンプ__はロックのdoorwayセクション用

__タイムスタンプ__の生成は__wait-free__で行えなければならない
__wait-free__の並列タイムスタンプ生成システムを構築することは可能だが難しい (ChapterNoteも参照)

ここではより簡単な__シーケンシャル__なタイムスタンプ生成システムにのみフォーカスする
__scan-and-label__操作が排他的(アトミック)に行われるものとする
直列版も並列版と原理は同じ。実装詳細は全く異なるけど。


タイムスタンプの取り得る範囲をノードの__direct-graph(precedence-graph)__と考える:

__a___から__b__へのエッジは、__a__が__b__より後のタイムスタンプであることを示す
このタイムスタンプは以下の性質を備える:

irreflexive: 自分自身へのエッジはない
antisymmetric: __a__から__b__へのエッジがあるなら、その逆は存在しない
__transitive__である必要はない: __a__から__b__へのエッジ、__b__から__c__へのエッジがあっても、__a__から__c__へのエッジはないかもしれない


スレッドへのタイムスタンプの割り当ては、スレッドのトークンをタイムスタンプのノード上に置くことに等しい

他のスレッドのトークンが乗っているノードを探し(scan)、
自分のトークンをそれらのノードすべてにエッジを持つノード上へと移動する(label)


__single-writer multi-reader__のフィールドを持つ配列で実装できる

配列[スレッドID]に自分が最後に使ったノード入れておく
スキャン時には配列の__snapshot__を取ると良い (四章位の話題)


図2.11: Bakeryロックで使われていたunboundedなタイムスタンプシステム


boundedなタイムスタンプシステム

図2.12　
スレッド数が二つの場合は、三つのノードを(交互に)ぐるぐる回り続ければ良い
二つ以上のスレッドに対応する場合は拡張が必要 (additional conceptual tools)

厳密は定義は本書を参照
対応スレッド数を一つ上げるには__T2__のグラフの各ノードを、現在のグラフで置換すれば良い
各スレッドのタイムスタンプは三進数で表現できる
最新のタイムスタンプがほしい場合は、上のレベルのグラフから順に、再帰的に先頭を探し続ければ良い


2.8 Lower Bounds on the Number of Locations - 最低限必要なread/write領域の数


Bakeryロックは簡潔でエレガントで公正

ただし__N__個のスレッドに対応しようとしたら__N__個の異なるread/write用の場所が必要という欠点がある
使用する場所は減らせる? => NO


read/write操作を用いている限りは__N__より少ない場所を使ってでは、__deadlock-freeロック__は実現できない

そのためマルチプロセッサマシンは、相互排除を実現するために、単なるread/writeよりもより強い同期命令を備えている必要がある
この章では、なぜこの制限が本質的なものであるかを説明する (より実践的な相互排除の実現方法は後続の章で扱う)
重要なのは「あるスレッドによってwriteされた情報は、誰かがそれをreadする前にoverwrittenされ得る」ということ


証明用の(マルチスレッドプログラムが使用するメモリの状態に関する)用語定義

object's state: そのオブジェクト自身のフィールドの状態
trhead's local state: スレッドのプログラムカウンタおよびローカル変数の状態
global(system) state: プログラム内の全ての__object's state__および__thread's local state__


定義 2.8.1:
次の条件を満たす場合、ロックオブジェクト__A__の状態__s__は__inconsistent__である:

あるスレッドがクリティカルセクション(CS)内に存在する
しかし、__A__の状態は「__CS__にスレッドがいない」あるいは「__CS__にスレッドが入ろうとしている」場合のそれと互換性がある

命題 2.8.1: デッドロックフリーアルゴリズムが inconsistent-state になることはない
証明(背理法):


仮定: ロックオブジェクトの状態__s__が__inconsistent__

スレッド__A__がクリティカルセクションに入っている
__B__はクリティカルセクションに入りたい
__A__がクリティカルセクションから抜けたかどうかが__s__からは判断できない
デッドロックフリーなら__B__はいつかクリティカルセクションに入れる(= __A__がいないことを判別できる)はず
矛盾！


全ての__deadlock-free__な相互排除ロックアルゴリズムは、スレッド数分の異なる場所(領域)を持っている必要がある

ここでは三スレッドのケースを考える


定義 2.8.2:


あるロックオブジェクト対する__covering state__とは、以下のような状態のことを云う:

ロックの全ての共有領域に対して、少なくとも一つのスレッドが、ちょうど書き込み直前の状態であり、
かつ、そのロックオブジェクトの(領域の)現在の状態では、クリティカルセクションが__"空いている"__ように見える

"空いている" => クリティカルセクションにスレッドがいない and 誰も入ろうとしていない


__covering state__下では、それぞれのスレッドが書き込みを行う直前の領域を__cover__している


定理 2.8.1: 三スレッド用の、メモリのread/write操作に基づく全てのデッドロックフリー相互排除ロックアルゴリズムは、最低でも三つの異なるメモリ領域を必要とする
証明(背理法):


仮定: 二つのメモリ領域だけを使った三スレッド用のデッドロックフリーロックアルゴリズムが存在する

初期状態__s__では、クリティカルセクション(CS)は__"空いている"__
あるスレッドが__CS__に入るためには、その前に、少なくとも一つの共有領域に書き込みを行わなければならない

でなければ__inconsistent state__になる


もし共有領域が(Bakeryロックの場合のように)__single-writer__用の場合:

全てのスレッドが同時に__CS__に入ろうとした場合は、全て異なる場所が必要


もし共有領域が(Peterson'sロックのvictimのように)__multiwriter_用の場合:

図2.13
スレッド__A__と__B__がそれぞれ異なる場所を__cover__している => covering state
新たに__C__が__CS__に入ろうとしてきた
デッドロックフリーなので、__C__は(共有領域に書き込みを行った後に)__CS__に入る
__A__と__B__が書き込みを実行
__C__が__CS__にいるという情報が上書きされてしまった! => __inconsistent state__なので矛盾！


__convering state__になった場合に矛盾が生じることは示せた


残りは、どうやったら__A__と__B__が__coversing state__に辿り着くか、を示す

略 => __A__が__L_B__にトレース用の情報を残しているかもしれない、というくだりが良くわからない
そんなことをしたらそもそも__inconsistent state__になるのでは？
__A__と__B__で同じ場所に書くことがある => inconsistent state => 別々の場所に書くしかない => covering state => __C__が加わる => 矛盾、という流れの方が分かりやすい


同じことが_N_スレッドに対するデッドロックフリー相互排除ロックに対しても云える

そのため__Petersonロック__や__Bakeryロック__は(アルゴリズムのオーダー的には)最適ではある
ただ明らかに非実用的


この証明はread/write操作の本質的な制限を示している

あるスレッドが書き込んだ情報は、誰も読まない間に別のスレッドによって上書きされる可能性がある
別のアルゴリズムのデザインに移る際にも、この制限を思い出すだろう


後続の章では、現代のマシンアーキテクチャがこの制限を克服するために提供しているより特殊化された操作を見ていく

それらの操作を使えば__N__スレッドロックが定数個のメモリ領域で実現可能
それらの操作を__効率的__に使ってロックを実装することが容易ではないことも見ていく