- 新しいマルチプロセッサをデザインするとしたら、どんなアトミック命令を用意する？
- いろんな論文に出てくるものを全て組み込むと複雑で非効率になる
- メモリ読み書き、getAndDecrement()、swap()、getAndComplement()、compareAndSet()、その他諸々
- 反対に、間違ったものを選択してしまうと最悪特定の同期問題を解決することが不可能になってしまう可能性がある
- いろんな論文に出てくるものを全て組み込むと複雑で非効率になる
- 現実の問題を解決するのに必要な、同期操作プリミティブセットを特定するのがこの章の目的
- そのためには各同期プリミティブのパワーを評価する仕組みが必要
- 共有オブジェクト(キュー、スタック、ツリー、etc)を__wait-free__に実装できるかどうかを調べるのは、ひとつの方法
- __deadlock-freedom__や__obstruction-freedom__といった性質は外部の環境(OS)に依存してしまうので不適切
- 各同期命令のパワーは等しくなく、明確な階層を形成している
- 低レベルのプリミティブをどのように使っても、高レベルのプリミティブを用いた__wait-free__実装を代替することは不可能
- 各階層(レベル)のプリミティブは対応する consensus number を有する
- その階層(クラス)のオブジェクトが__consensus__同期問題で扱えるスレッドの数の上限
- 以降では、低いクラスに属するオブジェクトを組み合わせても、より高いクラスのオブジェクトを(__wait-free__に)実装できないことをみていく
- __consensus object__は、以下の条件に満たした値を返す__decide()__メソッドを備える (図5.1)
- consistent: 全てのスレッドに同じ値を返す
- valid: いずれかのスレッドが入力した値を返す
- 簡単のために入力値は 0 か 1 のどちらかになるものとして話を進める (binary consensus)
- __wait-free__な実装を考える
- 歴史的な理由により、そういった実装を備えるクラスは__consensus protocol__と呼ばれる
- 複雑になりすぎるので非決定的なオブジェクト(クラス)は扱わない
- オブジェクトの数ではなくクラスの性質に着目 and 十分な読み書き用メモリが利用可能だと仮定
定義 5.1.1: もし任意の数の__クラスC__のオブジェクトと任意の数のアトミックレジスタを使って実装できる__consensus protocol__が存在するなら「__クラスC__は__n-thread consensus__を解決できる」と云える
定義 5.1.2: __クラスC__の__consensus number__は、そのクラスが解決できる最大の__n-thread consensus__である。もしそういった上限が存在しない場合は、そのクラスは__infinite__と呼ばれる
帰結 5.1.1: __クラスD__のオブジェクトとアトミックレジスタを組み合わせて、__クラスC__のオブジェクトを実装できるなら、__クラスC__が解決できる__n-consensus__は、__クラスD__も解決できる
- まず__consensus object__一般に関する話
- 二スレッド(スレッド__A__とスレッド__B__) かつ binary consensus のケースを考える
- それぞれのスレッドは値が定まるまで__move__する
- move: 共有オブジェクトに対するメソッド呼び出し
- protocol state(状態): スレッド群および共有オブジェクト群の状態
- initial state(初期状態): どのスレッドも__move__していない状態での__protocol state__
- final state(最終状態): 全てのスレッドの動作が完了した後の__protocol state__
- decision value: __final state__で全てのスレッドに確定した値
- __wait-free__での状態遷移は高さが有限のツリーで表現可能
- 図5.2: __A__と__B__が__final state__に至るまでのありえる__move__と状態遷移を図にしたもの
- bivalent: decision value__が定まっていない__protocol state(ノード)のこと
- univalent: decision value__が定まっている__protocol state(ノード)のこと。以降の__move__は結果に影響を与えない
- 確定した値によって、それぞれ__1-valent__、__0-valent__と呼ばれる
補題 5.1.1: 全ての__2-thread consensus protocol__は__bivalent initial state__を有する
証明:
- __A__が入力に0を、__B__が入力に1を持つ初期状態を考えるとして、
- もし__A__が、__B__が動作する前に処理を終えたとしたら、__decision value__は0にならなければいけない (__valid__条件)
- 逆の場合も同様
- よって__bivalent initial state__が存在することになる
補題 5.1.2: 全ての__n-thread consensus protocol__は__bivalent initial state__を有する
証明: エクササイズのためにとっておく
- 以下を満たす__protocol state__は__critical__と呼ばれる:
- bivalent
- いずれかのスレッドの__move__により__univalent__へと移行する
補題 5.1.3: 全ての__wait-free consensus protocol__は__critical state__を有する
証明:
- __補題 5.1.2__により必ず何らかの__bivalent initial state__が存在する
- bivalent => univalent への遷移がないスレッドを__move__し続けるとして、
- いつかは__univalent__へ切り変わざるを得ない状態に達する
- もし延々と__move__できるなら、それは__wait-free__ではない
- アトミックレジスタでは二スレッド以上のconsensus問題も解くことができない
- solo: 一つのスレッドが完全にそれのみで終了するまで動作し続けるシナリオ
定理 5.2.1: アトミックレジスタは__consensus number 1__を有する
証明:
- 背理法による証明
- __binary consensus protocol__が存在するか
- スレッド__A__と__B__が__critical state__にいると仮定
- __A__が先に動くと__0-valent state__に、__B__が先に動くと__1-valent state__に移行する
- 以下の３つのケースが考えられる
- 片方のスレッド(A)がレジスタを読み込もうとしている (図 5.3)
- 矛盾: __A__の__move__はレジスタの値を変化させないので、__B__の結果は(単独の場合と__A__が先の場合で)常に同じになる
- 両者が別々のレジスタに書きこもうとしている (図 5.4)
- 矛盾: どちらが先に動いても、最終的に同一の(区別できない)__protocol state__に到達する
- 両者が同じレジスタに書きこもうとしている (図 5.5)
- 矛盾: __A__が先に動いたとしても、__B__が上書きしてしまうので結果は(単独の場合と__A__が先の場合で)常に同じになる
- 片方のスレッド(A)がレジスタを読み込もうとしている (図 5.3)
帰結 5.2.1: アトミックレジスタを使って__consensus number__が1以上の__wait-free__オブジェクトを実装することは不可能
現代的なマルチプロセッサ上で、__lock-free__な並列データ構造を実装するためには、ハードウェアが単なるメモリ読み書き以外の同期操作プリミティブを提供している必要がある。
- これから__consensus problem__を解決する様々なオブジェクトクラスについて考えていく
- それらのプロトコル(実装)は 図5.6 に示される汎用的な形式を備えている
- decide(), propose()
- 同期オブジェクトによって decide() の実装が変化する
- アトミックレジスタを使って複数のdequeuerおよびenqueuerに対応したFIFOキューが実装できるか？
- より限定的に、二つのdequeuerに対応したキューが作れるか、を考える
定理 5.4.1: 二つのdequeuerに対応したFIFOキューは少なくとも2以上の__consensus number__を有する
証明:
- 図 5.7: __2-dequeuer FIFO queue__を持ちいた__2-consensus protocol__の実装
- __WIN__と__LOSE__を要素に入れておき、前者を取得したスレッドは自分の値を、後者の場合は相手の値を、使用する
- FIFOキューじゃなくても実装可能。例えばスタック、優先順序付きキュー、リスト、セット、etc
- 異なる順序で適用された場合に異なる値が返るオブジェクトなら何でも良い
帰結 5.4.1: アトミックレジスタからは__wait-free__なFIFOキューの実装は不可能 (スタックやリスト等も同様)
※ アトミックレジスタの__consensus number__がFIFOキューのそれより低いため
定理 5.4.2: FIFOキューの__consensus number__は2
証明:
- 背理法による証明
- スレッド__A__、B、__C__があり、A__が先なら__0-valent、B__が先なら__1-valent、という__critical state__にいると仮定
- __A__と__B__は同じFIFOキューに対して、メソッド呼び出しを行う直前の状態 (not commute, not registers により)
- 以下のケースが考えられる:
- __A__と__B__の両方が__deq()__を呼び出す (図 5.8)
- 矛盾: __C__からは、どちらが先に動いたかを判断できない (キューの要素が二つ減っているが、その順番は不明)
- __A__が__enq(a)__を、__B__が__deq()__を呼び出す
- 矛盾1: キューが空ではないなら、__A__と__B__の順番は結果に影響を与えない
- 矛盾2: キューが空でも、__C__は、「__B__が先の場合(1-valent)」と「__A__が単独で動いた場合(0-valent)」が区別できない
- __A__が__enq(a)__を、__B__が__enq(b)__を呼び出す (図 5.9)
- 前提: 両方がいずれの順番に__enq()__を呼んだとしても、その結果を知るために対応する__deq()__を呼ぶ必要がある
- 矛盾: 二つの__enq()__と対応する__deq()__が呼ばれた後、__C__からはどちらが先に動いたかを知るすべがない
- __A__と__B__の両方が__deq()__を呼び出す (図 5.8)
同様の証明が スタック、セット、デック、優先順位付きキュー、その他同様のオブジェクト、にも当てはまる。
- __(m, n)-assignment__問題 (__multiple assignment__とも云われる)
- n >= m > 1
- n個のフィールド(or n要素の配列)を持つオブジェクト
- __assigin()__メソッド: 引数としてm個の値(vi)と、m個のインデックス(ii)を受け取る (インデックスはn未満)
- 指定の各フィールド(配列)への代入をアトミックに行う: ary[ij] = vj、 j ∈ 0〜m-1
- __read()__メソッド: インデックスを引数にとり、対応する要素の値を返す
- 四章で出てきた__atomic snapshot__のdual: 一つのフィールドへの代入 と 複数のフィールドのアトミックな読み込み
- __snapshot__はアトミックレジスタで実装可能なので__定理 5.2.1__より、__snapshot__オブジェクトの__consensus number__も1
- 図 5.10: ロックベースの__(2,3)-assignment__オブジェクトの実装
定理 5.5.1: アトミックレジスタを用いて__(m,n)-assignment__オブジェクトの__wait-free__な実装を行うことは不可能 (n > m > 1)
証明:
- __(2,3)-assignment__オブジェクトが__2-consensus__問題を解けることを示せれば十分
- 一般に__decide()__メソッドは、どちらのスレッドが先に来たかを判別できる必要がある
- 図 5.11、図 5.12: __(2,3)-assigment__オブジェクトによる__2-consensus protocol__の実装と図解
- それぞれのスレッドに対して「自分だけが書き込む場所」と「両方が書き込む場所」を用意する (二箇所にはアトミックに書き込む)
- 「相手が書き込む場所が空」なら自分が先
- 「両方が書き込む場所が相手によって上書きされている」場合も自分が先
定理 5.5.2: n > 1__のアトミックな(n, n(n+1)/2)-assignment__オブジェクトは最低でも__n__以上の__consensus number__を有する
証明:
- __n-consensus__問題に対して、以下の__n(n+1)/2__個の二種類のフィールドを用意する
- ri: __n__個の、それぞれのスレッドに専用のフィールド
- rij: __(n-1)/2__個の、二つのスレッド__i__と__j__が共有するフィールド (i > j)
- 代入(到着)時には「自分用のフィールド」と「他と共有するn-1個のフィールド群」にアトミックに値を設定する
- 以下の判定によって、二つのスレッド間の代入(到着)の順序を判定可能
- __rij__を読んで、もし値がnullならどちらのスレッドも到着していない
- __ri__と__rj__を読んで、もし__ri__がnullなら__j__は__i__に先行する。逆も同様。
- __ri__と__rj__のどちらもnullではなく、__rij__の値が__ri__に等しいなら、__j__は__i__に先行する。逆も同様。
- 上の判定を繰り返すことによって、どれが一番早く到着したスレッドかを判定可能 (__decision value__が定まる)
- NOTE: __atomic snapshot__は__consensus number__が1なのに、類似の__multiple assignment__のそれはスレッド数に比例する
- 複数箇所へのアトミック書き込みは、読み込みよりもより大きなcomputationalパワーが要求される
- マルチプロセッサによってハードウェア的に提供されている古典的な同期操作の多くは__read-modify-write__(RMW)操作として表現可能
- あるいはオブジェクト的な観点に着目して、RMWレジスタ、とも呼ばれる
- ___F___を整数から整数への写像を行う関数の集合として、以下を行うメソッドはRMWと云える
- レジスタの現在の値__v__を、__f(v)__の適用結果にアトミックに置換する (f ∈ F)
- メソッドの結果として置換前の値__v__を返す
- 例えば、Javaの__java.util.concurrent.AtomicInteger__クラスは、以下のような豊富なRMWメソッドセットを提供している
- getAndSet(v), getAndIncrement(), getAndAdd(k), compareAndSet(), get()
- 対象の関数集合に恒等関数以外を含むRMWメソッドは__nontrivial__と云う
定理 5.6.1: 全ての__nontrivial__なRMWレジスタは最低でも2以上の__consensus number_を有する
証明:
- 図 5.14: __nontrivial__なRMWレジスタを用いた__2-thread consensus protocol__の実装
- レジスタをユニークな値で初期化しておき、自分のRMWメソッド呼び出しがその値を返したら、自分が先に到着したと分かる
帰結 5.6.1: アトミックレジスタを用いて__nontrivial__なRMWレジスタの、二つ以上のスレッドに対応した__wait-free__な実装を行うことは不可能
- __Common2__クラスに属するRMWレジスタ
- 20世紀の最後の方のプロセッサによって提供されていた多くの共通な同期プリミティブがこれに属する
- アトミックレジスタよりは強力だが__consensus number__は2に制限されている
定義 5.7.1: 関数集合___F___は、次のいずれかの条件を満たしているなら__Common2__に属する
- 全ての値__v__および___F___に属する関数__fi__、__fj__に対して:
- __fi__および__fj__が入れ替え可能: fi(fj(v)) = fj(fi(v))
- ある関数が別の関数の結果を上書きする: fi(fj(v)) = fi(v) or fj(fi(v)) = fj(v)
定義 5.7.2: 対応する関数集合___F___が__Common2__に属するなら、そのRMWレジスタも__Common2__に属する
- 例えば学術論文では__nontrivial__関数を一つだけ備えるRMWレジスタがよく出てくる
- 他を上書きするgetAndSet()や、他と入れ替え可能なgetAndIncrement() or getAndAdd()
定理 5.7.1: __Common2__に属する全てのRMWレジスタの__consensus number__は2
証明:
- __定理 5.6.1__によって__nontrivial__なRMWレジスタは最低2の__consensus number__を持っていることが分かっているので、__3-thread consensus__を解決できないことが示せれば良い
- 背理法
- 仮定: __Conmmon2__のRMWレジスタ、およびアトミックレジスタの組み合わせて__3-thread consensus__が解決可能
- スレッド__A__、B、__C__が__critical state__にいるとする
- 次の__move__は一つのRMWレジスタへのメソッド呼び出しでなければならない
- __A__が先なら__0-valent__に、__B__が先なら__1-valent__へと状態が遷移する
- 以下のケースが考えられる:
- 上書き関数の場合 (図 5.15)
- __C__から見たら、__B__が単独で走った後の状態、と、A=>__B__の後の状態の区別がつかない
- 入替可能関数の場合
- __C__から見たら、A=>__B__の後の状態と、B=>__A__の後の状態の区別がつかない
- 上書き関数の場合 (図 5.15)
- compareAndSet()
- Intelの__CMPXCHG__命令、compare-and-swapとも呼ばれる
- 引数に期待値と更新値を取り、現在の値が期待値と等しいなら、値を更新する (結果はboolean)
定理 5.8.1: compareAndSet()とget()を提供するレジスタは__infinite__な__consensus number__を有する
証明:
- 図 5.16: __infinite__な__consensus protocol__の実装
- 期待値が__FIRST__なら自分の値で更新、他のスレッドはその更新された値を参照する
- get()メソッドはなくても大丈夫
帰結 5.8.1: compareAndSet()を提供するレジスタは__infinite__な__consensus number__を有する
- compareAndSet()のようなプリミティブ操作を提供するマシンは、チューリングマシンの、非同期計算における対応物 (六章)
- その上では、いずれの並列オブジェクトも__wait-free__に実装することが可能
- compareAndSet() is "king of all wild things."
省略
省略