perfbook 付録F10 以降の訳

以下は、perfbook の付録F10以降の kanda.motohiro@gmail.com による訳です。perfbook の訳の他の部分は、親文書を参照。

F.10 データ構造

１０．１

チェーンされたハッシュテーブルは完全に分割可能です。なので、同時実行での使用に適します。完全に分割可能なハッシュテーブルは他にもあります。例えば、split-ordered list [SS06]。でもそれらは、かなり複雑です。なので、チェーンされたハッシュテーブルから始めます。

１０．２

おっしゃるとおり！しかし、ハッシュテーブルはとてもしばしば、文字列のようなキーを使って情報を格納します。そのキーは必ずしも unsigned long に入りません。キーが常にunsigned long に収まる時にハッシュテーブル実装を単純にするのは、読者への課題とします。

１０．３

答えは、とても多くのことに依存します。もしハッシュテーブルがバケツあたりに多くの要素を持つならば、ハッシュバケツ数を大きくするのが明らかに良いでしょう。一方、ハッシュテーブルにあまり要素が入ってない時は、答えは、ハードウェア、ハッシュ関数の有効性、そしてワークロードに依存します。興味を持たれた読者は実験してみると良いでしょう。

１０．４

まさにその通りのことができます！実際、このアイディアを大きなクラスタシステムに拡張して、クラスタの各ノードにアプリケーションの一つのコピーを実行させます。このやり方を“sharding”と呼び、実際に、大きなウェブベースの小売業者で頻繁に使われています。

しかし、マルチソケットシステムでソケットごとに shard をするならば、別々の、より小さく安い単一ソケットのシステムを買って、データベースの一つの shard をそれぞれで走らせたらどうでしょう？

１０．５

はい。そういうことがあります！ hashtab_lookup() が、RCU リード側クリティカルセクション内から呼ばれないといけないのは、このためです。さらに、hashtab_add() と hashtab_del() がRCU アウェアなリスト操作プリミティブを使わないといけないのもこのためです。最後に、hashtab_del() の呼び出し元が、削除された要素を解放する前に、グレースピリオドを（例えば、synchronize_rcu() を呼ぶことで）待たないといけないのもこのためです。

１０．６

少しも安全ではありません。これらのプログラムをより大きなシステムで走らせるのは、有意義な演習でしょう。とはいえ、他のテストでは、RCU リード側プリミティブは、少なくても１０２４CPUまでは、一貫した性能とスケーラビリティを提供することが示されました。

１０．７

古いハッシュテーブルと新しいのは、全く異なるハッシュ関数を持つかもしれないからです。なので、古いテーブルに対して計算されたハッシュは新しいテーブルでは全く使えないかもしれません。

１０．８

そのような保証は何もしません。その代わりに、それはこれから述べる更新側の同時実行制御関数の仕事です。

１０．９

このアプローチを使えば、hashtorture.h テストインフラ構造が再使用できます。とはいえ、本番品質のサイズ変更可能ハッシュテーブルは、この２重の計算を避けるように最適化されていることでしょう。この最適化を実現するのは読者への課題とします。

１０．１０

２つめのサイズ変更操作は、挿入がされているバケツを越えては進めません。挿入が、新しいハッシュテーブルのハッシュバケツの一つ（この例では、新しいハッシュテーブルの３つ目です）にロックをかけているためです。さらに、挿入は、RCU リード側クリティカルセクションの中で起きます。hashtab_resize() 関数の説明をするときにわかるように、これは、最初のサイズ変更操作は synchronize_rcu() を使って挿入のリード側クリティカルセクションが完了するのを待つことを意味します。

１０．１１

サイズ変更操作が始まって、古いテーブルのバケツの半分を新しいテーブルに移動したとします。そして、あるスレッドが新しい要素を追加し、それは既に移動されたバケツの一つに行くとします。そしてその同じスレッドが、この新しく追加された要素を検索するとします。検索が、無条件に古いハッシュテーブルだけをトラバースするならば、このスレッドは自分が今追加した要素の検索に失敗します。それは明らかに、私には、バグのように思えます！

１０．１２

いいえ。hashtab_del() は、サイズ変更操作が既に、今削除された要素を含むバケツを越えて進んだ時に限って、古いハッシュテーブルから要素を削除するのを省略します。しかしこれは、新しい hashtab_lookup() がその要素を検索するときには新しいハッシュテーブルを使うことを意味します。なので、hashtab_del() の前に開始した古い hashtab_lookup() 操作だけが、今削除された要素を見る可能性があります。ということは、hashtab_del() は、hashtab_lookup() 操作のじゃまをしないためには、RCU グレースピリオドだけ待てばよいということです。

１０．１３

図１０．２７の３０行目の synchronize_rcu() は、２９行目で新しいハッシュテーブルの参照を設定した時から、３６行目で ->ht_resize_cur を更新する時の間に、全ての既存の RCU リーダーが完了するのを保証します。これはつまり、負でない ->ht_resize_cur を見た全てのリーダーは ->ht_new の設定がされる前には開始しているはずがない事を意味します。なので、新しいハッシュテーブルへの参照を見ることができるはずです。

１０．１４

たぶんそれは可能です。そしてそうすれば、この章で示した全てのバケツごとのロックを取るハッシュテーブルが利益を受けます。この修正をするのは、読者への課題とします。

１０．１５

最初の質問の答えは、読者への課題とします。サイズ変更可能ハッシュテーブルを特殊化して、性能がどれだけ上がるかを調べて下さい。２つ目の質問への一般的な答えはありません。その代わりに、特定のユースケースにおいて考えなくてはいけません。ユースケースによっては、性能とスケーラビリティが極めて重要です。あまりそうでないものもあります。

F．１１ 検証

１１．１

たくさんの状況があります。しかし多分、最も重要な状況とは、開発されるべきプログラムに似たものを誰もかつて作ったことのない時でしょう。この場合、信用できる計画を作る唯一の方法は、プログラムを実装して、計画を作って、そしてもう一度実装することです。しかし、プログラムを最初に実装する人はだれでも、断片的計画に従う以外の選択肢はありません。なぜならば、無知のまま作られた詳細計画はすべて、本当の世界との最初の接触を生き延びることはできないからです。

そして多分、人類が、断片的計画に喜んで従う、正気と言えないほどの楽観性を持っていることが、進化において好まれた１つの理由かもしれません。

１１．２

１ CPUバウンドなプログラムによって、すべての時間がユーザモードで消費されるテストケースがありますか？

２ CPUバウンドなプログラムによって、すべての時間がシステムモードで消費されるテストケースがありますか？

３ ３つの時間が全部ゼロのテストケースがありますか？

４ “user” と “sys”時間の合計が、“real”時間より大きいテストケースがありますか？（これはもちろん、マルチスレッドプログラムでは完全に合法です。）

５ 時間の１つが、１秒以上かかるテストケースのセットがありますか？

６ 時間の１つが、１０秒以上かかるテストケースのセットがありますか？

７ 時間の１つが、ゼロでない分を持つテストケースのセットがありますか？（例えば、“15m36.342s”）

８ 時間の１つが、６０以上の秒の値を持つテストケースのセットがありますか？

９ 時間の１つが、ミリ秒で３２ビットをオーバーフローするテストケースのセットがありますか？ミリ秒で６４ビットは？

１０ 時間の１つが、負数であるテストケースのセットがありますか？

１１ 時間の１つが、正数の分を持ち、負数の秒を持つテストケースのセットがありますか？ １２ 時間の１つが、"m" あるいは "s" を省略しているテストケースのセットがありますか？ １３ 時間の１つが、数字でない（例えば、“Go Fish”）テストケースのセットがありますか？ １４ 時間の１つが、省略されているテストケースのセットがありますか？（例えば、“real” 値と “sys” 値があるのに “user” の値が無い） １５ 行の１つが重複しているテストケースのセットがありますか？あるいは、重複していて、値のところは異なるもの。 １６ ある行が１つ以上の時間値を持つテストケースのセットがありますか？（例えば、“real 0m0.132s 0m0.008s”） １７ ランダムな文字列を含むテストケースのセットがありますか？ １８ 不正な入力に関するすべてのテストケースで、あなたはすべての置換を生成しましたか？ １９ それぞれのテストケースにおいて、あなたはそのテストの期待される出力を持ちますか？ 上記の場合のかなりの数に対してあなたがテストデータを生成してないならば、あなたは、高品質なテストを生成することができるようになるために、もっと破壊的な態度を学ぶ必要があります。 もちろん、経済的に破壊的態度を得る１つの方法は、手元のテスト対象のソースコードを使ってテストを生成することです。これをホワイトボックステストと呼びます。（ブラックボックステストに対して。）しかしこれは、万能薬ではありません。あなたの考察がそのプログラムが処理できるものに限定されるというのは、実に簡単に起きます。こうして、本当に破壊的な入力は生成されることがないのです。

１１．３

もしそれがあなたのプロジェクト、例えば、趣味、ならば、お好きにしてください。どんなに時間をムダにしても、あなたの時間です。また、それについて誰かに説明を求められることもありません。それに、時間は全くムダになったわけでないということも十分にあります。例えば、もしあなたが前例のないプロジェクトを始めるとすると、要件はある意味、事前にはどうしても知ることはできないものです。この場合、最良のアプローチは、迅速にいくつか、ラフなソリューションをプロトタイプして、動かしてみて、それで、どれが一番うまくいくか見ることです。 １１．４ もし、WARN_ON_ONCE() がたまに、２回か３回、警告を出すのを気にしなければ、単純に、ゼロに初期化した静的変数を維持しましょう。条件が発火したら、静的変数を調べます。ゼロでないなら、戻ります。そうでなければ、それを１にして、メッセージを出力し、戻ります。

メッセージが、決して、１回以上出てはいけないなら、例えば、それがとても大きいためかもしれませんが、前記の、「１にする」の代わりに、アトミック交換操作を使うことができます。アトミック交換操作がゼロを返した時だけ、メッセージを出力して下さい。

１１．５ 写し間違いがご心配なら、 diff と呼ばれるとてもクールなツールをあなたにご紹介する最初の人となることをお許し下さい。さらに、複写をするのはとても大切です。 １ あなたがもしたくさんのコードをコピーしているなら、あなたは多分、抽象化の機会を活用できていないのかもしれません。実際にコードを複写するのは、抽象化への良い動機付けとなるでしょう。 ２ コードを複写することで、あなたはそのコードが本当に新しい設定のもとで動くのかを考える機会を持つことになります。自明でない制約条件は無いでしょうか？割り込みを禁止したり、何かロックを取ったり。 ３ コードを複写することで、あなたは、仕事を片付ける他のより良い方法がないかを考える時間を得ることになります。 なので、そうです。コードを複写しなさい。 １１．６ 確かに。何度も、手でコードを複写するのは、労力が必要で、遅いです。しかし、ヘビーデューティーな負荷テストと正確さの証明と組み合わせるならば、このアプローチは、複雑な並列コードに対してとても効果的でもあります。そこでは、究極の性能と信頼性が求められ、デバッグは困難です。Linux カーネルの RCU 実装は良い例です。 一方、あなたが何らかのデータを操作するための単純なシングルスレッドのシェルスクリプトを書いているなら、別の方法論がより役に立つでしょう。例えば、テストデータセットを使って、対話的シェルで、それぞれのコマンドを１つづつ打ち込んだらどうでしょう。そして、それがあなたの望んだことをしたかを確かめます。そうしたら、成功したコマンドをあなたのスクリプトにコピーアンドペーストします。最後に、スクリプト全体をテストします。 もしあなたが手伝ってくれる友人か同僚をお持ちなら、ペアプログラミングがとてもうまくいくかもしれません。または、多くの正式な設計とコードレビュー手続きも良いでしょう。 そしてもしあなたがコードを趣味として書いているなら、お好きにすればよいです。 要するに、異なるソフトウエアの種類は、異なる開発方法論を必要とします。 １１．７ このアプローチは、あなたの検証武器庫への貴重な追加となる資格があるかもしれません。しかし、いくつかの制限もあります。 １ バグによっては、極めて発生確率が小さいけど、直さないといけないものがあります。例えば、Linuxカーネルの RCU 実装にバグがあって、平均でマシン時間１世紀に１回だけ、発火すると考えて下さい。１世紀分のCPU時間は、最も安いクラウドプラットフォームでも結構高価です。しかし、２０１１年時点で世界にある１億以上のLinuxインスタンスでは、このバグは１日に２０００件以上の障害になることが予測されます。 ２ そのバグは、あなたのテスト設定では、発生確率がゼロかもしれません。ということは、あなたがどれだけのマシン時間をそれをテストするために費やしても、あなたはそれを見ることはないということです。 もちろんあなたのコードが十分小さければ、１２章で説明するように、形式的検証が役に立つかもしれません。しかしご注意。あなたのコードを形式的検証しても、あなたの前提の誤り、要件の誤解、ソフトウエアあるいはハードウエアプリミティブの誤解、あるいは、あなたが証明を構築しようと思わなかった誤りはみつけてくれません。

１１．８

あなたは正しいです。それは全く意味をなしません。

確率はゼロと１の間の数であることを思い出して下さい。なのであなたは、確率を得るには、パーセントを１００で割る必要があります。なので、10%は確率 0.１ であり、それは確率 0.4095 になり、丸めると４１％です。それは以前の結果にとても理にかなって一致します。

１１．９

どれでもいいです。ログのベースに何を使っても、同じ答えになります。結果は純粋に、ログの比率だからです。唯一の制約は、分子と分母の両方に同じベースを使うことです。

１１．１０

等式11.28で、n を3に、P を99.9 にします。その結果は:

もしテストが失敗なく２．3時間走ったら、修正が失敗の確率を下げたと99.9%確信できます。

１１．１１

一つのアプローチは、"maxima" と呼ばれるオープンソース記号処理プログラムを使うことです。このプログラムは、多くの Debian ベースの Linux ディストリビューションに入っています。それをインストールしたら、実行して、load(distrib); コマンドを与えます。それに続いて、任意個数の bfloat(cdf_poisson(m,l)); コマンドを与えます。ここで m をご希望の値に置換して、l をご希望のλの値に置換して下さい。

特に、bfloat(cdf_poisson(2,24)); コマンドの結果は、1.181617112359357b-8 になり、それは等式１１．３０で得られたものと一致します。 その代りに、１１．６．２節で述べた、荒いけどすぐに使える方法を使うこともできます。

１１．１２ 確かにそうなるでしょう。そして、実際にそうです。 これを見るために、e^-λ は i に依存しないことに注意下さい。ということは、それは以下のように総和から抜き出すことができます。 残った総和は、まさに、e^λ のテイラー展開です。その結果: 二つの指数関数は逆なので相殺し、正確に1となります。これは期待通りです。

１１．１３ たしかに、そういうことはあります。多くの CPU はハードウエアデバッグ機能を持ち、あなたが無関係のポインタを位置づける手伝いをすることができます。さらに、コアダンプがあるなら、コアダンプ内で、こわれたメモリ領域を参照しているポインタを探すことができます。こわれた部分のデータレイアウトを調べて、そのレイアウトに一致する型を持つポインタをチェックするのも良いでしょう。 あるいは、一歩下がって、あなたのプログラムを構成するモジュールをより厳しくテストすることもできます。そうすれば、破壊は、それに責任のあるモジュールだけに限定されることがありえます。この結果、破壊が消えてしまう時は、それぞれのモジュールが公開する関数の引数チェックを追加したらどうでしょう。 いずれにしても、これは難しい問題です。それが、私が「少しばかり黒魔術」という言葉を使った理由です。 １１．１４ 巨大なコミット？恥を知りなさい！これが、コミットを小さくしないといけない理由の一つです。 そして、それがあなたへの答えでもあります。コミットを、一口サイズに分割して、それぞれを２分探索してください。私の経験では、コミットを分割する作業は、しばしばバグを悲しいほど明らかにするのに十分なことがあります。 １１．１５ 条件付きロックプリミティブが嘘をつかないことに依存するロックアルゴリズムがあるからです。例えば、条件付きロックの失敗が、他のスレッドが既にその仕事をやっていることを示すとします。このときに嘘の失敗を返すと、その仕事はけっして実行されず、たぶん、ハングにつながります。

１１．１６ その質問は、全く答えを計算しないという選択肢を考慮に入れていません。そして、それにより、答えを計算するコストも考慮に入れていません。例えば、短期の天気予報を考えましょう。それには正確なモデルがあります。しかし、少なくてもあなたが天気よりも速く実際にモデルを動かしたいならば、巨大で（そして高価な）クラスタスーパーコンピュータが必要です。 そしてこの場合、モデルが実際の天気よりも速く走るのを妨げる性能バグは何でも、すべての予報の妨げになります。巨大なクラスタスーパーコンピュータを購入する唯一の目的が、天気予報ならば、天気よりも速くモデルを走らせられないならば、モデルを全く走らせないほうがましです。 より厳しい例は、安全クリティカルなリアルタイムコンピューティングの領域で見つかることでしょう。 １１．１７ 私はあなたの意志と情熱を心から尊敬しますが、あなたはプログラムの完成が遅れることによる高コストがあるかもしれないことを忘れています。極端な例として、シングルスレッドアプリケーションからの４０％の性能低下のために、毎日、１人が死ぬとしましょう。さらに、あなたは１日で、８CPUシステムで、シーケンシャルバージョンよりも５０％速く走る、クイックでダーティな並列プログラムをハックできるとします。しかし、最適な並列プログラムは、苦痛に満ちた設計、コーディング、デバッギング、そしてチューニングに４ヶ月必要だとします。 少なくても１００人以上の人が、クイックでダーティなバージョンを選ぶでしょうね。 １１．１８

メモリのレイアウトの変化は、実際に、非現実的な実行時間の減少をもたらすことがあります。例えば、あるマイクロベンチマークがほぼ常にL0 キャッシュのアソシエイティビティをオーバーフローさせたとしても、単純に正しいメモリレイアウトにしたら全部入るかもしれません。もしこれが本当に問題なら、あなたのマイクロベンチマークをヒュージページを使って(あるいはカーネル内か、ベアメタル上で)走らせれば、メモリレイアウトを完全に制御できます。 １１．１９ 確かに、そうかもしれません。しかし、ほとんどのマイクロベンチマーク作業であなたは、テスト対象コードを、それを取り囲むアプリケーションから抜き出すでしょう。でも、もしなんらかの理由であなたがテスト対象コードをアプリケーション内に留めないといけないならば、１１．７．６節で議論したテクニックを使う必要がきっとあるでしょう。 １１．２０ 平均と標準偏差は、その仕事をするために設計されたのでないからです。それを考えるために、以下のデータセットに対して、平均と標準偏差を適用してみましょう。測定には、１％の相対誤差があるとします。 49,548.4 49,549.4 49,550.2 49,550.9 49,550.9 49,551.0 49,551.5 49,552.1 49,899.0 49,899.3 49,899.7 49,899.8 49,900.1 49,900.4 52,244.9 53,333.3 53,333.3 53,706.3 53,706.3 54,084.5 問題は、平均と標準偏差は、どのような測定誤りの仮定も含まないことです。なので、49,500 の近くにある値と、49,900 の近くにある値の差を、統計的に優位であるとみなします。しかし、実際は、それらは十分に、予期される測定誤差の範囲内なのです。 もちろん、図１１．６に似たスクリプトを作ることは可能です。それは、同様の結果を得るために、絶対的な差異の代わりに標準偏差を使います。これは、興味を持った読者への課題とします。等しいデータ値の連続から来るゼロによる割り算に注意下さい！ １１．２１

確かにそうなるでしょう！でももしあなたの性能測定がしばしば正確にゼロの値を生成するならば、たぶんあなたはご自分の性能測定コードをよく見る必要があるでしょう。

この類のデータセットに対して、平均と標準偏差を元にする多くのアプローチも同様の問題を持つだろうことに注意下さい。

F.12 形式的検証 １２．１ ロッカープロセスは無限ループです。なので、制御はこのプロセスの最後には決して達しません。しかし、単調増加する変数はないので、Promela はこの無限ループを少ない数の状態でモデルできます。 １２．２ いくつかあります。 １ sum の宣言は、 init ブロック内に移すのがよいです。それは他のところでは使われませんから。 ２ アサーションコードは、初期化ループの外に移すのがよいです。そうすれば、初期化ループはアトミックブロック内に置くことができ、状態空間を大いに（どのくらい？）減らせます。 ３ アサーションコードを持つアトミックブロックは、sum と j の初期化とアサーションを含むように拡張するのがよいです。そうすれば、これも状態空間を減らせます（もう一度、どのくらい？）。 １２．３ はい。それを、if-fi で置換して、二つの break 文を除きます。

１２．４

これらの操作はアサーションのためだけにあるからです。それはアルゴリズム自身の一部ではありません。なのでこれらをアトミックにすることによる害はありません。そしてそうすることは Promela モデルが探索しなくてはいけない状態空間を大いに減らします。 １２．５ はい。これを見るために、その行を削除してモデルを走らせて下さい。あるいは、以下のステップのシーケンスを考えましょう。 １ 一つのプロセスが、RCU リード側クリティカルセクションにいます。なので、ctr[0] の値はゼロで ctr[1] の値は２です。 ２ 更新者が実行を始めます。そして、カウンタの合計が２であることを見ます。このため、高速パスは実行できません。なのでそれはロックを取ります。 ３ 二つ目の更新者が実行を始めます。そしてctr[0] の値をフェッチします。それはゼロです。 ４ 最初の更新者が１を ctr[0] に加え、インデックスをフリップし（それは今ゼロになりました）、そしてctr[1] から１を引きます（それは今１になりました）。 ５ 二つ目の更新者がctr[1] の値をフェッチします。それは今は１です。 ６ すると二つ目の更新者は誤って、高速パスに進むのが安全だと結論します。しかし元のリーダーはまだ完了していないというのが事実です。 １２．６ 落ち着いて下さい。この質問には、いくつかの合法的な答えがあります。 １ モデルをさらに最適化して、メモリ消費を削減します。 ２ 紙と鉛筆の証明をがんばります。たぶん、Linux カーネルのコードのコメントから始めるのが良いでしょう ３ 注意深い拷問テストを工夫します。それはコードが正しいことを証明できないとしても、隠れたバグを見つけることができます。 ４ より小さなマシンのクラスタの上でモデルチェックをするツールへのある程度の指向はあります。しかし、私は自分自身ではそのようなツールを使ったことが無いことに注意下さい。それは、Paul が時々アクセスできるいくつかの巨大マシンのおかげです。 ５ 購入可能なシステムのメモリサイズが、あなたの問題に適合するくらい大きくなるのを待って下さい。 ６ いくつかあるクラウドコンピューティングサービスのどれかを使って、巨大システムを短い期間だけ借りなさい。 １２．７ これは、NMIがある時に失敗します。これを見るために、rcu_irq_enter() が rcu_update_flag を加算した直後、ただし、dynticks_progress_counter を加算する前に、NMI が入ったと考えて下さい。NMIから呼び出された rcu_irq_enter() インスタンスは、rcu_update_flag の元の値がゼロでないことを見るでしょう。なので、dynticks_progress_counter を加算しようとしないでしょう。すると、RCUグレースピリオド機構は、このCPUでNMIハンドラが実行していることについてどんな手がかりも得られません。なので、NMI ハンドラにある全てのRCUリード側クリティカルセクションはRCU保護を失うでしょう。 NMI ハンドラ、それは定義によりマスクできません、の可能性はこのコードを実際に複雑にしています。 １２．８ 実行中のタスクを割り込んだ時には、そうではありません！その場合、dynticks_progress_counter は既に rcu_exit_nohz() によって加算されているはずで、それをもう一度加算する必要はありません。 １２．９ あなたが正しいかどうか、次の節を読んで下さい。 １２．１０ Promela は sequential consistency を前提とします。なので、メモリバリアをモデルする必要はありません。実はその代わり、例えば、３０７ページの図１２．１３が示すように、メモリバリアの欠落を明示的にモデルする必要があります。 １２．１１ それはより自然かもしれません。しかし、後で追加する、生きていることの確認のために、この特定の順序が必要です。 １２．１２ グレースピリオドのコードは、それぞれのCPUの dynticks_progress_counter と rcu_dyntick_snapshot 変数を個別に処理するため、その状態を単一CPUの上につぶすことができます。もしも、そうでなくてグレースピリオドのコードが特定のCPUで特定の値の時に何か特別なことをするならば、私達は複数CPUを実際にモデルしなくてはいけないでしょう。しかし幸運なことに、私達は安全に、二つのCPUに私達を閉じ込めることができます。グレースピリオド処理を走らせる一つと、dynticks-idle モードに入って出る一つです。 １２．１３ Promela と spin が全ての可能な状態変更のシーケンスを追跡することを思い出して下さい。なので、タイミングは無関係です。Promela/spin は喜んで、モデルの残り全部を、この二つの文の間に詰め込むことができます。何らかの状態変数が特に、そうすることを禁止しない限り。 １２．１４ 最も簡単なやり方は、そのような文それぞれを、それ自身の EXECUTE_MAINLINE() 文の中に置くことです。 １２．１５ 一つのアプローチ、それを後の節で見ますが、は、明示的なラベルと “goto” 文を使うことです。例えば、以下の構成は： if :: i == 0 -> a = -1; :: else -> a = -2; fi; このようにモデルすることができます。 EXECUTE_MAINLINE(stmt1, if :: i == 0 -> goto stmt1_then; :: else -> goto stmt1_else; fi) stmt1_then: skip; EXECUTE_MAINLINE(stmt1_then1, a = -1; goto stmt1_end) stmt1_else: skip; EXECUTE_MAINLINE(stmt1_then1, a = -2) stmt1_end: skip; しかし、“if”文の時にこのマクロが大いに助けになっているかは不明です。なので、以下の節では、このような状況はオープンコードすることにします。 １２．１６ これらのコード行は、モデルを制御するためのものです。モデルされているコードではありません。なので、ノンアトミックにそれをモデルする理由はありません。それをアトミックにモデルする動機は、状態空間の大きさを減らすことです。 １２．１７ そのような性質の一つは、ネストした割り込みです。次の節で扱います。 １２．１８ 常にではありませんが、そうすることがより多くなってきました。今の場合、Paul は割り込みハンドラを含む最小のコード断片からはじめました。それは彼が、Promela で割り込みをどのようにモデルするのが一番よいかよくわからなかったからです。それが動くようになったら、彼は他の機能を追加しました（しかしもし彼がそれをもう一度やるならば、彼は「おもちゃの」ハンドラから始めるでしょう。例えば、ハンドラが変数を二回加算して、メインラインのコードがその値が常に偶数であることを検証するなど。）。 なぜ、インクリメンタルなアプローチかって？以下を考えて下さい。Brian W. Kernighan の言葉です。 デバッグは、最初にコードを書くよりも二倍大変です。なので、あなたができる限り技巧的なコードを書くならば、あなたは、定義により、それをデバッグできるだけの賢明さは持っていないでしょう。 ということは、コードの作成を最適化しようとする全ての試みは、少なくても６６％の努力をデバッグプロセスを最適化することに向けるべきです。それは、コーディングに費やされる時間と努力を増やすことになってもです。インクリメンタルなコーディングとテストは、デバッグプロセスを最適化する一つの方法です。それはコーディング努力をいくらか増やしますが。Paul はこのアプローチを取ります。なぜならば、彼は何日も（まして何週間も）コーディングとデバッグに費やすことのできるほどの贅沢はとても望めないからです。 １２．１９ それは単一CPUの囲いの中では起き得ません。最初の割り込みハンドラは、NMIハンドラが戻るまで完了できません。なので、dynticks と dynticks_nmi のそれぞれが、与えられた時間間隔の間、偶数値を取っているならば、対応するCPUは本当にその時間間隔の間のどこかで、静止状態にいたということです。 １２．２０ そのアプローチは、機能的には正しいです。しかし、巨大マシンでは過剰な割り込み出入りのオーバーヘッドになります。それに対して、この節で説明したアプローチは、それぞれのCPUが割り込みとNMIの出入りで、CPUごとのデータだけをさわることを許し、特に巨大マシンでは、ずっと低い割り込みの出入りのオーバーヘッドとなります。 １２．２１ 実際のところ、学者たちは x86 メモリモデルを弱いと思っています。なぜならば、それは以前のストアを以降のロードとリオーダーすることを許すからです。学術的観点から言うと、強いメモリモデルとは、絶対にリオーダーを許さないものです。なので、全てのスレッドはそれから見える全ての操作のオーダーに合意します。 １２．２２ どちらでも動きます。しかし一般的には、明示的な命令を使うより初期化を使う方が良いです。この例では、明示的な命令の使い方を示すために、それを使いました。また、ツールのウェブサイト (http://www.cl.cam.ac.uk/~pes20/ppcmem/) にあるリトマス試験の多くは自動的に生成されたもので、明示的な初期化命令を生成します。

１２．２３ atomic_add_return() の powerpc バージョンの実装は、 stwcx 命令が失敗したらループします。その命令は、条件コードレジスタにゼロ以外の状態を設定することで伝えます。そして bne 命令がそれをテストします。実際にループをモデルするのは、状態空間の爆発になるので、その代わりに、Fail:ラベルに分岐して、モデルを終了します。この時、スレッド１の r3 レジスタの値は初期値の２で、exists アサーションは発火しません。 このトリックが普遍的に使えるかは少し議論がありますが、私はそうできなかった例を見たことはありません。 １２．２４ ARM はこの特定のバグは持ちません。それは、atomic_add_return() 関数のアセンブラ言語実装の前と後に smp_mb() を置くからです。 PowerPC はもうこのバグは持ちません。修正されてからずいぶんになります。Linuxカーネルの持っているかもしれないこれ以外のバグを見つけるのは読者への課題とします。

F.13 全部まとめると

１３．１ あるスレッドの __thread 変数は、そのスレッドが終了すると消えます。なので、他のスレッドの __thread 変数をアクセスする全ての操作は、スレッド終了と同期する必要があります。そのような同期をしないと、たった今終了したスレッドの__thread 変数をアクセスしてセグメンテーション違反になることがあります。 １３．２ ５７ページの図５．９を見て下さい。もし同時実行するinc_count()がなければ、 read_count() は正確な結果を返すことは明白です。しかし、同時実行するinc_count()があれば、read_count() が合計を計算している間にその合計は実際に変化しています。とはいえ、スレッドの作成と終了は final_mutex によって排他されますから、counterp にあるポインタは一定のままです。

メモリの即時のスナップショットを取る能力のある神秘的なマシンを考えましょう。このマシンが、read_count() の実行の開始時にそのようなスナップショットを取り、read_count() の実行の終了時にもうひとつのスナップショットを取るとします。そうすると、read_count() はそれぞれのスレッドのカウンタをこれら２つのスナップショットの間のどこかの時間にアクセスするでしょう。なので、これら２つのスナップショット、両端を含みます、によって上下限が決まる結果を得るはずです。なので、全体の合計は、２つのスナップショット（繰り返しますが、両端を含みます）それぞれに対してとられる合計の対によって上下限が決まるでしょう。

この結果、期待される誤差は、２つのスナップショットそれぞれに対して得られる合計の対の差の半分です。ということは、read_count() の実行時間の半分に、単位時間あたりの inc_count() 呼び出しの期待回数をかけたものとなります。 計算式が好きな方には、以下です。 εは read_count() の戻り値の期待される誤差、Tr は、read_count() が実行するのにかかる時間、そして Ri は、単位時間あたりの inc_count() 呼び出し回数です。（そしてもちろん、Tr と Ri は同じ時間の単位を使うべきです。マイクロ秒とマイクロ秒あたりの呼び出し数、秒と秒あたりの呼び出し数、あるいは、単位が同じならなんでもいいです。）

１３．３

そのとおり。私は確かにそう言いました。そして、count_unregister_thread() が現在行うように、 count_register_thread() が新しい構造体を確保するようにすることは可能でしょう。 しかし、それは不要です。read_count() の誤差の限界の導出を思い出して下さい。それはメモリのスナップショットを元としていました。新しいスレッドは counter の初期値ゼロを持って始まりますから、前記導出は、read_count() の実行の途中で新しいスレッドを加えても成り立ちます。なので、興味深いことに、新しいスレッドを加える時にはこの実装は、新しい構造体を確保する効果を得ますが、実際には確保をする必要はありません。 １３.４ これはもちろん、ケースバイケースで判断する必要があります。もしあなたが線形にスケールする read_count() の実装が必要なら、図５.９に示すロックを元とする実装は単純に、あなたの役には立たないでしょう。一方、read_count() の呼び出しが十分にまれなら、ロックを元とするバージョンはより単純で、そのためより望ましいかもしれません。ただ、サイズの差の多くは、構造体定義、メモリ確保、そして NULL リターンのチェックが原因ですけれど。 もちろん、より良い質問は、「なぜ言語は、 __thread 変数へのクロススレッドアクセスを実装しないか？」です。結局、そのような実装はロックとRCUの使用の両方を不要とするでしょう。そうすれば、図５．９に示したものよりも単純で、かつ、図１３.１に示した実装のスケーラビリティと性能の利点の全てを持つ実装が可能でしょう！ １３．５

確かにその可能性はあります。 このキャッシュミスオーバヘッドを避ける一つの方法を、図F１０に示します。animal 構造体に、単純に、measurement 構造体のインスタンスを、meas という名前で埋め込みます。そして、->mp フィールドで、この ->meas を指します。 すると、measurement の更新は、このように行うことができます。 １ 新しい measurement 構造体を確保して、新しい測定結果をそこに置きます。 ２ rcu_assign_pointer() を使って、->mp がこの新しい構造体を指すようにします。 ３ グレースピリオドが経過するのを待ちます。例えば、synchronize_rcu() あるいは call_rcu() を使います。 ４ 新しい measurement 構造体から、測定結果を、埋め込まれた ->meas フィールドに複写します。 ５ rcu_assign_pointer() を使って、->mp が古い埋め込まれた ->meas フィールドを指すようにします。 ６ もうひとつグレースピリオドが経過したら、新しい measurement 構造体を解放します。 このアプローチは、一般的な場合に余分なキャッシュミスを除くために、より重量級の更新手続きを使います。余分なキャッシュミスは、更新が実際に進行中の時にだけ発生します。 １３．６ そのとおり。１０．４節で述べたサイズ変更可能ハッシュテーブルは、サイズ変更の間は、完全なスキャンができません。これを回避する一つの単純な方法は、スキャンの間、hashtab構造体の ->ht_lock を取ることです。しかしこれは一つ以上のスキャンが同時実行するのを許しません。 もうひとつのアプローチは、サイズ変更が進行中の場合、更新の時に、新しいハッシュテーブルだけでなく古い方も変換することです。そうすれば、スキャンは古いハッシュテーブルのすべての要素を見つけることができます。これを実装するのは、読者への課題とします。

F.１４ 進んだ同期

１４．１ 鍵となる点は、こうです。直感的な解析は、Cへの設定とAへの設定が、どちらもthread2() に届くのを競争しているときに、前者が後者を追い越すのを防ぐものは何もないことを見落としています。この節の残りで、詳しく説明します。 １４．２ 一番簡単な修正は、１２行目の barrier() を smb_mb() に代えることです。 １４．３ このコードは、あるCPUが自分自身の値を見るのを止めたらすぐに、最終的に合意された値を直ちに見ると仮定しています。本物のハードウエアでは、CPUのいくつかは、最後の値に収束する前に、中間の値をいくつか見ることが十分あり得ます。 １４．４ 多くのCPUはライトバッファを持ち、それは最近のライトの値を記録します。それは、対応するキャッシュラインがそのCPUにやって来た時に適用されます。なので、それぞれのCPUが時間のある一点である変数の異なる値を見ることは容易にあり得ます。メインメモリがさらに別の値を持つことも。メモリバリアが発明された一つの理由は、ソフトウエアがこのような状況を優雅に扱うことができるようにするためです。 １４．５ CPU２と３は、同じコア上のハードウエアスレッドの対で、同じキャッシュ階層を共有します。なので、とても低い通信遅延を持ちます。これは、NUMA, もっと正確には、NUCA 効果です。 これは、そもそも、CPU２と３の意見が異なるのはなぜかという疑問を起こすでしょう。１つの可能な理由は、それらは大きな共用キャッシュに加えて、小さい量のプライベートキャッシュを持っているかもしれないということです。もう一つの可能な理由は、命令のリオーダリングです。意見の不一致期間が１０ナノ秒と小さいことや、コード断片にメモリバリアが一切使ってないことからそう思われます。

１４．６

MMIO レジスタは特殊ケースです。それは物理メモリのキャッシュされない領域に現れます。メモリバリアは、たしかに、１４．２．８節で述べるように、無条件に、キャッシュされないメモリへのロードとストアをオーダリングします。

１４．７

シナリオは以下です。AとBは両方とも最初ゼロです。

CPU 0: A=1; smp_mb(); r1=B; CPU 1: B=1; smp_mb(); r2=A; 両方のCPUが終わった時に、ロードのどちらも、対応するストアを見ないならば、r1, r2 のどちらもゼロでしょう。r1 がゼロだったとします。すると、CPU０のBからのロードはCPU１のBへのストアの前に起きたことがわかります。結局、そうでないと、r1 は１のはずです。しかし、CPU０のBからのロードがCPU１のBへのストアの前に起きたため、メモリバリアの対はCPU０のAへのストアがCPU１のAからロードより前に起きることを保証します。その結果、r2 はゼロでなく、１になることが保証されます。 なので、r1, r2 の少なくても一つはゼロでないはずです。それは、ロードの少なくても一つが対応するストアの値を見たことを意味し、それは意図されたとおりです。 １４．８ 組み合わせ２において、もしCPU１のBからのロードが、CPU２のBへのストアの前の値を見たならば、CPU２のAからのロードは、CPU１のAからのロードと同じ値か、それより後の値を返すことがわかります。 組み合わせ４において、もしCPU２のBからのロードが、CPU１のBへのストアの値を見たならば、CPU２のAからのロードは、CPU１のAからのロードと同じ値か、それより後の値を返すことがわかります。 組み合わせ８において、もしCPU２のAからのロードが、CPU１のAへのストアの値を見たならば、CPU１のBからのロードは、CPU２のBからのロードと同じ値か、それより後の値を返すことがわかります。

１４．９

もし、CPUが自分の全てのロードとストアをオーダーされて見る必要がないならば、b=1+a が変数 “a”の古いバージョンを見ることもありえます。

これが、それぞれのCPUあるいはスレッドが自分の全てのロードとストアをプログラムオーダーで見ることがそんなにも重要である理由です。

１４．１０

クリティカルセクションの最初の実行だけが、p==NULL を見るべきです。しかし、もしも mylock のクリティカルセクションに関してグローバルなオーダリングがなければ、あなたはどれか特定のが最初だとどうやって言えますか？もし、そのクリティカルセクションの異なるいくつかの実行が、自分が最初だと思ったら、それらは皆、p==NULL を見るでしょうし、それらは皆メモリを確保するでしょう。これらの確保の一つ以外のものは、リークされます。

これが、ある排他的ロックの全てのクリティカルセクションが、なんらかの、よく定義されたオーダーで実行するように見えることがそんなにも重要である理由です。

１４．１１

カウンタが値ゼロから始まったとします。クリティカルセクションの３つの実行がその結果、値を３にしました。もし４つ目のクリティカルセクションの実行がこの変数への最も最近の値を見るように制約されていないならば、それは初期値ゼロを見るかもしれません。すると、カウンタを１にします。それは、逆に進みます。

これが、あるクリティカルセクション内でのある変数からのロードが、その変数にストアをした以前の最後のクリティカルセクションの最後のストアを見ることがそんなにも重要である理由です。

１４．１２

全く何もありません。バリアは、“a” と “b”への代入が、それより後の全ての代入の前に起きることを保証するでしょうが、“a” と “b”への代入自身については、何らかのオーダーを強制することは何もしません。

１４．１３

２つの連続した、LOCK-UNLOCK 操作のシリーズです。あるいは、少し変ですが、UNLOCK 操作に続いて、LOCK 操作です。

１４．１４

Itanium が一つの例です。その他を探すのは、読者への課題とします。

１４．１５

１ 合法。順序通り実行。

２ 合法。ロック確保は、クリティカルセクションの前にある最後の代入と同時実行します。

３ 違法。“F”への代入は LOCK の後でなくてはいけません。

４ 違法。 LOCK はクリティカルセクションの全ての操作の前に完了しなくてはいけません。なお、UNLOCK がその後の操作と同時実行するのは合法です。

５ 合法。“A”への代入は、要求通り、UNLOCK の前にあります。そしてそれ以外の操作は順序通りです。

６ 違法。“C”への代入は LOCK の後でなくてはいけません。

７ 違法。“D”への代入は UNLOCK の前でなくてはいけません。

８ 合法。全ての代入は、LOCK と UNLOCK に関してオーダーされています。

９ 違法。“A”への代入は、UNLOCK の前でなくてはいけません。

１４．１６

全てのCPUは以下のオーダリング制約を見ないといけません。

１ LOCK M は、 B, C, and D の前にある。

２ UNLOCK M は、 A, B, and C の後にある。

３ LOCK Q は、 F, G, and H の前にある。

４ UNLOCK Q は、 E, F, and G の後にある。

F.15 使いやすさ

１５．１

はい。しかし、真ん中の要素を削除するためには、それぞれのスレッドは３つの連続する要素のロックを取らないといけません。なので、Nスレッドがあれば、2N+1 要素（N+1 でなく）が、デッドロックを避けるために必要です。

１５．２

それは Paul です。

彼は、食事をする哲学者問題を考えていました。それは、５人の哲学者が出席する少し非衛生的なスパゲッティの夕食でした。テーブルにはお皿は５枚で、でもフォークは５つ、哲学者は食べるためには、一度に２つのフォークが必要ですから、普通の人は、デッドロックを防ぐフォーク配分アルゴリズムを考えつくはずでした。Paul の答えは、「やれやれ、フォークをもう５つ、持って来い！」でした。

これはこれとして、OKでした。しかし、Paul は次に、この同じ解決策を、循環連結リストに適用しました。

これもこれとして、まあまあでした。でも、彼は誰かにそれを話したくてしかたありませんでした！

１５．３

一つの例外は、難しくて複雑なアルゴリズムであって、ある状況ではただひとつの、動作することがわかっているもの、というものでしょう。もう一つの例外は、難しくて複雑なアルゴリズムであって、ある状況では動作することがわかっているものの中ではそれでも最も単純、というものでしょう。しかし、これらの場合でも、少し時間を使って、より単純なアルゴリズムを考えようとするのはとても価値のあることかもしれません。結局、もしあなたが、何かの仕事をするために最初のアルゴリズムを発明できたなら、更に進んで、より単純なものを発明するのはそれほど難しいことではないはずです。

F.16 未来のビジョンはいろいろある

１６．１ exec() されたプログラムが、この同じメモリ領域をマップするならば、そのプログラムは原理的には、単純にロックを放すことができます。このアプローチが、ソフトウェア工学的に健全であるかは、読者への課題とします。 １６．２ もし、ロックがそれが守る変数のいくつかと同じキャッシュラインにあるならば、あるCPUからその変数への書き込みは、他の全てのCPUのそのキャッシュラインを無効にします。この無効化は多数の競合とリトライを起こし、ロックに比べて性能とスケーラビリティをむしろ落とすことになるかもしれません。

１６．３

更新が大きければ、競合の確率も高くなり、その結果リトライの確率も大きくなります。それは性能を落とします。

１６．４

多くの場合、列挙は正確である必要はありません。そういう場合は、ハザードポインタや、RCU を使って、任意の挿入と削除に伴う低確率の競合からリーダーを守ることができます。

訳注。（１）同期を取らない不正確な列挙をする。（２）正確な列挙が必要なら、RCUを使う。更新が少ない時は適度な性能を保ったままできる。

という流れかと思うのですが。

１６．５

このしかけは、かなり高確率でうまくいきます。しかし、ほとんどのユーザにとってとても驚くべき仕方で失敗することがあります。それを見るために、以下のトランザクションを考えましょう。

1 begin_trans();

2 if (a) {

3 do_one_thing();

4 do_another_thing();

5 } else {

6 do_a_third_thing();

7 do_a_fourth_thing();

8 }

9 end_trans();

ユーザがブレークポイントを３行目に設定したとします。それは発火し、トランザクションをアボートし、デバッガに入ります。ブレークポイントが発火した時と、デバッガがなんとか全てのスレッドを止めるまでの間に、どれか他のスレッドが a の値をゼロにしたとします。気の毒なユーザがプログラムをシングルステップしようとすると、びっくり！プログラムは今では then 節でなくて、else 節にいます。

こういうのを、私は、使いやすいデバッガとは呼びません。

１６．６

７．２．１節のクイッククイズの答えを見て下さい

しかし、前方進行保証のない強アトミックな HTM 実装においては、空のクリティカルセクションを基礎とする全てのメモリベースのロック設計は、トランザクショナルロック除去があっても正しく動作すると主張する人がいます。私はこの宣言の証明を見たことはありませんが、この主張には直裁的な理由があります。主なアイデアは、強アトミックな HTM 実装においては、あるトランザクションの結果は、トランザクションが成功して完了するまで見えません。なので、あなたにそのトランザクションが開始したことが見えるということは、それは既に完了していることが保証されます。ということは、以降の空のロックベースの空のクリティカルセクションは成功裏にそれを「待つ」でしょう。結局、待ちは何も必要ないのです。

この推論の流れは、弱アトミックシステム（多くのSTM 実装を含みます）には適用されません。それに、通信にメモリ以外の手段を使うロックベースのプログラムにも適用されません。そのような手段の一つは、時の流れ（例えば、ハードリアルタイムシステムにおいて）であり、優先度の流れ（例えば、ソフトリアルタイムシステムにおいて）です。

優先度ブーストに依存するロック設計は特に興味深いです。

１６．７

そうすることもできます。しかし、それは同時に不必要で不十分です。 空のクリティカルセクションが条件付きコンパイルの結果である時には、それは不必要です。ここでは、ロックの唯一の目的は、データを守ることであり、それを完全に除くことがするべきことであるということは十分あります。実際、空のクリティカルセクションを残すのは性能とスケーラビリティを落とします。 一方、空のクリティカルセクションが、データ保護と、時間ベースでありロッキングのメッセージングセマンティクスの両方のために使われていることもあります。そのような場合にトランザクショナルロック除去を使うのは正しいことではなく、バグにつながります。 １６．８ 短い答えは、一般的なコモディティハードウェアにおいて、何らかの種類の細粒度のタイミングをベースとする同期設計は無謀であり、全ての条件下で正しく動くことは望めないということです。 とはいえ、ずっと決定論的なハードリアルタイムの使用のために設計されたシステムがあります。あなたがそのようなシステムを使う（ほぼありえないでしょうが）時には、以下は、時間ベースの同期がどのように働くかを示すためのおもちゃの例です。繰り返しますが、これを、コモディティマイクロプロセッサにおいて試さないで下さい。それらはとても非決定論な性能特性を持ちますから。 この例は、複数のワーカスレッドと１つの制御スレッドを使います。それぞれのワーカスレッドは出力データフィードに対応し、一つの仕事の単位を実行した後、現在時刻（例えば、clock_gettime() システムコールから得て）をスレッドごとの my_timestamp 変数に記録します。この例のリアルタイムな性質の結果、以下の制限の組があります。 １ あるワーカスレッドが、MAX_LOOP_TIME 以上の期間、自分のタイムスタンプを更新できないことは致命的なエラーです。 ２ グローバル状態をアクセス、更新するために、ロックはまれに使われます。アイテムのロックは与えられたスレッドの優先度の中で厳格に FIFO 順に許可されます。 ワーカスレッドが自分のフィードを完了した時、スレッドはアプリケーションの残りの部分から自分を切り離して、スレッドごとの my_status 変数に状態値を置きます。 my_status 変数の初期値は -1 です。スレッドは終了しません。その代わり、以降の処理要求に応えるためにスレッドプールに置かれます。制御スレッドは必要に応じてワーカスレッドをアサイン、（そして再アサイン）するとともに、スレッド状態のヒストグラムを維持します。制御スレッドはワーカスレッドの優先度以下のリアルタイム優先度で走ります。 ワーカスレッドのコードは以下です。 制御スレッドのコードは以下です。 ５行目は、スレッドが終了したのを推測するために、時間の流れを使います。そうならば、６から１０行目を実行します。７と８行目の空のクリティカルセクションは終了しようとしているスレッドが完了するのを保証します。（ロックは FIFO 順に許可されるのを覚えていますか！） 繰り返しますが、この手のことを、コモディティマイクロプロセッサで試みないで下さい。結局、ハードリアルタイム使用のために特別に設計されたシステムにおいて正しいことをするのは十分に難しいのです！ １６．９ デッドロックは起きません。デッドロックになるには、２つの異なるスレッドがそれぞれ、２つのロックを逆順で確保しなくてはいけません。それはこの例では起きません。しかし、lockdep のようなデッドロック検出器は、これを擬陽性とフラグするでしょう。

F.17 重要な問題

A.1

１． タイトループに、barrier() あるいは volatile がありません。

２． 更新側にメモリバリアがありません。

３． 生産者と消費者の間に同期がありません。

A.2

１． 消費者は長時間プリエンプトされるかもしれません。

２． 長く走る割り込みが消費者を遅延するかもしれません。

３． 生産者が消費者よりも速いCPUで走っているかもしれません。（例えば、CPUの片方は熱拡散あるいは電力消費の制約のためにクロック周波数を落とす必要があったかもしれません。）

F.18同期プリミティブ

B.1

多くの例があります。最も単純なものの一つは、単一の独立変数を使った parametric study です。run_study プログラムが単一の引数を取るならば、以下の bash スクリプトを使って二つのインスタンスを並列に走らせることができます。それは、２CPUのシステムでは適切なことでしょう。

run_study 1 > 1.out& run_study 2 > 2.out; wait

もちろん、bash のアンパーサンド演算子と“wait”プリミティブは実は同期プリミティブであると主張することもできます。その場合、このスクリプトを手作業で二つの別々のコマンドウィンドウで走らせることができることに注意下さい。すると、唯一の同期は、ユーザの彼あるいは彼女だけが提供するでしょう

B.2

ロードストアアーキテクチャのCPUでは、counter を加算するのは、以下のようにコンパイルされるかもしれません。

LOAD counter,r0

INC r0

STORE r0,counter

そのようなマシンでは、二つのスレッドが同時に counter の値をロードし、それぞれがそれを加算し、そして結果を格納するかもしれません。すると counter の新しい値は、二つのスレッドがそれぞれが、それを加算したのにもかかわらず、前よりも一つ大きいだけです。

B.3

一つのアプローチは、smp_thread_id() でインデックスされる配列を作成することです。別のは、smp_thread_id() から配列インデックスにマップするハッシュテーブルを使うことです。ーそれは、実は、pthread 環境でこのAPIセットがやっていることです。

別のアプローチは、スレッド作成の時に、親がそれぞれ必要なスレッドごと変数のためのフィールドを含む構造体を確保してそれを子に渡すことです。しかし、このアプローチは巨大システムでは、大きなソフトウエアエンジニアリング的なコストを課します。それを見るために、ある巨大システムの全てのグローバル変数が単一ファイルに定義されなくてはいけない場合を考えてみましょう！それが C static 変数であってもなくても。

F.19 なぜメモリバリア？

C.1

ライトバックメッセージは、あるCPUもしくは設計によってはそのCPUのあるレベルのキャッシュから発生します。いくつかのCPUに共用されているキャッシュからの場合もあります。鍵となる点は、そのキャッシュはあるデータ要素のための空きを持たないため、場所を空けるためにどこか他のデータ断片がキャッシュから追い出されなくてはいけないことです。どこか他のキャッシュあるいはメモリに複製されたデータ断片があるならば、そのデータ断片は単純に捨てることができ、ライトバックメッセージは不要です。

そうでなくて、もし捨てられるデータ断片の全てが変更されていて、最新のコピーがこのキャッシュにしか無いならば、このデータ要素の一つはどこか他に複写されなくてはいけません。この複写操作が、「ライトバックメッセージ」を使って実行されます。

ライトバックメッセージのあて先は、その新しい値を格納できる何かでなくてはいけません。それはメインメモリかもしれません。しかし、どこか他のキャッシュでもかまいません。もしそれがキャッシュなら、通常はそれはその同じCPUのための高レベルのキャッシュです、例えば、レベル１キャッシュはレベル２キャッシュにライトバックすることができます。しかし、ハードウェア設計によっては、クロスCPUのライトバックを許します。なので、CPU０のキャッシュはライトバックメッセージをCPU1に送るかもしれません。

これは通常は、そのCPU１がそのデータへの興味を何らかの方法で示した時に行われるでしょう。例えば、最近、リード要求を発行したなど。

短く言えば、ライトバックメッセージは空きがないシステムのある部分から送られて、そのデータを受け入れることのできるシステムのどこか別の部分によって受け取られます。

C.2

CPUのどちらか一つが共用バスへのアクセスを最初に得ます。そしてそのCPUが「勝ちます」。別のCPUはそのキャッシュラインの自分のコピーを無効化して、「無効化応答」メッセージを他のCPUに送らなければいけません。

もちろん、負けた方のCPUは直ちに「リード無効化」トランザクションを発行することができますから、勝ったCPUの勝利はとてもはかないものでしょう。

C.3

もし巨大スケールのマルチプロセッサが実際にそのように実装されているならば、そうかもしれません。巨大マルチプロセッサ、特に NUMAマシンは、これや他の問題を避けるために、いわゆる「ディレクトリベース」のキャッシュコヒーレンスプロトコルを使う傾向にあります。

C.4

過去数十年間、この問題についてけっこうな議論がありました。一つの答えは、キャッシュコヒーレンスプロトコルはとても単純で、そのためハードウェアで直接実装することができ、ソフトウェアのメッセージパッシングでは実現不可能なバンド幅と低遅延が可能であるというものです。別の答えは、巨大SMPマシンの値段とより小さいSMPマシンのクラスタの値段で決まる経済学の中に本当の真実があるというものです。３つ目の答えは、SMPプログラミングモデルは、分散システムのそれに比べて使いやすいというものです。しかし、反論者は HPCクラスタとMPIの出現に注目するでしょう。このように議論は続くのです。

C.5

通常は、追加の状態を使います。ただ、この追加の状態は実際にキャッシュラインと一緒に格納される必要はありません。ある時に遷移の途中にあるのは、少しだけだという事実のためです。遷移を遅延させる必要というのは、実世界のキャッシュコヒーレンスプロトコルが、この付録で述べた過度に単純化されたMESIプロトコルよりもずっと複雑であることの理由の一つです。Hennessy and Patterson の、計算機アーキテクチャの古典的入門書[HP95] は、これらの問題を多くを扱っています。

C.6

そのようなシーケンスはありません。ただ、そのCPUの命令セットに、特別な、「私のキャッシュをフラッシュしなさい」命令があれば、別です。多くのCPUは実際にそのような命令を持ちます。

C.7

ストアバッファの目的は、単に、マルチプロセッサキャッシュコヒーレンスプロトコルの応答遅延を隠すことだけではなく、メモリ遅延一般を隠すことだからです。メモリは、ユニプロセッサのキャッシュよりもずっと遅いので、ユニプロセッサのストアバッファはライトミスの遅延を隠す助けになります。

C.8

問題のキャッシュラインは、変数 a 以外のものも含むからです。

C.9 CPU0は、"a" を含むキャッシュラインのリードオンリーのコピーを持つので、既にそれらの変数の値を持ちます。なので、CPU0がしなくてはいけないことは、他のCPUにこのキャッシュラインのコピーを捨てさせることです。なので、「無効化」メッセージで十分です。

C.10

CPUは投機的実行をする自由があります。それは、アサーションを while ループが終わる前に実行する効果を持つことが可能です。さらに、コンパイラは通常は、現在実行中のスレッドだけが変数を更新すると仮定します。そしてこの仮定は、コンパイラが a のロードをループの前に引き上げることを許します。

実際、以下のように、ループを、無限ループのまわりの分岐に変換するコンパイラもあります。

1 void foo(void)

2 {

3 a = 1;

4 smp_mb();

5 b = 1;

6 }

7

8 void bar(void)

9 {

10 if (b == 0)

11 for (;;)

12 continue;

13 smp_mb();

14 assert(a == 1);

15 }

この最適化をすると、明らかにアサーションは発火することがあります。

訳注

？ bar が最初に b をロードしてゼロなら、無限ループするし、1なら、メモリバリアのおかげで a == 1 は保証されるでしょう？

volatile キャストか、(可能なら)C++ relaxed atomic を使って、コンパイラがあなたの並列コードを最適化して忘れ去らないようにするべきです。

短く言えば、コンパイラとCPUの両方は最適化にとてもアグレッシブです。なのであなたは、コンパイラディレクティブとメモリバリアを使って、あなたの制約を明確に伝えないといけません。

C.11

いいえ。スレッドがあるCPUから他に移動して、移動先のCPUが移動元のCPUの最近のメモリ操作をアウトオブオーダーで感知する場合を考えましょう。ユーザモードの正気を守るために、カーネルハッカーはコンテキストスイッチのパスで、メモリバリアを使わなくてはいけません。しかし、安全にコンテキストスイッチをするために既に必要とされているロックが、自動的に必要なメモリバリアを提供するはずです。それはユーザレベルのタスクが、自分自身のアクセスを順序通りに見ることを許すでしょう。とは言え、もしあなたが超最適化スケジューラを設計しているなら、それがカーネルレベルでもユーザレベルでも、このシナリオを覚えておいて下さいね！

C.12

いいえ。そのようなメモリバリアはCPU1にローカルなオーダリングを強制するだけです。CPU0とCPU1のアクセスの相対的オーダリングには影響しません。なのでアサーションは依然として失敗することがあります。しかし、全てのメインストリームの計算機システムは、「推移律」を提供するための何らかの機構を持ちます。それは直感的な因果性のオーダリングを提供します。もし、BがAのアクセスの影響を見て、CがＢのアクセスの影響を見るなら、ＣはAのアクセスの影響も見なければいけないということです。短く言えば、ハードウェア設計者は、ソフトウェア開発者に少なくても小さな哀れみをかけてくれたのです。

C.13

アサーションは、"e" のロードが "a" のそれの前に来ることを保証するように書かれなくてはいけません。Linuxカーネルでは、barrier() プリミティブを使って、前の例でアサーションにおいてメモリバリアが使われたのとほとんど同じように、これを達成することができます。

C.14

結果はそのCPUが「推移律」をサポートするかによります。言葉を代えて言えば、CPU0は、CPU1が "c" にストアするのを見た後に、"e" にストアしました。そして、CPU0の "c" からのロードと"e" へのストアの間には、メモリバリアがあります。もしどれか他のCPUが、CPU0の"e" へのストアを見るならば、それはCPU1のストアも見ることを保証されるでしょうか？

私が知っている全てのCPUは推移律を提供すると言っています。

C.15

まず、Alpha は、mb と wmb 命令しか持ちません。なので、smp_rmb() は、どちらの場合もAlpha mb 命令で実装されるでしょう。

より重要なことは、smp_read_barrier_depends() は以降のストアもオーダーしないといけないことです。例えば、以下のコードを見ましょう。

1 p = global_pointer;

2 smp_read_barrier_depends();

3 if (do_something_with(p->a, p->b) == 0)

4 p->hey_look = 1;

ここで、 p->a とp->b からのロードだけでなく、p->hey_look へのストアもオーダーしないといけません。

F.20 リードコピーアップデートの実装

D.1

スリープはコンテキストスイッチを意味するからです。それは、クラシックRCUでは静止状態です。そして、RCUのグレースピリオド検出は、静止状態がRCUリード側クリティカルセクションには決して現れないことを要求します。

D.2

それは、ヘビーなカーネルモードの実行負荷（例えば、カーネルスレッドによる）のもとにあるシステムは決してグレースピリオドを完了できないことがあることを意味します。すると、遅かれ早かれ、メモリが枯渇します。

D.3

この性質は、RCUの synchronize_sched() の面がそもそも動くために必要だからです。例えば、オブジェクトをリストから除き、synchronize_sched() を呼び、そしてオブジェクトを解放するコードシーケンスを考えましょう。もしこの性質が保たれなければ、オブジェクトは、リストから除かれる前に解放されることがあるでしょう。それは、まさに、 synchronize_sched() が防ごうとする状況です！

D.4

順序が逆になったとします。CPU０が、ちょうど、synchronize_srcu() の１３行目に来ました。その時、CPU１とCPU２が、それぞれ、別の synchronize_srcu() の実行を開始しました。そして、CPU３は srcu_read_lock() の実行を開始しました。CPU１は、CPU０が１３行目のカウンタを加算するちょうどその前に、synchronize_srcu() の６行目に来たとします。

訳注。続くけど、もうわからん。

F.１５ 並列リアルタイムコンピューティング

１５．１ 遅かれ早かれ、電池は充電しないといけません。それにはエネルギーがそのシステムに流れ込む必要があります。そうしないとシステムは動作を止めるでしょう。 １５．２ 場合によります。利用率を低くすることで最悪の場合の応答時間を改善できる一つの状況は、問題のデバイスを全てのスレッドが使う時に、そのデバイスを使うリアルタイムスレッドが一つしかない時です。そのデバイスの使用を、ただ一つのリアルタイムスレッドに制限することで、キューイング遅延は、なくなります。少なくてもそのリアルタイムスレッドがそのデバイスを過負荷にしない限り。 １５．３ たぶんこの状況は、本物のソフトウェアの面倒な世界に飛び込むのを避けている理論家の言い訳に過ぎないのではないでしょうか？より建設的には、たぶん以下の進歩が必要です。 １ 形式的検証はより大きなソフトウェア作品を扱う必要があります。最大の検証作業でも、たった約一万行のコードのシステムのためでした。そしてそれはリアルタイム遅延と比べてずっと単純な性質を検証しました。 ２ ハードウェアベンダは正式のタイミング保証を公開しなくてはいけません。これはハードウェアがずっと単純だった過去には一般的慣習でした。しかし今日の複雑なハードウェアは、最悪の場合の性能を表すのに過度に複雑な式を必要とすることとなりました。不幸にも、エネルギー効率への関心は、ベンダをよりずっと複雑な方向に推し進めているようです。 ３ 開発メソドロジーとIDEに、タイミング解析を統合する必要があります。 とは言え、希望はあります。実際の計算機システムのメモリモデルの形式化についての最近の研究 [AMP+11, AKNT13]を見ると。 １５．４ この区別は、確かに、厳密に理論的な観点からは不十分です。しかし一方、それは、あるアプリケーションが標準的なリアルタイムでないアプローチを使って安価に簡単に開発できるのか、それとも、より困難で高価なリアルタイムアプローチが必要なのかを決定するために開発者がまさに必要とするものです。言葉を代えて言えば、理論はとても重要です。しかし、ものごとが達成されるのを好む私達のような者には、理論は実践をサポートするのであって、決してその逆ではありません。 １５．５ たしかにその通りです。ただし、APIを除きます。そしてAPIは重要です。なぜならば、それは -rt パッチセットがバカげた大きさに増大することなく、Linuxカーネルが、リアルタイム能力を提供することを許すからです。 しかし、このアプローチは明らかにそして厳しく、リード側のスケーラビリティを制限します。Linuxカーネルの -rt パッチセットがこの制限とこれまで共存できてきたのには、いくつか理由があります。 （１）リアルタイムシステムは伝統的に小規模だったこと。 （２）リアルタイムシステムは一般的にプロセス制御に焦点を当てたこと。このため、I/Oサブシステムのスケーラビリティ制限には影響されなかったこと。 （３）Linuxカーネルのリーダーライターロックの多くはRCUに変換されたこと。 それらを全て横に置くとしても、いつかLinuxカーネルが、優先度ブーストが必要となるリーダーライターロックに、ある程度のリード側並列性を許すというのは十分にありそうです。 １５．６ これは本当に問題です。そしてこれは、RCUのスケジューラフックによって解決されます。もしそのスケジューラフックが、t->rcu_read_lock_nesting の値が負であることを見たら、それは、コンテキストスイッチが完了するのを許す前に、必要に応じて rcu_read_unlock_special() を呼びます。 １５．７ はい。そしていいえ。 ノンブロッキングアルゴリズムは、フェイルストップバグがあっても、フォールトトレランスを提供できるという意味では、はいです。しかしそれは現実的なフォールトトレランスにはかなり不十分であるという意味では、いいえです。例えば、ウェイトなしのキューがあるとします。そして、あるスレッドがちょうどある要素をデキューしたとします。もしそのスレッドがフェールストップなバグによって死んだならば、それがちょうどデキューした要素は事実上は失われます。真のフォールトトレランスは、単なるノンブロッキングな性質以上のものを必要とし、それはこの本の守備範囲を越えます。

１５．８

そのとおり。たくさんあります。しかし、それらはある状況に特定であることが多いです。そして、それらの多くは、既に一覧とした制約の詳細化と考える事ができます。例えば、データ構造を選択することについての多くの制約は、「いかなるクリティカルセクションにおいても費やされる時間は有限であること」という制約を満足するのを助けます。

----ここから

----ここまで

以上