以下は、perfbook の７章の kanda.motohiro@gmail.com による全訳です。perfbook の訳の他の部分は、親文書を参照。
７章 ロック
最近の並列実行の研究では、ロックが多くの場合悪役を演じてきました。多くの論文と発表で、ロックはデッドロック、コンボイイング、飢餓、不公平、データ競合、そしてすべての他の同時実行の罪に問われています。興味深いことに、本番品質の共用メモリ並列ソフトウエアの働き馬としての役割も、お察しのとおり、ロックが演じています。この章では、図７．１と７．２に楽しく描かれたような悪役と英雄のこの二面性を詳しく調べることにしましょう。
このジキルとハイドの二面性には多くの理由があります。
１ ロックの罪の多くには、ほとんどの場合にうまく働く現実的なソリューションがあります。例えば、
(a) デッドロックを避けるには、ロックの階層を使います。
(b) Linuxカーネルの lockdep 機構のような、デッドロック検出ツールを使います。
(c) 配列、ハッシュテーブル、 radix tree のような、ロックに優しいデータ構造を使います。これらは、１０章で取り上げます。
２ ロックの罪のいくらかは、高いレベルの競合があるときだけ問題です。設計が誤っているプログラム以外はそんなレベルにはなりません。
３ ロックの罪のいくらかは、ロッキングとともに他の同期機構を使うことで避けられます。他の機構とは、統計カウンタ（５章を参照）、参照カウンタ（９．１節を参照）、ハザードポインタ（９．１．２節を参照）、シーケンスロッキングリーダ（９．２節を参照）、RCU（９．３節を参照）、そして、単純なノンブロッキングデータ構造（１４．３節を参照）などです。
４ ごく最近まで、ほとんどすべての巨大共用メモリ並列プログラムは秘密裏に開発されました。このため、ほとんどの研究者にとって、これらの現実的ソリューションを学ぶのは難しかったのです。
５ ロックは、あるソフトウエア作品にはとてもうまく働き、他のものには、とてもまずいことがあります。ロックがうまくいった作品で働いた開発者は、ロックがうまくいかなかった作品の開発者に比べて、ずっとロックに対して肯定的な意見を持つことがありえます。これは、７．５節で述べます。
６ すべての良い物語は悪役が必要です。そしてロックは、研究論文において、むち打たれる少年としての、長く名誉ある歴史を持ちます。
クイッククイズ７．１：
むち打たれる少年であることが、なんで、名誉あることになるのですか？？？
この章は、ロックのより深刻な罪を避けるいくつかの方法の概要を示します。
７．１ 生きてある
ロックが、デッドロックと飢餓の罪に問われていることを考えると、共用メモリ並列開発者の一つの重要な心配ごとは、ただ、生きてあることができるかです。このため、以下の節でデッドロック、ライブロック、飢餓、不公平、そして非効率を扱います。
７．１．１ デッドロック
デッドロックは、スレッドのグループのそれぞれが少なくても１つのロックを持っており、同時にその同じグループのメンバーが持っているロックを待っている時に起きます。
何らかの外部からの介入がない限り、デッドロックは永遠です。どのスレッドも、自分が待っているロックを持っているスレッドがロックを放さない限り、ロックを取ることはできませんが、そのロックを持っているスレッドは、自分が取ろうとしているロックが取れるまでロックを放すことはできません。
図７．３に示すように、スレッドとロックをノードとして、デッドロックシナリオの有向グラフ表現を作ることができます。ロックからスレッドへの矢印は、そのスレッドがそのロックを持っていることを示します。例えば、スレッドBはロック２と４を持っています。スレッドからロックへの矢印は、そのスレッドがそのロックを待っていることを示します。例えば、スレッドBはロック３を待っています。
デッドロックシナリオは常に少なくても１つのデッドロックサイクルを含みます。図７．３で、このサイクルは、スレッドB、ロック３，スレッドC,ロック４，そしてスレッドBに戻ります。
クイッククイズ７．２：
でも、デッドロックの定義は、それぞれのスレッドが少なくても１つのロックを持ち、他のスレッドが持っている別のロックを待っているとしか述べていません。サイクルがあると、なぜわかるのですか？
既存のデッドロックを修復できる、データベースシステムのようなある種のソフトウエア環境はありますが、このアプローチは、スレッドの１つが終了させられるか、あるいは、スレッドの１つから、ロックが強制的に盗まれる必要があります。この終了と強制的な盗みはトランザクションにとっては適切かもしれませんが、カーネルやアプリケーションレベルでのロックの使用にとっては、しばしば問題です。その結果できる、部分的に更新された構造を扱うのは、極めて複雑で、危険で、誤りを起こしやすいです。
なので、カーネルとアプリケーションはデッドロックから回復するのでなくて、それを避けるように働きます。デッドロック回避戦略はたくさんあります。ロック階層（７．１．１．１節）、ローカルロック階層（７．１．１．２節）、層をなすロック階層（７．１．１．３節）、ロックへのポインタを持つAPIを扱うための戦略（７．１．１．４節）、条件ロック（７．１．１．５節）、すべての必要なロックを最初に取る（７．１．１．６節）、一度に１つのロックだけ設計（７．１．１．７節）そして、シグナルあるいは割り込みハンドラのための戦略（７．１．１．８節）などがあります。すべての状況で完璧に働くデッドロック回避戦略はありませんが、デッドロック回避ツールにはたくさんの選択肢があります。
７．１．１．１ ロック階層
ロック階層はロックを順序付け、逆順でロックを取るのを禁止します。図７．３で、ロックを数字で順序付けて、スレッドが、あるロックを取ろうとするときに、既に同じかより大きい数字のロックを取っていたらそれを禁止することができます。スレッドBはこの階層を破っています。なぜなら、それはロック４を持ったままロック３を取ろうとしており、これがデッドロックを起こしているのです。
もう一度言うと、ロック階層を適用するには、ロックを順序付けて、逆順の確保を禁止します。大きなプログラムでは、ツールを使ってあなたのロック階層を強制するのが賢明でしょう。
７．１．１．２ ローカルロック階層
しかし、ロック階層はグローバルな性質を持ちますから、ライブラリ関数に適用するのは難しいです。結局、あるライブラリ関数を使うプログラムは、まだ書かれていないかもしれません。なので、哀れなライブラリ関数開発者が、これから書かれるプログラムのロック階層に従うことを期待するにはどうすればいいでしょう？
一つの特別な場合、それは幸運にも一般的ですが、は、ライブラリ関数が、コール元のコードを全く呼ばない時です。この場合、コール元のロックは、何らかのライブラリのロックを持ったまま取られることが決してないので、ライブラリとコール元の両方を含むデッドロックサイクルはあり得ません。
クイッククイズ７．３
この規則の例外はありますか？ライブラリのコードが決してコール元のコードを何も呼ばないにもかかわらず、ライブラリとコール元の両方のロックを含むデッドロックサイクルが実際に起きることがありますか？
でも、ライブラリ関数が実際にコール元のコードを呼ぶことを考えましょう。例えば、 qsort() 関数は、コール元の提供した比較関数を呼びます。qsort() の同時実行する実装はロックを使うことでしょうから、もしかするとあまりないだろう、比較関数がロックも使う複雑な関数であった場合、デッドロックになります。ライブラリ関数がデッドロックを防ぐにはどうすればいいでしょう？
この場合の黄金律は、「未知のコードを呼ぶ前に全てのロックを放す」です。この規則を守るには、qsort() 関数は比較関数を呼ぶ前に全てのロックを放す必要があります。
クイッククイズ７．４
でも、qsort() が比較関数を呼ぶ前に全てのロックを放したら、他の qsort() スレッドとの競合をどうやって守ればいいのでしょう？
ローカルロック階層の恩恵を見るには、図７．４と７．５を比べます。どちらの図でも、アプリケーション関数 foo() と bar() は、それぞれロックAとBを持ったままqsort() を呼びます。これは、qsort() の並列実装なので、ロックCを取ります。
関数 foo() は、関数 cmp() を qsort() に渡し、cmp() はロックBを取ります。関数bar() は、単純な整数比較関数（書いてありません）を qsort() に渡します。この単純な関数は、何もロックを取りません。
さて、もし qsort() が、前記の、全てのロックを放すという黄金律を破って、cmp() を呼ぶときにロックCを持っていると、図７．４に示すように、デッドロックが起きることがあります。これを考えるために、あるスレッドが foo() を呼び、２つ目のスレッドが同時に bar() を呼ぶとします。最初のスレッドはロックAを取り、２つ目のスレッドはロックBを取ります。もし、最初のスレッドが呼ぶ qsort() がロックCを取ったなら、それから cmp() を呼ぶときにロックBを取ることはできません。しかし、最初のスレッドはロックCを持っているので、２つ目のスレッドの qsort() 呼び出しはそれを取ることができず、ロックBを放すことができないため、デッドロックになります。
それに対して、もし qsort() が比較関数（それは、qsort() の観点からは、未知のコードです）を呼ぶ前にロックCを放したら、図７．５が示すように、デッドロックは避けられます。
もしそれぞれのモジュールが、未知のコードを呼ぶ前に全てのロックを放したら、それぞれのモジュールが自分のデッドロックを避ける限り、デッドロックは回避できます。なので、この規則はデッドロック解析を大いに簡単にし、モジュラリティを大いに改善します。
７．１．１．３ 層をなすロック階層
不幸にも、qsort() が比較関数を呼ぶ前に全てのロックを放すことができないことがあるでしょう。この場合、未知のコードを呼ぶ前に全てのロックを放すことで、ローカルロック階層を作ることはできません。しかし、その代わりに、図７．６で示した、層をなすロック階層を作ることができます。ここでは、cmp() 関数は新しいロックDを使います。これは、A, B, C 全てのロックを放した後で取られます。こうしてデッドロックは避けられます。こうして、グローバルデッドロック階層に、３つの層ができました。最初のは、A とB を持ち、２つめはC を持ち、３つめは、D を持ちます。
なお、機械的に cmp() 関数が新しいロックDを使うようにするのは、典型的には、不可能であることに注意下さい。全く、逆です。しばしば、深い設計レベルの変更をすることが必要です。とはいえ、そのような変更に必要な努力は、デッドロックを避けるためには安いものです。
未知のコードを呼ぶ前に全てのロックを放すことが現実的でないもう一つの例をあげます。図７．７ (locked_list.c)に示す、連結リストをたどるイテレータを想像して下さい。list_start() 関数がリストのロックを取り、最初の要素を（あれば）返します。そして、list_next() は、リストの次の要素へのポインタを返すか、あるいは、リストの終わりに達したらロックを放して、NULL を返します。
図７．８は、このリストイテレータがどのように使われるかを示します。１から４行目は、１つの整数を持つ list_ints 要素を定義します。６から１７行目が、リストをたどるところです。１１行目でリストをロックして、最初の要素へのポインタをフェッチします。１３行目は、取り囲む list_ints 構造へのポインタを与えます。１４行目は、対応する整数を表示して、１５行目で次の要素に進みます。これはとても単純で、ロックの全てを隠しています。
つまり、それぞれのリスト要素を処理するコードが、自分でロックを取ろうとしない限り、ロックは隠されたままです。もしそれがロックを取ろうとし、そのロックを持っている人が list_start() あるいは list_next() を呼ぶことがあるなら、デッドロックになります。このデッドロックは、リストイテレータのロックを考慮してロック階層を層にすることで避けられます。
この層をなすアプローチは、任意の多数の層に拡張できます。しかし、層を追加すると、ロック設計の複雑さが増します。そのような複雑さの増加は、あるタイプのオブジェクト指向設計にとっては特に面倒です。そこでは、制御が、オブジェクトの大きなグループの間をあちこち、規律なく行き来します。この、オブジェクト指向設計のくせと、デッドロックを避ける必要性の間のミスマッチが、人によっては並列プログラミングがとても難しく感じられることの重要な理由になっています。
高度に層をなすロック階層に代わるものを、９章でいくつか紹介します。
７．１．１．４ ロック階層と、ロックへのポインタ
いくらかの例外もありますが、ロックへのポインタを含む外部APIはとても多くの場合、誤ったAPI設計です。内部的なロックを何か他のソフトウエアコンポーネントに渡すのは、結局、情報隠蔽のアンチテーゼです。なお、情報隠蔽は鍵となる設計指針です。
クイッククイズ７．５
ロックへのポインタを関数に渡すのが、完璧に合理的である１つのよくある例外を述べて下さい。
一つの例外は、何かの要素を渡す関数で、受け渡しが完了するまでコール元のロックが取られたままでないといけなく、さらにその関数が戻るときにはロックが放されていないといけない時です。そのような関数の一つの例は、POSIX pthread_cond_wait() 関数です。そこでは、pthread_mutex_t のポインタを渡すことで、起床が失われたときのハングを防ぎます。
クイッククイズ７．６
pthread_cond_wait() が、まず mutex を放して、そして、取り直すことで、デッドロックの可能性は無くなりますか？
つまり、もしあなたが、引数あるいは戻り値として、ロックへのポインタを取るAPI をエクスポートしているのに気付いたら、あなたのAPI 設計を注意深く見直してください。それはやるべき正しいことかもしれませんが、経験によれば、あまりそういう事はないはずです。
７．１．１．５ 条件付きロック
しかし、合理的なロック階層がない時を考えてください。これは真の人生ではあり得ることです。例えば、層を成すネットワークプロトコルスタックで、パケットが両方向に流れる時です。このネットワークの場合、パケットをある層から別の層に渡すには、両方の層のロックを取る必要があるかもしれません。パケットは、プロトコルスタックを、上にも下にも旅するのを考えると、これは、図７．９に示したように、デッドロックの素晴らしいレシピです。ここでは、スタックを下に、電線に向けて動くパケットは、次の層のロックを、順序を逆に取らないといけません。スタックを上に、電線から動いてくるパケットは、ロックを順に取りますから、図の４行目のロック確保はデッドロックになります。
この場合にデッドロックを避ける一つの方法は、ロック階層を強制し、しかし、ロックを逆順で取らないといけないときは、図７．１０に示すように、条件付きで取ることです。無条件に１層のロックを取る代わりに、5行目では、 spin_trylock() プリミティブを使って、条件付きでロックを取ります。このプリミティブは、ロックが空いていれば直ちにロックを取り(ゼロ以外を返します)、そうでないときは、ロックを取らずに戻り、ゼロを返します。
spin_trylock() が成功したら、１５行目で、必要な１層の処理をします。そうでないときは、６行目でロックを放し、７と８行目で正しい順序でロックを取ります。不幸にも、システムには複数のネットワークデバイスがあるかもしれませんから(例えば、イーサネットとWifi) layer_1() 関数は、ルーティングの決定をしないといけません。この決定は、いつでも変わることがあります。特に、そのシステムがモバイルならば。
脚注
そして、１９９０年代とは違って、モバイルであることは一般的です。
なので、９行目で決定をもう一度チェックしないといけません。もし変わっていたら、ロックを放してやり直します。
クイッククイズ７．７
図７．９から図７．１０への変換は、普遍的に行うことができますか？
クイッククイズ７．８
でも、図７．１０の複雑さは、それがデッドロックを防ぐという点から、価値のあることですよね？
７．１．１．６ 必要なロックを最初に全部取る
条件付きロックの重要で特別なケースに、何らかの処理を実行する前に必要なロックを全部取るというのがあります。この場合、処理は、冪等でなくてもよいです。もし、既にとっているロックをまず、放さないと、すべてのロックを取れないことがわかったら、単にすべてのロックを放して、やり直します。必要なロックが全部取られてから初めて、何らかの処理が実行されます。
しかし、この処理はライブロックになることがあります。それについては、７．１．２節で述べます。
クイッククイズ７．９
７．１．１．６節で述べた、「必要なロックを最初に取る」アプローチを使うとき、ライブロックを避けるにはどうしますか？
関連するアプローチである、２相ロックは、トランザクションデータベースシステムで、永く本番環境で使われてきました。２相ロックのトランザクションの最初のフェーズでは、ロックは取られますが、放されません。必要なロックが全て取られたら、トランザクションは２つめのフェーズに入り、ロックは放されますが、取られません。このロッキングアプローチは、データベースが、そのトランザクションに、シリアライズ可能性に関する保証を与えるのを可能とします。つまり、全てのトランザクションが見たあるいは生成した全ての値は、全てのトランザクションの何らかのグローバルなオーダリングに矛盾なく一致することが保証されます。そのようなシステムの多くは、トランザクションを中止することができることを前提とします。ただ、全ての必要なロックを確保するまで、共用されるデータを一切変更しないことで、これを簡略化することはできます。
そのようなシステムで、ライブロックとデッドロックは問題ですが、現実的な解決策が、多くのデータベースの教科書にあります。
７．１．１．７ 一度に一つのロック設計
ある場合には、ネストするロックを避けることができ、このためデッドロックも避けられます。例えば、問題が完璧に分割可能であれば、それぞれの分割に一つのロックを割り当てることができるでしょう。そうすれば、ある分割の作業をしているスレッドは、対応するロックを一つだけ取れば良いのです。一度に一つ以上のロックを持つスレッドはいないので、デッドロックは不可能です。
しかし、どんなロックも取られていない間、必要なデータ構造が存在し続ける事を保証する何らかの機構がなくてはいけません。７．４節では、そのような機構の一つを議論しました。９章で、それ以外のいくつかを紹介します。
７．１．１．８ シグナルあるいは割り込みハンドラ
シグナルハンドラを含むデッドロックは、シグナルハンドラの中から pthread_mutex_lock() を呼ぶのは違法なことに気がつけば、しばしば簡単に退治できます。しかし、シグナルハンドラから呼ぶことのできるロックプリミティブを手作業で作り出すことは、（ほぼ常に愚かなことですが）可能です。それとは別に、ほぼすべてのオペレーティングシステムカーネルは、割り込みハンドラの中からロックを取るのを許しています。割り込みハンドラは、カーネルでのシグナルハンドラのようなものです。
トリックは、シグナルハンドラの中から取られる可能性のあるすべてのロックを取るときには、シグナルをブロック（あるいはカーネルの場合割り込みを禁止する）ことです。さらに、そのようなロックを持っている時には、シグナルをブロックすることなく、シグナルハンドラ以外のところで取られる可能性のあるロックを取ろうと試みるのは、違法です。
訳注
原文は、ever acquired ですが、取られる可能性のあると訳しました。
クイッククイズ７．１０：
なぜ、シグナルハンドラの中で取られる可能性のあるロックBを持っている時に、シグナルをブロックすることなく、シグナルハンドラ以外のところで取られる可能性のあるロックAを取るのが違法なのですか？
もしあるロックが複数のシグナルのためのハンドラにより取られる可能性があるならば、これらのそれぞれ、すべてのシグナルは、そのロックが取られている時にはブロックされなくてはいけません。そのロックがシグナルハンドラの中で取られたとしてもです。
クイッククイズ７．１１：
シグナルハンドラの中から、合法にシグナルをブロックするにはどうしますか？
不幸にも、あるオペレーティングシステムではシグナルをブロックしたりアンブロックするのは高価です。それには特に、Linux も含まれます。なので、性能を心配するため、シグナルハンドラで取るロックはシグナルハンドラでだけ取ることにして、アプリケーションコードとシグナルハンドラの間の通信にはロックを使わない同期機構を使うことがしばしば行われます。
あるいは、致命的なエラーを処理する時を除いてシグナルハンドラは全く使わないこともあります。
クイッククイズ７．１２：
シグナルハンドラからロックを取るのがそんなに悪い考えであるなら、なぜそもそも、それを安全に行おうとする議論をするのですか？
７．１．１．９ 議論
共用メモリ並列プログラマが使うことができるデッドロック回避戦略はたくさんあります。しかし、それらのどれも、ぴったりいかないシーケンシャルプログラムがあります。これが、優秀なプログラマが自分の道具箱に１つ以上のツールを持っている１つの理由です。ロックは強力な同時実行ツールですが、他のツールを使ったほうが良い作業もあります。
クイッククイズ７．１３
オブジェクトのグループ間で制御を自由に渡すために、直裁的なロック階層、多層もそうでないものも、が存在しないオブジェクト指向アプリケーションがあるとします。
脚注
「オブジェクト指向スパゲッティコード」とも呼ばれます。
このアプリケーションを並列化するにはどうしますか？
とはいえ、この節で述べた戦略は、多くの状況でとても有効であることが証明されてきました。
７．１．２ ライブロックと飢餓
条件付きロックはデッドロックを避ける有効なテクニックですが、乱用されることがあります。
例えば、図７．１１に示す美しい対称的な例を見ましょう。この例の美しさはみにくいライブロックを隠しています。それを見るために、以下のイベントのシーケンスを考えましょう。
１ スレッド１が、４行目で lock1 を取り、do_one_thing() を呼びます。
２ スレッド２が、１８行目で、lock2 を取り、do_a_third_thing() を呼びます。
３ スレッド１は、６行目で、lock2 を取ろうとしますが、スレッド２がそれを持っているので、失敗します。
４ スレッド２は、２０行目で、lock1 を取ろうとしますが、スレッド１がそれを持っているので、失敗します。
５ スレッド１は、７行目で、lock1 を放して、３行目の retry に飛びます。
６ スレッド２は、２１行目で、lock2 を放して、１７行目の retry に飛びます。
７ ライブロックの踊りは最初から繰り返されます。
クイッククイズ７．１４
図７．１１のライブロックを防ぐにはどうしたらいいですか？
ライブロックは、飢餓の極端な形と考えることができます。そこでは、一つのスレッドだけでなく、スレッドのグループが飢餓になります。
脚注
ライブロック、飢餓、そして不公平などの用語の正確な定義にあまりこだわらないようにして下さい。スレッドのグループが、適切な前方進行をすることを妨げるものは何でも、正されなくてはいけない問題です。あなたがそれをどう呼ぶにしても。
ライブロックと飢餓は、ソフトウエアトランザクショナルメモリ実装の深刻な問題です。このため、競合マネージャという概念がこれらの問題をカプセル化するために導入されました。ロックの場合、単純な指数的バックオフがしばしば、ライブロックと飢餓に効きます。その要点は、図７．１２に示すように、それぞれのリトライの前に、指数的に増加する遅延を加えることです。
クイッククイズ７．１５
図７．１２のコードで、どんな問題を見つけることができますか？
しかし、より良い結果のためには、バックオフは有限であるべきです。また、高い競合時には、キュードロックの方が良い結果が得られます。これについては、７．３．２節で詳しく述べます。もちろん、一番良いのは、良い並列設計を使って、ロック競合を低く抑えることです。
７．１．３ 不公平
不公平は、飢餓の、あまり深刻でない形であると考えることができます。そこでは、スレッドの一部が、あるロックを争って、ライオンの分け前を勝ち取ります。これは、共用キャッシュあるいはNUMAの性質を持つマシンで起きることがあります。例えば、図７．１３に示したものです。CPU0がロックを放し、他の全てのCPUがそれを確保しようとしているとき、CPU0とCPU1で共用されるインターコネクトの結果、CPU1は、CPU２から７に比べて有利です。なので、CPU1がたぶんロックを取ることができます。CPU1が、十分に長くロックを保持して、CPU1がそれを放すときにはCPU0がロックを要求するようになっていると、その逆の時も同じですが、ロックは、CPU２から７をバイパスして、CPU0とCPU1の間で往復することがあります。
クイッククイズ７．１６
単純に、良い並列設計を使って、ロック競合を低く抑えれば、不公平もなくなるでしょうから、そのほうが良いのでないですか？
７．１．４ 非効率
ロックは、アトミック命令とメモリバリアを使って実装されます。そして、しばしば、キャッシュミスを起こします。３章で見たように、これらの命令はとても高価です。単純な命令よりもほぼ２桁大きいオーバーヘッドを持ちます。これは、ロックにとって深刻な問題と言えます。もしあなたが、１つの命令をロックで守るなら、あなたはオーバーヘッドを１００倍のオーダーで増やすことになります。完璧なスケーラビリティを仮定したとしても、単一のCPUが同じコードを、ロック無しで実行するのに釣り合うためには、１００個のCPUが必要です。
この状況は、６．３節で議論した同期粒度のトレードオフ、特に図６．２２を裏付けます。粒度が荒すぎるとスケーラビリティが制限されますが、粒度が細かすぎると同期オーバーヘッドが過剰になります。
とはいえ、一度ロックを保持したら、そのロックが守るデータは、ロック保持者により干渉なしにアクセスできます。ロックを取るのは高価かもしれませんが、一度取れば、CPUのキャッシュが効果的な性能加速器となります。少なくても、クリティカルセクションが大きい時には。
クイッククイズ７．１７
ロック保持者が干渉を受けるとしたら、何によってでしょう？
７．２ ロックの型
ロックの型は驚くほどたくさんあります。この短い章が正当に扱うことのできる以上でしょう。以下の節は、排他ロック（７．２．１節）、リーダーライターロック（７．２．２節）、複数の役割のロック（７．２．３節）そして、スコープトロック（７．２．４節）を議論します。
７．２．１ 排他ロック
排他ロックは、名前のとおりです。一度に１つのスレッドだけが、ロックを取れます。そのロックの所有者は、なのでそのロックが守る全てのデータへの排他的アクセスを持ちます。なので、そういう名前です。
もちろん、これは、このロックが、そのロックが守ると主張するデータの全てのアクセスの時に保持されていることを、全て前提とします。助けとなるツールはいくつかありますが、ロックが全ての必要なコードパスで保持されていることを保証する最終的な責任は、開発者にあります。
クイッククイズ７．１８
あるロックを排他的に取ったすぐ後にそのロックを放すこと、つまり、空のクリティカルセクションに、なにか意味がありますか？
７．２．２ リーダーライターロック
リーダーライターロックは、任意の数のリーダーが同時にロックを持つことを許します。また、一方では、単一のライターがロックを持つのを許します。理論的には、リーダーライターロックは、度々読まれて、まれに書かれるデータに対して、素晴らしいスケーラビリティを与えるはずです。実際には、スケーラビリティは、リーダーライターロックの実装によります。
古典的なリーダーライターロックの実装は、アトミックに操作されるカウンタとフラグのセットを持ちます。このタイプの実装は、短いクリティカルセクションの時の排他ロックと同じ問題を持ちます。ロックを取り、放すオーバーヘッドは、単純な命令のオーバーヘッドよりもほぼ２桁大きいのです。もちろん、クリティカルセクションが十分に長ければ、ロックを取り、放すオーバーヘッドは無視できます。しかし、一度に１つのスレッドだけがロックを操作できることから、必要なクリティカルセクションの大きさは、CPUの数とともに、増加します。
スレッドごとの排他ロックを使うことで、リーダーにとって、ずっと優しいリーダーライターロックを設計することができます。読む時は、スレッドは自分のロックだけを取ります。書く時は、スレッドは、全てのロックを取ります。ライターがいないときは、それぞれのリーダーはアトミック命令とメモリバリアだけを起こし、キャッシュミスは起こしません。それは、ロックプリミティブにとって、とても良いことです。不幸にも、ライターは、キャッシュミス、アトミック命令、そしてメモリバリアのオーバーヘッドを起こさないといけません。それはスレッド数の倍、必要です。
要するに、リーダーライターロックは、多くの状況でとても便利です。しかし、それぞれのタイプの実装は、その欠点も確かに持ちます。リーダーライターロックの正統的ユースケースは、とても長いクリティカルセクション、できれば、何百マイクロ秒か、ミリ秒にもなるほどの、を持ちます。
７．２．３ リーダーライターロックを越えて
リーダーライターロックと排他ロックは、許可ポリシーが違います。排他ロックは最大でも１つの所有者を許し、リーダーライターロックは任意の数のリード所有者を許します（しかしライト所有者をは１つだけ）。可能な許可ポリシーはとてもたくさんあります。その１つが、表７．１に示す、VAX/VMS 分散ロックマネージャ(DLM)のものです。空白のセルは、互換モードで、“X”とあるセルは非互換モードです。
VAX/VMS DLM は、６つのモードを使います。比較のため示すと、排他ロックは２つのモード（持っているあるいは持ってない）を使い、リーダーライターロックは３つのモード（持ってない、リード所有、ライト所有）を使います。
最初のモードは、null あるいは、持ってない、です。このモードは他の全てのモードと互換です。それは期待通りです。もしスレッドがロックを持ってないなら、それは、他の任意のスレッドがロックを取るのを妨げることはありません。
２つ目のモードは、並列同時リードです。それは、排他以外のすべての他のモードと互換です。並列同時リードモードは、あるデータ構造の近似的統計を蓄積するのに使うことができます。その時、更新は同時に行われることが許されます。
３つ目のモードは、並列同時ライトです。それは、null、並列同時リード、並列同時ライトと互換です。並列同時ライトモードは、近似的統計を更新するのに使うことができます。その時、リードと、同時実行する更新は同時に行われることが許されます。
４つ目のモードは、保護されたリードで、null、並列同時リード、保護されたリードと互換です。保護されたリードモードは、データ構造の一貫したスナップショットを取るのに使うことができます。その時、リードは同時に行われることが許されますが、更新はだめです。
５つ目のモードは、保護されたライトで、null、並列同時リードと互換です。保護されたライトモードは、保護されたリーダーと干渉する可能性のあるデータ構造を更新するのに使うことができます。その更新は、保護されたリーダーに許されるものです。
６つ目、最後のモードは、排他です。nullだけと互換です。排他モードは、他の全てのアクセスを排除する必要のあるときに使います。
排他ロックと、リーダーライターロックを、VAX/VMS DLM でエミュレートすることができるのを見るのは面白いことです。排他ロックは、null と排他モードだけを使い、リーダーライターロックは、null、保護されたリード、そして保護されたライトモードを使うことができます。
クイッククイズ７．１９
VAX/VMS DLM で、リーダーライターロックをエミュレートする他の方法はありますか？
VAX/VMS DLM ポリシーは、分散データベースの本番で広く使われてきましたが、共用メモリアプリケーションではあまり使われていないようです。その一つの理由は、分散データベースのより大きな通信オーバーヘッドが、VAX/VMS DLM の、より複雑な許可ポリシーのオーバーヘッドを隠すことができたからでしょう。
とはいえ、VAX/VMS DLM はロックの背後の概念がどのくらい柔軟であることが可能かを示す面白い例です。またそれは、現代的な DBMS で使われるロックスキーマに対する、とても単純な紹介としても役に立ちます。それは、 VAX/VMS の６つでなく、３０以上のロックモードを持つことがあります。
７．２．４ スコープトロッキング
これまでに述べてきたロックプリミティブは、明示的な確保と解放プリミティブを必要とします。例えば、spin_lock(), spin_unlock() です。もう一つのアプローチは、オブジェクト指向の、「資源確保は初期化である」“resource allocation is initialization” (RAII) パターンを使うものです。
脚注
http://www.stroustrup.com/bs_faq2.html#finally に、より明確に書いてあります。
このパターンはしばしば、C++ のような言語の auto 変数に適用されます。そこでは、オブジェクトのスコープに入った時に対応するコンストラクタが呼ばれ、そのスコープから抜ける時に対応するデストラクタが呼ばれます。コンストラクタがロックを取り、デストラクタがロックを放せば、ロックに適用できます。
このアプローチは、とても便利に見えます。実際、１９９０年代に私は、これこそが唯一必要なタイプのロックだと確信しました。
脚注
その後、私は Sequent Computer Systems で並列性の仕事をして、すぐにこれが誤った考えだったと気がつきました。
RAII ロックのとても素敵な性質は、そのスコープを抜ける全ての、それぞれの、コードパスにおいて、あなたは注意深くロックを放す必要がないことです。この性質は、面倒なバグのセットを除くことができます。
しかし、RAII ロックにはダークサイドもあります。RAII では、ロック確保と解放をカプセル化するのがとても難しくなります。例えば、イテレータにおいて。多くのイテレータ実装で、あなたはイテレータの「開始」関数でロックを取り、イテレータの「終了」関数でロックを放したいことでしょう。その代わりに、RAII ロックは、ロック確保と解放が同じスコープのレベルで起きることを要求します。このため、前記カプセル化は困難あるいは不可能とさえなります。
RAII ロックはさらに、クリティカルセクションがオーバーラップするのを禁止します。スコープはネストしないといけないという事実のためです。
訳注。？
この禁止のために、多くの有用な構造を表現するのが困難あるいは不可能になります。例えば、あるイベントを発火させようとする複数の同時実行する試みを仲介するロック木を考えましょう。任意に大きい同時実行する試みのグループ内で、ただ一つが成功する必要があります。そして、それ以外の試みについての最良の戦略は、できる限り早く、苦痛なく失敗することです。そうしないと、巨大システムではロック競合が悲劇的になります。(「巨大」とは、CPU が数百です。)
図７．１４に、例となるデータ構造(Linux カーネルのRCU 実装から取りました)を示します。ここで、それぞれのCPU には、rcu_node 構造体の葉が割り当てられます。そしてそれぞれの rcu_node 構造体は、その親へのポインタ(奇妙なことに ->parent と名付けられた)を持ちます。それは、ルート rcu_node 構造体まで続き、ルートの ->parent ポインタは NULL です。親あたりの、子 rcu_node 構造体の数は変わりますが、典型的には３２か６４です。それぞれの rcu_node 構造体は、 ->fqslock という名前のロックを持ちます。
一般的アプローチはトーナメントです。あるCPU は自分の葉の rcu_node 構造体の ->fqslock を条件付きで確保します。もし成功したら、その親のロックを取ろうとします。そして、子のロックを放します。さらに、それぞれのレベルで、CPU はグローバルな gp_flags 変数をチェックします。もしこの変数が、どれか他のCPU がイベントを発火させたことを示すなら、最初のCPUは競争から脱落します。この、取って、放してのシーケンスは、gp_flags 変数が、誰か他の人がトーナメントに勝ったことを示すか、->fqslock を取ろうとする試みが失敗するか、あるいは、ルート rcu_node 構造体の ->fqslock が取れるまで続きます。
図７．１５に、これを実装する簡略化されたコードを示します。この関数の目的は、do_force_quiescent_state() 関数を呼ぶ必要のあることを同時に検出したCPUの間を仲介することです。いかなる時刻においても、do_force_quiescent_state() の一つのインスタンスだけがアクティブでないと意味がありません。なので、もし複数の同時実行するコール元があるときは、そのうちの最大でも一つが実際に do_force_quiescent_state() を呼ぶ必要があり、その他は、（可能な限り早く、苦痛なく）あきらめて去る必要があります。
このため、７から１５行目にあるループを一回りすると、 rcu_node 階層で１レベル、上がろうとします。もし gp_flags 変数が既にセットされているか（８行目）、現在の rcu_node 構造体の ->fqslock を取ることができない場合（９行目）、ローカル変数 ret が１になります。１０行目でローカル変数 rnp_old が NULL でない時、つまり、私達が rnp_old の ->fqs_lock を持っているとき、１１行目でこのロックを放します（ただし、親 rcu_node 構造体の ->fqslock を取ろうと試みた後で）。１２行目で、８あるいは９行目があきらめる理由を見つけた時１３行目でコール元に戻ります。そうでない時は、現在の rcu_node 構造体の ->fqslock を取ったはずなので１４行目でこの構造体のポインタをローカル変数 rnp_old に退避して、次のループを回るパスに備えます。
もし制御が１６行目に着いたら、トーナメントに勝ちました。今やルート rcu_node 構造体の ->fqslock を取っています。１６行目で、グローバル変数 gp_flags がゼロであるままなら、１７行目で gp_flags を１にし、１８行目で do_force_quiescent_state() を呼び、１９行目で gp_flags をゼロに戻します。いずれの場合も、２１行目でrcu_node 構造体の ->fqslock を放します。
訳注
図７．１５の１６行目 if 条件に、! が抜けています。
クイッククイズ７．２０
図７．１５のコードはばかばかしいほど複雑です！単一のグローバルロックを条件付きで確保したらどうです？
クイッククイズ７．２１
待ってください！もし、図７．１５の１６行目でトーナメントに「勝った」ら、do_force_quiescent_state() を呼ぶという仕事を全部しないといけないのですよね。実際、なんでこれが勝利なのですか？
この関数の示した階層ロックはよくあるパターンです。このパターンは、RAII ロックを使ってはとても実装が困難です。前述のイテレータのカプセル化も同じです。なので、予見できる限りの未来においてロック、アンロックプリミティブは必要でしょう。
７．３ ロック実装の問題
開発者は、ほとんど常に、POSIX pthread mutex ロックのように、システムで提供されているロックプリミティブを、それが何であれ、使うのが一番うまくいきます。それでも、実装例を勉強したり、極端なワークロードと環境が課す課題を熟考するのは有益なことです。
７．３．１ アトミック交換を基礎とする排他ロックの実装例
この節は、図７．１６に示した実装をレビューします。このロックのためのデータ構造は、１行目にあるように、ただの int です。整数型なら何でも良いです。このロックの初期値は、２行目にあるようにゼロで、「アンロック済み」を意味します。
クイッククイズ７．２２
図７．１６の２行目で、なぜ、C 言語のデフォルトゼロ初期化に頼らないで、明示的に初期設定をするのですか？
ロック確保は、４から９行目の xchg_lock() 関数で行います。この関数は、ネストされたループを使います。外側のループは、ロックの値を、１（「ロック済み」を意味します）と、アトミックに交換し続けます。古い値が、既に１（言葉を変えて言えば、誰か他の人が既にロックを持っています）であれば、内側のループ（７から８行目）はロックが空くまでスピンします。その後、外側のループがもう一度、ロックを取ろうと試みます。
クイッククイズ７．２３
図７．１６の７と８行目の内側のループは何ものですか？なぜ、６行目のアトミック交換操作を単純に繰り返さないのですか？
ロック解放は、１２から１５行目の xchg_unlock() 関数で行います。１４行目でロックに、値ゼロ「アンロック済み」をアトミックに交換し、解放済みと印をつけます。
クイッククイズ７．２４
図７．１６の１４行目で、なぜ、ロックワードに単純にゼロを入れないのですか？
このロックはテストアンドセットロックの単純な例です。しかし、本番環境の純粋なスピンロックとして、これにとても似た機構が広く使われてきました。
７．３．２ 他の排他ロック実装
アトミック命令を基礎とするとてもたくさんのこれ以外のロック実装があります。Mellor-Crummey and Scott が、そのうちの多くをレビューしています。これらの実装は、多次元の設計トレードオフの中で、それぞれ異なる点を代表します。例えば、前の節で紹介した、アトミック交換を基礎とするテストアンドセットロックは、競合が低い時にうまく働き、メモリのフットプリントが小さいという利点があります。それは、ロックを使うことのできないスレッドにロックを与えるのを避けます。しかしその結果、競合レベルが高い時には、不公平や飢餓さえも引き起こすおそれがあります。
これに比べ、Linux カーネルで使われているチケットロックは、高い競合レベルで不公平を避けることができます。しかし、その、ファーストインファーストアウト主義の結果、ロックを現在使うことのできないスレッドにロックを許可することがあります。そのスレッドはプリエンプトされていたり、割り込まれたり、あるいはそれ以外の原因で実行できないかもしれません。でも、プリエンプションと割り込みを心配しすぎるのもよくありません。プリエンプションと割り込みは、ロックを確保した後でも同じように起きる可能性があるからです。
脚注
ところで、高いロック競合を扱う最適な方法は、そもそも、それが起きないようにすることです！しかし、高いロック競合が、起きうる悪の中でまだましな状況ということもあります。そしていずれの場合も、高いロック競合を扱うスキームを学ぶのは、良い精神の鍛錬です。
テストアンドセットロックとチケットロックを含む、待つ人が単一のメモリ位置をスピンするすべてのロック実装は、高い競合レベルで、性能の問題があります。問題というのは、ロックを解放するスレッドが対応するメモリ位置の値を更新する必要があることです。低い競合レベルではこれは問題になりません。対応するキャッシュラインはロックを持っているスレッドにとってローカルで書き込み可能なままであることが十分期待されます。それに対して高い競合レベルでは、ロックを取ろうとしているそれぞれのスレッドはそのキャッシュラインのリードオンリーのコピーを持つでしょう。ロック保持者は、ロックを放すための更新を行う前に、それらすべてのコピーを無効化する必要があります。一般的に、CPU とスレッドが増えるほど、競合が高い条件下でロックを放すオーバヘッドは大きくなります。
この負のスケーラビリティは、多くの異なるキュードロック実装の動機となりました。キュードロックは、それぞれのスレッドにキュー要素を割り当てることでキャッシュ無効化の高いオーバーヘッドを避けます。これらキュー要素は１つのキューに並んでつながり、それが待っているスレッドにロックを許可する順序を決めます。鍵となる点は、それぞれのスレッドは自分自身のキュー要素をスピンすることです。このため、ロック保持者は、次のCPU のキャッシュから最初の要素を無効化するだけで済みます。この構成は、高い競合レベルでロックの受け渡しオーバーヘッドを著しく減らします。
もっと最近のキュードロック実装は、システムのアーキテクチャも考慮します。ロックを優先的にローカルに許可し、なおかつ飢餓を防ぐための対策もします。これらの多くは、伝統的にディスク I/O をスケジュールするのに用いられたエレベーターアルゴリズムの類似と考えることができます。
不幸にも、高い競合レベルでキュードロックの効率を改善した同じスケジューリングアルゴリズムは、低い競合レベルでそのオーバーヘッドを増すことになります。Beng-Hong Lim and Anant Agarwal はこのために、単純なテストアンドセットロックをキュードロックと組み合わせました。競合が低い時はテストアンドセットロックを使って、競合レベルが高くなるとキュードロックに切り替えます。こうして、低い競合レベルで低オーバーヘッドで、高い競合レベルで公平さと高スループットを得ます。Browning 達は類似のアプローチを取りましたが、個別のフラグを使わなくしました。こうして、テストアンドセット高速パスは、単純なテストアンドセットロックをで使われるのと同じ命令シーケンスを使うことができます。このアプローチは本番環境で使われています。
高い競合レベルで問題となるもう一つの問題は、ロック保持者が遅延する時です。特に、遅延がプリエンプションによる時です。それは優先度逆転になります。つまり、低優先度のスレッドがロックを持ち、しかし、中間の優先度の CPUバウンドのスレッドによってプリエンプトされ、その結果、高優先度のスレッドがロックを取ろうとしてブロックします。この結果、中間の優先度の CPU バウンドのスレッドが、高優先度のスレッドが走るのを妨げることになります。
訳注。原文は、スレッドとプロセスが混じって使われています。
１つの解決策は、優先度継承です。それは、多少の論争を伴いながらも、リアルタイムコンピューティングで広く使われてきました。
優先度逆転を防ぐもう一つの方法は、ロックが取られている間は、プリエンプションを禁止することです。ロックが取られている間にプリエンプションを禁止するのは、スループットも向上させますから、ほとんどの、プロプライエタリ UNIX カーネルは、なんらかのかたちの、スケジューラから見える同期機構を提供しています。これは主に、とある巨大データベースベンダの努力の結果です。これらの機構は通常は、プリエンプションが不適切であるというヒントの形をとります。このヒントはしばしば、特定のマシンレジスタのビットセットの形をとります。それにより、ロック確保ごとのその機構のためのオーバーヘッドが著しく低くて済みます。それに対して、Linux はそのようなヒントは使わず、 futex と呼ばれる機構を使って、類似の結果を得ています。
訳注。？
とても興味深いことに、ロックを実装するのにアトミック命令は厳密には不要です。Herlihy’s and Shavit の教科書に、単純なロードとストアを基礎とするロック実装にかかわる問題の優れた説明があります。そのような実装に今では実用性はほとんどない、という主な論点をここで繰り返しておきましょう。ただ、それらを詳細に学習することは楽しく、ためになります。しかし、以下に述べる一つの例外を除いて、そのような学習は読者への課題とします。
Gamsa 達は、トークンを基礎とする機構を説明しています。そこでは、トークンがCPU間を巡回します。トークンがある CPU に届いたら、そのCPUはトークンが保護するもの全てに排他的なアクセスを得ます。トークンを基礎とする機構を実装するために使われるしかけはいくらでもあります。例えば、
１ CPU ごとのフラグを維持します。それは１つのCPUを除いては最初はゼロです。CPUのフラグがゼロでない時は、それはトークンを持っています。トークンを使い終わったら、自分のフラグをゼロにして、次のCPUのフラグを１（あるいはゼロ以外の任意の値）にします。
２ CPU ごとのカウンタを維持します。それは、最初に、対応するCPUの番号に設定されます。それは、N を、システムにあるCPUの数とした時、ゼロから N - 1 であると仮定します。CPUのカウンタが、次のCPUのそれよりも大きい（カウンタのラップを考慮に入れて）ならば、その最初のCPUがトークンを持っています。トークンを使い終わったら、次のCPUのカウンタを、自分自身のカウンタより１つ大きな値に設定します。
クイッククイズ７．２５：
カウンタのラップを考慮に入れて、あるカウンタが他のより大きいと判断するには、どうしますか？
クイッククイズ７．２６：
カウンタアプローチとフラグアプローチと、どっちがいいですか？
他のCPUがその時にロックを使っていない時にも、あるCPUが直ちにロックを取ることができないことがあるという点で、このロックは普通ではありません。その代わりに、そのCPUはトークンが回ってくるのを待たないといけません。これは、CPUがクリティカルセクションへの周期的なアクセスを必要とし、さらに、トークン巡回時間の変動を許容できる時には便利です。
Gamsa 達は、それを、リードコピーアップデート（９．３節を参照）の変種を実装するために使いました。しかしそれは、周期的なCPUごとの操作を保護するためにも使うことができます。例えば、メモリアロケータが使っている CPUごとのキャッシュをフラッシュするときや、CPUごとのデータ構造のガーベッジコレクションをするとき、CPUごとのデータを共用記憶域（あるいは、必要なら大容量記憶域）にフラッシュするときなどです。
より多くの人々にとって並列ハードウエアが身近になり、より多くのコードを並列化するにつれて、より特別用途向けのロッキングプリミティブが現れることが予想されます。しかし、この重要な安全のための忠告を注意深く考えて下さい。人として可能な限り、標準の同期プリミティブを使いなさい。あなたが自分で作る作業に比べて、標準の同期プリミティブが大きく優れる点は、標準プリミティブは典型的にはよりずっとバグが少ないということです。
脚注
そうです。私は、同期プリミティブを自分で作る作業をした一人です。しかし、私の髪は、その類の作業を始める前と比べて、ずっと灰色になっているのに、あなたは気付かれるでしょう。偶然？たぶん。しかしあなたは、本当に、あなた自身の髪が普通より早く灰色になる危険をおかしたいですか？
７．４ ロックを基礎とする存在保証
並列プログラミングでの鍵となる難問は、存在保証を提供することです。あるオブジェクトへのアクセスが、そのアクセスの試みの間ずっと、そのオブジェクトが存在していることを前提とできるようにすることです。ある状況では、存在保証は暗黙的です。
１ ベースモジュールにあるグローバル変数とスタティックローカル変数は、アプリケーションが動いている限り存在します。
２ ロードされたモジュールにあるグローバル変数とスタティックローカル変数は、そのモジュールがロードされている限り存在します。
３ モジュールは、その関数の少なくても一つがアクティブインスタンスを持つ限りロードされたままです。
４ ある関数のスタック上の変数は、そのインスタンスが戻るまで存在します。
５ もしあなたがある関数の中で実行しているか、あるいは（直接あるいは間接的に）その関数から呼ばれたならば、その関数はアクティブインスタンスを持ちます。
これらの暗黙的存在保証は直裁的です。しかし、暗黙的存在保証をめぐるバグは実際に起こることがあります。
クイッククイズ７．２７：
暗黙的存在保証に依存することでバグになるのはどういう時ですか？
しかし、もっと面白い、そして面倒な、保証は、ヒープメモリに関するものです。ダイナミックに確保されたデータ構造は、解放されるまで存在します。解かれるべき問題は、構造の解放と、同じ構造への同時実行するアクセスを同期することです。これをする一つの方法は、明示的保証、例えばロックによるものです。もしもある構造が、あるロックを持っている時に限って解放されることができるならば、そのロックを持つことでその構造の存在は保証されます。
でも、この保証は、ロック自身の存在に依存します。ロックの存在を保証する１つの直裁的方法は、ロックをグローバル変数に置くことです。しかし、グローバルロックはスケーラビリティを制限するという欠点があります。データ構造のサイズが増えてもスケーラビリティを上げる１つの方法は、ロックを構造のそれぞれの要素に置くことです。不幸にも、データ要素を保護するためのロックをそのデータ要素自身に置くことは、図７．１７に示す微妙な競合条件に陥ります。
クイッククイズ７．２８：
図７．１７の８行目で、削除したい要素がリストの最初の要素でない時は、どうなりますか？
クイッククイズ７．２９：
図７．１７で、どのような競合条件が起きえますか？
この例を直す一つの方法は、グローバルロックのハッシュされたセットを使うことです。そして、図７．１８のように、それぞれのハッシュバケツが自分のロックを持ちます。このアプローチは、データ要素へのポインタを得る（１０行目）前に、適切なロック（９行目）を確保することを許します。このアプローチは、図に示したハッシュテーブルのように、単一の分割可能データ構造に含まれる要素に対しては、とてもうまく行きますが、与えられたデータ要素が複数のハッシュテーブルのメンバーだったり、ツリーやグラフのようなより複雑なデータ構造の場合には、問題があります。これらの問題は、実際、解決可能です。それらの解決法は、ロックを基礎とするソフトウエアトランザクショナルメモリ実装の基礎をなします。しかし、９章に、より単純で、そして高速な、存在保証を提供する方法を説明します。
７．５ ロッキング：英雄あるいは悪役？
実際の人生でよくあるように、ロッキングは英雄でも悪役でもあります。それはそれがどのように使われ、目前の問題が何かによります。私の経験では、アプリケーション全体を書いている人はロッキングで幸せで、並列ライブラリを書いている人は幸せ少なく、そして既存のシーケンシャルライブラリを並列化している人は極めて不幸です。以下の節は、これらの視点の違いの理由を議論します。
７．５．１ アプリケーションのためのロッキング：英雄！
アプリケーション全体（あるいは、カーネル全体）を書くとき、開発者は同期設計を含む設計全体の完全な制御を得ます。設計が、６章で述べたような、分割をうまく活用しているとしたら、ロッキングは極めて効果的な同期機構となります。これは、本番品質の並列ソフトウエアにおいてロッキングが多用されていることで証明されます。
しかし、そのようなソフトウエアは通常そのほとんどの同期設計をロックを基礎としますが、ほとんど常に、他の同期機構も使っています。それには、特別なカウンティングアルゴリズム（５章）、データ所有（８章）、参照カウンティング（９．１節）、シーケンスロッキング（９．２節）、そしてRCU（９．３節）が含まれます。さらに、実務家はデッドロック検知、ロック確保／解放バランス、キャッシュミス解析、ハードウエアカウンタをベースとするプロファイリングなどのための多くのツールを使います。
注意深い設計をして、同期機構をうまく組み合わせて使って、そして良いツールを使えば、ロッキングはアプリケーションとカーネルにおいてとてもうまく働きます。
７．５．２ 並列ライブラリのためのロッキング：ただの、もう一つのツール
アプリケーションやカーネルと違って、ライブラリの設計者は、ライブラリが相互作用するコードのロックの設計を知ることはできません。たしかに、そのコードはこれから何年先にならないと書かれないかもしれません。このため、ライブラリ設計者はあまり制御を得ることはできず、自分の同期設計を決めるときにはより注意深くする必要があります。
もちろん、デッドロックは特に大切です。７．１．１節で議論したテクニックを使う必要があります。１つのよくあるデッドロック回避戦略は、ライブラリのロックがそれを取り囲むプログラムのロッキング階層において独立したサブツリーであることを保証することです。しかしこれは、見た目よりは難しいです。
７．１．１．２節で、１つの問題点を議論しました。つまり、ライブラリ関数がアプリケーションのコードを呼び出す時のことです。qsort() の比較関数引数は良い例です。もう一つの問題点は、シグナルハンドラとの相互作用です。もしもライブラリ関数内で受信したシグナルによってアプリケーションのシグナルハンドラが呼び出されたら、ライブラリ関数が直接シグナルハンドラを呼んだのと同じくらい確かに、デッドロックは起きる可能性があります。
最後の問題点は、system() 関数の使用などによる、 fork(), exec() 対の間に使われるライブラリ関数によって起きます。この場合、あなたのライブラリ関数が fork() のときにロックを持っていたら、子プロセスは、そのロックが取られたまま、人生を始めます。ロックを放すスレッドは親プロセスで動いていて、子ではないので、子があなたのライブラリ関数を呼んだらデッドロックは確実です。
これらの場合、以下のデッドロック問題を避ける戦略を使うことができます。
１ コールバックもシグナルも使わない。
２ コールバックやシグナルハンドラから、ロックを取らない。
３ コール元が同期を制御する。
４ ライブラリAPI の引数によって、コール元にロックを任せる。
５ コールバックのデッドロックを明示的に避ける。
６ シグナルハンドラのデッドロックを明示的に避ける。
以下の節で、上記戦略を１つづつ説明します。
７．５．２．１ コールバックもシグナルも使わない
もしライブラリ関数が、コールバックを使わず、アプリケーションが全体としてシグナルを使わないなら、そのライブラリ関数が取るすべてのロックは、ロッキング階層ツリーの葉となります。この配置は、７．１．１．１節で述べたように、デッドロックを避けます。この戦略は、それが使える時には素晴らしくうまくいきますが、アプリケーションにはシグナルハンドラを使う必要のあるものがあり、ライブラリ関数には、（７．１．１．２節で述べた qsort() のように）コールバックを必要とするものがあります。
その場合、次の節で述べる戦略をしばしば使うことができます。
７．５．２．２ コールバックやシグナルハンドラから、ロックを取らない
コールバックもシグナルハンドラもロックを取らなければ、デッドロックサイクルに入ることはありえず、またしても、直裁的に、そのライブラリ関数がロッキング階層の葉であることができます。この戦略は、 qsort() のほとんどの使い方においてとてもうまくいきます。そのコールバックは普通は、渡される２つの値を比較するだけだからです。この戦略は、多くのシグナルハンドラにおいても、素晴らしくうまくいきます。特に、シグナルハンドラからロックを取るのは、一般的には非難されるべきものだからです。
脚注
しかし、規格書の言葉は、賢いコーダがアトミック操作から、自分自身の自家製ロックプリミティブを作り出すのを止めることはできません。
しかし、アプリケーションがシグナルハンドラから複雑なデータ構造を操作する必要がある時には使えません。
複雑なデータ構造を操作する必要がある時でも、シグナルハンドラからロックをとらないで済ませる方法がいくつかあります。
１ １４．３．１節で議論するノンブロッキング同期に基づく単純なデータ構造を使います。
２ ノンブロッキング同期を普通に使うにはデータ構造が複雑すぎる場合、ノンブロッキングなエンキュー操作を許すキューを作ります。シグナルハンドラでは、複雑なデータ構造を操作する代わりに、必要な変更を記述した要素をキューに加えます。別のスレッドがその要素をキューから取り出して、通常のロッキングを使って必要な変更を実行します。同時実行可能なキューのすぐに使える実装は、いくつもあります。
この戦略は、時々、マニュアルあるいは（可能ならば）自動の、コールバックとシグナルハンドラのインスペクションによって強化するのがよいでしょう。これらのインスペクションを実行する時は、アトミック操作から（愚かにも）自前のロックを作ってしまうことのある、お利口なコーダに注意下さい。
７．５．２．３ コール元が同期を制御する
コール元に同期を制御させます。これは、ライブラリ関数が、コール元から見える独立したデータ構造のインスタンスを操作し、それぞれが個別に同期できる時に、特にうまく働きます。例えば、ライブラリ関数が検索木を操作し、アプリケーションが多数の独立した検索木を必要とするなら、アプリケーションはそれぞれの木にロックを対応つければ良いです。そしてアプリケーションは、必要に応じてロックを取ったり放したりします。なので、ライブラリは並列性に全く気がつく必要がありません。そうでなく、アプリケーションが並列性を制御して、７．５．１節で議論したようにロックがとてもうまく働くようにします。
しかし、この戦略は、ライブラリが、内部的な同時実行性が必要なデータ構造を実装すると失敗します。例えば、ハッシュ表や並列ソートです。この場合、ライブラリはどうやっても、自分で同期を制御する必要があります。
７．５．２．４ ライブラリAPI の引数によって、コール元にロックを任せる
ここの発想は、ライブラリのAPIに引数を加えて、どのロックを取るか、あるいは、どのように取り放すか、もしくはその両方を指定させるというものです。この戦略は、アプリケーションに、デッドロックを避けるグローバルな仕事を受け持たせることができます。どのロックを取るか（問題のロックへのポインタを渡します。）、そしてどのように取るか（ロック確保と解放関数へのポインタを渡します。）を指定させます。しかし同時に、そのライブラリ関数は、ロックを確保、解放するのをいつにするか決めることができ、自分の同時実行性を制御できます。
特に、この戦略は、ロック確保と解放関数が、必要に応じてシグナルをブロックすることを許します。そのとき、ライブラリコードは、どのロックの時にどのシグナルがブロックされないといけないか、気にする必要がありません。この戦略が使う、問題点の分離はとても効果的なことがあります。しかし、前の節で述べた戦略の方がうまく行くときもあるでしょう。
とはいえ、ロックへの明示的なポインタを外部APIに渡すというのは、７．１．１．４節に述べたように、とても注意深く考慮されないといけません。この慣習がするべき正しいことであるときもありますが、あなたはまず、他の代わりとなる設計をよく調べるのがよいでしょう。
７．５．２．５ コールバックのデッドロックを明示的に避ける
この戦略の元となる基本的規則は、７．１．１．２ 「未知のコードを呼ぶ前にすべてのロックを放す。」で、議論しました。これは、通常は最適なアプローチです。なぜならば、こうすれば、アプリケーションはライブラリのロック階層を無視することができます。ライブラリは、アプリケーションのロッキング階層全体で、葉あるいは孤立したサブツリーのままです。
未知のコードを呼ぶ前にすべてのロックを放すことができない場合は、７．１．１．３節で述べた階層ロッキングがうまくいくかもしれません。例えば、未知のコードがシグナルハンドラならば、ライブラリはロック確保の間ずっと、シグナルをブロックすることになります。それは、複雑で、遅いでしょう。なので、シグナルハンドラが（あまり賢いこととは思えませんが）ロックを取る場合には、次の節の戦略の方が役に立つでしょう。
７．５．２．６ シグナルハンドラのデッドロックを明示的に避ける
シグナルハンドラのデッドロックを明示的に避けるにはこうします。 １ もしアプリケーションがシグナルハンドラの中からライブラリ関数を呼ぶならば、そのライブラリ関数をシグナルハンドラ以外から呼ぶときには、毎回必ず、そのシグナルをブロックしないといけません。 ２ もしアプリケーションが、あるシグナルハンドラで取るロックを持ったまま、ライブラリ関数を呼ぶならば、 訳注。ロックを取るライブラリ関数を呼ぶ？ そのライブラリ関数をシグナルハンドラ以外から呼ぶときには、毎回必ず、そのシグナルをブロックしないといけません。 これらの規則を強制するには、Linux カーネルの lockdep ロック依存関係チェッカのようなツールを使うことができます。lockdep の偉大な強みの１つは、人間の直感にだまされないことです。 ７．５．２．７ fork() と exec() の間で使われるライブラリ関数 前に述べたように、もしもあるライブラリ関数を実行しているスレッドが、他のスレッドが fork() を呼んだ時にロックを持っていたら、子を作成するために親のメモリが複写されるという事実は、このロックは、子のコンテキストでは最初からロックされたままになることを意味します。
この問題への一つのアプローチは、ライブラリ関数が、ロックの所有者がまだ実行中かを調べることです。もしそうでないなら、ロックを再初期化して確保することで「こわします」。しかしこのアプローチはいくつかの欠陥があります。
１ ロックが保護しているデータ構造はなんらかの中間状態にあることが予想されます。なので、ナイーブにロックをこわすのは、任意のメモリ破壊になるかもしれません。
２ 子がもう一つのスレッドを作ったら、二つのスレッドが同時にロックをこわすかもしれません。その結果、どちらも、自分がロックを持っていると判断します。これも、任意のメモリ破壊になります。
atfork() 関数は、この状況に対処するためにあります。発想は、関数を３つ、登録することです。一つは、親で、fork() の前に呼ばれ、もう一つは、親で、fork() の後に呼ばれ、最後は、子で、fork() の後に呼ばれます。これら３カ所で、適切な後始末をすることができます。
しかし、注意下さい。atfork() ハンドラのコーディングは、一般的にとても微妙です。atfork() が一番うまくいくのは、問題のデータ構造が、子によって単純に再初期化できるものの時だけです。
７．５．２．８ 並列ライブラリ:議論
どの戦略を使うにしても、ライブラリAPI の記述には、その戦略を明確に記述して、コール元がその戦略とどう関係するのかが書かれていなくてはいけません。要するに、ロックを使って並列ライブラリを作るのは可能ですが、並列アプリケーションを作るほどには簡単ではありません。
７．５．３ シーケンシャルライブラリを並列化するためのロッキング: 悪役！
低価格のマルチコアシステムが容易に入手可能となり、シングルスレッドでの使用しか想定されずに設計された既存ライブラリを並列化する作業がよくあるようになりました。この場合、並列性は全くあるいはほとんど無視されていますから、並列プログラミングの観点からは著しい欠陥のあるライブラリ API があるときがあります。欠陥の例は:
１ 分割が暗黙的に禁止されている。
２ コールバック関数がロックを必要とする。
３ オブジェクト指向スパゲッティコード。
以下の節で、これらの欠陥と、ロッキングに与える影響を議論します。
７．５．３．１ 分割が禁止されている
あなたが、シングルスレッドのハッシュテーブル実装を書いているとします。ハッシュテーブルにある要素の正確な総数を維持するのは簡単で高速です。さらに、追加と削除操作において、この正確な数を返すのは簡単で高速です。なら、やればいいですよね？
１つの問題は、５章で述べたように、マルチコアシステムでは、正確なカウンタは性能も、スケーラビリティも悪いということです。この結果、このハッシュテーブルの並列化実装は、性能もスケーラビリティも悪いです。
なら、この場合、どうしたらいいでしょう？１つのアプローチは、５章で述べたアルゴリズムの１つを使って近似的カウントを返すことです。もう一つのアプローチは、要素のカウントを全部やめることです。
どちらにしても、このハッシュテーブルの使い方を調べて、なぜ、追加と削除操作が正確なカウントを必要とするのか調べる必要があります。以下は、可能な例です。
１ ハッシュテーブルを再拡張する時を決めます。この場合、近似的カウンタで十分なはずです。あるいは、再拡張操作を、最も長いチェーンの長さで起動するのも有益でしょう。それなら、チェーンごとに素晴らしく分割されて計算、維持できます。
２ ハッシュテーブル全体を走査するのに必要な時間を見積もります。この場合も、近似的カウンタで十分です。
３ 診断のため。例えば、要素をハッシュテーブルに入れたり除いたりするときに、無くなってしまわないかチェックします。これは明らかに正確なカウントが必要です。しかし、この用途は本質的に診断なので、ハッシュチェーンの長さを維持して、たまに、追加と削除操作をロックで止めたうえで、合計を取れば十分かもしれません。
今では、並列ライブラリ API に、性能とスケーラビリティが課す制約のいくつかに、強力な理論的根拠があることがわかっています。並列ライブラリを設計する人は皆、この制約を良く注意する必要があります。
実際には並列性に優しくない API の問題であるのに、ロックを責めるのはとても簡単ですが、そうすることは役に立ちません。一方、この決定を(例えば)１９８５年におこなった不運な開発者への同情は禁じ得ません。その頃に、並列性の必要性を予期できるのは、稀で勇気ある開発者だけだったでしょう。また、実際に、良い並列性に優しい API に到達できるためには、さらに稀な、知性と運の組み合わせが必要でしょう。
時は過ぎ、コードも時と共に変わらなくてはいけません。とは言っても、人気のあるライブラリには膨大な数のユーザがいるかもしれません。その場合、API に非互換な変更をするのはとても愚かです。この状況では、既存の、多く使われているシーケンシャルオンリーのAPI に、それを補足する並列性に優しい API を加えるのが、多分、取りうる最上の策でしょう。
とはいえ、人間の性はご存知の通りですから、不運な開発者が、彼あるいは彼女の誤った(とはいえ、同情の余地のある) API 設計の選択を嘆く代わりに、ロックに文句を言うというのは良くあることでしょう。
７．５．３．２ デッドロックの危険のあるコールバック
７．１．１．２，７．１．１．３ そして７．５．２節で、規律のないコールバックの使用が、ロックの不幸につながるのを見ました。また、これらの節では、あなたのライブラリ関数をこれらの問題を避けるように設計するにはどうしたらいいか述べました。しかし、１９９０年代の、並列プログラミングの経験のないプログラマがそのような設計に従ったと期待するのは非現実的です。なので、既存の、コールバックを多用するシングルスレッドのライブラリを並列化しようとする人は、ロックが悪役であるとを呪う機会がたくさんあるでしょう。
コールバックを多用するライブラリの使用者がとても多いなら、今回も、並列性に優しい API をライブラリに加えて、既存の使用者が徐々にコードを変換していけるようにするのが賢明かもしれません。あるいは、こういう時はトランザクショナルメモリを使うのが良いと宣伝する人もいます。トランザクショナルメモリについては、未だ評定は出ていませんが、１６．２節はその長所と短所を議論します。なお、ハードウエアトランザクショナルメモリ（１６．３節で議論します）は、この場合、その実装が前方進行保証を提供しない限り（ほとんどの実装はしません）、役に立たないことに注意するのは大切です。その他の、とても現実的と思える（誇張が少ないだけとしても）代案は、７．１．１．５と７．１．１．６節に述べた、そして８章と９章でこれから議論する方法があります。
７．５．３．３ オブジェクト指向スパゲッティコード
オブジェクト指向プログラミングは、１９８０年代から１９９０年代あたりにメインストリームに現れました。この結果、本番環境にはたくさんのオブジェクト指向コードがあります。ほとんどはシングルスレッドです。オブジェクト指向は有益なソフトウェアテクニックかもしれませんが、規律のないオブジェクトの使用は容易にオブジェクト指向スパゲッティコードになります。オブジェクト指向スパゲッティコードでは、制御は、オブジェクトからオブジェクトに基本的にランダムに飛びかいます。それはコードを理解しにくくし、ロック階層を与えるのはより一層困難、もしかすると不可能です。
多くの人は、そんなコードはいつだってクリーンアップできると言うかもしれませんが、言うより行うは難しです。もしあなたがそんなけだものを並列化する仕事を与えられたなら、７．１．１．５と７．１．１．６節に述べた、そして８章と９章でこれから議論するテクニックを使えば、ロックを呪う機会を減らせるかもしれません。この状況は、トランザクショナルメモリの着想につながったユースケースのようなので、それを試してみるのも価値あることかもしれません。とはいえ、同期機構の選択は、３章で述べたハードウェアのくせを考慮した上でされなくてはいけません。結局、同期機構のオーバヘッドが、保護される操作よりも一桁大きいなら、結果は美しいものではありません。
そしてそれは、これらの状況で問う価値のある疑問につながります。このコードはシーケンシャルのままにしておくべきでないか？例えば、並列性はスレッドレベルでなくプロセスレベルで導入されるべきかもしれません。一般的に、もしもある作業がとても困難であることがわかったときは、少し時間をとって、その作業を完了させるための代案を考えるだけでなく、手元の問題をより良く解決できるかもしれない他の作業のことを考えるのも価値があります。
７．６ まとめ
ロックは多分最も広く使われ、最も一般的に便利な同期ツールです。しかし、それは最初からアプリケーションあるいはライブラリに設計済みであるときに最もうまく働きます。ある日、並列に走らなくてはいけない既存のシングルスレッドのコードが、たくさんあることを思うと、あなたの並列プログラミング道具箱にあるツールがロックだけであるというのは良いことではありません。以降のいくつかの章では、他のツールと、それらがロックと、そしてお互いに、協調してどのように使われるのが一番よいかを議論します。
以上