シーケンシャルコンピューティングの基礎は 1930 年代に Alan Turing と Alonzo Church の Church-Turing Thesis で確立した（Turing Machine, Church’s Lambda Calculus）。 「何が計算可能か？」を正確に定義していないので、命題（thesis）であって定理（theorem）ではないよ！
この章では、並行共有メモリ計算の基礎を説明。
複数スレッドで計算されるが、各スレッド自体はシーケンシャルで、
共有メモリのオブジェクトのメソッドを介してコミュニケートする。
スレッドは非同期なので、異なるスピードで走り、予期できない時間停止できてしまう。
古典的なシーケンシャル計算可能性は、有限オートマトンから、プッシュダウンオートマトン、 チューリングマシンと段階を追って進んできた。
並行コンピューティングでも段階を追う。
この章では、単純な共有メモリ計算（並行スレッドが共有メモリ
（歴史的な理由でレジスタと呼ばれる）に単純な読み書き）からスタート。
単純なレジスタから初め、それを元に一連の複雑なレジスタを扱う。
古典的なシーケンシャル計算可能性の大部分は効率には監視ながない。
チューリングマシンの計算は現実的でない方法なので、計算できるかどうかが重要。
同様にこの本でも、レジスタの構築を効率より実現可能で分かりやすい手法で取り扱う。
具体的には、値の時系列の比較にタイムスタンプを使ったりする。 タイムスタンプは上限がないので、固定長ではオーバーフローの問題があるけど、シンプルに説明するため。
ハードウェアレベルで、スレッドのコミュニケーションは共有メモリの読み書きで行う。
理解しやすくするために、ハードウェアのプリミティブではなく、共有並行オブジェクトでのやりとりを考える。
Fig. 4.1 でレジスタの共通インタフェース Register<T> を定義している。
M-valued register: 範囲 M の整数を取る Register<Integer>
メソッド呼び出しがオーバーラップしない場合は Fig. 4.2. のような実装でいいけど、マルチプロセッサではダメ。
読み書きで排他ロックを使うのが考えられるが、ここでは排他制御は使えない。
Chapter 2 のレジスタを使った相互排他の実現を扱ったので、相互排他を使ったレジスタの実装は意味ない。
Chapter 3 で、deadlock-free でも starvation-free であっても計算が progress するかは
OS のスケジューラがスレッドがクリティカルセクションで動けならないように保証しないといけない。
この progress を仮定して進めるのはあんまり意味ない。
なので、OS に依存しない wait-free (lock-free) のレジスタで考える。
atomic レジスタは Fig.4.2. の linearizable 実装のこと。
リーダーとライターの数も重要、SRSW のみのサポートは簡単。
- SRSW : single-reader, single-write
- MRSW : multi-reader, single-writer
- MRMW : multi-reader, multi-writer
この章では、最も弱いレジスタから、どこまで強力なレジスタを定義できるかという問題に取り組む。
Chapter 1 で、スレッド間のコミュニケーションに役立つ形式は persistent でなくてはならない。 最も弱い persistent な同期は、共有メモリに persistent な 1 ビットをセットできること。 最も弱い同期は何もしないこと。
1ビットのセットがそのビットの読み込みとオーバラップしないなら、読まれた値は書かれた値と同じ。 読みと書きがオーバーラップした時はなんらかの値が返される。 異なる種類のレジスタは異なる保証を提供する（データの種類、reader, writer の数、一貫性の違い）。
MRSW レジスタ実装が safe というのは
- read() が write() とオーバーラップしない時は、最後の write() の値を返す
- read() が write() とオーバーラップする時は、レジスタの取りうる値のいずれかが返される
"safe" という呼び方は歴史的な事故。 safe は弱い保証であり、実際には安全ではない。
safe と atomic の中間の一貫性レベルを regular (MRSW レジスタが atomic でない)とする。
- regular レジスタは safe
- read() がいくつかの write() とオーバーラップしている場合、 v0 を最新の write() の値とし v1〜vk をオーバーラップしている write() の値とする。 この時、read() は vi (0<=i<=k) を返す
regular レジスタは quiescently consistent だけど、逆は成り立たない。
safe と regular レジスタは single writer のみ許すと定義した。 regular レジスタは quiescently consistent single-writer sequential レジスタであることに注意。
Fig. 4.3. で、レジスタが
- safe なら
- R1 は 0 を返す
- R2, R3 はレジスタの取り得る値のいずれかを返す
- regular なら
- R1 は 0 を返す
- R2, R3 はそれぞれ 0 か 1 を返す
- SRSW atomic なら
- R1 は 0 を返す
- R2 が 1 を返したら R3 も 1 を返す
- R2 が 0 を返したら R3 も 0 か 1 を返す
Fig. 4.4 はレジスタの３次元の概念図。
- レジスタのサイズ
- readers, writers の数
- 一貫性のタイプ
multi-writer safe レジスタのような定義に無意味な組み合わせも含まれているので鵜呑みにしちゃだめ。
regular, atomic レジスタの実装を論じるために、オブジェクトヒストリーの観点で表現すると便利。 read() の結果は write() が書いた値を返す（regular, atomic レジスタでは read() が返り値を作らない） ヒストリーでのみ考える。
(Chapter 3 の復習は省略)
どのレジスタ実装も write() の total order ( write order ) を定義。
safe, regular レジスタは一度に一つの writer しかアクセスできないので write order は明らか。
atomic レジスタは linearization order。
この順番を使って、write に番号を付ける（W0 が最初、W1 がその次など）。
safe, regular レジスタに対する SRSW, MRSW の write order は precedence order と一致。
Ri は Wi で書かれた vi を返す read 呼び出し。 Wi はヒストリーで一つだが、Ri は複数存在できる。
regular レジスタの条件
- (4.1.1) 未来の値を返す read は存在しない
- (4.1.2) 離れた過去の値を返す read は存在しない
atomic レジスタの条件（regular に加えて）
- (4.1.3) 前の read は、後の read が返す値を返せない
すなわち
Ri → Wi となることはない (4.1.1)
Wi → Wj → Ri となる j は存在しない (4.1.2)
Ri → Rj なら i <= j (4.1.3)
レジスタ実装が regular であることを示すには、ヒストリーが 4.1.1 と 4.1.2 を証明する必要がある。 レジスタ実装が atomic であることを示すには、write order を定義し、4.1.1 〜 4.1.3 を示す。