１６章 未来のビジョンはいろいろある
この章では、並列プログラミングの未来のビジョンをいくつか示します。どれが起こるか、どれも起こらないか、わかりません。それでも、それらビジョンは重要です。それぞれのビジョンには熱烈な支持者がいます。十分多くの人々が何かを十分熱心に信じれば、それが支持者の思考、言葉、そして行動に与える影響という形で、そのものの存在の影であってもあなたはかかわりになる必要があります。それはそうとして、これらのビジョンの１つ以上が実際に起きるということも十分あります。しかし、ほとんどはいんちきです。どれが当たるかわかれば、お金持ちになれます。
なので、以下の節は、トランザクショナルメモリ、ハードウェアトランザクショナルメモリ、そして並列関数型プログラミングの概略を説明します。しかし、まず最初に、２０００年台初頭にあった予言についての警告の話から始めましょう。
１６．１ 未来のCPU技術は以前のものとは違います
何年にもわたる経験を通して見る過去の日々は、常にとても単純で、無邪気に見えます。そして、２０００年台初頭は、既に伝統となった、ムーアの法則がCPUクロック周波数を上げ続けることができるということがいよいよ続かなくなることに関しても、おおむね楽観的でした。ああ、技術の限界を警告する声はときどきありましたが、そんなものは何十年も前からあるものです。そのうえで、以下のシナリオを考えましょう。
１ ユニプロセッサは何より優れる。（図１６．１）
２ マルチスレッドマニア（図１６．２）
３ 同じものがたくさん（図１６．３）
４ 衝突実験人形がメモリの壁にぶつかる（図１６．４）
以下の節でそれぞれのシナリオを説明します。
１６．１．１ ユニプロセッサは何より優れる
２００４年の発言より。
このシナリオにおいて、CPU クロックレートのムーアの法則による増加と、水平にスケールするコンピューティングの連続する進歩の組み合わせは、SMP システムをどうでもよくします。なのでこのシナリオは、「Uniprocessor Über Alles」、文字通り、ユニプロセッサは何よりも優れる、と名付けられます。
これらのユニプロセッサシステムは、命令オーバヘッドだけが問題です。なぜならば、メモリバリア、キャッシュスラッシング、そして競合は、単一CPU システムには影響しないからです。このシナリオでは、RCU は、NMI と相互作用するなどのニッチなアプリケーション以外には役に立ちません。RCU を持たないオペレーティングシステムが、それを採用する要求を持つかは不明です。既にRCU を実装しているオペレーティングシステムは、それを使い続けるでしょう。
しかし、最近のマルチスレッドCPU の進歩は、このシナリオはとてもありえないだろうことを示しているようです。
全く、ありえないです！しかし、より大きなソフトウェアコミュニティは、並列性を取り入れる必要があるという事実を認めるのに消極的でした。なので、このコミュニティがムーアの法則が引き起こすCPU コアクロック周波数の増加による「フリーランチ」がついに、本当に、終わったことを結論付けるまでにはしばらく時間がかかりました。忘れないように。信念は情動です。必ずしも、合理的な技術的思考プロセスの結果であるとは限りません！
１６．１．２ マルチスレッドマニア
同じく２００４年の発言より。
ユニプロセッサは何より優れる、のもうちょっと穏やかな変種は、ハードウェアマルチスレッディングを持つユニプロセッサに注目します。実際、マルチスレッドCPUは、今では多くのデスクトップとラップトップ計算機システムの標準です。最もアグレッシブなマルチスレッドCPUは、全てのキャッシュ階層のレベルを共用します。そうして、CPUからCPUのメモリ遅延を除き、その結果、伝統的な同期機構の性能ペナルティを大いに減らします。しかし、マルチスレッドCPUは依然として、競合と、メモリバリアによって起きるパイプラインストールのオーバヘッドを持ちます。さらに、全てのハードウェアスレッドが全てのキャッシュのレベルを共有するために、あるハードウェアスレッドが使用可能なキャッシュは、同等のシングルスレッドCPUにおいて使用可能なものの何分の一かになります。それは、キャッシュフットプリントが大きいアプリケーションでは性能を落とします。さらに、使えるキャッシュ量が制限されるために、RCU ベースのアルゴリズムが、グレースピリオドに由来する追加のメモリ消費のために性能ペナルティを受ける可能性もあります。その可能性を調べるのは将来の課題です。
しかし、そのような性能ペナルティを避けるために、多くのマルチスレッドCPUとマルチCPUチップは、少なくてもいくらかのキャッシュのレベルを、ハードウェアスレッドごとに分割割り当てします。これはそれぞれのハードウェアスレッドが使うことのできるキャッシュ量を増やしますが、ハードウェアスレッド間で手渡されるキャッシュラインに関するメモリ遅延を再び導入します。
さて、私たちは皆、この物語がどうなったか知っています。マルチスレッドのコアが一つのダイに複数載って、一つのソケットに差し込まれます。すると問題は、将来の共用メモリシステムは、常に一つのソケットに収まるかです。
１６．１．３ 同じものがたくさん
また２００４年の発言より。
同じものがたくさんのシナリオは、メモリ遅延の割合はほぼ、今そうである状態にとどまることを前提とします。
このシナリオは、実際には変化を表します。同じものがたくさん、を得るためには、インターコネクトの性能は、コアCPU性能のムーアの法則による増加に追従し始める必要があります。このシナリオでは、パイプラインストール、メモリ遅延、そして競合のためのオーバヘッドは高いままであり、RCUは今と同様の、高いレベルの適用性を保つでしょう。
そして、変化は、ムーアの法則がいまだに提供する、増加し続ける統合のレベルです。しかし、長い目で見ると、ダイにより多くのCPUが良いのか、より多くの I/O、キャッシュ、そしてメモリが良いのか、どちらでしょう？
サーバは前者を選び、一つのチップ上の組込みシステム(SoC) は後者を選び続けているようです。
１６．１．４ 衝突実験人形がメモリの壁にぶつかる
もうひとつ、２００４年の発言より。
もし、図１６．５に示すメモリ遅延のトレンドが続くなら、メモリ遅延を命令実行オーバヘッドと比べた割合は増加し続けるでしょう。図１６．６で示すように、RCU をたくさん使っている Linux のようなシステムは、より多くのRCUを使うことで利益を得られるでしょう。この図でわかるように、RCUがたくさん使われているときには、メモリ遅延の割合が増えるにつれて、他の同期機構に対するRCUの優位性は増します。それに対して、RCUをあまり使わないシステムでは、図１６．７が示すように、RCUの使用が価値を持つためには、リードの割合がより高いことが必要となります。この図でわかるように、RCUがあまり使われてないときは、メモリ遅延の割合が増えるにつれて、他の同期機構に対してRCUはより不利になります。
訳注。r が、遅延の割合、ラムダがRCUの利用頻度らしいけど、話が見えない。drw って、何？
Linuxは、高負荷の時に、グレースピリオドあたり、１６００以上のコールバックが動くのが見えたそうなので、Linuxは前者のカテゴリーに属すると言っても良いでしょう。
一方、この文章は、更新が強いワークロードの時に、RCUが直面する、キャッシュを温める問題を予見することができませんでした。その理由の一つは、RCUが実際にそのような場合に使われることはあり得ないと思われたためです。現実には、このキャッシュを温める効果がシーケンスロックをするために問題となりそうな多くの事例で、
SLAB_DESTROY_BY_RCU が使われました。一方、この文章は、RCUがスケジューリング遅延を減らしたり、セキュリティのために使われることも予見できませんでした。
短く言えば、予言にご注意。なお、この章の残りの部分にあるものも含めて。
１６．２ トランザクショナルメモリ
データベース以外でトランザクションを使うというアイデアは、何十年も前からあります。データベースとそうでないトランザクションの重要な違いは、データベーストランザクションを定義する「ACID」属性のうち、後者は「D」が無いことです。ハードウエアでメモリベースのトランザクション、あるいは、「トランザクショナルメモリ」（TM）をサポートするというアイデアは、より最近のものですが、残念なことに、一般的ハードウエアがそういうトランザクションをサポートするというのは、すぐには実現しそうにありませんでした。少し違った提案がされたことはありますが。しばらくして、Shavit と Touitou が、一般的ハードウエアで動き、メモリ順序の問題は置いとくとして、ソフトウェアだけのトランザクショナルメモリの実装（STM）を提案しました。この提案は何年もの間、元気がありませんでした。たぶん、研究コミュニティの関心は、ノンブロッキング同期（１４．３節を参照）に吸い寄せられていたからでしょう。
しかし、２０世紀の終わり頃、TM はより多くの関心を集めるようになりました。そして２０００年代の中間には、関心のレベルは「白熱」としか言いようのないものとなりました。警告の声も少しはありましたが。
TM の基本的なアイデアは、コードのセクションをアトミックに実行し、他のスレッドが中間状態を見ないようにすることです。このため、TM のセマンティクスは、単純に、それぞれのトランザクションを再帰的に確保可能なグローバルロックの確保と解放に置換すれば実装可能です。この場合、性能とスケーラビリティはひどいものですが。ハードウエアにしろソフトウェアにしろ、TM の実装に必須の複雑さは、安全にトランザクションを同時実行させられる時を効率よく検出することです。検出はダイナミックに行われるので、競合するトランザクションはアボート、あるいは「ロールバック」されます。実装によってはこの失敗モードがプログラマから見えます。
トランザクションの大きさが小さければトランザクションロールバックはまれになりますから、スタック、キュー、ハッシュテーブル、そして探索木などで使われる連結リスト操作などの小さなメモリベースの操作にとって、TM はとても魅力的なものになります。しかし、現在のところ、プロセス生成やI/Oなどのメモリ操作でないものを含む大きなトランザクションに適用するのはよりずっと困難です。以下の節は、現在の、「どこでもトランザクショナルメモリ」というグランドビジョンへの挑戦を見ていきます。１６．２．１節は外の世界と相互作用するときの問題を調べます。１６．２．２節はプロセス変更プリミティブとの関係を見ます。１６．２．３節は他の同期プリミティブとの関係を調査します。最後に１６．２．４節は少し議論をして終わります。
１６．２．１ 外の世界
Donald Knuth の言葉より。
多くの計算機ユーザは、入出力は、実際に「本当のプログラミング」の部分ではないと感じています。それは、マシンに情報を入れたり出したりするために(不幸にも)しなくてはいけない、ただのものごとです。
入出力が「本当のプログラミング」だと信じるかどうかは別として、ほとんどの計算機システムにとって、外の世界との相互作用は、第１級の要件であることは事実です。なのでこの節は、トランザクショナルメモリが、I/O 操作、時間遅延、そして永続的記憶域を使って、相互作用する能力を批判検証します。
１６．２．１．１ I/O 操作
ロックベースのクリティカルセクションの中で I/O 操作は、可能です。そして、少なくても原理的には、RCU リード側クリティカルセクションの中からもです。トランザクションの中で I/O 操作を実行しようとしたら、何が起きるでしょう？
元となる問題は、トランザクションは例えば競合のためにロールバックされることがあることです。大まかに言えば、これは、どのようなトランザクションでもその中のすべての操作は取り消し可能でないといけないということです。その操作を２回実行しても、１回実行した時と同じ効果を持つ必要があります。不幸にも、I/O は、一般的に、典型的な取り消し不可能な操作ですから、トランザクションに一般的な I/O 操作を含めるのは難しいのです。実際、一般的なI/Oは取り消し不可能です。核弾頭を発射するボタンを押したら、戻ることはできません。
以下は、トランザクション内でI/Oを扱ういくつかの選択肢です。
１ トランザクション内のI/Oを、メモリ上のバッファへのバッファドI/Oに限定します。そしてこれらのバッファは、他のすべての関連するメモリ位置と同じ方法で、トランザクションに含めることができます。これは素晴らしい機構のように思えます。そして実際、ストリームI/Oや大容量記憶域のような多くの一般的な状況でうまくはたらきます。ただ、複数のプロセスからの複数のレコード指向の出力ストリームが、一つのファイルにマージされる状況では、特別な扱いが必要です。これは、fopen() の "a+" オプションや、open() の O_APPEND を使った時です。また、次の節で見るように、一般的なネットワーク操作はバッファリングでは扱えません。
２ トランザクション内のI/Oを禁止します。I/O操作を実行しようとする試みは全て、それを取り囲むトランザクション(そしてもしかすると複数のネストしたトランザクション)をアボートします。このアプローチは、バッファされないI/Oに対する、これまでの TM のアプローチのようです。しかし、TM が、I/Oを許容する他の同期プリミティブと協調する必要があります。
３ トランザクション内のI/Oを禁止します。なお、この禁止を強制するために、コンパイラの助けを借ります。
４ どの時点でも、ただ一つの特別な irrevocable トランザクションだけが進行するのを許します。そして、irrevocable トランザクションがI/O操作を含むのを許します。
脚注
以前の論文では、irrevocable トランザクションは、inevitable トランザクションと呼ばれました。
これは、一般的にはうまくいきますが、I/O操作のスケーラビリティと性能を著しく制限します。スケーラビリティと性能が並列性のゴールの第１級のゴールであることを考えると、このアプローチの一般性は自己規制が少し過ぎるようです。さらに悪いことに、I/O操作を許容するために irrevocable 性を使うことは、マニュアルのトランザクションアボート操作を禁止するようです。
脚注
この困難は、Michael Factor が指摘しました。
最後に、もしあるデータ要素を操作している irrevocable トランザクションがあるならば、その同じデータ要素を操作する他の全てのトランザクションは、ノンブロッキングなセマンティクスを持つことができません。
５ I/O操作をトランザクションの土台の上に持ってくることができるような、新しハードウェアとプロトコルを作成します。入力操作の場合、ハードウェアは操作の結果を正しく予言し、予言が違ったら、トランザクションをアボートする必要があります。
I/O操作はTMのよく知られた弱点です。そして、I/Oをトランザクション内でサポートする問題に、適切な一般解があるかは不明です。少なくとも、「適切」が、使い物になる性能とスケーラビリティを含むならばです。とはいっても、この問題に引き続き寄せられる関心と時間はさらなる進歩をもたらすことでしょう。
１６．２．１．２ RPC操作
ロックベースのクリティカルセクションの中で RPC を実行するのは、可能です。そして、RCU リード側クリティカルセクションの中からもです。トランザクションの中で RPC を実行しようとしたら、何が起きるでしょう？
RPC の要求とその応答がトランザクションに含まれ、そのトランザクションの一部が、応答によって返る結果に依存するならば、バッファドI/O の場合に使うことのできたメモリバッファのトリックを使うことはできません。このバッファリングアプローチを行おうとする全ての試みは、トランザクションをデッドロックさせます。なぜならば、要求はトランザクションが成功する保証が得られるまで送られることはなく、トランザクションが成功するかどうかは、応答が返るまでわからないかもしれないからです。以下の例のようにです。
1 begin_trans();
2 rpc_request();
3 i = rpc_response();
4 a[i]++;
5 end_trans();
トランザクションのメモリフットプリントはRPC応答を受信した後でないと決まりません。そして、トランザクションのメモリフットプリントが決まってからでないと、トランザクションがコミットするのを許すことができるか決めるのは不可能です。なので、トランザクショナルなセマンティクスと矛盾しない唯一の操作は、無条件にトランザクションをアボートすることです。それはどう見ても、役には立たないでしょう。
以下は、TMが取ることのできるいくつかの選択肢です。
１ トランザクション内のRPCを禁止します。RPC操作を実行しようとする試みは全て、それを取り囲むトランザクション(そしてもしかすると複数のネストしたトランザクション)をアボートします。あるいは、コンパイラに、RPCのないトランザクションを強制させます。このアプローチはたしかにうまくいきますが、TMが他の同期プリミティブと相互作用する必要があります。
２ どの時点でも、ただ一つの特別な irrevocable トランザクションだけが進行するのを許します。そして、irrevocable トランザクションがRPC操作を含むのを許します。
訳注。
前の節の項番４の説明と同じなので省略。
３ RPC応答を受ける前にトランザクションの成功を決められる特別な場合を識別します。そして、RPC要求を送る直前に、自動的にこれを irrevocable トランザクションに変換します。もちろん、もしいくつかの同時実行するトランザクションがこのようにRPC呼び出しを試みたら、それらのうち一つ以外を全部ロールバックすることが必要になるかもしれません。その結果、性能とスケーラビリティは落ちます。このアプローチは、それであってもなお、価値があるかもしれません。RPC で終わる、長時間走るトランザクションにとっては。このアプローチは、マニュアルのトランザクションアボート操作については問題があります。
４ RPC応答をトランザクションの外に移動できる特別な場合を識別します。そして、バッファドI/O で使ったのと類似のテクニックを使って進行します。
５ トランザクションの土台を、RPCサーバーとクライアントを含むように拡張します。これは理論的には可能です。分散データベースが示したように。しかし、分散データベースのテクニックで、必要な性能とスケーラビリティが得られるかは不明です。メモリベースのTMは、遅いディスクドライブの背後にある遅延を隠すことはできないからです。もちろん、SSD のおかげで、データベースが、ディスクドライブの背後にある自身の遅延をどれだけ隠し通せるかも不透明となってきました。
前の節で述べたとおり、I/OはTMのよく知られた弱点です。そしてRPCは、単純に、I/Oの特別に面倒なケースです。
１６．２．１．３ 時間遅延
トランザクション外のアクセスとの相互作用の重要な特別ケースに、トランザクション内の明示的な時間遅延があります。もちろん、トランザクション内の時間遅延という概念は、TMのアトミシティ属性とひどく矛盾するものです。しかし、弱いアトミシティとはまさにこういう類の事のためにあるとも言えます。さらに、メモリマップされたI/Oをうまく行うには、注意深く制御されたタイミングを必要とすることがあります。そして、アプリケーションはしばしばいろいろな目的で時間遅延を使います。
さて、TMは、トランザクション内の時間遅延をどうしたらいいでしょう？
１ トランザクション内の時間遅延を無視します。これは優雅に見えますが、あまりに多くの他の「優雅な」解決策と同様、レガシーコードとの最初の接触を生き延びることはありません。そのようなコードは、クリティカルセクション内の重要な時間遅延を持つことが十分にあり、トランザクションになるとすぐに失敗するでしょう。
２ 時間遅延操作があったら、トランザクションをアボートします。これは魅力的です。しかし、不幸にも、時間遅延操作を自動的に検知するのは常に可能とは限りません。あのタイトループは何か重要な計算をしているのでしょうか、時間が経つのを待っているのでしょうか？
３ コンパイラに、トランザクション内の時間遅延を禁止させます。
４ 時間遅延を通常通り実行させます。不幸にも、TM実装によっては変更をコミット時にしか公開しないものがあります。それは多くの場合、時間遅延の目的を損ないます。
単一の正解があるかはわかりません。弱いアトミシティを持ち、トランザクション内の変更を直ちに公開(アボートしたら変更をロールバックします)するTM実装は、最後の選択肢がかなりうまくいくかもしれません。その場合でも、トランザクションの反対側にいるコードは、アボートしたトランザクションに耐えるために大きな再設計を必要とするかもしれません。
１６．２．１．４ 永続性
ロックプリミティブには多くの異なるタイプがあります。一つの興味深い区別は、永続性です。言葉を代えると、ロックが、そのロックを使っているプロセスのアドレス空間とは独立して存在できるかです。
永続的でないロックには、pthread_mutex_lock(), pthread_rwlock_rdlock() それにほとんどのカーネルレベルのロックプリミティブがあります。永続的でないロックのデータ構造を実体化しているメモリ位置が消えたら、ロックも消えます。pthread_mutex_lock()の典型的な使い方に関して言えば、プロセスが終了する時はその全てのロックも消えるということです。この性質は、プログラム終了時にロックの後始末を簡単にするために使うことができますが、関連しないアプリケーションがロックを共用するのをより難しくします。そのような共用にはアプリケーションがメモリを共用する必要がありますから。
永続的ロックは、関連しないアプリケーションがメモリを共用しなくてもよくします。永続的ロックのAPIには、 flock ファミリー、 lockf(), システム V セマフォ、そして、open() の O_CREAT フラグがあります。これらの永続的APIは、複数のアプリケーション実行にまたがる大規模な操作を守るのに使えます。O_CREAT の時は、オペレーティングシステムリブートを超えてさえ存在します。必要なら、分散ロックマネージャを使って、ロックは複数の計算機システムにまたがることができます。
永続的ロックは任意のアプリケーションから使えます。異なる言語とソフトウェア環境で書かれたアプリケーションでもかまいません。実際、永続的ロックは C で書かれたアプリケーションで確保して、Python で書かれたアプリケーションで解放しても良いです。
TMには、同様の永続的機能はどのように提供されるでしょう？
１ 永続的トランザクションを、それをサポートするために設計された特別の環境、例えば、SQL 、に限定します。これはもちろん、数十年に渡るデータベースシステムの歴史を見てわかるように、うまくいきます。しかし、永続的ロックが提供する同じレベルの柔軟性は提供できません。
２ ある種のストレージデバイスやファイルシステムで提供されるスナップショット機能を使います。不幸にも、これはネットワーク通信を扱えませんし、メモリスティックのようにスナップショット機能を提供しないデバイスへのI/Oを扱えません。
３ タイムマシンを作ります。
もちろん、これがトランザクショナルメモリと呼ばれている事実は、我々を立ち止まらせるべきです。名前自身が、永続的トランザクションという概念と矛盾しているからです。とはいっても、この可能性を、トランザクショナルメモリの固有の限界を探るための重要なテストケースとして考えるのは価値のあることです。
１６．２．２ プロセス変更
プロセスは永遠ではありません。生成、破壊され、そのメモリマッピングは変更されます。ダイナミックライブラリとリンクされ、デバッグされます。以下の節で、トランザクショナルメモリがいかに、変化し続ける実行環境を扱うことができるかを見ます。
１６．２．２．１ マルチスレッドトランザクション
ロックを持ったまま、あるいは、RCUリード側クリティカルセクションの中から、プロセスとスレッドを作成するのは、完全に合法です。合法なだけでなく、それはとても単純です。以下のコード断片で明らかです。
1 pthread_mutex_lock(...);
2 for (i = 0; i < ncpus; i++)
3 pthread_create(&tid[i], ...);
4 for (i = 0; i < ncpus; i++)
5 pthread_join(tid[i], ...);
6 pthread_mutex_unlock(...);
この擬似コードは、pthread_create を使って CPUごとにスレッドを作成し、pthread_join でそれらが終わるのを待ちます。全ては、pthread_mutex_lock の保護のもとで行われます。この結果、ロックベースのクリティカルセクションが並列に実行されます。同様な効果は、fork() と wait() でも得られます。
もちろん、スレッド生成のオーバヘッドを正当化するためには、クリティカルセクションはとても大きい必要があります。しかし、本番ソフトウェアで、大きなクリティカルセクションを持つ例はたくさんあります。
トランザクション内からスレッドを生成することについて、TMはどうするべきでしょう？
１ pthread_create を、トランザクション内では不正とします。トランザクションは、アボート(望ましい)あるいは、未定義のふるまいとなります。あるいは、コンパイラによって、pthread_create のないトランザクションを強制します。
２ トランザクション内の pthread_create 実行を許します。ただ、親スレッドだけを、トランザクションの一部として扱います。このアプローチは、既存あるいは将来のTM実装と、十分互換であるように見えます。しかし、注意しないと罠があります。このアプローチは他の問題を提起します。例えば、競合する子スレッドのアクセスをどうしたらいいかです。
３ pthread_create を、関数呼び出しに変換します。このアプローチもまた、魅力的な困りものです。それは、子スレッド同士が通信し合うという、稀とはいえない場合を処理できません。さらに、それは、トランザクションのボディの並列実行を許しません。
４ 親と全ての子スレッドをカバーするようにトランザクションを拡張します。このアプローチは、競合するアクセスの性質について、興味深い問題を提起します。親と子は互いに競合することが許されているはずですが、他のスレッドとは許されないはずです。それはまた、もし親スレッドがトランザクションをコミットする前に、子を待たなかったら何が起きるべきかという興味深い問題を提起します。もっと面白いのは、親が、トランザクションに含まれる変数の値によって、pthread_join を呼んだり呼ばなかったりしたら何が起きるでしょう？ロックの場合のこれらの質問の答えは十分に直裁的です。TMの場合の答えは、読者への課題としましょう。
データベースの世界では、トランザクションの並列実行は当たり前です。それと比べて、現在のTMの提案がそれを提供しないのはたぶん驚くべきことでしょう。一方、これまでにあげた例は、普通は、単純な教科書の例には出てこないような、とても洗練されたロックの使い方をします。なので、それが考慮されなかったのは仕方ないことかもしれません。とはいえ、TM研究者には、トランザクション内の fork/join 並列性を研究している人がいるという噂があります。なので、この話題はいずれより完全な扱いがされることがあるかもしれません。
１６．２．２．２ exec() システムコール
ロックを持ったまま、あるいはRCUリード側クリティカルセクションからも、exec() システムコールを実行できます。正確なセマンティクスは、プリミティブのタイプに依存します。永続的でないプリミティブ(pthread_mutex_lock(), pthread_rwlock_rdlock(), そして RCU を含みます。）では、exec() が成功した時には、取られたロックを含むアドレス空間全体が消えます。もちろん、exec() が失敗した時には、アドレス空間も、全ての関連するロックも生き続けます。ちょっと変かもしれませんが、きちんと定義されたことです。
一方、永続的プリミティブ(flock ファミリー, lockf(), System V セマフォ, そして open() の O_CREAT フラグを含みます。）は、exec() が成功しても失敗しても残ります。なので、exec() されたプログラムがそれを解放しなくてはいけないかもしれません。
クイッククイズ １６．１：
mmap() されたメモリ領域にあるデータ構造であらわされる永続的でないプリミティブはどうなりますか？そのようなプリミティブのクリティカルセクションで、exec() があったらどうなりますか？
トランザクションの中でexec() システムコールを実行しようとしたら何が起きますか？
１ トランザクション内のexec() を禁止します。それを取り囲むトランザクションは、exec() があるとアボートされます。これはよく定義されていますが、明らかに、exec() と共に使う時には、TM以外の同期プリミティブを必要とします。
２ トランザクション内のexec() を禁止します。コンパイラを使ってこれを強制します。C++ での TMのためのドラフト仕様があり、このアプローチを取っています。関数を、transaction_safe と transaction_unsafe 属性でデコレートできます。
脚注
この仕様を教えてくれた Mark Moir と、しばらく前に、その初期の版を教えてくれた Michael Wong に感謝。
このアプローチは実行時にトランザクションをアボートするよりはいくらか優れますが、同様に、exec() と共に使う時には、TM以外の同期プリミティブを必要とします。
３ トランザクションを、永続的でないロックプリミティブと同様に扱います。なので、トランザクションは、exec() が失敗すると生き延びて、exec() が成功すると無言でコミットします。トランザクションにより影響のある変数が、mmap() されたメモリに存在(その結果、exec() システムコールが成功しても生き残ることがある)する場合については、読者への課題とします。
４ exec() システムコールが成功するはずであったならば、トランザクション（と exec() システムコール）をアボートし、exec() システムコールが失敗するだろうときには、トランザクションの続行を許します。これはある意味で、「正しい」アプローチですが、なんとも不満足な結果を何とかするにはかなりの作業が必要でしょう。
exec() システムコールは、たぶん、TMの普遍的適用への、最も奇妙な障害の例です。どんなアプローチが意味があるのか、完全にはわかっていません。これは、本当の人生で、 exec の仲間を扱うことが大変であることの反映にすぎないと言う人もいます。とはいえ、トランザクション内で exec() を禁止する二つの選択肢が、その中では最も論理的かもしれません。
exit(), kill() システムコールにも、似た問題があります。
１６．２．２．３ ダイナミックリンクとロード
ロックベースのクリティカルセクションも、RCUリード側クリティカルセクションも、ダイナミックにリンクされ、ロードされる関数を呼ぶコードを含むのは合法です。それには、C++ の共用ライブラリと Java のクラスライブラリが含まれます。もちろん、これらのライブラリに含まれるコードは定義により、コンパイル時には未知です。なので、トランザクション内からダイナミックにロードされた関数が呼ばれると何が起きるでしょう？
この問題は二つの部分を持ちます。(a) トランザクション内から関数をダイナミックにリンクとロードするにはどうするか？そして、(b) この関数内のコードの未知の性質をどうするか？公平に言えば、(b) は、ロックとRCUにとっても、少なくても理論上は問題となります。例えば、ダイナミックにリンクされた関数はロックの場合にデッドロックをもたらすかもしれませんし、RCUリード側クリティカルセクションに(誤って)静止状態をもたらすかもしれません。違いは、ロックとRCUクリティカルセクションで許される操作のクラスはよく理解されている一方、TMの場合はかなりわかっていないようだということです。実際、異なるTM実装は、異なる制限を持つようです。
では、TMは、ダイナミックにリンク、ロードされたライブラリ関数をどうしたらいいでしょう？(a) の部分、実際にコードをロードすること、の選択肢は、以下があるでしょう。
１ ダイナミックリンクとロードを、ページフォールトと似たやり方で扱います。なので、関数がロードされ、リンクされると、そのプロセスのトランザクションをアボートすることがあります。もしトランザクションがアボートしたら、リトライはその関数が既に存在しているのを見つけるので、トランザクションは通常通りに進むことができます。
２ トランザクション内からの関数のダイナミックリンクとロードを禁止します。
(b) の部分、まだロードされていない関数にある、TMに優しくない操作を検出することができないこと、の選択肢は、以下があるでしょう。
１ 単に、コードを実行します。その関数内にTMに優しくない操作があれば、単にそのトランザクションをアボートします。不幸にも、このアプローチは、コンパイラが、あるトランザクションのグループが安全に構成できるかを決めることを不可能とします。どのような場合でも構成可能とする一つの方法は、irrevocable トランザクションです。しかし、今の実装は、ある時点では一つの irrevocable トランザクションしか進むことを許しません。それは性能とスケーラビリティを著しく制限します。irrevocable トランザクションはさらに、手作業によるトランザクションアボート操作の使用を禁止するようです。最後に、もしあるデータ要素を操作している irrevocable トランザクションがあるならば、その同じデータ要素を操作している他のトランザクションはいずれも、ノンブロッキングなセマンティクスを持つことができません。
２ 関数定義をデコレートして、TMに優しい関数を指示します。そしてこのデコレーションは、コンパイラの型システムで強制できます。もちろん、多くの言語において、これは言語拡張の提案、標準化、そして実装を必要とします。それには対応する時間がかかります。とはいえ、標準化作業は既に始まっています。
３ 前述のとおり、トランザクション内からの関数のダイナミックリンクとロードを禁止します。
I/O 操作はもちろん、TMの既知の弱点です。そして、ダイナミックリンクとロードは、I/Oのさらに別の特別ケースと考えられます。それでも、TMの支持者はこの問題を解決するか、あるいはあきらめて、TMが並列プログラマの道具箱の多くのツールの中の一つである世界に留まるかを選ばなくてはいけません。（公平に言うならば、多くのTM支持者が、既にTM以外のものも含む世界を選択してずいぶんの時がたちます。）
１６．２．２．４ メモリマップ操作
ロックベースのクリティカルセクション内から、あるいは、少なくても原理的には、RCUリード側クリティカルセクションの中から、メモリマップ操作（mmap(), shmat(), そして munmap() など）をするのは、完全に合法です。トランザクション内からそのような操作を試みると何が起きるでしょう？問題点をより明確にするならば、リマップされるメモリ領域が現在スレッドのトランザクションに参加している何らかの変数を含んでいたら、何が起きるでしょう？さらに、このメモリ領域がどれか他のトランザクションに参加している変数を含んでいたらどうでしょう？
TM システムのメタデータがリマップされる場合を考える必要は必ずしもありません。ほとんどのロックプリミティブは自身のロック変数がリマップされたときの結果を定義していませんから。
以下は、いくつかの TM にとってのメモリマップの選択肢です。
１ トランザクション内のメモリリマップは違法で、それを取り囲む全てのトランザクションはアボートされます。これは確かにものごとをかなり簡単にしますが、TM はクリティカルセクションでリマッピングに耐える同期プリミティブと相互運用する必要があります。
２ トランザクション内のメモリリマップは違法で、コンパイラを使ってこれを強制します。
３ トランザクション内のメモリリマップは合法ですが、マップされた領域に変数を持つ他の全てのトランザクションはアボートされます。
４ トランザクション内のメモリリマップは合法ですが、マップされた領域が、現在のトランザクションのフットプリントと重なるならば、マップ操作は失敗します。
５ 全てのメモリマップ操作は、トランザクションの中でも外でも、マップされる領域を、システム内の全てのトランザクションのメモリフットプリントと比較します。重なりがあれば、メモリマップ操作は、失敗します。
６ システム内の任意のトランザクションのメモリフットプリントと重なるメモリマップ操作の効果は、TM 競合マネージャによって決定されます。それは、ダイナミックに、メモリマップ操作を失敗させるか、競合するトランザクションをアボートするかを決めます。
munmap() は、関連するメモリ領域をアンマップするのに注意するのは面白いことです。それはさらに、興味深い結果をもたらすことがあります。
脚注。マップとアンマップのこの違いは、Josh Triplett が指摘しました。
１６．２．２．５ デバッグ
ブレークポイントなどの通常のデバッグ操作は、ロックベースのクリティカルセクション内でも、RCUリード側クリティカルセクション内でも普通に動きます。しかし、初期のハードウェアトランザクショナルメモリハードウェア実装では、トランザクション内の例外はそのトランザクションをアボートしましたから、それはつまり、ブレークポイントはそれを取り囲む全てのトランザクションをアボートすることを意味しました。
では、トランザクションをデバッグするにはどうしたらいいでしょう？
１ ブレークポイントを含むトランザクション内では、ソフトウェアエミュレーション技術を使います。もちろん、あるトランザクションのスコープ内でブレークポイントが設定されたらいつでも、全てのトランザクションをエミュレートする必要があるかもしれません。もし、ランタイムシステムがあるブレークポイントがトランザクションのスコープ内にあるかを決められない時は、安全のために全てのトランザクションをエミュレートする必要があるかもしれません。しかし、このアプローチは、多大なオーバヘッドを課すでしょう。それはまた、追っかけているバグを不明瞭にするかもしれません。
２ ブレークポイント例外を扱うことのできるハードウェアTM実装だけを使います。不幸にも、これを書いている現在(２００８年９月)、そのような実装は全て、厳密な研究プロトタイプです。
３ ソフトウェアTM実装だけを使います。それは(とても大まかに言って)、ハードウェアTM実装の割と単純なものと比べると、より、例外に許容的です。もちろん、ソフトウェアTMはハードウェアTMと比べてオーバヘッドが大きい傾向にあるので、このアプローチは全ての状況で使えるわけではありません。
４ ずっと注意深くプログラムして、そもそも、トランザクション内でバグを作らないようにします。あなたが、これを行う方法がわかったら、どうかみんなに秘密を教えてください！
トランザクショナルメモリは他の同期プリミティブに比べて、生産性を上げるだろうと信じることのできる理由がいくらかあります。しかし、伝統的なデバッグ技術がトランザクションには適用できないとすると、そのような改善は容易に失われるというのは大いにあり得ます。これは特に、トランザクショナルメモリが巨大なトランザクションに対して、新人によって使われるならば、特に正しいでしょう。それに対して、マッチョの「トップガン」プログラマは、特に、小さなトランザクションに対しては、そのようなデバッグ補助なしでも済むかもしれません。
なので、トランザクショナルメモリが、新人プログラマにその生産性の約束を果たすことができるためには、デバッグ問題は必ず解決が必要です。
１６．２．３ 同期
いつの日にか、トランザクショナルメモリが、全ての人にとっての全てのものである事を証明できることになれば、他の同期機構と相互作用する必要はないでしょう。その日が来るまでは、それは、自分にできないことができるか、あるいは与えられた状況でより自然に働く同期機構と共に働く必要があります。以下の節は、この領域での現在の問題点の概要を説明します。
１６．２．３．１ ロック
他のロックを持ったままロックを取るのはよくあることで、デッドロックを避けるための通常のよく知られたソフトウェア技術テクニックを使うならばとてもうまくいきます。RCUリード側クリティカルセクションの中からロックを取るのはめずらしくありません。RCUリード側プリミティブはロックベースのデッドロックサイクルには参加できないので、デッドロックの心配はありません。しかし、トランザクションの中からロックを取ろうとしたらどうなるでしょう？
理論的には、答えは自明です。ロックを表すデータ構造をトランザクションの一部として単純に操作します。全ては完璧に動きます。実際には、多くの自明でない問題が起きます。それはTMシステムの実装の詳細によります。この問題を解決することはできますが、トランザクションの外で確保されるロックに対して４５％のオーバヘッドの増加、トランザクション内で確保されるロックに対して３００％のオーバヘッドの増加コストを要求します。このオーバヘッドは、少量のロックを持つトランザクションプログラムにとっては許容範囲かもしれませんが、たまにトランザクションを使いたいと願う本番品質のロックベースのプログラムにとってはしばしば全く許されません。
１ ロックに優しいTM実装だけを使います。不幸にも、ロックに優しくない実装はいくつかの素敵な性質を持ちます。それには、成功するトランザクションに対する低いオーバヘッドや、極端に大きなトランザクションを受け入れられることが含まれます。
２ TMをロックベースのプログラムに導入するときには、TMを「少しだけ」使います。そうすれば、ロックに優しくないTM実装の限界を受け入れられます。
訳注。原文は、優しいだけど、逆でしょう。
３ ロックベースのレガシーシステムは全部どけて、全てをトランザクションを使って再実装します。
このアプローチを賞賛する人はいつもいますが、それにはこの章で述べた全ての問題が解決されなくてはいけません。問題を解決するまでの間に、競合する同期機構も、もちろん、改善される機会を持ちます。
４ TMを、ロックベースのシステムでの最適化の一つに限定してして使います。これは、TxLinux グループが行なった事です。このアプローチは、健全に見えますが、ロック設計の限界(デッドロックを防ぐ必要があるなど)を未解決にそのまま残します。
５ ロックプリミティブの課すオーバヘッドを減らすようにがんばります。
TM とロックをインタフェースするときに、問題が起きうるという事実は、多くの人にとって驚きでした。それは、新しい機構とプリミティブを、本当の世界の本番ソフトウェアで試してみることが必要だということを裏付けました。幸運なことに、オープンソースの広まりは、そのような大量のソフトウェアが今では研究者を含む全ての人に自由に使用可能であることを意味します。
１６．２．３．２ リーダーライターロック
訳注。前節の最初のパラグラフを、リーダーライターロックにしただけで冗長なので省略。
不幸にも、トランザクション内から伝統的なカウンタベースのリーダーライターロックをリード確保する直裁的アプローチはリーダーライターロックの目的を損ないます。これを見るために、同じリーダーライターロックをリード確保しようとする同時実行する二つのトランザクションを考えましょう。リード確保はリーダーライターロックのデータ構造の変更を伴いますから、競合が起きます。それは二つのトランザクションの一つをロールバックします。このふるまいは、リーダーライターロックのゴールである、同時実行するリーダーを許すということと、完全に矛盾します。
以下は、TMに可能ないくつかの選択肢です。
１ CPUごと、あるいはスレッドごとのリーダーライターロックを使います。そうすれば、あるCPU（あるいはスレッド）はロックをリード確保するときにローカルデータだけを操作します。これにより、二つのトランザクションが同時にロックをリード確保するときの競合を防ぎます。そしてどちらも、期待通りに、進むことができます。不幸にも、（１)CPUあるいはスレッドごとのロックをライト確保するオーバヘッドはおそろしく高いです。（２）CPUあるいはスレッドごとのロックのメモリオーバヘッドはすごく高価です。（３）この変換は、問題のソースコードにあなたがアクセスできる時しか使えません。他の、より最近のスケーラブルなリーダーライターロックは、これらの問題の一部あるいは全てを回避できることがあります。
２ TMをロックベースのプログラムに導入するときには、TMを「少しだけ」使います。そうすれば、トランザクションの中からリーダーライターロックを確保するのを避けられます。
３ 訳注。前項の３と同じなので省略。
４ 訳注。前項の４と同じなので省略。
さらに、このアプローチは、複数のトランザクションが同じロックをリード確保しようとすると、不必要なトランザクションロールバックになることがあります。
もちろん、TMをリーダーライターロックと統合するためには、これ以外の自明ではない問題がまだたくさんある可能性があります。それは、排他ロックで実際にそうであったのと同じです。
１６．２．３．３ RCU
リードコピーアップデート(RCU)は、主にLinuxカーネルで使われているので、RCUとTMを組み合わせる学術的な研究はないだろうと思うのも無理はありません。
脚注
しかし、ユーザ空間RCUが広まるにつれ、カーネルだからという言い訳はできなくなりました。
しかし、テキサス大学オースチン校の TxLinux チームは選択肢がありませんでした。TMを、RCUを使う Linux2.6 カーネルに適用した結果、彼らは、TMとRCUを統合する以外にありませんでした。TMが、RCU更新のときのロックの代わりとなりました。論文には、RCU実装のロック(例えば、 rcu_ctrlblk.lock )が、トランザクションに変換された事は書かれていますが、不幸な事に、RCUベースの更新(例えば、dcache_lock) で、使われるロックがどうなったかは書いてありません。
RCUは、リーダーと更新者が同時に実行するのを許す事に注意するのは重要です。そうして、RCUリーダーは、今更新されている途中のデータをアクセスできます。もちろん、このRCUの性質は、その性能、スケーラビリティ、実時間応答性がどんなに優れていても、元となるTMのアトミックな性質と真っ向から対立するものです。
では、TMベースの更新は、同時実行するRCUリーダーとどのように相互作用するべきでしょう？いくつかの可能性は以下です。
１ RCUリーダーは同時実行する競合するTM更新をアボートします。これは、実は、TxLinux プロジェクトが取ったアプローチです。このアプローチは確かにRCUセマンティクスを保ちます。さらに、RCUのリード側性能、スケーラビリティ、実時間応答性も保ちます。しかし、それは競合する更新を不必要にアボートするという不孝な副作用も持ちます。最悪の場合、RCUリーダーの長いシーケンスが、全ての更新を飢餓させる潜在的可能性があります。それは理論的にはシステムハングになります。さらに、このアプローチを実装するのに必要な強アトミシティは、全てのTM実装で提供されるものではありません。
２ 競合するTM更新と同時実行するRCUリーダーは、競合するRCUロードの全てで、古い(トランザクションの前の)値を読みます。これは、RCUセマンティクスと性能を保ち、さらに、RCU更新の飢餓も防ぎます。しかし、全ての TM 実装が、実行中のトランザクションによって一時的に更新されている変数の古い値をタイムリーにアクセス可能だとは限りません。特に、古い値をログに維持する(そうすることで素晴らしいTMコミット性能が得られます)、ログベースのTM実装はこのアプローチは嬉しくはないでしょう。多分、rcu_dereference() プリミティブを活用することで、広い範囲のTM実装においてRCUが古い値をアクセスするのを可能とすることができるかもしれません。ただ、性能は問題でしょう。とはいえ、このようにしてRCUと簡単かつ効率よく統合できる著名なTM実装がいくつかあります。
３ RCUリーダーが実行中トランザクションと競合するアクセスをしたら、そのRCUアクセスは、競合するトランザクションがコミットあるいはあるいはアボートするまで遅延されます。このアプローチはRCUのセマンティクスを保ちますが、RCUの性能や実時間応答性は保ちません。特に、長く走るトランザクションがいるときにはそうです。さらに、全てのTM実装が競合するアクセスを遅延する能力を持つわけではありません。とはいえ、このアプローチは、小さなトランザクションだけをサポートするハードウェアTM実装にとっては素晴らしく合理的と思われます。
４ RCUリーダーをトランザクションに変換します。このアプローチは、RCUがどんなTM実装とも互換である事を完全に保証します。しかし、RCUリード側クリティカルセクションにTMのロールバックを強制し、RCUの実時間応答保証を破壊し、RCUのリード側性能を落とします。さらに、このアプローチは、RCUリード側クリティカルセクションのいずれかが、問題のTM実装が扱うことのできない操作を含むときには不可能です。
５ 多くのRCUの更新側用途は、単一のポインタを変更して、新しいデータ構造をパブリッシュします。これらの場合のいくつかでは、RCUは、後にロールバックされる、トランザクションによるポインタ更新を安全に見ることが許されます。なお、トランザクションがメモリオーダリングを尊重し、ロールバック処理で対応する構造体を解放するときに call_rcu() を使う限りにおいてです。不幸にも全てのTM実装がトランザクション内のメモリバリアを尊重するわけではありません。トランザクションはアトミックであるはずなので、トランザクションの中のアクセスの順序は問題となるはずがないというのが理由でしょう。
６ RCU更新でのTM使用を禁止します。これはうまくいく保証がありますが、ちょっと制限が強すぎるでしょう。
他のアプローチが発見されるのはありえます。特に、ユーザレベルのRCU実装が広まるにつれて。
脚注
これらの選択肢のいくつかを思いついた、TxLinux グループ、 Maged Michael,そして Josh Triplett に拍手。
１６．２．３．４ トランザクション外のアクセス
ロックベースのクリティカルセクションの中では、同時にアクセスされている変数や、ロックのクリティカルセクションの外で更新されている変数でさえ、それを操作するのは完璧に合法です。一つのよくある例は統計カウンタです。RCUリード側クリティカルセクション内でも同じことが可能で、それは実際、一般的なことです。
本番データベースシステムでよく使われる、いわゆる「ダーティリード」のような機構を考えれば、TMの賛同者が、トランザクション外のアクセスに真剣に注目してきたのは驚くことではありません。その一つの例をあげれば、弱そして強アトミシティ概念です。
TMに可能な、トランザクション外アクセスの選択肢をいくつかあげます。
1 トランザクション外のアクセスのための競合は常にトランザクションをアボートします。これが強アトミシティです。
２ トランザクション外のアクセスのための競合は無視されます。なので、トランザクション間の競合だけがトランザクションをアボートできます。これが弱アトミシティです。
３ トランザクションは、特別な場合だけ、トランザクションでない操作を実行することが許されます。それは、メモリ確保や、ロックベースのクリティカルセクションと相互作用する時などです。
４ ハードウェア拡張を作って、ある操作(例えば、加算)が、複数のトランザクションによって単一の変数に対して同時実行できるようにします。
５ トランザクショナルメモリに、弱いセマンティクスを導入します。一つのアプローチは、１６．２．３．３節で述べたRCUとの組み合わせです。また、Gramoli と Guerraoui は、多くの他の弱いトランザクションアプローチをサーベイしています。例えば、大きな"elastic" トランザクションを条件付きでより小さいトランザクションに分割することで、競合の確率を減らします(ただ、性能とスケーラビリティはいまひとつ)。今後の経験の結果、トランザクション外のアクセスのいくらかの用途は弱いトランザクションによって置換できる事が示されるかもしれません。
トランザクションはスタンドアロンで、他のどんな同期機構とも相互作用しないものだと考えられてきたようです。もしそうなら、トランザクションをトランザクションでないアクセスと組み合わせる時に多大な混乱と複雑さが起きるのも驚く事ではありません。しかし、トランザクションが、孤立したデータ構造の小さな更新に閉じ込められるか、あるいは、既存の並列コードの大きな中心部と相互作用しない新しいプログラムに閉じ込められるのでない限り、近い将来に大規模な現実的インパクトを与えようとするならば、トランザクションは絶対に、前述したように組み合わされる必要があります。
１６．２．４ 議論
TMの普遍的受容への障害となるものは以下です。
１ TMの興味深い性質の一つは、トランザクションがロールバックとリトライを必要とするという事実です。この性質のために、バッファされないI/O、RPC、メモリマップ操作、時間遅延、そして exec() システムコールなどの取り消し不可能な操作に対するTMの困難が起きます。さらにこの性質は、しばしば開発者に見える形で、同期プリミティブが失敗する可能性があることから来る全ての複雑さを導入するという、不幸な結果ももたらします。
２ TMのもう一つの興味深い性質、 Shpeisman 達によれば、は、TMは、同期をそれが守るデータと一緒に練り合わせていることです。この性質のために、I/O、メモリマッピング操作、トランザクション外のアクセス、そしてデバッグブレークポイントに対するTMの問題が起きます。それに対して、ロックやRCUを含む今までの同期プリミティブは、同期プリミティブとそれが守るデータを明確に分離しています。
３ TM領域で働く多くの人々の明言されたゴールの一つは、大きなシーケンシャルプログラムの並列化を容易にすることです。そうであれば、個々のトランザクションはシリアルに実行することが一般的に期待されますから、TMがマルチスレッドトランザクションで持つ問題も説明がつくでしょう。
TM 研究者と開発者は、これら全てに対してどうしたらいいでしょう?
一つのアプローチは、小さい領域のTMに集中することです。ハードウェア補助が、他の同期プリミティブに対して、大きな利点を与える潜在性のある状況に集中することです。これは実際、Sun がその Rock 研究で採用したアプローチです。TM 研究者にはこのアプローチに同意するものもいるようです。TM によりずっと高い望みを抱く研究者もいます。
もちろん、TMがより大きな問題を引き受けることができるようになる可能性も十分あります。そしてこの節は、TMがこの大きなゴールを得るために解決しないといけない問題のいくつかを列挙しました。
もちろん、関連する全ての人はこれを学習の経験だと扱うべきです。TM研究者は、伝統的な同期プリミティブを使って巨大なソフトウェアシステムを構築するのに成功した実務家から多くを学んだようです。
そして、逆も真です。
しかし、今のところは、STMの現在の状況は、以下の何枚かのマンガによって最も適切に要約されていると言えるでしょう。まず、図１６．８は、STMの幻想を示します。いつものことながら、現実はそれより少し複雑です。図１６．９，１６．１０，１６．１１に楽しく描かれる通りです。
訳注。マンガのセリフの訳。
１６．８ おい、TMは完全にロックを打ち負かすよね。（beat というのは、卵を混ぜること。）
ほんとだよね、このデッドロックは嫌だったんだ。
１６．９ 今日で３度目でないか?
でも裁判長、多くのレシピが卵を必要としているのです！
１６．１０ 静粛に。この競合を解決するために君たちのうち２人はロールバックしないといけない！
やったぜ！あばよお前ら！
なんと *#$! 割って混ぜた卵を元に戻せと言われるのですか?
。。。あなたは私に切ったソーセージを元に戻せと言われるのですか？
１６．１１ 静粛に。この競合を解決するために君はロールバックしないといけない！
私をロールバックし続けると、私のスフレは失敗してしまいます！
商用利用可能なハードウェアの最近の進歩は、HTMのいくつかの変種への扉を開きました。以下の節でそれらを紹介します。
１６．３ ハードウエアトランザクショナルメモリ
２０１２年初頭、ハードウエアトランザクショナルメモリ (HTM) が、商用利用可能なコモディティー計算機システムに現れようとしています。この節は、並列プログラマの道具箱で、その場所を考える最初の試みをします。
概念的観点で言えば、HTM は、プロセッサのキャッシュと投機実行を使って、指定された命令のグループ(一つの「トランザクション」)が、他のプロセッサで動いている他の全てのトランザクションの観点からはアトミックに効果を発揮するようにします。このトランザクションは、トランザクション開始機械命令で始まり、トランザクションコミット機械命令で完了します。典型的には、トランザクションアボート機械命令もあり、投機を廃棄して、(あたかも、トランザクション開始命令とその後の全ての命令が実行されなかったかのように)失敗ハンドラの実行を始めます。失敗ハンドラの位置は、典型的にはトランザクション開始命令で与えます。それは、明示的な失敗ハンドラのアドレスのことも、その命令自身が設定するコンディションコードを使うこともあります。それぞれのトランザクションは、他の全てのトランザクションから見て、アトミックに実行します。
HTMは多くの重要な利点があります。それには、データ構造の自動的ダイナミックな分割、同期プリミティブのキャッシュミスの削減、そして多くの実用的適用先のサポートがあります。
しかし、素敵な文書を読むことは、常に報われます。HTMも例外ではありません。この節の要点は、どのような条件のもとで、HTMの利点が、素晴らしい文書に隠された複雑さを上回るかを決めることです。そのため、１６．３．１節はHTMの利点を述べ、１６．３．２節はその弱点を述べます。これは、以前の論文で使ったのと同じアプローチですが、TM全体でなくて、HTMに焦点を当てています。
脚注
そして私は、その他の著者、Maged Michael, Josh Triplett, そして Jonathan Walpole, また Andi Kleen との多くの刺激的な議論に大いに感謝します。
１６．３．３節は、Linuxカーネル(と、いくつかのユーザ空間アプリケーション)で使われている同期プリミティブの組み合わせに関する、HTMの弱点を述べます。１６．３．４節で、HTMが並列プログラマの道具箱で一番適した場所を考えます。そして、１６．３．５節は、HTMのスコープと魅力を大いに増すかもしれないイベントをいくつか列挙します。最後に、１６．３．６節はまとめです。
１６．３．１ ロックに対するHTMの利点
HTMの主な利点は、以下です。(1)他の同期プリミティブでよく引き起こされるキャッシュミスがありません。(2)データ構造をダイナミックに分割できます。(3)とても多くの現実的適用先があります。私は、TMで伝統的に言われる使いやすさをあげませんでした。これは以下の２つの理由があります。最初に、HTMの使いやすさは、この論文が焦点を当てているHTMの主な利点に基づくべきです。次に、生のプログラミング能力をテストしようと試みたり、採用面接で小さなプログラム演習を使うことについて、大変な論争がありました。これは、私たちが、何がプログラミングを簡単にしたり困難にしたりするかについて、実際にわかっていないことを示します。なので、この論文では、前記の３つの利点に焦点を当てます。以下の節で一つづつ扱います。
１６．３．１．１ 同期のキャッシュミスを避ける
ほとんどの同期機構は、アトミック命令で操作されるデータ構造を基礎とします。これらのアトミック命令は、通常は最初に、自分が動いているCPUが、関連するキャッシュラインを持つように動作しますから、その同期プリミティブの同じインスタンスがその後どこか別のCPUで動くと、キャッシュミスを起こします。これら、コミュニケーションによるキャッシュミスは、通常の同期機構の性能とスケーラビリティを著しく落とします。
それに対して、HTMはCPUのキャッシュを使って同期しますから、同期のためのデータ構造も、その結果となるキャッシュミスも必要としません。HTMの有効性は、ロックデータ構造が別々のキャッシュラインに置かれる状況で最大になります。その場合、あるクリティカルセクションをHTMトランザクションにすることで、そのクリティカルセクションのオーバヘッドを一つのキャッシュミスにすることができます。この削減効果は、一般的な場合である短いクリティカルセクションの時にとても重要となりえます。少なくても、削除されたロックが、それが保護するしばしば書かれる変数とキャッシュラインを共有しない状況に於いて。
クイッククイズ１６．２
なぜ、しばしば書かれる変数がロック変数とキャッシュラインを共有するかどうかが重要なのですか？
１６．３．１．２ データ構造のダイナミックな分割
いくつかの一般的な同期機構を使うことに対する主な障害は、データ構造を静的に分割しなければいけないことです。分割が自明にできるデータ構造もいくつかあります。その最も顕著な例はハッシュテーブルで、それぞれのハッシュチェーンが分割を構成します。それぞれのハッシュチェーンにロックを与えれば、ハッシュテーブルを、あるチェーンに閉じた操作に対して並列化するのは自明です。
脚注
そして、この枠組みを、複数のハッシュチェーンをアクセスする操作に拡張するのも簡単です。そのような操作が、ハッシュオーダーで、関連する全てのチェーンのロックを取れば良いのです。
配列、radix tree、そしていくつかの他のデータ構造にとっても、分割は同様に自明です。
しかし、多くの木とグラフのタイプを分割するのはとても難しく、その結果はしばしば、とても複雑です。一般的なデータ構造を分割するのに、２相ロックと、ロックのハッシュ配列を使うこともできますが、１６．３．３節で述べるように、他のテクニックの方が好ましいことがわかっています。HTMは同期キャッシュミスを避けますから、大きな分割不可能なデータ構造にとって、それはとても現実的な可能性です。少なくても、比較的更新が少ない時は。
クイッククイズ１６．３
HTMの性能とスケーラビリティにとって、比較的更新が少ないことがなぜ重要なのですか？
１６．３．１．３ 現実的価値
HTMの現実的な価値の証拠は、多くのハードウエアプラットホームで示されてきました。それには、Sun Rock, Azul Vega が含まれます。現実的な利点は、より最近の、IBM Blue Gene/Q, Intel Haswell TSX, そして AMD AFS システムにも及ぶだろうと考えるのはもっともです。
期待される現実的利点には、以下があります。
１ メモリ上のデータアクセスと更新での、ロックの省略
２ 大きな、分割不可能なデータ構造への同時アクセスと、小さいランダムな更新。
しかし、HTMはいくつかのとても現実的な欠点も持ちます。これについては次の節で。
１６．３．２ ロックに比べた時のHTMの弱点
HTMの概念はとても単純です。メモリへのアクセスと更新のグループがアトミックに起きます。しかし、単純なアイディアの多くでそうであるように、あなたがそれを本当の世界の本当のシステムに適用するとき、面倒な問題が現れます。問題は以下です。
１ トランザクションサイズの限界
２ 競合の扱い
３ アボートとロールバック
４ 前方進行保証の欠如
５ 取り消しできない操作
６ セマンティクスの違い
以下の節で、これらの問題を取り上げます。最後はまとめです。
１６．３．２．１ トランザクションサイズの限界
現在のHTM実装のトランザクションサイズの限界は、そのトランザクションで影響があるデータを保持するのにプロセッサのキャッシュを使っていることによります。これによって、あるCPUは、トランザクションを自分のキャッシュの囲いの中で実行することで、他のCPUからはアトミックに見えるようにすることができます。しかしそれは、入りきらないトランザクションは皆、アボートされないといけないことを意味します。さらに、実行コンテキストを変えるイベント、例えば、割り込み、システムコール、例外、トラップ、そしてコンテキストスイッチは、以下のいずれかを引き起こします。問題のCPUで実行していた全てのトランザクションをアボートするか、あるいはもう一つの実行コンテキストのキャッシュフットプリントのために、さらにトランザクションサイズを制限するかです。
もちろん、現代的なCPUは大きなキャッシュを持つことが多いですし、多くのトランザクションで必要なデータは、１メガバイトのキャッシュに容易に入るでしょう。不幸にも、キャッシュにおいては、単純なサイズだけが重要なのではありません。問題はこうです。ほとんどのキャッシュはハードウェアで実装されたハッシュテーブルと考えることができます。しかし、ハードウェアキャッシュはバケツ（普通は、セットと呼ばれます）をチェーンせず、セットごとに固定数のキャッシュラインを提供します。あるキャッシュのそれぞれのセットが持つ要素の数は、そのキャッシュのアソシアティビティと呼ばれます。
キャッシュのアソシアティビティにはいろいろありますが、私がこれをタイプしているラップトップのレベル０キャッシュが８−ウェイアソシアティブというのは、珍しいものではありません。これが意味するのは、もしあるトランザクションが９つのキャッシュラインを触る必要があり、９つのキャッシュライン全てが同じセットにマップしたなら、そのトランザクションはたぶん完了できないということです。そのキャッシュに、何メガバイトの余分な領域があっても関係ありません。そうです。あるデータ構造の中でランダムに選択したデータ要素を取ってみれば、そのトランザクションがコミットできる可能性はとても高いです。しかし、保証は何もありません。
この制限を緩和する研究がありました。完全アソシアティブの victim cache ならば、アソシアティビティの制限は緩和されるでしょうが、現在は、victim cache の大きさに性能とエネルギー効率の厳しい制限があります。とはいっても、変更されていないキャッシュラインのための HTM victim cache はとても小さくて済みます。アドレスだけを記憶すればいいからです。データ自身はメモリに書いても、他のキャッシュにシャドウしてもよく、競合するライトを検出するにはアドレス自身で十分です。
Unbounded transactional memory (UTM) スキーマは、DRAM をとても大きな victim cache に使います。しかし、そのようなスキーマを、本番品質のキャッシュコヒーレンス機構に統合するのは、いまだ未解決の問題です。さらに、DRAM を victim cache に使うのは、性能とエネルギー効率の点で不幸な結果になるかもしれません。特に、victim cache が完全アソシアティブであるならば。最後に、UTM の「限界のない」面は、全てのDRAMが victim cache に使えることを前提としますが、実際には、あるCPUに割り当てられた、巨大であっても固定量のDRAMは、そのCPUのトランザクションのサイズを制限するでしょう。他のスキーマは、ハードウェアとソフトウェアトランザクショナルメモリの組み合わせを使います。これは、STMを、HTMのフォールバック機構として使うのだと考えることができます。
しかし、私の知る限り、現在入手可能なシステムは、これらの研究アイデアをどれも実装していません。それにはたぶん、もっともな理由があるのでしょう。
１６．３．２．２ 競合を扱う
最初の面倒な問題は、競合の可能性です。例えば、トランザクション A と B が次のように定義されているとします。
Trasaction A Transaction B
x = 1; y = 2;
y = 3; x = 4;
それぞれのトランザクションは、自分自身のプロセッサでそれぞれ同時実行するとします。もしトランザクション A が、トランザクション B が y に格納するのと同じ時に x に格納したら、どちらのトランザクションも進めません。それを説明するために、トランザクション A が y への格納を実行したとしましょう。すると、トランザクション A はトランザクション B にインタリーブされることになり、トランザクションが互いにアトミックに実行しなくてはいけないという要件を破ります。トランザクション B が x への格納を実行すると考えても、同様にアトミック実行の要件を破ります。この状況は、競合と名付けられました。それは、２つの同時実行するトランザクションが同じ変数をアクセスし、少なくても一つがストアであるならばいつでも起きることがあります。システムは、実行が進むためには、トランザクションの一つあるいは両方をアボートしなくてはいけません。実際にどっちのトランザクションをアボートさせるかという選択は面白い問題で、ここしばらくの間は、博士号を取ることのできる問題であり続けるでしょう。例えば、[ATC+11] を見て下さい。
脚注
Liu と Spear の論文 “Toxic Transactions”は、この問題について、とても勉強になります。
この節の目的のためには、システムはランダムな選択をすると思っておいてかまいません。
もうひとつの面倒な問題は、競合を検出することです。それは、少なくても最も単純な場合には比較的直裁的です。プロセッサは、トランザクションを実行中は、そのトランザクションが触る全てのキャッシュラインに印をつけます。もし、プロセッサのキャッシュが、現在実行中のトランザクションが触ったと印が付いているキャッシュラインを含む要求を受けたならば、潜在的競合が起きたとわかります。より洗練されたシステムは、現在のプロセッサのトランザクションを、キャッシュ要求を送ってくるプロセッサのトランザクションよりも前に来るように並べなおそうとするかもしれません。そして、この処理を最適にするのは、またしても、当分の間、博士号を取ることのできる問題であり続けるでしょう。しかし、この節では、とても単純な競合検出戦略を取るとしましょう。
しかし、HTM が効率よく働くためには、競合の確率はとても低くないといけません。それはまた、データ構造が十分に低い競合を維持できるように構造化されている必要があるということです。例えば、単純な挿入、削除と検索操作ができる赤黒木はこれを満たします。しかし、木の要素数の正確なカウンタを維持する赤黒木はそうではありません。
脚注
カウンタを更新しなくてはいけないために、木への追加と削除はお互いに競合し、強い non-commutativity を起こします。
もうひとつの例としては、木の全ての要素を単一のトランザクションで列挙する赤黒木は、高い競合の確率を持ち、性能とスケーラビリティを落とすでしょう。つまり、多くのシリアルプログラムは、HTM が効率よく働くためには何らかの再構成を必要とするでしょう。ある場合には、実務家は追加の手順（赤黒木の場合、radix tree やハッシュテーブルのような分割可能なデータ構造に変えるなど）を踏んで、単純にロックを使うことにするかもしれません。特に、HTM が全ての関係あるアーキテクチャですぐに使える状態にあるようになる前には。
クイッククイズ１６．４；
赤黒木で、同期機構の選択にかかわらす、効率的に全ての木の要素を列挙するにはどうしたらいいでしょう？？？
さらに、競合が起きる可能性があるという事実は、全体図の中に、エラー処理を持ち込みます。これについては次の節で。
１６．３．２．３ アボートとロールバック
いかなるトランザクションも、いつでもアボートされるかもしれないので、トランザクションが、取り消せない文を含まないことは重要です。ということは、トランザクションはI/O、システムコール、それにデバッグブレークポイント（HTMトランザクションでは、デバッガ下のシングルステップ実行はできません！！！）をしてはいけないということです。そしてトランザクションは通常のキャッシュされたメモリをアクセスすることに、自身を閉じ込めないといけません。さらに、システムによっては、割り込み、例外、トラップ、TLB ミス、そしてその他のイベントもトランザクションをアボートします。エラー条件を正しく処理しなかったことによるバグの多さを考えると、アボートとロールバックが、使いやすさにどれだけのインパクトを与えるかを問うのは公平でしょう。
クイッククイズ１６．５：
トランザクションの全ての行にブレークポイントをかければ、デバッガはシングルステップをエミュレートできるのではないでしょうか？リトライは以前のトランザクションのインスタンスの取ったステップを再実行するでしょうから。
訳注。ブレークポイントによってトランザクションは中断されてアボートするが、リトライで最初の行からその行までを再実行するから、これを繰り返せば一行ずつ進んでいけます。
もちろん、アボートとロールバックは、HTM はハードリアルタイムシステムで使えるかという問題を提起します。HTM の性能向上は、アボートとロールバックのコストを越えるでしょうか？もしそうなら、どういう条件のもとで？トランザクションは優先度ブーストを使えるでしょうか？それとも、高優先度スレッドのためのトランザクションは、その代わりに優先的に低優先度のスレッドのトランザクションをアボートするべきでしょうか？もしそうなら、ハードウェアに効率的に優先度を伝えるにはどうしますか？HTM のリアルタイム使用についての論文はとてもわずかです。これは研究者が、リアルタイムでない環境でトランザクションをうまく働かせるために、十分以上の問題を見つけているのが理由かもしれません。
現在のHTM 実装はあるトランザクションを決定論的にアボートするかもしれないので、ソフトウェアはフォールバックコードを用意する必要があります。このフォールバックコードは、何か他の形の同期を使わなくてはいけません。例えば、ロックのような。もしフォールバックコードがひんぱんに使われるなら、デッドロックの可能性を含む、ロックの全ての限界が再び現れます。もちろん、このフォールバックはひんぱんには使われないと考えることはでき、その結果、より単純でデッドロックの可能性が少ないロック設計を使うこともできるかもしれません。しかしここで、システムがロックベースのフォールバックから、トランザクションにどのように遷移するかという問題が起きます。
脚注
アプリケーションが、フォールバックモードから抜け出せない可能性のことを、“lemming effect”と呼びます。 Dave Dice が名づけました。
一つのアプローチは、test-and-test-and-set 規約を使うことです。そうすれば、全ての人が、ロックが放されるまで待ちますから、システムはその時点から、トランザクショナルモードでクリーンに開始することができます。しかし、これは多量のスピニングになることがあり、ロック保持者がブロックしたり、プリエンプトされた場合には、賢明ではありません。もう一つのアプローチは、トランザクションが、ロックを保持しているスレッドと並行して進むのを許します。しかしこれは、アトミシティを維持するのを難しくします。特に、スレッドがロックを持っている原因が、対応するトランザクションがキャッシュに入りきらないためであるときにはそうです。
最後に、アボートとロールバックの可能性と対処するのは、開発者に追加の負担を与えるようです。開発者は、可能なエラー条件の全ての組み合わせを正しく扱わなくてはいけません。
HTM の使用者が、フォールバックコードのパスと、フォールバックコードからトランザクションコードに戻る遷移の両方をテストするのに、十分な検証努力をしなくてはいけないのは明らかです。
１６．３．２．４ 前方進行保証の欠如
トランザクションサイズ、競合、そしてアボートとロールバックが全て、トランザクションをアボートする可能性があるとしても、十分に小さく、短期間のトランザクションは最終的には成功する保証があると期待できるのではないでしょうか。そうすれば、トランザクションを無条件にリトライするのも許されます。これは、compare-and-swap (CAS) と load-linked/store-conditional (LL/SC) 操作が、これら命令を使ってアトミック操作を実装するコードにおいて無条件にリトライされるのと同じです。
不幸にも、現在入手可能なほとんどの HTM 実装はいかなる前方進行保証も提供するのを拒否しています。ということは、HTM はこれらのシステムではデッドロックを防ぐために使うことはできないということです。
脚注
HTM はデッドロックの可能性を小さくするために使われるのは十分ありえます。しかし、フォールバックコードが実行される確率が少しでもあるうちは、デッドロックの確率もあります。
未来のHTM 実装は、きっとなんらかの前方進行保証を提供することが期待されます。その時までは、HTM はリアルタイムアプリケーションで使うためは、特別の注意が必要です。
脚注
２０１２年の中頃では、トランザクショナルメモリのリアルタイム属性については驚くほど研究がされていません。
２０１３年時点でのこの暗い全体図の一つの例外は、IBM メインフレームの次のバージョンです。それは、特別の制限されたトランザクションを開始するために使うことのできる個別の命令を持ちます。その名前からわかるように、そのようなトランザクションは、以下の制限のもとで生きなくてはいけません。
１ 各トランザクションのデータフットプリントは４つの３２バイトメモリブロック内に含まれなくてはいけません。
２ 各トランザクションが実行できる最大のアセンブラ命令数は、３２です。
３ トランザクションは後ろ向きの分岐を持ってはいけません（つまり、ループ無し）。
４ 各トランザクションのコードは２５６バイトのメモリに制限されます。
５ もしあるトランザクションのデータフットプリントの一部がある４Kページ内にあるならば、その４K ページはそのトランザクションの命令を何も含んではいけません。
これらの制限は厳しいです。しかし、それでも広い種類のデータ構造を更新する実装が可能です。それには、スタック、キュー、ハッシュテーブルなどが含まれます。これらの操作は最終的には完了することが保証されますから、デッドロックもライブロックも起き得ません。
時とともに、前方進行保証のハードウェアサポートがどのように進化していくかを見るのは興味深いことでしょう。
１６．３．２．５ 取り消し不可能操作
アボートとロールバックのもうひとつの結果は、HTM トランザクションは、取り消し不可能操作を含むことができないことです。現在の HTM 実装は、典型的にはこの制限を、トランザクション内の全てのアクセスが、キャッシュ可能メモリであり、（これによりMMIO は禁止されます）割り込み、トラップそして例外でトランザクションをアボートする（これによりシステムコールは禁止されます）ことで強制します。
なお、バッファドI/O は、HTM トランザクションに含めることができることに注意下さい。ただし、バッファのフィルとフラッシュ操作はトランザクションの外でされる必要があります。これが許される理由は、バッファにデータを加えたり除いたりする操作は取り消し可能だからです。実際のバッファのフィルとフラッシュ操作だけが取り消し不可能です。もちろん、このバッファドI/Oアプローチは、I/Oをトランザクションのフットプリントに含める効果を持ちますから、トランザクションのサイズを増し、失敗の可能性を増やす影響があります。
１６．３．２．６ セマンティクスの違い
HTMは多くの場合、ロックをそのまま代替できるものとして使われますが、(なので、トランザクショナルロック除去と呼ばれます。)セマンティクスの微妙な違いがあります。Blundell は、トランザクションで実行するとデッドロックやライブロックになる、調整されたロックベースのクリティカルセクションを含む、特別に面倒な例を指摘しました。でも、ずっと単純な例は、空のクリティカルセクションです。
ロックベースのプログラムでは、空のクリティカルセクションは、以前にそのロックを持っていた全てのプロセスが今はそれを放していることを保証します。この慣用句は、2.4Linux カーネルのネットワーキングスタックで設定の変更を調停するために使われました。しかし、この空のクリティカルセクションがトランザクションに変換されると、その結果は noop です。全ての以前のクリティカルセクションが終わったという保証は失われます。言葉を代えれば、トランザクショナルロック除去はロックのデータ保護セマンティクスを保ちますが、ロックの時間ベースのメッセージセマンティクスを失います。
クイッククイズ１６．６：
でも、なぜ、空の、ロックベースのクリティカルセクションを必要とする人なんているのですか？？？
クイッククイズ１６．７：
トランザクショナルロック除去で、ロックの時間ベースのメッセージセマンティクスを得るには、単純に、空の、ロックベースのクリティカルセクションを除去しなければいいんじゃないですか？
クイッククイズ１６．８：
現代的なハードウェアにおいて、タイミングに依存する並列ソフトウェアがうまく動くなんて、期待できるのでしょうか？
ロックとトランザクションの一つの重要なセマンティクスの違いは、ロックベースのリアルタイムプログラムで使われる、優先度逆転を防ぐための優先度ブーストです。優先度逆転が起きる一つの例は、ロックを持っている低優先度のスレッドが、中優先度のCPUバウンドのスレッドによってプリエンプトされる時です。もし全てのCPUで少なくても一つのそのような中優先度のスレッドがいるならば、低優先度のスレッドは決して走る機会がありません。もしも高優先度のスレッドがそのロックを取ろうとしたら、ブロックします。それは、低優先度のスレッドがロックを放すまでそれを取ることはできませんし、低優先度のスレッドは走る機会が与えられなければロックを放せませんし、それは、中優先度のスレッドの一つが自分の CPU を明け渡すまで走る機会がありません。なので、中優先度のスレッドは結果的に高優先度のスレッドをブロックしており、それが「優先度逆転」という名前の理由です。
優先度逆転を防ぐ一つの方法は、優先度継承です。そこでは、ロックによりブロックした高優先度のスレッドは一時的に自分の優先度をロック保持者に与えます。これを、優先度ブーストとも呼びます。しかし、優先度ブーストは、図１６．１２が示すように、優先度逆転以外の事にも使えます。この図の１から１２行目は、低優先度のプロセスです。ただし、ほぼ１ミリ秒ごとに走る必要があります。そして、その図の１４から２４行目は、高優先度のプロセスで、boostee() が必要に応じて定期的に走るのを保証するために優先度ブーストを使います。
boostee() 関数はこれを、常に、boost_lock のどちらかを保持することで実現します。なので、 booster() の２０から２１行めは必要に応じて優先度をブーストします。
クイッククイズ１６．９：
でも、図１６．１２の boostee() 関数はロックを交互にとっているので、逆順になることがあります！これはデッドロックになりませんか？
この機構では、システムがビジーになる前に、boostee() が５行目で最初のロックを取る必要があります。これは、現代的なハードウェアにおいても、用意に保証できます。
不幸にも、この機構は、トランザクショナルロック除去のもとでは破綻します。boostee() 関数のオーバーラップするクリティカルセクションは、一つの無限のトランザクションになります。それは遅かれ早かれアボートします。例えば、boostee() 関数を実行中のスレッドが最初にプリエンプトされた時に。この時点で、boostee() はロッキングにフォールバックするでしょうが、それは低優先度ですし、静かな初期化期間は終わっているので（それがそもそも、boostee() がプリエンプトされた原因です）このスレッドは再び走る機会を得ることはけっしてないでしょう。
そして、もし boostee() スレッドがロックを持っていないなら、図１６．１２の２０と２１行目の booster() スレッドの空のクリティカルセクションは空のトランザクションとなり、効果を持ちません。なので、boostee() が走ることはありません。この例は、トランザクショナルメモリのロールバックとリトライのセマンティクスの微妙な結果のいくらかを明らかにしました。
経験を重ねるにつれて他にも微妙なセマンティクスの違いが見つかるのはあり得ることでしょうから、大きなプログラムに HTM ベースのロック除去を適用するのは、注意して行わないといけないでしょう。
１６．３．２．７ まとめ
HTMが重要なユースケースを持つだろうことは十分ありえるでしょうが、現在の実装は、トランザクションサイズの制限、競合を扱う時の面倒さ、アボートとロールバック、そしてセマンティクスの違いに重大な問題を持ち、それらは注意深い扱いが必要です。表１６．１に、ロックと比べたHTMの現在の状況をまとめました。おわかりのように、現在のHTMの状態は、ロックのいくつかの重要な欠点を緩和しますが、それによって、自身の多数の欠点をもたらします。TMコミュニティーのリーダー達は、これらの欠点に気がついています。
脚注
公平に言うなら、ロックの欠点には、よく知られ、多く使われてきた技術的ソリューションが確かにあることを強調するのは重要です。それには、デッドロック検出器、ロックに適応した多くのデータ構造、そして、１６．３．３節で議論する強化の長い歴史が含まれます。さらに、多くの学術論文をさらっと見た人が合理的にそう思わされるほどに、ロックが本当にひどいものであるなら、全ての巨大なロックベースの並列プログラム（FOSSも、プロプライエタリも）はいったいどこから来たというのでしょう？
脚注
また、２０１１年初頭に私は、トランザクショナルメモリの元となるいくつかの仮定に対する批判をする講演に招かれました。聴衆は驚くほど友好的でしたが、それはたぶん、私が発表の時にひどい時差ボケだったために手加減してくれたのかもしれません。
さらに、話はこれで終わりではありません。ロックは普通は単独では使われません。参照カウンティング、アトミック操作、ノンブロッキングデータ構造、ハザードポインタ、それにリードコピーアップデート（RCU）を含む他の同期機構によって強化されるのが典型的です。次の節で、その強化がどのように等式を変えるかを調べます。
１６．３．３ 強化されたロックに比べた時のHTMの弱点
実務家達は長いこと、参照カウンティング、アトミック操作、ノンブロッキングデータ構造、ハザードポインタ、それにRCUを使って、ロックの欠点のいくらかを回避してきました。例えば、デッドロックは多くの場合、データ構造を守るために参照カウント、ハザードポインタ、あるいはRCUを使うことで避けることができます。リードオンリーのクリティカルセクションの場合は顕著です。これらのアプローチはデータ構造を分割する必要性も減らすことができます。RCUはさらに、競合のない、待ちもないリード側プリミティブを提供します。これらの考察を表１６．１に加えると、強化されたロックとHTMの比較を示す、更新された表１６．２になります。２つの表の違いの要約は以下です。
１ ノンブロッキングなリード側機構を使うと、デッドロック問題は起きません。
２ ハザードポインタやRCUのようなリード側機構は、分割不可能なデータに対して効率的に動作します。
３ ハザードポインタとRCUは互いに、あるいは、更新と、競合しません。このため、リードがほとんどのワークロードで素晴らしい性能とスケーラビリティが得られます。
４ ハザードポインタとRCUは前方進行保証（それぞれ、ロックからの自由と待ちからの自由）をもたらします。
５ ハザードポインタとRCUをプライベート化するのは直裁的です。
もちろん、次の節で述べるように、HTMを強化することも可能です。
１６．３．４ HTM はどこに最も適しますか？
HTMの適用範囲を、２０１ページの図９．３４のRCUのように、明確に描くことができるのは、しばらく先のことでしょうが、その方向に動き始めない理由はありません。
HTMは、巨大なマルチプロセッサで動き、比較的大きなメモリ上データ構造の、バラバラの部分に、比較的小さな変更を行う、更新がヘビーなワークロードに最適だと思われます。これならば、現在のHTM実装のサイズ制限に合いますし、競合と、その結果起きるアボートとロールバックの確率も最小にできます。このシナリオは、現在の同期プリミティブでは扱いが比較的難しいものの一つです。
HTMをロックと一緒に使うのは、HTMの取り消し不可能操作に関する困難を解決してくれそうです。また、RCUあるいはハザードポインタと一緒に使うのは、データ構造の大きな部分をトラバースするリードオンリー操作の時の、トランザクションサイズの制限を緩和してくれそうです。現在のHTM実装は、RCUあるいはハザードポインタリーダーと競合する更新トランザクションを、無条件にアボートします。しかし、将来のHTM実装は、これら同期機構とよりスムーズに協調するようになるかもしれません。一方、大きなRCUあるいはハザードポインタのリード側クリティカルセクションと更新が競合する確率は、同様のリードオンリートランザクションと競合する確率よりもずっと小さいはずです。
脚注
共用メモリシステムで厳格なトランザクション機構が現れてきたのとほぼ同時に、NoSQL データベースが、厳格なトランザクションへの、伝統的なデータベースアプリケーションの依存をゆるめているのは、とても皮肉なことです。
それでも、RCUあるいはハザードポインタリーダーの恒常的なストリームが、結果となる恒常的な競合のストリームのために、更新者を飢えさせるのはとてもあり得ることです。この脆弱性は、(多分、多大なハードウェアコストと複雑さを払えば)ロードされるメモリ位置のトランザクション前のコピーをトランザクションの外で読むことで除くことができます。
HTMトランザクションがフォールバックを持たなくてはいけないという事実は、ある場合には、HTMに対して逆に、データ構造の静的分割可能性を強制することもあるかもしれません。もし将来のHTM実装が前方進行保証を提供するなら、この制限は緩和できるでしょう。それはある場合にはフォールバックコードを不要とし、その結果、より大きな競合の確率がある状況でも、HTMが効率的に使えるようになるかもしれません。
つまり、HTMは重要な用途とアプリケーションを持つでしょうが、それは並列プログラマの道具箱のもう一つのツールであって、道具箱全部の代わりとなるものではありません。
１６．３．５ 潜在的にゲームを変える能力のあるもの
HTMの必要性を大きく増すかもしれない、ゲームを変える能力のあるものは以下です。
１ 前方進行保証
２ トランザクションサイズの増加
３ デバッグサポートの改善
４ 弱いアトミシティ
以下の節でこれらを説明します。
１６．３．５．１ 前方進行保証
１６．３．２．４節で述べたように、現在のHTM実装は前方進行保証がありません。なので、HTM失敗を処理するためにフォールバックソフトウェアが必要です。もちろん、保証を求めるのは簡単ですが、それを提供するのは常に簡単とは限りません。HTMの場合、障害となるのは、キャッシュサイズとアソシアティビティ、TLBサイズとアソシアティビティ、トランザクションの長さと割り込みの頻度、そして、スケジューラ実装などです。
キャッシュサイズとアソシアティビティについては、１６．３．２．１節で、現在の限界を回避するための研究のことも含めて議論しました。しかし、HTM前方進行保証が、大きさの限界を持つとしても、いつの日にかはその限界も十分大きいと思える日が来ることでしょう。なので、なぜ、現在のHTM実装は小さなトランザクションに対して前方進行保証を提供しないのでしょう？例えば、キャッシュのアソシアティビティの範囲に限ってでも。
潜在的理由の一つは、ハードウエア故障に対処するためでしょう。例えば、キャッシュSRAMセルが故障したら、そのセルをデアクティベートするでしょう。すると、キャッシュのアソシアティビティが減り、前方進行保証できるトランザクションの最大サイズも減ります。これは単に、保証できるトランザクションサイズを減らすだけですが、他の理由もいろいろあるだろうことは想像できます。多分、本番品質のハードウエアで前方進行保証を提供するのは、皆が考えているよりずっと難しいのでしょう。ソフトウェアで前方進行保証を提供するのが難しいことが、その十分な説明になっています。問題をソフトウェアからハードウエアに移しても、解くのが簡単になるわけではありません。
物理的にタグおよびインデックスされたキャッシュでは、トランザクションがキャッシュに収まるだけでは不十分です。そのアドレス変換も、TLBに入らないといけません。なので、前方進行保証は皆、TLBサイズとアソシアティビティも考慮しなければいけません。
現在のHTM実装では、割り込み、トラップ、そして例外はトランザクションをアボートしますから、あるトランザクションの実行時間は、予想される割り込み間隔より短くないといけません。トランザクションの触るデータがどんなに少なくても、長く走りすぎるとアボートされます。なので、前方進行保証は皆、トランザクションサイズだけでなく、トランザクションの長さにも依存します。
前方進行保証は、いくつかの競合するトランザクションのどれをアボートするべきかを決める能力に致命的に依存します。いくつかのトランザクションが、前のトランザクションをアボートしても、後のトランザクションにアボートされるために、どのトランザクションも実際にはコミットできないという、終わりの無いトランザクションの連続を想像するのはとても簡単です。競合処理が複雑なことは、これまでに提案されたHTM競合解決ポリシーの多さで証明されます。
Blundell が述べたように、トランザクション外のアクセスは、さらなる複雑さをもたらします。これら全ての問題の責任を、トランザクション外のアクセスにかぶせるのは容易ですが、この手の思考がばかげていることは、トランザクション外のアクセスを全てそれ自身の単一アクセスのトランザクション内に置いてみれば、すぐにわかります。問題なのは、アクセスのパターンであって、それらがトランザクションに囲まれているかは無関係なのです。
最後に、全てのトランザクションの前方進行保証は、スケジューラにも依存します。スケジューラは、トランザクションを実行中のスレッドを、コミットに成功するまで十分長く走らせないといけません。
なので、前方進行保証を提供するHTMベンダには重要な障害があります。しかし、それを実際に行うベンダがいれば、その影響は多大でしょう。それは、HTMトランザクションはもはやソフトウェアロールバックを必要としないことを意味します。それはつまり、HTMがとうとう、TMの約束である、デッドロックの除去をもたらすことができるということです。
２０１２年終わりに、IBMメインフレームは、通常のベストエフォートHTM実装に加えて、制限されたトランザクションを含むHTM実装を発表しました。ベストエフォートトランザクションは、tbegin 命令で始まり、制限されたトランザクションは tbeginc 命令で始まります。制限されたトランザクションは、常に完了することが保証されています(最後には)。このため、もしトランザクションがアボートした時は、フォールバックパスに飛ぶのでなく、(ベストエフォートトランザクションではそうなります)、ハードウエアはそのトランザクションを、tbeginc 命令から再開します。
メインフレームアーキテクトは、この前方進行保証を提供するために、ものすごい手段の数々を使わなければなりませんでした。もし、ある制限されたトランザクションが度々失敗する時は、CPUは分岐予測を無効にし、インオーダー実行を強制し、パイプラインさえ止めることがあります。競合が高いために繰り返し失敗が起きる場合、CPUは投機的フェッチを無効にし、ランダムな遅延を入れ、競合するCPUの実行をシリアライズすることさえあります。「面白い」前方推進シナリオは、２つのCPUだけの事もあれば、１００個のCPUの事もあります。なぜ他のCPUはこれまで制限されたトランザクションを提供しなかったかを考えるのに、前記ものすごい手段の数々は、いくらかの洞察を与えるでしょう。
名前の通り、制限されたトランザクションは、実際に厳しく制限されています。
１ 最大のデータフットプリントは、メモリ４ブロックです。なお、それぞれのブロックは、３２バイトを超えてはいけません。
２ 最大のコードフットプリントは、２５６バイトです。
３ ある４KBページが制限されたトランザクションのコードを含むなら、そのページはそのトランザクションのデータを含んではいけません。
４ 実行できる最大のアセンブラ命令数は、３２です。
５ 後ろ向きの分岐は禁止されます。
それであっても、これらの制限は、連結リスト、スタック、キューそして配列を含む多くの重要なデータ構造をサポートします。なので、制限されたHTMは、並列プログラマの道具箱の中の、重要なツールとなることが期待されます。
１６．３．５．２ トランザクションサイズの増加
前方進行保証は大切です。しかし、これまで見てきたようにそれは、トランザクションサイズと持続時間を元とする条件付きの保証でしょう。小さなサイズの保証であっても、とても便利であろうことに注意するのは重要です。例えば、スタック、キュー、双方向キューにとって、２つのキャッシュラインの保証で十分です。しかし、より大きなデータ構造はより大きな保証が必要です。例えば、木を順にトラバースするのは、その木のノードの数に等しい保証が必要です。
なので、保証のサイズを増すのは、HTMの有効性を増すことになります。この結果、CPUはそれを提供するか、あるいは良い、十分な、回避策を提供する必要性が増します。
１６．３．５．３ デバッグサポートの改善
トランザクションサイズに次ぐ問題点は、トランザクションをデバッグする必要性です。現在の機構の問題は、シングルステップ実行が取り囲むトランザクションをアボートすることです。この問題には多くの回避策があります。それは、プロセッサをエミュレートする(遅い！)こと、HTMをSTMに代えること(遅くて、セマンティクスが少し違います！)、前方推進をエミュレートするために繰り返しリトライをするプレイバック技術(変な失敗モード！)、そして、HTMトランザクションのフルデバッグサポート(複雑！)などがあります。
HTMベンダの一つでも、ブレークポイント、シングルステップ、そして print 文のような古典的なデバッグテクニックをトランザクション内で直裁的に使用可能とするようなHTMシステムを開発したならば、HTMはよりずっと魅力的となるでしょう。トランザクショナルメモリ研究者の何人かは、２０１３年にこの問題に気が付き、少なくても一つの、ハードウェア補助のあるデバッグ機能を提案しました。もちろん、この提案は、そのような機能を持つ使用可能なハードウェアに依存します。
１６．３．５．４ 弱いアトミシティ
HTMは当分の間、なんらかのサイズの制限に直面し続けるだろうことを考えると、HTMが 他の機構とスムーズに協調するのは必要なことでしょう。HTMが、ハザードポインタやRCUのようなリードが主な機構と協調する能力は、トランザクション外のリードが競合するライトにあっても無条件にトランザクションをアボートさせないならば、改善することができます。その代わり、リードはトランザクション前の値を単純に使えばよいのです。こうすれば、HTMがより大きなデータ構造を扱い、競合の確率を下げることができるようにするために、ハザードポインタとRCUを使うことができます。
しかし、これは必ずしも単純なことではありません。これを最も直裁的に実装する方法は、それぞれのキャッシュラインとバスに追加の状態を必要とします。その追加の出費はわずかとはいえません。この出費の結果得られる利益は、連続する競合が原因で更新者を飢えさせる危険をおかすことなく、フットプリントの大きなリーダーを可能とすることです。
１６．３．６ 結論
現在のHTM実装は、実際の利益をもたらすことができるようですが、重大な欠点もあります。最も重大な欠点は、トランザクションサイズが限定されていること、競合処理が必要なこと、アボートとロールバックが必要なこと、前方進行保証が無いこと、取り消しできない操作を扱えないこと、そして、ロックとの微妙なセマンティクスの違いです。
これらの欠点のいくつかは、将来の実装で軽減されるかもしれません。しかし、以前に述べたように、HTMを多くの他のタイプの同期機構とうまく働くようにしなければいけない強い必要性はこれからもずっとあるでしょう。
要するに、現在のHTM実装は、並列プログラマの道具箱にとって歓迎すべきもので、便利な追加要素となるでしょう。また、それを活用するためには多くの興味深く挑戦的な作業が必要でしょう。しかし、それは、全ての並列プログラミングの問題をひと振りで解決する魔法の杖だと思ってはいけません。
１６．４ 並列化のための関数型プログラミング
１９８０年代初めに、私が実に初めての関数型プログラミング課程を取ったとき、教授は、副作用のない関数型プログラミングスタイルは、自明な並列化と解析にぴったりだと主張しました。３０年後、この主張はまだありますが、本番のメインストリームでの並列関数言語の使用はわずかです。それはもしかすると、その教授のもう一つの主張である、プログラムは状態を維持したり、I/O をしてはいけないという意見のせいかもしれません。Erlang のような関数型言語にはニッチな用途があります。他の関数型言語のいくつかにもマルチスレッドサポートが加わりました。しかし、本番のメインストリームでの使用は、C, C++, Java, そして Fortran (通常は、 OpenMP, MPI, あるいは、 Fortran の場合、 coarrays で補強されます。)などの手続き型言語の領域としてとどまっています。
この状況は、当然、疑問を起こします。「もし解析がゴールなら、解析をする前に、手続き型言語を関数型言語に変換したらどうでしょう？」もちろんこのアプローチには多くの反対意見があります。そのうち、３つだけをあげましょう。
１ 手続き型言語は、しばしば、グローバル変数を多用します。それは異なる関数、あるいはさらに悪いことに複数スレッドで、独立に更新されることがあります。Haskell の monad は、シングルスレッドのグローバル状態を扱うために発明されたことに注意下さい。なので、グローバル状態にマルチスレッドでアクセスするのは、関数モデルに対するさらなる違反が必要です。
２ マルチスレッドの手続き型言語はしばしば、ロック、アトミック操作、そしてトランザクションのような同期プリミティブを使います。それは、関数モデルに対するさらなる違反となります。
３ 手続き型言語は関数引数をエイリアスすることができます。例えば、ある関数を一度呼ぶときに、同じ構造体へのポインタを異なる二つの引数に渡すことで。こうなると、その関数が知らないうちにその構造体を二つの異なる(そしてたぶんオーバラップする)コードシーケンスで更新することになり、解析をひどく複雑にします。
もちろん、グローバル状態、同期プリミティブ、そしてエイリアスは重要ですから、賢い関数型プログラミングの熟達者達は、関数型プログラミングをそれらと調整する多くの試みを提案してきました。monad は、その一つの例です。
もう一つのアプローチは、並列手続き型言語を関数型プログラムにコンパイルすることです。そして、関数型プログラミングのツールを使って結果を解析します。しかし、これよりずっと良い方法があります。全ての実際の計算は、有限の入力を持ち、有限時間動作する、巨大な有限状態マシンであるからです。これが意味するのは、全ての実際のプログラムは式に変換できるということです。ただ、たぶん非現実的に大きなものだとしても。
しかし、多くの並列アルゴリズムの低レベルの核は現代的な計算機のメモリに容易に入るくらい小さな式に変換されます。そのような式をアサーションと組み合わせた場合、そのアサーションがそもそも発火するのかを判定するのは、充足可能性問題となります。充足可能性問題はNP完全ですが、しばしば、完全な状態空間を生成するのに必要な時間よりずっと短い時間で解くことができます。さらに、解決に要する時間は、元となるメモリモデルとは無関係のようです。なので、弱いオーダリングのシステムで走っているアルゴリズムを、シーケンシャルにコンシステントなシステムで同じくらい速くチェックできます。
一般的なアプローチはプログラムを single-static-assignment (SSA) 形式に変換することです。そうすれば、変数へのそれぞれの代入は、その変数の別々のバージョンを作成します。これは、全てのアクティブなスレッドからの代入にも適用されますから、結果となる式は、問題のコードの全ての可能な実行を具体化します。アサーションを加える事で、入力と初期値の何らかの組み合わせが、アサーションを発火させる可能性があるかを問うことになります。それは、前述したようにまさに、充足可能性問題です。
一つの可能な反対意見は、それは任意のループ構成を優雅に扱うことができないというものです。しかし、多くの場合、ループを有限回アンロールすることで対処できます。さらに、ループによっては、推論メソッドによって、つぶすことができると証明されるものも出てくるでしょう。
もう一つの可能な反対意見は、スピンロックは任意の長さのループを含むことがあるため、いかなる有限回のアンロールもスピンロックの完全な振る舞いを捉えることはできないだろうというものです。この意見は、容易に克服されることがわかりました。完全なスピンロックをモデル化する代わりに、そのロックを取ろうと試みる trylock をモデル化します。そして、すぐに取れない時は、アボートさせます。アサーションは、スピンロックがすぐに取れないためにアボートしたことによって発火しないように直さないといけません。論理式は時間と無関係なので、このアプローチを使えば、全ての可能な同時実行の振る舞いは捉えることができます。
最後の反対意見は、このテクニックはLinuxカーネルを構成する数百万行のコードのようなフルサイズのソフトウェア作品を扱うことはできないだろうというものです。これはそのとおりかもしれません。しかし、Linuxカーネル内のずっと小さな並列プリミティブを全て検証することは、とても価値のあることだろうというのは事実です。そして実際、このアプローチの先頭に立つ研究者達は、Linuxカーネル内のRCU実装を含む自明でない実世界のコードに対して、それを適用してきました（RCUのあまり重要でない性質の一つを検証するためであったとしても）。
このテクニックがどのくらい広く適用できるかは、まだわかりません。しかし、それは、形式的検証の分野でのより興味深い革新の一つです。そして、伝統的な、全てのプログラムを関数型で書けという忠告と比べると、より受け入れられるものであるかもしれません。
以上