以下は、perfbook の１３章の kanda.motohiro@gmail.com による全訳です。編集に不便なので、ファイルを分けました。perfbook の訳の他の部分は、親文書を参照。
１３章 全部まとめると
この章はいくつかの同時実行プログラムのパズルを扱うためのヒントをいくつか与えます。ます、１３．１節はカウンタの難問。１３．２節は RCU の救い、最後に１３．３節はハッシュの悩みです。
１３．１ カウンタの難問
この節は、カウンタの難問の可能な対策の概要をいくつか示します。
１３．１．１ 更新を数える
シュレディンガーが（１０．１節を参照。）それぞれの動物の更新の数を数えたいとします。そして、これらの更新は、データ要素ごとのロックを使って同期されるとします。この数を数えるにはどうすれば一番いいでしょう？
もちろん、５章のカウンティングアルゴリズムのどれを考えることもできます。しかし、最適なアプローチは、この場合、ずっと簡単です。単に、それぞれのデータ要素にカウンタを置いて、その要素のロックの保護のもとで加算しなさい！
１３．１．２ 検索を数える
シュレディンガーがそれぞれの動物の検索の数も数えたいとします。検索は、RCU で保護されます。この数を数えるにはどうすれば一番いいでしょう？
１つのアプローチは、１３．１．１節で述べたように、要素ごとのロックで参照カウンタを保護することです。不幸にも、これはすべての検索がそのロックを取る必要があり、大規模システムでは厳しいボトルネックになります。
もう一つのアプローチは、カウンティングは「単に、ダメと言う」ことです。noatime マウントオプションの例にならいます。もしこのアプローチが許されるなら、それが明らかに最適です。結局、何もしないより速いことはありません。もし参照カウントをやめることができなければ、読み続けましょう！
５章のカウンタをどれでも使うことができます。５．２節で述べた統計カウンタが、多分最も一般的でしょう。でもそれは大きなメモリフットプリントにつながります。必要なカウンタの数は、データ要素の数かけるスレッド数です。 もしこのメモリオーバヘッドが大きすぎるなら、一つのアプローチは、CPUごとのカウンタでなくソケットごとのカウンタを維持することです。なお、図１０．８に示したハッシュテーブルの性能に気をつけて下さい。これは、カウンタ加算がアトミック操作であることを要求します。ユーザモード実行では、あるスレッドがいつでも他のCPUに移動することがあるので、それは特に重要です。 もしある要素がとてもひんぱんに検索されるなら、スレッドごとのログを維持することで更新をまとめるアプローチがいくつかあります。ある要素の複数のログエントリをマージすることができます。あるログエントリに十分大きな加算がされた後、もしくは十分な時間が経過した後、ログエントリを対応するデータ要素に適用します。Silas Boyd-Wickizerは、この概念を形式化する研究をしました。
１３．２ RCU の救い
この節は、この本で以前に述べた例に RCUを適用するやり方を示します。ある場合、RCUはコードをより単純にします。別の場合、それはより良い性能とスケーラビリティを与えます。両方できる場合もあります。
１３．２．１ RCU と、スレッドごと変数を元とする統計カウンタ
５．２．４節は、素晴らしい性能を提供する統計カウンタの実装を述べました。その性能は、単純な加算(C 言語の ++ 操作のような) にほぼ等しく、線形のスケーラビリティも得られます。ただし、inc_count() を使っての加算に限ります。不幸にして、read_count() 経由で値を読む必要のあるスレッドは、グローバルロックを取らないといけません。このため、オーバヘッドが高く、スケーラビリティは低いです。ロックを元とする実装のコードは、５７ページの図５．９にあります。
クイッククイズ１３．１ そもそも、一体全体なぜグローバルロックが必要なんでしたっけ？
１３．２．１．１ 設計
read_count() でのスレッドトラバーサルを、final_mutex ではなくてRCUで守ることによって、inc_count() だけでなく、read_count() においても素晴らしい性能とスケーラビリティを得るのが、私たちの望みです。しかし、計算された合計において、正確さを犠牲にすることはしたくありません。特に、あるスレッドが終了するときに、終了するスレッドのカウントを失ったり、二重に数えたりするのは、決していけません。そのような誤差は、結果の完全な正確さに等しい不正確さをもたらすことがあります。言葉を代えて言えば、そのような誤差は結果を完全に無効にします。そして実際、final_mutex の一つの目的は、スレッドが read_count() の実行中に出たり入ったりしないことを保証することでした。
クイッククイズ１３．２
いったい、read_count() の正確さとは何ですか？
なので、final_mutex をやめるためには、一貫性を保証する何か他の方法を思いつく必要があります。一つのアプローチは、単一の構造体に、以前に終了した全てのスレッドのカウント総数と、スレッドごとカウンタへのポインタの配列を置くことです。そのような構造体を、一旦 read_count() に対して公開して、一定に保持すれば、read_count() が一貫したデータを見るのを保証できます。
１３．２．１．２ 実装
図１３．１の１から４行目は、countarray 構造体です。これは、以前に終了したスレッドのカウントのために ->total フィールドを持ち、現在実行中のスレッドのスレッドごと counter へのポインタの配列である counterp[] を持ちます。この構造体は、ある read_count() の実行が、指定された実行中スレッドのセットに矛盾しない合計を見ることを可能とします。
６から８行目はスレッドごとの counter 変数、現在の countarray 構造体を参照するグローバルポインタ countarrayp 、そして final_mutex スピンロックの定義です。
１０から１３行目は inc_count() で、図５．９から変わっていません。
１５から２９行目は read_count() で、大きく変わっています。２１と２７行目は rcu_read_lock() と rcu_read_unlock() であり、final_mutex の確保と解放に代わります。２２行目は rcu_dereference() を使って現在の countarray 構造体をローカル変数 cap にスナップショットします。正しくRCUを使えば、この countarray 構造体は、少なくても２７行目の現在の RCUリード側クリティカルセクションの終わりまでは、私達と共にあることが保証されます。２３行目は sum を cap->total に初期化します。これは、以前に終了したスレッドのカウンタの合計です。２４から２６行目は現在実行中のスレッドに対応するスレッドごとのカウンタを加算します。そして最後に２８行目で合計を返します。
countarrayp の初期値は、３１から３９行目の count_init() で提供されます。この関数は最初のスレッドが作成される前に走り、その仕事は、最初の構造体を確保してゼロにし、そしてそれを countarrayp に設定することです。
４１から４８行目は count_register_thread() 関数で、新しく作成されたそれぞれのスレッドによって呼ばれます。４３行目で現在スレッドのインデックスをピックアップして、４５行目で final_mutex を取り、４６行目でこのスレッドの counter へのポインタを設定し、４７行目で final_mutex を放します。
クイッククイズ１３．３
ヘイ！！！図１３．１の４６行目は、既存の countarray 構造体の値を変更します！この構造体は、一旦 read_count() に公開されたら、一定のままだと言いませんでしたか？？？
５０から７０行目は、count_unregister_thread() です。これは、それぞれのスレッドが、終了するすぐ前に呼ばれます。５６から６０行目で新しい countarray 構造体を確保します。６１行目は final_mutex を取り、６７行目で放します。６２行目は、現在の countarray の内容を、新しく確保したバージョンに複写します。６３行目は終了しようとしているスレッドの counter を新しい構造体の total に加えます。そして６４行目は終了しようとしているスレッドの counterp[] 配列要素を NULL にします。そして６５行目は現在の（すぐに古くなります）countarray 構造体へのポインタを退避します。６６行目は rcu_assign_pointer() を使って、countarray 構造体の新しいバージョンを設定します。６８行目はグレースピリオドが経過するのを待ちます。このとき、同時に read_count 内を走っており、そのために古い countarray 構造体への参照を持っている可能性のある全てのスレッドが、そのRCUリード側クリティカルセクションを終わり、そのような参照を全て落とすことができるようにします。その結果、６９行目で安全に古い countarray 構造体を解放できます。
１３．２．１．３ 議論
クイッククイズ１３．４
ワゥ！図５．９は４２行のコードしか無いのに、図１３．１は、６９行あります。この余分の複雑さは、本当にその価値があるのですか？
RCUを使うことで、終了しようとしているスレッドは、他のスレッドが、終了しようとしているスレッドの __thread 変数を使い終わったことが保証されるまで待つことができます。なので read_count() 関数はロック無しで済みます。この結果、inc_count() と read_count() 関数の両方で素晴らしい性能とスケーラビリティが得られます。しかしこの性能とスケーラビリティはコードがかなり複雑になるというコストを伴います。コンパイラとライブラリの開発者が、ユーザーレベルRCUを活用して、__thread 変数への安全なスレッドまたがりのアクセスを提供してくれることが期待されます。そうすれば、_thread 変数の利用者が見る複雑さを大いに減らすことができるでしょう。
１３．２．２ リムーバブルI/O デバイスのための RCUとカウンタ
５．５節は、リムーバブルデバイスへの I/O アクセスを数えるためのヘンテコなコード断片の対を見ました。このコード断片は、リーダーライターロックを取る必要から、高速パス(I/O を開始するとき)、高いオーバヘッドに悩まされました。
この節は、RCU を使ってこのオーバヘッドを避ける方法を示します。
I/O を実行するコードは、元のととても似ています。元の、リーダーライターロックのリード側クリティカルセクションが、RCU リード側クリティカルセクションに代わっています。
RCU リード側プリミティブは最小のオーバヘッドを持ちますから、期待通り、高速パスをスピードアップします。
デバイスを削除する、修正後のコード断片は以下です。
ここでは、リーダーライターロックを排他的スピンロックに代え、synchronize_rcu() を追加して全てのRCUリード側クリティカルセクションが完了するのを待ちます。synchronize_rcu() のため、６行目に着いたときには、全ての残っているI/O は対策済みであることがわかっています。
もちろん、synchronize_rcu() のオーバヘッドは大きいかも知れませんが、デバイス削除はとてもまれですから、これは通常は良いトレードオフです。
１３.２.３ 配列と長さ
図１３.２ に示すような、RCU保護された可変長配列があるとします。配列 ->a[] の長さはダイナミックに変わることがあり、いかなるときも、その長さは ->length フィールドで与えられます。もちろん、これは以下の競合条件を引き起こします。
１ 配列は初め、１６文字の長さで、なので ->length は１６に等しいです。
２ CPU0は ->length の値をロードして、値１６を得ます。
３ CPU1は配列を長さ８に縮小して、 ->a[] に、新しい８文字ブロックのメモリへのポインタをアサインします。
４ CPU0は新しいポインタを ->a[] からピックアップし、新しい値を要素１２に格納します。配列は８文字しかありませんから、この結果は、SEGV あるいは(もっと悪いことに)メモリ破壊です。
これを防ぐにはどうしましょう？
一つのアプローチは、メモリバリアを注意深く使うことです。これは、１４.２節で取り上げます。これはうまくいきますが、リード側のオーバヘッドを起こしますし、もっと悪いことに、明示的なメモリバリアの使用が必要です。
訳注
？長さとポインタの読み書きの途中が見えるのは、メモリバリアでも防げないと思います。
より良いアプローチは、図１３．３のように、値と配列を同じ構造体に入れることです。新しい配列(foo_a 構造体)を確保すれば自動的に配列の長さに新しい場所が提供されます。ということは、あるCPUが ->fa への参照をピックアップする時は、その ->length は、->a[] の長さに等しいことが保証されます [ACMS03]。
１ 配列は最初１６文字の長さで、->length は１６に等しいです。
２ CPU0 は ->fa の値をロードして、値１６と１６バイト配列を含む構造体へのポインタを得ます。
３ CPU0 は ->fa->length の値をロードして、値１６を得ます。
４ CPU１は配列を長さ８に縮小します。そして、ポインタに、->a[] に８文字ブロックのメモリを持つ新しい foo_a 構造体をアサインします。
５ CPU０はポインタを ->a[] からロードして、新しい値を要素１２に格納します。CPU０はまだ、１６バイト配列を持つ古い foo_a 構造体を参照していますから、全てはうまくいきます。
訳注
原文は new pointer ですが、誤りです。４の ->a[] は、５のとは違います。
もちろん、両方の場合にCPU１は古い配列を解放する前にグレースピリオドの間、待たなくてはいけません。
次の節は、このアプローチのより一般的なバージョンを示します。
１３.２.４ 相関するフィールド
シュレディンガーの動物は図１３.４に示すデータ要素で表現されるとします。meas_1, meas_2, そして meas_3 フィールドは周期的に更新される、相関のある測定値のセットです。リーダーがこれらの３つの値の、単一の測定更新から得られたものを見ることは致命的に重要です。もしリーダーが meas_1 の古い値と、meas_2, そして meas_3 の新しい値を見たら、おそろしく混乱します。リーダーがこれら３つの値の調整されたセットを見ることを保証するにはどうしたらいいでしょう？
一つのアプローチは、新しい animal 構造体を確保して、古い構造体を新しい構造体に複写し、新しい構造体の meas_1, meas_2, そして meas_3 フィールドを更新し、そして次に、ポインタを更新することによって古い構造体を新しい構造体と交換します。これは確かに、全てのリーダーが測定値の調整されたセットを見ることを保証します。しかしこれは、->photo[] フィールドのために、大きな構造体を複写する必要があります。この複写は許容できないほど大きなオーバヘッドを起こすかもしれません。
別のアプローチは、図１３．５のように、間接レベルを入れることです。新しい測定がされたら、新しい measurement 構造体を確保します。これに測定値を入れて、animal 構造体の ->mp フィールドを、rcu_assign_pointer() を使ってこの新しい measurement 構造体を指すように更新します。グレースピリオドが過ぎたら、古い measurement 構造体は解放できます。
クイッククイズ１３.５
でも、図１３.５に示したアプローチは、余分なキャッシュミスを起こし、その結果リード側オーバヘッドが増すことになりませんか？
このアプローチは、最小のリード側オーバヘッドで、リーダーが選択したフィールドの調整された値を見ることを可能とします。
１３．３ ハッシュの悩み
この節は、ハッシュテーブルを使う時に起きる問題をいくつか調べます。これらの問題は、多くの他の検索構造にもあてはまることに注意下さい。
１３．３．１ 相関するデータ要素
この状況は、１３．２．４節に似ています。ハッシュテーブルがあり、２あるいはそれ以上の要素の、相関したビューが必要です。これらの要素は一緒に更新されます。その時、最初の要素の古いバージョンともう一つの要素の新しいバージョンが見えるのは困ります。例えば、シュレディンガーは、彼の親族を、彼の全ての動物と一緒に、インメモリデータベースに加えることに決めました。シュレディンガーは、結婚や離婚は即座には起きないことを理解していますが、彼は伝統主義者でもあります。なので彼は、データベースが、新婦は現在結婚しているが、新郎はしていないとか、その反対とか、を示すのは絶対に許せません。言葉を代えて言うと、シュレディンガーは結婚状態について一貫性のあるデータベースのトラバーサルを実行したいと考えています。
一つのアプローチは、シーケンスロック（９．２節を参照）を使うことです。結婚状態に関係ある更新は、write_seqlock() の保護のもとで行われるようにします。また、結婚状態の一貫性を必要とするリードは、read_seqbegin() / read_seqretry() ループの中で行われます。シーケンスロックは、RCU 保護の代わりではないことに注意下さい。シーケンスロックは、同時実行する更新に対して保護をしますが、同時実行する削除に対して保護をするためにRCU はなおも必要です。
このアプローチは、相関する要素の数が少ない時、これらの要素を読む時間が短い時、そして更新比率が低い時にはとてもうまくはたらきます。そうでない場合、更新があまりに素早く起きると、リーダーは決して完了しないことがあります。シュレディンガーは、彼の最も変人の親戚でさえ、これが問題となるほど素早く結婚、離婚するとは思いませんが、この問題は他の状況で確かに起きうることをよく理解しています。このリーダー飢餓問題を避ける一つの方法は、あまりに多くの再試行があった時にはリーダーが、更新側プリミティブを使うようにすることです。しかしこれは、性能とスケーラビリティの両方を落とします。
さらに、更新側プリミティブが頻繁に使われすぎると、ロック競合のために性能とスケーラビリティが落ちます。これを避ける一つの方法は、要素ごとのシーケンスロックを持ち、結婚状態を更新する時には、夫婦両方のロックを保持することです。リーダーは、夫婦の両方のメンバに関わる結婚状態の変化についてステーブルなビューを得るために、夫婦のロックのどちらかに対して再試行のループを行えばよいのです。これにより、結婚と離婚の頻度が高いために起きる競合は避けられます。しかし、データベースを一度スキャンして、全ての結婚状態のステーブルなビューを得るのを、複雑にします。
もし要素のグループ分けがよく定義され永続的ならば、それは結婚状態に望みたいことですが、一つのアプローチは、データ要素にポインタを追加して、あるグループのメンバを一緒につなぐことです。リーダーは、そうすれば、このポインタをトラバースして、グループの最初のものを位置づけた後、同じグループの全ての要素をアクセスできます。
バージョン番号を使うもう一つのアプローチは、興味を持った読者への課題とします。
１３．３．２ 更新に優しいハッシュテーブルトラバーサル
あるハッシュテーブルの全ての要素を統計的にスキャンする必要があるとします。例えば、シュレディンガーは彼の全ての動物に対して、身長と体重の比率の平均を計算したいとします。
脚注
そんな数字は何の役に立つかって？私をぶってください！でも一般的なグループ統計はしばしば役に立ちます。
さらに、シュレディンガーはこの統計的スキャンが行われる間に、動物がハッシュテーブルに追加あるいは削除されることから来るわずかな誤差は無視したいとします。同時実行制御をするためにシュレディンガーは何をするべきでしょう？
一つのアプローチは、統計的スキャンをRCUリード側クリティカルセクションにくるむことです。そうすれば、更新はスキャンを不要にじゃますることなく同時に進行できます。特に、スキャンは更新をブロックしませんし、逆もそうです。その結果、とても多くの要素を持つハッシュテーブルのスキャンが、とても更新頻度が高い場合にも優雅にサポートできます。
クイッククイズ１３．６
でも、サイズ変更可能ハッシュテーブルがサイズ変更している時に、このスキャンはどのようにはたらきますか？その場合、古いハッシュテーブルも新しい方も、ハッシュテーブルの全ての要素を持っている保証はありません！
以上