perfbook 付録F7-F9の訳

以下は、perfbook の付録F7からF9の kanda.motohiro@gmail.com による訳です。perfbook の訳の他の部分は、親文書を参照。付録の続きは、こちらを参照。

F.7 ロック

７．１ ロックが、研究論文において、むち打たれる少年である理由は、それが現実にたくさん使われているからです。そうでなくて、ロックを誰も使わず、気にしないなら、ほとんどの研究論文はわざわざそれに触れることもないでしょう。

７．２

グラフにサイクルが無いと仮定します。すると、directed acyclic graph (DAG) ができます。それは少なくても１つのリーフノードを持つはずです。

もしこのリーフノードがロックなら、どのスレッドにも持たれていないロックを待っているスレッドがいることになり、定義に反します。（そして、この場合、そのスレッドは、直ちにロックを取れます。）

一方、そのリーフノードがスレッドなら、ロックを何も待っていないスレッドがいることになり、これも定義に反します。（そして、この場合、そのスレッドは実行中であるか、ロックでないもののためにブロックしています。）

なので、このデッドロックの定義によれば、対応するグラフにサイクルがなくてはいけません。

７．３

まさしくあります！以下は、そのわずかです。

１ ライブラリ関数の引数の１つが、ロックへのポインタで、このライブラリ関数でそのロックを取るとします。そしてもし、ライブラリ関数が、自分のロックの一つを保持している時に、コール元のロックを取ろうとすると、コール元とライブラリの両方を含むデッドロックサイクルができることがあります。

２ ライブラリ関数の戻り値が、ロックへのポインタで、コール元でそのロックを取るとします。そしてもし、コール元が、ライブラリのロックを保持している時に、コール元のロックの１つを取ろうとすると、またも、デッドロックになります。

３ ライブラリ関数の一つがロックを取り、それを持ったまま戻ったとします。そしてもし、コール元が自分のロックの一つを取ろうとすると、またまた、デッドロックになります。

４ コール元が、ロックを取るシグナルハンドラを持っているとします。すると、デッドロックになります。しかしこの場合、ライブラリのロックは、デッドロックサイクルにおいて無実の傍観者です。しかし、シグナルハンドラからロックを取るのは、ほとんどの環境で、ダメダメであることに注意下さい。それは悪い考えであるだけでなく、サポートされてないのです。

７．４

比較されるデータ要素をプライベート化します。（８章で述べるように）あるいは、参照カウンティングのような、遅延機構を使います。（９章で述べるように）

７．５ ロッキングプリミティブです。もちろん！ ７．６ 絶対に違います！ あるプログラムが、mutex_a そして mutex_b を、この順に取るとします。そして、 mutex_a を pthread_cond_wait に渡します。ここで、pthread_cond_wait は、mutex_a を放し、戻る前に再度、確保します。何か他のスレッドがその間に mutex_a をとって、mutex_b を待ってブロックするなら、プログラムはデッドロックします。 ７．７ 絶対に違います！ この変換は、layer_2_processing() 関数が冪等であることを前提とします。つまり、layer_1() のルーティング決定が変わったら、同じパケットに対して複数回実行することができます。なので、本当の人生では、この変換は任意に複雑となります。

７．８ そうかも。 もし、layer_1() のルーティング決定がとても頻繁に変わると、コードは常にリトライし、決して前に進みません。これは、どのスレッドも進むことができない時は「ライブロック」と呼ばれ、あるスレッドは進むけど他のスレッドは進まない時は、「飢餓」と呼ばれます。（７．１．２節を参照。） ７．９ もう一つ、グローバルロックを追加します。あるスレッドが必要なロックを取るのを、何度も繰り返して試み、失敗した時には、そのスレッドに、無条件に新しいグローバルロックを取らせます。その後、無条件に必要なロックを全て取らせます。（Doug Lea の提案によります。）

７．１０

なぜなら、これはデッドロックになるからです。シグナルハンドラ以外のところで、シグナルをブロックすることなく、ロックAが取られているとします。このロックを持っている時にシグナルが来るかもしれません。対応するシグナルハンドラは、次に、ロックBを取ろうとします。こうして、ロックAを持ったまま、ロックBが取られます。このため、問題で述べたように、ロックBを持っている時にさらにロックAを取るなら、デッドロックサイクルになります。

なので、シグナルハンドラの中で取られる可能性のあるロックを持っている時に、シグナルをブロックすることなく、シグナルハンドラ以外のところで取られる可能性のある別のロックをさらに取るのは違法です。

７．１１

最も簡単で、高速な一つの手段は、シグナルを設定する時に sigaction() に渡す struct sigaction の sa_mask フィールドを使うことです。

７．１２

なぜならば、これらの同じ規則が、オペレーティングシステムカーネルと、ある種の組み込みアプリケーションで使われる、割り込みハンドラに適用できるからです。

多くのアプリケーション環境では、シグナルハンドラでロックを取るのは非難されることです。しかし、それは、賢い開発者が、（通常は愚かにも）自作のロックをアトミック操作を使って作るのを止めることはできません。そして、アトミック操作は多くの場合、シグナルハンドラで完全に合法です。

７．１３

アプローチはたくさんあります。

１ シミュレーションでパラメタサーチをする場合、（例えば）機械あるいは電子デバイスの優れた設計に集中するために、多数のシミュレーションが実行される場合は、シミュレーションはシングルスレッドのままにしておいて、そのシミュレーションの多数のインスタンスを並列に実行します。これは、オブジェクト指向デザインを保持し、しかもより高いレベルでの並列性を得ます。さらに、同期オーバヘッドも避けることが期待されます。

２ オブジェクトをグループに分割し、ある時点では、一つ以上のグループのオブジェクトを操作する必要が無いようにします。そして、それぞれのグループにロックを関連付けます。これは、７．１．１７節で述べた、一度に一つのロック設計の例です。

３ オブジェクトをグループに分割し、すべてのスレッドはグループのオブジェクトを、なんらかのグループごとの順序に従って操作できるようにします。そして、それぞれのグループにロックを関連付けます。さらに、グループ間にロック階層を強制します。

４ ロックに、任意に決めた階層を強制します。そして、７．１．１５節で述べたように、ロックを逆順に取らないといけない時は条件付きロックを使います。

５ ある操作のグループを実行する前に、どのロックが取られるかを予想します。そして、実際に何らかの更新を行う前にそれらを取ろうと試みます。予想が間違っていた時は、すべてのロックを放して、新しい予想のもとでやり直します。それは、経験によって改善しているはずです。このアプローチは、７．１．１．６節で述べました。

６ トランザクショナルメモリを使います。このアプローチは多くの利点と欠点を持ち、１６．２節で議論します。

７ アプリケーションをリファクタして、同時実行に優しくします。これは、そのアプリケーションを、シングルスレッドの時にでも速くする副作用も持つことが期待されます。しかし、そのアプリケーションを変更するのをより難しくすることもあるかもしれません。

８ ロックの他に、これ以降の章で述べるテクニックを使います。

７．１４

図７．１０に、良いヒントがあります。多くの場合、ライブロックは、あなたがご自分のロック設計を見直すべきだということを示します。あるいは、そのロック設計が「できたばかり」なら、初めて、よく見る機会です。

とはいえ、１つの良い、十分なアプローチは、Doug Lea によるもので、７．１．１．５節で述べる条件付きロックを使うことです。さらに、７．１．１．６節で述べる。共用データを変更する前に、まず必要なロックをすべて取るというのと組み合わせます。もしあるクリティカルセクションがあまりに多くリトライする時は、無条件にグローバルロックを取って、そして無条件に必要なロックを全て取ります。これにより、デッドロックとライブロックを避けます。さらに、グローバルロックがあまりに頻繁に取られる必要のある時を除けば、けっこうスケールします。

７．１５

いくつかあります。

１ １秒の待ちは、ほとんどの用途にはかなり長過ぎます。待ち時間は、ほぼクリティカルセクションを実行するのに必要な時間から始めるべきです。それは普通は、マイクロ秒かミリ秒の範囲でしょう。

２ コードは、オーバーフローを考慮していません。一方、このバグは、前のバグによって、無害になります。３２ビットの秒は、５０年以上です。

７．１６

ある意味ではそれも良いでしょう。しかし、時には高いロック競合になる設計を使うのが適切である状況もあります。

例えば、まれにエラー条件が起きるシステムを考えましょう。まれなエラー条件の間は、低い性能とスケーラビリティを持つ単純なエラー処理の設計をするほうが、複雑でデバッグが困難で、前記まれなエラー条件が実際に起きた時にだけ役に立つ設計よりも良いかもしません。

とはいえ、普通は、単純であり、かつ、エラー条件のときにも効率が良い設計を作るように努力するのは意味のあることです。例えば、問題を分割することによって。

７．１７

ロックで守られるデータがロック自身と同じキャッシュラインにあると、他のCPUがそのロックを取ろうと試みるとき、ロックを持っているCPUにとって高価なキャッシュミスが起きます。これは、偽の共有の特別ケースで、異なるロックで守られる変数の対がたまたまキャッシュラインを共有すると起きることがあります。それに対して、ロックがそれが守るデータと異なるキャッシュラインにあれば、ロックを持っているCPUは通常はその変数への最初のアクセスの時にキャッシュミスをするだけです。

もちろん、ロックとデータを別々のキャッシュラインに置く欠点は、競合のないときにコードが１回でなく２回のキャッシュミスを起こすことです。

７．１８

この使い方はまれです。しかし、たまに行われます。要点は、排他ロックのセマンティクスが２つのコンポーネントを持つことです。（１）よく知られた、データ保護のセマンティクスと、（２）メッセージのセマンティクスです。後者では、あるロックを放すと、同じロックの確保を待っている人に通知がされます。空のクリティカルセクションは、データ保護コンポーネントを使わないで、メッセージのコンポーネントを使います。

この答えの残りの部分は、空のクリティカルセクションの使用例をいくつか提供します。しかし、これらの例は、「灰色の魔法」と考えられるべきです。

脚注

この言葉を考えてくれた Alexey Roytman に感謝します。

なので、空のクリティカルセクションは、ほとんど決して、現実では使われません。ですが、この灰色の領域に進みましょう。。。

空のクリティカルセクションの１つの歴史的な使用は、2.4 Linux カーネルのネットワークスタックに現れました。この使用パターンは、９．３節で述べるリード、コピー、アップデート（RCU)の効果を近似する方法と考えることができます。

空のクリティカルセクションのイディオムは、ある状況でロック競合を減らすのに使うこともできます。例えば、マルチスレッドのユーザ空間アプリケーションで、それぞれのスレッドがスレッドごとのリストで維持される、仕事の単位を処理する時を考えましょう。スレッドは、お互いのリストを触ることは禁止されています。そして、また、更新があり、更新が進む前には、全ての以前にスケジュールされた仕事の単位が完了していることが必要です。これを処理する１つの方法は、それぞれのスレッドで１つの仕事の単位をスケジュールすることです。これらの全ての仕事の単位が完了すれば、更新は進むことができます。

あるアプリケーションでは、スレッドは来て、去ります。例えば、それぞれのスレッドはそのアプリケーションの１人のユーザに対応するかもしれません。なので、そのユーザがログアウトあるいは切断したら、スレッドは除去されます。多くのアプリケーションで、スレッドはアトミックに去ることはできません。そうでなく、そのアプリケーションのいろいろな部分から、特別のアクションのシーケンスを使って、明示的に自身を取り除いていく必要があります。１つの特定のアクションは、それ以上の要求を他のスレッドから受け取るのを拒否することでしょう。そして、もう一つの特定のアクションは、自分のリストに残った全ての仕事の単位を捨てることでしょう。例えば、これらの仕事の単位をグローバルな、仕事のアイテムを捨てるためのリストに置いて、残った他のスレッドの一つに拾ってもらうようにすることでしょう。（単に、そのスレッドの仕事のアイテムのリストを順に実行して、空にしたらどうでしょう？ある仕事のアイテムはさらに多くの仕事のアイテムを生成するかもしれないので、リストは期限内に空にできないかもしれません。）

アプリケーションが性能とスケールの点でうまくやるには、良いロック設計が必要です。１つの一般的な解決策は、一つのグローバルロック（Gと呼びましょう）を、去るプロセス全体（そしてたぶん、他のものも）を保護するために使い、より細かい粒度のロックをそれぞれの除去操作を保護するために使うことです。

さて、去るスレッドは明らかに、自分のリストにある仕事を捨てる前に、それ以上の要求を受け付けるのを拒否しないといけません。なぜなら、そうしないと捨てたアクションの後から、新しい仕事が届き、せっかく捨てたのが無効になります。なので、去るスレッドのための単純化された擬似コードは、以下になります。

１ ロックGを取る。

２ コミュニケーションを守るロックを取る。

３ 他のスレッドからの以降のコミュニケーションを拒否する。

４ コミュニケーションを守るロックを放す。

５ グローバルな仕事アイテムを捨てるためのリストを守るロックを取る。

６ 全てのペンディングの仕事アイテムを、グローバルな仕事のアイテムを捨てるためのリストに移す。

７ グローバルな仕事アイテムを捨てるためのリストを守るロックを放す。

８ ロックGを放す。

もちろん、全ての既存の仕事アイテムを待つ必要のあるスレッドは、去るスレッドも考慮に入れないといけません。これを考えるために、このスレッドが、去るスレッドが他のスレッドからのコミュニケーションを拒否したちょうどすぐ後に、全ての既存の仕事アイテムが終わるのを待ち始めたとしましょう。このスレッドは、どうしたら、去るスレッドの仕事アイテムが完了するのを待つことができるでしょう？スレッドは、他のスレッドの仕事アイテムのリストをアクセスするのは許されないのを思い出して下さい。

一つの直裁的なアプローチは、このスレッドがG を取って、次に、グローバルな仕事アイテムを捨てるためのリストを守るロックを取って、次に、仕事アイテムを自分のリストに移すことです。

そのスレッドは、次に、両方のロックを放し、仕事アイテムを自分のリストの最後に置き、そして、自分がそれぞれのスレッド（自分も含む）のリストに置いた仕事アイテムが全て完了するのを待ちます。

このアプローチは、多くの場合にうまくいきます。しかし、それぞれの仕事アイテムが、グローバルな仕事アイテムを捨てるためのリストから取り出されるときに特別な処理が必要だとすると、Gの競合が激しくなります。この競合を避ける一つの方法は、Gを取って、すぐに放すことです。そうすると、全ての既存の仕事アイテムを待つ処理は、以下のようになります。

１ グローバルカウンタを１にして、条件変数をゼロにします。

２ 全てのスレッドにメッセージを送って、それぞれが、グローバルカウンタをアトミックに加算し、仕事アイテムをエンキューするようにさせます。仕事アイテムはアトミックにグローバルカウンタを減算し、結果がゼロなら、条件変数を１にします。

３ Gを取ります。これにより、現在去ろうとしているスレッドが去り終わるのを全て待つことになります。一度に一つのスレッドしかされないので、残りのスレッドは全て、前の手順で送ったメッセージを受け取っているはずです。

４ Gを放します。

５ グローバルな仕事アイテムを捨てるためのリストを守るロックを取ります。

６ グローバルな仕事アイテムを捨てるためのリストから全ての仕事アイテムを、このスレッドのリストに移します。

７ グローバルな仕事アイテムを捨てるためのリストを守るロックを放します。

８ このスレッドのリストに、追加の仕事アイテムをエンキューします。（前と同じく、この仕事アイテムは、グローバルカウンタを減算し、もし結果がゼロなら、条件変数を１にします。）

９ 条件変更が値１を取るのを待ちます。

この手順が完了したら、全ての既存の仕事アイテムは完了したことが保証されます。空のクリティカルセクションは、ロックを、データ保護のためだけでなく、メッセージとしても使います。

７．１９

実際、いくつかのやり方があります。一つの方法は、 null、保護されたリード、排他モードを使うことです。他の方法は、null、保護されたリード、並列同時ライトモードを使うことです。３つ目の方法は、null、並列同時リード、排他モードを使うことです。

７．２０

単一のグローバルロックを条件付きで確保するのは、確かにとてもうまくいきます。ただし、比較的少ない数のCPU に限ります。なぜこれが、数百のCPUを持つシステムで問題になるかを考えるために、図５．３を見て、遅延を８から１０００CPUに外挿して下さい。 

７．２１

なぜかって？これは、並列制御において、人生と同じく、ゲームを始める前に、勝利が実際に何を伴うのかを調べるべきだということを、単に示しているのです。

７．２２ なぜならば、このデフォルト初期化は、ある関数のスコープ内で auto 変数としてアロケートされたロックに対しては効かないからです。

７．２３ そのロックが確保されていて、いくつかのスレッドがそのロックを取ろうとしているとします。この状況では、これらのスレッドが全部、アトミック交換操作でループしたならば、そのロックを含むキャッシュラインはそれらの間でピンポンされて、インターコネクトに負荷を与えます。一方、これらのスレッドが７から８行目の内側のループでスピンしたなら、それらはすべて自分自身のキャッシュ内でスピンしますから、インターコネクトには無視できる負荷しか与えません。 ７．２４ それも正しい実装です。ただし、このストアの前にメモリバリアがあって、それが ACCESS_ONCE() を使う限りにおいて。xchg() 操作を使う時にはメモリバリアは不要です。なぜならばそれが値を返すためにその操作は完全なメモリバリアを暗黙的に意味するからです。

７．２５ C 言語では、以下のマクロがこれを正しく扱います。

#define ULONG_CMP_LT(a, b) \

 (ULONG_MAX / 2 < (a) - (b))

単純に二つの符号付き整数を引き算しがちですが、それはいけません。C 言語では、符号付きオーバーフローは未定義です。例えば、もしコンパイラが、値の片方が正数でもう一つが負数だと知っていれば、単純に、正数のほうが負数より大きいと判断する権利があります。しかし、正数から負数を引いた結果がオーバーフローして、負数になることもあります。

コンパイラは、どのようにして２つの数の符号を知るのでしょう？以前のポインタアサインメントあるいは、比較から推測できるかもしれません。この場合、もしCPU ごとのカウンタが符号付きであれば、コンパイラはそれらが常に値が増加すると推論できます。そして、決して負にならないと仮定するかもしれません。この仮定は、コンパイラに不幸なコードを生成させることになります。

７．２６ フラグアプローチは通常、キャッシュミスが少ないと思われます。しかし、より良い答えは、両方をやってみて、あなたの固有のワークロードにとってどちらが良いか、見ることです。 

７．２７ 以下は、暗黙的存在保証の不適切な使用に起因するバグのいくつかです。

１ プログラムが、グローバル変数のアドレスをファイルに書きます。そして、後で、その同じプログラムのインスタンスがそのアドレスを読んで、ディレファレンスしようとします。これは、アドレス空間ランダム化のために失敗することがあります。そのプログラムを再コンパイルしたら、言うまでもありません。 

２ モジュールが、自分の変数の一つのアドレスを他のモジュールにあるポインタに記録するとします。そのモジュールがアンロードされた後で、そのポインタをディレファレンスしようとします。

３ 関数が、自分のスタック上の変数の一つのアドレスをグローバルポインタに記録するとします。その関数が戻った後で、他の関数がそれをディレファレンスしようとします。 

あなたはきっと他の可能性も思いつくことでしょう。

７．２８

これはとても単純なハッシュテーブルで、チェーニングはありません。なので、あるバケツにある唯一の要素は、最初の要素です。読者は、この例を、完全なチェーニングを持つハッシュテーブルに適用すると良いでしょう。

７．２９

以下のイベントのシーケンスを考えましょう。

１ スレッド０が、delete(0) を呼んで、図の１０行目に来て、ロックを取ります。

２ スレッド１が、同時に delete(0) を呼び、１０行目に来て、スレッド０がロックを持っているのでスピンします。

３ スレッド０は、１１から１４行目を実行し、その要素をハッシュテーブルから除き、ロックを放し、要素を解放します。

４ スレッド０は、実行を続け、メモリを確保し、今解放したばかりのそのブロックを得ます。

５ スレッド０は、このメモリブロックを、何か他の型の構造として初期化します。

６ スレッド１の、 spin_lock() 操作は失敗します。 p->lock であると信じているものが、既にスピンロックでは無いという事実のためです。

存在保証が無いため、データ要素のアイデンティティは、あるスレッドがその要素のロックを、１０行目で確保しようとしている間に変わることがあります！

F.8 データ所有 ８．１ 関数での auto 変数の使用です。デフォルトで、これらは、現在の関数を実行しているスレッドにプライベートです。 ８．２ sh & 演算子を使ったスレッド作成と、 sh wait コマンドを使ったスレッドジョインです。 もちろん、プロセスが、例えば、shmget() や mmap() システムコールによって、明示的にメモリを共有するときは、共用メモリをアクセスあるいは更新するときには明示的な同期がもちろん必要です。プロセスは、以下のプロセス間通信機構のどれを使っても、同期することができます。 １ システム V セマフォー ２ システム V メッセージキュー ３ UNIX ドメインソケット ４ TCP/IP, UDP そしてその他いろいろのネットワークプロトコル ５ ファイルロック ６ O_CREAT と O_EXCL フラグをつけた open() システムコールの使用 ７ rename() システムコールの使用 可能な同期機構の完全なリストを作るのは、読者への課題とします。なお、とても長いリストになるだろうと警告します。驚くほどの数の予期しないシステムコールを、同期機構として使うことができます。 ８．３ これは哲学的質問です。 「いいえ」と答えたい人は、プロセスは定義からして、メモリを共用しないと主張するでしょう。 「はい」と答えたい人は、共用メモリを必要としない多数の同期機構をリストするでしょう。なお、カーネルはいくらかの共用状態を持ちますし、プロセスID (PID) の割り当てでさえ、共用データを構成すると主張することもできるでしょう。 そのような議論は、素晴らしい知的演習です。そして、自分が知的だと感じたり、不運なクラスメートや同僚から点を勝ち取ったり、（特に！）なにか役に立つことをするのを避けるための素晴らしい方法です。 ８．４ 十分驚くべきことに、はい、です。一つの例は、単純なメッセージパッシングシステムで、スレッドが他のスレッドのメールボックスにメッセージを置く時です。そして、それぞれのスレッドが、そのメッセージが処理された後、メッセージを削除する責任があるとします。そのようなアルゴリズムの実装は、読者への課題とします。また、似たような所有パターンを持つ他のアルゴリズムを探すのも課題とします。 ８．５ そのような機構にはとても多くがあります。例えば： １ システム V メッセージキュー ２ 共用メモリデキュー（６．１．２節を参照） ３ 共用メモリメールボックス ４ UNIX ドメインソケット ５ TCP/IP や UDP。そして、 RPC, HTTP, XML, SOAP などなど多数の高レベルのプロトコルによる補強。 完全なリストを作るのは、十分に視野の狭い読者への課題とします。なお、とても長いリストになるだろうと警告します。 ８．６

鍵となるフレーズは、「データへの権利を持つ」です。この場合、問題となる権利は、図の１行目で定義されるスレッドごとの counter 変数をアクセスする権利です。この状況は、８．２節で述べたものに似ています。

しかし、eventual() スレッドが所有しているデータも実際にあります。つまり、図の１７と１８行目で定義される、t と sum 変数です。

専用スレッドの他の例としては、Linuxカーネルのカーネルスレッドを見て下さい。例えば、kthread_create() と kthread_run() で作られるものです。

８．７

はい。一つのアプローチは、read_count() が、自分自身のスレッドごと変数の値を加える事です。これは、完全な所有と性能を維持しますが、正確さはわずかしか改善しません。特に、とても多数のスレッドのあるシステムでは。

他のアプローチは、read_count() が、関数シッピングを使うことです。例えば、スレッドごとのシグナルという形で。これは、大いに正確さを改善しますが、read_count() に多大な性能コストを払わせます。

しかし、これらのどちらの方法も、カウンタを更新するという一般的な場合での、キャッシュラインの往復を除くという利点があります。

F.9 遅延処理

９．１

これは、最後の参照を放すことと新しい参照を得ることの間の競合を解決することができますが、データ構造が解放されて再確保、時には全く異なるタイプの構造体として、されるのを防ぐためには、全く何もしません。「単純なコンペアアンドスワップ操作」を、異なるタイプの構造体に適用したら、未定義の結果になるのは十分あり得ることです。

要するに、コンペアアンドスワップのようなアトミック操作を使うには、型の安全あるいは存在の保証が絶対に必要です。

９．２

CPUは、参照を得るためには、すでにその参照を持っていなければいけないというのが規則でした。なので、あるCPUが最後の参照を放したら、新しい参照を得ることのできるCPUはいないはずです。図９．２の２２行目でアトミックでないチェックをしてもいいのは、このためです。

９．３

これらの関数が正しく使われるなら、そういうことは起きないはずです。既に参照を持っていないのに、 kref_get() を呼ぶのは間違いです。その場合、kref_sub() がカウンターをゼロに減算するはずはありません。

９．４

コール元は、少なくとも１つの参照があり続けることがわかっている場合以外は、オブジェクトが継続的に存在することを期待できません。通常、コール元はこれを知る手段がないので、kref_sub() を呼んだ後は、そのオブジェクトを参照しないように注意しないといけません。

９．５

「if」条件が終わって、参照カウンター値が１だったとします。解放操作が走って、参照カウンターをゼロにし、クリーンアップ操作を始めます。しかし、「then」節がそのカウンターを１に戻します。こうして、オブジェクトがクリーンアップの後に使われることになります。

９．６

hp_record() は、同時実行する変更をチェックする必要があるからです。そのために、要素へのポインターのポインターが必要です。要素へのポインターの変化をチェックできるためです。

９．７

ある意味、非効率かもしれませんが、そのような再開始は正確さのために絶対必要だというのが真実です。これを見るために、ハザードポインタで保護された連結リストに、要素、A,B そして C があり、以下のイベントが起きるとします。

１ スレッド０が要素Bへのハザードポインタを格納する。（たぶん、要素Aから要素Bにトラバースしてきたのでしょう。）

２ スレッド１がリストから要素Bを削除し、要素Bから要素Cへのポインターを、特別な HAZPTR_POISON 値にして、削除がわかるようにする。スレッド０は要素Bへのハザードポインタを持っているので、まだ解放されることはできない。

３ スレッド１が要素Cをリストから削除する。要素Cを参照するハザードポインタはないので、直ちに解放される。

４ スレッド０が、現在は削除されている要素Bの次の要素のハザードポインタを得ようとする。しかし、HAZPTR_POISON 値を見て、ゼロを返す。コール元は、リストの最初からトラバーサルをやり直さないといけない。

それはとても良いことです。そうしないと、スレッド０は現在は解放されている要素Cをアクセスしようとし、とんでもないメモリー破壊になるところでした。特に、要素Cのメモリーがそれ以降、他の用途のために再確保されていた場合は大変です。

９．８

論文のハザードポインタ実装は、挿入と削除にノンブロッキング同期技術を使っています。この技術は、データ構造をトラバースするリーダーが、更新者が更新を完了するのを「助ける」必要があります。つまり、リーダーは削除された要素の次を見る必要が有ることを意味します。

一方、私達は更新を同期するのにロックを使います。リーダーが、更新者が更新を完了するのを助ける必要はありません。このため、ポインターのボトムビットを使う必要はありません。このアプローチは、リード側のコードが単純で高速になります。

９．９

これらの制限は、参照確保が失敗する可能性のある、参照カウンティング機構にだけ必要です。

９．１０

そういう見方もできます。しかし、問題のアトミック変数に他のCPUがアクセスしない場合、実際にアトミック命令を使うオーバーヘッドは無駄です。他のCPUがアクセスしない例を２つ上げると、初期化とクリーンアップです。

９．１１

たしかにしません。しかし、ハザードポインタ自身への書き込みはしますし、もっと大切なのは、それぞれが失敗する可能性のある hp_store() すべてについて失敗のケースが処理されないといけないことです。なので、ハザードポインタはとても便利ですが、改善された機構を調べるのは意味のあることでしょう。

９．１２

シーケンスロック機構は、実際には、２つの別々の同期機構、シーケンスカウントとロック、の結合です。実際、シーケンスカウント機構は、 Linux カーネルでは、独立した write_seqcount_begin() と write_seqcount_end() プリミティブで使用可能です。

しかし、結合した、write_seqlock() と write_sequnlock() プリミティブの方が、 Linux カーネルでは、ずっとより頻繁に使われます。もっと大切なのは、あなたが「シーケンスカウント」と言うより「シーケンスロック」と言う方が、より多くの人があなたが意味するものを理解できるということです。

なので、この節は、人々が題だけからなんのことかわかるように、「シーケンスロック」と題がついています。「遅延処理」の章にあるのは、（１）「シーケンスロック」の「シーケンスカウント」面を強調するためと、（２）「シーケンスロック」はただのロック以上のものだからです。

９．１３

それを実現する１つの自明な方法は、リードオンリーアクセスを含むすべてのアクセスを、write_seqlock() と write_sequnlock() で囲むことです。もちろん、この方法はすべてのリード側並列性を禁止しますし、それより、単純なロックを使って同じように簡単に実装できます。

あなたが、read_seqbegin() と read_seqretry() を使ってリード側アクセスを保護する解決策を思いついたなら、以下のイベントシーケンスを正しく処理できるか確認して下さい。

１ CPU0が連結リストをトラバースしていて、リスト要素Aへのポインターを、拾う。

２ CPU1がリストから要素Aを削除して、解放する。

３ CPU2が無関係なデータ構造を確保して、かつて要素Aが占めていたメモリを得る。この無関係なデータ構造で、かつて要素Aの ->next ポインターとして使われていたメモリーは、浮動小数点数が入っている。

４ CPU0は、かつての要素Aの ->next ポインターを拾い、ランダムビットを得て、セグメントフォールトする。

この種の問題を防ぐ１つの方法は、「型安全なメモリー」を使うことです。これは、９．３．３．６節で説明します。しかしその場合、あなたはシーケンスロックに加えて、他の同期機構も使っていることになります！

９．１４

それも正しい実装でしょう。しかし、チェックを read_seqretry() まで動かしても、得るものはないでしょう。命令数はほぼ同じでしょう。さらに、リーダーが呪われたリード側クリティカルセクションから行うアクセスはライターのキャッシュミスという形でオーバーヘッドを起こすことがあります。このキャッシュミスは、図９．９の１９行目にあるように、チェックを read_seqbegin() の中に置くことで避けることができます。 ９．１５ もしそれがないと、コンパイラもCPUも、read_seqretry() 呼び出しの前にあったクリティカルセクションを、この関数の後に動かすことができます。すると、シーケンスロックはクリティカルセクションを守ることができません。smp_mb() プリミティブがそのような再配置を防ぎます。 ９．１６ 古い Linux カーネルでは、ノーです。 とても新しいバージョンの Linux カーネルでは１７行目を、ACCESS_ONCE() でなく、smp_load_acquire() にすることができます。すると、１８行目の smp_mb() を落とすことができます。同じように、４４行目は smp_store_release() を使うことができます。例えば、以下のとおり。 smp_store_release(&slp->seq, ACCESS_ONCE(slp->seq) + 1); これによって、４３行目の smp_mb() を落とすことができます。 ９．１７ なにもありません。これが、シーケンスロックの１つの弱点です。この結果、シーケンスロックはリードがほとんどの状況でしか使うべきではありません。もちろん、あなたの状況で、リード側の飢餓が許容できるならば、シーケンスロックの更新をじゃんじゃんやるがよいでしょう！ ９．１８ 今の場合、 ->lock フィールドは除くことができます。Linux カーネルでは、seqcount_t にありますから。 ９．１９ 全然ダメです。Linux カーネルはいくつかの特別な属性を持って、以下のイベントのシーケンスを無視できるようにしています。 １ スレッド０が read_seqbegin() を実行して、１７行目で up ->seq を拾う。値は偶数なので、コール元に返す。 ２ スレッド０がリード側クリティカルセクションを始める。しかし、長い間、プリエンプトされる。 ３ 他のスレッドが、繰り返し write_seqlock() と write_sequnlock() を呼んで、up ->seq がオーバーフローしてスレッド０がフェッチした値になる。 ４ スレッド０は実行を続行し、リード側クリティカルセクションを終わるが、データは矛盾している。 ５ スレッド０は read_seqretry() を呼び、シーケンスロックで守られたデータは一貫していると誤って結論付ける。 Linux カーネルはシーケンスロックを、まれにしか更新されないものに使います。現在時刻はその例です。この情報はせいぜい１ミリ秒に１回、更新されるだけなので、カウンターがオーバーフローするには７週間必要です。もしカーネルスレッドが７週間の間プリエンプトされたなら、Linux カーネルのソフトロックアップ検出コードがその間ずっと、２分に１回、警告を出し続けるはずです。 これに比べて、６４ビットカウンターでは、ナノ秒ごとに更新をしても、オーバーフローには５世紀以上必要です。なので、この実装は６４ビットシステムでは ->seq の型に６４ビットを使います。 ９．２０ はいでもいいえでもあります。seqlock リーダーはライターと同時実行できますが、それが起きた時には、read_seqretry() プリミティブはリーダーにリトライを強制します。これはつまり、seqlock ライターと同時実行する seqlock リーダーの行った仕事は、すべて、破棄され、やり直さないといけないということです。なので、seqlock リーダーは、ライターと同時に走ることはできますが、実際にはなんの仕事も行えません。 これとは違って、RCUリーダーは同時実行するRCU更新者がいても、役に立つ仕事をすることができます。 ９．２１ Linux が動くシステムではみんな、ポインタへのロードとストアはアトミックです。つまり、もしポインタへのストアがその同じポインタからのロードと同時に起きた場合、ロードは、最初の値か、ストアされた値のいずれかを返し、決してその２つをビットごとの混ぜあわせたものを返すことはありません。 さらに、list_for_each_entry_rcu() は常にリストを前に進み、後ろを見ることはありません。なので、list_for_each_entry_rcu() は list_add_rcu() が加えた要素を見るか見ないかのどちらかであり、いずれにしても有効で、正しい形式のリストを見ます。 ９．２２ hlist では、終端チェックはヘッドに当たるのでなくて、NULL で行う必要があるからです。（単一ポインタの hlist_for_each_entry_rcu() をコーディングしてみるとよいです。ちゃんとできたら、すごいです！） ９．２３ それをやる１つの方法を図 F.5 に示します。 複数の同時実行する削除が synchronize_rcu() で待つことがあるのに注意してください。

９．２４ それは同期の設計に依存します。更新を守るセマフォーが、グレースピリオドの間、持たれたままなら、最大でも２バージョンしかありません。新しいのと古いのです。 しかし、検索と更新と list_replace_rcu() だけがロックで守られ、synchronize_rcu() がロックの外にあるとします。図 F.5 に示すコードを参照。さらに、多数のスレッドがRCU 置換をほぼ同時に行い、リーダーはデータ構造をコンスタントにトラバースしているとします。 すると、以下のイベントのシーケンスが起きます。図９．２２の最後の状態から始まります。 １ スレッドAがリストをトラバースして、5,2,3 要素への参照を得る。 ２ スレッドBが 5,2,3 要素を新しい 5,2,4 要素と置換する。そして、synchronize_rcu() 呼び出しが戻るのを待つ。 ３ スレッドCがリストをトラバースして、 5,2,4 要素への参照を得る。 ４ スレッドDが、5,2,4 要素を新しい 5,2,5 要素と置換する。そして、synchronize_rcu() 呼び出しが戻るのを待つ。 ５ スレッドEがリストをトラバースして、5,2,5 要素への参照を得る。 ６ スレッドFが5,2,5 要素を新しい 5,2,6 要素と置換する。そして、synchronize_rcu() 呼び出しが戻るのを待つ。 ７ スレッドGがリストをトラバースして、5,2,6 要素への参照を得る。 ８ 前記２ステップが素早く繰り返され、全部が、いずれの synchronize_rcu() 呼び出しが戻るより前に起きる。 このように、任意の数のバージョンがアクティブであることができます。メモリーと、グレースピリオドの間に、どれだけの更新が完了できるかにだけ制限されます。しかし、こんなに頻繁に更新されるデータ構造は、RCU には向いてないかもしれないことに注意してください。結論は、RCU は、必要とあれば、高い更新率も処理できるということです。 ９．２５ あるRCU更新者が行う変更は、関連するCPUの、そのデータを含むキャッシュラインを無効にし、同時実行するRCUリーダーに高価なキャッシュミスを強制します。（同時実行するリーダーに高価なキャッシュミスを起こさないで、データ構造を変更できるアルゴリズムを設計できますか？以降のすべてのリーダーに対しても？）

９．２６ まず、この測定をしたときの内部のループは、以下です。 つぎに、rcu_read_lock() と rcu_read_unlock() の実質的定義は以下です。 さらに、コンパイラが簡単な最適化をして、ループは、以下になります。 なので、１００フェムト秒の「測定」は、時間測定の固定オーバーヘッドをrcu_read_lock() と rcu_read_unlock() 呼び出しを含む内部ループの回数で割ったものとなります。なので、実はこの測定は、誤りです。任意のオーダーだけ誤っています。上記 rcu_read_lock() と rcu_read_unlock() の定義でわかるように、実際のオーバーヘッドは正確にゼロです。 １００フェムト秒の時間計則が見積もり過ぎだったというのは珍しいことです！ ９．２７ 元となる rwlock_t に対する競合が、クリティカルセクションのオーバーヘッドが長くなるに連れて少なくなるためです。しかし、このリードライトロックのオーバーヘッドは、単一CPUの時の値まで減ることはありません。キャッシュスラッシングのオーバーヘッドがあるためです。 ９．２８ RCUリード側クリティカルプリミティブを含むデッドロックサイクルを起こす１つの方法は、以下の（不正な）文のシーケンスです。 synchronize_srcu() は、すべての既存のSRCUリード側クリティカルセクションが完了するまで戻りません。しかし、それは、synchronize_srcu() が戻るまで完了できない SRCUリード側クリティカルセクションの中にあります。この結果、古典的な自己デッドロックになります。リーダーライターロックで、リードロックを持っている時にそれをライトロックしようとするのと同じです。 この自己デッドロックシナリオは、クラシックRCUには当てはまりません。なぜならば、synchronize_rcu() によって起こるコンテキストスイッチがこのCPUに対して静止状態として働くため、グレースピリオドが完了するからです。しかし、これはむしろよりひどいことであり、RCUリード側クリティカルセクションで使っているデータがグレースピリオド満了の結果、解放されることがあるからです。 つまり、RCUリード側クリティカルセクションの中から、同期のRCU更新側プリミティブを呼んではいけません。 ９．２９ 本当にうまくいきます。実際、そうでなければ、 Linux カーネルは動きません。 ９．３０ これは、おもちゃの例の法則の結果です。ある時点を超えるとコード断片は同じに見えます。私達がコードをどう考えるかだけが違います。しかし、この差が、とても重要なときがあります。１つの例をあげると、RCUを制限された参照カウンティングスキーマであると思うならば、更新がRCUリード側クリティカルセクションを排除することがあると誤って思い込むことはないでしょう。 それにしても、例えばあなたがリーダーライターロックをRCUで置換しようとしているならば、RCUをリーダーライターロックの代わりとして考えるのはとても役に立ちます。 ９．３１ たぶん、NUMA効果です。しかし、エラーバーでわかるように、 refcnt 線の測定値にはかなりの偏差があります。実際、ある場合には標準偏差が測定値の１０％以上になることもありました。なので、オーバーヘッドのへこみは、統計的異常なのかもしれません。 ９．３２ 図７．１７と同じように、これはとても単純なハッシュテーブルで、チェーンを持ちません。なので、あるバケツには先頭要素しかありません。読者は、この例を、完全なチェーンを持つハッシュテーブルに拡張してみるよう、再度、おすすめします。 ９．３３ まず、１４行目の２回めのチェックは必要なことに注意ください。私達がロックを取るのを待つ間に他のCPUがこの要素を削除しているかもしれません。しかし、ロックを取るときに、私達がRCUリード側クリティカルセクションにいるという事実は、この要素が再確保されてこのハッシュテーブルに再挿入されることがありえないことを保証します。さらに、ロックを取った以降は、ロック自身が、要素の存在を保証します。なので、RCUリード側クリティカルセクションにいる必要はなくなります。 要素のキーをもう一度チェックする必要があるかという問題は、読者の宿題とします。 ９．３４ この２行の順序を入れ替えるとします。するとこのコードは以下のイベントのシーケンスの場合こわれます。 １ CPU0が delete() を呼び、１５行目を実行して削除する要素を見つけます。要素を実際には削除しておらず、これからするところです。 ２ CPU1が同時に delete() を呼び、この同じ要素を削除しようとします。しかし、CPU0がロックを持っているので、CPU1は１３行目で待ちます。 ３ CPU0が１６と１７行目を実行して１８行目で、CPU1がそのRCUリード側クリティカルセクションを抜けるのを待ちます。 ４ CPU1がロックを取りますが、CPU0が既に要素を削除しているので１４行目のテストが失敗します。CPU1は２２行目を実行します。（クイッククイズのために、２３行目と入れ替えてあります。）そして、RCUリード側クリティカルセクションを抜けます。 ５ CPU0は synchronize_rcu() から抜けることができます。そして、１９行目を実行し、要素をフリーリストに移します。 ６ CPU1は要素のロックを放そうとしますが、要素は解放されています。さらに悪いことに、何か他のデータ構造型として再確保されているかもしれません。これは致命的なメモリ破壊エラーです。 ９．３５ 少なくても１つのスレッドがRCUリード側クリティカルセクションにいる期間が、任意に長くなる可能性のあるということは確かです。しかし、９．３．３．６節の説明のキーワードは、「使用中」と「既存の」です。あるRCUリード側クリティカルセクションは、概念的には、そのクリティカルセクションが開始した時に使用中であったデータ要素だけに対して参照を得ることができることに注意下さい。さらに、スラブは、そのすべてのデータ要素が解放された時に限りシステムに返されることを思い出して下さい。実際、それらすべてが解放されるまで、RCUグレースピリオドは始まりません。 このため、スラブキャッシュは、スラブの最後の要素が解放される前に始まったRCUリード側クリティカルセクションだけを待てばよいのです。これはつまり、最後の要素が解放された後に開始したRCUグレースピリオドであれば、どれでも良いということです。そのグレースピリオドが終わったら、スラブは、システムに返されることができます。 ９．３６ １つのアプローチは、nmi_profile() で、rcu_read_lock() と rcu_read_unlock() を使うことです。そして、synchronize_sched() を、synchronize_rcu() に代えます。図F.6で示したとおりです。 ９．３７ 感嘆符の着いたAPIメンバー（rcu_read_lock(), rcu_read_unlock(),そして call_rcu()）だけが、Paul E. McKenney が、１９９０年代中頃に知っていた Linux RCU API です。その頃は、彼は、RCU のことは全部わかったという誤った思いを抱いていました。 ９．３８ RCUリード側クリティカルセクションが synchronize_rcu() 呼び出しを無限にブロックするのを防ぐために、何かをする必要はありません。なぜならば、synchronize_rcu() 呼び出しは既存のRCUリード側クリティカルセクションだけを待つ必要があるからです。なので、それぞれのRCUリード側クリティカルセクションが有限の長さならば、何も問題はありません。 ９．３９ 全然違います！特に、プリエンプティブRCUを使っている時は違います！その時は、synchronize_irq() を使う必要があります。あるいは、あなたが、synchronize_rcu() に待ってほしい割り込みハンドラの中に、rcu_read_lock() と rcu_read_unlock() 呼び出しを入れてもよろしい。 ９．４０ call_rcu_bh() が呼ばれた時に、rcu_read_lock_bh() と rcu_read_unlock_bh() で区切られるRCUリード側クリティカルセクションがない場合、RCUはコールバックを直ちに呼び出す権利を持ちます。それはたぶん、RCUリード側クリティカルセクションでまだ使っているデータ構造を解放することになるでしょう！これは、理論的な可能性というだけではありません。rcu_read_lock() と rcu_read_unlock() で区切られる長く走るRCUリード側クリティカルセクションは、この失敗モードになる可能性があります。 しかし、rcu_dereference() ファミリーの関数は、RCUのすべてのフレーバーで使えます。（かつては、rcu_dereference() のフレーバーごとの変種を作ろうとしたことがありますが、単純に面倒過ぎました。）

９．４１

絶対にいいえ！そして特に、プリエンプト可能RCUを使っている時にはそうです！もしあなたが割り込みハンドラ内で “rcu_bh” で守られるデータ構造をアクセスする必要があるならば、rcu_read_lock_bh() と rcu_read_unlock_bh() の明示的な呼び出しが必要です。

９．４２ non-PREEMPT あるいは PREEMPTカーネルでは、この二つを混ぜると、「事故によって」うまくいきます。なぜならば、これらのカーネルビルドでは、RCUクラシックとRCU Sched は同じ実装にマップするからです。しかし、-rt パッチセットを使った PREEMPT_RT ビルドでは、この混合は致命的です。それは、リアルタイムRCUのリード側クリティカルセクションはプリエンプトされることがあるという事実のためです。その結果、RCUリード側クリティカルセクションがその rcu_read_unlock() 呼び出しに達する前に、synchronize_sched() が戻ることが許されます。この結果、そのリード側クリティカルセクションがあるデータ構造を使い終わる前にそれが解放されることにつながります。それはあなたのカーネルが経験する統計的危険を大きく増すことになります。 実は、RCUクラシックとRCU Sched を分けたのは、プリエンプト可能なRCUリード側クリティカルセクションの必要性に触発されたからです。

９．４３ それは正しいです！-rt Linux はスレッド化した割り込みハンドラを使うため、割り込みハンドラのまんなかでコンテキストスイッチがあるかもしれません。synchronize_sched() はそれぞれのCPUがコンテキストスイッチを通過するまで待つだけなので、それはある割り込みハンドラが完了する前に戻ることがあります。 もしあなたが、ある割り込みハンドラが完了するのを待つ必要があるならば、その代わりに synchronize_irq() を使うか、あるいはあなたが待ちたい割り込みハンドラの中に、明示的なRCUリード側クリティカルセクションを置くべきです。

９．４４ 非同期インタフェースがあると、一つのタスクが、任意の多数のSRCUあるいはQRCUコールバックを登録できます。それは、任意の多量のメモリを消費します。それに対して、現在の同期の synchronize_srcu() と synchronize_qrcu() インタフェースでは、あるタスクは次のグレースピリオドを待ち始めることができる前に、その前のグレースピリオドの待ちを終わらなくてはいけません。

９．４５ 原理的には、あなたは、ある srcu_struct を使っているRCUリード側クリティカルセクションの中で、何か他の srcu_struct によって synchronize_srcu() を使うことができます。しかし現実的には、そうするのはほぼ確実に、悪い考えです。特に、図F．７に示すコードはそれでもデッドロックになります。 ９．４６ next ポインタをポイズンするのは、このポインタを使わなくてはいけない同時実行するRCUリーダーに干渉します。しかし、RCUリーダーはprev ポインタを使うことを禁止されているので、安全にそれをポイズンできます。

９．４７ そのような例外の一つは、複数要素の連結データ構造が一つの単位として他のCPUからアクセスできない状況で初期化され、そしてその後、このデータ構造へのグローバルポインタを植え付けるために、rcu_assign_pointer() が一度使われる場合です。初期化時のポインタ代入は rcu_assign_pointer() を使う必要はありません。しかし、その構造体がグローバルに見えるようになった後に起きる全てのそのような代入は rcu_assign_pointer() を使わなくてはいけません。 しかし、この初期化コードが極めてホットなコードパスにあるのでない限り、いずれにしても rcu_assign_pointer() を使うのが賢明かもしれません。理論的には不必要としてもです。「ちっぽけな」変更が、あなたが大切に守ってきた、初期化がプライベートに起きるという前提を無効にするのはあまりにも簡単なことです。

９．４８ “sparse”のような自動コードチェッカー(あるいは、実に、人類)にとって、あるRCUトラバーサルプリミティブがどんなタイプのRCUリード側クリティカルセクションに対応するかを判断するのが難しいことがあります。例えば、図F．８に示すコードを考えましょう。 このrcu_dereference()  プリミティブは、RCU クラシックのクリティカルセクションにあるのでしょうか、RCU Sched でしょうか？これを見つけるにはどうしたらいいでしょう？

９．４９ 図 F.9 の foo() と bar() が異なるCPUで同時に実行されたとします。foo() は、３行目で my_lock をとり、 bar() は１３行目で rcu_gp_lock をとります。foo() が４行目に行って、 bar() が持つ rcu_gp_lock をとろうとします。そして、bar() が１４行目で、foo() が持つ my_lock をとろうとします。 それぞれの関数は、他方が持つロックを待ちます。古典的なデッドロックです。 他のRCU実装は、rcu_read_lock() でスピンもブロックもしませんから、デッドロックは起きません。 ９．５０ 実際、このようにリーダーライターロックを使うこともできます。しかし、教科書のリーダーライターロックは、メモリー競合が激しいので、実際に並列実行を可能とするには、RCUリード側クリティカルセクションはとても長くないといけません。 一方、rcu_read_lock() で、リード用にリーダーライターロックを使うのは、前記のデッドロック条件を避ける事ができます。 ９．５１ この変更は、デッドロックを再度、導入します。なので、いいえ、クリーンではありません。 ９．５２ １つのデッドロックは、ロックが synchronize_rcu() の間保持されていて、その同じロックがRCUリード側クリティカルセクションで取られるケースです。しかし、この状況は、どんな正しいRCU実装でもデッドロックします。結局、synchronize_rcu() プリミティブはすべての既存のRCUリード側クリティカルセクションが終わるのを待たないといけませんが、これらクリティカルセクションのどれかが synchronize_rcu() を実行しているスレッドが持つロックに対してスピンしているならば、これはRCUの定義に内在するデッドロックと言えます。 もうひとつのデッドロックは、RCUリード側クリティカルセクションをネストしようとすると起きます。このデッドロックは、この実装固有のもので、再帰的なロックを使ったり、リーダーライターロックを使って rcu_read_lock() でリード確保、synchronize_rcu() でライト確保するなどをすることによって避ける事ができます。 しかし、以上の２つのケースを除くと、このRCU実装は、これ以上のデッドロック状況を持ちません。これは、他のスレッドのロックを取ろうとするのが、synchronize_rcu() を実行するときだけであり、その場合も、ロックは直ちに解放されるので、最初のケースで述べた synchronize_rcu() の間ずっとロックが保持されるケースを除いては、デッドロックサイクルの出現を許さないためです。 ９．５３ これはたしかに、利点です。でも、rcu_dereference() と rcu_assign_pointer() も必要なことを忘れないように。つまり、rcu_dereference() では volatile 操作、rcu_assign_pointer() では、メモリーバリアです。もちろん、アルファCPUの多くは両方のプリミティブでメモリーバリアを必要とします。 ９．５４ そのとおりです。これは、すべての正しいRCU実装でデッドロックします。しかし、rcu_read_lock() は、本当にデッドロックサイクルに寄与していますか？そうだと思うなら、９．３．５．９節のRCU実装を見てから、同じ問題を考えてください。 ９．５５ 更新側のテストはリーダーなしに行われたので、 poll() システムコールは呼ばれていません。 訳注。問いと答えが合ってないみたい。 ９．５６ そうすればたしかに、飢餓を除くことはできますが、それは、rcu_read_lock() がライターを待ってスピンあるいはブロックすることを意味します。一方、ライターはリーダーを待っています。リーダーのどれかが、スピンあるいはブロックしている rcu_read_lock() が持っているロックを取ろうとしたら、またデッドロックになります。 つまり、治療は、病気よりも悪質でした。正しい治療は、９．３．５．４節を参照。

９．５７

スピンロック確保は、そのスピンロックのクリティカルセクションがその確保の前に「漏れ出る」ないことを保証するだけです。それはいかなる意味でも、スピンロック確保の前にあるコードがクリティカルセクションの中にリオーダーされないことを保証するものではありません。そのようなリオーダリングは、RCU保護されたリストからの削除が、rcu_idx をひっくり返した後にリオーダーされることを許すかもしれません。すると、新しく始まったRCUリード側クリティカルセクションが最近削除されたデータ要素を見るということが起きるかもしれません。 読者への課題: Promela/spin のようなツールを使って、図９．４１のメモリバリアの内どれが(もしあるとして)本当に必要かを決定しなさい。それらのツールを使うための情報は、１２章を参照下さい。正しくて完全な最初の回答は、クレジットされます。

９．５８ 両方のフリップが、絶対的に必要です。これを見るために、以下のイベントのシーケンスを考えましょう。 １ 図９．４０の rcu_read_lock() の８行目が、rcu_idx をピックアップし、その値がゼロであることを見つけます。 ２ 図９．４１の synchronize_rcu() の８行目が、rcu_idx の値をひっくり返してその値を1に設定します。 ３ synchronize_rcu() の１０から１３行目は rcu_refcnt[0] の値がゼロであることを見つけます。そのため、戻ります。(質問は、１４から２０行目が無かったら何が起きるかを聞いているのを思い出して下さい。)