全てのタイプのレジスタは計算可能性の面では同じということをこの節で説明
- レジスタ構築の流れ(図4.5)
コーディングルールの解説
- 整合性の特性をフィールド名の prefix で表現: safe なら (s_), regular なら (r_), atomic なら (a_)
SRSW safe → MRSW safe (コード: 図4.6)
- SRSW safe レジスタをスレッド数並べただけ
- 同じレジスタに複数のスレッドが読み込みしないようにする
- read()がwrite()と重複していない場合:
- s_table[i] は safe なので最後にwrite()された値を返す
- read()がwrite()と重複している場合:
- s_table[i] は safe なので何かを返す
MRSW Boolean safe → MRSW Boolean regular (コード: 図4.7)
- boolean レジスタの場合、 safe と regular の違いは write() で値が変更しない場合だけ起こる
- 値の変更が起こる write() を起こさない
- ThreadLocal によるガードは Single Writer だから可能
- write() で値の変更が起こらない場合
- write() 自体を起こさないので regular が保たれる
- write() で値の変更が起こった場合
- Boolean のどの値を返しても regular になる
MRSW Boolean regular → MRSW M-Valued regular (コード: 図4.8)
- 簡単。ただし脅威の非効率性
- 要素の数だけの Boolean レジスタを用意する
- true になっているレジスタのindexが現在の値
- 書き込みでは、値x以下のレジスタの配列を逆順に更新する
- 読み込み前に write(x) が最後に実行されたと仮定
- read()で読み込まれた値がxでは無い時、過去のwrite()で書き込まれた値のどれかを返す(補題)
- (いまいちよくわかっていない…)
SRSW regular → SRSW atomic (コード: 図4.11)
- 条件4.1.1〜4.1.3を満たさないといけない
- タイムスタンプ付きの値(図4.10)を使う
- reader スレッドでの読み込みの値をスレッドローカルで保持する
SRSW atomic → MRSW atomic (コード: 図4.12)
- MRSW safe の作り方に倣う、ただしこれでは条件4.1.3を満たさない
- 他のスレッドが更新された値を読んだ事を通知する
- 2次元配列で構築する
- 条件4.1.1: 略
- 条件4.1.2: 書き込みが完了後であれば、各行のデータに書いた値があるはずなのでOK
- 条件4.1.3
- 読み込みが完了していれば、各列のデータが更新されているはずなのでOK
- 二つの読み込みが同時期に起きていれば、戻りが生じる可能性がある
- (同時に読み込まれた場合、戻りが起きないだろうか? それは問題ではないのだろうか?)
MRSW atomic → MRMW atomic (コード: 図4.14)
- 条件4.1.1
- read()が終わった後に値を読むことはできない。(当たり前?)
- write()で発行するタイムスタンプは、過去完了したどのread()のタイムスタンプよりも値が大きい
- 条件4.1.2
- (略したい…)
- writeA()→writeB()の場合
- タイムスタンプが大きい値を取るのでBの値が取られる
- 条件4.1.3
- readA()→readB()
- tC<tDの場合、a_table[D]が読まれる
- tC==tDの場合、a_table[C]もtDと同じ時間の値なので間違いではない
今回のMRMWは現実的ではない。 現実のアーキテクチャを考える際に、弱い特性から強い特性のレジスタを構築する方法の議論を再度行う予定
Atomic Snapshot … Atomic レジスタの配列の瞬間的な状態が取得できるオブジェクト
- wait-free な Atomic Snapshot の実装を考える
- バックアップやチェックポイントに使える
Snapshot のインタフェース(図4.15)
- MRSW atomic レジスタの配列と同等
- update() … 自分のスレッドの値を更新する
- scan() … 各update()で最後に更新した値を取得する
Snapshot のロックを使った実装 (図4.16)
- これと同等で wait-free な実装を構築するのが目的
- update() は wait free、scan() は obstruction free
コード: 図4.17
- collect() で現在のスナップショットのコピーを取る
- collect() を二回実行して同じだったら、どのスレッドもレジスタを更新していない機関があった事が分かる
- (本当か?)
- この collect() の組を本書では clean double collect と呼ぶ
scan()は wait free ではない
- update() で毎回邪魔されたら返せないから
- scan を wait-free にするために update() でスナップショットを取って scan() の手助けをする
- double collect で場合は update() が作った snapshot を利用できる
実は簡単ではない
- update() が終わったときの事を「動いた」と呼ぶ
- A の clean collect が、 B が動いたために失敗したとする
- B のスナップショットを A が使えるか? というと使えない
- 例 (図4.18)
- ??
wait free の実装 (コード: 図4.19、図4.20、図4.21)
- B が 2 回 move したのを見た場合、 B は update() を完了したと見なして、Bのスナップショットを使用する
補題: clean double collect が成功した場合、その値はどこか時点で実際に存在したはずの状態である
- 1回目と2回目のcollectの間を考える。update()がその間に置きていれば値が違うはずなのでcleanにならない qed
補題: scan() するスレッド A が update() するスレッド B が動いた事を、2回のdouble collect で検出したとする。この時、最後の collect で得られた B の値は、最初の collect の後で update() された値を持っている
補題: scan() の結果は呼び出し前と呼び出し後の間にある状態を返す
補題: scan() と update() は最大で n^2 の書き込みか読み込みを行う