１４．１ ロックを避ける
ロックは本番並列環境の働き馬ですが、多くの状況では、ロックなしの技術を使うことで、性能、スケーラビリティ、そしてリアルタイム応答時間を大いに改善できることがあります。５．２節で述べた統計カウンタはそのようなロックなしの技術の特に印象的な例です。そこでは、ロックだけでなく、アトミック操作、メモリバリア、カウンタ加算時のキャッシュミスまでを避けることができました。今まで述べた他の例は、
１ ５章の、多くのそれ以外のカウンティングアルゴリズムを使った高速パス。
２ ６．４．３節の、資源確保キャッシュを使った高速パス。
３ ６．５節の迷路ソルバ。
４ ８章で述べた、データ所有のテクニック。
５ ９章で述べた、参照カウンティングとRCU テクニック。
６ １０章で述べた、参照コードパス。
７ １３章で述べた、多くのテクニック。
つまり、ロックなしテクニックは、とても有効で、たくさん使われています。
しかし、inc_count(), memblock_alloc(), rcu_read_lock() などのような、うまく定義されたAPIの背後に、ロックなしテクニックが隠されているのが最善です。その理由は、規律のないロックなしテクニックの使用は、難しいバグを作る良い方法だからです。
多くのロックなしテクニックの鍵となるコンポーネントは、メモリバリアです。以下の節で説明します。
１４．２ メモリバリア
著者 David Howells and Paul McKenney
因果律と順序性は深く直感的です。そして、ハッカーは一般人よりもずっと強くこの概念を把握していることが多いです。この直感は、ロックやRCUのような、標準的な排他制御を使う、シーケンシャルコード、並列コードのいずれでも、を書き、調べ、デバッグする時のきわめて強力なツールです。
不幸にも、この直感は、共用メモリにあるデータ構造に、直接、明示的なメモリバリアを使うコードの前では、完全に崩壊します。(MMIOレジスタを使うドライバ開発者はご自分の直感にもう少しは信頼を置くことができます。これについては後ほど。)以下の節は、この直感が正確にどこで崩壊するかを示し、あなたがこれらの落とし穴を避ける助けになる、メモリバリアの心のモデルを提唱します。
１４．２．１節は、メモリオーダリングとメモリバリアの簡単な概要を示します。この背景が準備できたら、次のステップはあなたの直感に問題があることをあなたに認めてもらうことです。１４．２．２節はこの苦痛に満ちた作業をします。そこでは、直感的に正しく見えるコード断片が本物のハードウェアの上ではみじめに失敗するのを見ます。そして１４．２．３節で、スカラー変数が同時に複数の値を持つことのできることを示すコードを紹介します。あなたの直感が悲しみの時をくぐり抜けたなら、１４．２．４節はメモリバリアが従う基本的規則を示します。これが私たちが基礎とするものです。１４．２．５節から１４．２．１４節で、この規則をさらに詳細にします。
１４．２．１ メモリオーダリングとメモリバリア
しかし、なぜそもそも、メモリバリアは必要でしょう？CPUは自分で、オーダリングを記録できないのでしょうか？そもそも、私達が計算機を使うのは、ものごとを記録するためでなかったでしょうか？
多くの人々は、たしかに、自分の計算機がものごとを記録するのを期待します。ただ、さらに、記録は高速にされるよう主張します。現代的な計算機システムベンダが直面する困難の一つは、メインメモリはCPUと同歩調で行けないということです。現代的CPUは１つの変数をメモリからフェッチするのに必要な時間の間に、数百の命令を実行できます。このためCPUは、図１４．１が示すように、より大きなキャッシュを活用します。あるCPUがひんぱんに使う変数は、そのCPUのキャッシュに残ることが多いでしょうから、対応するデータに高速なアクセスが出来ます。
不幸にも、CPUが、まだ自分のキャッシュに無いデータをアクセスしたときは、高価な「キャッシュミス」になり、データはメインメモリからフェッチされなくてはいけません。二重に不幸なことに、典型的なコードを実行すると、とても多くのキャッシュミスが起きます。その結果起きる性能低下を制限するために、CPUは、キャッシュミスがデータをメモリからフェッチするのを待つ間、他の命令とメモリ参照を実行するように設計されてきました。これは明らかに、命令とメモリ参照がアウトオブオーダーに実行されることになり、図１４．２の示すような深刻な混乱を起こしかねません。コンパイラと同期プリミティブ（ロックやRCUのような）は、オーダリングの幻想を、「メモリバリア」（例えば、Linuxカーネルでは、 smbmb()）を使って維持する責任があります。これらのメモリバリアは、ARM, POWER, Itanium, そして Alpha でそうであるように、明示的な命令であることも、 x86 でそうであるように、他の命令で暗黙的に決まることもあります。
標準の同期プリミティブは、オーダリングの幻想を維持しますから、あなたの、最も抵抗の少ない道は、この節を読むのをやめて、単にこれらのプリミティブを使うことです。
しかし、もしあなたが、同期プリミティブをご自分で実装しないといけない時、あるいは、あなたが単純にメモリオーダリングとメモリバリアがどのように働くかを理解することに興味があるならば、読み続けましょう！
次の節は、あなたが明示的なメモリバリアを使うときに遭遇するかもしれない、直感に反したシナリオを紹介します。
１４．２．２ もしBがAの後で、CがBの後なら、なぜ、CはAの後でないのですか？
メモリオーダリングと、メモリバリアは極めて直感に反します。例えば、図１４．３の関数が並列に走っていると考えて下さい。変数 A,B, C は最初ゼロです。
直感的には、thread0() は、Aを設定した後、Bを設定します。thread1() は、thread0() がBを設定するまで待ってその後に、Cを設定します。そして、thread2() はthread1() がCを設定するまで待って、その後に、Aを参照します。なので、繰り返しになりますが、直感的には、２１行目のアサーションは発火することはできないはずです。
この推論の連鎖は、直感的には自明かもしれませんが、完全に、全く、誤りです。これは理論的な断定でないことに注意下さい。このコードを実際に、本当の世界のウィークオーダリングのハードウエア(1.5GHz 16-CPU POWER 5 システム)で走らせたところ、1千万回の実行で、アサーションは１６回発火しました。明示的なメモリバリアを使うコードを作成する人は誰でも、かなり極端なテストをするべきなのは明らかです。正しさの証明は役に立つかもしれませんが、メモリバリアの振る舞いの性質はおそろしく直感に反するので、そのような証明への信頼も、かなり限定されるものとなるでしょう。多数の汚いハードウエア依存のトリックが、このテストを失敗させる確率を増すために使われているのを考えると、極端なテストの必要性は軽く考えられるべきではありません。
クイッククイズ１４．４
３５６ページの図１４．３のコードの２１行目のアサーションは、一体全体、失敗するなんてあり得るのですか？
クイッククイズ１４．２
すごい。。。じゃあ、どう直したらいいんですか？
さて、どうしましょう？あなたの最善の戦略、もし可能なら、は、全ての必要なメモリバリアを組み込んだ既存のプリミティブを使うことです。そうすればあなたはこの章の残りは単純に無視できます。
もちろん、あなたが同期プリミティブを実装しているなら、そういう贅沢は言えません。以下のメモリオーダリングとメモリバリアの議論はあなたのためにあります。
１４．２．３ 変数は一つ以上の値を取ることができます
変数は、良く定義されたグローバルなオーダーのもとで、良く定義された値のシーケンスを持つと考えるのは自然です。不幸にも、この手の安らかな物語に「さよなら」を言う時がきました。
これを考えるため、図１４．４に示すプログラム断片を見てください。このコード断片は複数のCPUで並列に実行されます。1行目で共用変数を今のCPUのIDに設定します。２行目は、いくつかの変数を gettb() 関数から初期化します。 それは、全てのCPU同期した、細粒度のハードウエア「タイムベース」カウンタです。(不幸にも、全てのCPUアーキテクチャーに有るわけではありません。)そして、３から８行目のループで、その変数が、このCPUがそれに設定した値のままである時間の長さを記録します。もちろん、CPUの一つが「勝ち」、７と８行目のチェックにかかるまでずっとループを抜けません。
クイッククイズ１４．３
図14.4のコード断片が前提としていることで、実際のハードウエアでは無効かもしれないことは何ですか？
ループから抜けた時、firsttb は、設定のすぐ後に取られたタイムスタンプを保持します。lasttb は、共用変数が、設定された値をまだ持っていた最後のサンプリングの前に取られたタイムスタンプを保持します。あるいは、共用変数が、ループに入る前に変わっていれば、firsttb と同じです。これによって、私達は、図１４．５に示すように、５３２ナノ秒の間にわたって、state.variable の値をそれぞれのCPUが見た結果をプロットすることができます。このデータは、８コアの 1.5GHz POWER5 システムで測定されました。コアのそれぞれは、ハードウエアスレッドを２つ持っています。CPU １，２，３と４が値を記録し、CPU０がテストを制御します。タイムベースカウンタの周期は約 5.32ns なので、途中のキャッシュ状態を観測するのに十分細粒度です。
それぞれの水平な線は、あるCPUの時間を通した観察を表します。左の黒い領域は、そのCPUの最初の測定の前に対応します。最初の 5ns の間、CPU３だけが、この変数の値について意見を持っています。次の10ns の間、CPU２と３は、この変数の値について意見が違います。しかしその後、値が「２」であるとに合意します。それは、実際、最終的に合意された値です。しかし、CPU１は、ほぼ 300ns の間、値は「１」であると信じており、CPU４は、ほぼ 500ns の間、値は「４」であると信じていました。
クイッククイズ１４．４
CPUが、同時に、単一の変数の値に対して異なる意見を持てるのはなぜですか？
クイッククイズ１４．５
CPU１と４が仲間になるのにこんなに時間がかかったのに、CPU２と３は、こんなに速く合意に達したのはなぜですか？
私達は、変数の値と時の流れについての安らかな直感に心からのお別れを告げる必要のある領域に入ったのです。これが、メモリバリアが必要な領域です。
１４．２．４ 何を信用できますか？
あなたがご自分の直感を信用できないのは明らかです。
何を信用できますか？
あなたがうまくメモリバリアを使うための、十分に単純な規則がいくつかあることがわかっています。この節では、その規則を導きだします。これは、メモリバリア物語の底辺にたどり着こうと願う人のためです。少なくともポータブルなコードという視点から。あなたが、ただ、規則を教えられれば良くて、実際にそれを導出する苦悩を望まれないなら、どうぞ、１４．２．６節まで飛ばしてください。
正確なメモリバリアのセマンティックスは、CPUによってワイルドに異なります。なので、ポータブルなコードは、メモリバリアの最小公約数のセマンティックスに依存しなければいけません。
幸運にも、全てのCPUは以下の規則を、強制します。
１ あるCPU の全てのアクセスは、そのCPUにとって、プログラムオーダーで起きたように見えます。
２ 全てのCPUの、単一の変数へのアクセスは、その変数へのストアの何らかのグローバルオーダリングと矛盾しません。
３ メモリバリアは、対になって動作します。
４ 排他ロックプリミティブをそれから構築することのできる操作が提供されます。
なので、あなたがポータブルコードでメモリバリアを使う必要がある時は、これらの性質全てを前提とできます。
脚注
あるいは、それより良いのは、明示的なメモリバリアを全く使わないで良いことですが、それは他の節の主題です。
以下の節で、これらの性質を一つづつ説明しましょう。
１４．２．４．１ 自己参照はオーダーされています
あるCPUは、自分自身のアクセスを、「プログラムオーダー」で起きているように見ます。これは、そのCPUが一度に１つの命令だけを、リオーダリングも推測もなしに実行しているのと同じです。より古いCPUにとっては、この制限は、バイナリ互換性のために必要でした。私たちソフトウェア屋さんの精神的健康のためというのは二次的理由でしかありません。この規則を限られた程度破るCPUもいくつかありましたが、その場合は、コンパイラがオーダリングが必要に応じて明示的に強制されることを保証する責任を持ってきました。
いずれにせよ、プログラマの目から見ると、CPUは自分自身のアクセスをプログラムオーダーで見ます。
１４．２．４．２ 単一変数のメモリ一貫性
現在商用利用可能な計算機システムはキャッシュコヒーレンスを提供します。なので、もし、CPUのグループが全て単一の変数にアトミックでないストアを同時に実行したら、全てのCPUが見る値のシリーズは、少なくても一つのグローバルなオーダリングに矛盾ないはずです。例えば、図１４.５に示したアクセスのシリーズにおいて、CPU１はシーケンス{1,2}, CPU 2 はシーケンス {2}, CPU 3 はシーケンス {3,2}, そして CPU 4 はシーケンス {4,2} を見ます。これは、グローバルなシーケンス {3,1,4,2} と矛盾しませんが、この４つの数字のシーケンスのうち、“2” で終わる、残り５つの全てとも矛盾しません。なので、単一の変数が取った値のシーケンスについての合意はあるでしょうが、あいまいさがあるかもしれません。
それに対して、もしCPUが、一意の値の単純なストアでなく、アトミック操作(Linux カーネルのatomic_inc_return() プリミティブのような)を使っていたら、それらが見るものは、単一のグローバルに一貫した値のシーケンスを決定することが保証されるはずです。atomic_inc_return()の実行の一つが最初に起きて、値を0から1に変えます。二つ目は、1から2に、などです。それぞれのCPUは記録を取っておいて、後から比較すれば、atomic_inc_return()の実行のシーケンスの正確なオーダリングを合意できるはずです。これは前述のアトミックでないストアではうまくいきません。なぜならばアトミックでないストアは以前の値が何であったかについては何も返さないので、あいまいさが生じます。
この節は、全てのCPUのアクセスが、一つの単一の変数に対してであるときにだけ当てはまることによく注意して下さい。この単一の変数の場合、キャッシュコヒーレンスがグローバルなオーダリングを保証します。少なくても、Linux カーネルの ACCESS_ONCE() ディレクティブや、C++11 の relaxed atomic [Bec11] によって、よりアグレッシブなコンパイラ最適化のいくつかが無効にされているのは前提とすればです。それに対して、現在商用利用可能な計算機システムにおいて、複数の変数がある場合には、CPUが順序に関して矛盾ない合意に達するためには、メモリバリアが必要です。
１４．２．４．３ 対となるメモリバリア
対となるメモリバリアは、条件付きオーダリングセマンティクスを提供します。例えば、以下の操作のセットにおいて、CPU１のAへのアクセスは、外部のロジックアナライザの観点からは、そのBへのアクセスに無条件に先行することはありません（付録Cの例を参照下さい）。しかし、もしCPU２のBのへのアクセスがCPU１のBへのアクセスの結果を見たならば、CPU２のAへのアクセスは、CPU１のAへのアクセスの結果を見ることが保証されます。CPUによっては、メモリバリアがより強い、無条件のオーダリング保証を実際に提供することもありますが、ポータブルなコードはこの、より弱い、 if-then 条件付きのオーダリング保証にだけ依存することができます。
クイッククイズ１４．６
でも、もしメモリバリアが無条件にオーダリングを保証しないならば、デバイスドライバは一体全体どうしたら、MMIOレジスタへのロードとストアのシーケンスを安全に実行できるのですか？
もちろん、アクセスはロードかストアのどちらかでなくてはならず、それらは実際に異なる性質を持ちます。表１４．１は、CPUの対に対して、ロードとストアの全ての可能な組み合わせを示します。もちろん、条件付きのオーダリングを強制するためには、それぞれのCPUの操作の対の間にはメモリバリアが必要です。
１４．２．４．４ 対となるメモリバリア：ポータブルな組み合わせ
表１４．１から取った以下の対は、ポータブルなソフトウェアが依存することのできる全てのメモリバリアの対を列挙します。
対１
この対では、一つのCPUはメモリバリアで分割されたロードの対を実行し、二つ目のCPUは同様にメモリバリアで分割されたストアの対を実行します。以下のとおり（AとBはどちらも最初はゼロです）。
両方のCPUがこのコードシーケンスを実行し終わった時、もしも Y==1 ならば、X==1 でなくてはいけません。この場合、Y==1 である事実は、CPU２のメモリバリアの前にあるロードが、CPU１のメモリバリアの後にあるストアを見たことを意味します。これにより、メモリバリアの対となる性質によって、CPU２のメモリバリアの後にあるロードは、CPU１のメモリバリアの前にあるストアを見なくてはいけません。なので、X==1 です。
一方、Y==0 ならば、メモリバリアの条件は満たされないので、この場合、X は０でも１でもかまいません。
対２
この対では、それぞれのCPUはロードをして、次にメモリバリア、そしてストアを実行します。以下のとおり（AとBはどちらも最初はゼロです）。
両方のCPUがこのコードシーケンスを実行し終わった時、もしも X==1 ならば、Y==0 でなくてはいけません。この場合、X==1 である事実は、CPU１のメモリバリアの前にあるロードが、CPU２のメモリバリアの後にあるストアを見たことを意味します。これにより、メモリバリアの対となる性質によって、CPU１のメモリバリアの後にあるストアは、CPU２のメモリバリアの前にあるロードの結果を見なくてはいけません。なので、Y==0 です。
一方、X==0 ならば、メモリバリアの条件は満たされないので、この場合、Y は０でも１でもかまいません。
この二つのCPUのコードシーケンスは対称的です。なので、両方のCPUがこのコードシーケンスを実行し終わった時、もしも Y==1 ならば、X==0 でなくてはいけません。
対３
この対では、一つのCPUはロード、次にメモリバリア、そしてストアを実行します。他のCPUはメモリバリアで分割されたストアの対を実行します。以下のとおり（AとBはどちらも最初はゼロです）。
両方のCPUがこのコードシーケンスを実行し終わった時、もしも X==1 ならば、B==1 でなくてはいけません。この場合、X==1 である事実は、CPU１のメモリバリアの前にあるロードが、CPU２のメモリバリアの後にあるストアを見たことを意味します。メモリバリアの対となる性質によって、CPU１のメモリバリアの後にあるストアは、CPU２のメモリバリアの前にあるストアの結果を見なくてはいけません。ということは、CPU１のBへのストアはCPU２のBへのストアを上書きしますから、B==1 です。
一方、X==0 ならば、メモリバリアの条件は満たされないので、この場合、B は１でも２でもかまいません。
１４．２．４．５ 対となるメモリバリア：半ポータブルな組み合わせ
表１４．１から取った以下の対は、現代的なハードウェアで使うことができます。しかし、１９００年代に製造されたいくつかのシステムでは失敗するかもしれません。しかし、これらは２０００年以降に出荷された全てのメインストリームなハードウェアの上で安全に使うことができます。なので、もしあなたが、メモリバリアは扱うのが難しいとお考えならば、それはシステムによってはかつてはずっと大変だった事に注意下さい！
耳から口
ストアはロードの結果を見ることはできません（繰り返しますが、とりあえず、MMIOレジスタは無視します）から、メモリバリアの条件が満たされたかを決めるのは常に可能とは限りません。しかし、２１世紀のハードウェアは少なくてもロードの一つは、対応するストアが格納した値（あるいはその同じ変数のその後の値）を見ることを保証するでしょう。
クイッククイズ１４．７
耳から口のシナリオの場合、現代的なハードウェアが、少なくてもロードの一つが他のスレッドが格納した値を見ることを保証することをどうやって確認できるでしょう？
「夜にすれ違う」ストア
以下の例で、両方のCPUがそれらのコードシーケンスを実行し終わった時に、{A==1,B==2} という結果は起き得ないと結論付けるのはとても妥当に思えます。
この結論は、２１世紀のシステムでは正しいですが、不幸にも、２０世紀のアンティークシステムの全てで成り立つわけではありません。Aを含むキャッシュラインが最初にCPU２にあり、Bを含むのが最初にCPU１にあったとします。すると、無効化キューとストアバッファを持つシステムでは、最初の代入が「夜にすれ違った」結果、二つ目の代入が実際は最初に起きることがあります。付録Cはこの変な効果を説明しています。
この同じ効果は、それぞれのCPUのメモリバリアの前にストアがある、全てのメモリバリアの対で起きる可能性があります。それには、「耳から口」の対も含みます。
しかし、２１世紀のハードウェアは実際にこのオーダリングの直感を受け入れ、この組み合わせが安全に使われることを許します。
１４．２．４．６ 対となるメモリバリア：あやしい組み合わせ
表１４．１から取った以下の組み合わせにおいては、２１世紀のハードウェアであっても、メモリバリアはポータブルなコードではとても限定された用途しか持ちません。しかし、「限定された用途」は、「使い物にならない」事とは違います。なので、何ができるか見ましょう！熱心な読者は、この組み合わせのそれぞれに依存するおもちゃのプログラムを書いて、これがどのように働くかを完全に理解すると良いでしょう。
耳から耳
ロードはメモリの状態を変えませんから（とりあえず、MMIOレジスタを無視します）ロードの片方がもう一つのロードの結果を見るのは不可能です。しかし、もしCPU2のBからのロードがCPU１のBからのロードよりも新しい値を返したならばCPU２のAからのロードは、CPU１のAからロードと、同じ値か、それより後の値を返すことがわかります。
口から口、耳から耳
変数の一つはロードされるだけで、もう一つは、ストアされるだけです。ロードが、他のロードの結果を見るのは不可能ですから（繰り返しますが、MMIOレジスタを無視します）メモリバリアが提供する条件付きのオーダリングを検出することはできません。
しかし、どちらのストアが最後に起きたかを決めることはできます。でもそれには、Bからのもう一つのロードが必要です。この追加のBからのロードがCPU１と２の両方が完了してから実行され、そしてCPU２のBへのストアが最後に起きたことがわかった場合、CPU２のAからのロードは、CPU１のAからのロードと同じ値か、それより後の値を返すことがわかります。
ストアが一つだけ
ストアが一つだけなので、変数の一つだけが、あるCPUが他のCPUのアクセスの結果を見ることを許します。なので、メモリバリアが提供する条件付きのオーダリングを検出することはできません。
しかし、表１４．１の組み合わせ１において、CPU１のAからのロードが、CPU２がAへストアした値を返すとします。その場合、CPU１のBからのロードは、CPU２のBからのロードと同じ値か、それより後の値を返すことがわかります。
訳注。原文は、Aからのロードだが、誤りです。
クイッククイズ１４．８
表１４．１の、他の「ストアが一つだけ」のエントリは、どのように使うことができますか？
１４．２．４．７ ロックを実装するために十分なセマンティクス
いくつかの変数を守る排他ロック（Linuxカーネルの spinlock_t、pthread コードのpthread_ mutex_t）があるとします(言葉を代えて言えば、これらの変数は、ロックのクリティカルセクション以外ではアクセスされません)。この時、以下の性質が真でなくてはいけません。
１ あるCPUあるいはスレッドは、自分自身の全てのロードとストアをそれらがプログラムオーダーで起きたかのように見なければいけません。
２ ロック確保と解放は、単一のグローバルオーダーで実行されたかのように見えなければいけません。
脚注
もちろん、このオーダーは、実行ごとに違うかもしれません。しかし、いかなる実行においても、全てのCPUとスレッドはある排他ロックのクリティカルセクションのオーダーに関して、矛盾しないビューを持たなくてはいけません。
３ もし、現在実行中のクリティカルセクションの中で、ある変数がまだストアされていないとします。それなら、そのクリティカルセクションにおけるその変数から行われる全てのロードは、それをストアした最後の以前のクリティカルセクションにおけるその変数への最後のストアを見なければいけません。
最後の二つの性質の違いは少し微妙です。二つ目は、ロック確保と解放が良く定義されたオーダーで起きる事を要求します。そして三つ目は、クリティカルセクションが遠くまで「浸み出して」他のクリティカルセクションで問題を起こすことがない事を要求します。
これらの性質は、なぜ必要でしょう？
最初の性質が満たされないとします。すると、以下のコードのアサーションが実際に失敗する事があります！
a = 1;
b = 1 + a;
assert(b == 2);
クイッククイズ１４．９
３６３ページのb==2 のアサーションが失敗するなんて、どうしたら可能でしょう？
二つ目の性質が満たされないとします。すると、以下のコードはメモリをリークする事があります！
spin_lock(&mylock);
if (p == NULL)
p = kmalloc(sizeof(*p), GFP_KERNEL);
spin_unlock(&mylock);
クイッククイズ１４．１０
３６３ページのコードがメモリをリークするなんて、どうしたら可能でしょう？
三つ目の性質が満たされないとします。すると、以下のコードに示すカウンタは、逆にカウントする事があります。この三つ目の性質はとても重要です。これは、厳密にはメモリバリアの対では対処できないからです。
spin_lock(&mylock);
ctr = ctr + 1;
spin_unlock(&mylock);
クイッククイズ１４．１１
３６３ページのコードが逆にカウントするなんて、どうしたら可能でしょう？
もしあなたが、これらの規則が必要だと確信できたら、それらが典型的なロック実装とどのように関係するかを調べましょう。
１４．２．５ ロック実装のレビュー
以下に、単純なロックとアンロック操作のナイーブな擬似コードを示します。atomic_xchg() プリミティブは、アトミック交換操作の前と後の両方に暗黙のメモリバリアを意味することに注意下さい。また、アトミック交換操作の後の暗黙のバリアは spin_lock() での明示的なメモリバリアを不必要にします。また、名前とは違って、atomic_read() と atomic_set() はアトミック命令を何も実行せず、その代わりにそれぞれ、単純なロードとストアを実行することにも注意下さい。この擬似コードは、アンロック操作の Linux におけるいくつかの実装にもとづきます。それは、メモリバリアに続く、単純なアトミックでないストアです。これらの最小の実装は、１４．２．４節で列挙した全てのロックの性質を持たなくてはいけません。
spin_lock() プリミティブは、その前の spin_unlock() プリミティブが完了するまで進めません。CPU１が、CPU２が確保しようとしているロックを放した時、操作のシーケンスはこのようになるでしょう。
この特別の場合、対となるメモリバリアが、二つのクリティカルセクションを正しく置くのに十分です。CPU２の atomic_xchg(&lck->a, 1) は、CPU１の lck->a=0 を見ました。なので、CPU2以下のクリティカルセクションの全てのものは、CPU１が以前のクリティカルセクションが行なった全てのことを見なければいけません。逆に、CPU１のクリティカルセクションは、CPU２のクリティカルセクションがするであろうことを何も見ることはできません。
１４．２．６ 単純な規則をいくつか
多分、メモリバリアを理解する最も簡単な方法は、単純な規則をいくつか理解することです。
１ それぞれのCPUは、自分自身のアクセスを順序どおりに見ます。
２ もし単一の共用された変数が複数CPUによってロードとストアされたら、あるCPUが見る値のシリーズは、他のCPUが見るシリーズと矛盾がありません。そして、その変数にストアされた全ての値からなる少なくても一つのシーケンスがあり、それはそれぞれのCPUのシリーズと矛盾しません。
脚注
あるCPUのシリーズはもちろん、不完全かもしれません。例えば、あるCPUがその共用された変数をロードもストアもしないならば、それはその変数の値について何の意見も持つことはできません。
３ もし一つのCPUが変数 A と B にオーダードストアをして、二つ目のCPUが B と A からオーダードロードをしたとします。
脚注
例えば、A へのストアを実行、メモリバリア、そして B へのストア。
例えば、B からのロード、メモリバリア、そして A からのロード。
そして、もし二つ目のCPUのB からのロードが最初のCPUがストアした値を得るなら、二つ目のCPUがAからロードするときは、最初のCPUがストアした値を得なければいけません。
４ もしあるCPUがBへのストアの前にオーダーされるAからのロードをして、二つ目のCPUがAへのストアの前にオーダーされるBからのロードをしたとします。そして、もし二つ目のCPUのBからのロードが最初のCPUによってストアされた値を得るなら、最初のCPUのAからのロードは二つ目のCPUによってストアされた値を得てはいけません。
５ もしあるCPUがBへのストアの前にオーダーされるAからのロードをして、二つ目のCPUがAへのストアの前にオーダーされるBへのストアをしたとします。そして、もし最初のCPUのAからのロードが二つ目のCPUによってストアされた値を得るなら、最初のCPUのBからのへのストアは二つ目のCPUのBへのストアの後に起きなくてはいけません。つまり、最初のCPUのストアした値が残ります。
脚注
あるいは、より競争が好きな人のために言うなら、最初のCPUのBへのへのストアが「勝ちます」。
次の節は、これらの規則のより操作的な見方を考えます。
１４．２．７ 抽象メモリアクセスモデル
図１４.６に示すシステムの抽象モデルを考えましょう。
それぞれのCPUはメモリアクセス操作を生成するプログラムを実行します。抽象CPUでは、メモリ操作のオーダーはとても緩やかで、CPUは実際に、プログラムの因果律が維持されているように見える限り、自分の好きな任意のオーダーでメモリ操作を実行する事があります。同様に、コンパイラは、プログラムの明白な操作に影響しない限り、生成する命令を自分の好きな任意のオーダーで配置する事があります。
なので、上図において、CPUが行うメモリ操作の効果は、その操作がCPUとシステムの残りの部分とのインタフェース(点線)を越える時に、システムの残りの部分によって検出されます。
例えば、初期値が {A = 1, B = 2} の時に、以下のイベントのシーケンスを考えましょう。
中間にあるメモリシステムから見えるアクセスのセットは、２４の異なる組み合わせに並べる事ができます。ロードは "ld" で、ストアは "st" で示します。
その結果、4つの異なる値の組み合わせになる可能性があります。
さらに、あるCPUがメモリシステムにコミットしたストアは、他のCPUが行うロードにおいて、ストアがコミットされたのと同じオーダーで検出されない事があります。
もう一つの例として、初期値が {A = 1, B = 2, C = 3, P = &A, Q = &C} の時に、以下のイベントのシーケンスを考えましょう。
ここには明らかなデータ依存があります。D にロードされる値は、CPU２が P から得たアドレスに依存するからです。このシーケンスの終わりでは、以下の結果の全てが可能です。
CPU２が C を D にロードしようとは決してしない事に注意下さい。CPU は、*Q のロードを発行する前に、P を Q にロードするからです。
１４．２．８ デバイス操作
制御インタフェースを、メモリ位置の集まりとして提供するデバイスがあります。しかし、その制御レジスタをアクセスするオーダーはとても重要です。例えば、アドレスポートレジスタ(A) とデータポートレジスタ (B) を経由してアクセスされる内部的なレジスタのセットを持つイーサネットカードを想像してください。内部的なレジスタ５を読むには、以下のコードが使われるでしょう。
*A = 5;
x = *D;
しかし、これは、以下の二つのシーケンスのどちらかになるでしょう。
STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5
二つ目の方は、ほぼ確実に誤動作になるでしょう。それはアドレスをレジスタを読もうとする後に設定しますから。
１４．２．９ 保証
CPUに期待できる最低限の保証がいくつかあります。
１ どのCPUにおいても、依存するメモリアクセスは、自分自身から見てオーダーを守って発行されます。ということは、
Q = P; D = *Q;
に対してCPUは以下のメモリ操作を発行します。
Q = LOAD P, D = LOAD *Q
これは常にこのオーダーです。
２ 特定のCPU内でのオーバラップするロードとストアは、そのCPU内ではオーダーされているように見えます。ということは、
a = *X; *X = b;
に対してCPUは以下のメモリ操作のシーケンスを発行するだけです。
a = LOAD *X, STORE *X = b
そして、
*X = c; d = *X;
に対しては、CPUは以下を発行するだけです。
STORE *X = c, d = LOAD *X
(ロードとストアは、それらがオーバラップするメモリの部分を対象とするときオーバラップします。)
３ 単一の変数へのストアのシリーズは、全てのCPUにとって、単一のオーダーで起きたかのように見えます。ただ、このオーダーはコードから予見することはできないかもしれず、実際、オーダーは実行ごとに変わるかもしれません。
そして、前提としなくてはいけないこと、前提としてはいけないことが、いくつかあります。
１ 独立したロードとストアは、指定されたオーダーで発行されることを前提としてはいけません。ということは、これに対して、
X = *A; Y = *B; *D = Z;
以下のシーケンスのどれでもが起きることがあります。
X = LOAD *A, Y = LOAD *B, STORE *D = Z
X = LOAD *A, STORE *D = Z, Y = LOAD *B
Y = LOAD *B, X = LOAD *A, STORE *D = Z
Y = LOAD *B, STORE *D = Z, X = LOAD *A
STORE *D = Z, X = LOAD *A, Y = LOAD *B
STORE *D = Z, Y = LOAD *B, X = LOAD *A
２ オーバラップするメモリアクセスはマージあるいは破棄されることがあることを前提としなくてはいけません。ということは、これに対して、
X = *A; Y = *(A + 4);
以下のシーケンスののどれでもが起きることがあります。
X = LOAD *A; Y = LOAD *(A + 4);
Y = LOAD *(A + 4); X = LOAD *A;
{X, Y} = LOAD {*A, *(A + 4) };
そしてこれに対して、
*A = X; Y = *A;
このどれもが起きます。
STORE *A = X; STORE *(A + 4) = Y;
STORE *(A + 4) = Y; STORE *A = X;
STORE {*A, *(A + 4) } = {X, Y};
最後に、これに対して、
*A = X; *A = Y;
このどちらもが起きます。
STORE *A = X; STORE *A = Y;
STORE *A = Y;
１４．２．１０ メモリバリアとはなんですか
以上のことからわかるように、独立したメモリ操作は、実効的にはランダムなオーダーで行われます。しかしこれは、CPUとCPUの相互作用、あるいは I/Oにとって問題となることがあります。ここで必要となるのは、コンパイラとCPUにオーダーを制限するように、介入して命令するための何らかの方法です。
メモリバリアはそのような介入です。それは、バリアの両側のメモリ操作に対して、感知できる部分的オーダリングを強制します。
CPUとシステムのそれ以外のデバイスは、性能を上げるためにいろいろなトリックを使うことがありますから、前記強制は重要です。トリックには、リオーダリング、メモリ操作の遅延と結合、投機的ロード、投機的分岐予測に、多くのタイプのキャッシュが含まれます。メモリバリアはこれらのトリックを上書きあるいは抑止するために使われ、コードが複数CPUそしてあるいはデバイスの相互作用を健全に制御するのを可能とします。
１４．２．１０．１ 明示的メモリバリア
メモリバリアには4つの基本的な変種があります。
１ ライト(あるいはストア)メモリバリア
２ データ依存バリア
３ リード(あるいはロード)メモリバリア
４ 一般的メモリバリア
以下にそれぞれの変種を説明します。
ライトメモリバリア
ライトメモリバリアは、システムの他のコンポーネントから見て、バリアの前に指定された全てのSTORE操作が、バリアの後に指定された全てのSTOREの前に起きたかのように見えることを保証します。
ライトバリアはストアだけに対する部分的オーダリングです。ロードに対して何の影響も持つ必要はありません。
CPUは、時間が経過するにつれてメモリシステムにストア操作のシーケンスをコミットするものと見ることができます。ライトバリアの前の全てのストアはそのシーケンスの中で、ライトバリアの後の全てのストアより先に起きます。
ライトバリアは通常は、リードあるいはデータ依存バリアと対になるべきです。「SMPバリアの対」の節を参照下さい。
データ依存バリア
データ依存バリアは、リードバリアのより弱い形です。二つのロードが実行されて、二つ目が最初の結果に依存するとき(例えば、最初のロードが、二つ目のロードが向かうべきアドレスを得る)、データ依存バリアが必要です。それは、最初のロードによって得られたアドレスがアクセスされる前に、二つ目のロードの対象が更新されることを保証します。
データ依存バリアは、相互に依存するロードだけに対する部分的オーダリングです。それは、ストア、独立したロード、あるいはオーバラップするロードに対して何の影響も持つ必要はありません。
ライトメモリバリアについて述べたように、システムの他のCPUは、メモリシステムにストアのシーケンスをコミットするものと見ることができます。これをこのCPUが感知することができます。このCPUが発行するデータ依存バリアは、その前にある全てのロードが、もしそのロードが他のCPUのストアのシーケンスの一つを触るならば、バリアが完了する前に、そのロードが触るストアの前の全てのストアの効果は、データ依存バリアの後に発行された全てのロードから感知することができることを保証します。
オーダリング制約を示した図については、「メモリバリアのシーケンスの例」の節を参照下さい。
最初のロードは実際、制御依存ではなくて、データ依存を持たないといけないことに注意下さい。もし二つ目のロードのためのアドレスが最初のロードに依存しており、しかし依存関係が、実際にアドレス自身をロードすることでなくて条件によるのであれば、それは制御依存であって、完全なリードバリア以上のものが必要です。詳しくは、「制御依存」の節を参照下さい。
データ依存バリアは通常は、ライトバリアと対になるべきです。「SMPバリアの対」の節を参照下さい。
リードメモリバリア
リードバリアは、データ依存バリアであり、さらに、システムの他のコンポーネントから見て、バリアの前に指定された全てのLOAD操作が、バリアの後に指定された全てのLOAD操作の前に起きたかのように見えることを保証します。
リードバリアはロードだけに対する部分的オーダリングです。ストアに対して何の影響も持つ必要はありません。
リードメモリバリアはデータ依存バリアを暗黙的に意味します。なので、その代わりとして使うことができます。
リードバリアは通常は、ライトバリアと対になるべきです。「SMPバリアの対」の節を参照下さい。
一般的メモリバリア
一般的メモリバリアは、システムの他のコンポーネントから見て、バリアの前に指定された全てのLOADとSTORE操作が、バリアの後に指定された全てのLOADとSTORE操作の前に起きたかのように見えることを保証します。
一般的メモリバリアはロードとストアの両方に対する部分的オーダリングです。
一般的メモリバリアはリードとライトメモリバリアの両方を暗黙的に意味します。なので、その代わりとして使うことができます。
１４．２．１０．２ 暗黙のメモリバリア
暗黙のメモリバリアのタイプがいくつかあります。それらがロックプリミティブに埋め込まれているためにそう呼ばれます。
１ LOCK 操作と
２ UNLOCK 操作
LOCK 操作
ロック操作は、一方通行の浸透性バリアとしてはたらきます。それは、システムの他のコンポーネントから見て、LOCK 操作の後の全てのメモリ操作が、LOCK 操作の後に起きたように見えることを保証します。
LOCK 操作の前に起きたメモリ操作が、LOCK 操作が完了した後に起きたように見えることがあります。
LOCK 操作はほぼ常に、UNLOCK操作と対になるべきです。
UNLOCK 操作
アンロック操作も、一方通行の浸透性バリアとしてはたらきます。それは、システムの他のコンポーネントから見て、UNLOCK 操作の前の全てのメモリ操作が、UNLOCK 操作の前に起きたように見えることを保証します。
UNLOCK 操作の後に起きたメモリ操作が、UNLOCK 操作が完了する前に起きたように見えることがあります。
LOCK と UNLOCK 操作は、互いにとって、厳密に指定された順序で見えることが保証されています。
LOCK と UNLOCK 操作を使えば、通常は他のメモリバリアの類を使う必要はありません（ただし、「MMIO ライトバリア」節に書いた例外に注意下さい）。
クイッククイズ１４．１２
以下のシーケンスは、変数 “a” と “b”へのストアに対して、どんな影響を持ちますか？
a = 1;
b = 1;
<write barrier>
１４．２．１０．３ メモリバリアについて期待してはいけないことは何ですか？
特定のアーキテクチャの囲いの外で、メモリバリアが保証できないことがいくつかあります。
メモリバリア命令が完了するまでに、そのメモリバリアの前に指定された何らかのメモリアクセスが完了する保証はありません。バリアは、そのCPUのアクセスキューに、線を引くものと考えられます。その線を、特定のアクセスのタイプは越えることができません。
一つのCPUでメモリバリアを発行することが、他のCPUあるいはそのシステムの他のハードウェアに何らかの直接の影響を与える保証はありません。間接的な影響は、二つ目のCPUが、最初のCPUのアクセスが起きたことの影響を見る順序でしょう。しかし、次項を参照。
あるCPUが二つ目のCPUのアクセスによる影響の正しい順序を見る保証はありません。二つ目のCPUがメモリバリアを使っても同じです。最初のCPUも対応するメモリバリアを使わない限り(「SMPバリアの対」の節を参照下さい。)。
CPUの外にあるハードウェアの何らかの干渉する部品がメモリアクセスをリオーダーしない保証はありません。
脚注
これは主に、オペレーティングシステムカーネルの心配事です。ハードウェア操作とメモリオーダリングについて詳しくは、Linuxソースツリーの Documentation ディレクトリにある pci.txt, DMA-API-HOWTO.txt と DMA-API.txt ファイルを参照下さい。
CPUキャッシュのコヒーレンシー機構は、CPU間でメモリバリアの間接的な影響を伝搬するはずです。しかしそれを順序通りにしないかもしれません。
１４.２.１０.４ データ依存バリア
データ依存バリアを使わなくてはいけない場合というのは少しわかりにくく、それが必要かどうかは必ずしも常に明確ではありません。説明のために、以下のイベントのシーケンスを考えましょう。初期値は {A = 1, B = 2, C = 3, P = &A, Q = &C} です。
ここには明確なデータ依存があります。そして、シーケンスの終わりでは、Qが&A あるいは &B でなくてはならず、以下が成り立つことは直感的に自明と思われるかもしれません。
(Q == &A) implies (D == 1)
(Q == &B) implies (D == 4)
直感に反するかもしれませんが、CPU2 の Pの感知が、それがBを感知する前に更新されることは十分にあり得るのです。なので以下の状況になります。
(Q == &B) and (D == 2) ????
これはコヒーレンスあるいは因果律の維持に失敗したように見えるかもしれませんが、違います。そしてこのふるまいはある種の本物のCPU(DEC Alpha のような)で観察できます。
これに対処するために、アドレスのロードとデータのロードの間にデータ依存バリアを入れないといけません。(初期値は同じく、 {A = 1, B = 2, C = 3, P = &A, Q = &C} です。)
これが、前記二つの例のどちらかが起きることを強制し、三つ目の可能性が起きるのを防ぎます。
スプリットキャッシュを持つシステムでは、極端に直感に反する状況が最も簡単に起きることに注意下さい。その場合例えば、一つのキャッシュバンクは偶数のキャッシュラインを処理し、他のバンクは奇数のキャッシュラインを処理します。ポインタPは奇数のキャッシュラインに格納され、変数Bは偶数のキャッシュラインに格納されます。そこでもし、リードしているCPUのキャッシュの偶数バンクがとても忙しく、一方奇数バンクは暇なら、ポインタPの新しい値(それは&Bです)と、一方、変数Bは古い値（それは１）が見えるかもしれません。
データ依存バリアが必要とされるかもしれない場合のもう一つの例は、数字をメモリから読んで、それを配列のインデックス計算に使う時です。初期値を {M[0] = 1, M[1] = 2, M[3] = 3, P = 0, Q = 3} とします。
データ依存バリアは、LinuxカーネルのRCUシステムにとってとても重要です。例えば、include/linux/rcupdate.h の rcu_dereference() を見て下さい。これにより、RCU対象のポインタの現在のターゲットを、新しい変更されたターゲットと交換するときに、変更されたターゲットが不完全に初期化されて見えることを防ぎます。
１４．２．１３．１節の例も参照下さい。
１４.２.１０.５ 制御依存
制御依存が正しく働くためには、単純にデータ依存バリアがあるのではだめで、完全なリードメモリバリアが必要です。以下のコード断片を見ましょう。
1 q = &a;
2 if (p)
3 q = &b;
4 <data dependency barrier>
5 x = *q;
実際のデータ依存はないので、これは期待通りの効果を持ちません。そうでなくこれは制御依存です。CPUは結果を事前に予言して近道を取ろうとするかもしれません。この場合、実際に必要なのは以下です。
1 q = &a;
2 if (p)
3 q = &b;
4 <read barrier>
5 x = *q;
１４．２．１０．６ SMPバリアの対
CPUーCPUの相互作用を扱うとき、ある種のメモリバリアは常に対にして使うべきです。正しい対がないことは、ほぼ必ず誤りです。
ライトバリアは常に、データ依存バリアあるいはリードバリアと対になるべきです。なお一般的バリアでも良いです。同様に、リードバリアあるいはデータ依存バリアは常に、少なくともライトバリアと対になるべきです。なお、繰り返しますが、一般的バリアでも良いです。
いずれにしても、リードバリアは常に存在しなくてはいけません。より弱い型のものであってもです。
脚注
「弱い」とは、「オーダリングの保証がより少ない」の意味です。弱いバリアは通常は、強いバリアよりもオーバヘッドも低いです。
なお、ライトバリアの前のストアは通常は、リードバリアあるいはデータ依存バリアの後のロードに対応付くことが期待されるのに注意下さい。逆も同じです。
１４．２．１０．７ メモリバリア対の例
まず、ライトバリアはストア操作の部分的オーダリングとしてはたらきます。以下のイベントのシーケンスを考えましょう。
このイベントのシーケンスはメモリシステムに以下のオーダーでコミットされ、システムの残りの部分から感知されます。図１４.７に示すように、順序のない {A=1,B=2,C=3} のセット、それが全て、順序のない {D=4,E=5} のセットの前に起きます。
次に、データ依存バリアはデータ依存するロードの間の部分的オーダリングとしてはたらきます。初期値が {B = 7, X = 9, Y = 8, C = &Y} の以下のイベントのシーケンスを考えましょう。
介入なしでは、図１４．８に示すように、CPU２は、CPU1のイベントを、何らかの実効的にランダムなオーダーで感知するかもしれません。CPU１がライトバリアを発行してもです。
上の例では、CPU2は、Bが7だと思います。*C(それはＢのはずです)が、C の LOADの後に来てもです。
でもしかし、CPU2において、データ依存バリアがCのロードと*C(つまりＢ)の間に置かれたとします。初期値は同様に {B = 7, X = 9, Y = 8, C = &Y} です。
するとオーダリングは図１４.9に示すように、直感で期待されるものとなります。
そして3つ目、リードバリアはロードに対して部分的オーダリングとしてはたらきます。初期値が {A = 0, B = 9} の以下のイベントのシーケンスを考えましょう。
介入なしでは、図１４．１０に示すように、CPU２は、CPU1のイベントを、何らかの実効的にランダムなオーダーで感知するかもしれません。CPU１がライトバリアを発行してもです。
でもしかし、CPU2において、リードバリアがＢのロードとのAのロードの間に置かれたとします。初期値は同様に {A = 0, B = 9} です。
すると、図１４.１１に示すように、CPU1のライトバリアによって強制された部分的オーダリングは、CPU2によって正しく感知されます。
これをもっと完全に示すために、コードがリードバリアの両側にAのロードを持っていたら何が起きるか考えましょう。初期化は同じで、{A = 0, B = 9} です。
二つのAのロードはどちらもＢのロードの後に起きますが、図１４.１２が示すように異なる値になってくることがあります。
もちろん、図１４.１３に示すように、CPU1のAへの更新が、リードバリアが完了する前にCPU2から見えることも十分にありえます。
保証されるのは、もしBのロードが B == 2 になるなら、二つ目のロードは必ず、 A == 1 になることです。最初のA のロードにはそのような保証は何もありません。A == 1 にもA == 2 にもなります。
１４．２．１０．８ リードメモリバリア対ロード投機
多くのCPUはロードを投機します。つまり、CPUは、将来何かをメモリからロードする必要があるとわかったら、他のロードのためにバスを使っていない時を見つけて、それを事前にロードします。命令実行フローの上で、まだその時点に達していないとしてもです。後になって、これは実際のロード命令を即座に完了できるようにする潜在的効果があります。CPUはその値をすでに持っていますから。
CPUがその値を実際には必要としないことがわかることもあります(多分、分岐がロードを無効としたからかもしれません)。その場合はCPUはその値を捨てることもできますし、後で使うために単にキャッシュすることもできます。例えば、以下を考えましょう。
CPUによっては、割り算命令は長くかかることがあります。ということは、CPU2のバスはその間アイドルになることを意味します。なのでCPU2は割り算が終わらないうちにAを投機的にロードするかもしれません。割る数の一つが例外を起こすという(できれば)まれな場合には、この投機的ロードはむだになるでしょう。しかし、(繰り返しますが、できれば)一般的な場合には、図１４.１４が示すように、ロードを割り算とオーバラップすることは、ロードがより速く完了するのを可能とします。
二つ目のロードのすぐ前にリードバリアあるいはデータ依存バリアを置くと、投機的に得られた全ての値は、使われたバリアの型に依存する程度、再考慮されます。投機されたメモリ位置に変更がされていないときは、図１４.１５に示すように、投機された値は単純に使われます。そうでなく、どれか他のCPUから、Aの更新あるいは無効化があった場合、図１４.１６の示すように、投機はキャンセルされ、A の値は再ロードされます。
１４．２．１１ ロックの制約
前に述べたようにロックプリミティブは暗黙のメモリバリアを含みます。この暗黙のメモリバリアは以下の保証を提供します。
１ LOCK操作の保証
LOCKの後に発行されたメモリ操作は、LOCK操作が完了してから完了します。
LOCKの前に発行されたメモリ操作は、LOCK操作が完了してから完了することがあります。
２ UNLOCK操作の保証
UNLOCKの前に発行されたメモリ操作は、UNLOCK操作が完了する前に完了します。
UNLOCKの後に発行されたメモリ操作は、UNLOCK操作が完了する前に完了することがあります。
３ LOCK 対 LOCKの保証
ある LOCK 操作の前に発行された全ての LOCK 操作はそのLOCK操作の前に完了します。
４ LOCK 対 UNLOCKの保証
あるUNLOCK操作の前に発行された全てのLOCK操作はそのUNLOCK操作の前に完了します。
あるLOCK操作の前に発行された全てのUNLOCK操作は、そのLOCK操作の前に完了します。
５ 失敗した条件付きLOCKの保証
LOCKの変種には、失敗するものがあります。すぐにロックが取れなかった場合や、ロックが空くのを待って眠っている間に、ブロックされないシグナルや、例外を受けた場合です。失敗したロックはいかなる種類のバリアも伴いません。
１４．２．１２ メモリバリアの例
１４．２．１２．１ ロックの例
LOCKの次にUNLOCK
LOCKの次にUNLOCKが来るのは、完全なメモリバリアと思ってはいけません。LOCKの前のアクセスがLOCKの後に起き、UNLOCKの後のアクセスがUNLOCKの前に起きることが可能だからです。そして二つのアクセス自身も交差することがあります。例えば以下の、
1 *A = a;
2 LOCK
3 UNLOCK
4 *B = b;
が以下の順に実行されるのは十分ありえます。
2 LOCK
4 *B = b;
1 *A = a;
3 UNLOCK
繰り返しますが、LOCKとUNLOCKは、以前の操作がクリティカルセクションに「浸み込んで」来るのを許します。
クイッククイズ １４.１３
LOCK-UNLOCK 操作のどんなシーケンスならば、完全なメモリバリアとして動作しますか？
クイッククイズ １４.１４
このような半浸透性のロックプリミティブを構成することができるメモリバリア命令を持つCPUとは(もしあるなら)どのようなものですか？
LOCK を元とするクリティカルセクション
LOCK-UNLOCK の対は完全なメモリバリアとしてははたらきませんが、これらの操作は実際にメモリオーダリングに影響を与えます。
以下のコードを考えましょう。
1 *A = a;
2 *B = b;
3 LOCK
4 *C = c;
5 *D = d;
6 UNLOCK
7 *E = e;
8 *F = f;
これは、合法的に以下のオーダーで実行することができます。同じ行にある操作の対は、CPUがこれらの操作を同時に実行することを示します。
3 LOCK
1 *A = a; *F = f;
7 *E = e;
4 *C = c; *D = d;
2 *B = b;
6 UNLOCK
クイッククイズ １４．１５
表１４．２において、大カッコでグループになっている操作は同時実行するとしたら、変数「A」から「F」への代入と、LOCK／UNLOCK 操作に対するリオーダリングで合法なのはどの行でしょう？（コードのオーダリングは、A, B, LOCK, C, D, UNLOCK, E, F です。）なぜですか？なぜいけませんか？
複数のロックがある時のオーダリング
複数のロックを持つコードもそれらのロックによるオーダリングの制約を受けますが、どのロックがどれなのかをよく区別しないといけません。例えば、表１４．３に示すコードを考えましょう。これは「M]と「Q」と名付けられるロックの対を使います。
この例では、「A」から「H」までの変数への代入がどのようなオーダーで起きるか、前の節で述べたロック自身が課する制約以外には何も保証はありません。
クイッククイズ１４．１６
表１４．３にある制約は何ですか？
一つのロックを複数のCPUが取る時のオーダリング
表１４．３の２つの異なるロックの代わりに、表１４．４に示すように、両方のCPUが同じロックを取る場合を考えましょう。
この場合、CPU１は、CPU２より前に M を確保するか、その逆かです。最初の場合、A,B,C への代入はF,G,H への代入よりも前にないといけません。一方、CPU２が先にロックを取ったならば、E,F,G への代入はB,C,D への代入よりも前にないといけません。
１４．２．１３ CPUキャッシュの効果
メモリ操作の感知されるオーダリングは、CPUとメモリの間にあるキャッシュに影響されます。また、メモリのコンシステンシーとオーダリングを維持するキャッシュコヒーレンスプロトコルにも影響されます。ソフトウェアの観点からは、これらのキャッシュは全ての意図と目的において、メモリの一部です。メモリバリアは図１４.１７の垂直の点線に対して動作していると考えることができ、CPUが自分の値をメモリに正しい順序で提供することを保証します。また、CPUが他のCPUの行った変更を正しい順序で見ることも保証します。
キャッシュはあるCPUのメモリアクセスをシステムの残りの部分から「隠す」ことがあります。しかし、キャッシュコヒーレンスプロトコルが、他の全てのCPUがこの隠れたアクセスの全ての影響を見ることを保証します。必要に応じて、キャッシュラインを移動、無効化します。さらに、CPUコアは任意の順番で命令を実行するかもしれません。プログラムの因果律とメモリオーダリングが維持されているように見えるべきだという要求だけに制約されます。命令によっては、そのCPUのメモリアクセスキューにキューイングされる必要のあるメモリアクセスを生成するかもしれません。しかし実行はそれでも続行することができます。そのCPUが自分の内部資源を使い尽くすか、CPUがキューイングされたメモリアクセスのどれかが完了するのを待つ必要があるまで。
１４．２．１３．１ キャッシュコヒーレンシー
キャッシュコヒーレンスプロトコルは、あるCPUが自分自身のアクセスを順に見たり、単一のキャッシュラインに含まれる単一の変数への変更の順序を全てのCPUが合意することを保証しますが、異なる変数への変更が全てのCPUで同じ順に見えることの保証はありません。計算機システムによってはそのような保証をある程度は実際にするものもありますが、ポータブルなソフトウェアはそれに頼ってはいけません。
なぜリオーダリングが起きるかを考えるために、図１４.１８に示す二つのCPUのあるシステムを考えましょう。それぞれのCPUはスプリットキャッシュを持ちます。このシステムは以下の性質を持ちます。
１ 奇数のキャッシュラインは、キャッシュA、キャッシュC、メモリにあります。あるいはそれらの組み合わせ。
２ 偶数のキャッシュラインは、キャッシュB、キャッシュD、メモリにあります。あるいはそれらの組み合わせ。
３ CPUコアがそのキャッシュの一つに問い合わせをしている間、そのもう一つのキャッシュは静かにしている必要はありません。そのキャッシュは、無効化要求に応えていたり、ダーティキャッシュラインを書き戻していたり、CPUのメモリアクセスキューの要素を処理していたり、などをしているかもしれません。
脚注
でも、「スーパースカラー」システムでは、CPUは自分のキャッシュの両方の半分を同時にアクセスしていることも十分ありえます。そして実際にそれら半分に複数の同時実行アクセスをするかもしれません。
４ キャッシュのそれぞれは、キャッシュに適用される必要のある操作のキューを持ちます。それは、必要とされるコヒーレンスとオーダリングの性質を維持するためです。
５ これらのキューのエントリが影響するキャッシュラインがロードあるいはストアされても、キューは必ずしもフラッシュされません。
短く言うと、もしキャッシュAがビジーでキャッシュBがアイドルの時、CPU１の奇数のキャッシュラインへのストアは、CPU１の偶数のキャッシュラインへのストアに比べて遅れることがあります。
訳注。原文では、CPU2ですが誤り。
それほど極端な場合を考えなくても、CPU2はCPU１の操作をアウトオブオーダーで見ることはあるでしょう。
ハードウェアとソフトウェアのメモリオーダリングについてより詳しくは、付録Cにあります。
１４．２．１４ メモリバリアはどこで必要ですか？
メモリバリアは、二つのCPUの間あるいは、CPUとデバイスの間に相互作用の可能性があるときにだけ必要です。もし、どのコード部分にも、そのような相互作用がないことが保証できるなら、メモリバリアはそのコード部分では不要です。
これは最小限の保証であることに注意ください。付録Cで述べるように、異なるアーキテクチャはより多くの保証を与えることがあります。しかしそれは、そのアーキテクチャでだけ動くために特別に設計されたコードの外では、それに頼ることはできません。
しかし、ロックプリミティブや、アトミックデータ構造操作とトラバーサルプリミティブのように、アトミック操作を実装するプリミティブは、通常は必要なメモリバリアをその定義の中に含んでいます。なお、Linux カーネルの atomic_inc() のような例外もいくらかあります。なのでドキュメントと、もし可能ならあなたのソフトウェア環境の実際の実装を、よく見るように注意ください。
最後に一つ忠告を。生のメモリバリアプリミティブを使うのは最後の手段であるべきです。メモリバリアの面倒を見てくれる既存のプリミティブを使う方が、ほぼ常に良いでしょう。
１４．３ ノンブロッキング同期
ノンブロッキング同期(NBS)という語は６つのクラスの線形化可能なアルゴリズムを意味し、それぞれは異なる前方進行保証(forward-progress guarantee) をもちます。これら前方進行保証は、リアルタイムプログラミングの基本となるそれとは直交しています。
１ リアルタイム前方進行保証は、通常、なんらかの決められた時間に関係します。例えば、「スケジューリング遅延は１００マイクロ秒以下でなくてはいけません」など。それに対して、NBSは進行が有限時間でされればよく、決められた限界はありません。
２ リアルタイム前方進行保証は、時には確率的です。例えば、ソフトリアルタイム保証は、「少なくても９９．９%の時間、スケジューリング遅延は１００マイクロ秒以下でなくてはいけません」など。それに対して、NBSの前方進行保証は伝統的に条件をつけません。
３ リアルタイム前方進行保証はしばしば環境の制約で条件付けられます。例えば、最高の優先度のタスクにだけ有効、それぞれのCPUがある程度の割合の時間以上アイドルであるときだけ有効、あるいは、I/Oの比率がある指定された最大値より小さいときだけ有効、などです。それに対して、NBSの前方進行保証は通常条件をつけません。
４ リアルタイム前方進行保証は通常、ソフトウェアバグがないときだけ有効です。しかし、ほとんどのNBS保証は失敗したら止まってしまうバグがある時にも適用できます。
脚注
繰り返しますが、最近のいくつかのNBSの研究はこの保証を緩めます。
５ NBS前方進行保証クラスは、線形化可能性を意味します。それに対して、リアルタイム前方進行保証はしばしば、線形化可能性のようなオーダリング制約と独立です。
このような違いがあっても、いくつかのNBSアルゴリズムはリアルタイムプログラミングにおいてとても便利です。
NBS階層には、現在６つのレベルがあります。それはほぼ、以下のとおりです。
１ ウェイトなし同期。すべてのスレッドは有限時間内に進行します。
２ ロックなし同期。少なくても１つのスレッドは有限時間内に進行します。
３ 障害なし同期。競合のない時、すべてのスレッドは有限時間内に進行します。
４ 衝突なし同期。競合のない時、少なくても１つのスレッドは有限時間内に進行します。
５ 飢餓なし同期。失敗のない時、すべてのスレッドは有限時間内に進行します。
６ デッドロックなし同期。失敗のない時、少なくても１つのスレッドは有限時間内に進行します。
NBSクラス１と２は、１９９０年代初頭に最初に形式化されました。クラス３は２０００年代初頭に最初に定式化され、クラス４は２０１３年に最初に定式化されました。最後の二つのクラスは、何十年にわたって正式でないやり方で使われてきましたが、２０１３年に再度、定式化されました。
理論的には、どんな並列アルゴリズムも待ちのない形式に変換できますが、一般的に使われているのはNBSアルゴリズムの比較的小さなサブセットです。以下の節で、そのうちいくつかを示します。
１４．３．１ 単純なNBS
たぶん、最も単純なNBSアルゴリズムは、fetch-and-add (atomic_add_return()) プリミティブを使う整数カウンタのアトミックな加算です。
もう一つの単純なNBSアルゴリズムは配列内の整数のセットを実装します。ここで配列のインデックスはそのセットのメンバであるかもしれない値を示し、配列要素はその値が実際にセットのメンバであるかどうかを示します。NBSアルゴリズムの線形化可能性は、配列のリードと更新が、アトミック命令を使うかあるいはメモリバリアを伴うことを要求します。しかし、線形化可能性が重要ではないわりによくある場合は、例えば ACCESS_ONCE() を使った単純な volatile なロードとストアで十分です。
NBSセットをビットマップで実装することもできます。ここでそのセットのメンバであるかもしれないそれぞれの値は、一つのビットに対応します。リードと更新は通常はアトミックなビット操作命令で実行しないといけませんが、コンペアアンドスワップ (cmpxchg() あるいは CAS) 命令を使うこともできます。
５.２節で述べた統計カウンタアルゴリズムは、待ちがないとみなすことができます。しかしそれは、合計が正確でなく近似的であるという素敵な定義のトリックを使っただけです。
脚注
出典必要。私はこのトリックを Mark Moir から聞きました。
read_count 関数がカウンタを合計するのに要する時間の長さの関数である誤差限界値を十分に広く取れば、線形化可能でないふるまいがあったことを証明するのは不可能です。これはもちろん、(少し無理がありますが)統計カウンタアルゴリズムを待ちなしに分類します。このアルゴリズムはたぶん、Linuxカーネルで最も多く使われている NBSアルゴリズムです。
もう一つの一般的なNBSアルゴリズムは、アトミックキューです。そこでは、要素はアトミック交換命令と、それに続いて新しい要素の前の要素の ->next ポインタへのストアによってエンキューされます。図１４.１９はこれを示したもので、ユーザ空間RCUライブラリの実装です。９行目はテールポインタが新しい要素を参照するように更新し、その前の要素への参照を返します。それはローカルへ変数 old_tail に格納されます。そして１０行目で、前の要素の ->next ポインタを新しく追加された要素を参照するように更新し、最後に１１行目でキューが最初に空だったかどうかの結果を返します。
単一の要素をデキューするには相互排他が必要です(デキューがブロッキングであるためです)。しかし、キューの内容全体をノンブロッキングにデキューするのは可能です。不可能なのは、任意の要素をノンブロッキングなやり方でデキューすることです。エンキューする人は、図の９行目と１０行目の間で落ちることがあるでしょう。すると問題の要素は部分的にだけエンキューされます。この結果、エンキューはNBSですがデキューはブロッキングである半NBSアルゴリズムになります。しかしこのアプローチはそれでも現実に使われています。それは、一つには、ほとんどの本番ソフトウェアは任意の失敗して止まってしまうエラーに耐えられることは求められていないからでしょう。
１４．３．２ NBSの議論
完全にノンブロッキングなキューを作ることは可能です。しかし、そのようなキューは前に述べた半NBSアルゴリズムに比べてずっと複雑です。ここでの教訓は、あなたの要件が本当は何であるかを注意深く考えることです。関係ない要件を緩めれば、しばしば、単純さと性能の両方が素晴らしく向上することがあります。
最近の研究は、要件を緩めるためのもう一つの重要な方法を示します。公平なスケジューリングを提供するシステムは、それが、ノンブロッキングな同期だけを提供するアルゴリズムを実行していても、待ちのない同期のほとんどの利点を享受できることが、理論的にも現実でも証明されました。本番環境で使われているとても多くのスケジューラは実際に公平さを提供しますから、待ちのない同期を提供する複雑なアルゴリズムは、それより単純でしばしばより速いノンブロッキング同期の代替品に対して、通常は現実的な利点は何もないわけです。
さらに興味深いことに、現実にしばしば尊重されている制約で利益をもたらすものは、公平なスケジューリングだけではありません。制約の他のセットは、ブロッキングアルゴリズムが決定論的な実時間応答を達成するのを可能とします。例えば、ある優先度レベルにおいて要求者にFIFO順に許可される公平なロック、優先度逆転を防ぐための方法(優先度継承とか、優先度シーリングなどの)、有限個数のスレッド、有限個数のクリティカルセクション、有限の負荷、そして失敗したら止まってしまうバグを避けること、これらの条件のもとでは、ロックベースのアプリケーションは決定論的な応答時間を提供できます。このアプローチはもちろん、ブロッキングと待ちのない同期の区別をあいまいにします。それはいずれにしても良いことです。理論的フレームワークが進歩を続けて、ソフトウェアが現実にどのように実際に構築されるかを説明するその能力が高められることを期待しましょう。
以上