http://www.amazon.co.jp/dp/1608452352
を読んで自分の気になった所を読みながらメモした物を置いておく。抄訳ほどすら訳していない。
発表のプロットに使うまとめ。論文の参照番号がそのまま埋め込まれてるのは酷いのでそのうち直すかも。気になる人は本を買ってください。
あまりに乱雑に書いてある&&Markdown記法なので読むに耐えないかも…。
## 並行制御
ロックのタイミング。
衝突頻度が高いほどPessimisiticの方が性能が出るが、衝突頻度が低い場合はOptimisticのほうが速い事が多い。
### Pessimistic
アクセス時にロックする。デッドロックに気をつける必要がある。
### Optimistic
それ以外。デザインの幅が広い。ライブロックの危険がある。
readにOptimistic、writeにPessimiesicを使う亜種もある。
IOを使ったり、衝突頻度が高いトランザクションを確実に完了させるために`irrevocable`トランザクションという特別なトランザクションを定義してそこにPessimisticを使う研究もされている。(37,300,303,308,333)
## バージョン管理
いつ生データを書き換えるかという戦略。2種類ある。
### Eager
トランザクション中に即座に生データを書き換えてしまう。`direct update`とも言う。
書き換えた元のデータはトランザクションの実行者が`undo-log`としてバックアップしてアボートする際にロールバックする必要がある。
ログを消去するだけで良いのでコミット時の動作が簡単。
writeしたdirtyな値は正しく調停される必要があるのでpessimisticな並行制御が要求される。
### Lazy
コミット時にデータを書き換える。`deferred update`とも言う。
書き込みは自身の`redo-log`に行い、直接書き込みはしない。
コミット時にすべて目的の場所に書き込む必要があるが、アボートはログを消去するだけで良いので簡単。
## 衝突検知
どの瞬間に衝突を検知するか。
Pessimisticな並行制御を行っているうちは衝突検知はロックによって自明に行われるためさほど選択肢に幅はない。
Optimisticならば、衝突を検知できる`validation`操作がどの瞬間に実行されるかによって設計上の選択肢がいくつもある。
3次元に直交する境界で分類できる。
### 粒度
HTMであればキャッシュラインを衝突検知の粒度、STMならオブジェクトの粒度で扱う。
False Sharingのように実際に衝突していなくても衝突として誤検知してしまう現象(`false conflict`)はHTM, STMの両方で起きうる。
それを避けるための`value-based validation`という方法も提案されている。
### タイミング
データに初回アクセスした瞬間にチェックする`eager conflict detection`手法(227)
データに二回目以降アクセスする際にも適宜何度もチェックする手法。
コミットを行う瞬間にだけチェックする`lazy conflict detection`手法。
### どの種類のアクセスを衝突として扱うか
#### tentative
コミット前であってもread-write write-writeが衝突したらコミット前であってもconflictとして扱う。Eagerな機構のトランザクションでよく見られる。
#### commited
実行中のトランザクションの衝突はconflictとして扱わずコミット時にだけconflictとして扱う。Lazyな機構のトランザクションでよく見られる。
write-writeとread-writeの衝突時で別の戦略を使う戦略が提案されている。
# セマンティクス
トランザクション同士の並行性とトランザクション内のオペレーション同士の並行性は別で考えるべき。
トランザクション内での動作がどの値を読むべきかについては`sequential semantics`(282)が詳しい。
## データベースでの基準
ACID特性は有名であるが、DurabilityだけはSTMに関しては要らないとよく言われる。何を持ってしてDurableと呼ぶかに関しても人によって意見が別れる。
### serializability
`serializability`とは、複数のトランザクションが最終的に生成する結果が、何らかの順序で逐次実行されたかのような結果を残すこと。
しかし逐次実行の結果が現実の実行順序と乖離していても`serializability`の要件を満たしている事に気をつける事。
トランザクション1を完了した後にトランザクション2を実行して、最終的な実行順序が2->1になっていようとも`serializability`の要件を満たす。
#### Strict Serializability
2つのトランザクション間で、2の開始が1の完了より後なら、`serialize`された実行順序は1->2の順にならなくてはダメ、という要件。
#### Linearizability
トランザクションの開始から終了までのどこかの一点で処理全体が開始&完了したかのように見える、という要件。
とても自明で明快そうな基準に見えるけれど、このモデルは衝突によってアボートするモデルへとマッピングはできない。
なぜなら処理全体が一瞬で完了したかのように見えるのならばそもそも衝突によるアボートが発生しえないからだ。
（自動でリトライするセマンティクスであれば問題ない、と言っているように見える）
#### Snapshot Isolation
データベースでは一般的であるけれど、ボトルネックの箇所がDBとは違うため必ずしも良いとは限らない。研究は(263)にある。
```
x = y = 0;
tx { x = x + y + 1 }
ty { y = x + y + 1 }
```
が、serializableであれば{x=1, y=2}もしくは{x=2, y=1}の結果しか残らないが`Snapshot Isolation`では{x=1, y=1}という結果になりうる。(Write Skewだね)
今の所大きなパフォーマンスのアドバンテージがあるように見えないのであまり研究されていないが今後とても速い実装が出てきたら変わるかも知れない。
もしくは分散実行やらマルチプロセッサでのトランザクションになった時にはコミュニケーションコストが大きくなるので有効になるかも知れない。
`z-linearizability`という基準も定義されている。
大きいトランザクションと小さいトランザクションが並走する環境において並列度が向上する。
すべてのトランザクションにSerializableを要求するが、その中の指定された一部のトランザクションにだけLinearizableを要求する。
長いトランザクションは一つのそのような集合を構成し、短いトランザクションも複数で一つの集合を構成する。(260)
### 実行中のトランザクションの一貫性
データベースでのトランザクションの正当性基準は良い参考にはなるが、そこだけでは足りない課題もSTMにはある。
ここまではずっと「コミットされたトランザクションの挙動」についてしか話してこなかったが、実行中のトランザクションの挙動については定義してない。
簡単にいうと「そのトランザクションが最終的にabortするなら、そこまでの過程でどんな腐った値をReadTxに返却してやっても構わないというのか？」ということ。
データベースではトランザクションを経由していようがしていまいがデータへのすべてのアクセスを仲介していたが、プログラミングではデータに触る際にトランザクションを使わない場合もありうる。
トランザクション経由と非トランザクションのアクセスはどのようにlinearizeされるべきか？
#### 読み出しの非一貫性とIncremental Validation
Eagerなバージョン管理とLazyな衝突検知において、Read Skewすると無限ループやSegment違反などが起こりうる。
型安全な言語であってもトランザクションで守られていない場所にトランザクションでアクセスした場合には何が起こるかわからない。
無限ループするとそもそもValidationが発生しないため永久に検知できない。これをゾンビトランザクションと呼ぶ。
これを回避するためにはプログラマが明示的にバリデーションをループ中で指示する事によって、過去に読んだ値が今も正当かどうかを確認する手法が考えられる。
これは`Incremental Validation`と呼ばれる手法だが、いくつか問題がある。
まずそれぞれのアクセス毎にValidationしていたらO(n^2)のコストが掛かりろくな性能が出ない。
次に、更新のタイミングがLazyなものとEagerなものとで適切なValidationのタイミングが変わってしまう。
そのため両方のトランザクションシステムで満足に動くようなポータブルな記述にならない。
#### Opacity
`Opacity`という概念が提唱されている。(125)
これは`Strict Serializability`に加えてトランザクションがabortする場合であっても何らかの逐次順序で実行しているかのように見えなくてはならないという定義である。
これをサポートするトランザクショナルメモリは、トランザクションのどの時点においても一貫性のあるread-setを読んでいる事を保証しなくてはならない。
TL2などのSTMはグローバルクロックを用いる事でOpacityを提供する。
HTMはOpacityを提供しており、そうでなくともwriteはすべてトランザクションの中に閉じるので問題ない。
Opaityとserializabilityの関係及びその間にある一貫性(Virtual World Consisteny)については(163)が詳しい。
### モードを混在させたアクセス
トランザクションの外からデータに触った際にまともに動くのが`Strong Isolation`なトランザクション。まともに動かないものは`Weak Isolation`。
Weakなトランザクションは多くの問題がある。
まずトランザクションと非トランザクションな処理の間でデータレースが発生した場合の挙動が不定であること。
次に粒度の問題で、トランザクションによって管理されているデータの粒度がプログラム中よりも荒い場合。
3つ目がOpacityがない場合のゾンビトランザクションの問題。
最後が`privatization`や`publiation`イディオムを使った問題。特にこれはTMがOpacityを提供していようが関係無いという点で厄介。
weakなトランザクションの問題は数多く研究されており、(35,36,288,115,219,220,3,226)あたりが詳しい。
あまりにいろんな問題ありそうなケースが出るし、すべての入力に対してそもそもTMがどのように振る舞うべきかについても全員が合意できているわけでもない。
更にはこれらのケースすべての他にもまだ別の問題が無いとも限らない。なのでこれらのケースそれぞれに個別に対応するよりは体系立てて考えていく事にする。
#### Lock-basedな調停でも発生するanomaly
`non-repeatable read` anomly: トランザクションが一度読んだ値をトランザクション外から書き換えられた場合、トランザクション側がバッファしていない限り狂った値を読む事になる
`intermediate los update` anomaly: トランザクションがread-modify-writeする間にトランザクション外から書き込みを割り込ませた場合、トランザクション側も気づかないうちにデータを上書きしてぶっ壊す
`intermediate dirty read` anomaly: Eagerな場合そのままターゲットのアドレスに書き込んでしまうため、トランザクション外から読みだした場合にdirtyな値を読んで死ぬ。
#### 書き込み粒度が粗い事によるanomaly
xとyが同一のワードに載ったそれぞれ2バイトの変数だったとして、トランザクションの中でxだけを書き換えるとトランザクションの外でyを使ったコードが動いていた場合つられて壊れる。
バージョン管理がlazyだったら、xに対するコミット時の更新がついでにyの値も書き換えてしまう。
バージョン管理がeagerだったら、xがロールバックする際にやっぱりyの値をredo-logを用いてわざわざ壊してしまう。
`granular lost update`と名付けられたこの問題は、トランザクション内で扱うデータの場所をビットマップを用いるなどしてより細粒度で管理してやることで回避できる。
#### ゾンビトランザクションによるanomaly
ゾンビトランザクションが思わぬ場所にtransactionalなwriteを行ってeagerに更新しているものを非トランザクションスレッドが読みだすと不味い。
本来ならばどこにも存在しないはずの値を読んでしまう。これを`speculative dirty read`と呼ぶ。
もし他の非トランザクションが書き換えたデータにゾンビトランザクションが書き換え、そこからabort時にundo-logから書き戻すと非トランザクションの書き換え結果を壊す事になる。これを`speculative lost update`と呼ぶ。
#### privatizationとpublicationの問題
```
// トランザクションA
do {
StartTx();
x_is_public = false;
} while(!CommitTx());
x = 100;
```
と
```
// トランザクションB
do {
StartTx()
if (x_is_public) { x = 200; }
} while(!CommitTx());
```
が衝突した場合、どういう実行順序でもx=100という結果が残ったはず。
これはロックを用いていた場合であれば問題なく動いていたであろう事に注意して欲しい。つまりSTMを普通に使うユーザが普通に書きうるコードであるということ。
これを`weak isolation`で`commit-time conflict detection`で`eager version management`で動かすと
1, Bがコミット直前まで進める（xに200を書き込んで、x=0のundo-logを持つ）
2, Aがトランザクションを全部終わらせてxに100を書き込む。
3, BがAに先行された事に気づいてロールバックする
4, x=0にundoするのでx=0という結果が残る
という異常状態が残る。
仮にこれが`lazy version management`だった場合は、トランザクションBのコミット時のx=200の生書き込み操作と、トランザクションAの直後のx=100がデータレースして死ぬ。
これに限らず、lazyなトランザクションの結果反映操作のタイミングのズレや、eagerなトランザクションのロールバック直前状態などの遅れは`delayed cleanup problem`と呼ばれている。
更には書き戻しの順番もトランザクション内と同一とは限らない。これを`memory inconsistency`と呼ぶ。
```
// Thread A
x = 42
do {
StartTx();
WriteTx(&x_is_shared, true);
} while(!CommitTx());
```
と
```
// Thread B
do {
if (x_is_shared) {
// use x
}
} while(!CommitTx())
```
このコードも、xとx\_is\_sharedの順序関係がコンパイラやCPUに適切に扱われなかった場合に問題になりうる。
フラグより先に投機的にxを読んだ値をそのまま使ってしまう事がありうるから。
これに関係して`granular inconsistent read`問題も指摘されている。
例えばThread Bがxに触る前にyに触っていて、しかもxとyが同じワードに乗っていた場合、xの値を意図せずしてプリフェッチしてトランザクションのバッファに押し込む。
これによって本来期待していたよりも速い順序でxを読みだしてしまう。
#### 議論
`Weak Isolation`がいかにオワコンかわかったと思う。
多くのHTMが提供しているようにSTMも`Strong Isolation`な挙動で動くべきだし、多くの研究がその方向へなされている(5,155,281,288)。
`Storong Isolation`なトランザクションであっても、その反映順序がプログラムオーダーと一致していないとフラグ変数の読み書きで非トランザクションなアクセスとメモリバリアに起因するような異常アクセスを起こしうる。
```
do {
StartTx();
WriteTx(&data, 42);
WriteTx(&ready, true);
} while (!CommitTx());
```
```
if (ready) {
// use data
}
```
このようなコードも、トランザクション側がdataとreadyの反映順序を間違えたら死ぬ。
メモリバリアの問題ならdata, readyの両方がvolatileであれば解決する問題ではあるが、言語のメモリモデルとトランザクションのメモリモデルは切って離せない関係にある。
### ロックベースのモデリング
これから無限に出てくるかも知れない個々のコーナーケースについて扱うより、セマンティクスを定義する方が良い。
その一つ目が、`lock-based model`というモノで、トランザクションがあたかもロックに基づいて動いているかのように動作を規定するものだ。
つまり、トランザクションの開始・終了をロックの取得・開放に置き換えた時に動くかどうかで動作を決定する。
#### Single-Lock Atomicity
`single-lock atomicity(SLA)`とは「トランザクションがまるで単一のロックで守られていたらどう動くか」によって規定する動作モデル。
ロックそのものは既に現実世界で広く使われているため、その実用性に疑いの余地がない点で魅力的に見える。
データレースについても、ロック版eeeeでデータレースが起こっている場合に限りデータレースが発生する事に絞れば対象ケースを制限できる。
しかしいくつか問題もある。
1, トランザクションのセマンティクスをロックと同じにするのは自明ではない。特にロックに存在しない特徴（故意のアボートや条件の同期やネスト）のマッピングは難しい。
2, 直感に沿わせる事が難しい。もしロックの中で故意に無限ループするなどでわざと並列度を下げるようなコードを書いた場合、これをTMで実行するのは完全に結果を変えてしまう(202)。
3, 空トランザクションをメモリバリア代わりに使われた場合（Empty Publicationパターン）、データの衝突が無くてもトランザクションの前後関係を守ってやる必要があって無理ゲー(219)
#### Disjoint Lock Atomicity
`disjoint lock atomicity(DLA)`という、また別のロックベースモデルも定義されている(219)。
これは`SLA`を緩和したモノである。
トランザクション開始時に、トランザクション中でアクセスするすべてのオブジェクトのロックを獲得したかのように見えるという一貫性である。
Empty Publicationイディオムは明確にサポートされない。
Racy Publicationイディオムはサポートされる。
だが実際の所、走らせてみないとどのオブジェクトに触るかどうかは確定しないため、将来アクセスするデータがすべて予見できる場合でしかロックで同等の処理を作る事はできない。
だからSTM利用時と等価なロック実装というものが作れなくて完全とは言えない。
#### Asymmetric Lock Atomicity
`asynmmetric lock atomicity(ALA)`というDLAを更に緩めたロックベースモデルも定義されている(219)。
これはトランザクション内で初めてwriteアクセスをする際にやっとそのオブジェクトのwriteロックを取るというモデル。
ALAはすべての読みだすデータに対して排他的アクセス権があることを保証するため、Racy Publicationイディオムをサポートする。
#### Encounter-time Lock Atomicity
`encounter-time lock atomicity(ELA)`とはALAを更に緩めたモノで、すべてのアクセスするデータに対して初めてアクセスするときにやっとそのwriteロックを取るというモデル。
これは読み出しがif文を追い抜くタイプのコンパイル時最適化さえ抑制できればRacy Publicationイディオムをサポートできる。
### Lockをベースにしない並行動作モデリング
`Transactional Sequential Consistency(TSC)`
shared memoryアーキテクチャの上でどのようなセマンティクスを提供するべきかという観点の上で考えられたモノ(187)
あたかも命令を発行した順番に即座に読み書きが行われたかのように見える(76)。
トランザクション内での操作は順序反転せず、トランザクション内の操作は何らかの順序でインターリーブせずに実行したかのように見える。
順序に基づくセマンティクスに基づいて設計された（299, 115）
これは`strong isolation`より強い特性である。なぜならstrong isolationはコンパイル時にどのようなリオーダが行われるかについて規定していないからだ。
そのような不可分な構造を提供するプログラム言語レベルでのnotionを定義する試みもある(3, 226)
実用上SequenitalConsistenyやTSCはすべてのプログラマでサポートされない。
その代わりに、`race-freedom`という定義と組み合わせて使わる事が多い。
`race-free`ならばそのプログラムはSCやTSCで実装されているという事になる。
SLAでデータレースがハンドリングされている時にプログラムが`race-free`でないなら、より弱い保証でサポートされているか保証が無いかだ。
`race-free`であるかどうかという基準はSC上で実行したという仮説に基づいて定義されるべきだと主張されている（10）
このタイプのモデルはプログラマ中心である。なぜなら特定のプロセッサのメモリシステムに依らないSCという慣れ親しんだ理論に基づいた定義だからだ。
これがプログラマと実装の間の契約となるという効果がある
TSCを使ってトランザクションのプログラムをモデリングした場合、どのプログラムの集合がrace-freeであると判断されるかどうかが正確に問題となる。
どんなプログラムがrace-freeとなるか3つの基準が研究されてきた。`static separation``dynamic separation``data-race freedom`である。
#### `static separation`
すべてのmutableな場所が「常にトランザクションでアクセスされる」もしくは「常に非トランザクションでアクセスされる」分けられるプログラミング制約のことを`static separation`と呼ぶ。
プログラマはプログラムを「immutableな場所」「スレッドローカルで共有しない場所」「トランザクションでしか触らない所」に分ける事で`race free`を達成する。
この場合もちろんprivatizingやpublicationのidiomは使用できない。
この`static separation`に従うプログラムは`strong isolation`でも`weak isolation`でも区別ができなくなる。
これはTMの実装者にしてみればだいぶ大きな柔軟性を提供する。
しかも、プログラムの静的解析によってプログラムがrace-freeかどうかを判断できるようになる。この観点での正式な議論は(3, 226)に詳しい。
型による保護の確認というのは的確なツールたりうる。例えばトランザクショナルとしてマーキングされた型にしかトランザクション中ではアクセスできない、など。
その方法はSTM-Haskell（136）で実装されている。
Haskellではほとんどのデータはimmutableなのでプログラムをtransactionalとnon-transactionalへと効率的に分ける事ができる。
この分離は、non-transactionで作ったデータをtransactinに渡したり、transactionの結果をIOなどに渡すなどをしたい際にアーキテクチャを複雑化する。
これを解決するにはトランザクションと非トランザクションを行き来する際にマーシャライズするか、そこら中でトランザクションを使うしかない。
前者は患わしいし、後者は遅すぎて使い物にならない。(284)
#### `dynamic separation`
プログラムのheapをトランザクションと非トランザクションに分離して、さらに二つのセクション間をデータを跨らせる手順を提供する。
これは`static separation`のとっつきにくさを解消するし、TMの実装にもそれなりに柔軟性を提供する。
たとえばlazyなconflict detectionでeagerなversion managementで`dynamic separation`を実装した物がある(1,2)
直感的にはトランザクション内ですべてのアクセス対象のデータがトランザクションヒープの中に入っているかどうかをチェックするだけでよい。
こうすることによってeagerなupdateがzombie内でトランザクションで保護されていないデータにアクセスすることを回避させることができる。
HaskellのSTMのようにread-onlyなトランザクションをアクセスする亜種もある。
`dynamic separation`の欠点はコンパイル時のチェックでrace-freeかどうかを判定できないことだ。
データがスレッドローカルなのかスレッド間共有なのかを動的にトラッキングするアイデアがある（189）
read-writeはアクセサメソッドで扱われる。それらのメソッドはスレッドローカルなら直接アクセスし、トランザクショナルならトランザクションでアクセスする。
それぞれのオブジェクトに共有なのかスレッドローカルなのかをフラグを持たせる、グローバルな変数がスレッドローカルな値をポイントした際に共有データへと遷移する。
strong isolationのトランザクションを高速化するアイデアでも似たような物が出ている（288）
#### `Transational Data-Race-Freedom`
（76）で定義されているのが、`Transactional Data-race freedom(TDRF)`である。
TRDFなプログラムはデータレースが起きない、さらにトランザクショナルデータレースも起きない。
トランザクショナルデータレースを`violation`と呼び、そのようなレースがない状態を`violation-free`と定義した（3）
TDRFはその`violation-free`よりも強い保証である、なぜなら非トランザクショナルなデータレースも起きないのだから。
TDRFはTSCの振る舞いの元に定義されており、特定の実装に依らない。
したがってゾンビトランザクションでしか発生しないアクセスはデータレースとして考えられず、メモリの隣の番地にアクセスすることもない。
`write granularity`や`zombie transaction`や`privatization and publication`はTDRFである。
`racy publication`や`empty publication`はTDRFではない。
いろいろな基準が出てきたが、何らかの基準を定めることでトランザクションの実装者と利用者の間でインタフェースが生まれるため、実装の差し替えなども容易になりポータブルな物が出来上がるという点で有益であり、未だどれが一番良いのか結論は出ていない。
### Nest
さまざまな研究がなされていろい、並行性・マルチスレッド・トランザクションを組み合わせたリッチなシステムの調査などがある（128）
`linear nesting`(229)を対象に考慮する。
- `Flattened Nesting` 最外周のトランザクションに内部のトランザクションを合成する方法。内側トランザクションでアボートした際に外側まで全部ロールバックする。実装は簡単。
- `Closed Nesting` アボート時に内側トランザクションだけロールバックするもの。アボートしない限りは`Flattened Nesting`と全く同じ挙動をする。ロールバックが多い時にはこっちが速いが、アボートが少ない限り動的に`Flattened`を選択する高速化はありうる。
- `Open Nesting` トランザクション中でのトランザクションは、一旦コミットしたら仮に外周のトランザクションがアボートしても残り続けるタイプ(231)。利用にかなり深い注意を要する、例えば外側のトランザクションの未コミットの値を内側のトランザクションが読んで、内側のトランザクションだけがコミットしたらどうなってしまうのか。`open nesting`を実装したトランザクションの参照モデルは(229)にある。
また`open nesting`に似た概念として`pause`というものも提案されている(346)。これはトランザクション中に突然トランザクションを辞めて、普通の処理を行い、トランザクションを途中から続けるというものである。
`Parallel Nesting` 親トランザクションの中で複数の子トランザクションが並列に走るパターンになると一気に問題は難しくなる。
OpenMPとSTMの組み合わせも研究されている（25,225,323）トランザクションが複数のスレッドを持っていてその中でさらにトランザクションが無い場合に`shallow`とよび、トランザクションがあるものを`deep`とよんで区別した(323)そして`herarchical lock atomicity`というセマンティクスを定義した。
（44ページ付近なんだけどあんまり興味ないから飛ばす）
実装について
-----------------
# はじめに
ハードウェアサポートなしでSTMがどこまで行けるかはわかっていない。
しかしSTMが優れている理由はいくつかある。
- 実装の幅が広い
- ハードウェアに手を加えなくても差し替え可能
- 言語実装特有の機能と組み合わせやすい（GCとか）
- キャッシュサイズなどの物理的制約がない
ぶっちゃけSTMの研究分野は矛盾する要求や様々なケースに対応するために複雑になっている。
その業界を反映して、これからまとめる内容も大きく分けて4つの実装技術に関して議論する。
そのそれぞれが最先端のSTMで使われているものであり、それらの中での選択がSTMの設計の基盤を表現すると言える。
1つ目は`versioned lock`である。
書く側のトランザクションがロックとバージョン番号を操作することによって、読む側のトランザクションが競合を検知するためのものである。
典型的な設定としてはMcRT-STM(7, 274)とBatrok-STM(138)がこれを利用している。
衝突のないトランザクションのオーバーヘッドを減らすために開発された。
例えば`eager version management`とTMの操作の配置を最適化する静的解析などに使う。
2つ目は`global clock`である。
それはオブジェクトごとのSTMメタデータにそっている。
これらのテクニックはSTMにOpaityを容易に提供するために使われている。
TL2（83）でこのテクニックは有名になった。
その基本的なデザインとスケーラビリティと並列度を改善する拡張について議論する。
3つ目として、オブジェクトごとのメタデータと固定サイズのグローバルな状態を衝突検知に用いる寄港について検討する。
グローバルなメタデータはスケーラビリティの面に置いて難があるように見えるかもしれないが、しかしこれは完全に適切である。
Niagara2 CMPではスレッドは同一のチップに乗ってキャッシュを共有しているため、メタデータは関係するスレッドの間で共有される。
異なるケースではSTM実装の簡略化はワークロードによっては何らかのロスを相殺する事がある。
JudoSTM(236)やRingSTM(305)やNOrecSTM(77)はグローバルメタデータの良い例である。
4つ目として、ノンブロッキングなシステムについて議論する。
中にはブロッキングとノンブロッキングの混合のような亜種もある。
最近のノンブロキング実装では、(208, 313, 314)は強い進行保証を保持するためにフォールバックメカニズムを用意している。
もちろんここに書かれていることが全てではなく、他にもIsolationやらirrevocabilityや条件の同期などやることはいっぱいある。
それらのテクニックにも4.6章で議論する。
4.7章は分散したクラスタマシン内を跨るトランザクションに付いて、4.8章ではSTMの正しさを検証するモデルチェッキングについての研究を紹介する。
# ログとメタデータの管理
## メタデータの管理
大きく分けて2つのアプローチがある
- `object-based STM`ではメタデータはそれぞれのオブジェクトに取り付けられる。これは実際のオブジェクトかも知れないし、ただのメモリかもしれない。
- オブジェクト内のすべてのフィールドは幾らかのメタデータと関係性がある。
- オブジェクトはメモリ内の表現においてメタデータ分だけサイズが余分に必要になる。
- `word-based STM`ではメタデータはそれぞれのメモリアドレスと関連付けられる。いくつかの選択肢がある。
- メタデータとメモリアドレスと1-1対応付ける方法
- データのアドレスをハッシュに掛けて固定サイズのメタデータに割りつける方法
- もしくはプロセス全体で一つのメタデータしか持たない方法
これらのアプローチを比較する観点は
- メモリ消費量
- メタデータへのアクセス速度
- `false conflict`の発生頻度
メタデータの量が少なくなると`false conflict`が起きる頻度が高まる(348)。
セカンドチャンスという手法によって`false conflict`の影響を減らす方法などが研究されている(4.4章)
メモリアドレスからメタデータへのマッピングの計算オーバーヘッドは簡単なマッピング関数を使う事で削減できる。
いくつかのword-basedなSTMはモジュロを使ってアドレスをメタデータへと割り付けている。
object-basedなSTMではオブジェクトにアクセスする際に容易にメタデータにアクセスできる。
オブジェクトのヘッダを発見するためのアドレス計算が入るともう少し複雑になりうる、そういう場合ではオブジェクトの先頭にポインタを向ける機構を要求する。
例えばsegregated heap(327)のように、プログラムがオブジェクトのヘッダアドレスが可能なように変更するか、ヘッダへの内部的なポインタをテーブル化する。
オブジェクトのヘッダにメタデータを置くことの利点は3つある。
- キャッシュラインに乗る。そのためトータルで触るキャッシュラインが減る
- 単一オブジェクトの異なるフィールドに対するアクセスも一つのメタデータに入る
- オブジェクト単位で管理することで衝突が明示的になる（word-baseでhash関数使ってると知らないうちに衝突する）
欠点は2つある。
- 複数のトランザクションによる同一のオブジェクトの異なるフィールドへのアクセスが衝突する。配列等の場合各要素は独立しているし、配列そのもののメタデータに触れたい時もあってもうダメだ。
- メモリマネジメントシステムと密結合になること（83, 162）オブジェクトが開放されたり再利用されたりするときに必要である。そして古いロケーションはゾンビトランザクションによってアクセスされるかもしれない。
ハイブリッドなアプローチもある。リードオンリーな物にはより簡単なメタデータを利用し、大きなオブジェクトや配列にはword-basedな物を使う、など（261, 265）
多くの言語処理系はオブジェクトにヘッダ情報をつけている。また、それぞれのオブジェクト複数のワードのためにそれぞれの領域を確保するのではなく、ヘッダ情報をシェアすることもよくある(12)
図4.2はBartokSTMのアプローチである(138)
# 4.2.3 opacityの提供
McRT-STMやBartok-STMは`invisible read`という特徴がある。
同一データに対して読み出し側のトランザクションが居るかどうかが書き込み側のトランザクションからは感知できない。
これはトランザクションの衝突を許し、ゾンビトランザクションとして実行され続ける恐れがある。端的に言うとこれは`Opacity`を提供していない。
Opaityの実現方法は以前にも書いたが`Incremental Validiton`を行う事で実現できる。しかしこれは非常に負荷が高いO(n^2)である。
`Incremental Validation`を避けるなら、そもそも`invisible read`を避けて明示的にread-setを外から見えるようにするという手もある。
これはread操作そのものがvisibilityのためにwriteを行うためパフォーマンスボトルネックになりやすい。
それはMcRT-STMの亜種やRSTMなどで実現されているが、一般にこちらもコストが高い事で有名である（274）。
それ以外の手として、Global clockを使う手があり、STMの界隈ではよく使われている。
とはいえGlobal Clockに頼らずに`Incremental Validation`のコストを低減化する方法はいくつか提案されている。
## global commit ounter
最後にそのデータを読んでから他のトランザクションがコミットした場合にしかValidationが必要ないという事実(302)から、`global commit counter`という考え方が生まれた。
lazy version managementの時にコミットの瞬間で共通のカウンタをインクリメントする手法である。
これを用いて他のトランザクションは前回のvalidationからカウンターが変動した場合に限りvalidationを行うという方法である。
これは簡単にそこそこの性能が得られるが、全く衝突のないトランザクションのコミットに対してもvalidationを行ってしまい効率的ではない。
## semi visible read
(188, 191)で提案されているのが`semi-visible reading`である。
これはwriterがreaderの所在を観測できるが、どのreaderが呼んでいるかはわからないというものである。
それはSNZIを用いる。
writerが書き換える値のSNZIの値が0でない事を観測した場合に限り、コミット時に`global commit counter`をインクリメントする。
これによって、トランザクションが衝突した場合に限りvalidationが走るのでただの`global commit counter`技法よりも効率的になる。
## discussion
これらの方法は
- Opacityがない
- 非トランザクショナルアクセスと協調できない。
- Privatization Idiomが使えない
という欠点がある。もし言語仕様からそれを要求された場合、STMのインタフェースの上でそれを提供する必要がある。
(せせこましい議論なので省略)
99やら154やら。
# Global Clock
TL2(83)とこれまで追ってきたMcRT-STM/Bartok-STMの違いはOpaityを提供するか否かである。
TL2はincremental validationを行う事無くOpacityを提供する。
4.3.1ではTL2のアルゴリズムを、4.3.2ではさらなる並行性を提供する`timebase extention`について説明する。
4.3.3では`global clock`内でのcontentionの問題を改善する技法に付いて説明する。
## TL2
TL2はバージョンドロックを使う。それはタイムスタンプの値か、そのデータを保持するトランザクションを指し示す。
TL2は`lazy version management`を使う。そのためアップデートは`redo-log`に記録され、`commit-time-locking`を用いてアップデートされる。
ロックはトランザクションのコミット関数の中でのみ獲得される。
そしてバージョンドロックに加えてグローバルなクロックを持つ。それはただの64bitの共有カウンタかもしれない。トランザクションがコミットされるたびにインクリメントされる。
すべてのトランザクションはトランザクション開始時にグローバルクロックを読む。
このタイムスタンプは`read-version`として知られる。
そしてそれぞれのトランザクションは`write-version`という固有の値も割り振られる。コミット操作の一部として。
これは逐次順序でのトランザクションの位置を定義するために使われる。
それぞれのオブジェクトが保持するバージョン番号は、最後にそのオブジェクトにコミットしたトランザクションの`write-version`を保持する。
読み出す歳に
```
v1 = obj.timestamp;
result = obj[offset];
v2 = obj.timestamp;
```
のように2度読みした後、lockBitの確認、2度読み間でのskewやそのトランザクションの`read-version`との大小比較を経てvalidationを行う。
この`read-version`の比較1回によって`Opacity`の保証ができる。
writeはもっと簡単で、普通にredo-logに無いことを確認してからredo-logに書き足すだけである。
コミットの際は、全部のwritesetのロックを取る→`write-vesion`を獲得→read-setをvalidationする(ロックされていない事も確認する必要がある)→redo-logから書き込む→`write-version`を設定してからアンロック、の順で操作を行う。
### 最適化
いくつかの最適化が考えられる
#### read-only
読み出ししかしないトランザクションならvalidationだけで話が済む
#### adjacent transactions by the same thread
`write-version`が`read-version`と1しか違わないなら他のスレッドが間に挟まってないのでread-setのvaridationが不要になる。
#### 階層ロック
保護対象のメモリをセグメントに分けて、それぞれのセグメントに行われたコミットの回数をカウントする配列を作る。
トランザクションはセグメント毎にread-writeのマスクパターンを保持し、初回読み出し時には関連するカウンターを記録する。
カウンタがコミット時までにインクリメントされていなかったらその部分のチェックをパスできる。
#### Eager Version Management
(103, 327)ではTL2のEager版について説明している。
Encounter-Time-Lockingで動くが、アボート時にもバージョン番号を更新しなくてはならない。
そうしないと、ReadTxがアボート前にv1を読む→アボート後にv2を読む→ReadTxがダーティな値を読むという流れを観測できない。
しかしこれだと競合が多い時にダーティな値を実際に読んだわけでもないのにReadTxがアボートしてしまい効率的でない。
この問題に対処するためにFelberらは`incarnation number`というメタデータを個々のオブジェクトに取り付けた。
アボートされたトランザクションはその`incarnation number`をインクリメントする一方でバージョン番号を増やさない。
ReadTxはその`incarnation number`を確認する。
（よく意味がわからない）
#### バージョン番号のオーバーフロー
2^64回のカウントが過ぎたらどうするのかについて、実用的というよりは理論的な意味での興味はある。
(103)によると、インクリメント時にオーバーフローを検知したら現在のトランザクションをAbort()させ、他のすべてのトランザクションの完了を待ち、すべてのバージョン番号を書き換えて回る。
これは競合のないトランザクションのアボートさせるが非常に稀なイベントなため問題ない。
#### メモリフェンス
TL2はread-before-readのメモリフェンスを要求する。
これはPOWER4などのプロセッサでは結構な負荷となる。
それを減らすための研究もなされている(304)
N個のメモリを読む際に、1回バージョン番号を読んで1回メモリフェンスして1回データを読んで1回メモリフェンスして1回バージョン番号を読む、という操作をN回やる代わりに
N回バージョン番号を読んで、1回メモリフェンスして、N回データを読んで、1回メモリフェンスして、N回バージョン番号を読む、という感じにバッチ化する。
### 時間ベースの拡張
TL2はOpcityを提供するが、偽陰性があるパターンがある
```
// Thread1
StartTx()
// ☆
r = ReadTx(&x)
````
の☆の部分に
```
// Thread2
StartTx()
WriteTx(&x, 42)
CommitTx()
```
が入ると、Thread1はそのケースの場合その読んだ42をそのまま使っても問題ないにも関わらずAbortする。
これに対応する改良も提案されている(264)
この手法はTL2っぽいSTMたちに適用可能である(327, 342, 300)。
ReadTxで読みたいオブジェクトのバージョンクロックを持ってくるのではなくて、readで新しい`read-version'`をGlobal Clockから取ってくる。
そして既に存在するread-setの`read-version`とで矛盾がないことを検証して`read-version'`で`read-verision`を置き換える。
先ほどの例で言うと、Thread1は現在のグローバルクロックからバージョンを読んだ後、手元のread-set（空っぽ）と比較して、thread1の`read-version`を0から1に変えて良いと判断できる。
残念なことにこの拡張は`racy publication`イディオムが使用不能になる。
非トランザクションによる書き込みに対して気づくことができなくなるからだ。
何にせよ、トランザクションがどのようなセマンティクスを提供するかを考えて注意深く設計しなくてはならない。
## グローバルクロックのボトルネック解消案
グローバルクロックのアップデートはパフォーマンスに大きな劣化をもたらしかねない。
### (TL2の論文に書いてあった技法)
GlobalClockの中にスレッドIDを埋め込んどいて、自分が前回コミットした事が分かったらインクリメントせず前回の番号を使いまわす。
キャッシュコヒーレンシ上でグローバルカウンタがSステートに落ちる率が高まる。
### スレッドを跨ってタイムスタンプを使いまわす
(83)で提案されている方法でもスレッドIDとタイムスタンプをクロックに埋め込んでおいて、自分の最近のトランザクションのWrite-versionと現在のグローバルクロックとを比較する。
もしwrite-versionとグローバルクロックが異なれば、そのグローバルクロックをインクリメントせず利用する。もし一致していたらインクリメントする。
その代わり、readTx側はバージョン番号が一致した場合にはアボートしなくてはならない。これは偽競合である場合がある。
### 非ユニークタイムスタンプ
タイムスタンプのアップデートに失敗した場合でも何かしらの新しい値になってるはずなので無視する戦略。
複数のトランザクションが次々にvalidateする状況に置いてなら、それらのトランザクションは同一のwrite-versionを共有しても大丈夫。
### false updateの回避
グローバルクロックは、トランザクションのコミット時に検証失敗した際であってもインクリメントされてしまうのは良くないということで改良したのが（342）
### Deferred update
(188)では、writerのバージョン番号は上げるがグローバルクロックのバージョン番号は増やさない（サボる）という手法GV5が提案されている。
その場合バージョン番号がグローバルクロックより大きくなることがある。
readerはそれを見た場合グローバルクロックの方をそのバージョン番号まで増やす。これは不要なアボートを引き起こす事がある。
GV6という1/32の確率でpass on failureを使うという改良もある。
### スレッドローカルタイムスタンプ
グローバルクロックを共有するのではなくて、各スレッドが持ち、バージョン番号とグローバルクロックの両方にスレッドIDとバージョン番号を埋め込むという方法がある(24)。
各スレッドは過去に観測した自分以外のスレッドのバージョン番号も保持しており、それと比較することで大きくなったかどうかを確認できる。
要するにベクタクロックのような物である。
ReadTxで読んだ値が自分が過去に観測した他スレッドのバージョンより進んでいたらアボートするので、必要のないアボートが起きる事もある。
## グローバルクロック以外の方法
snapshot isolation(263)とlinarizable(264)をサポートしたマルチバージョニングSTMが提案されている。
それぞれのトランザクションはそれは現在のスナップショットが正しいと思われている間のタイムスタンプウィンドウを保持する。
最初にグローバルクロックを読み取ったらタイムウィンドウは[RV, ∞]になる。
この実装では一つの値に対して複数のバージョンを保持して、異なるタイムウィンドウに対してそれぞれ正当である。
そのため、充分な量のバージョンが利用可能であればリードオンリートランザクションは必ずコミット可能になる。
オブジェクトにアクセスする度にタイムウィンドウが狭くなっていく。
オブジェクトの現在のバージョンにアクセスすると、現在のバージョンの正当性は現在のタイムスタンプで近似される。（なぜならいつ利用不能になるかはわからないからだ
re-validationによってタイムウィンドウは拡張される。競合する更新が無い限りは。
linearizabilityを提供するためには、トランザクションのタイムスタンプウィンドウはコミットタイムスタンプを覆うまで拡張されなくてはならない。
SwissTM(93)ではTL2スタイルのグローバルクロックと、二種混合された競合検出とを組み合わせている。
write/write競合はeagerに検知され、read/write競合はコミット時にのみ検出される。（93）
これに適合するために、STMのメタデータはバージョン番号の他に、現在そのオブジェクトを保有しているトランザクションディスクリプタへのポインタを保持している。
Spearらによると(302)これによって、read/write衝突したトランザクションがreaderが先に競合に気づかずにコミットするチャンスを広げる可能性があるようだ。
# グローバルメタデータによるSTMシステム
オブジェクト毎にメタデータを取り付ける事なく、グローバルな共有メタデータと各スレッドのトランザクションディスクリプタのみでSTMを行う方法も研究されている。
これによって細粒度なメタデータによってもキャッシュを逼迫すること無く、実行中やコミット中のトランザクション内でのアトミック命令の使用量も削減できる。
大きく分けて2つのチャレンジがある。
一つ目は、メタデータはすべてのスレッドで共有されるのでメモリ競合を減らすために慎重に設計する必要がある。
ここで解説するシステムでは、アクセス毎にメタデータをアップデートするのではなくトランザクション毎にメタデータをアップデートする。
加えて、JudoSTM(236)やNOrec(77)システムでは、メタデータに対して何の更新も行わずにread-onlyなトランザクションを完遂できる。
二つ目は、トランザクションをシリアルに実行していくよりも、STMシステムは実際のロケーション上で競合をを検知する必要があるという事である。
その点について二つのテクニックについて見ていく。一つ目はブルームフィルターを用いたアクセス箇所のサマライズである。
これによってトランザクションが競合しているか否かを決定できる。
一つ目は値に基づく競合検知である。これはつまり実際の値をトランザクション中にも保持しておき、検証時に生の値と比較するというものである。
## Bloom Filter競合検知
RingSTMはブルームフィルタを`lazy-versioning`における競合検知に導入した（305）
これによってロケーションごとのTMメタデータをヒープに持つ必要が無くなり、read/write-setをスレッドローカルな二つのブルームフィルタに保持する事を可能にした。
RingSTMは時間順に並んだトランザクションのコミット記録のリストを共有している。
それぞれのレコードはコミット時に付与されたトランザクションの論理タイムスタンプとwrite-setのブルームフィルタ、現在のステータス（writing/complete）とプライオリティフィールドを保持する。
writing状態のトランザクションは逐次順序を割り当てられては居るがまだ書き戻しが終わっていないトランザクションであり、complete状態のトランザクションは書き込みが終わったものである。
トランザクションは、リスト内で一番古いwriting状態のトランザクションの論理タイムスタンプを記録することから始める。
トランザクションがトランザクションが走る歳、read-set/write-setのブルームフィルタとredo-logを保持する。
opacityを保証する際にはトランザクションは共有リストが更新された際には他のトランザクションのwrite-setと自分のread-setとを比較して競合を検知する。
(これはグローバルコミットカウントに相当する変更である)
コミットするために、トランザクションは最後にreadを検証し、CAS命令を用いて共有リストへ新エントリとして登録される。
そして書き込みを行ってステータスをCOMPLETEに変える。
`priority`ビットは競合時の繰り返しの再実行を避けるために使われる。スレッドはダミートランザクションをhigh-priorityでコミットして、それによってhigh-priorityでない他のトランザクションを一時的にコミットできないようにする。
コミット記録の物理リストを保持するのではなく、RingSTMは固定サイズのRingリストを用いる。
RingのエントリーはCOMPLETEになるまで保持されなくてはならない。
トランザクションはその開始時間がリング内の一番遅いタイムスタンプよりも遅くなったらアボートしなくてはならない。
もしそうなるとしたら、トランザクションを跨るwrite-setを獲得することができなくなり、正確な競合検知ができなくなるからだ。
投機的実行されたループイタレーションの競合検知に用いられるSTMlite(218)システム
RingSTMのようにアクセスをブルームフィルタでサマライズするが、コミットはセントラルトランザクショナルコミットマネージャー(TCM)によって管理される。
それはsignatureを用いてどのトランザクションがコミットされてよいかを決定する。
TCMからの了承があり次第、スレッドは書き戻しを進める。
TCMが既に異なるデータに対してアクセスすることを保証してくれているため、同期化は不要である。
InvalSTM（112）でもブルームフィルタを使う。
それぞれのトランザクションはvalidフラグを保持して、opacityを保証するためにそれぞれの読み出しの際にvalidフラグを確認する。
コミット時には自分のwritesetのブルームフィルタを他のトランザクションのread/writeブルームフィルタと比較する。
競合した場合にはトランザクションマネージャがどちらをabortもしくはstallさせるかを決定する。
コミットはグローバルロックで逐次化される。
トランザクションのディスクリプタごとのロックは、read/writeセットそれぞれを守るために使われる。
これはread-onlyトランザクションが自信のvalidフラグを見るだけで一貫した値を読んでいるか検知できるので検証が不要になって良いという利点がある。
## 値に基づくvalidation
ブルームフィルタなどを用いずにグローバルメタデータで競合を検知する方法の一つがvalue-basedな方法である。
これはメモリから読んだ値だけに基づいてバージョン番号などを用いずに競合を検知する方法である。
しかし、コミット時に値を検証するだけでは不十分である。
下のような状況の場合やばい
- Xは初めAであった
- T1がAをXから読みだした
- T2がXをBに書き換えてコミットした
- T1がXを再び読みだした、その時にBを読んだ
- T3はXをAに書き換えてコミットした
- T1はread-setを検証し、XにAと書いてあるので検証はパスする。一貫していない値を読んだにも関わらずだ。
### JudoSTM
JudoSTMはトランザクションのリードは常に自分自身のログから読み出す。(236)
そして、トランザクションはその検証とコミットをロックによって直列化する。（そのためT1のアクセスがチェックされている間に他の書き込みは発生しえない）
JudoSTMは二種類のコミットを提供する。一つ目が粗粒度モードで、検証とコミットを一つのバージョンドロックで保護する。
writerはロックを獲得し、検証とコミットをバージョン番号のインクリメント前に行う。
readerはロックを採らずにコミットする。しかしバージョン番号が検証の前後で変わっていない事を確認する。
二つ目が細粒度モードで、個々の場所に対するハッシュ関数で複数のロックを使い分けるという物である。
JudoSTMはTMを使ったC/C++のコードにバイナリ変換を掛けるだけで実現可能であるという点でも新しい。
トランスレータは汎用ログを用いるのではなく特別版のTM命令を生成する。
つまり、アクセスされる場所の数によって検証用のコードをスペシャライズすることができるのだ。
### TMLとNOrec
(77, 307)
ライブロックのないコストの低いファストパスをコミットタイムの競合検知で提供する。
TMLはグローバルなバージョンロックを用いる。これはトランザクションの書き込みをシリアライズするために使われる。
これはwriteトランザクションが走る間保持され、そのためにどの種類のログも必要としない。（それ故ユーザーが明示的にabortを呼ぶことすらできない）
read-onlyなトランザクションは現在のバージョン番号をトランザクション開始時に記録し、読み出しの度にそれを確認する事でopacityを保証する。
readが多い場合にはこのトランザクションは効果的である。
もちろん、シングルロックでログを使わないということは競合検知は相当保守的になる。つまりwriterは他のすべてのトランザクションと衝突する。
NOrecも単一のグローバルバージョンドロックを用いている。しかしTMLと違ってこれはコミット時にしかロックを要求しない。
トランザクションはreadlog(addr, valのペア)と、スナップショットのタイムスタンプ（RV）を持つ。これはトランザクション開始時のグローバルロックのバージョン番号である。
writeはredo-logに書き込む。そして検索を避けるためにハッシュスキームを用いる。
readはもう少し複雑になる
```
int ReadTx(TMDesc tx, int *addr) {
if (tx.writeSet.contains(addr))
return tx.writeSet[addr];
val = *addr;
while (tx.RV != global_clock) {
tx.RV = global_clock;
ValidateTx(tx);
val = *addr;
}
tx.readSet.append(addr, val)
return val;
}
```
このwhileループの中でRVがグローバルクロックとマッチする事を確認する。
もしマッチしなければ、トランザクションは再度検証される。(validateTx関数はグローバルロックが手放されるのを待ってから、redo-log内の(addr,val)のペアが有効化どうかを確認する)
これはOpacityを実現する。そして同一の場所から同一の値を読むことを保証する。
ReadOnlyなトランザクションはコミット時に何もする必要はない、なぜなら毎read毎に一貫性を確認しているからだ。
Writeのあるトランザクションをコミットするには、グローバルロックのバージョン番号は最初に獲得され、トランザクションを再び検証した後でグローバルロックを確保する。
もしこの時にバージョン番号が変化していたら、コミットオペレーションが再実行される。
検証が成功したらトランザクションはredo-logを書き戻してロックを開放し、バージョン番号をインクリメントする。
バージョンドドックの使い方によって、検証がロックなしで行える点に注意して欲しい。
### ハイブリッドなvalue-based validationの使い方
word-baseな手法ではvalue-based validationは`second chance`として利用される事もある。
バージョン番号のチェックで弾かれた場合であっても、value-basedなチェックを用いて期待するバージョン番号をrefreshする事ができる(135)
Dingらはvalue-basedなvalidationはプロセスレベルの仮想メモリを用いて投機的に並列化することができるとした(88)。
(30)
# ノンブロッキングSTM
ノンブロッキング保証や進行保証が欲しい場合にノンブロッキングSTMが必要な事もある。
その中ではすべてのメモリアクセスがアトミックにならなくてはならない。もしCPUが1ワード幅のアトミック命令しか具備していなくても、だ。
まずDSTMについて説明すrう。それは最初のノンブロッキングなSTMだ。
そして次により多くの実装上の洗濯について見ていく。
それによって一つ以上の間接化を追加する手法である。
最終的に間接化なしで行うテクニックを紹介する。
## オブジェクトごとの間接化
(146)ではDynamicSTM(DSTM)が紹介されている。
それはプログラマが前もってトランザクションがアクセスするであろう場所を明示する必要がないというものである。（(285)の手法と違って）
Javaのライブラリとして実装され、プログラミングモデルではatomicブロックではなくて明示的なトランザクションを用いる。
```
class TMObject {
TMObject(Object obj);
Object OpenForReadDSTM();
Object OpenForWriteDSTM();
}
```
// DSTMの仕組みは僕の修論でも書いたぐらいに知ってるので中略
Opacityを提供するにはincremental-validationすればよい。（146）
グローバルコミットカウンタ（302）やvisible readerやsemi-visible reader(188, 191)も利用可能だ。
### ノンブロッキングなSTMのデザインスペース
DSTMは影響力のある初期のSTMだった。
それは
- 動的にオブジェクトをトランザクションディスクリプタと結びつける事でディスクリプタへの単一のアップデートがアトミックな更新となる
- オブジェクトの論理的な内容をメタデータとオブジェクトのスナップショットの観点で定義したこと
- immutableなオブジェクトを用いる事でロック無しでオブジェクトを共有したこと
このタイプのSTMは(278, 122, 105, 106, 209, 211, 302)などにも見られる。
- いつオブジェクトは書き込みのために獲得されるか？
書き込み時にロックを取ってしまえば、コンフリクトがより早期にわかる。
遅延して獲得すれば実際にコミット完了に成った時にだけコンフリクトする。これはlivelockを回避させてくれる。
DSTMはeagerなロック獲得をしている。OSTM(105, 106)はlazyなロック獲得の例である。
両方の選択を適応的に利用するものも提案されている(209)
- readerは可視であるか？
ロックベースなSTMシステムではvisible, invisible, semi-visibleの3つが選択可能である。
Invilible readerはreader同士のメモリ上の競合を無くす。
visible readerは競合マネージャの選択に幅を持たせ、opacityをincremental validationなしに提供する。
オブジェクト毎にvisible-readerを用いた(211)。
bitmap-basedなvisible-readerもある（302）readerが単一のワードの中のビットとして表現される物である。
- オブジェクトがどのようにしてトランザクションから獲得されるか？
TMObjectは他のメタデータオブジェクトを参照する。
OSTMでのアプローチはTMObjectはオブジェクトを獲得しているかをタグビットを用いて区別する。
オブジェクトが獲得されてない間はオブジェクトは直接ポインタで参照される。
そうでなければ、タグビットの立ったポインタはトランザクションディスクリプタを指す。
ロケータを無くすことで間接参照の回数を2から1に減らしている。
しかし、ロケータがなくてもSTMのシステムは通常それぞれの書き込みオブジェクトに2度アクセスする
ロケータの導入と排除に1回ずつだ。
- 静止状態の時にオブジェクトがどう見えるべきか？
どれほど多くの間接化が必要なのかという問題。
(209)ではオブジェクトが静止状態のときには直接アクセスされるというテクニックについて解説している。
さらにその次に、新しいオブジェクトのペイロードはロケーターの中にインライン化するという技法について説明している。
コミット済みのTMObjectの中に`clean`のビットを入れる事によってディスクリプタまで見に行くコストを削減する。
- どのノンブロッキング保証が提供されるのか？
lock-freeにするかobstruction-freeにするかが問題だ。
Lok-freeなSTMはオブジェクトをlazyに獲得する。
それゆえにトランザクションTAがTBによって妨害されていると気づいた時にはTAはTBがトランザクションのコミット操作を助ける事ができる。
ロックフリーということはライブロックを回避するという事である。
しかしこれはメモリシステムの中に重度の競合を引き起こすことになるし、Wait-free保証が得られるわけでもない。
### 間接化なしのノンブロッキングシステム
#### WSTM
WSTM(134)はノンブロッキングかつ関節化のない最初のシステムである。
これはワードベースのSTMシステムで、ある。
データは普通のフォーマットでヒープ上に存在し、STMメタデータのセパレートテーブルを用いてトランザクションのディスクリプタと結びつける。
トランザクションはlazy-acquireで、invisibleなreadingである。
それぞれのトランザクションディスクリプタは[addr, old-val, new-val, version]のタプルをそれぞれトランザクションがアクセスした場所に対して保持する。
それぞれのメタデータエントリーはバージョン番号を保持しうる。もしくはコントロールするトランザクションへ参照することもできる。
メタデータの中のビットがこれを区別する。
Wの中の論理的な値はW自身とWのメタデータM(W)によって以下のように表される。
- もしM(W)がバージョン番号を保持していれば、W自身がその値である。
- もしM(W)がABORTEDもしくはACTIVEなトランザクションによって保持されていれば、そのトランザクションディスクリプタのold-valを読む
- もしM(W)がCOMMITEDなトランザクションによって保持されていればWの論理的な値はトランザクションディスクリプタのnew-valもしくはW自身に書いてある。
ハッシュの利用がこれをオブジェクトベースなシステムよりも複雑にしている。が、大まかな挙動はオブジェクトベースドなlazy-acquireなトランザクションと大筋で似ている。
トランザクションTAがトランザクションTBによって妨害された場合、TAはTBのディスクリプタを用いてTBの完了を助ける。
TBがメモリに書き戻す最中の所で、TBが再びスケジュールされて書き戻しを再開した際、間に発生した他の書き込みを踏みつぶしてしまう可能性がある。
この問題を避けるために、メタデータエントリーは`ownership count`という物を持つ。
それはacquireやreleaseの度にincrementやdecrementされる。
データへのダイレクトなアクセスはそのカウントが0を返した時のみ可能であり、そうでなければすべてのアップデートはトランザクションディスクリプタ内にしか行ってはならない。
(208)ではこの形のノンブロッキングでword-basedなSTMの実装での`metadata-stealing`のテクニックに付いて説明している。
`eager-version management`なものや`global time stamp`を使ったものでのバリエーションに関しても書いてある。
実装は一般に複雑ではあるが、ReadTxのfast-pathに限って言えばMcRT-STMやBartok-STMに近い。
OSのサポートを用いてコミットをいい感じにする方法を考えた（135）
Alert-on-Updateを行うハードウェアがあればOSのサポートが要らなくなるという研究もある（306）
### NZTM
NZTM（313,314）ではDSTMの考え方を拡張して関節化をなくしている。
オブジェクトは`inflated`状態か`non-inflated`状態のどちらかになる。
`inflated`状態ではDSTMスタイルのロケータを持つ。`non-inflated`状態ではトランザクションのステータスフィールドを直接指す。
`non-inflated`な状態であれば、比較的簡単である。
それぞれのオブジェクトは`backup copy`という複製を持っている。それは現在そのオブジェクトを保有しているトランザクションがオブジェクトを獲得する前に作成したものである。
もしトランザクションがACTIVEもしくはABORTEDであればその値の論理的な在対は`backup copy`である。
そうでなければ論理的な場所はオブジェクトのボディである。
これまでのSTMシステムと違って、abortは協力して行われる。それは`abort-request`フラグを立てることによって。このフラグはトランザクションステータスの中の1ビットである。
もしトランザクションがこのフラグが立っていることに気づいたら、自身の状態をABORTEDに変えることでackする。
もしトランザクションTAがTBにabortを要求したがすぐに反応がなかった場合、TAはオブジェクトをinflateする。
inflateはDSTMスタイルのロケータを導入し、オブジェクトのオーナーがこれを指すようにする。（この時にinflate bitを立てる）
これでオブジェクトの論理的な状態はロケーターを経由して決定される。
WSTMのオーナーシップカウントのように、元々のオブジェクトの場所は最初のオーナーがアボート操作を完了するまで触れる事はできない。
実用上インフレーションはめったに起きないと期待されている。
なぜなら所有しているトランザクションが何らかの理由（ページフォルトなど）で長時間帰ってこない場合にしか起きないからだ。
作者はsingle-compare-single-store命令があればこれの実装が相当楽になると書いている。
なぜならabort-requestフラグが立っていない事を毎書き込み毎に確認できるからだ。
これはWSTMにおいても同様だと言っている（210）
# さらなる実装テクニック
## Privatization SafetyとPublication Safety
一種のJudoSTMやNOrecやRingTMがprivatization safetyを満たしている。
それぞれの書き込みはそれぞれのコミット順に即している。
それに加えてグローバルなメタデータの利用によって、read-onlyなトランザクションが読もうとした値が直前のwriterによってprivatizeされた場合であってもwriterが完全に書き込むまで待つ。
TLRWというシステムでは（86）異なる方法を取っている。
TLRWではencounter-timeのロックで問題を解決している。Pessimisticなので問題が起きない。
* memo
# McRT-STM
タイムアウトによるデッドロック回避。eagerなバージョニングでundo-logを使う。
独自のreader-writerロックによる競合解決を検討したが死ぬほど遅かったので諦めた。
ちなみに検討していたロックは以下のような感じ
下3bitでロックがリードロック中か・ロックがアップグレードを要求しているか・ロックがリーダーから要求されているか、を表現している。
その上のビットで、writerロックを獲得したトランザクションディスクリプタを指す。
writeロックが採られている間、つまりこのロックオブジェクトは普通のポインタのように動くので下の3ビットはすべて0である。
readロックが採られている場合、リードロックのビットが立つ他に、リーダーの人数が3ビット目より上の部分でカウントされる（+8/-8で調整する）
これをちょっと書き換えればバージョン番号とロックディスクリプタが同居するバージョンドロックが作れる。
# SkySTM
Privatizationを高速に行える事を売りにしたSTM.
Lazyでsemi-visible-readerで動く。
memo:
probability of deadlocks is proportional to NW4/L2 and hence small:
(N=no. of concurrent transactions, W = no. of locks acquired on average (~no. of stores), L = total no. of locks that can be acquired (~total no. of shared objects)).
