以下は、perfbook の９章の kanda.motohiro@gmail.com による全訳です。９．３節は、RCU の作者による RCU の詳細な説明です。perfbook の訳の他の部分は、親文書を参照。
９章 遅延処理
仕事を後回しにする戦略は、記録に残る歴史以前からありました。ぐずとかなまけもの、と呼ばれることもありました。しかし、最近の数十年で、研究者たちは並列アルゴリズムを単純かつ合理的にするためにこの戦略の持つ価値に気が付きました。信じられないかもしれませんが、並列プログラミングにおいて、「なまけること」はしばしば、一生懸命にやるよりも高性能で、よりスケールするのです！そのような仕事を後回しにする戦略の一般的アプローチには、参照カウンティング、シーケンスロック、そして、RCU があります。
９．１ 参照カウンティング
参照カウントはあるオブジェクトの参照の回数を追跡して、そのオブジェクトが使われているのに解放されるのを防ぎます。これは概念としては単純な技術ですが、多くの悪魔が細部に潜んでいます。結局、オブジェクトが使われているのに解放されるということがなければ、そのそも参照カウンタは不要です。しかし、オブジェクトが解放されうるなら、参照を確保する処理そのものの間に、解放がされるのをどうやって防ぐでしょう？
この問題にはいくつかの答えがあります。
１ 参照カウントを操作するには、オブジェクトの外に有るロックを取る必要が有ることにします。
２ オブジェクトはゼロでない参照カウントを持って作成されます。新しい参照は、参照カウンタの現在値がゼロでない時に限って得ることができます。あるスレッドがあるオブジェクトに参照を持たない場合、既に参照を持っている他のスレッドの助けをかりて参照を得ることができます。
３ オブジェクトに存在の保証が提供されます。それにより、あるエンティティが参照を得ようとしているときにオブジェクトが解放されることはなくなります。存在の保証は、アトミックなガーベッジコレクターによって提供されることが多いです。９．３節の、RCU のところを参照。
４ オブジェクトにタイプ安全の保証が提供されます。参照を得たら、追加の身元チェックを実行する必要が有ります。タイプ安全の保証は、専用のメモリアロケーターで提供されます。Linux カーネルのSLAB_DESTROY_BY_RCU機能はその例です。９．３節を参照。
もちろん、定義からいって、存在の保証を提供する機構は、タイプ安全の保証も必ず提供します。このため、この節では最後の２つの回答を、RCUにまとめます。すると、参照確保を保護する一般的カテゴリーが３つになります。参照カウント、シーケンスロック、そしてRCUです。
クイッククイズ９．１：
単純なコンペアアンドスワップ操作を使って、参照カウンタがゼロ以外の時だけ参照を得ることで、参照確保を実装してはいけないのでしょうか？
キーとなる、参照カウントの問題は、参照の確保と、オブジェクトの解放の間の同期ですから、表９．１に示すように、９つの機構の組み合わせが可能です。この表は、参照カウントの機構を以下の広いカテゴリーに分類します。
１ アトミック操作も、メモリバリアも、アラインメント制限もない単純なカウント操作（”-”）
２ アトミックカウント。メモリバリアなし。（”A”）
３ アトミックカウント。解放の時だけメモリバリアを使う。（”AM”）
４ アトミックカウント。確保の時チェックを含む。解放の時だけメモリバリアを使う。（”CAM”）
５ アトミックカウント。確保の時チェックを含む。（”CA”）
６ アトミックカウント。確保の時チェックを含む。確保の時もメモリバリアを使う。（”MCA”）
しかし、 Linux カーネルの、値を返すすべてのアトミック操作は、メモリバリアを含むように定義されていますから、解放操作は必ずメモリバリアを使います。さらに、すべてのチェックを含む確保もメモリバリアを含みます。この結果、ケース ”CA” と ”MCA” は、”CAM” と同じです。このため、以下の節は、最初の４ケース、”-”、”A”、”AM”、”CAM” だけを説明します。参照カウントをサポートする Linux プリミティブは、９．１．３節で説明します。その後の節は、参照確保と解放がとても頻繁であり、参照カウントをゼロと比較するのがとてもまれであるときに性能を向上させることのできる最適化を示します。
９．１．１ 参照カウントカテゴリーの実装
９．１．１．１節は、ロックで保護される単純なカウント（”-”）を説明します。９．１．１．２節は、メモリバリアのないアトミックカウント（”A”）を説明します。９．１．１．３節は、確保時にメモリバリアを使うアトミックカウント（”AM”）を説明します。９．１．１．４節はチェックと解放時のメモリバリアを使うアトミックカウントを説明します。
９．１．１．１ 単純なカウンティング
アトミック操作もメモリバリアも使わない単純なカウンティングは、参照カウンタの確保と解放が同じロックで守られている時なら使うことができます。この場合、参照カウント自身の操作は、アトミックでなく行うことができるのは明らかです。ロックが、必要な排他制御、メモリバリア、アトミック命令、コンパイラの最適化の防止などを提供するからです。これは、参照カウント以外の操作を保護するためにロックが必要であり、ロックを放した後でもオブジェクトへの参照を持っている必要の有る場合には良い方法です。図９．１に、単純なアトミックでない参照カウンティングをするための単純なAPIを示します。ただ、単純な参照カウンティングはほとんどの場合、オープンコード、つまり、べたに書かれますけど。
９．１．１．２ アトミックカウンティング
参照を得ようとするCPUは、既に参照を持っていなければいけないことにすれば、単純なアトミックカウンティングを使うことができます。このスタイルは、単一のCPUが自分専用で使うためにオブジェクトを作って、他のCPU,タスク、タイマーハンドラー、I/O完了ハンドラーを後から起動し、それらもそのオブジェクトにアクセスする必要の有る場合に使うことができます。オブジェクトを他に渡すCPUは、最初に、受信者のために新しい参照を得る必要があります。 Linux カーネルでは、図９．２に示す kref プリミティブがこのスタイルの参照カウンティングを実装するために使われます。
ロックがすべての参照カウント操作を保護するために使われないため、アトミックカウンティングが必要です。２つの異なるCPUが同時に参照カウントを操作することがあるということです。普通の加算と減算を使ったなら、２つのCPUが同時に参照カウントをフェッチするかもしれません。両方が「３」を得たとします。両方共この値を加算して「４」を得て、両方共この値をカウンタにストアバックします。カウンタの新しい値はそうでなくて「５」であるはずなので、２つの加算の片方が失われました。これでわかるように、カウンタの加算と減算にはアトミック操作を使う必要があります。
解放が、ロックあるいはRCUで保護されているなら、メモリバリアは不要です。ただし、別の理由のためです。ロックの場合、ロックが必要なメモリバリアを提供します。（さらに、コンパイラの最適化も無効にします。）そして、ロックが２つの解放が同時に走るのを防ぎます。RCUの場合、クリーンアップはすべての現在実行中のRCUリード側クリティカルセクションが完了するまで遅延されます。そして、必要なメモリバリアとコンパイラ最適化を無効にするのも、RCUインフラストラクチャが提供します。このため、２つのCPUが最後の２つの参照を同時に放した場合、実際のクリーンアップは両方のCPUがRCUリード側クリティカルセクションを終わるまで遅延されます。
クイッククイズ９．２：
あるCPUが最後の参照を放した直後に別のCPUが参照を得るケースをガードしなくていいのはなぜでしょう。
kref 構造体自身は、１つのアトミックデータアイテムからなり、図９．２の１から３行目にあります。５から８行目の kref_init() 関数が、カウンタの値を「１」にします。なお、atomic_set() プリミティブはただの代入で、そういう名前なのは操作がそうだからではなくてデータタイプ atomic_t に由来します。kref_init() 関数は、オブジェクト作成のときに、他のCPUにそのオブジェクトが渡される前に呼ばれなくてはなりません。
１０から１４行目にある kref_get() 関数はカウンタを無条件にアトミックに加算します。atomic_inc() プリミティブはすべてのプラットフォームであらわにコンパイラ最適化を無効にするわけではありませんが、kref プリミティブが個別のモジュールに存在し、 Linux カーネルのビルドプロセスがモジュールをまたがる最適化をしないという事実の結果、同じ効果が得られます。１６から２８行目の kref_put() 関数はカウンタをアトミックに減算し、結果がゼロなら、２４行目で指定された release() 関数を呼びます。２４行目から戻ったら、コール元に release() が呼ばれたことを知らせませす。そうでない場合、kref_put() はゼロを返し、 release() が呼ばれなかったことを知らせませす。
クイッククイズ９．３：
図９．２の２２行目、atomic_sub_and_test() が呼ばれた直後、他のCPUが kref_get() を呼んだとします。この結果、他のCPUは解放されたオブジェクトに不正な参照を持っていることになりませんか。
クイッククイズ９．４：
kref_sub() がゼロを返し、 release() が呼ばれなかったことを知らせたとします。コール元が、このオブジェクトが継続的に存在することを期待できるのは、どのような条件下でしょうか。
９．１．１．３ 解放時にメモリバリアを使うアトミックカウンティング
このスタイルの参照は、 Linux カーネルのネットワーク層で、パケットルーティングに使う宛先キャッシュを追跡するために使われます。実際の実装はかなり面倒なので、この節では struct dst_entry の参照カウント操作にフォーカスします。それは図９．３に示され、このユースケースに当てはまります。
dst_clone() プリミティブはコール元が既に指定された dst_entry の参照を持っている時に使うことができます。そして、コール元はカーネル内の他のエンティティに渡すためにもうひとつの参照を得ます。コール元は既に参照を持っているので、dst_clone() がメモリバリアを実行する必要はありません。dst_entry を他のエンティティに渡す行為はメモリバリアを必要とするときもしない時もあります。しかし、メモリバリアが必要ならば、 dst_entry を渡す時に使う機構の中に埋め込まれているはずです。
dst_release() プリミティブは任意の環境で呼ばれることがあり、コール元は dst_release() を呼ぶ直前に、dst_entry 構造体の要素を参照していることは十分にありえます。このため、dst_release() プリミティブは１４行目にメモリバリアを持ち、コンパイラとCPUがアクセスを誤って並び替えないようにします。
なお、dst_clone() と dst_release() を使うプログラマーは、メモリバリアを意識する必要はありません。これら２つのプリミティブを使う規則を知っていればよろしい。
９．１．１．４ チェックを伴い解放時にメモリバリアを使うアトミックカウンティング
コール元がまだ参照を持っていないオブジェクトに新しい参照を得ないといけない状況を考えましょう。最初の参照カウント確保が、参照カウント解放と同時に走ることがあるために、より複雑です。参照カウント解放で、新しい参照カウントの値がゼロだとわかったとします。これは、今や参照カウントされるオブジェクトをクリーンアップしても安全だという印です。明らかにそのようなクリーンアップが始まった後、参照カウントの確保を開始させてはいけません。このため、確保はゼロ参照カウントのチェックを含む必要があります。チェックは、以下に示すように、アトミック加算の一部でなくてはいけません。
クイッククイズ９．５：
参照カウントがゼロであるチェックを、単純な「if」文で行って、アトミック加算をその次の「then」節で行ってはいけないのはなぜでしょう？
Linux カーネルの fget() とfput() プリミティブはこのスタイルの参照カウンティングを使います。これらの関数の簡略化されたバージョンを図９．４に示します。
fget() の４行目は、現在プロセスのファイル記述子テーブルへのポインターをフェッチします。それは他のプロセスと共用されていることがあります。６行目で rcu_read_lock() を呼び、RCUリード側クリティカルセクションに入ります。これ以降のすべてのcall_rcu() プリミティブから呼ばれるコールバック関数は、対応するrcu_read_unlock() （この例だと１０行目あるいは１４行目）が呼ばれるまで遅延されます。７行目で、 fd 引数で指定されるファイル記述子に対応するファイル構造体を検索します。これについては後述します。指定のファイル記述子に対応するオープンファイルがあれば、９行目でアトミックに参照カウントを得ようとします。失敗したら１０と１１行目でRCUリード側クリティカルセクションを抜けて失敗を返します。そうでなく、成功したら、１４と１５行目でリード側クリティカルセクションを抜けてファイル構造体へのポインターを返します。
fcheck_files() プリミティブは、 fget() のヘルパー関数です。それは、rcu_dereference() プリミティブを使って、後でデレファレンスするために、安全に、RCU で保護されているポインターをフェッチします。（この関数は、DEC Alpha のように、データ依存がメモリオーダリングを強制しないCPUでは、メモリバリア命令を展開します。）２２行目で、rcu_dereference() を使ってこのタスクの現在ファイル記述子テーブルのポインターをフェッチし、２４行目で指定されたファイルが範囲内にあるか見ます。そうなら、２５行目でまた、rcu_dereference() プリミティブを使って、ファイル構造体のポインターをフェッチします。２６行目でファイル構造体へのポインタを返します。失敗したらNULLを返します。
fput() プリミティブはファイル構造体への参照を解放します。３１行目でアトミックに参照カウントを減算し、結果がゼロなら、３２行目で call_rcu() プリミティブを呼んで、ファイル構造体を解放します。（call_rcu() の２つ目の引数である file_free_rcu() 関数を使います。）ただし、解放がされるのは、すべての現在実行中のRCUリード側クリティカルセクションが完了してからです。すべての現在実行中のRCUリード側クリティカルセクションが完了するまでに必要な時間間隔を、「グレースピリオド」と呼びます。なお、atomic_dec_and_test() プリミティブはメモリバリアを含みます。この例では、このメモリバリアは不要です。構造体は、RCUリード側クリティカルセクションが完了するまで破壊されないからです。しかし、 Linux では結果を返すすべてのアトミック操作は、定義によってメモリバリアを含まなくてはいけません。
グレースピリオドが終わったら、３９行目でfile_free_rcu() 関数がファイル構造体へのポインターを得て、４０行目で解放します。
このアプローチは、Linux の仮想記憶システムでも使われています。ページ構造体を扱う get_page_unless_zero() と put_page_testzero() 、そして、メモリマップ構造体を扱う try_to_unuse() と mmput() を見てください。
９．１．２ ハザードポインター
前の節で説明したすべての参照カウンティング機構は、参照カウントを取ろうとするときに、データ要素が削除されるのを防ぐための、別の機構を必要としました。別の機構とは、そのデータ要素にあらかじめ取られている参照、ロック、RCU、アトミック操作などでした。しかしそれらは全て性能やスケーラビリティを落としたり、ユースケースに制限がありました。
これらの問題を避ける一つの方法は、参照カウンタを裏返しにもうけることです。つまり、データ構造に格納されている整数を加算するのでなく、データ要素へのポインターをCPU（あるいはスレッド）ごとのリストに格納します。このリストの各要素はハザードポインタと呼ばれます [Mic04]。
脚注
他の人も、独立に発明しました [HLM02].。
あるデータ要素の「仮想参照カウンタ」の値は、その要素を参照しているハザードポインタを数えれば求められます。このため、ある要素がリーダーからアクセスできなくなりそれを参照しているハザードポインタもなければ、その要素は安全に解放できます。
もちろん、ハザードポインタの確保は同時に起きる削除との破壊的競合を避けるためにとても慎重にしなければいけません。図９．５は、１つの実装です。１から１３行目に、hp_store() が、１５から２０行目に hp_erase() があります。smp_mb() プリミティブは、１４．２節で詳しく説明するので、この簡単な説明のためには無視して下さい。データ要素のポインターは、p で参照されます。そのデータ要素のためのハザードポインタは、 hp に記録されます。hp_store() は、同時更新をチェックしながら、ハザードポインタを記録します。同時更新があると、hp_store() は、ハザードポインタを記録するのを拒否してゼロを返し、コール元がトラバーサルを最初からやり直さなければいけないことを伝えます。そうでない時、hp_store() は、１を返し、そのデータ要素のためのハザードポインタを記録できたことを伝えます。
クイッククイズ９．６：
なぜ、図９．５の hp_store() は、データ要素の２重間接参照をとるのでしょう？なぜ、void * でなく void ** なのでしょう？
クイッククイズ９．７：
なぜ、 hp_store() のコール元は、失敗の時、トラバーサルを最初からやり直さないといけないのでしょう？大きなデータ構造の時、非効率でしょう。
クイッククイズ９．８：
ハザードポインタの論文では、ポインタのボトムビットを削除された要素であることの印とします。HAZPTR_POISON とはなんでしょう？
ハザードポインタを使うアルゴリズムは、データ構造をトラバースするどのステップでも、再開始される可能性があります。このため、そういうアルゴリズムは、典型的には、すべての関連するハザードポインタを確保し終わるまでは、データ構造に一切変更を加えないように注意する必要があります。
クイッククイズ９．９：
でも、このハザードポインタに関する制限は、他の形の参照カウンティングにも適用されなければいけないのではないですか？
これらの制限と引き換えに、ハザードポインタは、リーダーに対してすばらしい性能とスケーラビリティを提供します。他の機構との性能の比較は、１０章と、他の論文で見ることができます。
９．１．３ 参照カウンティングをサポートする Linux プリミティブ
前の例で使われた Linux カーネルプリミティブを以下のリストにまとめます。
・ atomic_t アトミックに操作される 32-bit 量の定義。
・ void atomic_dec(atomic_t *var); メモリバリアの発行とコンパイラ最適化の無効化を必ずしもすることなく、参照される変数をアトミックに減算します。
・ int atomic_dec_and_test(atomic_t *var); 参照される変数をアトミックに減算します。結果がゼロの場合、真（ゼロ以外）を返します。メモリバリアを発行します。このプリミティブを越えてメモリ参照を動かす可能性のあるコンパイラ最適化を無効にします。
・ void atomic_inc(atomic_t *var); メモリバリアの発行とコンパイラ最適化の無効化を必ずしもすることなく、参照される変数をアトミックに加算します。
・ int atomic_inc_not_zero(atomic_t *var); 値がゼロでない場合に限り、参照される変数をアトミックに加算します。加算が起きたら、真（ゼロ以外）を返します。メモリバリアを発行します。このプリミティブを越えてメモリ参照を動かす可能性のあるコンパイラ最適化を無効にします。
・ int atomic_read(atomic_t *var); 参照される変数の整数値を返します。これはアトミック操作ではありません。そして、メモリバリア命令は何も発行しません。これを、「アトミックなリード」と考えるのでなく、「アトミック変数からの通常のリード」と考えて下さい。
・ void atomic_set(atomic_t *var, int val); 参照されるアトミック変数の値を、“val”に設定します。これはアトミック操作ではありません。そして、メモリバリア命令は何も発行しません。これを、「アトミックな設定」と考えるのでなく、「アトミック変数への通常の設定」と考えて下さい。
・ void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head)); 現在実行している全てのRCUリード側クリティカルセクションが完了したしばらく後に、func(head) を呼びます。なお、call_rcu() プリミティブは直ちに戻ります。head は通常は、RCUで保護されるデータ構造内のフィールドであり、func は通常はこのデータ構造を解放する関数であることに注意下さい。call_rcu() を呼んでから、func が呼ばれるまでの期間を、「グレースピリオド」と呼びます。グレースピリオドを含む全ての期間は、それ自身がグレースピリオドです。
・ type *container_of(p, type, f); 指定された型の構造体内のフィールド f へのポインタ p をもらって、その構造体へのポインタを返します。
・ void rcu_read_lock(void); RCU リード側クリティカルセクションの開始を印づけます。
・ void rcu_read_unlock(void); RCU リード側クリティカルセクションの終了を印づけます。RCU リード側クリティカルセクションはネスト可能です。
・ void smp_mb__before_atomic_dec(void); プラットフォームの atomic_dec() プリミティブが既にそうしていない場合に限り、メモリバリアを発行し、コードを移動するコンパイラ最適化を無効にします。 ・ struct rcu_head RCU インフラ構造が使うデータ構造で、グレースピリオドを待っているオブジェクトを追跡します。これは通常は、RCUで保護されるデータ構造内のフィールドとして含まれます。
クイッククイズ９．１０：
atomic_read() と atomic_set() はアトミック操作ではないって、悪い冗談でしょう？
９．１．４ カウンタ最適化
加算と減算が一般的で、ゼロとの比較がまれであるときは、５章で述べたような、CPUあるいはタスクごとのカウンタを維持するのも意味があります。RCUにこの技術を適用した例が、付録Dにあります。このアプローチは、加算と減算プリミティブでアトミック命令やメモリバリアを不要にします。ただし、コードを移動するコンパイラ最適化は無効しなければいけません。さらに、synchronize_srcu() のように、参照カウンタの総和がゼロになるのをチェックするプリミティブはとても遅い可能性があります。これは、この技術が、参照が頻繁に確保、解放されるが、ゼロ参照カウントをチェックするのはほとんど必要ない状況のために設計されたものであるという事実を強調します。
しかし、参照カウンタを使うということは、それを使わない時にはリードオンリイであるデータ構造への書き込み（しばしば、アトミックな）が必要となることが通常、多いです。その場合、参照カウンタはリーダーに高価なキャッシュミスを強いることになります。
クイッククイズ９．１１：
でも、ハザードポインタはデータ構造への書き込みはしないです！
なので、リーダーが書き込みを一切しないで良い同期機構を考えるのは意味のあることです。次の節は、そういう同期機構の１つであるシーケンスロックを紹介します。
９．２ シーケンスロック
シーケンスロックは、Linux カーネルで、主にリードされることが多く、リーダーにとって一貫した状態で読まれなくてはいけないデータに使われます。しかし、リーダーライターロックと違って、リーダーはライターを排除しません。その代わりに、ハザードポインタと同じように、シーケンスロックはリーダーが同時実行されるライトアクティビティを検出したら操作をリトライさせます。図９．６でわかるように、シーケンスロックを使うコードは、リーダーがめったにリトライする必要が無いように設計するのが大事です。
クイッククイズ９．１２：
なぜ、このシーケンスロックの議論は、ロックについての７章にないのでしょう。
シーケンスロックのキーコンポーネントはシーケンス番号です。それは、ライターがいないときは偶数で、更新中の時は奇数です。リーダーは、その値を、各アクセスの前と後でスナップショットします。スナップショットのどれかが奇数であるか、２つのスナップショットが異なる場合、同時に更新があったわけで、リーダーはアクセスの結果を捨てて、リトライする必要があります。リーダーは、シーケンスロックで守られるデータをアクセスする時に、図９．７の read_seqbegin() と read_seqretry() 関数を使います。ライターは各更新の前と後で値を加算します。一度に一人のライターしか許されません。ライターはシーケンスロックで守られるデータを更新する時に、図９．８の write_seqlock() と write_sequnlock() 関数を使います。
シーケンスロックで守られたデータには任意の数の多数の同時実行するリーダーがいてもかまいません。しかし、ライターは一度に一人です。シーケンスロックは、Linux カーネルで、タイムキーピングに使うキャリブレーション量を守るために使われます。パス名トラバースで、同時実行するリネーム操作を検出するためにも使われます。
クイッククイズ９．１３：
同時の追加、削除、検索をサポートする連結リストを守るために、シーケンスロックだけを同期機構として使うことができますか？
シーケンスロックの簡単な実装を図９．９（seqlock.h）に示します。１から４行目に seqlock_t データ構造があり、シーケンス番号とライターをシリアライズするロックがあります。６から１０行目は seqlock_init() で、名前のとおり、seqlock_t を初期化します。１２から２２行は read_seqbegin() で、シーケンスロックのリード側クリティカルセクションを始めます。１７行目でシーケンスカウンタのスナップショットを取って、１８行目はこのスナップショット操作を、コール元のクリティカルセクションの前に並べます。１９行目でスナップショットが奇数、つまり、同時実行するライターがいるか見ます。そうなら、２０行目で最初に戻ります。そうでなければ、２１行目でスナップショットの値を返し、それをコール元は後で read_seqretry() を呼ぶ時に与えます。
クイッククイズ９．１４：
なぜ、図９．９の１９行目 read_seqbegin() でわざわざチェックをするのでしょう。新しいライターはいつでも始まることがあるのですから、単純にそのチェックを３１行目の read_seqretry() と一緒にしたらいけないのですか？
２４から３２行目は read_seqretry() で、対応する read_seqbegin() から今までにライターがいなければ真を返します。２９行目は、３０行目のシーケンスカウンタの新しいスナップショットのフェッチの前に、コール元の以前のクリティカルセクションを並べます。最後に、３０行目でシーケンスカウンタが変わっていない、つまり、ライターがいなかったことを確認して、そうならば真を返します。
クイッククイズ９．１５：
なぜ、図９．９の２９行目、smp_mb() がいるのでしょう？
クイッククイズ９．１６：
図９．９のコードで、より弱いメモリバリアを使うことはできませんか？
クイッククイズ９．１７：
シーケンスロックの更新がリーダーを飢餓させることはありませんか？
３４から３９行目は write_seqlock() です。それは単純にロックを取って、シーケンス番号を加算して、メモリバリアを実行します。それは、この加算が、コール元のクリティカルセクションの前に並ぶのを保証するためです。４１から４６行目は write_sequnlock() です。これは、メモリバリアを実行して、コール元のクリティカルセクションが４４行目のシーケンス番号の加算より前に並ぶことを保証し、そしてロックを放します。
クイッククイズ９．１８：
ロック以外のものを使って、ライターをシリアライズすることができますか？
クイッククイズ９．１９：
図９．９の２行目、seq は、なぜ、unsigned long でなくて、unsigned でしょう？結局、unsigned が Linux カーネルにとって十分ならば、他のどんな場合でもそれで十分でないでしょうか？
シーケンスロックの、リード側とライト側の両方のクリティカルセクションは、トランザクションと考えることができます。なので、シーケンスロックは、１６．２節で説明するトランザクショナルメモリの限定された形と思うことができます。シーケンスロックの制限は、以下です。（１）シーケンスロックは更新を制限します。（２）シーケンスロックは更新によって解放されるかもしれないオブジェクトへのポインタのトラバースを許しません。これらの制限は、もちろん、トランザクショナルメモリによって克服されますが、シーケンスロックと他の同期プリミティブを組み合わせることによってもそれは可能です。
シーケンスロックでは、ライターがリーダーを遅延させることがありますが、逆はありません。これは、不公平ですし、ライターが重い負荷のもとでは飢餓にもつながります。一方、ライターがいない時は、シーケンスロックのリーダーは十分に高速で線形にスケールします。両方の世界のいいところを欲しがるのは人間だけです。高速なリーダー、リード側の失敗はなし、飢餓が無いのはもちろん。さらに、シーケンスロックのポインタについての制限も外せたら、けっこうなことでしょう。以下の節は、まさにこういう特性を持った同期機構を紹介します。
９．３ Read-Copy Update (RCU)
この節では、RCU を、いろいろな異なる見方から説明します。９．３．１節はRCUの古典的な紹介をします。９．３．２節は基本的なRCUの概念を説明します。９．３．３節はRCUのよくある使い方を紹介します。９．３．４節は Linux カーネルAPIを説明します。９．３．５節はユーザーレベルRCUの「おもちゃの」実装のシーケンスを説明します。最後に、９．３．６節はRCUの練習問題を提供します。
９．３．１ RCUの紹介
あなたが、徐々に変化するデータをアクセスする必要のある並列リアルタイムプログラムを書いているとします。データ変化は、温度、湿度、気圧のために起こるとします。このプログラムのリアルタイム応答要件はとてもきついので、スピンもブロックも許されないため、ロックは問題外です。また、リトライループも許されないため、シーケンスロックも使えません。幸運にも、温度と気圧は普段は制御されているため、ハードコードされたデフォルトのデータのセットが普通は十分です。
しかし、温度、湿度、気圧は時々、デフォルトから遠く離れることがあるので、そのような状況では、デフォルトに代わるデータを提供する必要があります。温度、湿度、気圧はゆっくり変わるので、変化後の値を提供するのは、２，３分のうちに行われる必要はあるものの、緊急ではありません。このプログラムは、想像力豊かに gptr と名付けられたグローバルポインタを使います。それは通常は NULL で、デフォルト値を使うべきだということです。そうでない場合、gptr は想像力豊かにa, b, c と名付けられ、リアルタイムの計算で使われる値を提供する構造体を指します。
必要な時に、リアルタイムリーダーを妨げることなく、変化後の値を安全に提供するにはどうしたらいいでしょう。
図９．１０に、古典的なアプローチがあります。最初の行はデフォルトの状態で、gptr はNULLです。２行目は構造体を確保しました。疑問符がついていることで示されるように、初期化はされていません。３行目は構造体を初期化しました。次に、gptr がこの新しい要素を指すように設定します。
脚注
多くの計算機システムで、単純な代入は、コンパイラとCPU の干渉があるため、不十分です。９．３．２節はこの問題を扱います。
現代的な汎用システムではこの設定はアトミックです。つまり、同時実行するリーダーはNULLポインタを見るか、新しい構造体 p を指すポインタを見るかのいずれかで、両方の値からのビットが混ざったものを見ることはありません。このため、それぞれのリーダーはデフォルト値のNULLか新しくインストールされたデフォルトでない値のいずれかを得ることが保証されます。いずれの場合も、リーダーが見る結果は一貫しています。さらに良いことに、リーダーは高価な同期プリミティブを使う必要もないので、このアプローチはリアルタイム用途にとても適しています。
脚注
繰り返しますが、多くの計算機システムで、コンパイラと、さらに DEC Alpha システムにおいてはCPUも、の干渉を防ぐために、余分の仕事が必要です。９．３．２節を参照。
しかし、遅かれ早かれ同時実行するリーダーが参照しているデータを削除しなくてはいけない時が来ます。より複雑な例を考えましょう。図９．１１にあるように、連結リストから要素を削除します。リストは最初、要素 A, B, C を持ち、要素 B を削除する必要があります。まず、 list_del() を使って削除を実行します。
脚注
またまた、これは現実を近似的に示しただけです。９．３．２節を参照。
この時点で、すべての新しいリーダーは B はリストから削除されているのを見ます。しかし、古いリーダーがまだこの要素を参照しているかもしれません。これらすべての古いリーダーが終わったら、安全に要素 B を解放できます。この結果、図の一番下の状況となります。
しかし、リーダーが終わったことはどうやってわかるでしょう。
参照カウントスキーマに頼りたくなるかもしれませんが、５章の図５．３は、それが長い遅延を起こすことがあるのを示します。それは、すでにあきらめた、ロックとシーケンスロックのアプローチと同じです。
論理的な極限を考えましょう。リーダーは自分の存在を全く表明しないとします。このアプローチは明らかに、リーダーにとって最高の性能を可能とします。（タダというのはお値段として最高です。）しかし、更新者が、すべての古いリーダーがいなくなったことをどうやって知るかという問題には答えません。この問題に妥当な回答を得るためには、何らかの追加の制限が必要なのは明らかです。
ある種のリアルタイムオペレーティングシステム（そしてあるオペレーティングシステムカーネル）にうまく適する１つの制限は、スレッドがプリエンプションされないケースを考えることです。そのような、ノンプリエンプティブ環境では、各スレッドは、あらわに、そして自分からすすんで、ブロックするまで走ります。これはつまり、ブロックしない無限ループは、無限ループを始めたら以降、あるCPUをそれ以外の目的には使えなくなるということです。
脚注
それに対して、プリエンプト可能環境の無限ループはプリエンプトされることがあります。この無限ループはそれでもかなりのCPUをむだに使いますが、問題のCPUはそれでも他の仕事もできます。
ノンプリエンプティブということはさらに、スレッドはスピンロックを持っているときはブロックしてはいけないことも要求します。この要求がないと、ブロックしたスレッドの持つスピンロックを取ろうとして回るスレッドですべてのCPUが消費されることになるおそれがあります。回っているスレッドはロックを取るまでCPUを放そうとしません。しかし、ロックを持っているスレッドは回っているスレッドのうち１つがCPUを放さないとロックを放すことができないかもしれません。これは古典的なデッドロックの状況です。
この同じ制限を、連結リストをトラバースするリーダースレッドに適用してみましょう。このスレッドはトラバーサルを終えるまでブロックしてはいけません。図９．１１の２つ目の行に戻ると、更新者はちょうど list_del() を実行し終わったところです。CPU ０がコンテキストスイッチしたとしましょう。リーダーは連結リストをトラバースしている間はブロックできないので、CPU０で実行していたかもしれないすべての以前のリーダーは完了していると保証できます。他のCPUについてもこの論理を適用すれば、それぞれのCPUが一度、コンテキストスイッチを実行したことが観察されたならば、すべての以前のリーダーは完了しており、要素 B を参照しているリーダースレッドはいないことが保証できます。このため更新者は安全に要素 B を解放でき、図９．１１の最後の状況になります。
図９，１２はこのアプローチを図で示したものです。時間は、図の上から下へ流れます。
このアプローチの本番品質の実装はとても複雑になるでしょうが、おもちゃの実装は驚くほど簡単です。
1 for_each_online_cpu(cpu) 2 run_on(cpu);
for_each_online_cpu() プリミティブはすべてのCPUを列挙し、run_on() 関数は現在のスレッドが指定したCPUで実行するようにします。それは宛先CPUにコンテキストスイッチを強要します。このため、一度、for_each_online_cpu() が終わったら、それぞれのCPUはコンテキストスイッチを実行済みであり、ということはすべての以前のリーダースレッドは完了したことを保証できます。
このアプローチは、本番品質ではないことに注意下さい。多くの特殊ケースを正しく扱うことができ、多くの強力な最適化が必要なため、本番品質の実装はずっと複雑です。さらに、プリエンプティブ環境のための RCU実装は、リーダーが実際に何かをする必要があります。しかし、この単純な、ノンプリエンプティブアプローチは、概念的には完全であり、次の節で説明するRCUの基本を理解するための最初の基礎として、優れたものです。
９．３．２ RCUの基本要素
著者：Paul E. McKenney and Jonathan Walpole
Read-copy update (RCU) は、２００２年の１０月に Linux カーネルに加わった同期機構です。RCU は、更新と同時の参照を可能とすることで、スケーラビリティを改善しました。従来のロックプリミティブは、参照か更新かにかかわらず同時実行するスレッドの相互排他を保証しました。あるいは、リーダーライターロックは、同時実行する参照を許しましたが更新がないときに限りました。これらと異なり、RCUは１人の更新者と複数のリーダーの同時実行をサポートします。RCUはオブジェクトの複数のバージョンを持ち、すべての既存のリード側クリティカルセクションが完了するまでオブジェクトは解放されないようにします。これにより、リードがコヒーレントであることを保証します。RCUはオブジェクトの新しいバージョンをパブリッシュあるいは参照する効率的でスケーラブルな機構を定義し、使用します。さらに、オブジェクトの古いバージョンの回収を遅延させる機構も定義、使用します。これらの機構は、リードのパスがものすごく速くなるように、リードとライトのパスの間で仕事を分配します。ある場合（ノンプリエンプティブカーネル）には、RCUのリード側プリミティブはオーバーヘッドがゼロです。
クイッククイズ９．２０：
９．２節のシーケンスロックも、リーダーと更新者が同時実行するのを許しませんでしたか？
これは、「RCUとは実は何なのか？」という疑問や、「RCUはなぜうまくいくのか？」という疑問を引き起こすでしょう。（あるいは、たまにですが、RCUがうまくいかないという宣言につながることもあります。）この文書は、基本的な視点から、前記の疑問に答えます。後の項は、その使用法とAPIという視点からそれを取りあつかいます。最後の項は参考文献をリストします。
RCUは３つの基本的機構からなります。１つ目は挿入に使われ、２つ目は削除に、３つ目はリーダーが同時実行する挿入と削除に耐えられるようにするために使われます。９．３．２．１節は、挿入に使われるパブリッシュ、サブスクライブ機構を説明します。９.．３．２．２節は既存のRCUリーダーを待つことで削除がどのように可能となるかを説明します。９．３．２．３節は最近更新されたオブジェクトの複数のバージョンを維持することで、同時実行する挿入と削除がどのように可能となるかを説明します。最後に、９．３．２．４節はRCUの基本をまとめます。
９．３．２．１ パブリッシュ、サブスクライブ機構
RCUの１つのキーとなる特性は、データが同時に変更されていても安全にデータを走査することができることです。同時実行する挿入を可能とするこの特性を提供するために、RCUはパブリッシュ、サブスクライブ機構と考えることができるものを使います。例えば、最初が NULL のグローバルポインター gp があり、新しく確保され初期化されたデータ構造を指すように更新されるとしましょう。図９．１３に示したコード断片（適当なロックを加えて）が、この目的のために使えるでしょう。
残念なことに、コンパイラとCPUが最後の４つの代入文をこの順で実行するように強制するものはなにもありません。gp への代入が p のフィールドの初期化の前に起きたら、同時実行するリーダーは初期化されていない値を見るかもしれません。メモリバリアを使って順番を保証する必要がありますが、メモリバリアは使うのが難しいことで有名です。なので、パブリケーションセマンティクスを持つ rcu_assign_pointer() プリミティブにそれらをカプセル化します。すると、最後の４行はこうなります。
rcu_assign_pointer() は、新しい構造体をパブリッシュし、コンパイラとCPUが、 gp への代入を p が参照するフィールドへの代入の後に実行されるように強制します。
しかし、更新者においてオーダリングを強制するだけでは十分でなく、リーダーでも適当なオーダリングを強制する必要があります。例えば、以下のコード断片を見ましょう。
このコード断片はミスオーダリングは起きなさそうに見えます。しかし、残念なことに、 DEC Alpha CPU や、value-speculation コンパイラ最適化は、信じられないかもしれませんが、値 p->a, p->b そして p->c が、 p の値の前にフェッチされるようにすることがあります。value-speculation コンパイラ最適化のケースを考えるのが最も簡単でしょう。その場合コンパイラは、 p の値を推測し、p->a, p->b そして p->c をフェッチし、そして、実際の p の値をフェッチして、推測が正しかったかをチェックします。この種の最適化はとてもアグレッシブです。たぶん正気と言えないほど。しかし、プロファイルドリブンの最適化のコンテキストでは実際に起きることがあります。
明らかに、コンパイラとCPUが行うこのようなインチキはやめさせる必要があります。rcu_dereference() プリミティブは、このために必要なメモリバリア命令とコンパイラディレクティブをなんでも使います。
脚注
Linux カーネルでは、 rcu_dereference() は volatile キャストを使って、なお DEC Alpha においては、メモリバリア命令によって実装されます。C11 と C++11 標準では、 memory_order_consume が、 rcu_dereference()のためのより長期に渡るサポートを提供するためにあります。しかし、これをネイティブに実装するコンパイラは、まだありません。（それらはその代わりに、 memory_order_consume を、 memory_order_acquire に強化していますが、これは弱いオーダリングのシステムでは不要なメモリバリア命令を生成します。）
このため、rcu_dereference() プリミティブは、指定されたポインタの、与えられた値にサブスクライブすると考えることができます。このとき、そのポインタをパブリッシュした、対応する rcu_assign_pointer() 操作の前に起きたすべての初期化が、以降のデレファレンス操作で見えることが保証されます。rcu_read_lock() と rcu_read_unlock() 操作は絶対に必要です。これによって、RCUリード側クリティカルセクションの範囲が定義されます。その目的は、９．３．２．２節で説明します。ただ、それらは、けっして、スピンもブロックもすることなく、list_add_rcu() が同時実行するのを妨げることもありません。実際、CONFIG_PREEMPT がついてないカーネルでは、それらは全くコードを生成しません。
理論的には、 rcu_assign_pointer() と rcu_dereference() を使えばすべてのRCU 保護されたデータ構造を作ることができますが、実際には高レベルの構造を使うほうが普通はよいです。なので、rcu_assign_pointer() と rcu_dereference() プリミティブは、Linux のリスト操作 API の特別なRCU変種に組み込まれています。Linux には、２重連結リストの２つの変種があります。循環の struct list_head と、線形の struct hlist_head/struct hlist_nodeペアです。前者は図９．１４のようになります。緑の（最も左の）箱が、リストヘッダーで青い（右の３つ）箱がリストの要素です。この表記はめんどうなので、図９．１５のように省略されます。ヘッダー以外（青い）要素だけが表示されます。
ポインタをパブリッシュする例を連結リストに適用すると、図９．１６で示すコードになります。
１５行目は、複数の list_add_rcu() インスタンスが同時実行しないように、何らかの同期機構で（最も一般的には何らかのロック）保護されなくてはいけません。しかし、その同期は、RCUリーダーが list_add_rcu() と同時実行するのを妨げません。
RCU保護されたリストにサブスクライブするのは簡単です。list_add_rcu() プリミティブはエントリをパブリッシュします。指定リストの先頭に挿入し、対応する list_for_each_entry_rcu() の実行が正しくこの同じエントリをサブスクライブすることを保証します。
クイッククイズ９．２１：
list_for_each_entry_rcu() が list_add_rcu() と全く同時に実行することになった時に、セグメントフォールトしないでしょうか。それはなぜですか？
Linux のもうひとつの二重連結リスト、 hlist は、線形リストです。つまり、図９．１７に示すように、ヘッダには、循環リストの時の２つと違って、１つしかポインタが必要ではありません。なので、hlist を使うと、巨大なハッシュテーブルのハッシュバケツ配列のメモリ使用量を半分にできます。以前と同じく、この表記は面倒なので、図９，１５の list と同様に、hlist の表記も簡略化されます。図９．１８に示す、新しい要素をRCUで保護された hlist にパブリッシュするのは、循環リストのときにそうすることと、とても似ています。
前と同じく、１５行目はロックのような何らかの同期機構によって保護されなくてはいけません。
RCU保護された hlist にサブスクライブするのも、循環リストと似ています。
クイッククイズ９．２２：
なぜ、hlist_for_each_entry_rcu() には、２つのポインタを渡さないといけないのでしょう？ list_for_each_entry_rcu() のときは１つでよかったのに。
表９．２は、RCUパブリッシュとサブスクライブのプリミティブのセットと、もうひとつの、「アンパブリッシュ」つまり取り消すプリミティブを示します。
なお、list_replace_rcu(), list_del_rcu(), hlist_replace_rcu(), そして hlist_del_rcu() API は、ある問題を明らかにします。置換あるいは削除したデータ要素を解放しても安全なのはいつでしょう？特に、そのデータ要素への参照をすべてのリーダーが解放したのをどうやって知ったら良いでしょう？
次の節で、この問いに答えます。
９．３．２．２ 既存のRCUリーダーが完了するのを待つ
最も基本の形では、RCUはものごとが終わるのを待つ方法です。もちろん、ものごとが終わるのを待つ方法は他にもそれはたくさんあります。参照カウント、リーダーライターロック、イベントなど。RCUの大きな長所は、（例えば）２００００の異なるものごとが終わるのを待つときに、それぞれのすべてを１つづつ明示的に追跡しないでもいいことです。さらに、明示的な追跡をするスキーマにつきものの、性能低下、スケーラビリティの限界、複雑なデッドロックシナリオ、そしてメモリリークの危険について心配する必要もありません。
RCUの場合、待たれるのは、「RCUリード側クリティカルセクション」と呼ばれるものです。RCUリード側クリティカルセクションは、rcu_read_lock() プリミティブで始まり、対応する rcu_read_unlock() プリミティブで終わります。RCUリード側クリティカルセクションはネストしても良く、多くの任意のコードを含むことができます。ただし、コードは明示的にブロックやスリープしてはいけません。（なお、RCUの特別な形式で、SRCU と呼ばれるものは、SRCU リード側クリティカルセクション内で一般的なスリープを許します。）以上の条件を守れば、RCUを、任意の望むコード断片が完了するのを待つために使うことができます。
RCUはこの芸当を、その他のものごとが完了したかを間接的に判断することで達成します。詳しくは、付録Dを参照。
特に、図９．１９でわかるように、RCU は既存のRCUリード側クリティカルセクションが完全に終わるのを待つ方法です。それには、前記クリティカルセクションが実行したメモリ操作も含まれます。しかし、あるグレースピリオドが始まった後で開始ししたRCUリード側クリティカルセクションは、そのグレースピリオドが終わるまで続くこともあり、それがグレースピリオドを引き伸ばすこともあることに注意下さい。
以下の擬似コードは、RCUを使ってリーダーを待つためのアルゴリズムの基本形です。
１ 変更をする。例えば、連結リストの要素を置換する。
２ すべての既存のRCUリード側クリティカルセクションが完全に終わるまで待つ。（例えば、synchronize_rcu() プリミティブを使う。）ここでキーとなる事実は、以降のRCUリード側クリティカルセクションは、今削除された要素への参照を得る方法がないことです。
３ 後始末。例えば、前に置換された要素を解放する。
図９．２０で示したコード断片は、９．３．２．１節から持ってきたものですが、この処理を説明します。a は検索キーです。
１９，２０と２１行は、前述の３つのステップを実装します。１６から１９行目は RCU (“read-copy update”) の名前の由来を示します。同時リードを許しながら、１６行目はコピーをし、１７から１９行目は更新をします。
９．３．１節で説明したように、synchronize_rcu() プリミティブはとても簡単であることもできます。（９．３．５節のいろいろな「おもちゃの」RCU実装を参照）しかし、本番品質の実装は、多くの特殊ケースを正しく扱う必要があり、強力な最適化が必要なため、ずっと複雑になります。でも、synchronize_rcu() の概念的で単純な実装があることを理解できるのは良いことです。ここで疑問となるのは、例えば、RCUリーダーが同時に更新されているリストをトラバースするときに、実際、何を見るかということです。次の節でそれを説明します。
９．３．２．３ 最近更新されたオブジェクトの複数バージョンを維持する
この節は、RCU がどのようにして、複数バージョンのリストを維持し、同期が不要なリーダーを可能とするかを見ます。２つの例を示し、そこで、あるリーダーが参照しているかもしれない要素が、そのリーダーがRCU リード側クリティカルセクションにいる間は、元のままでいなければいけないことを示します。最初の例は、リスト要素の削除で、２つ目の例は、要素の置換です。 例１：削除の間、複数バージョンを維持する
９．３．１節の削除の例をもう一度見ましょう。今回は、RCUの元となる基本概念をちゃんとわかっているという利点があります。この新しい削除の例を始めるには、図９．２０の１１から２１行目をこのように変えます。 このコードは図９．２１に示すように、リストを更新します。それぞれの要素の３つの数字は、フィールド a, b, c の値を示します。赤く塗られた要素は、RCUリーダーがその参照を持っているかもしれないことを示します。なので、図の一番上の初期状態では、すべての要素は赤色です。後ろ向きのポインタと、リストの最後からヘッドへのリンクは、簡単のために省略してあるのに注意下さい。 ３行目の list_del_rcu() が終わった後、5,6,7 要素は、図９．２１の２つ目の行が示すように、リストから除かれています。リーダーは更新者と直接同期しないので、リーダーはこのリストを同時に走査しているかもしれません。これらの同時実行するリーダーは、タイミングによって、今削除された要素を見ることも見ないこともあります。しかし、今削除された要素のポインタをフェッチしたすぐ後に遅延した（例えば、割り込み、ECC メモリエラー、あるいは CONFIG_PREEMPT_RT カーネルの場合プリエンプションのために）リーダーは、削除からずいぶんたったあともリストの古いバージョンを見るかもしれません。このため、私達は今、リストの２つのバージョンを持ちます。5,6,7 要素があるものと、5,6,7 要素がないもの。図の２行目の 5,6,7 要素は、今は黄色です。これは、古いリーダーがまだそれを参照しているかもしれないことと、新しいリーダーはそれへの参照を得られないことを示します。
リーダーは、自分の RCU リード側クリティカルセクションを抜けた後は、5,6,7 要素への参照を持っていることは許されないことに注意下さい。なので、４行目の synchronize_rcu() が終わったら、すべての既存のリーダーは完了したことが保証され、この要素を参照しているリーダーはもういません。これは、図９．２１の３行目の緑色で示されます。こうして、リストのバージョンは１つに戻りました。 この時点で、5,6,7 要素は安全に解放できます。これは、図９．２１の最後の行で示されます。この時点で、5,6,7 要素の削除は完了しました。次の節は、置換です。 例２：置換の間、複数バージョンを維持する
置換の例を始めるには、図９．２０の最後の数行を見ましょう。 ポインタ p を含むリストの初期状態は、削除の例と同じで、図９．２２の最初の行です。 以前と同じく、それぞれの要素の３つの数字は、フィールド a, b, c の値を示します。赤く塗られた要素は、RCUリーダーがその参照を持っているかもしれないことを示します。リーダーは更新者と直接同期しないので、リーダーはこの置換処理全体と同時に走っているかもしれません。今回も、後ろ向きのポインタと、リストの最後からヘッドへのリンクは、簡単のために省略してあるのに注意下さい。 以下の文章は、5,6,7 要素を 5,2,3 に置換し、すべてのリーダーがこれら２つの値のうちどちらかを見るにはどうするか示します。 １行目で、以前のように置換する要素を kmalloc() します。図９．２２の２行目に示す状態になります。この時点で、新しく確保された要素への参照を持っているリーダーはいません。（緑色で示されます。）そして、それは初期化されていません。（感嘆符で示されます。） ２行目で古い要素を新しい要素に複写します。図９．２２の３行目の状態になります。新しく確保された要素はまだリーダーには参照されませんが、初期化がされました。 ３行目は、 q->b を “2”の値にし、４行目は q->c を“3”の値にします。図９．２２の４行目です。 次に、５行目は置換をします。ここで、新しい要素はついにリーダーから見えるようになります。なので、赤色です。図９．２２の５行目です。この時点で、以下に示すように、私達はリストの２つのバージョンを持ちます。既存のリーダーは 5,6,7 要素を見るかもしれません。（なので、黄色です。）しかし、新しいリーダーはそうでなくて 5,2,3 要素を見ます。すべてのリーダーは、どちらかの正しく定義されたリストを見ることが保証されます。 ６行目の synchronize_rcu() が戻ったら、グレースピリオドが経過したので、list_replace_rcu() の前に開始したすべてのリードは完了したはずです。特に、5,6,7 要素への参照を持っているかもしれないすべてのリーダーはそれぞれの RCU リード側クリティカルセクションを抜けたことが保証されます。なので、参照を持ち続けることは許されません。このため、古い要素への参照を持っているリーダーはもういないはずです。これは、図９．２２の６行目で示されます。リーダーから見る限り、リストのバージョンは１つに戻りました。ただし、新しい要素が古いものと変わっています。 ７行目の kfree() が終わったら、リストは図９．２２の最後の行になります。 RCU の名前は、置換ケースのためにつけられましたが、Linux カーネルでの RCU の使用の大部分は、９．３．２．３節に示した単純な削除のケースです。 議論 これらの例は、更新操作の間はずっと、mutex が取られていると仮定しています。ということは、ある時点でアクティブなのは、最大でも２つのリストのバージョンだということです。 クイッククイズ９．２３： 削除の例を直して、リストの２つ以上のバージョンがアクティブであるのを可能にするにはどうしますか？ クイッククイズ９．２４： ある時点で、あるリストのいくつの RCU バージョンがアクティブであることが可能ですか？ このイベントのシーケンスは、RCU 更新が、複数バージョンを使って、同時実行するリーダーがいても変更を安全に行えることを示しました。もちろん、アルゴリズムによっては、複数バージョンを優雅に扱えないものもあります。そのようなアルゴリズムを変更して、RCU を使えるようにする技術はありますが、この節のスコープを超えます。
９．３．２．４ RCU の基本のまとめ
この節は、RCU ベースのアルゴリズムの３つの基本的なコンポーネントを述べました。
１ 新しいデータを追加するためのパブリッシュ、サブスクライブ機構。
２ 既存の RCU リーダーが終わるのを待つ方法
３ 複数バージョンを維持して、同時実行する RCU リーダーを損なったり不要に待たせりしないで変更を許す規則
クイッククイズ９．２５：
rcu_read_lock() と rcu_read_unlock() プリミティブはスピンもブロックもしないのに、なぜ、RCU 更新者が RCU リーダーを遅延させることができるのですか？
これらの３つの RCU コンポーネントは、同時実行するリーダーがいても、データを更新することを許します。そして、驚くほどの種類の、異なる RCU ベースのアルゴリズムを実装するために、いろいろな方法で組み合わせることができます。以下の節で、そのアルゴリズムのいくつかを紹介します。
９．３．３ RCUの使いみち
この節では「RCUとは何か？」という質問に、RCUを使うことのできるところとは、という点から答えます。RCUは何か、既存の機構の代わりとして使われることが最も多いので、表９．３にしたがって、それらの機構との関係を主に見て行きましょう。最後に、９．３．３．８節はまとめです。 ９．３．３．１ RCUはリーダーライターロックの代わりです Linux カーネルで、RCUが最も一般的に使われているのは、リードがおもな状況での、リーダーライターロックの代わりです。しかし、このRCUの使い方は、最初は、私にはすぐに明らかではありませんでした。実際、私は、汎用のRCU実装をする前に、１９９０年代初頭、軽量リーダーライターロックを実装する方を選択したのです。
脚注
2.4 Linux カーネルの brlock そしてより新しいLinux カーネルの lglock に似ています。
私が軽量リーダーライターロックのために想定したそれぞれすべての用途は、その代わりに、RCUを使って実装されていきました。全く、軽量リーダーライターロックが最初の使用者を見つけたのは、それから実に３年以上後のことでした。やれやれ、私はばかでした。
RCUとリーダーライターロックの鍵となる類似点は、どちらも、リード側クリティカルセクションが同時実行できることです。実際、機械的に、RCU APIを、対応するリーダーライターロックAPIに置換できる場合もあります。しかし、ならどっちでもいいじゃないですか？
RCUの利点は、性能、デッドロックがないこと、そして、リアルタイムの遅延です。もちろん、RCUの限界もあります。例えば、リーダーと更新者が同時実行するために、低優先度のRCUリーダーが、グレースピリオドが終わるのを待っている高優先度のスレッドをブロックすることです。さらに、グレースピリオドの遅延は何ミリ秒にもなることがあります。これらの利点と限界は、以下の節で説明します。
性能
リード側性能について、リーダーライターロックと比べた時のRCUの利点を図９．２３に示します。
クイッククイズ９．２６：
何だって？３GHｚのクロック期間が３００ピコ秒なのに、RCUのオーバーヘッドが１００フェムト秒って、どうやって信じろというの？
リーダーライターロックは単一CPUで、RCUに比べて何オーダーも遅く、１６CPUでさらに、２オーダー遅いことに注意ください。これに比べて、RCUはとてもよくスケールします。両方とも、エラーバーは、両方向への単一標準偏差です。
CONFIG_PREEMPT カーネルの場合、差は小さくなります。しかし、図９．２４に示すように、RCUはリーダーライターロックを、なおも１から３オーダーの差で破ります。エラーバーは、両方向への単一標準偏差です。
もちろん、図９．２４のリーダーライターロックの低性能は、実際にはありえない長さゼロのクリティカルセクションのために誇張されています。図９．２５が１６CPUシステムについて示すように、クリティカルセクションのオーバーヘッドが増加すると、RCUの性能優位性は弱まります。ここで y 軸は、リード側のプリミティブとクリティカルセクションの和のオーバーヘッドを示します。
クイッククイズ９．２７：
クリティカルセクションのオーバーヘッドが増えるにつれてリーダーライターロックのばらつきとオーバーヘッドが減るのはなぜでしょう？
しかし、この結果は、多くのシステムコール（そしてそれらが含むすべてのRCUクリティカルセクション）は数マイクロ秒で終わるという事実を考慮すべきです。
さらに、次の節で述べるように、RCUリード側プリミティブはほとんど完全にデッドロックしません。
デッドロック安全性
RCU は、リードが主なワークロードにおいて、大きな性能優位性を示しますが、そもそもRCUを作った最初の主な理由は、リード側デッドロックが無いことでした。この安全性は、RCUのリード側プリミティブはブロック、スピンをせず、戻る方向の分岐さえしないという事実に基づきます。なので、その実行時間は決定論的です。このため、デッドロックサイクルに加わることは不可能です。 クイッククイズ９．２８：
このデッドロック安全性に例外はありますか。あるならば、どのようなイベントシーケンスがデッドロックを起こしますか。 RCUのリード側がデッドロック安全であることの面白い結果として、RCUリーダーを無条件にRCU更新者にアップグレードできることがあげられます。リーダーライターロックでそんなアップグレードをしようとすると、デッドロックになります。RCUリードを更新にアップグレードするサンプルコード断片は以下です。 do_update() は、ロックの保護とRCUリード側保護の両方のもとで実行されることに注意ください。 RCUがデッドロック安全であることのもうひとつの面白い結果として、RCUが多くのクラスの優先度逆転問題からも安全であることがあげられます。例えば、低優先度のRCUリーダーが高優先度のRCU更新者が更新側のロックを取るのを妨げることはありません。同様に、低優先度のRCU更新者が高優先度のRCUリーダーがRCUリード側クリティカルセクションに入るのを妨げることはありません。
クイッククイズ９．２９：
デッドロックと優先度逆転から安全？？？良い話すぎて本当とは思えません。そんなことが可能だとどうやって信じろと言うのですか？ リアルタイム遅延
RCUリード側プリミティブはスピンもブロックもしないため、リアルタイム遅延は素晴らしいものです。さらに、前に述べたように、これはRCUリード側プリミティブがRCUリード側プリミティブとロックに関わる優先度逆転から安全であることを意味します。
しかし、RCUがおちいるより微妙な優先度逆転シナリオもあります。例えば、RCUグレースピリオドが終わるのを待っている高優先度のプロセスが低優先度のRCUリーダーによってブロックされるということが、-rt （訳注。リアルタイムパッチセット）カーネルでは起きます。これは、RCU優先度ブーストを使えば解決します。 RCUリーダーと更新者は同時実行する
RCUリーダーはスピンもブロックもせず、更新者はいかなる種類のロールバックや中断セマンティクスにも従う必要がないため、RCUリーダーと更新者は必然的に同時実行します。この結果、RCUリーダーは古いデータをアクセスすることがあり、矛盾した状態を見ることもあるということです。このため、リーダーライターロックからRCUの変換は単純ではありません。
しかし、驚くほど多くの状況で、矛盾も古いデータも問題とはなりません。古典的な例は、ネットワークルーティングテーブルです。ルーティングの更新はあるシステムに届くまでにずいぶん時間が（何秒とか、ときには何分も）かかります。このため、システムは、更新が届くまで結構な時間、パケットを間違った方向に送っていることがあります。通常は、さらに何ミリ秒か、パケットを間違った方向に送り続けるのは、問題とはなりません。さらに、RCU更新はRCUリーダーが終わるのを待たないで更新をできるため、図９．２６が示すように、RCUリーダーは、まとめて公平なリーダーライターロックのリーダーに比べて、より早く更新を見ることができることがあります。
更新が届いたら、リーダーライターロックのライターは、最後のリーダーが終わるまで進むことはできません。そして、その後のリーダーは、ライターが終わるまで進むことはできません。しかし、これらの後のリーダーは右端の緑色の箱で示される新しい値を読むことが保証されます。それに比べて、RCUリーダーと更新者はお互いにブロックしませんから、RCUリーダーが更新後の値をより早く見ることが許されます。もちろん、それらの実行はRCU更新者と重なるため、すべてのRCUリーダーが更新後の値を見ることもありえます。それには、更新の前に開始した３つのリーダーも含みます。しかし、更新後の値を見ることが保証されているのは、右端の緑色の３つのRCUリーダーだけです。 リーダーライターロックとRCUは単純に、保証するものが違います。リーダーライターロックでは、ライターが開始した後に開始したすべてのリーダーは新しい値を見ることが保証されます。そして、ライターがスピンしているときに開始しようとするリーダーは新しい値を見ることも見ないこともあります。それは、そのリーダーライターロック実装のリーダーとライターの優先度合いで決まります。
これに対し、RCUでは更新者が完了した後に開始するすべてのリーダーは新しい値を見ることが保証され、更新者が開始した後に完了するリーダーが新しい値を見るかどうかは、タイミングによります。 ここで鍵となる点は、リーダーライターロックはたしかに計算機システムに閉じた世界での一貫性を保証しますが、ときには、この一貫性が、外の世界での一貫性を損なう可能性が高くなることにつながることです。つまり、リーダーライターロックは、外の世界における検知されない無効データという犠牲を払って内部的な一貫性を獲得しているのです。
訳注。例えば？RCUではそうならないの？ しかし、閉じた世界での矛盾や無効データが許されない状況もあります。幸い、矛盾と無効データを防ぐいくつかのアプローチがあります。参照カウンティングを基礎とする方法を、９．１節で説明します。 低優先度のRCUリーダーが高優先度の更新者をブロックすることがある
リアルタイムRCU（D.4節を参照）、SRCU（D.1節を参照）、QRCU（１２．６節を参照）、それぞれは、この連載の最後の回で説明します、では、プリエンプトされたリーダーが、高優先度のタスクがグレースピリオドが終わるのを待ってブロックしているにもかかわらず、そのグレースピリオドが終わるのを妨げることがあります。
リアルタイムRCUでは、この問題は、call_rcu() を synchronize_rcu() にするか、RCU優先度ブーストを使うことで避ける事ができます。後者は２００８年初めではまだ実験的です。SRCUとQRCUでも優先度ブーストが必要になるかもしれませんが、明らかな現実世界での要求がわかるまでは、それはないでしょう。
RCUグレースピリオドが何ミリ秒も続く
QRCUと、９．３．５節で述べる「おもちゃの」RCU実装のいくつかを除いては、RCUグレースピリオドが何ミリ秒も続くことがあります。そのような長い遅延を無害にする技術はいくつもあります。例えば、可能なら、非同期インタフェース (call_rcu() と call_rcu_bh())を使うなどです。しかし、これが、RCUがリードが主である状況で使われるのが良いことの主が原因です。 リーダーライターロックとRCUコードの比較
図９．２７，９．２８，９．２９が示すように、最もうまくいく場合、リーダーライターロックからRCUへの変換はとても単純です。これらの図はすべて、ウィキペディアから取られました。 リーダーライターロックをRCUに置換するより高度なケースは、この文書のスコープ外です。 ９．３．３．２ RCUは制限された参照カウンティング機構です グレースピリオドは、実行中のRCUリード側クリティカルセクションがあるうちは完了できないので、RCUリード側プリミティブは制限された参照カウンティング機構として使うこともできます。例えば、以下のコード断片を見ましょう。 rcu_read_lock() プリミティブは、p への参照を確保していると考えることができます。なぜならば、rcu_dereference() が p を設定した後に開始するグレースピリオドは、対応するrcu_read_unlock() が動くまで、たぶん、完了することができません。この参照カウンティングスキーマは、制限されたものです。RCUリード側クリティカルセクションでブロックすることはできませんし、RCUリード側クリティカルセクションをあるタスクから別のタスクに渡すことは許されないからです。 これらの制限にもかかわらず、以下のコードは安全に p を削除できます。 head への代入は、それ以降、p への参照が確保されるのを止めます。synchronize_rcu() は以前に確保されたすべての参照が解放されるのを待ちます。
クイッククイズ９．３０：
しかし待って！このコードは、RCUをリーダーライターロックの代わりとして考えた時に使ったのと全く同じでないですか！どういうこと？
もちろん、RCUを伝統的な参照カウンティングと組み合わせることもできます。それは、LKML で議論され、９．１節でまとめられています。 しかし、なぜ、こだわるのでしょう？再び、答えのひとつは、性能です。図９．３０に、16-CPU 3GHz Intel x86 システムで取ったデータを示します。 クイッククイズ９．３１：
６CPUあたりで、参照カウンティングオーバーヘッドが下がるのはなぜですか？ リーダーライターロッキングのときと同じように、RCUはクリティカルセクションが短い時に最も性能が優位となります。これは、１６CPUシステムのとき、図９．３１で示されます。また、リーダーライターロッキングのときと同じく、多くのシステムコール（そして、それが含むRCUリード側クリティカルセクション）は数マイクロ秒で完了します。 しかし、RCUの制限は、とても面倒なときもあります。例えば、多くの場合、RCUリード側クリティカルセクションでスリープできないという制限は、そもそもの目的に合わないことがあります。次の節は、この問題への対処を考え、ある状況では伝統的な参照カウンティングの複雑さを軽減する方法を述べます。
９．３．３．３ RCUは、バルク参照カウンティング機構です
前の節で述べたように、伝統的参照カウンタは、通常、特定のデータ構造あるいは特定のデータ構造のグループに関連づいています。しかし、多様なデータ構造に対して１つだけのグローバル参照カウンタを維持するのは、普通は、その参照カウンタを持つキャッシュラインの競合につながります。そのようなキャッシュライン競合は、性能を著しく落とします。 これに比べて、RCUのリード側プリミティブは軽量なので、リード側でとても頻繁に使用してもほとんど性能低下は起きません。これにより、RCUを、性能損失が低いかあるいは全くない「バルク参照カウンティング」機構として使うことができます。参照が、ブロックするコードセクションに渡って、単一タスクにより保持されなくてはいけない状況は、スリープ可能RCU（SRCU)で対処できます。ただし、これは、参照があるタスクから他に、「渡される」という時々ある状況をカバーすることはできません。例えば、I/Oを開始した時に参照を確保して、対応する割り込みハンドラで解放されるというような。（原理的には、これもSRCU実装で処理可能ですが、現実的にはそれが正しいトレードオフかは不明です。） もちろん、SRCUにも固有の制限があります。つまり、srcu_read_lock() の戻り値を、対応する srcu_read_unlock() に渡さなければいけないことです。さらに、ハードウェア割り込みハンドラとマスク不可能割り込み（NMI)ハンドラからはSRCUプリミティブを呼べないことです。これらの制限によりどんな問題が起きるか、そしてどう解決できるかは、まだ不明です。
９．３．３．４ RCUは貧しい人のガーベッジコレクタです
RCUを最初に学んだ人のよくある驚きは、「RCUはガーベッジコレクタみたいだ！」というものです。この意見は、多くの真実も含みますが、人を誤らせるものでもあります。 RCUと自動ガーベッジコレクタ（GC)との関係を考える最も良い方法は、RCUは、回収のタイミングが自動的に決まる点でGCに似ているというものでしょう。しかし、RCUがGCと違うのは、（１）プログラマーは、あるデータ構造が回収可能になった時にあらわに指示する必要があること。そして、（２）プログラマーは、参照が保持されている必要のある期間を示すためにあらわにRCUリード側クリティカルセクションを宣言する必要が有ることです。 これらの違いはありますが、類似はとても深いものを持っており、少なくても１つのRCU理論的解析においてそれが明らかにされたことがあります。また、私が知っている最初のRCU的な機構はグレースピリオドを処理するのにガーベッジコレクタを使っていました。とはいえ、RCUを考えるより良い方法を、次の節で紹介します。
９．３．５．５ RCUは存在保証を提供する方法です
Gamsa 達は、存在保証について議論し、RCUに似た機構を使って存在保証を提供できることを示しました。（PDF の７ページ、５節を参照。）また、７．４節ではロックを使って存在を保証するやり方と、そうするときの欠点について述べました。存在保証とは、RCUで保護されるデータ要素がRCUリード側クリティカルセクション内でアクセスされるとき、そのデータ要素は、そのRCUリード側クリティカルセクションが続く間、存在が保証されるというものです。
図９．３２はハッシュテーブルから要素を削除する関数で、RCUベースの存在保証が、要素ごとのロックを可能とする方法を示します。６行目はハッシュ関数を計算し、７行目でRCUリード側クリティカルセクションに入ります。９行目で、ハッシュテーブルの対応するバケツが空であるかあるいはそこにある要素が削除したいものではないとき、１０行目でRCUリード側クリティカルセクションを抜け、１１行目で失敗を返します。
クイッククイズ９．３２：
図９．３２の９行目で、削除したい要素がリストの最初の要素でない時はどうしますか？
そうでないとき、１３行目で更新側のスピンロックを取り、１４行目でその要素が今でも求めるものか確認します。そうならば１５行目でRCUリード側クリティカルセクションを抜け、１６行目でテーブルからそれを削除します。１７行目でロックを放し、１８行目ですべての既存のRCUリード側クリティカルセクションが完了するまで待ちます。１９行目で今削除した要素を解放し、２０行目で成功を返します。要素が、目的のものではなかった場合、２２行目でロックを放し、２３行目でRCUリード側クリティカルセクションを抜け、２４行目で指定されたキーを削除できなかったことを返します。
クイッククイズ９．３３：
図９．３２の１５行目で、１７行目でロックを放すより先にRCUリード側クリティカルセクションを抜けても良いのはなぜですか？
クイッククイズ９．３４：
図９．３２の２３行目で、２２行目でロックを放すより先にRCUリード側クリティカルセクションを抜けてはいけませんか？
注意深い読者は、これが、９．３．３．７節で述べた、元の、「RCUは、何かが終わるのを待つ方法です」主題のわずかなバリエーションにすぎないことに気が付かれるでしょう。
また、７．４節で述べたロックベースの存在保証に比べて、これがデッドロック安全性という利点を持つこともおわかりでしょう。
９．３．３．６ RCUは型安全なメモリを提供する方法です
ロックレスアルゴリズムのいくつかは、あるRCUリード側クリティカルセクションがあるデータ要素を参照している間ずっと、そのデータ要素が同じアイデンティティを保つことを要求しません。しかし、そのデータ要素が同じ型を保つことを要求します。つまり、これらのロックレスアルゴリズムは、参照されているデータ要素が、解放され、同じ型の構造体として再確保されることに耐えることができます。しかし、型の変更は禁止します。この保証は、学術論文では「型安全メモリ」と呼ばれ、以前の節で述べた存在保証より弱いものです。このため、扱うのが少し難しいです。
Linux カーネルの型安全メモリアルゴリズムは、スラブキャッシュを使います。キャッシュに、SLAB_DESTROY_BY_RCU で印をつけて、解放されたスラブをシステムメモリに返すときにRCUが使われるようにします。RCUをこのように使うことで、そのスラブ内のすべての使用中要素が、既存のすべてのRCUリード側クリティカルセクションが続く間、そのスラブにとどまり、その型を保持することが保証されます。
クイッククイズ９．３５：
複数スレッドで、任意の長さのRCUリード側クリティカルセクションがあって、いかなる時間の一点においても、システムで少なくても１つのスレッドがRCUリード側クリティカルセクションを実行中だとしたら、どうなりますか？
そうなると、SLAB_DESTROY_BY_RCU スラブのデータが全くシステムに返されることがなく、OOM（メモリ不足）イベントを生ずるのでありませんか。 これらのアルゴリズムは典型的には、新しく参照したデータ構造が本当に要求されたものであるかを確認する検証段階を使います。これら検証は、データ構造の一部が、解放と再確保処理においても変更されないことを要求します。そういう検証は通常は正しく行うのがとても難しく、微妙で難しいバグを隠すことが多いです。 このため、型安全ベースのロックレスアルゴリズムは、ごく限られた難しい状況ではとても役に立ちますが、その代わりにあなたは可能ならば存在保証を使うのをおすすめします。単純さは、結局、ほとんど常により優れているのです！
９．３．３．７ RCUは、何かが終わるのを待つ方法です
９．３．２節で述べたように、RCUの重要な要素に、RCUリーダーが終わるのを待つ方法があります。RCUの大きな長所は、何千もの異なるものごとが終わるのを待つときに、それぞれのすべてを１つづつ明示的に追跡しないでもいいことです。さらに、明示的な追跡をするスキーマにつきものの、性能低下、スケーラビリティの限界、複雑なデッドロックシナリオ、そしてメモリリークの危険について心配する必要もありません。
この節では、 synchronize_sched() のリード側の対と競合する方の（プリエンプションを禁止するもの何でも、それに割り込みを禁止するハードウエア操作とプリミティブ）ものを使って、マスク不可能割り込み（NMI）ハンドラーとの相互作用を実装できることを示します。それは、ロックを使ってはとても難しいのです。このアプローチは、「ピュア RCU」と呼ばれており、 Linux カーネルのいくつかのところで使われています。
その「ピュア RCU」の基本的設計は以下のとおりです。
１ 変更をする。例えば、OSがNMIに反応する方法を変更する。
２ すべての既存のリード側クリティカルセクションが完全に終わるまで待つ。（例えば、synchronize_sched() プリミティブを使う。）
３ 後始末。例えば、変更が正しく行われたかを示すステータスを返す。
この節の残りでは、 Linux カーネルから取られたコードの例を紹介します。この例で、timer_stop 関数は、synchronize_sched() を使って、すべての実行中のNMI通知が完了してから関連するリソースを解放します。このコードの簡略版を図９．３３に示します。
１から４行目は profile_buffer 構造を定義します。これはサイズと、不定長のエントリの配列を持ちます。５行目はプロファイルバッファへのポインタです。たぶん、ダイナミックに確保されたメモリ領域を指すようにどこかで初期化されています。７から１６行目はnmi_profile() 関数で、NMIハンドラから呼ばれます。そのため、これはプリエンプトされず、通常の割り込みハンドラによって割り込まれることもありません。しかし、キャッシュミス、ECCエラー、同じコアの他のハードウェアスレッドによるサイクルスチーリングによって、遅延することもあります。９行目で、DEC Alpha でのメモリオーダリングを保証するために rcu_dereference() プリミティブを使ってプロファイルバッファへのローカルなポインタを得ます。１１と１２行目で現在確保されているプロファイルバッファがなければ、関数を終わり、１３と１４行目では pcvalue が範囲外なら関数を終わります。そうでない時は、１５行目で pcvalue 引数でインデックスされるプロファイルバッファエントリを加算します。サイズをバッファと一緒に格納しているため、大きなバッファが突然小さいものに変わっても、範囲チェックはバッファにマッチしていることが保証されるのに注意ください。
１８から２７行目は nmi_stop() 関数を定義します。コール元が、排他制御に責任を持ちます。（例えば、正しいロックを持つことで）２０行目でプロファイルバッファのポインタをフェッチし、バッファがなければ、２２と２３行目で関数を終わります。そうでなければ、２４行目でプロファイルバッファポインタを NULL にします。
（弱いメモリオーダリングのマシンでメモリオーダリングを維持するために rcu_assign_pointer() プリミティブを使います。）２５行目はRCU Sched （訳注。後述。９．３．４．１節）グレースピリオドが過ぎるのを待ちます。特に、NMIハンドラを含むすべてのノンプリエンプティブなコード領域が完了するのを待ちます。２６行目で実行が再開したとき、古いバッファへのポインタを持っている nmi_profile() のすべてのインスタンスは終了していることが保証されています。なので、今の場合 kfree() プリミティブを使ってバッファを解放しても安全です。
クイッククイズ９．３６：
nmi_profile() 関数がプリエンプティブだったとしたら、この例が正しく動くためには何を変える必要があるでしょう？
要するに、RCUを使えばプロファイルバッファをダイナミックに切り替えるのを簡単にできます。（なんなら、これをアトミック操作や、ロックだけで効率的にできるかやってみるとよいです。）しかし、普通は、以前の節で述べたように、RCUはより高い抽象レベルで使われます。
９．３．３．８ RCU使用法のまとめ
中核においてRCUは以下を提供するAPI 以上でも以下でもありません。
１ 新しいデータを追加するためのパブリッシュ、サブスクライブ機構
２ 既存のRCUリーダーが終わるのを待つ方法
３ 複数のバージョンを維持することによって、並列実行するRCUリーダーを損なったり必要以上に遅延させたりすることなく、変更を許す方法。
ということは、RCUの上に、リーダーライターロック、参照カウンティング、存在保証される要素など、以前の節で述べた高レベルの構造を作ることも可能です。さらに、Linux コミュニティは、RCU や他の多くの同期プリミティブの、新しく面白い用途をこれからも見つけてくれるだろうと信じます。
ところで、図９．３４に、RCUがどういうときに最も有効であるか、おおまかな規則を示します。
図の一番上の青い箱で示されるように、RCUはリードがほとんどであるデータで、古くて矛盾したデータが許されるときに、最もうまく働きます。（なお、古くて矛盾したデータについて、後でもう少し詳しく述べます。）このケースの Linux カーネルでの正統的な例は、ルーティングテーブルです。ルーティングの更新がインターネットで伝搬するには何秒も、時には何分もかかることがありますから、システムはパケットを間違った方向にずいぶん長いこと送ってきたかもしれません。これをさらにあと数ミリ秒、間違った方向に送り続ける可能性がわずかにあることはほとんど問題にはなりません。 リードがほとんどのワークロードで、一貫したデータが必要な場合、緑色の、「リードがほとんど、一貫したデータが必要」の箱で示すように、RCUはうまく働きます。このケースの１つの例は、Linux カーネルの、ユーザーレベルシステムVセマフォーIDから対応するカーネルデータ構造へのマッピングです。セマフォーは作成と削除に比べてずっと、頻繁に使われます。なので、このマッピングはリードがほとんどです。しかし、既に削除されたセマフォーにセマフォー操作をするのは誤りです。
この、一貫性の必要性は、カーネル内のセマフォーデータ構造にロックを使い、さらに、セマフォーを削除する時に「削除済み」フラグをつけることで対処されます。もしも、ユーザーのIDが、「削除済み」フラグがついているカーネル内データ構造にマップするならば、そのデータ構造は無視され、ユーザーのIDは無効とされます。 この場合、リーダーは、セマフォー自身を表すデータ構造のロックを取る必要がありますが、マッピングのためのデータ構造のロックは不要です。このため、リーダーはIDをデータ構造にマップするツリーをロック無しでトラバースできます。その結果、性能、スケーラビリティ、リアルタイム応答が大いに改善します。 黄色の、「読み書き」の箱で示されるように、RCUを読み書きのワークロードで一貫性が必要なところで使うこともできます。ただし、この場合、普通は、いくつかの他の同期プリミティブと一緒に使われます。例えば、最近の Linux カーネルのディレクトリエントリーキャッシュは、RCUとともに、シーケンスロック、CPUごとのロック、データ構造ごとのロックを使って、一般的なケースでパス名トラバーサルをロック無しで行えます。 この読み書きのケースでRCUはとても便利ですが、ほとんどがリードのケースと比べると、多くの場合、ずっと複雑な使い方となります。 最後に、図の一番下の赤い箱で示されるところ、更新が主なワークロードでデータの一貫性が必要な場合は、RCUを使うのにほぼ、良い所とは言えません。ただ例外はあります。なお、９．３．３．６節で述べたように、 Linux カーネルにおいて、SLAB_DESTROY_BY_RCU スラブアロケータフラグは、RCUリーダーに型安全なメモリを提供します。それは、ブロックしない同期と他のロックレスアルゴリズムを大いに簡略化することができます。
ようするに、RCUは、新しいデータを追加するためのパブリッシュ、サブスクライブ機構を含むAPIであり、既存のRCUリーダーが終わるのを待つ方法であり、複数のバージョンを維持することで、更新が同時実行するRCUリーダーを害したり不要に遅らせたりすることのないようにする規範です。このRCU API はリードがほとんどの状況、特に、古い矛盾したデータがアプリケーションにより許容される場合に、最も適します。
９．３．４ RCU Linux カーネル API
この節では、Linux カーネル API の観点から、RCU を見ます。９．３．４．１節は、RCU の終わるのを待つAPIを紹介し、９．３．４．２節はパブリッシュ、サブスクライブとバージョン維持のAPIを紹介します。最後に、９．３．４．４節はまとめです。
９．３．４．１ RCU には、終わるのを待つAPIのファミリーがあります
「RCU とは何ですか」という問いの最も簡単な答えは、RCUは Linux カーネルで使われるAPIで、表９．４と９．５，そして表９．６でまとめられるもの、です。前者はRCUリーダーを待つ機能の方の、スリープ不可能なものと可能なもののAPIで、後者はパブリッシュ、サブスクライブの方のAPIです。
もしあなたがRCUが初めてなら、９．４の表のカラムの１つだけをじっと見るのが良いです。カラムのそれぞれは、Linux カーネルのRCU API ファミリーの１つのメンバーをまとめたものです。例えば、もしあなたが、RCUがLinux カーネルでどのように使われているかを主に理解したいならば、「RCU クラシック」が始めるに適した場所です。それは最も頻繁に使われていますから。逆に、あなたが、RCU自身のことを理解したいならば、「SRCU」が最も単純なAPIを持ちます。他のカラムは、後からいつでも調べることができます。
もしあなたがRCUをよく知っているなら、この表は良いレファレンスとなるでしょう。
クイッククイズ９．３７：
表９．４のセルで、感嘆符（！）がついたものがあるのはなぜですか？
「RCU Classic」カラムは、オリジナルの RCU 実装に対応します。それでは、RCUリード側クリティカルセクションは、rcu_read_lock() と rcu_read_unlock() で区切られます。ネストしてもよいです。対応する同期更新プリミティブである synchronize_rcu() とそのシノニム synchronize_net() は、すべての現在実行しているRCUリード側クリティカルセクションが完了するのを待ちます。この待ち時間を「グレースピリオド」と呼びます。非同期の更新プリミティブである call_rcu() は、以後のグレースピリオドの後で、指定された関数を指定された引数で呼びます。例えば、call_rcu(p,f); とすると、以後のグレースピリオドの後で、「RCUコールバック」f(p) が呼ばれることになります。call_rcu() を使う Linux カーネルモジュールをアンロードするときのように、すべての実行待ちをしているRCUコールバックが終わるのを待つ必要がある状況があります。なお、D.2 と D.3 節で説明する、これより新しい、階層RCU実装も、「RCU Classic」セマンティクスに従います。
最後に、９．３．３．６節で述べたように、RCUは型安全なメモリを提供するために使うことができます。RCUの文脈では、型安全なメモリは、それをアクセスするRCUリード側クリティカルセクションがいずれかあるうちは決して、あるデータ要素がその型を変えないことを保証します。RCUベースの型安全なメモリを使うには、kmem_cache_create() に、SLAB_DESTROY_BY_RCU を与えます。注意してほしいですが、 SLAB_DESTROY_BY_RCU をつけても、kmem_cache_alloc() が、たった今 kmem_cache_free() で解放したメモリを再確保するのをやめさせることはできません！実際、rcu_dereference で返却された、SLAB_DESTROY_BY_RCU で保護されたデータ構造は、rcu_read_lock() の保護のもとであっても、任意の回数、解放と再確保がされることがあります。そうでなくて、SLAB_DESTROY_BY_RCU は、kmem_cache_free() が、完全に解放されたデータ構造のスラブをシステムに返すのを、RCUグレースピリオドが終わるまで留めることで働きます。ようするに、データ要素は任意の頻度で解放と再確保されますが、少なくてもその型は同じままです。
クイッククイズ９．３８：
とてもたくさんのRCUリード側クリティカルセクションが、synchronize_rcu() 実行を無限に遅らせるのを防ぐにはどうしたらいいですか？
クイッククイズ９．３９：
synchronize_rcu() API は、すべての既存の割り込みハンドラが完了するのは待つのですよね？
「RCU BH」カラムでは、rcu_read_lock_bh() と rcu_read_unlock_bh() が、RCUリード側クリティカルセクションを区切ります。そして、call_rcu_bh() が、 以後のグレースピリオドの後で、指定された関数を指定された引数で呼びます。なお、RCU BH は、同期の synchronize_rcu_bh() インタフェースを持たないことに注意下さい。お望みなら、簡単に追加できますが。
クイッククイズ９．４０：
混ぜるとどうなりますか？例えば、rcu_read_lock() と rcu_read_unlock() を、RCUリード側クリティカルセクションを区切るのに使って、しかし、call_rcu_bh() を使ってRCUコールバックをポストするとします。
クイッククイズ９．４０：
ハードウェア割り込みハンドラは、暗黙的な rcu_read_lock_bh() で守られていると考えてよいですよね？
「RCU Sched」カラムでは、プリエンプションを妨げるものはすべて、RCUリード側クリティカルセクションとして働きます。そして、synchronize_sched() は、対応するRCUグレースピリオドを待ちます。２．６．１２カーネルでRCU API ファミリーが追加され、古い synchronize_kernel() API は、現在の synchronize_rcu() （RCU Classic 用) と synchronize_sched() (RCU Sched 用) に別れました。なお、RCU Sched は、元は、非同期の call_rcu_sched() インタフェースを持ちませんでしたが、２．６．２６でそれが追加されました。Linux コミュニティーの、小さいことは良いことだという哲学に従って、API は必要に応じて追加されるのです。
クイッククイズ９．４２：
RCU Classic と、RCU Sched を混ぜて使うとどうなりますか？
クイッククイズ９．４３：
一般的には、synchronize_sched() によって、既存のすべての割り込みハンドラを待つことはできないですよね？
「Realtime RCU」カラムは、RCU Classic と同じ API を持ちます。違いは、RCUリード側クリティカルセクションはプリエンプトされる可能性があることと、スピンロックを持ってブロックしても良いことだけです。Realtime RCU の設計は、他で書いてあります。
クイッククイズ９．４４：
SRCU と、 QRCU に、非同期の call_srcu() あるいは call_qrcu() インタフェースが無いのはどうしてですか？
表９．５の「SRCU」カラムは、RCUリード側クリティカルセクションで一般的なスリープを許す特別の RCU API です。（詳しくは、付録D.1 を参照ください。）もちろん、SRCU リード側クリティカルセクション内で synchronize_srcu() を使うと自己デッドロックになるので、避けなければいけません。SRCU は、コール元が、SRCU を使う時にそれぞれ、srcu_struct を確保するという点で、以前の RCU 実装とは異なります。このアプローチは、SRCU リード側クリティカルセクションが、関係ない synchronize_srcu() 呼び出しをブロックしないようにします。さらに、この RCU の変種では、srcu_read_lock() は値を返し、それを対応する srcu_read_unlock() に渡す必要があります。
「QRCU」カラムは、SRCU と同じ API 構造を持ちますが、リーダーのいないときに、極めて低遅延のグレースピリオドになるように最適化された RCU 実装です。詳しくは、他で書いてあります。SRCU と同じく、QRCU リード側クリティカルセクション内で synchronize_qrcu() を使うと自己デッドロックになるので、避けなければいけません。QRCU は、まだ Linux カーネルに受け入れられていませんが、カーネルレベル RCU 実装で、はるかにマイクロ秒以下のグレースピリオド遅延を誇るものはこれだけなので、注目に値します。
クイッククイズ９．４５：
SRCU リード側クリティカルセクション内で synchronize_srcu() を安全に使うことのできる条件はなんですか？
Linux カーネルは現在、驚くほど多くの RCU API と実装を持ちます。この数を減らせないかという希望もあります。ある Linux ビルドでは、４つの API の背後に、最大でも３つの実装（RCU Classic と Realtime RCU は、同じAPI です。）を持つことが出来るだけであるという事実からもそれは言えます。しかし、注意深い調査と解析が必要です。それは、多くのロックAPI の一つを削除するのに必要な注意と同じでしょう。
いろいろな RCU API は、それらの RCUリード側クリティカルセクションが提供しなければいけない、前方進行（訳注。forward progress）保証と、それぞれのスコープによって、以下のように区別されます。
１ RCU BH:リード側クリティカルセクションは、NMI と割り込みハンドラ以外の全てに対して、前方進行を保証しなくてはいけません。ソフトウェア割り込み (softirq) ハンドラは除きます。RCU BH のスコープはグローバルです。
２ RCU Sched: リード側クリティカルセクションは、NMI と割り込みハンドラ以外の全てに対して、前方進行を保証しなくてはいけません。softirq ハンドラも含みます。RCU Sched のスコープはグローバルです。
３ RCU (classic と real-time):リード側クリティカルセクションは、NMI、割り込みハンドラ、softirq ハンドラ、そして（リアルタイムの場合）より高い優先度のリアルタイムタスク以外の全てに対して、前方進行を保証しなくてはいけません。softirq ハンドラも含みます。RCU のスコープはグローバルです。
４ SRCU と QRCU:リード側クリティカルセクションは、どれか他のタスクが対応するグレースピリオドが完了するのを待っている場合を除いて、前方進行を保証する必要がありません。その場合、そのリード側クリティカルセクションは数秒以内に完了するべきです（できれば、もっと早く）。
脚注
単純に、前方進行保証は無いと言う代わりに、私にこの形式化をするように促した James Bottomley に感謝します。
SRCU と QRCU のスコープはそれぞれ、対応する srcu_struct あるいは qrcu_struct の使用で決まります。
つまり、SRCU と QRCU は、極端に弱い前方進行保証を、開発者がそのスコープを制限できるようにすることで補っていると言えます。
９．３．４．２ RCU には、パブリッシュ、サブスクライブとバージョン維持のAPIがあります
幸い、以下の表で示す、RCU パブリッシュ、サブスクライブとバージョン維持のプリミティブは、これまで述べたすべての RCU の変種で使えます。この共通性のために、場合によってはより多くのコードを共用でき、そうでなかったときに起きるであろう API の増殖を抑えることがたしかにできていると思われます。RCU パブリッシュ、サブスクライブAPI の本来の用途は、メモリバリアをこれら API の中に埋め込んで、Linux カーネルプログラマーが、Linux がサポートする２０以上のCPUファミリーそれぞれのメモリオーダリングモデルのエキスパートでなくても、RCU が使えるようにすることでした。
カテゴリーの最初の対は、Linux struct list_head リストに作用します。それは、２重連結の循環リストです。
list_for_each_entry_rcu() プリミティブは、RCU 保護されたリストを型安全な方法でトラバースします。そのとき、トラバーサルと同時に新しいリスト要素がそのリストに挿入される場合のために、メモリオーダリングも強制します。
Alpha 以外のプラットフォームでは、このプリミティブは list_for_each_entry() に比べて性能低下はわずかあるいは全くありません。list_add_rcu(), list_add_tail_rcu(), そして list_replace_rcu() プリミティブは、それらの RCU でないものと似てますが、弱いオーダリングのマシンでは追加のメモリバリアのオーバーヘッドがあります。list_del_rcu() プリミティブもRCU でないものと似てますが、おかしなことに少し速いです。それは、list_del() が prev と next ポインタの両方をポイズン（訳注。無効値を入れる。）する必要があるのに比べて、 prev ポインタだけをポイズンするためです。最後に、list_splice_init_rcu() プリミティブはその RCU でないものに似てますが、完全なグレースピリオド遅延を引き起こします。このグレースピリオドの目的は、元のリストを完全にリストヘッダから切り離す前に、それをたどっているRCUリーダーが終わるのを待つことです。そうしないと、リーダーはトラバーサルを終わることができなくなることがあります。
クイッククイズ９．４６：
なぜ、list_del_rcu() は prev と next ポインタの両方をポイズンしないのですか？
カテゴリーの２つめの対は、Linux struct hlist_head リストに作用します。それは、線形の連結リストです。struct hlist_head が struct list_head より良いことの一つは、前者はリストヘッダに１つのポインタしか必要としないため、大きなハッシュテーブルで大いにメモリを節約できることです。表の struct hlist_head プリミティブは、struct list_head プリミティブと同様に、それらのRCU でないものに関連しています。
カテゴリーの最後の対は、直接ポインタに作用します。それはRCU 保護された配列や木構造など、RCU 保護されたリストでないデータ構造を作成するのに使います。rcu_assign_pointer() プリミティブは、弱いオーダリングのマシンで、すべての以前の初期化がそのポインタへの代入の前に並ぶのを保証します。同様に、rcu_dereference() プリミティブは、Alpha CPU で、ポインタをデレファレンスする以降のコードが、対応する rcu_assign_pointer() の前の初期化コードの結果を見ることを保証します。Alpha 以外の CPU では、rcu_dereference() は、RCU 保護されるポインタデレファレンスを文書化するだけです。
クイッククイズ９．４７：
通常は、rcu_dereference() が使われるポインタはすべて、常に rcu_assign_pointer() を使って更新しなくてはいけません。この規則の例外は何でしょう？
クイッククイズ９．４８：
これらのトラバーサルと更新プリミティブが、RCU API ファミリーメンバーのどれとでも一緒に使うことができることの欠点はありますか？
９．３．４．３ RCUのAPIはどこで使うことができますか？
図９．３５は、どのAPIがどのカーネル内環境で使えるかを示します。RCUリード側プリミティブは、NMI を含むすべての環境で使えます。RCU 置換と非同期のグレースピリオドプリミティブは、NMI 以外のすべての環境で使えます。そして最後に、RCU 同期のグレースピリオドプリミティブはプロセスコンテキストでだけ使えます。RCU リストトラバーサルプリミティブには、list_for_each_entry_rcu(), hlist_for_each_entry_rcu() などが含まれます。同様に、RCU リスト置換プリミティブには、list_add_rcu(), hlist_del_rcu() などが含まれます。
なお、RCU の他のファミリーのプリミティブも読み替えることができます。例えば、srcu_read_lock() は、rcu_read_lock() が使えるコンテキストならどこでも使えます。
９．３．４．４ 結局、RCU とは何ですか？
中核においてRCUは、挿入におけるパブリッシュとサブスクライブ、既存のRCUリーダーが終わるのを待つこと、そして複数のバージョンを維持すること、をサポートするAPI 以上でも以下でもありません。ということは、RCUの上に、リーダーライターロック、参照カウンティング、存在保証される構造など、別の記事で述べた高レベルの構造を作ることも可能です。さらに、Linux コミュニティは、カーネル内の他の多くの同期プリミティブと同様に、RCUの、新しく面白い用途をこれからも見つけてくれるだろうと信じます。
訳注
H.4 初出に示すように、この節は、Linux Weekly News の連載記事として発表されたものです。別の記事とは、そのことです。９．３．３．８と重複する記述があります。
もちろん、RCU のより完全な観点には、あなたがこれらの API でできるすべての事が含まれるでしょう。
しかし、多くの人々にとって、RCU の完全な観点には、RCU のサンプル実装が必要です。なので次の節では、「おもちゃの」RCU 実装のシリーズを紹介します。複雑さと能力が増していくように並んでいます。
９．３．５ 「おもちゃの」RCU実装
この節で説明するおもちゃのRCU実装は、高性能、実用性、本番での使用のために設計されたものではありません。そうでなくて、説明のためです。とはいえ、このおもちゃのRCU実装をたやすく理解するには、２，３，４，６と９章を完全に理解してないとだめです。
この節では、存在保証の問題を解決するという観点から、いくつかのRCU実装を紹介します。順に、より洗練されたものを紹介します。
９．３．５．１節は、単純なロックに基づく原始的なRCU実装を紹介します。９．３．５．３から９．３．５．９節は、ロック、参照カウンタ、そしてフリーランニングカウンタに基づく単純なRCU実装を紹介します。最後に、９．３．５．１０節はまとめで、望ましいRCUの属性をリストします。
９．３．５．１ ロックベースのRCU
たぶん、最も簡単なRCUの実装は、図９．３６(rcu_lock.h と rcu_lock.c) に示すように、ロックを使います。この実装では、rcu_read_lock() はグローバルなスピンロックを取り、rcu_read_unlock() はそれを放し、synchronize_rcu() はそれを取って、すぐ放します。
synchronize_rcu() はロックを取る（そして放す）まで戻りません。それはすべての以前のRCUリード側クリティカルセクションが完了するまで戻ることはできません。こうして、RCUセマンティクスを忠実に実装しています。もちろん、一度には１つのRCUリーダーしか、リード側クリティカルセクションにいることはできませんから、RCUの目的をほとんど完全に無視しています。さらに、rcu_read_lock() と rcu_read_unlock() のロック操作はとても重いです。リード側のオーバーヘッドは単一のPower5 CPU で約１００ナノ秒、６４CPUシステムで１７マイクロ秒以上です。さらに悪いことに、これらの同じロック操作は、rcu_read_lock() がデッドロックサイクルに入ることを許します。さらにさらに、再帰ロックが許されない時は、RCUリード側クリティカルセクションはネストできません。そして最後に、同時実行するRCU更新は、原理的には、同じグレースピリオドの間それぞれが待てばよいのですが、この実装はグレースピリオドをシリアライズするので、グレースピリオドを共有することができません。
クイッククイズ９．４９：
図９．３６のRCU実装で起きる可能性のあるデッドロックが、他のRCU実装では起きないのはなぜですか？
クイッククイズ９．５０：
図９．３６のRCU実装で、単純にリーダーライターロックを使えば、RCUリーダーは同時に動けるのでないですか？
この実装が本番環境で役に立つとはとても思えませんが、これはほとんど任意のユーザーレベルアプリケーションで実装可能であるという利点があります。また、これと似た、CPUごとにロックを持つ実装や、リーダーライターロックを使う実装が、２．４ Linux カーネルの本番で使われたことがあります。
次の節では、この、１つのCPUに１つのロックというアプローチを変えたバージョンで、スレッドに１つのロックを使う実装を紹介します。
９．３．５．２ スレッドごとのロックをベースにするRCU
図９．３７(rcu_lock_percpu.h と rcu_lock_percpu.c)は、スレッドごとのロックをベースにする実装です。
rcu_read_lock() と rcu_read_unlock() 関数は、それぞれ、現在スレッドのロックをとり、放します。synchronize_rcu() 関数は、すべてのスレッドのロックを順に取り、放します。このため、synchronize_rcu() が始まった時に実行中のすべての RCUリード側クリティカルセクションは、synchronize_rcu() が戻る時には終わっているはずです。
この実装は、たしかに、同時実行するRCUリーダーを許す利点がありますし、単一のグローバルロックの時に起きる可能性のあったデッドロック条件を避けることができます。さらに、リード側オーバーヘッドは、約１４０ナノ秒と高いのですが、CPUの数によらず約１４０ナノ秒のままです、しかし、更新側のオーバーヘッドは、単一のPower5 CPU で約６００ナノ秒、６４CPUシステムで１００マイクロ秒以上です。
クイッククイズ９．５１：
図９．３７の１５から１８行目のループで、最初に全部のロックを取って、それから全部を放すほうがきれいでないですか？この変更の結果、リーダーが全くいない時刻ができるから、いろんなことがずっと簡単になるでしょう。
クイッククイズ９．５２：
図９．３７の実装はデッドロックがありますか？なぜですか？
クイッククイズ９．５３：
図９．３７のRCUアルゴリズムの１つの利点は、広く利用可能なプリミティブ、例えば POSIX pthread においても可能なもの、だけを使っていることでないですか？
このアプローチはある状況ではわりと使えます。似たアプローチが、 Linux ２．４カーネルで使われました。
次に説明するカウンタベースのRCU実装は、ロックベースの実装のいくつかの欠点を克服します。
９．３．５．３ 単純なカウンタベースのRCU
図９，３８(rcu_rcg.h と rcu_rcg.c)は、少し洗練されたRCU実装です。この実装は、１行目で定義したグローバル参照カウンタ rcu_refcnt を使います。rcu_read_lock() プリミティブはこのカウンタをアトミックに加算し、メモリバリアを実行して、RCUリード側クリティカルセクションがアトミック加算の後に並ぶのを保証します。同じように、rcu_read_unlock() は、メモリバリアを実行してRCUリード側クリティカルセクションを閉じ込めて、アトミックにカウンタを減算します。
訳注。このメモリバリアの説明、以下の他の実装例にも出てくるけど、くどいので、適当に訳を省略します。
synchronize_rcu() プリミティブは、参照カウンタがゼロになるのをスピンして待ちます。メモリバリアで囲まれています。１９行目の poll() は、単純な遅延を提供するだけで、純粋なRCUセマンティクスから見るとなくてもよいです。以前と同じように、synchronize_rcu() が戻った時は、すべての以前のRCUリード側クリティカルセクションは完了したことが保証されます。
９．３．５．１節で示したロックベースの実装と比べて素晴らしいことに、この実装はRCUリード側クリティカルセクションの並列実行を許します。９．３．５．２節で示したスレッドごとのロックベースの実装と比べて素晴らしいことに、この実装はそれらがネストしても大丈夫です。さらに、rcu_read_lock() プリミティブはスピンもブロックもしないので、たぶん、デッドロックサイクルに参加することはないはずです。
クイッククイズ９．５４：
でも、もし、synchronize_rcu() を呼ぶ間、ロックを持っていて、同じロックをRCUリード側クリティカルセクションで取ったらどうなりますか？
しかし、この実装はまだいくつかの深刻な欠点があります。１つ目は、rcu_read_lock() と rcu_read_unlock() のアトミック操作はとても重いことです。リード側オーバーヘッドは、単一のPower5 CPU で約１００ナノ秒、６４CPUシステムで４０マイクロ秒以上です。ということは、RCUリード側クリティカルセクションは、現実的なリード側並列性を得るためには、かなり長くないといけないということです。一方、リーダーがいないときは、グレースピリオドは約４０ナノ秒で終わり、Linux カーネルの本番品質の実装と比べて何桁も高速です。
クイッククイズ９．５５：
synchronize_rcu() が１０ミリ秒の遅延があるのに、グレースピリオドが４０ナノ秒で終わるというのはどういうことですか？
２つ目は、もし多くの同時実行する rcu_read_lock() と rcu_read_unlock() 操作があると、 rcu_refcnt にすごいメモリ競合が生じ、高価なキャッシュミスが起きます。最初にあげたこれら２つの欠点は、RCUの主な目的、つまり、低オーバーヘッドのリード側同期プリミティブを提供するということを大きく損ないます。
最後に、多数のRCUリーダーが長いリード側クリティカルセクションを持っていると、synchronize_rcu() が全く終わらないことがあります。グローバルカウンタがけっしてゼロにならないからです。これは、RCU更新の飢餓につながり、もちろん、本番環境では許されないことです。
クイッククイズ９．５６：
図９．３８のRCU実装で、rcu_read_lock() を、同時実行する synchronize_rcu() が長く待ち過ぎているときには、単純に待つようにしたらどうですか？そうすれば、 synchronize_rcu() が飢餓することもないでしょう？
このため、この実装を本番環境で使うのはまだ考え難いです。ただ、これはロックベースの機構と比べると少しは可能性があります。例えば、高負荷のデバッグ環境のためのRCU実装としてなら良いかもしれません。次の節は、参照カウンタスキーマの変種を説明します。これはライターにより優しいのです。
９．３．５．４ 飢餓のないカウンタベースのRCU
図９．４０ (rcu_rcgp.h) は、RCU実装のリード側プリミティブです。これは、参照カウンタの対 (rcu_refcnt[]) 、その対から一つのカウンタを選ぶグローバルインデックス (rcu_idx) スレッドごとのネストのカウンタ rcu_ nesting グローバルインデックスのスレッドごとのスナップショット (rcu_read_idx)、 そしてグローバルロック (rcu_gp_lock) を使います。これらは、図９．３９にあります。
設計
飢餓からの自由を提供するのは、二要素の rcu_refcnt[] 配列です。鍵となる点は、synchronize_rcu() は既存のリーダーを待つ必要だけがあることです。ある synchronize_rcu() のインスタンスが既に実行を開始した後に新しいリーダーが始まっても、その synchronize_rcu() インスタンスはその新しいリーダーを待つ必要はありません。あるリーダーが rcu_read_lock() を使ってそのRCUリード側クリティカルセクションに入った時にはいつでも、それは、rcu_idx 変数が示す rcu_refcnt[] 配列の要素を加算します。その同じリーダーが rcu_read_unlock() を使ってそのRCUリード側クリティカルセクションを抜けた時には、それは自分が加算した要素を減算します。rcu_idx の値が、その後どのように変わっていても無関係です。
このしかけによって synchronize_rcu() は rcu_idx = !rcu_idx のように、rcu_idx の値をひっくり返すことによって飢餓を防ぐことができます。rcu_idx の古い値がゼロだったとします。なので、新しい値は1です。ひっくり返した後にやって来る新しいリーダーは rcu_idx[1] を加算するでしょうし、以前に rcu_idx[0] を加算した古いリーダーは、自分のRCUリード側クリティカルセクションを抜ける時に rcu_idx[0] を減算するでしょう。これは、rcu_idx[0] の値はもう加算されないことを意味します。なのでそれは単調に減少します。
脚注
この、「単調減少」文が無視している競合条件があります。この競合条件は、synchronize_rcu() のためのコードが対処します。とりあえずは、不信を棚上げすることをおすすめします。
これは、この synchronize_rcu() がしなくてはいけないことは、rcu_refcnt[0] の値がゼロになるのを待つだけであることを意味します。
この背景を理解したら、実際のプリミティブの実装を見る準備が出来ました。
実装
rcu_read_lock() プリミティブは、rcu_idx がインデックスする rcu_refcnt[] 対のメンバをアトミックに加算して、このインデックスのスナップショットをスレッドごと変数 rcu_read_idx に保持します。次に rcu_read_unlock() プリミティブはその対のうち、対応する rcu_read_lock() が加算した方のカウンタをアトミックに減算します。しかし、スレッドごとには rcu_idx の一つだけの値が記憶されるため、ネストを許すには追加の策が必要です。追加の策は、スレッドごとの rcu_nesting 変数を、ネストを追跡するために使います。
これを全部まとめて動かすと、図９．４０の rcu_read_lock() の６行目は現在スレッドの rcu_nesting のインスタンスをピックアップし、７行目でこれが一番外側の rcu_read_lock() ならば、８から10行目で rcu_ idx の現在値をピックアップして、それをこのスレッドの rcu_read_idx インスタンスに退避し、そして rcu_refcnt の選択された要素をアトミックに加算します。１２行目は rcu_nesting の値にかかわらず、それを加算します。１３行目はメモリバリアです。
同様に、rcu_read_unlock() 関数は２１行目でメモリバリアを実行し、２２行目でこのスレッドの rcu_nesting インスタンスをピックアップし、２３行目でこれが一番外側の rcu_read_unlock() ならば、24と２５行目で rcu_read_idx のこのスレッドのインスタンスをピックアップします(これは一番外側の rcu_ read_lock() で退避されました)。そして、rcu_refcnt の選択された要素をアトミックに減算します。２７行目は、ネストレベルにかかわらず、rcu_ nesting のこのスレッドのインスタンスを減算します。
図９．４１ (rcu_rcpg.c) は、対応する synchronize_rcu() 実装です。６と１９行目は rcu_gp_lock を確保、解放して、一つ以上の同時実行する synchronize_rcu() インスタンスを防ぎます。7と８行目は、rcu_idx の値をピックアップして、ひっくり返します。これによって、以降の rcu_read_lock() インスタンスは、その前のインスタンスが使ったのとは異なる rcu_refcnt の要素を使うようになります。
訳注
原文は、rcu_idx だけど、rcu_refcnt が正しいです。
次に、１０から１２行目は以前の rcu_refcnt の要素がゼロになるのを待ちます。９行目のメモリバリアは、rcu_idx の判定が、rcu_idx をひっくり返すことの前にリオーダーされないことを保証します。１３から１８行目はこの処理を繰り返します。そして２０行目はその後のメモリ回収操作が、rcu_refcnt の判定の前にリオーダーされないことを保証します。
クイッククイズ９．５．７
なぜ、図９．４１の synchronize_rcu() の５行目にメモリバリアがあるのですか？そのすぐ後にスピンロック確保があるではないですか。
クイッククイズ９．５８
なぜ、図９．４１ではカウンタは二回フリップされるのですか？単一の、フリップして待つサイクルで十分でないですか？
この実装は、図９．３８に示した単一のカウンタ実装で起きる可能性のある更新の飢餓問題を避けます。
議論
まだいくつかの深刻な欠点があります。最初に、rcu_read_lock() と rcu_read_unlock() にあるアトミック操作はまだとても重量級です。実際、それは図9.３８に示した単一のカウンタ変種よりも複雑です。リード側プリミティブは、単一の Power5 CPU で、約１５０ナノ秒、64-CPU システムでほぼ４０マイクロ秒を消費します。更新側の synchronize_ rcu() プリミティブも、より高価です。単一の Power5 CPU で、約２００ナノ秒、64-CPU システムで４０マイクロ秒以上を消費します。ということは、ある程度の実際のリード側並列性を得るためには、RCUリード側クリティカルセクションは極めて長くないといけないことを意味します。
二つ目に、もし多くの同時実行する rcu_read_lock() と rcu_read_unlock() 操作があると、rcu_refcnt 要素に極端なメモリ競合が起きます。それは高価なキャッシュミスになります。これは、並列なリード側アクセスを提供するために必要なRCUリード側クリティカルセクションの長さをさらに伸ばすことになります。この二つの欠点は、ほとんどの状況で、RCUの目的を損ないます。
三つ目に、rcu_idx を二回フリップする必要は、更新にかなりのオーバヘッドを課します。特にスレッド数が多い時は。
最後に、原理的には、同時実行するRCU更新は共通のグレースピリオドによって満足させられるという事実にもかかわらず、この実装はグレースピリオドをシリアライズして、グレースピリオドの共有をさせません。
クイッククイズ９．５９
アトミック加算と減算がそんなに高価なら、単純に、図９．４０の１０行目でアトミックでない加算を、２５行目でアトミックでない減算を使ったらどうです？
これらの欠点にもかかわらず、小規模な密結合マルチプロセッサ上でこのRCUの変種が使われることを想像するのは可能です。それはもしかすると、より複雑なRCU実装とAPI互換性を保つ、メモリの節約になる実装としてかもしれません。しかしそれは２，３のCPUを超えては上手くスケールするとは思えません。
次の節はさらに別の参照カウンタスキームの変種を説明します。それは、リード側の性能とスケーラビリティを大きく改善します。
９．３．５．５ スケーラブルなカウンタベースのRCU
図９．４３ (rcu_rcpl.h) は、参照カウンタのスレッドごとの対を使うRCU実装のリード側プリミティブです。この実装は図９．４０に示したものにとても似ています。唯一の違いは、rcu_refcnt がスレッドごと配列になった(図９．４２に示すように)ことです。前の節のアルゴリズムと同様に、この二要素の配列を使うことで、リーダーが更新者を飢餓させることはありません。
スレッドごとの rcu_refcnt[] 配列の利点は、rcu_read_lock() と rcu_read_ unlock() プリミティブがもはや、アトミック操作をしないことです。 クイッククイズ９．６０ うそつき！rcu_read_lock() には、atomic_read() プリミティブが見えます！！！なぜ、rcu_read_lock() がアトミック操作を含んでないふりをしようとするのです？？？
図9.４４ (rcu_rcpl.c)は、synchronize_rcu() と、ヘルパー関数 flip_counter_and_wait() の実装です。synchronize_rcu() 関数は図９．４１に示したものと似ていますが、繰り返されるカウンタフリップは、２２と２３行目の、新しいヘルパー関数呼び出しの対に置き換わっています。
新しい flip_counter_and_wait() 関数は、５行目で rcu_idx 変数を更新し、６行目でメモリバリアを実行し、７から１１行目でそれぞれのスレッドの以前の rcu_refcnt 要素に対して、それがゼロになるまで待って、スピンします。それら要素が全てゼロになったら、１２行目でもう一つメモリバリアを実行して戻ります。 このRCU実装は、そのソフトウェア環境に対して重要な新しい要求を課します。つまり、(１)スレッドごとの変数を宣言できること、(２)そのスレッドごとの変数は、他のスレッドからアクセスできること、(３)全てのスレッドを列挙できること。これらの要求は、ほとんど全てのソフトウェア環境で満足することができます。しかししばしば、スレッド数の上限は固定となります。その制限を避けることのできるより複雑な実装は可能です。例えば、拡張可能ハッシュテーブルを使うことにより。そのような実装では、rcu_read_lock() の最初の呼び出しで、発行元スレッドをテーブルに追加することでダイナミックにスレッドを追跡するかもしれません。
クイッククイズ９．６１ 結構。N スレッドがあると、2N 10ミリ秒ウェイト(flip_counter_and_wait() 呼び出しごとに一回)かかることがあります。しかもこれは、それぞれのスレッドに対してたった一度しか待たないことを前提とします。グレースピリオドがずっと速く完了する必要はないのですか？
この実装はなお、いくつかの欠点があります。最初に、rcu_idx を二回フリップするオーバヘッドがあります。 二つ目は、synchronize_rcu() は今回は、スレッド数に対して線形に増加する数の変数を調べなければいけません。これは多数のスレッドを持つアプリケーションではかなりなオーバヘッドを課します。
三つ目は、前と同様、グレースピリオドが共用できないことです。
最後に、前に述べたように、スレッド変数とスレッドを列挙することの必要性は、ソフトウェア環境によっては問題となるかもしれません。 とは言え、リード側プリミティブはとても良くスケールします。単一の Power5 CPUシステムで走っても、64-CPU でも、約１１５ナノ秒を要します。言ったように、synchronize_rcu() プリミティブはスケールしません。単一の Power5 CPU で、ほとんど１マイクロ秒、64-CPU システムでほぼ２００マイクロ秒のオーバヘッドになります。この実装は、本番品質のユーザレベルRCU実装の基礎をなすことができるかもしれません。 次の節は、より効率的な同時実行するRCU更新を可能とするアルゴリズムを説明します。
９．３．５．６ グレースピリオドを共用し、カウンタをベースとするスケーラブルなRCU
図９．４６ (rcu_rcpls.h) は、以前のようにスレッドごとの参照カウンタの対を持ち、かつ、更新がグレースピリオドを共用することができるRCU実装のリード側プリミティブです。図９．４３に示す以前の実装との主な違いは、rcu_idx が今回は自由にカウントできる long であることです。このため、図９．４６の８行目は、低オーダービットをマスクして除く必要があります。また、atomic_read() と atomic_set() の使用は、ACCESS_ONCE() に変えました。図９．４５に示すように、データもとても似ています。rcu_idx は atomic_t ではなく long になっています。
図９．４７ (rcu_rcpls.c) は、synchronize_rcu() と、そのヘルパー関数 flip_counter_and_wait() の実装です。これらは、図９．４４と似ています。flip_counter_and_wait() の違いは、 １ ６行目は atomic_set() でなく ACCESS_ONCE() を使います。ひっくり返すのではなく、加算します。 ２ 新しい７行目はカウンタの最低位ビットを取ります。 synchronize_rcu() はよりたくさん、あちこち変わっています。 １ 新しい oldctr ローカル変数があって、２３行目で rcu_idx のロック確保前の値を捕らえます。 ２ ２６行目は atomic_read() でなく ACCESS_ONCE() を使います。 ３ ２７から３０行目は、ロックが確保されている間に、他のスレッドによって少なくても３回のカウンタフリップがされたかを判定します。そして、もしそうなら、ロックを放し、メモリバリアをして、戻ります。この場合、カウンタがゼロになるまでのウェイトが完全に２回行われたわけで、この他のスレッドがすでに必要な仕事を全てしています。 ４ ３３と３４行目で、二回目の flip_counter_and_wait() は、ロックが確保されている間に2より少ないカウンタフリップがされた時に限って呼ばれます。そうでない時、二つのカウンタフリップがあったならば、他のスレッドがカウンタがゼロになるまでのウェイトを完全に一回したため、あと一つだけが必要です。 このアプローチでは、任意個数の多数のスレッドが同時に flip_counter_and_wait() を呼んだならば、カウンタがゼロになるまでのウェイトは全体でたった３回だけでしょう。
訳注 原文の、スレッドごとに一つのCPUというのは、不要でない？
改善はありましたがこのRCU実装はまだいくつかの欠点を持ちます。最初に、以前と同様、rcu_idx を二回フリップするオーバヘッドがあります。 二つ目に、それぞれの更新者は、行う仕事がなくても、rcu_gp_lock を取らないといけません。これは、同時実行する更新が多数の時、スケーラビリティを厳しく制限します。D.４節は、Linuxカーネルのための本番品質のリアルタイムRCU実装において、それを避ける一つの方法を示します。 三つ目に、この実装はスレッド変数とスレッドを列挙する必要があります。 最後に、３２ビットマシンにおいて、ある更新スレッドが長時間プリエンプトされて、rcu_idx カウンタがオーバフローするかもしれません。その結果、そのスレッドは不要なカウンタフリップを二回強制します。しかし、グレースピリオドがそれぞれ、１マイクロ秒しかかからないとしても、問題となるスレッドは１時間以上プリエンプトされる必要があります。その場合、余分にカウンタフリップを二回しても、あなたの心配事となることはないでしょう。 ９．３．５．３節で説明した実装と同様、リード側プリミティブは極めてよくスケールします。CPUの数によらず、ほぼ１１５ナノ秒のオーバヘッドです。synchronize_rcu() プリミティブはまだ高価です。約１マイクロ秒から、約１６マイクロ秒の範囲です。これはそれでも、９．３．５．５節の実装が起こす、ほぼ２００マイクロ秒と比べるとずっと安価です。なので、欠点はありますが、このRCU実装が現実世界のアプリケーションの本番で使われることを想像するのは可能です。
クイッククイズ９．６２ これらのおもちゃのRCU実装は全て、rcu_read_lock() と rcu_read_unlock() にアトミック操作を持つか、あるいは synchronize_rcu() のオーバヘッドがスレッド数に線形に増加するかのどちらかです。RCU実装が、これら３つのプリミティブ全てにおいて軽量の実装を楽しみ、全てが決定論的（O(1))オーバヘッドと遅延を持つことができるのは、どのような状況においてでしょうか？
図９．４６に戻ると、グローバル変数アクセスが一つと、少なくても４つのスレッドローカル変数へのアクセスがあります。POSIX スレッドを実装するシステムでの、スレッドローカルアクセスの比較的高いコストを考えると、３つのスレッドローカル変数を単一の構造体につぶして、rcu_read_lock() と rcu_read_unlock() がそれらのスレッドローカルデータを、一回のスレッドローカル記憶域アクセスでアクセスできるようにするのは、魅力的です。しかし、より良いアプローチは、スレッドローカルアクセスの回数を一回に減らすことでしょう。それについては次の節で。
９．３．５．７ フリーランニングカウンタをベースとするRCU
図９．４９(rcu.h と rcu.c)は、単一の、グローバルな、フリーランニングカウンタをベースとするRCU実装です。カウンタは、偶数値だけを取ります。図９．４８にデータを示します。これを使う rcu_read_lock() 実装はとても簡単です。３と４行目は単純に、グローバルなフリーランニングカウンタ変数 rcu_gp_ctr に１を加え、結果の奇数を、スレッドごとの変数 rcu_reader_gp に格納します。５行目はメモリバリアです。
rcu_read_unlock() 実装も似たようなものです。１０行目はメモリバリアで、１１と１２行目で rcu_gp_ctr グローバル変数を rcu_reader_gp スレッドごとの変数にコピーします。この結果、このスレッドごとの変数は偶数になるので、同時実行する synchronize_rcu() インスタンスはこれを無視して良いことがわかります。
クイッククイズ９．６３：
synchronize_rcu() があるタスクを無視して良いことを伝えるのに、偶数なら何でもよいのならば、図９．４９の１０と１１行目で単純に rcu_reader_gp にゼロを入れるのではだめですか？
このようにして、synchronize_rcu() はすべての、rcu_reader_gp スレッドごとの変数が偶数値になるのを待てばよいです。しかし、もっとずっと良い方法があります。なぜならば、synchronize_rcu() は、既存のRCUリード側クリティカルセクションだけを待てば良いからです。１９行目はメモリバリアで、RCU保護されたデータ操作が２１行目の加算の後に並べ直されないようにします。２０行目で rcu_gp_lock をとって、（３０行目で放します。）複数の synchronize_rcu() インスタンスが同時実行しないようにします。２１行目でグローバルな rcu_gp_ctr 変数を２つ加算します。これにより、すべての既存のRCUリード側クリティカルセクションの対応する rcu_reader_gp スレッドごとの変数が、マシンのワード長で剰余を取った場合、rcu_gp_ctr よりも小さくなります。偶数値を取る rcu_reader_gp を持つスレッドはRCUリード側クリティカルセクションにはいないことを思い出してください。こうして、２３から２９行目で rcu_reader_gp を走査して、すべてが偶数であるか、（２４行目）グローバルな rcu_gp_ctr より大きい（２５から２６行目）間、待ちます。２７行目は既存のRCUリード側クリティカルセクションを待つため、短い時間、ブロックします。しかし、グレースピリオドの遅延が重要ならば、これはスピンループに変えることもできます。最後に３１行目はメモリバリアで、次に来る破壊が以前のループの中に並べ直されるのを防ぎます。
クイッククイズ９．６４：
図９．４９の１９と３１行目のメモリバリアはなぜ必要ですか？２０と３０行目にあるロックプリミティブに必然的についてくるメモリバリアで十分でないですか？
このアプローチはずっと良いリード側性能を達成します。Power5 CPU の数によらず約６３ナノ秒のオーバーヘッドです。更新のオーバーヘッドはもっと大きく、単一のPower5 CPU で約５００ナノ秒、６４CPUシステムで１００マイクロ秒以上です。
クイッククイズ９．６５：
９．３．５．６節に説明した更新側のバッチ最適化を、図９．４９の実装に適用できないでしょうか？
この実装は、以前に述べた、更新側の高いオーバーヘッド以外にも、いくつかの深刻な欠点があります。１つ目は、RCUリード側クリティカルセクションをネストすることができなくなったことです。これについては次の節で取り上げます。２つ目は、もしリーダーが図９．４９の３行目でプリエンプトされたとします。rcu_gp_ctr のフェッチの後、rcu_gp_ctr のストアの前とします。そしてさらに、rcu_gp_ctr カウンタが半分以上進んで、すべての以前の値の前だったとします。すると、このとき、synchronize_rcu() は以降のRCUリード側クリティカルセクションを無視してしまいます。３つ目、最後は、この実装はまわりのソフトウェア環境が、スレッド一覧を列挙し、スレッドごとの変数を維持する機能を持つことを要求します。
クイッククイズ９．６６：
図９．４９の３から４行目でリーダーがプリエンプトされる可能性があるということは、本当に問題ですか？つまり、問題を引き起こす実際のイベントのシーケンスがありますか？ないならば、なぜないのですか？あるならば、どういうイベントのシーケンスですか？問題はどのように明らかになりますか？
９．３．５．８ フリーランニングカウンタをベースとするネスト可能なRCU
図９．５１(rcu_nest.h と rcu_nest.c)は、単一のグローバルフリーランニングカウンタをベースとするRCU実装を示します。ただ、これはRCUリード側クリティカルセクションのネストを許します。このネスト可能性は、グローバル rcu_gp_ctr の低オーダーのビットをネストを数えるために使うことで実現されます。その定義を図９．５０に示します。これは９．３．５．７節の図式の一般化です。それは、単一の低オーダーのビットをネストの深さを数えるために使っていたと考えることができます。このために、二つのCプリプロセッサマクロが使われます。RCU_GP_CTR_NEST_MASK と RCU_GP_CTR_BOTTOM_BIT です。これらは関係づいています。RCU_GP_CTR_NEST_MASK=RCU_GP_CTR_BOTTOM_BIT-1。RCU_GP_CTR_BOTTOM_BIT マクロは、ネストを数えるために使われるビットのちょうど上に位置づけられる単一のビットを含みます。そして RCU_GP_CTR_NEST_MASK は、ネストを数えるために使われる rcu_gp_ctr の全ての領域をカバーする１が立ったビットを持ちます。明らかに、これら二つのCプリプロセッサマクロは、RCUリード側クリティカルセクションの最大のネストを可能とするために必要な十分な、カウンタの低オーダービットを確保しなければいけません。この実装は、７ビットを確保します。これは、RCUリード側クリティカルセクションの最大１２７のネストの深さになります。これはほとんどのアプリケーションにとって必要な物を十分に超えるはずです。
結果となる rcu_read_lock() 実装はそれでも十分に直裁的です。６行目は rcu_reader_gp のこのスレッドのインスタンスへのポインタをローカル変数 rrgp に置きます。これは、高価な pthread スレッドローカル状態APIの呼び出し回数を最小にします。７行目は rcu_reader_gp の現在値を他のローカル変数 tmp に記録し、８行目は低オーダービットがゼロかを見ます。それは、これが最も外側の rcu_read_lock() であるかを示すはずです。そうならば、９行目はグローバルな rcu_gp_ctr を tmp に起きます。なぜならば、７行目で以前にフェッチした現在値は古くなっている可能性が高いからです。いずれの場合も１０行目はネストの深さを加算します。それは前に述べたように、カウンタの低位の７つのビットに格納されています。１１行目は更新されたカウンタを rcu_reader_gp のこのスレッドのインスタンスに書き戻します。そして最後に１２行目は、メモリバリアを実行して、RCUリード側クリティカルセクションが rcu_read_lock() を呼ぶ前にあるコードの中にしみだしていくのを防ぎます。
言葉を代えて言えば、この rcu_read_lock() の実装は、現在の rcu_read_lock() 呼び出しがRCUリード側クリティカルセクション内でネストしていない時に限って、グローバル rcu_gp_ctr のコピーをピックアップします。ネストしている時は、その代わりに現在スレッドの rcu_reader_gp インスタンスの内容をフェッチします。いずれの場合も、それはフェッチした値を、さらなるネストレベルを記録するために加算します。そしてその結果を現在スレッドの rcu_reader_gp インスタンスに格納します。
とても興味深いことに、rcu_read_unlock() の実装は、９．３．５．７節に示したものと全く同じです。１９行目はRCUリード側クリティカルセクションが rcu_read_unlock() を呼ぶ後にあるコードの中にしみだしていくのを防ぎます。そして２０行目は rcu_reader_gp のこのスレッドのインスタンスを減算します。それは、rcu_reader_gp の低オーダービットに含まれるネストのカウンタを減算する効果を持ちます。このプリミティブのデバッグ版は、（減算の前に！）これら低オーダービットがゼロでなかったかを確認します。
synchronize_rcu() の実装は、９．３．５．７節に示したものととても似ています。二つの違いがあります。最初は、２９と３０行目が、グローバル rcu_gp_ctr に定数「２」を加算するのではなく、RCU_GP_CTR_BOTTOM_BIT を加算することです。二つ目は、３３行目の比較が独立した関数に抽象化されたことです。それは、無条件に低オーダービットを判定するのではなく、RCU_GP_CTR_BOTTOM_BIT で示されるビットを判定します。 このアプローチは、９．３．５．７節に示したものとほぼ等しいリード側性能を達成します。Power5 CPU の数によらず、ほぼ６５ナノ秒のオーバーヘッドを起こします。更新は同様に、より多くのオーバーヘッドを起こします。単一の Power5 CPU で約６００ナノ秒、同じ６４CPUで１００マイクロ秒以上になります。
クイッククイズ９．６７ なぜ、単純に、前の節でやったように、スレッドごとのネストレベル変数を維持しないのですか？
この全ての複雑なビット操作をする代わりに。 この実装は、９．３．５．７節と同じ欠点を持ちます。ただ、RCUリード側クリティカルセクションのネストが許されました。さらに、３２ビットシステムでは、このアプローチはグローバル rcu_gp_ctr 変数がオーバフローするために必要な時間を短くします。次の節は、オーバフローが起きるのに必要な時間を大いに伸ばす一つの方法を示します。そしてそれは、リード側オーバーヘッドを大いに減らします。
クイッククイズ９．６８ 図９．５１で示したアルゴリズムにおいて、グローバル rcu_gp_ctr がオーバフローするために必要な時間を倍にするにはどうしますか？
クイッククイズ９．６９ 同様に、図９．５１で示したアルゴリズムにおいて、カウンタのオーバフローは致命的ですか？なぜ？あるいは、なぜそうでない？もしそれが致命的ならば、それをなおすにはどうすればいいですか？
９．３．５．９ 静止状態をベースにするRCU
図９．５３(rcu_qs.h) は、静止状態をベースにするRCU実装をユーザーレベルで作る時に使われる、リード側のプリミティブです。データは図９．５２です。図の１から７行目でわかるように、rcu_read_lock() と rcu_read_unlock() プリミティブは何もしません。なので、実際、インラインされて最適化の結果、なくなることが期待されます。Linux カーネルのサーバービルドではそうなっています。これは、静止状態をベースにするRCU実装が、RCUリード側クリティカルセクションの範囲を、前記静止状態を使って、近似するという事実のためです。これらの静止状態はそれぞれ、rcu_quiescent_state() 、図の９から１５行目です、呼び出しを持っています。長い休止状態（extended quiescent state）に入る（例えば、ブロックするとき）スレッドはその代わりに、長い休止状態に入るときに rcu_thread_offline() （７から２３行目）を、出る時に rcu_thread_online() （２５から２８行目）を呼んでもいいです。なので、rcu_thread_online() は rcu_read_lock() に、 rcu_thread_offline() は rcu_read_unlock() に似ています。また、rcu_quiescent_state() は、rcu_thread_online() に続けてすぐ rcu_thread_offline() を呼ぶと考えることもできます。
脚注
図のコードは、rcu_quiescent_state() が、rcu_thread_online() をしてすぐに rcu_thread_offline() することに同じであるということと矛盾しませんが、この関係は、性能最適化の結果、不明瞭になります。
RCUリード側クリティカルセクションから rcu_quiescent_state() 、 rcu_thread_offline() 、rcu_thread_online() を呼ぶのは誤りです。
rcu_quiescent_state() では、１１行目でメモリバリアを実行して静止状態の前にあるいずれかのコード（RCUリード側クリティカルセクションも含む）が静止状態の中に並べ直されるのを防ぎます。１２から１３行目はグローバル rcu_gp_ctr のコピーを持ってきます。ACCESS_ONCE() を使って、コンパイラが、rcu_gp_ctr を１回以上フェッチするような最適化をしないことを保証します。次に、フェッチした値に１を加えてそれをスレッドごとの rcu_reader_qs_gp 変数に格納します。そうすることで、同時実行する synchronize_rcu() が奇数値を見て、新しいRCUリード側クリティカルセクションが始まったことがわかるようにします。古いRCUリード側クリティカルセクションを待っている synchronize_rcu() インスタンスは、この新しい方を無視することができます。最後に、１４行目でメモリバリアを実行し、以降のコード（RCUリード側クリティカルセクションも含む）が１２から１３行目に並べ直されるのを防ぎます。
クイッククイズ９．７０：
図９，５３の１４行目の追加のメモリバリアは、rcu_quiescent_state のオーバーヘッドを大きく増やしませんか？
アプリケーションによっては、RCUを使うのはとてもまれですが、使うときにはとてもヘビーに使うものがあるでしょう。そのようなアプリケーションは、RCUを使い始めたら rcu_thread_online() を、使い終わったら、rcu_thread_offline() を呼ぶのが良いかもしれません。rcu_thread_offline() を呼んでから、次の rcu_thread_online() を呼ぶまでの期間は、長い静止状態です。RCUはこの期間は、明示的に静止状態が登録されることを期待しません。
rcu_thread_offline() 関数は単純にスレッドごとの rcu_reader_qs_gp 変数を rcu_gp_ctr の現在値に設定します。それは、偶数値です。同時実行する synchronize_rcu() インスタンスは、このスレッドを無視することができます。
クイッククイズ９．７１：
なぜ、図９．５３の１９と２２行目に、２つのメモリバリアが必要でしょう？
rcu_thread_online() 関数は、単純に rcu_quiescent_state を呼び、長い休止状態の終わりを示します。
図９．５４(rcu_qs.c)は、synchronize_rcu() の実装で、以前の節のものとよく似ています。
この実装は驚くほど速いリード側プリミティブを持ちます。rcu_read_lock() から rcu_read_unlock() のラウンドトリップは約５０ピコ秒のオーバーヘッドを引き起こします。synchronize_rcu() オーバーヘッドは、単一のPower5 CPU で約６００ナノ秒、６４CPUシステムで１００マイクロ秒以上です。
クイッククイズ９．７２：
念の為言っておくと、２００８年の Power システムのクロック周波数はとても高いですが、5GHz クロック周波数でも、ループを５０ピコ秒で実行するには足りません！これはどういうこと？
しかし、この実装は、それぞれのスレッドが定期的に rcu_quiescent_state() を呼ぶかあるいは長い静止状態のときは rcu_thread_offline() を呼ぶ必要があります。これらの関数を定期的に呼ばなくてはいけないというのは、この実装を、ある環境、例えばある種のライブラリで使うことを難しくします。
クイッククイズ９．７３：
図９．５３と９．５４のRCU実装を使うのが簡単かどうかということに、そのコードがライブラリにあるかどうかという事実がなぜ違いを生むのでしょう？
クイッククイズ９．７４：
もし、synchronize_rcu() を呼ぶ間、ロックを持っていたとします。同じロックをRCUリード側クリティカルセクションで取ったらどうなりますか？これはデッドロックになるでしょう。でも、全くコードを生成しないプリミティブがデッドロックサイクルに寄与するなんてできるのでしょうか？
さらに、この実装は同時実行する synchronize_rcu() がグレースピリオドを共有するのを許しません。とはいえ、このバージョンのRCUをベースにした本番品質のRCU実装を想像するのは難しくはないでしょう。
９．３．５．１０ おもちゃのRCU実装のまとめ
ここまでたどりつけた方、おめでとう！あなたは今では、RCU自身についてだけでなく、まわりのソフトウェア環境とアプリケーションの要求についても、ずっと明快にわかったはずです。さらに深い理解を求める方は、付録Dを読まれることをおすすめします。そこでは、本番で十分に使われているRCU実装をいくつか紹介します。
これまでの節は、いろいろなRCUプリミティブの好ましい性質のリストを示しました。以下のリストは新しいRCU実装を作ろうという人へのわかりやすいレファレンスです。
１ リード側プリミティブ（rcu_read_lock() と rcu_read_unlock() のような）と、グレースピリオドプリミティブ（synchronize_rcu() と call_rcu() のような）が必要です。グレースピリオドが始まった時に存在したすべてのRCUリード側クリティカルセクションは、グレースピリオドが終わった時には完了している必要があります。
２ RCUリード側プリミティブは、最小限のオーバーヘッドであるべきです。特に、キャッシュミス、アトミック命令、メモリバリア、そして分岐などの高価な操作は避けるべきです。
３ RCUリード側プリミティブは、リアルタイムの使用に耐えるため、 O(1) 計算複雑量を持つべきです。（これは、リーダーが更新者と同時実行することを意味します。）
４ RCUリード側プリミティブは、すべてのコンテキストで使えるべきです。（ Linux カーネルでは、アイドルループ以外のどこででも許されます。）重要な特別ケースとして、RCUリード側プリミティブはRCUリード側クリティカルセクションで使えるべきだということです。これは、RCUクリティカルセクションをネストできるようにするためです。
５ RCUリード側プリミティブは、条件なしに実行可能で、エラーリターンするべきでありません。この特性はとても重要です。エラーチェックは複雑さを増し、テストと検証を面倒にします。
６ 静止状態（そして、つまりはグレースピリオド）以外の操作は何でも、RCUリード側クリティカルセクションで許されるべきです。特に、I/O などの不可逆の操作は許されるべきです。
７ RCUリード側クリティカルセクションの中で実行しているときに、RCUで保護されたデータ構造を更新できるべきです。
８ RCUリード側と、更新側のプリミティブの両方とも、メモリアロケーターの設計と実装とは無関係であるべきです。つまり、あるRCU実装が、あるデータ構造を保護するとき、そのデータ要素がどのように確保、解放されるかによらずに可能であるべきです。
９ RCUグレースピリオドは、RCUリード側クリティカルセクションの外側で停止するスレッドによってブロックされるべきではありません。（しかし、ほとんどの静止状態をベースとする実装は、この要求に従わないことに注意ください。）
クイッククイズ９．７５：
RCUリード側クリティカルセクションではグレースピリオドは禁止されます。では、RCUリード側クリティカルセクションにいるときにRCUデータ構造を更新するにはどうしたらいいでしょう。
９．３．６ RCU練習問題
この節は、クイッククイズの連続として構成されます。それはあなたに、この本の以前の例のいくつかに対して、RCUを適用するように勧めます。それぞれのクイッククイズの答えは、少しのヒントを与え、また、解決策が詳細に説明されている後の節へのポインタも含みます。この練習のほとんどにとって、rcu_read_lock(), rcu_read_unlock(), rcu_dereference(), rcu_assign_pointer(), そして synchronize_rcu() プリミティブで十分のはずです。
クイッククイズ９．７６ 図５．９に示す統計カウンタ実装 (count_end.c) は、read_count() での合計を守るために、グローバルロックを使いました。それは、貧弱な性能と負のスケーラビリティをもたらします。RCU を使って、素晴らしい性能と良いスケーラビリティを持つ read_count() を提供するにはどうしたらいいでしょう？（read_count() のスケーラビリティは、それが全てのスレッドのカウンタを走査する必要が有ることから必然的に制限されることを覚えておいて下さい。）
クイッククイズ９．７７ ５．５節は、リムーバブルデバイスへのI/Oアクセスを数えることを扱う奇妙なコード断片の対を示しました。これらのコード断片は、リーダーライターロックを取る必要に由来する、高速パス（I/O を開始する）での高いオーバーヘッド問題を持ちます。RCU を使って、素晴らしい性能とスケーラビリティを提供するにはどうしたらいいでしょう？（I/O アクセスを行う、一般ケースである最初のコード断片の性能は、デバイス削除のコード断片の性能よりもずっと重要であることを覚えておいて下さい。）
９．４ どれを選んだらいいか？
表９．７は、この章で説明した４つの遅延処理技術の中であなたが選択をするのを助けるためのおおまかな規則です。
“Existence Guarantee” カラムに示されるように、連結データ要素に存在確認が必要なら、参照カウンティング、ハザードポインタ、あるいはRCUを使わなくてはいけません。シーケンスロックは存在確認を提供しません。その代わり、更新を検出して、更新と当たったリード側クリティカルセクションをリトライします。
もちろん、“Updates and Readers Progress Concurrently” カラムに示されるように、この更新の検出は、シーケンスロックが更新とリーダーが同時に進行するのを許しません。
訳注。表のYはNの誤りです。
結局、そのような進行を防ぐのが、シーケンスロックを使うそもそもの目的ですから！この状況は、シーケンスロックを参照カウント、ハザードポインタ、そしてRCUと一緒に使って、存在保証と更新の検出の両方を提供するという道を示します。実際、Linuxカーネルはパス名検索の時に、RCUとシーケンスロックをこの方法で組み合わせています。 “Read-Side Overhead”カラムは、これらの技術の大まかなリード側オーバーヘッドと呼べるものを与えます。参照カウントのオーバーヘッドは、大きく変わることがあります。最も低い場合、単純なアトミックでない加算で十分です。少なくても、他の理由のために確保されないといけないロックの保護のもとで、参照が得られるという場合においては。最も高い場合、完全にオーダーされたアトミック操作が必要です。参照カウントは、トラバースされる全てのそれぞれのデータ要素ごとにこのオーバーヘッドを起こします。ハザードポインタは、トラバースされるそれぞれのデータ要素ごとにメモリバリアのオーバーヘッドを起こします。そして、シーケンスロックはクリティカルセクションを実行しようとする試みごとに、メモリバリアの対のオーバーヘッドを起こします。RCU実装のオーバーヘッドは何もないこともあり、それぞれのリード側クリティカルセクションごとのメモリバリアの対のこともあります。この結果、RCUは最も高性能です。特に、多くのデータ要素をトラバースするリード側クリティカルセクションのためには。 “Bulk Reference”カラムは、RCUだけが、定数のオーバーヘッドで複数の参照を得る能力があることを示します。シーケンスロックのエントリは、“N/A”です。なぜならば、繰り返しますが、シーケンスロックは更新を検出するのであって、参照を確保しないからです。
クイッククイズ９．７８ でも、参照カウントもハザードポインタも、定数のオーバーヘッドで複数のデータ要素への参照を得ることができるのではありませんか？
単一の参照カウントが複数のデータ要素をカバーすればよいですよね？ “Low Memory Footprint”カラムはどの技術が小さいメモリフットプリントを提供するかを示します。このカラムは、“Bulk Reference”カラムの鏡像となりました。多数のデータ要素に対して参照を得る能力は、それら全てのデータ要素が永続的でなくてはいけないことを意味し、それは転じて、場合によっては大きなメモリフットプリントを意味します。例えば、あるスレッドが長いRCUリード側クリティカルセクションを実行している間に、同時に他のスレッドが多数のデータ要素を削除しているかもしれません。リード側クリティカルセクションは潜在的に新しく削除されたデータ要素のどれの参照も持っていることがあり得ますから、これら全てのデータ要素はそのクリティカルセクションの完全な長さの間、保持されなくてはいけません。それに対して、参照カウントとハザードポインタは同時実行するリーダーが実際に参照している特定のデータ要素だけを保持するでしょう。
しかし、この低メモリフットプリントの利点は、犠牲を伴います。“Unconditional Acquisition” カラムに示すとおりです。それを見るために、巨大な連結されたデータ構造を想像して下さい。参照カウントあるいはハザードポインタのリーダー(それをスレッド A と呼びます)がその構造の中間の孤立したデータ要素への参照を保持しています。以下のイベントのシーケンスを考えましょう。
１ スレッド B は、スレッド A が参照しているデータ要素を削除します。この参照のために、そのデータ要素はまだ解放できません。
２ スレッド B は、スレッド A が参照しているデータ要素に隣接するものを全て削除します。これらのデータ要素の参照を持っているものはないので、それらは直ちに解放されます。スレッド A のデータ要素は既に削除されているので、その外に向かうポインタは更新されません。
３ スレッド A のデータ要素の全ての外に向かうポインタはフリーリストを参照することになりました。なので、安全にトラバースすることはできません。
４ 参照カウントあるいはハザードポインタ実装はこのため、スレッド A がそのデータ要素から外に向かうポインタを経由して参照を得ようとする全ての試みを失敗させる以外の選択肢を持ちません。
短くいえば、参照の正確な追跡を提供する全ての遅延処理技術は、参照を得ようとする試みを失敗させる準備もしなくてはいけません。なので、RCUのメモリフットプリントの短所は、使いやすさという長所を意味します。つまり、RCUリーダーは確保の失敗を扱わなくてよいです。 メモリフットプリント、正確な追跡、そして確保の失敗の間のこの緊張は、Linuxカーネルにおいて、RCUと参照カウンタを組み合わせることで解決されることがあります。RCUは短寿命の参照のために使われます。ということは、RCUリード側クリティカルセクションは短いでしょう。この短いRCUリード側クリティカルセクションはさらに、対応するRCUグレースピリオドも短いだろうことを意味します。それはメモリフットプリントを制限します。より長寿命の参照が必要ないくつかのデータ要素に対しては、参照カウントが使われます。ということは、それらわずかのデータ要素だけが、参照確保の失敗という複雑さを扱わなくてはいけないだけだということです。参照確保のほとんどは、RCUのおかげで、無条件です。 最後に、“Non-Blocking Updates” カラムは、ハザードポインタがノンブロッキング更新を提供できることを示します [Mic04, HLM02]。参照カウントは実装によって、できることもできないこともあります。しかし、シーケンスロックは、その更新側ロックのために、ノンブロッキング更新を提供できません。RCU更新者はリーダーを待たなくてはいけないので、これも、完全にノンブロッキングな更新は不可能です。しかし、唯一のブロッキング操作は、メモリ解放を待つことだけである状況があります。それはその結果、多くの目的に対して、ノンブロッキングと同じくらいに良いと言える状況もあります [DMS+12]。
これらの技術を個別に、あるいは、組み合わせて使う経験がより多く得られるにつれて、この節で述べたおおまかな規則は改良される必要があるでしょう。しかし、この節は、たしかに現在の最近の状況を反映しています。
９．５ 更新の方は？
この章で取り上げた遅延処理技術は、リードがほとんどの状況で最も直接的に適用可能です。それは、「更新はどうですか？」という疑問を起こします。結局、リーダーの性能とスケーラビリティを増すのは全く結構なことです。しかし、ライターにも、素晴らしい性能とスケーラビリティを求めるのはただ、自然なことです。 ライターの高性能とスケーラビリティを特徴とする一つの状況を、既に見ました。つまり、５章で概観を述べたカウンティングアルゴリズムです。これらのアルゴリズムは、部分的に分割されたデータ構造を特徴とします。このため、更新はローカルに作用することができます。その一方、より高価なリードは、データ構造全体にわたって合計をしなくてはいけません。Silas BoydWickhizer は、この概念を一般化して OpLog を開発しました。それを彼は、Linux カーネルのパス名検索、仮想メモリリバースマップそして、stat() システムコールに適用しました [BW14]。 “Disruptor”と呼ばれるもう一つのアプローチは、入力データの大容量ストリームを処理するアプリケーションのために設計されました。このアプローチは、単一生産者、単一消費者の FIFO キューに依存し、同期の必要を最低にします[Sut13]。Java アプリケーションにとって、Disruptor はガーベッジコレクションの使用を最低にする利点もあります。 そしてもちろん、それが使える状況ならば、６章で述べたように、完全に分割された、あるいは、“sharded”システムは、素晴らしい性能とスケーラビリティを提供します。
以上