以下は、perfbook の付録Fの kanda.motohiro@gmail.com による抄訳です。perfbook の訳の他の部分は、親文書を参照。クイッククイズのF7-F9の訳、F10以降の訳を別ページにしました。
付録F クイッククイズの答え
F.1 この本の使い方
１．１
５８９ページから始まる、付録F にあります。
やあ、これは簡単だよね。
１．２
たしかにそうです！多くの質問は、Paul E. McKenney がその題材を学んでいる講座の新人学生だったらならばきっと質問したであろうものです。Paul はこれらのほとんどを、教授からでなくて、並列ハードウエアとソフトウェアから学んだということは注目すべきです。Paul の意見では、教授は、並列システムと比べると、言葉による質問に答えてくれることが多いようです。ワトソンは置いときます。もちろん、この種の質問に、教授と並列システムのどちらが最も有意義な答えを出すかという長い議論を始めることもできますが、とりあえずは、答えの有意義さは、たくさんいる教授と並列システムの中で、人によってものによって、大きく異なるということを認めることでよしとしましょう。 その他のクイズは、この本で述べた題材を扱った学術会議の発表や、講義の席で、実際にされた質問にとても良く似ています。その他に、著者の視点からの質問もいくつかはあります。 １．３ 以下は可能ないくつかの戦略です。 １ クイッククイズを無視して、本の残りを読む。クイッククイズの面白い題材を見逃すかもしれませんが、本の残りにもよい題材がたくさんあります。もしあなたの主な目的が、題材について一般的な理解を得ることだったり、特定の問題の答えを探して本を斜め読みしているならば、それは明らかに合理的なアプローチです。 ２ もしあなたが、クイッククイズは気が散って嫌だけど無視できない時は、この本の latex ソースを git アーカイブからクローンして、Makefile と qqz.sty を編集し、PDF 出力からクイッククイズを除くことができます。あるいはそれらの２つのファイルを編集して、答えを、質問のすぐ後にインラインで置くこともできます。 ３ 自分の独自の答えを考えて長時間を費やすことなく、直ちに答えを見ましょう。あなたが解こうとする特定の問題の鍵を、そのクイッククイズの答えが持っているときには、このアプローチは合理的です。または、あなたがその題材のより深い理解を望むけれども、白紙だけを与えられて、並列ソリューションをつくり上げることを要求されるのは望まない場合にも良いでしょう。
F.2 前書き
２．１
あなたがもし本当に、並列プログラミングがすごく難しいと信じているなら、「なぜ並列プログラミングは難しいか？」という質問に簡単に答えることができるでしょう。理由はたくさんあげることができます。デッドロック、競合条件、テストのカバレッジなど。しかし、本当の答えは、それは実際はそんなに難しくない、です。結局、もし並列プログラミングが本当におそろしく難しいなら、Apache、 MySQL に Linux カーネルなどの多くのオープンソースプロジェクトがそれをマスターできているというのはどういうことでしょう？
より良い質問は、「なぜ、並列プログラミングはそれほど難しいと思われているか？」でしょう。この答えを考えるのに、１９９１年に戻りましょう。Paul McKenney は、駐車場を、Sequent のベンチマークセンターに向かって、６枚のデュアル 80486 Sequent Symmetry CPU ボードを抱えて歩いていました。その時彼は突然、自分の最近買った家の何倍もの価格のものを持っているのに気が付きました。この並列システムの高コストは、並列プログラミングが、１９９１年の米国ドルで $100,000 以上するマシンを製造するかあるいは買うお金のある会社に務めている特権ある少数の人々にだけ開かれていることを意味しました。
それに対して、２００６年、Paul はこの文章をデュアルコアの x86 ラップトップでタイプしています。デュアル 80486 CPU ボードと違ってこのラップトップには、２GBのメインメモリ、６０GBのディスクドライブ、ディスプレイ、イーサネット、USB ポート、無線、そして Bluetooth がついています。そしてそのラップトップはデュアル 80486 CPU ボード１枚と比べても、一桁以上安いのです。インフレを勘定に入れなくてもです。
並列システムは本当に到来したのです。特権ある少数の人々だけの領域ではもはやなく、ほとんど誰にでも手が届く何かです。
昔、並列ハードウエアを使える人が限定されたことが、並列プログラミングがそれほど難しいと思われた本当の理由です。ともかく、アクセス出来ないマシンなら、どんなに単純なものであっても、プログラムを学ぶのはとても難しいと思えます。稀で高価な並列マシンの時代はほぼ、終わりました。なので、並列プログラミングが心が折れるほど難しいと思われる時代もそろそろ終わりに近いと言えます。
２．２
それはプログラミング環境によります。SQL は十分に注目されていない成功物語です。それは、並列性について何も知らないプログラマが、巨大な並列システムを生産的にビジーであリ続けるようにするのを可能とします。並列計算機はより安く、入手しやすくなり続けるでしょうから、この主題の変化形はこれからもっと現れるでしょう。例えば、科学技術計算の領域での１つの注目株といえるのは、MATLAB*P です。それは、一般的な行列操作を、自動的に並列化する試みです。
最後に、、Linux と UNIX システムで、以下のシェルコマンドを考えましょう。
get_input | grep "interesting" | sort
このシェルパイプラインは、get_input, grep, そして sort プロセスを並列に走らせます。
ね、難しくはなかったでしょう？
つまり、並列プログラミングはシーケンシャルプログラミングと同じくらい簡単です。少なくとも、並列性をユーザから隠すような環境においては！
２．３ それらは重要なゴールですが、それらはシーケンシャルプログラミングにとっても並列プログラミングにとっても同じように重要です。なので、重要なのですが、並列プログラミングに固有の一覧には入りません。 ２．４ 並列プログラミングはシーケンシャルプログラミングよりもずっと難しいと思われているので、生産性は外すことはできません。さらに、SQL のような高い生産性の並列プログラミング環境は、特別用途のものなので、一般性も一覧に加えられなくてはいけません。 ２．５ 技術的視点から言うと、形式的、非形式的いずれにせよ、正しさを証明することの困難さは、主たる目的である生産性に影響する限りに置いて、重要と言えます。なので、正確さの証明が重要だという場合、それは、「生産性」の項目に含まれます。 ２．６ 楽しいのは重要です。しかし、あなたがホビイストでない限り、主なゴールには普通はならないでしょう。そうでなくて、もしあなたがホビイストなら、いけいけ。 ２．７ 解くべき問題が本質的に並列である場合も確かにあります。例えば、モンテカルロ法や、ある種の数値計算など。しかしこういう場合でも、並列性を管理する余分の作業がいくらかは必要です。 並列性は、ときには、高信頼性のために使われることもあります。１つの例として、３多重冗長系は、３つのシステムが並列に動き、結果を採決します。極端な場合、３つのシステムは、異なるアルゴリズムと技術を使って、独立に実装されることがあります。 ２．８ もしあなたが、純粋なホビイストなら、気にする必要はありません。でも、純粋なホビイストでも、いかにたくさん、速くできるかを気にすることがよくあるでしょう。結局、最も人気のあるホビイストのツールは、普通は、仕事にも最も適したものであり、「最も適した」の定義の重要な部分に生産性も含まれるでしょう。もし誰かがあなたが並列コードを書くことにお金を払ってくれるとしたら、その人はあなたの生産性がとても気になるはずです。そして、あなたにお金を払ってくれる人が何かを気にしているなら、あなたもそれに少しは気を配るのが賢明ということです！ ところで、あなたが本当に生産性に興味が無いなら、計算機なんて使わないで、手で計算したらどうですか？
２．９
この質問にはいくつかの答えがあります。 １ 並列マシンの巨大な計算クラスタがあるとします。クラスタ全体のコストは、けっこうな開発者のコストを容易に正当化します。開発コストは、多数のマシンに分散されますから。 ２ 数千万人のユーザーが動かす人気のあるソフトウエアは、けっこうな開発者のコストを容易に正当化します。コストは、数千万人のユーザーに分散されますから。これには、カーネルやシステムライブラリも含まれるのに注意下さい。 ３ 低コストの並列マシンが、装置の貴重な部分の操作を制御しているとします。この装置の部分のコストは、けっこうな開発者のコストを容易に正当化します。 ４ 低コスト並列マシンのソフトウエアが、極めて貴重な結果を生成するとします。（例えば、鉱物探査。）ならば、その結果はけっこうな開発者コストを正当化します。 ５ 生命を守る安全クリティカルなシステム。ならば、当然、多数の開発者コストを正当化します。 ６ ホビイストと研究者は、知識、経験、楽しみ、あるいは栄光を、お金の代わりに求めます。 なので、ハードウエアのコストが下がることが、ソフトウエアを無価値にするというのは誤りです。そうではなくて、ソフトウエア開発のコストを、ハードウエアのコストに「隠す」ことがもうできなくなったのです。少なくとも、極めて多数のハードウエアがあるのでない限り。
２．１０
これは明らかに達成可能です。携帯電話は、電話をかけたりテキストメッセージを送受信することができる計算機ですが、エンドユーザーの側にはプログラミングも設定も全くあるいはごくわずかしか必要ありません。 これは最初に見たときにはつまらない例だと思えるかもしれませんが、よく考えるとそれは単純で奥深いことがわかります。一般性を犠牲にすれば、本当に驚くほどの生産性の増加を得ることができます。なので、過剰な一般性を求める人たちは、ソフトウェアスタックの一番上に近いところで、生産性のバーを十分に上げることができなくて失敗します。この人生の真実は、独自の省略語を持っています。YAGNI, あるいは、 “You Ain’t Gonna Need It.”「そんなものは要らないはずだよ。」
２．１１ 潜在的ボトルネックはいくらでもあります。 １．メインメモリ。もし、1つのスレッドがすべての使用可能なメモリを消費したら、他のスレッドは自分が動くだけでページフォルトするでしょう。 ２．キャッシュ。もし、1つのスレッドのキャッシュフットプリントがすべての共用CPUのキャッシュを完全に満たしたら、追加のスレッドは、それが使うためにキャッシュを捨てることになるだけでしょう。 ３．メモリバンド幅。もし、1つのスレッドがすべての使用可能なメモリバンド幅を消費したら、追加のスレッドはシステムインターコネクトの待ちを増やすだけでしょう。 ４．I/O バンド幅。もし、1つのスレッドが I/O バウンドなら、追加のスレッドは、そのI/O 資源を待ってみんな列を作るだけでしょう。 特定のハードウェアシステムは他にもたくさんのボトルネックを持つかもしれません。複数のCPUあるいはスレッドで共用されるすべての資源は、潜在的にボトルネックになる可能性を持つというのが真実です。
２．１２ スレッド数の潜在的な制限はいくらでもあります。 １．メインメモリ。それぞれのスレッドはメモリをいくらか使います。(ほかに何もないとしても、そのスタック)なので、スレッド数が多すぎると、メモリを使い果たし、過剰なページングや、メモリ確保の失敗になります。 ２．I/O バンド幅。もし、それぞれのスレッドが、一定の大容量記憶域 I/O あるいはネットワークトラフィックを発生させるとすると、スレッドが多すぎるとI/O キューイング遅延が過剰となり、これも性能を落とします。ネットワークプロトコルによっては、スレッドが多すぎて、ネットワークイベントが時間通りに応答されないとタイムアウトなどの失敗になることがあります。
３．同期オーバヘッド。多くの同期プロトコルにとって、多すぎるスレッドは多すぎるスピニング、ブロッキング、ロールバックを起こすことがあります。そうして性能は低下します。
特定のアプリケーションとプラットホームは、他にもたくさんの限界ファクタを持つかもしれません。
２．１３ 並列プログラミングの潜在的障害は、その他にたくさんあります。以下は、そのわずかです。 １ あるプロジェクトの既知のアルゴリズムが、本質的にシーケンシャルな性質を持っているとします。この場合、並列プログラミングを避けるか（あなたのプロジェクトが並列に走らなくてはいけないという法律はありませんから）あるいは新しい並列アルゴリズムを発明して下さい。 ２ プロジェクトは同じアドレス空間を共有するバイナリーオンリイのプラグインだけを許すとします。それは、１人の開発者が、そのプロジェクトのすべてのソースコードにアクセスできるのを避けるためです。もちろん、デッドロックを含む多くの並列バグは、本質的にグローバルなので、そのようなバイナリーオンリイプラグインは、現在のソフトウエア開発方法論にとって、困難な挑戦を課します。これは変わっていくかもしれませんが、当分は、あるアドレス空間を共有する並列コードの開発者すべては、そのアドレス空間で動くすべてのコードを見ることが出来る必要があります。 ３ プロジェクトが、並列性を考えずに設計されたAPIをたくさん使っているとします。System V メッセージキューAPIの、かなり凝った機能のいくつかは、この例です。もちろん、あなたのプロジェクトが二、三十年の間存在して、その開発者が並列ハードウエアへのアクセスを持たなかったとすると、必ず、そのようなAPIを使っていることでしょう。 ４ プロジェクトは、並列性を考えずに実装されているとします。シーケンシャル環境でとてもうまく働くけど並列環境ではみじめに失敗する技術は山のようにありますから、あなたのプロジェクトがその生涯のほとんどにおいてシーケンシャルハードウエアでしか動いたことがないならば、あなたのプロジェクトは、間違いなく、並列性にフレンドリーでないコードを持っているはずです。 ５ プロジェクトが、良いソフトウエア開発慣習を考えずに実装されたとします。残酷な真実は、共用メモリ並列環境はしばしば、いいかげんな開発慣習に対して、シーケンシャル環境に比べてずっと容赦無いということです。並列化を試みる前に、既存の設計とコードをクリーンアップするのが良いでしょう。 ６ あなたのプロジェクトで元々開発をした人たちは、それ以降、異動しているかもしれません。そして残った人々は、それを維持したり、小さな機能を追加することはできても、「ビッグアニマル」変更はできないとします。この場合、あなたが自分のプロジェクトを並列化するとても単純な方法を思いつかない限り、たぶん、それはシーケンシャルのままにしておくのが良いでしょう。つまり、あなたが自分のプロジェクトを並列化するのに使える単純なアプローチはたくさんあります。例えば、その複数インスタンスを動かすとか、ある頻繁に使われるライブラリ関数の並列実装を使うとか、あるいは、データベースなどの何か他の並列プロジェクトを利用するなど。 これらの障害の多くは、技術的性質のものではないという人がいるかもしれませんが、そうだからといって、現実性が少なくなるわけではありません。要するに、大きなコードのボディを並列化するのは、大きく複雑な作業です。すべての大きく複雑な作業でそうなように、あらかじめあなたの宿題をするのは意味があることです。
F.3 ハードウエアとそのくせ ３．１ ハードウエアの詳細な性質を無視するのはより簡単かもしれません。しかし多くの場合、そうするのはとても愚かなことです。もしあなたが、並列性の唯一の目的は性能を上げることであると認め、かつ、性能はハードウエアの詳細な性質に依存することを認めるならば、論理的に、並列プログラマが少なくても、ハードウエアの性質のいくらかは知る必要があることが導かれます。 これはほとんどの技術分野に当てはまります。あなたは、橋を構成するコンクリートと鉄鋼の性質を理解していない技術者が設計した橋を使いたいですか？お嫌なら、なぜあなたは、元となるハードウエアのいくらかの理解を持たない並列プログラマが競合力のある並列ソフトウエアを開発できると期待できるのですか？ ３．２ この質問への１つの回答は、データの複数要素を単一のマシンワードにパックすることがしばしば可能だということです。そうすれば、アトミックに操作できます。 より流行の回答は、トランザクションメモリをサポートするマシンがそれだというものです。しかしそれらのマシンはいまだに研究上の好奇の対象です。しかし、２０１２年初頭の時点で、ハードウエアトランザクションメモリの限定された形式をサポートするコモディティシステムが、数年以内に商用的に利用可能になるだろうと思われます。ソフトウエアトランザクションメモリが応用可能かどうかについては、いまだわかりません。ソフトウエアトランザクションメモリについての情報は、１６．２節にもあります。 ３．３ 不幸にも、あまりそうではありません。一定数のCPUではある程度の削減がありました。しかし、光速の有限性と、物質の原子的性質のために、CPU設計者が、大きなシステムでのキャッシュミスオーバーヘッドを減らす能力には限界があります。３．３節は、将来の進歩に向けたいくつかの可能性を議論します。
３．４
このシーケンスは多くの可能な複雑さを無視しています。例えば：
１ 他のＣＰＵが同時にこの同じキャッシュラインに関するCAS操作をしようとしているかもしれません。
２ このキャッシュラインはいくつかのCPUのキャッシュにリードオンリーで複製されているかもしれません。その場合、そのキャッシュからフラッシュされなければいけません。
３ CPU７はそのキャッシュラインへの要求が届いた時に、それを操作しているかもしれません。その場合、CPU７は自分の操作が完了するまで要求を止めておく必要があるでしょう。
４ CPU７は、自分のキャッシュからそのキャッシュラインを除いたところかもしれません（例えば、他のデータを置く場所を作るために）。なので、要求が届いた時は、キャッシュラインはメモリに向かう途中です。
５ そのキャッシュラインにコレクタブルエラーが起きたかもしれません。そのデータが使われる前にどこかの時点で修正される必要があります。
本番品質のキャッシュ同期機構は、これらのたぐいの考察のために著しく複雑です。
３．５
もしCPU７のキャッシュからキャッシュラインがフラッシュされなければ、CPU０と７はキャッシュライン上に、同じセットの変数の異なる値を持つかもしれません。このたぐいの同期の誤りは並列ソフトウエアをとても複雑にします。なので、ハードウエアアーキテクトはそれを避けるように言われてきました。
３．６ ハードウエア設計者達は実際にこの問題に取り組んできました。そして物理学者スティーヴン・ホーキングと並ぶ指導者たちに教えを仰いできました。ホーキングの意見は、ハードウエア設計者達は２つの基本的問題を持つということでした。 １ 有限な光速 ２ 物質の原子的性質 最初の問題は、生の速度を制限し、２つ目は微細化、それは結局周波数、を制限します。そしてこれは、電力消費を脇においています。それは現在、本番の周波数を 10 GHz のはるか下に抑えている要因です。 それでも、ある程度の進歩はありました。これは、表F.1を２９ページの表３．１と比べるとわかります。ハードウエアスレッドを１つのコアに統合し、複数コアを１つのダイに統合することで、遅延は大いに改善しました。少なくても、１つのダイあるいは１つのコアの囲いの中では。全体のシステム遅延についていくらかの改善がありましたが、せいぜい、２倍程度のものです。不幸にも、光速も物質の原子的性質も、この数年ではあまり変わっていないようです。 ３．３節は並列プログラマの窮状を和らげるためにハードウエア設計者が他にできることはないか、調べます。 ３．７ トイレットペーパーを１巻、持ってきます。米国では、１巻は、普通、３５０から５００枚くらいあります。１枚、切り取って、横に置きます。これが１クロック周期を表します。さて、残りのロールをほどきます。 できたトイレットペーパーの山が、１つのCASキャッシュミスにほぼ、対応します。 より高価な、システム間通信遅延のためには、トイレットペーパーを何巻か（あるいは何ケースか）使って、通信遅延を表します。 重要な安全のための忠告：トイレットペーパーを使う時は、あなたが一緒に住んでいる人たちの需要を考慮に入れて下さい！ ３．８ 電子のドリフト速度は、個々の電子の長期間に渡る移動を追跡します。個々の電子は、とてもランダムにはねまわることがわかっており、なので、それらの瞬間的な速度はとても速いのですが、長い目で見ると、あまり遠くに行けません。ここで、電子は遠距離通勤者に似ています。その人は自分のほとんどの時間を使って、完全なハイウェイ速度で移動していますが、長い目で見ると、どこにも行っていないのです。これらの遠距離通勤者の速度は、時速７０マイル（時速１１３キロメートル）かもしれませんが、この惑星の表面に相対的な長期間のドリフト速度はゼロです。 回路を設計するとき、電子の瞬間的速度が、しばしば、ドリフト速度よりも重要です。電線に電圧が印加された時、電線に入る電子のほうが、出る電子よりも多くなります。しかし、入る電子は既にそこにいる電子を電線のむこうに少し移動させます。それにより他の電子が次々に動きます。この結果、電場は電線にそってとても速く動きます。空中の音の速度が、典型的な風速よりもずっと大きいのと同じように、電場は、電線を、電子ドリフト速度よりずっと速い速度で伝搬します。 ３．９ たくさんの理由があります。 １ 共用メモリマルチプロセッサシステムは厳格な大きさの限界があります。何千個以上のCPUが必要なら、分散システムを使う以外の選択肢はありません。 ２ 極端に巨大な共用メモリシステムは、とても高価で、表３．１に示した小さな４CPUシステムに比べてより長いキャッシュミスの遅延を持つことが多いです。 ３ 分散システムの通信遅延は、必ずしもCPUを消費しません。なので、しばしば計算とメッセージ転送は平行して進めることができます。 ４ 多くの重要な問題は、「なんちゃって並列」です。なので、極端に巨大な処理量がとても少ない数のメッセージで可能なことがあります。SETI@HOME はそのようなアプリケーションの１つの例です。これらのたぐいのアプリケーションは極端に長い通信遅延があっても、計算機のネットワークを有効に活用できます。 並列アプリケーションの努力が続くことで、長い通信遅延を持っているマシンそしてあるいはクラスタの上でもうまく動作するなんちゃって並列アプリケーションの数は増えていくだろうというのはあり得ることです。とはいえ、ハードウエア遅延が大いに削減されるのはとても喜ばれる開発でしょう。 ３．１０ なぜならば、プログラムのごく小さな部分だけが性能クリティカルであるというのがよくあることだからです。共用メモリ並列性は、私達がその小さな部分に分散プログラミングテクニックを集中するのを許し、性能クリティカルでないぼうだいなプログラム部分に、より単純な共用メモリテクニックを使うのを可能とします。
F.4 仕事のツール ４．１ なぜなら、あなたはけっして、単純な物事を忘れてはいけないからです！ この本の題は、「並列プログラミングは難しいでしょうか。なら、どうしたらいいでしょう？」であることを心に留めて下さい。それに対して、あなたができる最も効果的なことの１つは、単純な物事を忘れる事を避ける事です！結局、あなたが並列プログラミングを難しいやり方でするのを選ぶなら、責めることのできるのは自分だけです。 ４．２ １つの直截的なアプローチは、シェルパイプラインです。 grep $pattern1 | sed -e ’s/a/b/’ | sort 十分に大きな入力に対して、grep は、並列にパターンマッチし、sed は編集し、sort は入力を処理します。シェルスクリプト並列性とパイプラインのデモンストレーションとして、parallel.sh ファイルを見て下さい。 ４．３ 実際、今日使われている並列プログラムのとても多くの割合が、スクリプトベースであるというのはとてもありえます。しかし、スクリプトベースの並列性はその限界があります。 １ 新しいプロセスを作るのは通常、とてもヘビーウェイトで、高価な fork() と exec() システムコールを伴います。 ２ パイプラインを含むデータの共用は、典型的には高価なファイルI/Oを伴います。 ３ スクリプトから使用できる信頼できる同期プリミティブも典型的には高価なファイルI/Oを伴います。 これらの限界は、スクリプトベースの並列性が、荒い粒度の並列性を使うことを要求します。その場合、仕事の単位は少なくても数十ミリ秒の実行時間を有し、できればもっと長いほうが良いです。 私は、細かい粒度の並列性を求める人たちには、ご自分の問題をしっかり考えて、それが荒い粒度の形式で表現できないかを判断するように、強く忠告します。それができないときは、４．２節で述べたような、他の並列プログラミング環境を使うことを考えるのが良いでしょう。
４．４ 並列アプリケーションによっては、ある子プロセスが終了した時に特別の動作をする必要があります。なので、子プロセスを個別に待つ必要があります。さらに、並列アプリケーションによっては、子プロセスが終了した原因を調査しなくてはいけません。図４．３で見たように、wait() 関数から waitall() 関数を作り上げるのは難しくありません。しかし、逆は不可能です。ある子の情報が失われたら、それは永遠にわかりません。 ４．５ そのとおり。あります。そして、この節は、将来の版では、メッセージ機能（UNIX パイプ、TCP/IP、そして共用ファイルI/O）や、メモリマップ（mmap() と shmget() のような）を含むように拡張されているかもしません。ところで、これらのプリミティブをとても詳しく扱う多くの教科書があります。また、本当にモーティベーションの高い人は、マニュアルページや、これらのプリミティブを使っている既存の並列アプリケーションや、Linux カーネル実装そのもののソースコードを読むこともできます。 ４．６ この簡単な例では、そうするべき理由は何もありません。しかし、より複雑な例を想像して下さい。そこでは、mythread() が他の関数を呼び出します。それは別々にコンパイルされたものかもしれません。その場合、pthread_exit() は、これら他の関数が、はるばる、mythread() に戻るまで、なんらかのエラー戻り値を渡さなくても、スレッドの実行を終わらせることができます。 ４．７ ああ、でも、Linuxカーネルは、注意深く選択された、C 言語のスーパーセットで書かれています。それは、asm のような特別の gcc 拡張を含みます。それによって、データ競合があっても、安全な実行ができます。さらに、Linuxカーネルは、データ競合が特に問題となるいくつかのプラットフォームでは動きません。例えば、３２ビットポインタと１６ビットのバスを持つ組込みシステムを考えましょう。そのようなシステムでは、指定されたポインタへのストアとロードに関わるデータ競合の結果、ロードが、ポインタの指す古い値の低オーダーの１６ビットと、ポインタの指す新しい値の高オーダーの１６ビットが組み合わさったものを返すことがあります。 ４．８ あなたがするべき最初の事は、ご自分に、なぜそのような事がしたいかを問うことです。答えが、「私は、多くのスレッドが読むけれど、とてもまれにしか更新されないデータをたくさん持つからです。」であれば、POSIX リーダーライターロックがあなたの探しているものでしょう。これは、４．２．４節で紹介します。 複数スレッドが同じロックを保持する効果を得るもう一つの方法は、あるスレッドがロックを取って、そして pthread_create() を使って他のスレッドを作成することです。これがそもそも良い案なのかという質問は、読者への課題とします。 ４．９ pthread_create() に、lock_reader() を渡すのに必要だからです。pthread_create() に関数を渡すときに、それをキャストすることもできますが、関数のキャストは単純なポインタのキャストと比べると少し、きれいでなく、正しく行うのが難しいのです。 ４．１０ たしかに！そしてそのために、pthread_mutex_lock() と pthread_mutex_unlock() プリミティブは通常、このエラーチェックをする関数にラップされます。後でそれらを、Linuxカーネルの spin_lock() と spin_unlock() プリミティブでラップします。 訳注。？
４．１１ いいえ。 "x=0" が出力されたのは、lock_reader() が最初にロックを取ったからです。その代わりに lock_writer() が最初にロックを取ったら、出力は "x=3" のはずです。しかしコード断片は lock_reader() を最初に開始し、この実行はマルチプロセッサで行われましたから、通常は、lock_reader() が最初にロックを取るのが期待されます。しかし、保証はありません。特に、ビジーなシステムにおいては。 ４．１２ 単一のグローバルなロックを使って、性能もスケーラビリティも良いプログラムを書くのが可能な場合も時にはあるかもしれませんが、そのようなプログラムは規則の例外です。通常は良い性能とスケーラビリティを得るには複数のロックが必要です。 この規則の一つの可能な例外は、「トランザクショナルメモリ」であり、今のところ、研究トピックです。トランザクショナルメモリのセマンティクスは、大まかには、単一のグローバルロックであり、最適化が許され、ロールバックが追加されたものだと考えることができます。 ４．１３ いいえ。ビジーなシステムでは、lock_reader() は、lock_writer() が実行する間ずっと、プリエンプトされたままかもしれません。その場合、それは、lock_writer() の x の中間状態を全く見ることはないでしょう。 ４．１４ 図４．６の３行目を見てください。図４．７のコードは先に走るので、コンパイル時の x の初期化に依存できます。図４．８のコードは次に走るので、x を再初期化しないといけません。
訳注。４．７が走った後同じプロセスで４．８が走るという想定らしい。 ４．１５ volatile 宣言は、この場合に限れば、実際に合理的な代替策です。しかし、ACCESS_ONCE() を使うのは、読者に対して、goflag が同時に読み書きされることを明確に旗を立てるという利益もあります。しかし、ACCESS_ONCE() は、ほとんどのアクセスがロックで守られており(そしてそのために変更はあり得ない)けれども、わずかなアクセスがロックの外で行われる場合に特に便利です。この場合に volatile 宣言をすると、読者にとってはロックの外の特別なアクセスに気がつくのが難しくなり、さらにコンパイラにとっては、ロックの元で良いコードを生成することが難しくなります。 ４．１６ いいえ。ここではメモリバリアは不要で、何の役にも立ちません。メモリバリアは、複数のメモリ参照の間のオーダリングを強制するだけです。システムの一部から他の部分にデータの伝搬を促すためには全く何もしません。これは、素早い大まかな規則を導きます。あなたが、複数のスレッド間で通信するための変数を、一つよりたくさん使わない限り、メモリバリアは要りません。 でも、nreadersrunning はどうでしょう？これは、通信のための２つ目の変数ではないですか？たしかにそうです。そして実は、必要なメモリバリア命令は、__sync_fetch_and_add() に埋め込まれているのです。これによって、スレッドは開始するべきであるかを判定する前に、自分の存在を宣言することが保証されるのです。 ４．１７ 場合によります。もしもスレッドごと変数が、そのスレッドからしかアクセスされず、シグナルハンドラからも決してアクセスされないならば、いいえ、不要です。そうでないならば、ACCESS_ONCE() が必要だという可能性が高いでしょう。５．４．４節で、両方の状況の例を見ます。 これは、あるスレッドが他のスレッドの __thread 変数にどのようにアクセスを得ることができるかという疑問を引き起こします。答えは、２つ目のスレッドは、最初のスレッドがアクセスできるどこかの場所に、__thread 変数へのポインタを格納しないといけない、です。一つのよくあるアプローチは、スレッドごとに要素のある連結リストを維持して、それぞれのスレッドの __thread 変数のアドレスを対応する要素に格納するというものです。 ４．１８ 全くそんなことはありません。 実際、この比較は、どちらかと言えば、かなり寛大です。より公平なのは、ロックプリミティブがコメントアウトされた場合の単一CPUのスループットでしょう。
４．１９
もしも読まれるデータが決して変わらないなら、あなたはそれをアクセスするときにどのようなロックも持つ必要はありません。もしデータが十分にまれにしか変わらないなら、あなたは実行をチェックポイントし、全てのスレッドを停止し、データを変更し、そしてチェックポイントから再開始することもできるでしょう。
もう一つのアプローチは、スレッドごとに単一の排他ロックを持ちます。スレッドは、自分自身のロックを取ることで、より大きな、集合的なリーダーライターロックをリード確保することになります。全てのスレッドごとロックを取れば、それをライト確保することになります。これは、リーダーにとってはとてもうまく働きます。しかし、ライターにとっては、スレッド数が増えるとより大きなオーバヘッドを課すことになります。
とても小さなクリティカルセクションを扱うための他の方法のいくつかを、９．３節で議論します。
４．２０ あなたの最初のヒントは、６４CPUは、システムにある１２８CPUのちょうど半分だということです。この差は、ハードウェアスレッディングの結果です。このシステムは６４コアを持ち、コアごとに二つのハードウェアスレッドがあります。６４以下のスレッドが走っているうちは、それぞれは自分自身のコアで動くことができます。しかし、６４以上のスレッドがあると、スレッドのいくつかはコアを共用しないといけません。どのコア上の対のスレッドも、いくらかのハードウェア資源を共用するので、コアを共有している２つのスレッドのスループットは、それぞれ自分だけのコアで動く２つのスレッドには及びません。なので、100M の線の性能は、リーダーライターロックのためというよりは、単一コアにおいてハードウェアスレッドがハードウェア資源を共有することによって制限されるのです。
これは、10M の線でも見られます。それは、６４スレッドまでは、理想の線から少しずれていきます。その後、鋭く落ちます。これは、100M の線と同様です。６４スレッドまでは、10M の線は主に、リーダーライターロックのスケーラビリティによって制限され、それを超えたら、単一コアにおいてハードウェアスレッドがハードウェア資源を共有することによっても制限されます。
４．２１ 一般的には、より新しいハードウェアは進歩しています。しかし、リーダーライターロックが１２８CPUで理想的性能を達成するためには、二桁以上の進歩が必要でしょう。さらに悪いことに、CPU数が増えれば、必要な性能向上も大きくなります。なので、リーダーライターロックの性能問題は、当分私達と共にあるでしょう。 ４．２２
厳密に言うと、いいえ。二つ目のセットのどんなメンバも、一つ目のセットの対応するメンバから実装できます。例えば、__sync_fetch_and_nand() を使って、__sync_ nand_and_fetch() を実装するにはこうします。
同様に、 __sync_fetch_and_add(), __sync_ fetch_and_sub(), そして __sync_fetch_and_xor() も、それらの対応する、後の値を取るものを使って実装できます。
しかし、代わりとなる形式は、プログラマにとっても、コンパイラ、ライブラリの実装者にとっても、とても便利です。
４．２３
不幸にも、いいえ。 厳しい反例のいくつかは、５章を参照下さい。
４．２４
そういうものは実際ありません。Linuxカーネル内で動く全てのプロセスはメモリを共用します。あなたが手で膨大なメモリマップ作業をしたいのでない限り。
４．２５
そうかもしれません。しかし、それを確かめるのは読者への課題とします。でも一方、vfork() は fork() の変種だということはご理解いただけるでしょうから、fork() を、両方の意味を持つ用語として使っても良いのではないですか。
F.5 カウンティング
５．１
例えば、共用されるカウンタにアトミック操作をするなどの単純なカウンティングアルゴリズムは、遅くてスケールしないか、あるいは不正確です。５．１節を参照。
５．２
ヒント。カウンタを更新するのはきらめくほど速い必要がありますが、カウンタは５ミリ秒に一度くらいしか読み取られないので、カウンタを読む動作はとても遅くても構いません。さらに、読まれた値は、通常はそんなに正確である必要はありません。結局、カウンタは１ミリ秒に１０００回も更新されるので、「真の値」から、数千カウント以内にある値なら、なんとかなるでしょう。この文脈で、「真の値」がどんな意味であるとしてもです。しかし、読まれた値は、おおまかに同じ、絶対誤差値をすべての時間にわたって持つべきです。例えば、カウントが１００万くらいのオーダーであるなら、１％の誤差は問題にならないかもしれませんが、１兆になったら、明らかにまずいでしょう。５．２節を参照。
５．３
ヒント。今回も、カウンタを更新するのはきらめくほど速い必要がありますが、カウンタは加算されるたびに読まれます。そして、読まれた値は正確である必要はありません。ただし、限界未満の値と限界以上の値を近似的に区別する必要があります。５．３節を参照。
５．４
ヒント。またまた、カウンタを更新するのはきらめくほど速い必要がありますが、カウンタは加算されるたびに読まれます。そして、読まれた値は正確である必要はありません。ただし、ゼロから限界までの値の場合と、ゼロ以下もしくは限界以上の２つの場合は、絶対に、完全に区別する必要があります。５．４節を参照。
５．５
ヒント。さらにまた、カウンタを更新するのはきらめくほど速く、スケーラブルである必要があります。I/O操作を遅らせないためです。しかし、カウンタはユーザがデバイスを取り外したいときにだけ読まれるので、カウンタを読むのはすごくゆっくりでかまいません。さらに、ユーザがデバイスを取り外したいと言った時以外は、カウンタを読むことのできる必要は全くありません。また、読まれた値は正確である必要はありません。ただし、ゼロとゼロ以外の場合は絶対に、完全に区別する必要があります。それは、デバイスが取り外されるときにだけ、必要です。そして、カウンタがゼロになったら、他のスレッドが取り外されるデバイスにアクセスを得るのを防ぐ何らかの手段を取るまでは、カウンタをゼロのままにしておかなければいけません。５．５節を参照。
５．６
++ 演算子はアトミックであることもできますが、そうでなくてはいけない要件はありません。実際、 gcc は多くの場合、値をレジスタにロードし、レジスタを加算し、その値をメモリにストアします。これは明らかにアトミックではありません。
５．７
自明な並列プログラムなんてほとんどない、というのが１つの理由です。自明なシーケンシャルプログラムもたくさんあるか、私は日頃、疑問に思っています。
どんなに小さいあるいは単純なプログラムであっても、あなたがテストしない限りは、動きません。テストしたとしても、マーフィーの法則によれば、少なくてもいくつかのバグがいまだに潜んでいるはずです。
さらに、正しさの証明というものは確かにあるのですが、テストの代わりとはけっしてなりません。それは、ここで使われた counttorture.h テスト環境もそうです。結局、証明は、それが元になる仮定以上のことはできません。また、証明にも、プログラムと同じく、簡単にバグが紛れ込みます。
５．８
アトミック操作のオーバーヘッドのためです。x 軸のダッシュ線は、アトミックでない単一の加算のオーバーヘッドを示します。結局、理想的アルゴリズムは、線形にスケールするだけでなく、シングルスレッドのコードに比べて、どんな性能ペナルティもないはずです。
このレベルの理想主義は厳しく見えるでしょうが、もしそれが Linus Torvalds にとって十分良いなら、あなたにとっても十分良いです。
５．９
多くの場合、アトミック加算はあなたにとって実際、十分に速いことでしょう。そういうときには、もちろん、アトミック加算を使うべきです。つまり、より精巧なカウンティングアルゴリズムが必要とされる多くの実世界の状況があります。そのような状況の標準的な例としては、高度に最適化されたネットワークスタックにおいて、パケット数とバイト数を数えるというものです。そういう場合、巨大マルチプロセッサでは特に、実行時間のほとんどが、このようなアカウンティング作業によって費やされるのを見ることがとても多いのです。
さらに、この章の最初で述べたようにカウンティングは共用メモリ並列プログラムで起きる問題の優れた視点を提供してくれます。
５．１０
場合によってはそれは可能です。しかし、面倒がいくつかあります。
１ 変数の値が必要なとき、スレッドは演算がデータに送られるのを待ち、結果が送り返されるのを待つ必要があります。
２ アトミック加算が、以前そして／もしくは以降の操作に対してオーダーしなくてはいけないとき、スレッドは演算がデータに送られるのを待ち、操作が完了した知らせが送り返されるのを待つ必要があります。
３ CPU の間で演算を送るのは、システム接続により多くの線が必要で、ダイ領域と電力をより多く消費します。
しかし、最初の２つの条件が成立しない時はどうでしょう？そのとき、５．２節で議論したアルゴリズムを注意深く考えてみましょう。そうすれば、コモディティハードウエアを使って、ほぼ理想的な性能が得られるはずです。
最初の２つの条件のどちらかあるいは両方が成立するとき、ハードウエア改善の望みがいくらかあります。combining tree を実装するハードウエアを考えることができます。複数のCPUからの加算要求はハードウエアによって結合され、その要求がハードウエアに届いた時には１つの加算に結合されるというものです。また、ハードウエアは要求を順序付けて、それぞれのCPUにその特定のアトミック加算に対応する戻り値を返すこともできます。この結果、命令遅延は、図F.1に示すように、N をCPUの数としたとき、O(logN) で変わります。そして、このようなハードウエア最適化を備えたCPUは、２０１１年に現れ始めています。
これは,図５．４に示す現在のハードウエア性能である、O(N) に比べるとすごい改善です。さらに、３次元回路などのイノベーションが現実になったら、さらにハードウエア遅延が少なくなることも可能です。それでもなお、いくつかの重要な特別ケースにおいては、ソフトウェアの方がずっとうまくできるということはあるでしょう。 ５．１１ いいえ。剰余加算は同様に可換で推移的ですから。少なくても、あなたが符号なし整数を使っているなら。C 標準では、符号付き整数のオーバーフローは未定義の振る舞いとなります。最近は、オーバーフローが起きた時に、ラップ以外のことをするマシンは極めてまれだという事実は置いときます。不幸にも、コンパイラはよく、符号付き整数がオーバーフローしないことを仮定する最適化を行うことがあるので、あなたのコードで符号付き整数がオーバーフローすることがあるなら、２の補数を使うハードウエアにおいても、トラブルに巻き込まれることがあります。 それは置いといても、１つの潜在的な余分な複雑さが、３２ビットのスレッドごとのカウンタから、（例えば）６４ビットの総和を集める時に起きることがあります。この余分な複雑さに対処するのは、読者への課題とします。なお、この章の後のほうで紹介される技術がとても役に立ちます。 ５．１２ その可能性はあります。そして、このおもちゃの実装では、実際そうです。しかし、任意の数のスレッドを許す他の実装を考えるのは、それほど難しくはありません。例えば、５．４．２節で述べたように、gcc の __thread 機構を使います。 ５．１３ C 標準では、他のスレッドが同時に変更しているかもしれない変数をフェッチした結果は未定義です。実際、C 標準には他の選択肢はないとわかります。C は（例えば）long をアトミックにロードできない８ビットアーキテクチャもサポートする必要があるからです。これから作られるバージョンの C 標準はこのギャップをうめようとしています。しかし、それまでは、gcc 開発者の親切心に頼ることになります。 その代わりに、ACCESS_ONCE() で提供されるような、揮発性アクセスの使用は、コンパイラを抑制する助けになります。少なくても、ハードウエアがその値を単一のメモリ参照命令でアクセスする能力がある場合には。 ５．１４ C 標準では、明示的に初期化されないグローバル変数の初期値はゼロです。なので、counter のすべてのインスタンスの初期値はゼロです。さらに、ユーザが統計カウンタの連続するリードの間の差分だけに興味があるという一般的なケースでは、初期値は無関係です。 ５． １５ そのとおり。このおもちゃの例は、１つ以上のカウンタをサポートしません。それを直して、複数のカウンタを提供できるようにするのは、読者への課題とします。 ５．１６ まず、最悪の場合の分析をして、次に、それほど保守的ではない分析をしましょう。 最悪の場合、リード操作は直ちに完了しますが、戻る前に、Δ 単位時間、遅延します。その場合、最悪の場合の誤差は単純に rΔ です。 この最悪の場合の振る舞いはあまりあり得ないので、その代わり、N カウンタそれぞれからのリードが時間期間Δにわたって均等に起きる場合を考えましょう。N個のリードの間には、長さ Δ / N + 1 のインターバルが N + 1 あります。最後のスレッドのカウンタを読んだ後の遅延による誤差は、rΔ / N(N + 1) で与えられるでしょう。最後から２つ目のスレッドのカウンタは 2rΔ / N(N + 1) で、最後から３つ目のが、3rΔ / N(N + 1) などと続きます。誤差の合計は、それぞれのスレッドのカウンタを読む時の誤差の合計で与えられます。それはこうです。 合計を閉じた形で表すと、こうです。 キャンセルすると、直感的に期待される結果となります。
rΔ /2 呼び出し元がリード操作が戻したカウントを使うコードを実行するに従い誤差は蓄積し続けることを覚えておくのは重要です。例えば、もしコール元が戻ったカウントの結果をベースとする何らかの計算を実行して時間 t を使ったならば、最悪の場合の誤差は r(tΔ) に増加したでしょう。 誤差の期待値も同様に、以下に増加したでしょう。 もちろん、リード操作の間、カウンタが増加し続けるのは許されないこともあるでしょう。５．５節はこの状況に対処する方法を議論します。 それはそれとして、統計カウンタのほとんどの用途においては、read_count() が返す値の誤差はどうでもよいことです。それは、read_count() が実行するのに必要な時間は、通常は、read_count() を続けて呼ぶその時間間隔に比べて極めて小さいという事実のためです。 ５．１７
２つのスレッドのうち片方は、読むだけで、変数はアラインされ、マシン長なので、アトミックでない命令で十分です。さらに、ACCESS_ONCE() マクロを使って、コンパイラ最適化を防いでいるので、eventual() にカウンタ更新が見えるようになるのを妨げることはありません。 このアルゴリズムの古いバージョンは、実際に、アトミック命令を使っていました。それらが実は不要だと指摘してくれた Ersoy Bayramoglu に拍手。一方、スレッドごとの counter 変数が、グローバルの global_count より小さい時は、アトミック命令が必要でしょう。しかし、３２ビットシステムで、スレッドごとの counter 変数はそれらを正確に合計するために３２ビットに限定される必要があるかもしれません。そのとき、global_count は、オーバーフローを防ぐために６４ビットであるとします。この場合、定期的にスレッドごとの counter 変数をゼロにして、オーバーフローを防ぐ必要があります。より小さいスレッドごとの変数がオーバーフローしないために、このゼロクリアはあまり長く遅延することができないことに注意するのはとても重要です。このため、このアプローチは元となるシステムに実時間の要求を課すことになり、このため、細心の注意を払って使わなくてはいけません。 これに比べて、すべての変数が同じ長さなら、どの変数がオーバーフローしても無害です。最終的な合計値は、ワード長の剰余となるからです。 ５．１８ この場合、いいえ。その代わりに起きるのは、スレッド数が増すにつれ、read_count() が返すカウンタ値の期待値がより不正確になることです。 ５．１９ はい。もしこれが問題なら、１つの対策は、複数の eventual() スレッドを提供することです。それぞれは、他のスレッドの自分用のサブセットをカバーします。より極端な場合、木構造の eventual() スレッドの階層が必要かもしれません。 ５．２０ eventual() を実行するスレッドはCPU時間を消費します。これら結果整合なカウンタがより多く追加されると、その結果生ずる eventual() スレッドは最後には、すべての可能なCPUを使ってしまうでしょう。なのでこの実装は、異なる種類のスケーラビリティの限界を持ちます。スレッドやCPUの数によるのではなく、結果整合なカウンタの数によるスケーラビリティ限界です。 ５．２１ ほんとに何故でしょうね？ 公平に言うと、gcc は Linux カーネルが無視することにした問題に直面しています。ユーザレベルスレッドが終了するとそのスレッドごとの変数はすべて消滅します。それが、スレッドごとの変数のアクセスの問題を複雑にします。特に、ユーザレベルRCU（９．３節を参照）が発明される前はそうでした。それに対し、Linux カーネルでは、CPUがオフラインになってもそのCPUのCPUごとの変数はマップされアクセス可能なままです。 同様に、新しいユーザレベルスレッドが作成された時、そのスレッドごとの変数は突然存在するようになります。それに対して、Linux カーネルでは、すべてのCPUごとの変数はブート時にマップされ初期化されます。対応するCPUがその時に存在するかにはよりませんし、実際、対応するCPUがいつか将来に存在するかにもよりません。 Linux カーネルが課す鍵となる制限は、CPU数のコンパイル時の最大限界つまり、CONFIG_NR_CPUS と、典型的にはそれよりきつい、ブート時の限界である nr_cpu_ids です。それに対して、ユーザ空間では、スレッド数にハードコードされた上限はありません。 もちろん、どちらの環境でもダイナミックにロードされるコードを扱う必要があります。（ユーザ空間では、ダイナミックライブラリ、Linux カーネルではカーネルモジュール）それらは、スレッドごとの変数の複雑さを増します。 これらの複雑さが、ユーザ空間の環境において、他のスレッドのスレッドごとの変数へのアクセスを提供することをとても難しくします。しかし、そういうアクセスはとてもベンチなので、いつかそれができるようになるとよいです。
５．２２
それは合理的な戦略です。性能差を調べるのは、読者への課題とします。しかし、高速パスは、read_count() でなくて、 inc_count() だってわかってますね。 ５．２３ スレッドが終わるときには、そのスレッドごとの変数は消滅することをわかっていますか。なので、もし、あるスレッドが終わった後でそのスレッドごとの変数をアクセスしようとすると、セグメンテーション違反になります。このロックは、合計とスレッド終了を調停して、このシナリオを防ぎます。 もちろん、その代わりに、リーダーライターロックを、リードロックすることもできます。しかし、９章で、必要な調停を実装するこれより軽量の機構を紹介します。 もうひとつのアプローチは、スレッドごとの変数の代わりに、配列を使うことです。 Alexey Roytman が述べたように、NULL のテストも不要となります。しかし、配列のアクセスは、しばしば、スレッドごとの変数のアクセスより遅く、配列を使うことでスレッドの数に固定の上限が決まってしまいます。さらに、inc_count() 高速パスでは、テストもロックも不要であることに注意ください。 ５．２４ このロックは、実は、省いても構いません。しかし、転ばぬ先の杖と言います。特に、この関数は、スレッド開始時にだけ実行されます。なので、クリティカルパスにはどうやってもなりません。さて、私達が数千のCPU を持つマシンでテストをしているなら、このロックは省くのが良いかもしれません。しかし、「たった」１００個位のCPUなら、小技を使う必要はありません。
５．２５
Linux カーネルのCPUごとの変数は、常にアクセス可能であることに注意下さい。そのCPUがオフラインであっても、そのCPUが一度も存在したことがなく、将来も存在しないとしてもです。
１つの回避策は、図 F.2 (count_tstat.c) で示すように、すべてのスレッドが終了するまで、それぞれのスレッドが存在し続けるのを保証することです。このコードの調査は、読者への課題とします。ただ、これは、counttorture.h カウンタ評価スキームにはうまく合わないことに注意下さい。（なぜでしょう？）９章では、この状況をずっと優雅に対処できる同期機構を紹介します。
５．２６ パケットを数える時は、カウンタは１しか加算されません。一方、バイト数を数える時は、カウンタは大きい数、加算されることがあります。 なぜこれが重要でしょう？なぜならば、１を加算するケースでは、戻される値は正確です。これは、カウンタはどこかの時間にその値を必ずとっていたことがあるという意味です。いつそれが起きたかは正確にわからないとしてもです。それに対して、バイト数を数えるときは、２つの異なるスレッドはいずれのグローバルな操作のオーダリングとも矛盾する値を返すことがあります。 それを説明するために、スレッド０が自分のカウンタに３を足し、スレッド１が自分のカウンタに５を足し、スレッド２と３がカウンタを合計するとしましょう。システムが「弱いオーダリング」であるか、コンパイラが積極的な最適化を使うなら、スレッド２は合計を３と、スレッド３は合計を５と見ることがあります。カウンタの値のシーケンスの唯一可能なグローバルオーダリングは、０，３，８と０，５，８であり、どちらのオーダリングも得られた結果と矛盾しています。 もしあなたがこれをわからなくても、あなたは一人ではありません。Michael Scot はこの質問で、Paul E. McKenney を、Paul の博士課程の答弁の時につまづかせました。 ５．２７ １つのアプローチは、値のグローバルな近似値を維持することです。リーダーはそれぞれのスレッドごとの値を加算しますが、それが予め決められた限界になったら、それをグローバル変数に足し、自分のスレッドごとの変数をゼロにします。こうすれば加算オーバヘッドの平均と、読まれる値の正確さをトレードオフできます。 読者は、さらに他のアプローチ、例えば、combining tree を使うなどを考え、試みるのをおすすめします。 ５．２８ 構造体の大きさは別々だからです。もちろん、特定の大きさの構造体に対応する限界カウンタは、inc_count() と dec_count() を使うこともできます。 ５．２９ ２語で、「整数オーバーフロー」。 前記の式で、counter が１０、delta が ULONG_MAX を試して下さい。そして、図５．１２に示したコードで同じことをします。 この例の残りでは、整数オーバーフローの正しい理解が必要です。なので、あなたが今まで整数オーバーフローを扱ったことがないならば、いくつかの例をやって、それに慣れて下さい。整数オーバーフローは時には、並列アルゴリズムよりも、正しく行うのは難しいのです！ ５．３０ このコードの昔のバージョンでは確かにそうしていました。しかし、加算と減算はとても安いですし、起きる特殊ケースのすべてを扱うのはとても複雑です。もう一度言いますと、ご自分で試すのは良いことです、ただし、整数オーバーフローに注意！ ５．３１ globalreserve 変数は、すべてのスレッドの countermax 変数の和を追跡します。これらスレッドの counter 変数の和は、ゼロから globalreserve のどこかです。なので、保守的アプローチをとる必要があります。add_count() では、すべてのスレッドの counter 変数は一杯、 sub_count() では、すべて空っぽ、と仮定します。 なお、この質問を覚えておいて下さい。後から、また、ここに来ます。 ５．３２
実際にそうなります！多くの場合、５．３．３節で議論するように、これは問題となります。そういう場合は、５．４節のアルゴリズムの方が望ましいかもしれません。
５．３３
add_count() は、引数に unsigned long を取りますから、それに負数を与えるのはちょっと難しいかもしれません。それに、あなたが反物質メモリか何かを持っているのでない限り、使用中の構造体の数を数えるのに、負数を許すのは意味がありません！
５．３４
まず、それは実際には、countermax 数を確保します。（１４行目を参照。）しかし、その時には、そのうち半分だけが実際にそのスレッドによって使用中であるように調整します。これにより、このスレッドは、もう一度 globalcount を参照しに行く必要が生じる前に、少なくても countermax / 2 の加算あるいは減算を実行できるようになります。
なお globalcount の計算は、１８行目の調整のために正確なままです。
５．３５
これが起きるのは、スレッド０の counter がその countermax の半分に設定されたからです。なので、スレッド０に割り当てられた４／１のうち、その半分（１／８）は globalcount から来ます。残りの半分（これも１／８）は残りのカウントから来ます。 このアプローチを取るのは２つの理由があります。（１）スレッド０が加算と減算で高速パスを使えるようにする。（２）すべてのスレッドが単調増加的に限界まで加算するときの不正確さを減らす。この最後の点を確認するには、アルゴリズムをステップ実行してみて、どうなるか、観察してください。
５．３６ それは可能ですが、特別な注意が必要です。最初に countermax をゼロにしないで、counter を削除すると、対応するスレッドが、counter がゼロになった直後に加算することになり、カウンタをゼロにした効果を完全に無効とします。 逆の順序、つまり、countermax をゼロにしてから counter を削除する場合も、ゼロでない counter になることがあります。これを説明するために、以下のイベントのシーケンスを考えましょう。 １ スレッドAが自分の countermax をフェッチして、ゼロでないことを知る。 ２ スレッドBはスレッドAの countermax をゼロにする。 ３ スレッドBはスレッドAの counter を削除する。 ４ スレッドAは、 countermax がゼロでなかったので、自分の counter に加算しようとする。この結果、 counter はセロでなくなる。 もう一度言いますと、countermax と counter を別々の変数として、アトミックに操作することはできるかもしれませんが、特別な注意が必要なのは明らかです。そうすることで高速パスが遅くなることも十分ありえます。 これらの可能性を調査するのは、読者への課題とします。 ５．３７ １バイトに８ビットあることを前提としています。この仮定は、簡単に共用メモリマルチプロセッサに組み立てることができる、現在一般的なマイクロプロセッサすべてで正しいですが、C 言語を走らせたことのあるすべての計算機システムでは明らかに正しくありません。（C 標準に準拠するためには、その代わりに何をしたらいいでしょう？それはどんな短所を持つでしょう？） ５．３８ ctrandmax 変数は、スレッドごとに、１つだけあります。後で、他のスレッドの ctrandmax 変数を split_ctrandmax() に渡す必要のあるコードを見ます。 ５．３９ 後で、atomic_cmpxchg() プリミティブに渡すためには、 int 戻り値が必要なことを見ます。 ５．４０ goto を break にするには、１５行目が戻るべきかどうかを決めるフラグを維持することが必要です。そういうことは高速パスではやりたくない種類のことのはずです。もしあなたがそれほど goto を憎むなら、高速パスを別の関数に抜き出して、それが成功か失敗かを返すのが最も良いでしょう。「失敗」は、低速パスが必要ということを示します。これは、goto を憎む読者への課題とします。 ５．４１ 後で、図５．２０の flush_local_count() 関数が、このスレッドの ctrandmax 変数を、図５．１８の８から１４行目の高速パスの実行と同時に更新することのある様子を調べます。 ５．４２ この他のスレッドは、flush_local_count() のコール元が gblcnt_mutex を放すまでは、自分の ctrandmax を再設定することはできません。その時までには、flush_local_count() のコール元は、カウントを使い終わっているでしょうから、この他のスレッドが再設定をすることは問題ありません。globalcount の値が、再設定を許すほどに大きいと仮定して。 ５．４３ 何もありません。以下の３つの場合を考えましょう。 １ もし、flush_local_count() の atomic_xchg() が、いずれかの高速パスの split_ctrandmax() より前に実行されたとします。高速パスは、ゼロの counter と countermax を見ます。そして、低速パスに移ります。（もちろん、delta がゼロでない限り。） ２ もし、flush_local_count() の atomic_xchg() が、いずれかの高速パスの split_ctrandmax() より後、かつ、高速パスの atomic_xchg() の前に実行されたとします。すると、atomic_xchg() は失敗し、高速パスは再実行します。そして、前記１の場合になります。 ３ もし、flush_local_count() の atomic_xchg() が、いずれかの高速パスの split_ctrandmax() より後に実行されたとします。すると高速パスは、flush_local_count() がそのスレッドの ctrandmax 変数をゼロにする前に、（普通は）比較を成功します。 どの場合も、競合は正しく解決されます。
５．４４ balance_count() と flush_local_count() のコール元は、どちらも gblcnt_mutex を持っています。なので、一度にどちらかだけしか動きません。 ５．４５ いいえ。シグナルハンドラが他のCPUに移動するときは、割り込まれたスレッドも一緒に移動します。 ５．４６ 高速パスだけが theft 状態を変える事ができることを示すためです。そして、もしスレッドがこの状態に長く居すぎると、低速パスを実行しているスレッドは POSIX シグナルを投げ直すことを示すためです。 ５．４７ REQ と ACK 状態を一緒にするのが悪い考えである理由は、 １ 低速パスは、REQ と ACK 状態を、シグナルを投げ直すべきかを決めるために使います。状態が一緒だと、低速パスは余分なシグナルを投げる以外の選択肢が無いため、高速パスを不要に遅くするという悪い効果があります。 ２ 以下の競合が起きます。
(a) 低速パスがあるスレッドの状態を REQACK にします。 (b) そのスレッドがちょうどその高速パスを終わり、REQACK 状態に気が付きます。 (c) スレッドはシグナルを受け、それも REQACK 状態に気が付きます。そして、高速パスが走ってないので、状態を READY にします。 (d) 低速パスは READY を見て、カウントを盗み、状態を COMPLETE にして終わります。 (e) 高速パスは状態を READY にして、このスレッドの以降の高速パスの実行を不可能にします。ここでの基本的な問題は、結合された REQACK 状態は、シグナルハンドラと高速パスの両方から参照されることがあるということです。４つの状態を使う設定によって維持される明確な分離により、正しい状態遷移が保証されます。 とは言うものの、３つの状態を使う設定を正しく動かすことは可能かもしれません。もし本当にそれができたなら、それを４つの状態の設定と注意深く比べましょう。３状態のソリューションは本当に望ましいですか？なぜですか？
５．４８
最初の方（１１行目にある）は、不要と言えます。後の２つ（１４と１６行目）は重要です。これを削除すると、コンパイラは自分の権限のもとで１４から１７行目をこのように書き換えることができます。 これは、低速パスが THEFT_READY の一時的な値を見て、そのスレッドが準備が整う前に盗みを始めることがあるため、致命的です。 ５．４９ そのほかのスレッドは、gblcnt_mutex ロックを持っていない限り、自分の countermax 変数の値を変えることを許されないからです。しかし、コール元はこのロックを持っています。なので、他のスレッドがそれを取ることはできません。なので、countermax 変数の値は変えられません。このため、安全にそれをアクセスできます。ただし、変更はできません。 ５．５０ 追加のチェックは必要ありません。flush_local_count() のコール元は、既に globalize_count() を呼んでいます。なので、２８行目のチェックは成功したはずで、後の pthread_kill() はスキップされます。
５．５１ シグナルハンドラとシグナルに割り込まれたコードとの間で安全に共有されるためには、theft 変数は、sig_atomic_t 型でないといけません。 ５．５２ 多くのオペレーティングシステムは、数十年にわたって、時々シグナルを失う性質を持ち続けているからです。これが機能なのかバグなのかは議論の余地がありますが、関係無いです。ユーザー視点からの明らかな現象は、カーネルバグではなく、ユーザーアプリケーションのハングです。 あなたのユーザーアプリケーションがハングしてますよ！ ５．５３ １つのアプローチは、５．２．３節に示したテクニックを使うことです。すべてのカウンタ値の近似値を合計して、１つの変数に入れます。他のアプローチは、リードをするのに複数のスレッドを使って、そのそれぞれのスレッドが更新をしているスレッドの特定のサブセットと相互作用するというものです。 ５．５４ １つの単純な解決策は、上限を、好きなだけ大きくすることです。その時に問題となるのは、カウンタが表現できる最大値に上限が限られることです。 ５．５５ 上限値は、バイアスと、アクセスの予想される最大値、そして、アクセスが最大値になってもカウンタが効率的に動くために十分な「余裕」のすべてを入れるのに十分大きく設定するのが良いでしょう。
５．５６ たぶん、変です。しかし、正しい！「リーダーライターロック」という名前がよくないとあなたも思いますよね？ ５．５７ たくさんあります！ 手始めは、こんなところから。 １ デバイスは複数あるでしょう。なので、グローバル変数ではいけません。また、do_io() 関数他には引数が必要です。 ２ 実システムでは、ポーリングループは問題です。多くの場合、最後に完了したI/Oがデバイス削除スレッドを起こすのがずっと良いでしょう。 ３ I/Oは失敗することがあります。do_io() は戻り値があるべきでしょう。 ４ デバイスが障害になったら、最後のI/Oはけっして完了しません。その場合、エラー回復を可能とするためのタイムアウトの類が必要です。 ５ add_count() と sub_count() は失敗することがありますが、それらの戻り値はチェックされていません。 ６ リーダーライターロックは、うまくスケールしません。リードロックの高いコストを回避する１つの方法は、７章と９章にあります。 ７ ポーリングループは、エネルギー効率の点で、問題があります。イベント駆動の設計が望ましいです。
５．５８
リード側コードは、スレッド数によらず、固定長配列全体を走査しないといけません。だから、性能差はありません。それに対して、最後の２つのアルゴリズムでは、スレッドが多いとリーダーはより多くの仕事をしないといけません。さらに、最後の２つのアルゴリズムは、整数のスレッド ID を対応する __thread 変数にマップするために追加のレベルの間接を挿入します。
５．５９
「仕事にあったツールを使うこと」
図５．３でわかるように、単一変数のアトミック加算は並列更新のヘビーな使用を伴う仕事には適用できません。それに対して、表５．１で示したアルゴリズムは、ヘビーな更新の状況を扱う上で素晴らしい仕事をします。もちろん、あなたがリードがほとんどの状況にあるなら、他のものを使うべきです。例えば、５．２．３節で使ったアプローチと同じように、単一のアトミックに加算される変数で、単一のロードを使って読むことができる、結果整合の設計などはどうでしょう。
５．６０
それはワークロードに依存します。６４コアシステムにおいては、１つのシグナル（ほとんど、５マイクロ秒の性能損失）とつりあうためには、１００以上のアトミックでない操作（約４０ナノ秒の性能向上）が必要です。
これよりずっとリードが多いワークロードは他にもいくらもあるでしょうが、あなたは自分の特定のワークロードをよく考える必要があります。 さらに、メモリバリアは歴史的に、通常の命令に比べて高価でしたが、あなたは自分が動かす特定のハードウェアでそれをチェックするべきです。計算機ハードウェアの性質は時間が経つと変わり、アルゴリズムもそれにつれて変わらなくてはいけません。
５．６１
１つのアプローチは、scalable non-zero indicators (SNZI) でやるように、更新側性能をある程度あきらめることです。取り組むことのできる方法は他にもたくさんあります。これは読者への課題とします。頻繁なグローバルロック確保をその階層内のより低いレベルに対応するローカルロック確保に置き換えるという、階層を適用するアプローチはたくさんありますが、どれもとてもうまくいくと思います。
５．６２
C++ 言語では、１０００桁の数字に対して ++ 演算子を使うことができます。そのような数を実装するクラスにアクセスできればです。しかし、２０１０年現在、C 言語は演算子オーバーロードは許していません。
５．６３
たしかに、別々のアドレス空間を持った複数プロセスは並列性を追求する優れた方法かもしれません。それは、フォーク、ジョイン機構と、Erlang 言語の支持者が喜んで教えてくれるでしょう。しかし、共用メモリ並列性にも、いくつか利点があります。
１ 最も性能クリティカルなアプリケーションの部分だけを分割すれば良いです。そして普通は、そのような部分は、アプリケーションのごく一部です。
２ キャッシュミスは、個々のレジスタからレジスタへの命令に比べるととても遅いですが、典型的にはそれはプロセス間通信プリミティブに比べるととても速いです。後者にしても、TCP/IP ネットワーキングのようなものと比べるととても速いといえます。
３ 共用メモリマルチプロセッサは、すぐに入手可能で、とても低価格です。なので、１９９０年代とは全く違って、共用メモリ並列性を使う上での価格ペナルティはほとんどありません。
いつものことですが、仕事にあったツールを使うこと！
F6 分割と同期の設計
６．１ 改善されたそのような解決策の一つを図Ｆ３に示します。単純に、あと５つのフォークを哲学者に与えます。５人全ての哲学者は同時に食べられるようになりました。哲学者がお互いに待つ必要は全くありません。さらに、このアプローチは病気が広がるのも防げます。 この解決策は、ズルをしているように見えるかもしれません。しかし、そのような「ズル」は、多くの同時実行問題への良い解決策を探す時の鍵となります。 ６．２ Inman はプロトコルスタックを研究していました。それは通常は、垂直に描かれます。アプリケーションが一番上にあって、ハードウェアインターコネクトが一番下です。データはこのスタックを上と下に流れます。「水平並列性」は、異なるネットワークコネクションから来るパケットを並列に処理します。そして、「垂直並列性」は、あるパケットの異なるプロトコル処理ステップを並列に処理します。 「垂直並列性」を、「パイプライニング」とも呼びます。 ６．３ この場合、単純に、空でないキューからアイテムをデキューし、両方のロックを放し、戻ります。 ６．４ これに答える最も良い方法は、 lockhdeq.c を多くの異なるマルチプロセッサシステムで走らせることです。そしてあなたは、本当に本当にそうするようにお勧めします。心配となる一つの理由は、この実装のそれぞれの操作は、一つでなく二つのロックを取らないといけないことです。 最初の、良く設計された性能測定研究をあげておきます。 脚注 Dalessandro et al. [DCW+11] と、 Dice et al. [DLM+10] が、良い開始点となるでしょう。 シーケンシャル実装との比較を忘れないように！ ６．５ それは、データフローの方向がほとんど変わらない場合に、最適です。双方向キューが同時に両方の端から空になる場合、それはもちろん、極めて悪い選択です。これはもちろん。もう一つの疑問を引き起こします。つまり、同時に両方の端から空にするのが合理的に考えて行うべきことであるのはいかなる可能な宇宙においてなのでしょう。work-stealing キューは、この問題への一つの可能な回答です。 ６．６ ロック階層を強制することでデッドロックを避ける必要性から、非対称が強制されます。食事をする哲学者問題のフォークを番号付ける解決策でやっていたのと同じです。(６．１．１節を参照) ６．７ このスレッドが２５行目で d->rlock を落としてから、２７行目で同じロックをもう一度取るその間の時間に、どれか他のスレッドが要素をエンキューしたかもしれないので、このリトライが必要です。 ６．８ 左側のロックが空いているなら、 spin_trylock() を使ってそれを取ろうと試みるのは可能でしょう。しかし、失敗した場合は、それでも、右側のロックを放して、それから二つのロックを順に再確保する必要があります。この変更をする(そして、それをする価値があるかを決める)のは、読者への課題とします。 ６．９ ハッシュされた双方向キューのロック設計は、それぞれの端で一度に一つのスレッドだけを許します。そしてさらにそれぞれの操作に二つのロック確保を必要とします。並んだ双方向キューも、それぞれの端で一度に一つのスレッドを許します。そして、一般的な場合は操作に一つのロックしか必要としません。なので、並んだ双方向キューはハッシュされた双方向キューより性能が良いことが期待されます。 それぞれの端で、複数の同時実行する操作を許す双方向キューを作ることはできますか？できるなら、どのように？できないなら、それはなぜ？ ６．１０ 一つのアプローチは、解くべき問題を変形して、複数の双方向キューが並列に使えるようにすることです。そうすれば、より簡単な、単一ロックの双方向キューが使えます。そしてさらに、それぞれの双方向キューを通常の単一終端のキューの組に代えるのも良いかもしれません。そのような「水平スケーリング」なしでは、スピードアップの限界は２です。それに対し、水平スケーリング設計はとても大きなスピードアップを得ることができます。そして、キューの端のどちらかで複数のスレッドが動作しているならば、それは特に魅力的です。なぜならば、この複数スレッドの場合、デキューはそもそも、強いオーダリングの保証を提供できないからです。結局、あるスレッドがアイテムを最初に取り除いたという事実は、それがそのアイテムを最初に処理することを意味しないのです。そして、保証がないのなら、そういう保証を提供することを拒否することで得られる性能上の利益を活用してもいいはずです。 問題を、複数のキューを使うように変形できるかどうかにかかわらず、仕事をまとめて、それぞれのエンキューとデキュー操作がより大きな仕事の単位に対応するようにできないかを問うのは意味のあることです。このまとめアプローチは、キューデータ構造への競合を減らします。それは、６．３節で見るように、性能とスケーラビリティの両方を向上させます。結局、あなたが高い同期オーバヘッドを起こさないわけにはいかないならば、あなたはそれに見合うものを受け取っているのか、よく確認ください。 キューの限定されたオーダリング保証を活用するこれ以外の方法を研究している人もいます。 ６．１１ ノンブロッキング同期がとても便利な場合もありますが、万能薬ではありません。また、ノンブロッキング同期も、実はクリティカルセクションを持ちます。Josh Triplett が指摘した通りです。例えば、コンペアアンドスワップ操作をベースにするノンブロッキングアルゴリズムにおいて、最初のロードで始まって、コンペアアンドスワップに続くコードは、多くの点でロックベースのクリティカルセクションに似ています。 ６．１２ 以下は、この存在保証問題へのいくつかの可能な解法です。 １ 静的に確保されたロックを提供し、構造ごとのロックを取るときにそれを保持します。これは、階層ロック（６．４．２節を参照)の例です。もちろん、この目的のために、単一のグローバルロックを使うと、受け入れがたいほどの高いレベルのロック競合を起こすことになり、性能とスケーラビリティを劇的に落とします。 ２ 静的に確保されたロックの配列を提供し、７章で述べるように、構造体のアドレスをハッシュして、取るロックを選びます。十分に良い質のハッシュ関数を使えば、これは単一グローバルロックのスケーラビリティ限界を避けられます。しかし、リードがほとんどの場合、ロック確保オーバヘッドは受け入れがたいほどの性能低下になるかもしれません。 ３ ガーベッジコレクタがあるソフトウェア環境で、それを使います。そうすれば、構造体は、参照があるうちは解放されません。これはとてもうまくいきます。開発者の肩から存在保証の重荷(それにその他たくさんも)を取り除きます。しかし、プログラムにガーベッジコレクションのオーバヘッドを課します。この数十年でガーベッジコレクション技術は大いに進歩しましたが、アプリケーションによっては、そのオーバヘッドは受け入れがたいほど高いかもしれません。さらに、アプリケーションによっては、開発者がデータ構造のレイアウトと配置に、ほとんどのガーベッジコレクタがある環境が許す以上の制御を自由に振るうことを必要とするものもあります。 ４ ガーベッジコレクタの特殊ケースとして、グローバル参照カウンタあるいは参照カウンタのグローバル配列を使います。 ５ ハザードポインタを使います。それは裏表がひっくり返った参照カウントと考えることができます。ハザードポインタをベースとするアルゴリズムは、スレッドごとにポインタのリストを維持します。これらのリストのどこかに、ある構造へのポインタが現れるかどうかが、その構造の参照として働きます。ハザードポインタは興味深い研究の方向です。しかし、本番ではあまり使われていません(２００８年に記す)。 ６ トランザクションメモリ(TM) を使います。そうすれば、問題のデータ構造へのそれぞれの参照と更新は、アトミックに行われます。TM は、最近大変な熱狂を呼んでおり、本番のソフトウェアでもある程度使われる見込みらしいですが、開発者は注意したほうが良いでしょう。特に、性能クリティカルコードでは。特に、存在保証は、トランザクションが、グローバルな参照から、更新されるデータ要素までの全てのパスをカバーすることを必要とします。 ７ RCUを使います。それは、ガーベッジコレクタの極めて軽量な類似品と思うことができます。RCUリーダーがまだ参照しているかもしれない、RCU保護されたデータ構造を、更新者は解放することが許されません。RCUは、リードがほとんどのデータ構造に対して最も大いに使われており、９章で十分に議論します。 存在保証を提供することについて詳しくは、７章と９章を参照下さい。 ６．１３ matmul.c プログラムは、指定された数のワーカースレッドを作成します。なので、単一のワーカースレッドの場合も、スレッド作成のオーバヘッドが起きます。単一のワーカースレッドの場合に、スレッド作成のオーバヘッドを最適化して除くのに必要な変更をするのは、読者への課題とします。 ６．１４ 気がついてくれて嬉しいです！この例は、データ並列性はとても良いものですが、あらゆる全ての非効率の源を自動的に除去してくれる魔法の杖ではないことを示す役目がありました。「たった」６４スレッドであっても、線形にスケールするフル性能というのは、設計と実装の全てのフェーズで注意が必要です。 特に、分割のサイズには大きな注意が必要です。例えば、６４かける６４行列の掛け算を、６４スレッドに分割したならば、それぞれのスレッドはたった６４回の浮動小数掛け算をするだけです。浮動小数掛け算のコストは、スレッド作成のオーバヘッドと比べると微小です。 教訓：もしあなたが可変の入力を持つ並列プログラムを持つならば、常に、入力サイズが並列化に見合うだけの大きさであるかをチェックしなさい。そして、並列化が役に立たない時は、スレッドを作成するオーバーヘッドを起こすのも役には立ちませんよね？ ６．１５ もし、図６．２６の３１行目の比較が、それよりずっと重量級の操作に置き換わったら、bp->bucket_lock を放すことによってロック競合を減らすことができ、それは、cur->node_lock を余分に確保、解放するオーバーヘッドを上回るかもしれません。 ６．１６ これは、CPU ごとの目的変数が３つあるためです。１２のラン長は、グローバルプールのロックを２回取らないといけません。一方、１３のラン長は、グローバルプールのロックを３回取らないといけません。 ６．１７ この回答は、 Alexey Roytman が発案したものを使っています。以下の定義を使います。 g グローバルに使用可能なブロック数 i 初期化スレッドのスレッドごとプールに残ったブロック数（これが、あなたがコードを見ないといけない理由の一つです！） m 確保／解法のラン長 n スレッド数。初期化スレッドは除く。 p スレッドごとの最大ブロック消費数。実際に確保されたブロックと、スレッドごとプールに残っているブロックを含みます。 g, m, そして n の値は与えられています。p の値は、 m を s の次の倍数に丸めたものです。 i の値は、このとおり。 これらの量の間の関係を図F.4に示します。グローバルプールは、図の一番上です。「余分な」初期化スレッドのスレッドごとプールとスレッドごと確保数は、一番左の箱の対です。初期化スレッドはブロックを確保しませんが、i ブロックを、そのスレッドごとプールに閉じ込めています。右端の２つの箱の対は、最大可能なブロック数を持っているスレッドの、スレッドごとプールと、スレッドごと確保数です。そして、左から２番目の箱の対は、今これから確保しようとしているスレッドを表します。 ブロックの総数は g で、スレッドごとの確保数とスレッドごとプールを合計すると、グローバルプールは、g−i− p(n−1) プールを持っていることがわかります。確保しようとしているスレッドが成功するためには、グローバルプールに少なくても m ブロックが必要です。言葉を代えて言うと、こうです。 質問は、g = 40, s = 3, and n = 2 です。式 F.6 の結果、 i = 4 です。そして式 F.5 の結果、 p = 18 for m = 18 and p = 21 for m = 19 です。これらを式 F.7 に入れると、 m = 18 はオーバーフローしない、しかし、 m = 19 はするかもしれない、とわかります。 i の存在はバグと考えることができます。結局、なぜ、初期化スレッドのキャッシュに閉じ込められるだけのために、メモリを確保するのでしょう？これをなおす一つの手は、memblock_flush() 関数を提供して、現在スレッドのプールをグローバルプールにフラッシュすることでしょう。そして初期化スレッドは全てのブロックを解放した後にこの関数を呼ぶことができます。
訳注
クイッククイズのF7-F9の訳、F10以降の訳を別ページにしました。
以上