以下は、perfbook の5章 カウンティングの kanda.motohiro@gmail.com による全訳です。perfbook の訳の他の部分は、親文書を参照。
5章 カウンティング
カウンティングはたぶん、計算機ができる最も単純で自然なことでしょう。しかし、巨大な共用メモリマルチプロセッサにおいてカウンティングを効率的にスケーラブルに行うのはとても難しいのです。さらに、カウンティングの元になる概念はとても単純なので、私達は、複雑なデータ構造や同期プリミティブに惑わされることなく、同時実行の基本的問題を調べることができます。なので、カウンティングは、並列プログラミングの導入としてとても優れています。 この章では、単純で、高速で、スケーラブルなカウンティングアルゴリズムが存在する特別なケースをいくつか紹介します。しかしその前に、あなたが既に並列カウンティングについてどの程度知っているか確かめましょう。
クイッククイズ5.1:
効率的でスケーラブルなカウンティングが難しいって、なぜですか?結局、計算機はカウンティング、加算、減算などのためだけの特別なハードウエアを持っているではないですか???
クイッククイズ5.2:
ネットワークパケットカウンティング問題 あなたが、送信あるいは受信されるネットワークパケットの数(あるいは合計バイト数)の統計を取る必要があるとします。パケットは、システムのどのCPUでも送信、受信されます。さらに、この巨大マシンは、1秒に100万パケットを扱えます。また、5秒毎に、カウンタを読むシステム監視パケットがあります。あなたは、この統計カウンタをどのように実装しますか?
クイッククイズ5.3:
近似的構造体確保限界問題 あなたが、確保された構造体の数を監視し、使用中の構造体数が限界(10000としましょう。)を超えたら確保を失敗させたいとします。さらに、これらの構造体は短期間だけ存在し、限界はめったに超えられず、そして、「テキトー」な近似的限界は許されるとします。
クイッククイズ5.4:
正確な構造体確保限界問題 あなたが、確保された構造体の数を監視し、使用中の構造体数が限界(また、10000としましょう。)を超えたら確保を失敗させたいとします。さらに、これらの構造体は短期間だけ存在し、限界はめったに超えられず、ほとんど常に、少なくても1つの構造体が使用中である、とします。さらに、このカウンタがゼロになった時を正確に知る必要があるとします。例えば、少なくても1つの構造体が使用中であるとき以外は不要なメモリーを解放するために。
クイッククイズ5.5:
リムーバブルI/Oデバイスのアクセスカウント問題 あなたが、頻繁に使われている大容量リムーバブル記憶デバイスの参照カウントを監視したいとします。ユーザーに、デバイスを外しても安全な時を伝えるためです。このデバイスは、通常の取り外し手続きに従います。つまり、ユーザーがデバイスを取り外したいことを表明し、システムが、ユーザーにそれが安全にできる時を伝えます。
この章の残りは、これらの質問の答えを作っていきます。5.1節は、なぜマルチコアシステムでのカウンティングが自明でないかを問います。5.2節はネットワークパケットカウンティング問題を解くいくつかの方法を探ります。5.3節は近似的構造体確保限界問題を調べます。5.4節は、正確な構造体確保限界問題です。5.5節は、これまでの節で紹介されたいろいろな特別な並列カウンタをどのように使うかを議論します。最後に、5.6節は性能測定結果でこの章をしめくくります。 5.1節と5.2節は入門的な内容で、残りの節はより進んだ学生に適します。
5.1 なぜ並列カウンティングは自明でないか
単純なものから始めましょう。例えば、図5.1(count_nonatomic.c)に示す単純な算数です。ここでは、1行目にカウンタがあり、5行目で加算し、10行目で値を読みます。これ以上簡単なものはないですよね? このアプローチは、リードをたくさんして、ほとんど加算の無い時に、驚くほど速いという利点もあります。小さいシステムで、性能は素晴らしいものです。 ただ、薬の瓶に大きなハエが1ついます。このアプローチはカウントを失うことがあります。私のデュアルコアラップトップで、少し走らせた結果、inc_count() は 100,014,000 回呼ばれましたが、カウンタの最後の値はたったの 52,909,118 でした。近似値というのは、コンピューティングの中でそれなりの位置を占めるものですが、50%を大きく超える正確さが、ほぼ、常に、必要です。
クイッククイズ5.6:
でも、 ++ 演算子は、 x86 add-to-memory 命令を生成するでしょう?そして、CPU キャッシュはこれをアトミックにするはずですよね?
クイッククイズ5.7:
失敗の回数が8桁の精度だということは、あなたがこれを実際にテストしたということですね。バグが目視で簡単にわかる時に、このような自明なプログラムをテストしないといけないのはなぜですか?
正確にカウントする直裁的な方法は、図5.2(count_atomic.c) に示すように、アトミック操作を使うことです。1行目でアトミック変数を定義し、5行目でアトミックに加算し、10行目で読みます。これはアトミックですから、カウントは常に完全です。しかし、これは遅くなります。Intel Core Duo ラップトップで、1つのスレッドが加算しているときには、アトミックでない加算に比べて約6倍、2つのスレッドが加算しているときは10倍以上、遅いです。
脚注
興味深いことに、アトミックでなくカウンタを加算する2つのスレッドは、アトミックにカウンタを加算する2つのスレッドよりも、カウンタをより速く進めます。もちろん、あなたの唯一の目的が、カウンタを速く進めることなら、最も簡単なアプローチは、単純に大きな値をカウンタに設定することです。
とはいえ、より良い性能とスケーラビリティを得るために、正確さの概念を注意深くゆるめたものを使うアルゴリズムの役割というものも、それなりにあるようです。[And91, ACMS03, Ung11]
3章の議論を考えれば、この低性能は驚きではないでしょう。また、図5.3が示すように、CPU 数とスレッド数が増えるにつれて、アトミック加算の性能が落ちるのも当然です。この図で、水平のダッシュ線が x 軸に沿って見えますが、これが、完全にスケーラブルなアルゴリズムの結果得られるはずの理想的性能です。そのようなアルゴリズムでは、ある加算は、シングルスレッドのプログラムの時と同じオーバーヘッドを起こすだけです。1つのグローバル変数へのアトミック加算は明らかに、明確に、理想的とは言えず、CPU が増えるに連れて悪化します。
クイッククイズ5.8:
なぜ、x 軸のダッシュ線は、x = 1 で対角の線と同じにならないのですか?
クイッククイズ5.9:
でも、アトミック加算はそれでも十分に速いです。きついループ内で1つの変数を加算するのは、私にはとても非現実的と思えます。結局、ほとんどのプログラムの実行は、実際に何かをするために行われるべきで、自分の行った加算を数えるだけのためではないはずです!なぜ、こんなことをより速くすることにこだわるのですか?
グローバルアトミック加算に関するもうひとつの観点として、図5.4を見ましょう。それぞれのCPUがあるグローバル変数を加算する機会を得るためには、その変数を保持するキャッシュラインが、図の赤い矢印で示されるようにすべてのCPUを循環しないといけません。それには長い時間がかかり、図5.3に示す低性能につながります。この様子は、図5.5で示したように考えることができます。
以下の節は、高性能なカウンティングを議論します。そこでは、前記の循環に固有の遅延を避けています。
クイッククイズ5.10:
CPU設計者は、単純に加算演算子をデータに送ったらどうですか。そうすれば、加算されるグローバル変数を保持するキャッシュラインを循環させる必要もないでしょう?
5.2 統計的カウンタ
この節は、一般的な特別ケースである統計カウンタを扱います。この場合、カウンタは非常に頻繁に更新されますが、値は読まれないか、あるいはとてもまれに読まれます。これは、クイッククイズ5.2で提示された、ネットワークパケットカウンティング問題を解くのに使われます。
5.2.1 設計
統計カウンティングは、典型的には、スレッド(あるいは、カーネルで実行している時にはCPU)ごとにカウンタを設けて処理されます。それぞれのスレッドは、自分自身のカウンタを更新します。カウンタの合計値は、単純にすべてのスレッドのカウンタを加算して読み出されます。これは、加算が可換で推移的である性質を利用しています。これは、6.3.4節で紹介する、データ所有パターンの例です。
クイッククイズ5.11:
でも、 C の「整数」型が長さが限られているということが、問題を複雑にしませんか?
5.2.2 配列ベースの実装
スレッドごとの変数を提供する1つの方法は、スレッドごとに1つの要素を持つ配列を確保することです。(たぶん、キャッシュアラインされていて、偽の共有を避けるためにパッドされているでしょう。)
クイッククイズ5.12:
配列???でもそれだと、スレッド数が制限されますよね?
そのような配列は、図5.6(count_stat.c) が示すように、スレッドごとのプリミティブにラップすることができます。1行目はスレッドごとのカウンタのセットを持つ配列を定義します。型は long で、名前は、十分創造的に、counter です。
3から6行目はカウンタを加算する関数です。counter 配列から、現在実行中のスレッドの要素を位置づけるために、__get_thread_var() プリミティブを使います。この要素は、対応するスレッドからしか変更されないので、アトミックでない加算で十分です。
8から16行目は、カウンタの合計を読む関数です。現在実行中のすべてのスレッドのリストをたどるために、for_each_thread() プリミティブを使い、そのスレッドのカウンタを得るのに per_thread() プリミティブを使います。ハードウエアは正しくアラインされた long をアトミックにフェッチとストアできますし、gcc は親切にこの能力を活用してくれるので、普通のロードで十分です。特別なアトミック命令は不要です。
クイッククイズ5.13:
そもそも、gcc には、他の選択肢もあるのですか???
クイッククイズ5.14:
図5.6のスレッドごとの counter 変数は、どうやって初期化されますか?
クイッククイズ5.15:
図5.6のコードで、1つ以上のカウンタを許すには、どうしたらいいですか?
このアプローチは、inc_count() を呼ぶ更新スレッドの数が増えても、線形にスケールします。図5.7の緑色の矢印で示すように、その理由は、それぞれのCPUが自分のスレッドの変数を加算するのは高速にでき、高価なクロスシステム通信がいらないためです。こうして、この節で、この章のはじめに提示されたネットワークパケットカウンティング問題は解けました。
クイッククイズ5.16:
リード演算は、スレッドごとの値を足し合わせるのに時間がかかります。そして、その間にもカウンタは変わることがあります。これはつまり、図5.6の read_count() で返される値は、正確ではないということです。カウンタが、単位時間あたり r カウントだけ加算され、read_count() の実行が、∆ 時間単位かかるとします。戻り値の期待される誤差はどれだけですか?
しかし、この素晴らしい更新側スケーラビリティは、スレッド数が多いと、大きなリード側の負担を伴います。次の節では、リード側の負担を減らして、かつ、更新側のスケーラビリティを保つ方法を示します。
5.2.3 結果整合な実装
更新側のスケーラビリティを保ったまま、大いにリード側の性能を向上させる1つの方法は、一貫性の要求を弱めることです。前の節のカウンティングアルゴリズムは、理想的なカウンタが、 read_count() の実行がされる始め付近でとるだろう値と、実行の終わり付近でとるだろう値の間の値を返すことが保証されています。結果整合性 [Vog09] は、より弱い保証を提供します。inc_count() 呼び出しがない場合、read_count() 呼び出しは、最後には、正確なカウントを返します。
結果整合性を使うには、グローバルカウンタを維持します。しかし、更新者は、スレッドごとのカウンタだけを操作します。別のスレッドが、スレッドごとのカウンタをグローバルカウンタに転送するために存在します。リーダーは、単純に、グローバルカウンタの値をアクセスします。更新者がアクティブならば、リーダが使う値は古いものです。しかし、更新が終わったらグローバルカウンタは最終的には真の値に収束していきます。なので、このアプローチは、結果整合性と呼ばれます。
図5.8 (count_stat_eventual.c) に実装を示します。1から2行目はスレッドごとの変数と、グローバル変数で、カウンタの値をトラックします。3行目は stopflag で、停止を調停します。(正確なカウンタ値でプログラムを停止したい時のためです。)5から8行目の inc_count() 関数は図5.6のものと似ています。10から13行目の read_count() 関数は、単純に global_count 変数の値を返します。
しかし、34から42行目の count_init() 関数は、15から32行目に示す eventual() スレッドを作成し、それがすべてのスレッドを回って、スレッドごとのローカル counter を加算して、合計を global_count 変数に格納します。eventual() スレッドは、任意に選ばれた1ミリ秒待って、繰り返します。44から50行目の count_cleanup() 関数は、停止を調停します。
このアプローチは、とても速いカウンタリードを提供し、しかも、線形のカウンタ更新性能をサポートします。しかし、この素晴らしいリード側性能と更新側スケーラビリティは、 eventual() を実行する追加のスレッドのコストを伴います。
クイッククイズ5.17:
なぜ、図5.8の inc_count() はアトミック命令を使わないでよいのですか?結局、今の場合、複数スレッドがスレッドごとのカウンタをアクセスしていますよね!
クイッククイズ5.18:
図5.8の eventual() を実行する単一のグローバルスレッドは、グローバルロックと同じようにシビアなボトルネックになるのではないですか?
クイッククイズ5.19:
図5.8の read_count() が返す推定値は、スレッド数が増えるに連れてどんどん不正確になっていくのではないですか?
クイッククイズ5.20:
図5.8の結果整合アルゴリズムでは、リードも更新も、とても低オーバーヘッドであり、極めてスケーラブルです。5.2.2節で述べたような実装は、リード側コードが高価ですから、そんなものはいらないのではないですか?
5.2.4 スレッドごと変数ベースの実装
幸い、 gcc は __thread 記憶域クラスを提供し、これはスレッドごとの記憶域です。これを使って、図5.9(count_end.c) に示すように、スケールするだけでなく、単純なアトミックでない加算に比べてごくわずかあるいは全く性能低下のない統計的カウンタを実装することができます。
1から4行目は必要な変数を定義します。counter は、スレッドごとのカウンタ変数、counterp[] 配列は、スレッドが互いのカウンタをアクセス可能にします。finalcount は、それぞれのスレッドが終了するときに合計を蓄積します。そして、final_mutex は、スレッドがカウンタの合計値を蓄積するときと、終了するときに調停をします。
クイッククイズ5.21:
なぜ、他のスレッドのカウンタを探すのに明示的な配列を必要とするのですか?なぜ、gcc は Linux カーネルの per_cpu() プリミティブのような per_thread() インタフェースを提供しないのですか?そうすれば、スレッドは他のスレッドの変数をより簡単にアクセスできるでしょう。
更新者が使う inc_count() 関数はとても簡単で、6から9行目にあります。
リーダーが使う read_count() 関数は少し複雑です。16行目で終了するスレッドを排他するためにロックを取ります。21行目で放します。17行目は合計を、既に終了したスレッドの蓄積した値に初期化します。18から20行目で現在実行中のスレッドの蓄積しつつあるカウンタを合計します。最後に、22行目で合計を返します。
クイッククイズ5.22:
図5.9の19行目の NULL チェックは余計な分岐予測の失敗を増やすだけでないですか?恒久的にゼロである変数を持って、未使用のカウンタのポインタを、その変数を指すようにしたらどうですか。NULL を設定するより良いと思いますが。
クイッククイズ5.23:
図5.9の read_count() 関数で、ロックのように重いものを使って合計を保護しないといけないのはいったいぜんたいなぜですか?
25から32行は、count_register_thread() 関数です。これは、それぞれのスレッドが、このカウンタを最初に使う前に呼ばれなくてはいけません。この関数は、単に、counterp[] 配列のこのスレッドの要素を、そのスレッドごとの counter 変数にポイントさせます。
クイッククイズ5.24:
図5.9の count_register_thread() で、ロックをとらないといけないのは、いったいぜんたいなぜですか?それは、単一の適切にアラインされたマシンワード記憶域で、他のスレッドは変更しない位置を指しています。なので、どうやってもアトミックですよね?
34から42行目は、count_unregister_thread() 関数です。これは、以前に count_register_thread() を呼んだスレッドが終了するときに呼ばなくてはいけません。38行目はロックを取り、41行目で放します。そうして、他の read_count() と、 count_unregister_thread() の呼び出しを排他します。39行目でこのスレッドの counter をグローバルな finalcount に加え、40行目で自分の counterp[] 配列エントリを NULL にします。以降の read_count() 呼び出しは、終了したスレッドのカウントをグローバルな finalcountで見て、counterp[] 配列を走査するときは終了したスレッドをスキップします。こうして、正しい合計を得ます。
このアプローチは、アトミックでない加算とほぼ同じ性能で更新ができます。線形にスケールもします。一方、同時実行するリードは単一のグローバルロックで競合するので、性能は低く、スケーラビリティはひどいものです。しかし、これは、統計カウンタにとっては問題ではありません。加算はひんぱんに、リードはほとんど起きないからです。もちろん、このアプローチは配列ベースのスキーマに比べてかなり複雑です。これは、それぞれのスレッドのスレッドごとの変数は、スレッドが終わるときに消滅するためです。
クイッククイズ5.25:
けっこう。しかし、Linux カーネルでは、CPUごとのカウンタの合計を読むときに、ロックを取る必要はありません。なので、なぜ、ユーザ空間のコードはこれが必要なのです???
5.2.5 議論
これらの3つの実装は、並列マシンで実行しても、ユニプロセッサの性能を得ることが可能だということを示しました。
クイッククイズ5.26:
パケットの長さがまちまちのとき、パケットの数を数えるのと、パケットのバイト数の合計を数えるのとで、何か、基本的な差がありますか?
クイッククイズ5.27:
リーダーはすべてのスレッドのカウンタを合計しないといけないので、スレッドがたくさんあると、時間がかかります。加算操作を、速く、スケーラブルとしたままで、リーダーも適当な性能とスケーラビリティを得る方法は無いでしょうか?
この節で説明したことを使えば、あなたはこの章の最初で示した、ネットワーキングの統計カウンタに関するクイッククイズに答えることができると思います。
5.3 近似的限界カウンタ
もう一つのカウンティングの特別ケースは、限界チェックに関係あります。例えば、クイッククイズ5.3の近似的構造体確保限界問題で述べたように、あなたが確保された構造体の数を監視して、使用中の構造体数が、限界、今の場合、10000を超えたならばそれ以上の確保を失敗させる必要があるとします。さらに、これらの構造体は短期間だけ存在し、限界はめったに超えられないとします。また、この限界は近似的で、たまに、少しの数であれば、限界を超えることがあっても良いとします。(そうでなくて、正確な限界が必要なときは、5.4節を参照。)
5.3.1 設計
限界値カウンタの1つの可能な設計は、10000の限界を、スレッドの数で分けて、それぞれのスレッドに構造体の固定数のプールを与えることです。例えば、100スレッドがあれば、それぞれのスレッドは自分の100スレッドのプールを管理します。このアプローチは単純で、ある場合にはうまくいきます。しかし、これだと、ある構造体があるスレッドで確保され、別のスレッドで解放されるという一般的なケースを扱えません [MS93]。一方で、あるスレッドがそれが解放した構造体の分だけ割り当て値を得るとすると、確保を主にするスレッドは構造体を使い尽くしてしまいますし、解放を主にするスレッドは使い切れない割り当て値を持つことになります。そうでなくて、解放された構造体は、それを確保したCPUの割り当て値に寄与することにすると、CPUが互いのカウンタを操作する必要が生じ、それは高価なアトミック命令か、その他のスレッド間の通信手段を必要とします。
脚注
とはいえ、もしそれぞれの構造体が常に、それを確保したのと同じCPU(あるいはスレッド)によって解放されるなら、この単純な分割アプローチは素晴らしくうまくいきます。
つまり、多くの重要なワークロードにおいて、カウンタを完全に分割することはできないのです。5.2節で議論した3つのスキーマにおいて、カウンタの分割は素晴らしい更新側性能をもたらしたものであることを考えると、悲観的になるかもしれません。しかし、5.2.3節で述べた結果整合アルゴリズムが、面白いヒントを与えてくれます。このアルゴリズムは、2つの帳簿のセットを維持したことを思い出してください。スレッドごとの counter 変数を更新用に、global_count 変数をリーダーに。そして、eventual() スレッドが定期的に、スレッドごとの counter の値と結果的に同じであるように、 global_count を更新しました。スレッドごとの counter はカウンタ値を完全に分割し、global_count は総和を維持しました。
限界カウンタにおいても、この主題の変種を使うことができます。そこでは、カウンタを部分的に分割します。例えば、4つのスレッドのそれぞれはスレッドごとの counter を持ちますが、それぞれは同時に、スレッドごとの最大値も持ちます。(countermax と呼びます。)
しかし、あるスレッドが自分の counter を加算したい時に、 counter が countermax に等しかったら、どうなるでしょう?ここでのトリックは、スレッドの counter 値の半分を global_count に移動し、それから counter を加算することです。例えば、あるスレッドの counter と countermax がいずれも10とします。以下のようになります。
1 グローバルロックを得る。
2 5を、global_count に足す。
3 加算を埋め合わせるために、このスレッドの counter から5を引く。
4 グローバルロックを放す。
5 このスレッドの counter を加算する。値はこの結果、6になる。
この手続きは、グローバルロックを必要としますが、ロックは5回めの加算ごとに確保する必要があるだけでそのロックのレベルの競合は大きく減らせます。この競合は、 countermax を大きくすれば、いくらでも減らすことができます。しかし、 countermax 値を増やすことに対応するペナルティは、global_count の正確さが落ちることです。例えば、4CPUシステムで countermax が10に等しい時、global_count の誤差は最大で40カウントです。それに対して、countermax が100に増えると、global_count の誤差は最大で400カウントです。
こうなると、global_count のカウンタ合計値からの誤差をどこまで許すかという問題が明らかになります。カウンタ合計値とは、global_count とそれぞれのスレッドの counter 値の合計です。その問題の答えは、合計値がカウンタの限界値(globalcountmax と呼びましょう)からどれだけ離れているかに依存します。これら2つの値の差が大きければ、より大きな countermax であっても、globalcountmax 限界を超える危険をおかすことはありません。これはつまり、あるスレッドの countermax 値はこの差を元に設定されることができるということです。限界から離れている時は、スレッドごとの countermax 値は大きくして、性能とスケーラビリティを最適化します。そして、限界値に近くなったら、これを小さくして、 globalcountmax 限界値のチェックの誤差を小さくします。
この設計は、並列高速パスの例です。それは、重要なデザインパターンであり、そこでは一般的なケースは高価な命令やスレッド間の相互作用なしに実行されますが、まれなケースではより保守的に設計された(そして高いオーバーヘッドの)グローバルアルゴリズムを使うというものです。このデザインパターンについては、6.4節でより詳しく扱います。
5.3.2 単純な限界カウンタの実装
図5.10は、この実装で使うスレッドごととグローバルな変数を両方示します。スレッドごとの counter と countermax 変数は、それぞれ、そのスレッドのローカルカウンタと、そのカウンタの上限です。3行目の globalcountmax 変数は、カウンタの総計の上限で、4行目の globalcount 変数はグローバルカウンタです。globalcount と、それぞれのスレッドの counter の合計が、カウンタの全体の総計です。5行目の globalreserve 変数は、スレッドごとの変数 countermax 変数の合計です。これらの変数の関係を、図5.11に示します。
1 globalcount と globalreserve の和は、globalcountmax 以下でなくてはいけません。
2 すべてのスレッドの countermax 値の合計は、globalreserve 以下でなくてはいけません。
3 それぞれのスレッドの counter は、そのスレッドの countermax 以下でなくてはいけません。
counterp[] 配列のそれぞれの要素は対応するスレッドの counter 変数を指します。そして最後に、 gblcnt_mutex スピンロックが、すべてのグローバル変数を守ります。ということは、スレッドは、グローバル変数をアクセスあるいは変更するためには、gblcnt_mutex ロックをとらないといけません。
図5.12は、add_count(), sub_count(), そして read_count() 関数です。 (count_lim.c)
クイッククイズ5.28:
なぜ、図5.12は、5.2節にあった inc_count() と dec_count() インタフェースでなくて、add_count() と sub_count() を使うのですか?
1から18行目は add_count() です。指定された値 delta を counter に足します。3行目でこのスレッドの counter に delta が入るかを見ます。よければ、4行目でそれを足して、6行目で成功を返します。これが、add_count() の高速パスです。ここでは、アトミック操作はせず、スレッドごとの変数だけを参照し、キャッシュミスは起こさないはずです。
クイッククイズ5.29:
図5.12の、3行目の変な条件の形はなんですか?なぜ、以下の様に直感的な高速パスの形にしないのですか?
3行目のテストが失敗したら、グローバル変数をアクセスしないといけません。なので、7行目で gblcnt_mutex をとらないといけません。それを放すのは、11行目の失敗ケースと、16行目の成功ケースです。8行目は、図5.13に示す globalize_count() を呼びます。それは、スレッドローカル変数をクリアして、必要に応じてグローバル変数を調整し、グローバル処理を簡単にします。(でも、私のいうことを信じないで、自分でコーディングしてみて下さいね!)
9と10行目は delta を足せるかをを見ます。つまり、小なり記号の前の式の意味は、図5.11で、2つの赤い(左端の)棒の高さの差です。もし、delta の加算を収容できない場合、11行目で、(以前に述べたように)gblcnt_mutex を放して、12行目で失敗を返します。
そうでないときは、遅いパスを取ります。14行目で delta を globalcount に足し、15行目で balance_count() (図5.13にあります)を呼び、グローバルとスレッドごとの変数を更新します。この balance_count() 呼び出しの結果、普通は、スレッドの countermax が、高速パスが有効になるように設定されます。16行目で gblcnt_mutex を放して、(これも以前に述べたように)最後に、17行目で成功を返します。
クイッククイズ5.30:
なぜ、図5.12で globalize_count() はスレッドごとの変数をゼロにするのですか?どうせ後で、balance_count() を呼んで、設定し直すのに。なぜ、スレッドごとの変数をゼロ以外のままにしておかないのですか?
20から36行目は sub_count() で、指定された delta をカウンタから引きます。22行目で、スレッドごとのカウンタがこの減算を受け入れられるかをチェックし、そうならば、23行目で減算をし、24行目で成功を返します。これらの行が、 sub_count() の高速パスです。add_count() の時と同じように、高速パスは高価な操作はしません。
高速パスで、 delta の減算ができないときは、26から35行目の低速パスに実行が進みます。低速パスはグローバル状態をアクセスしなくてはいけないので、26行目で gblcnt_mutex をとります。これは、29行目(失敗の時)あるいは34行目(成功の時)に放します。27行目は図5.13に示す globalize_count() を呼びます。これも、スレッドローカル変数をクリアして、グローバル変数を必要に応じて調整します。28行目でカウンタが delta の減算を受け入れられるかをチェックし、そうでないときは、29行目で gblcnt_mutex を放して、(前に述べたように)30行目で失敗を返します。
クイッククイズ5.31:
なぜ、図5.12で、add_count() では、globalreserve を見ているのに、sub_count() ではそれを見ないでいいのでしょう?
クイッククイズ5.32:
図5.12で、あるスレッドが add_count() を呼んで、他のスレッドが sub_count() を呼んだとします。sub_count() は、カウンタの値がゼロでないにもかかわらず、失敗しませんか?
一方、もし28行目でカウンタが delta の減算を受け入れられるなら、低速パスは終わりです。32行目で減算をして、33行目で balance_count() を呼び、(図5.13にあります。)グローバルとスレッドごとの変数を更新します。(できれば、高速パスを再度、有効にします。)34行目で gblcnt_mutex を放して、35行目で成功を返します。
クイッククイズ5.33:
図5.12には、なぜ、add_count() と sub_count() の両方があるのですか?add_count() に単純に負数を渡したらどうですか?
38から50行目は read_count() で、カウンタの合計値を返します。43行目で gblcnt_mutex を取って、48行目で放します。グローバルな操作を、add_count() と sub_count() から排他します。また、いすれ見るように、スレッド作成と終了とも排他します。44行目はローカル変数 sum を、globalcount の値に初期化して、45から47行目にあるループが、スレッドごとの counter 変数を合計します。49行目で sum を返します。
図5.13は、図5.12の add_count() 、sub_count() 、read_count() で使われるユーティリティ関数がいくつかあります。
1から7行目は、globalize_count() で、現在のスレッドのスレッドごとのカウンタをゼロにし、グローバル変数を適切に調整します。この関数は、カウンタの合計値を変えずに、カウンタの現在値がどう表現されるかだけを変えることに注意するのは重要です。3行目でスレッドの counter 変数を globalcount に足し、4行目で counter をゼロにします。同様に、5行目はスレッドごとの countermax を globalreserve から引き、6行目で countermax をゼロにします。この関数と、次の balance_count() を読むときは、図5.11を参照すると良いです。
9から19行目は balance_count() で、ほぼ、globalize_count() の逆です。この関数の仕事は、現在スレッドの countermax 変数を、カウンタが globalcountmax 限界値を超える危険をおかすことのない最大値に設定することです。現在スレッドの countermax 変数を変えるのは、当然、対応する、counter, globalcount と globalreserve を調整する必要があります。それは、図5.11に戻って見れば、わかります。こうすることで、balance_count() は、add_count() と sub_count() の低オーバーヘッドの高速パスの使用を最大化します。globalize_count() と同様に、 balance_count() はカウンタの合計値を変えることは許されません。
11から13行は、このスレッドの globalcountmax の割り当て分のうち、既に globalcount あるいは globalreserve でカバーされていない部分を計算します。そして、計算結果をこのスレッドの countermax に設定します。14行目は、globalreserve に対応する調整をします。15行目は、このスレッドの counter を、ゼロから、countermax までの中間値とします。16行目で globalcount が確かにこの counter 値を受け入れられるかを見て、そうでなければ、17行目で counter をそのように減らします。最後に、いずれの場合も、18行目で globalcount に対応する調整をします。
クイッククイズ5.34:
図5.13の15行目で、counter を countermax / 2 にするのはなぜですか?countermax カウントにするほうが、簡単でないですか?
図5.14に、globalize_count() と、その後の balance_count の実行によって、カウンタの関係が、どのように変わるかを図式で示しましたから、見てもらうとよいでしょう。時間は、左から右に流れます。最も左の構成が、ほぼ、図5.11のものです。中心の構成は、スレッド0が globalize_count() を実行した後の、同じカウンタの関係を示します。図でわかるように、スレッド0の counter (図では“c 0” ) が、globalcount に足され、globalreserve からは同じ値が引かれています。スレッド0の counter と countermax (図では“cm 0” )は、ゼロになっています。他の3つのスレッドのカウンタは変わっていません。この変更は、左端と中心の構成をつなぐ、一番下の点線で示されるカウンタの全体の値には影響を与えないことに注意ください。つまり、どちらの構成でも、globalcount と、4つのスレッドの counter 変数の和は同じです。同様に、この変更は、上の点線で示される、globalcount と globalreserve の和にも影響を与えません。
一番右の構成は、同じくスレッド0が balance_count() を実行した後の、これらのカウンタの関係を示します。3つのすべての構成から上に伸びる垂直線で示される、残りのカウントの1/4が、スレッド0の countermax に加えられ、その半分がスレッド0の counter に加えられます。 スレッド0の counter に加えられた分は、globalcount から引かれます。これは、カウンタの全体の値(それは、前と同じく、globalcount と3つのスレッドの counter 値の和です。)を変えないためです。カウンタの全体の値は、中心と右端の構成をつなぐ、2つの点線のうち、下の方で示されます。globalreserve 変数も調整され、この変数が、4つのスレッドの countermax 値の合計に等しくあり続けるようにされます。スレッド0の counterは、それの countermax より小さいので、スレッド0は、もう一度、カウンタをローカルに加算することができます。
クイッククイズ5.35:
図5.14で、残りのカウントの1/4から限界値までがスレッド0にアサインされていますが、残りのカウントの1/8だけしか使われていません。これは、中心と右端の構成をつなぐ、上の点線で示されています。これはなぜでしょう?
21から28行目は、count_register_thread() で、新しく作られたスレッドで状態を設定します。この関数は単純に、新しく作られたスレッドの counter 変数へのポインタを、対応する counterp[] 配列のエントリに、gblcnt_mutex の元で設定します。
最後に、30から38行目は count_unregister_thread() で、終了しつつあるスレッドの状態を後始末します。34行目で gblcnt_mutex を取って、37行目で放します。35行目は globalize_count() を呼んで、このスレッドのカウンタ状態をクリアし、36行目で counterp[] 配列のこのスレッドのエントリをクリアします。
5.3.3 単純な限界カウンタの議論
このタイプのカウンタは、合計値がゼロに近い時、とても速いです。add_count() と sub_count() の両方の高速パスにある、比較と分岐によるわずかなオーバーヘッドがあるだけです。しかし、スレッドごとの countermax 予約を使うということは、add_count() はカウンタの合計値が、globalcountmax の近くにないときでも失敗することがあるということです。同様に、sub_count() も、カウンタの合計値がゼロの近くにないときでも失敗することがあります。
多くの場合、これは許容できません。globalcountmax が近似的限界値としてあるといっても、通常は、どの程度の近似までが許されるかという限界があります。近似の度合いを制限する1つの方法は、スレッドごとの countermax インスタンスの値に、上限を強制することです。次の節でこれをやりましょう。
5.3.4 近似的限界カウンタの実装
この実装 (count_lim_app.c) は、前の節(図5.10,5.12そして5.13)ととても似ているので、ここでは違いだけを示します。図5.15は図5.10と同じですが、MAX_COUNTERMAX が追加されています。これは、スレッドごとの countermax 変数の、上限を強制します。
5.3.5 近似的限界カウンタの議論
この変更は、前のバージョンで見られた、限界の不正確さを大いに減らします。しかし、別の問題を起こします。どんな MAX_COUNTERMAX 値をとっても、ワークロードに依存する割合のアクセスが、高速パスを通らなくなります。スレッド数が増すと、高速パスでない実行は性能とスケーラビリティの両方の問題を起こします。しかし、この問題は置いといて、その代わりに正確な限界値のカウンタに移りましょう。
5.4 正確な限界値のカウンタ
クイッククイズ5.4で述べた、正確な構造体確保限界問題を解くために、限界がいつ、越えられたのかを正確に知ることのできる限界カウンタが必要です。そのような限界カウンタを実装する1つの方法は、カウントを予約していたスレッドにそれを返させることです。それを行う1つの方法は、アトミック命令を使うことです。もちろん、アトミック命令は高速パスを遅くしますが、まあ、やってみないことにはわかりません。
5.4.1 アトミック限界カウンタ実装
不幸なことに、あるスレッドが他のスレッドから、安全にカウントを除くためには、両方のスレッドがアトミックに、そのスレッドの counter と countermax 変数を操作する必要があります。これをやる普通の方法は、2つの変数を1つの変数にまとめることです。例えば、32ビット変数であれば、高位の16ビットを counter にして、低位16ビットを countermax を表すようにします。
クイッククイズ5.36:
なぜ、スレッドの counter と countermax 変数を、1ユニットとしてアトミックに操作する必要がありますか?それぞれを、アトミックに操作すれば十分でないですか?
図5.17 (count_lim_atomic.c)に、単純なアトミック限界カウンタの変数とアクセス関数を示します。以前のアルゴリズムにあった counter と countermax 変数は、1行目にある1つの変数、ctrandmax に結合されています。counter が、上半分、countermax が下半分にあります。この変数は、atomic_t 型であり、元となる表現は int です。
2から6行目は、globalcountmax, globalcount, globalreserve,
counterp, そして gblcnt_mutex の定義です。いずれも、図5.15のそれらに対応するものに類似の役をはたします。7行目は CM_BITS の定義で、ctrandmax の上と下半分のビット数です。8行目は MAX_COUNTERMAX で、ctrandmax の半分に格納することのできる最大値です。
クイッククイズ5.37:
図5.17の7行目は、どのへんが、C 標準違反でしょうか?
10から15行目は、split_ctrandmax_int() 関数で、atomic_t ctrandmax 変数の元となる int を得て、counter (c) と countermax (cm) コンポーネントに分割します。13行目は、 int の上位半分を分離して、結果を引数 c の指すところに入れます。14行目は、同じ int の下位半分を分離して、結果を引数 cm の指すところに入れます。
17から25行目は split_ctrandmax() 関数です。21行目で、指定された変数から、元となる int を得て、23行目で、 old 引数の指すところに入れます。そして24行目で、split_ctrandmax_int() を呼んで分割します。
クイッククイズ5.38:
図5.17の18行目で、ctrandmax 変数は1つしか無いのに、わざわざそれへのポインタを渡すのはなぜですか?
27から33行目は、merge_ctrandmax() 関数で、split_ctrandmax() の逆と考えることができます。31行目は c と cm で渡された counter と countermax 値をマージして、結果を返します。
クイッククイズ5.39:
図5.17の merge_ctrandmax() は、なぜ、直接 atomic_t に格納するのでなくて、 int を返すのでしょう?
図5.18は、 add_count(), sub_count(), そして read_count() 関数です。
1から32行目は、add_count() です。その高速パスは8から15行目で、残りは低速パスです。高速パスの8から14行目は、 compare-and-swap (CAS) ループを構成します。13と14行目の atomic_cmpxchg() プリミティブが、実際の CAS をします。9行目は現在スレッドの ctrandmax 変数を、その counter (c に) と countermax (cm に)に分割します。そして、元となる int を old に入れます。10行目で、delta 量がローカルに扱えるかを(整数オーバーフローを起こさないように注意して)判定し、もしだめなら、11行目で低速パスに移ります。そうでなければ、12行目で、更新された counter 値を、元の countermax 値と結合して、 new に入れます。13と14行目の atomic_cmpxchg() プリミティブは、このスレッドの ctrandmax 変数と old をアトミックに比較して、比較が成功したなら、new を設定します。比較が成功したら、15行目で成功を返し、そうでなければ、9行目のループに戻ります。
クイッククイズ5.40:
イエーイ!図5.18の11行目のみにくい goto はなぜですか?break 文って、聞いたこと無いの???
クイッククイズ5.41:
図5.18の13と14行目の atomic_cmpxchg() プリミティブが失敗するって、ありえますか?結局、9行目で元の値を拾って、変更してないはずですよね!
図5.18の16から31行目は、 add_count() の低速パスです。それは、gblcnt_mutex で守られます。17行目で取って、24と30行目で放します。18行目は globalize_count() を呼びます。これが、このスレッドの状態をグローバルなカウンタに移動します。19と20行目は現在の状態に delta 値が収まるかを見ます。ダメなら、21行目で flush_local_count() を呼んで、すべてのスレッドのローカルな状態をグローバルカウンタにフラッシュします。そして、22と23行目で、delta 値が収まるかもう一度見ます。それでもなお、delta 値が加算できない時は、24行目で gblcnt_mutex を放して、(以前に言ったように)25行目で失敗を返します。
そうでない時は、28行目で delta をグローバルカウンタに足して、29行目で、必要があればカウントをローカル状態に反映させます。30行目で gblcnt_mutex を放して、(やはり以前に言ったように)最後に31行目で成功を返します。
図5.18の34行から63行目は、sub_count() です。add_count() と似た構造です。41から48行目に高速パスがあり、49から62行目に低速パスがあります。この関数を1行ずつ調べるのは、読者への課題とします。
図5.19は、read_count()です。9行目で gblcnt_mutex を取って、16行目で放します。10行目で、ローカル変数 sum の値を globalcount に初期化します。11から15行目にあるループが、スレッドごとのカウンタをこの合計値に加えます。13行目で、それぞれのスレッドごとのカウンタを split_ctrandmax を使って取り出します。最後に、17行目で合計値を返します。
図5.20と5.21はユーティリティ関数 globalize_count(), flush_local_count(), balance_count(), count_register_thread(), そして count_unregister_thread() です。globalize_count() のコードは図5.20の1から12行にあります。以前のアルゴリズムで使ったものと似ています。ただ、7行目で、ctrandmax から counter と countermax を取り出すところが違います。
flush_local_count() のコードは4から32行目で、すべてのスレッドのローカルカウンタ状態をグローバルカウンタに移動します。22行目で、globalreserve の値がスレッドごとのカウンタを許すかを見て、だめな時は、23行目で戻ります。そうでない時は、24行目でローカル変数 zero を、ゼロにした counter と countermax を結合させたものに初期化します。25から31行目にあるループはそれぞれのスレッドをまわります。26行目で、現在のスレッドがカウンタ状態を持つかを見て、そうならば、27から30行でその状態をグローバルカウンタに移動します。27行目で現在スレッドの状態を、アトミックにフェッチしてゼロと入れ替えます。28行目はこの状態を counter (ローカル変数 c) と countermax (ローカル変数 cm) コンポーネントに分離します。29行目でこのスレッドの counter を globalcount に足し、30行目でこのスレッドの countermax を globalreserve から引きます。
クイッククイズ5.42:
図5.20の14行目にある flush_local_count() で ctrandmax 変数をゼロにした後、すぐに、そのスレッドがまた ctrandmax を設定するのを止めるものはありますか?
クイッククイズ5.43:
図5.20の27行目で flush_local_count() が ctrandmax 変数をゼロにしている時に、同時実行する高速パスの add_count() あるいは sub_count() が ctrandmax をアクセスして干渉するのを防ぐものはありますか?
図5.21の1から22行目は、balance_count() のコードです。これは、呼び出し元スレッドのローカル変数 ctrandmax を入れます。この関数は、以前のアルゴリズムで使ったものととても似ています。マージされた ctrandmax 変数を扱うための変更があるだけです。コードの詳細な調査は、読者への課題とします。24行目から始まる count_register_thread() 関数と、33行目から始まる count_unregister_thread() 関数も同様です。
クイッククイズ5.44:
atomic_set() プリミティブは、指定された atomic_t に単純なストアをするだけです。なぜ、図5.21の21行目の balance_count() が、同時実行する flush_local_count() がこの変数を更新しても正しく動作できるのはなぜですか?
次の節は、この設計の定性的評価です。
5.4.2 アトミック限界カウンタの議論
これは、カウンタがその限界の両方まできっちり数えることのできる最初の実装です。しかし、それには高速パスにアトミック操作を加えるという代償を払っています。その結果、システムによっては高速パスが大いに遅くなります。負荷によってはこの遅延が許容されるかもしれませんが、より良いリード側性能のアルゴリズムを探すのは意味のあることでしょう。そのようなアルゴリズムの1つは、他のスレッドからカウントを奪うのに、シグナルハンドラを使います。シグナルハンドラは、シグナルを受けたスレッドのコンテキストで動きますからアトミック操作は必要有りません。続きは次の節で。
クイッククイズ5.45:
でも、シグナルハンドラは動作中にどこか他のCPUに移動することがあります。この結果、シグナルハンドラと、それが割り込んだスレッドとの間できちんと対話するためには、アトミック命令とメモリーバリアが必要だということになりませんか?
5.4.3 シグナル泥棒限界カウンタの設計
今回は、スレッドごとの状態はそのスレッドによってだけ操作されますが、シグナルハンドラとの同期がまだ、必要です。この同期を、図5.22に示す状態マシンで示します。状態マシンは、IDLE 状態で始まり、add_count() あるいは sub_count() が、ローカルスレッドのカウントとグローバルなカウントの組み合わせが、要求を満たすことができないと判断した時、対応する低速パスが、それぞれのスレッドの theft 状態を REQ にします。(そのスレッドがカウントを持たない時を除きます。その場合、直接、READY に遷移します。)gblcnt_mutex ロックを持っている低速パスだけが、 IDLE 状態から遷移することが許されます。これは図で緑色で示されます。
脚注
この本の白黒バージョンをお持ちの方に申し上げますが、IDLE と READY は緑色、 REQ は赤色、そして ACK は青色です。
低速パスは、次に、それぞれのスレッドにシグナルを送り、対応するシグナルハンドラは、そのスレッドの theft と counting 変数を調べます。theft 状態が REQ でない時は、シグナルハンドラは状態を変更することが許されないので、リターンします。そうでない時は、counting 変数が設定されているなら、それは現在のスレッドの高速パスが実行中であるということなので、シグナルハンドラは theft 状態を ACK にします。そうでない時は、 READY にします。
theft 状態が ACK ならば、高速パスだけが theft 状態を変えることが許されます。これは、図で青色で示されます。高速パスが終わったら、それは theft 状態を READY にします。
低速パスがスレッドの theft 状態が READY であることに気づいたら、低速パスはスレッドのカウントを盗むことが許されます。低速パスは、次にスレッドの theft 状態を IDLE にします。
クイッククイズ5.46:
図5.22で、REQ theft 状態が赤色なのはなぜですか。
クイッククイズ5.47:
図5.22で、REQ と ACK theft 状態を別々に持つ理由は何ですか?2つを、単一の REQACK 状態に縮退させて状態マシンを簡単にしてはどうですか?そうして、シグナルハンドラでも高速パスでも、最初にそこに達したほうが、状態を READY にしたらどうでしょう。
5.4.4 シグナル泥棒限界カウンタの実装
図5.23 (count_lim_sig.c) が、シグナル泥棒ベースのカウンタ実装で使われるデータ構造です。1から7行目は、前の節で説明したスレッドごとの状態マシンで使われる状態と変数を定義します。8から17行目は以前の実装と似ています。14と15行目に、スレッドの countermax と theft 変数を、それぞれリモートからアクセスできるようにしています。
図5.24はカウントをスレッドごとの変数とグローバル変数との間で移動するための関数です。1から7行目は globalize_count() で、以前の実装と同じです。9から19行目は、flush_local_count_sig() で、これが、泥棒処理で使われるシグナルハンドラです。11から12行目は theft 状態が REQ であるか調べ、そうでないなら、何も変更せず戻ります。13行目は theft 変数のサンプリングがその変数へのすべての変更より後に起きることを保証するためのメモリバリアを実行します。14行目で、 theft 変数を ACK にし、15行目でこのスレッドの高速パスが実行中でないと判断したら、16行目で theft 変数を READY にします。
クイッククイズ5.48:
図5.24の flush_local_count_sig() 関数で、スレッドごと変数 theft を使うまわりに、ACCESS_ONCE() ラッパーがあるのはなぜですか?
21から49行目は、flush_local_count() で、低速パスから呼ばれて、すべてのスレッドのローカルカウントをフラッシュします。26から34行目にあるループは、ローカルカウントを持つそれぞれのスレッドの theft 状態を進めます。また、そのスレッドにシグナルを送ります。27行目は、存在しないスレッドをスキップします。そうでない場合、28行目で現在のスレッドがローカルカウントを持っているかを見て、なければ、29行目でそのスレッドの theft 状態を READY にして、30行目で次のスレッドに行きます。そうでない場合、32行目でそのスレッドの theft 状態を REQ にして、33行目でシグナルを送ります。
クイッククイズ5.49:
図5.24で、なぜ、28行目で他のスレッドの countermax 変数を直接アクセスしても安全なのでしょう?
クイッククイズ5.50:
図5.24で、現在スレッドの自分自身にシグナルを送らないようにチェックしないのはなぜでしょう?
クイッククイズ5.51:
図5.24のコードは、 gcc と POSIX で動作します。これを、ISO C 標準に準拠させるためには何が必要でしょう?
35から48行目のループは、それぞれのスレッドが READY 状態に達するのを待ち、そのスレッドのカウントを盗みます。36と37行目は、存在しないスレッドをスキップし、38から42行目のループは現在スレッドの theft 状態が READY になるのを待ちます。
39行目は優先度逆転問題を回避するために1ミリ秒ブロックします。40行目でスレッドにシグナルが届いてないと判断したら、41行目でもう一度シグナルを投げます。スレッドの theft 状態が READY になったら、43行目に来ます。なので、43から46行目で実際に盗みをします。47行目でスレッドの theft 状態を IDLE に戻します。
クイッククイズ5.52:
図5.24で、41行目でシグナルを投げ直すのはなぜですか?
51から63行目は balance_count() で、前の例と似ています。
図5.25は、add_count() 関数です。高速パスは5から20行目で、低速パスは21から35行目です。5行目でスレッドごとの counting 変数を1にします。これにより、以降このスレッドを割り込むシグナルハンドラは、theft 状態を READY でなくて ACK にします。こうして、この高速パスが無事に完了することができます。
6行目はコンパイラが高速パスのボディのどこかを、counting の設定より前に動かすのを止めます。7と8行目はスレッドごとのデータが add_count() を受け入れられるか、そして、現在実行中の盗みがないかを見て、そうならば9行目で高速パスの加算をして、10行目で高速パスが使われたことを示します。
いずれの場合も、12行目はコンパイラが高速パスのボディを13行目の下に動かすのを止めます。13行目は、以降のシグナルハンドラが盗みをすることを許します。14行目はまたコンパイラの再配置を禁止し、15行目でシグナルハンドラが theft 状態の READY への遷移を先延ばしにしたかを見ます。そうならば、16行目でメモリバリアを実行して、17行目で状態が READY になったのを見たCPUは必ず、9行目の効果も見ることを保証します。もし、9行目の高速パス加算が実行されたら、20行目は成功を返します。
そうでない場合、21行目から始まる低速パスに続きます。低速パスの構造は前の例と似ていますから、その解析は読者への課題とします。同様に、図5.26の sub_count() の構造は add_count() と同じですから、その解析と、さらに、図5.27の read_count() の解析も、読者への課題とします。
図5.28の1から12行目は、count_init() です。これは、SIGUSR1 のシグナルハンドラとして、flush_local_count_sig() を設定します。これにより、flush_local_count() からの pthread_kill()
が、flush_local_count_sig() を呼ぶようになります。スレッド登録と登録解除のコードは前の例と同じなので、その解析は読者への課題とします。
5.4.5 シグナル泥棒限界カウンタの議論
シグナル泥棒の実装は、私のインテル Core Duo ラップトップで、アトミックな実装に比べて2倍速く走ります。これは常に望ましいことでしょうか?
シグナル泥棒の実装は、Pentium-4 システムでは、広く望ましいと言えます。そのアトミック命令は遅いためです。しかし、古い 80386 ベースの Sequent Symmetry システムでは、より短いパス長を持つアトミック実装の方がずっと速いでしょう。しかし、この改善された更新側性能は、リード側オーバーヘッドの増加という代償を伴います。これら POSIX シグナルはタダではありません。もしも最高の性能が問題であるならば、あなたはご自分のアプリケーションが使われるシステムにおいて、両方を測定する必要があるでしょう。
クイッククイズ5.53:
POSIX シグナルは遅いだけでなく、シグナルをそれぞれのスレッドに送るのは、まるでスケールしません。もしも(例えば)10000スレッドがあって、しかも、リード側が高速でなくてはいけないならば、どうしたら良いでしょう。
これは、高品質の API がとても重要であることの1つの例です。それにより、常に変わっていくハードウエア性能特性の要求に従って実装を変えていくことができます。
クイッククイズ5.54:
もしも、正確な限界カウンタの下の限界値だけが正確である必要があり、上の限界値は不正確であっても良いとしたら、どうしますか?
5.5 特別な並列カウンタの応用
5.4節で述べた正確な限界カウンタ実装はとても便利ですが、カウンタの値が常にゼロ付近にとどまるような場合はあまり役に立ちません。これは、I/O デバイスへの実行中のアクセス数を数える時に起きます。そのような場合のゼロ付近のカウンティングの高いオーバーヘッドは、普段はいくつの参照があるか気にかけないことを思うと特に困ったものです。クイッククイズ5.5で問われた、リムーバブルI/O デバイスのアクセスカウント問題で示したように、アクセスの数は、誰かが実際にデバイスを削除しようとしているというまれな場合を除いては、どうでもよいのです。
この問題の1つの単純な解決策は、カウンタに大きな「バイアス」(例えば、100万)を加算して、値がゼロから遠く離れるようにすることです。そうすれば、カウンタは効率的に動きます。誰かがデバイスを削除したいときには、このバイアスをカウンタ値から引きます。最後のいくつかのアクセスを数えるのはとても効率が悪いでしょうが、重要なのは、その前の多くのアクセスはフルスピードで実行することができたということです。
クイッククイズ5.55:
バイアスのあるカウンタを使うときに、他に注意するべきことはありますか?
バイアスのあるカウンタはとても助けになり、使いやすいですが、それは、49ページで述べたリムーバブルI/Oデバイスのアクセス数問題の部分的な解決策でしかありません。デバイスを削除するときは、現在の正確なI/O アクセス数を知るだけではだめで、以降の新しいアクセスが始まるのを防ぐ必要があります。これを実現する1つの方法は、カウンタを更新するときに、リーダーライターロックをリードロックすることです。そして、同じリーダーライターロックを、カウンタをチェックするときにライトロックします。I/Oをするコードは、以下のようになるでしょう。
1行目はロックをリードロックし、3あるいは7行目で放します。2行目でデバイスが削除されようとしているかを見て、そうならば、3行目でロックを放し、4行目でI/Oをキャンセルするか、あるいはデバイスが削除されようとしている場合に適当なアクションをとります。そうでなければ、6行目でアクセスカウントを加算し、7行目でロックを放し、8行目でI/Oを実行し、9行目でアクセスカウントを減算します。
クイッククイズ5.56:
これはばかげてます!カウンタを更新するのに、リーダーライターロックをリードロックするって?何をやってんですか???
デバイスを削除するコードは以下のようになるでしょう。
1行目はロックをライトロックし、4行目で放します。2行目はデバイスが削除されることを示します。そして、5から7行目にあるループで、すべてのI/O操作が完了するのを待ちます。
最後に、8行目でデバイス削除に備えるためのそれ以外の必要な処理をします。
クイッククイズ5.57:
実際のシステムでは、他にどんな問題に対処する必要がありますか?
5.6 並列カウンティングの議論
この章では、伝統的カウンティングプリミティブの、信頼性、性能そしてスケーラビリティ問題を示しました。C 言語の ++ 演算はマルチスレッドのコードでは正しく機能する保証がなく、単一の変数へのアトミック操作は性能も悪く、スケールもしません。この章では、さらに、ある特別なケースでは素晴らしい性能を示し、スケールもするいくつかのカウンティングアルゴリズムを示しました。
表5.1は、4つの並列統計カウンティングアルゴリズムの性能を示します。すべての4つのアルゴリズムは、更新においては、ほぼ完全に線形のスケーラビリティを示します。スレッドごとの変数の実装(count_end.c)は更新では配列ベースの実装(count_stat.c)に比べて素晴らしく速いですが、多数コアの場合のリードは遅く、多数の並列のリーダーがいる場合、厳しいロック競合にみまわれます。
この競合は、表5.1の count_end_rcu.c の列で示すように、9章で紹介する遅延処理技術を使えば対策できます。遅延処理の輝きはまた、結果整合性を使う、count_stat_eventual.c の列ででも見ることができます。
クイッククイズ5.58:
表5.1の count_stat.c 列で、更新側は、スレッド数に線形にスケールすることがわかります。スレッドが増えれば、より多くのスレッドごとのカウンタを合計しないといけないのになぜこれが可能なのでしょう?
クイッククイズ5.59:
表5.1の最後の列を見ても、これらの統計カウンタ実装のリード側性能はずいぶんひどいものです。なぜ、こんなものにかかわるのですか?
図5.2は、並列限界カウンティングアルゴリズムの性能を示します。限界を正確に適用するために、多大な性能ペナルティがあります。ただし、この 4.7GHz Power-6 システムでは、そのペナルティを、更新側アトミック操作を、リード側シグナルで代わりとすることで軽減することができます。これらすべての実装で、同時実行するリーダーがあるときは、リード側ロック競合がひどいです。
クイッククイズ5.60:
表5.2の性能データから見ると、常にシグナルの方が、アトミック操作より良いように見えます。そうですよね?
クイッククイズ5.61:
表5.2のリーダー間のロック競合を対策する高度な技術はありませんか?
これらのアルゴリズムが、それぞれの特別ケースでしかうまく働かないという事実が、並列プログラミング一般にとって大きな問題であると言えます。結局のところ、C 言語の ++ 演算子は、シングルスレッドのコードで普通に動きますし、それが特別ケースに限られることなく一般的にそうですよね?
この論理は少しの真実を持ちますが、本質的には誤ったものです。問題は並列性そのものではなく、スケーラビリティにあります。これを理解するために、まず、C 言語の ++ 演算子を考えましょう。事実は、それは一般的に働くのではなく、限られた範囲の数にだけ働くということです。あなたが1000桁の十進数を扱う必要がある時は、C 言語の ++ 演算子はあなたのためにはうまく働きません。
クイッククイズ5.62:
++ 演算子は、1000桁の数にだって普通に動きますよ!演算子オーバーロードって聞いたことないのですか?
この問題は、算数に限ったものではありません。データを格納、検索する必要があるとします。あなたは、ASCII ファイルを使いますか?XML?リレーショナル・データベース?連結リスト?稠密な配列?B ツリー?radix ツリー?あるいはその他たくさんある、データの格納と検索を許すデータ構造と環境のいずれかですか?それは、あなたが何をする必要があるかにより、どのくらい速くする必要かにより、あなたのデータセットがどのくらい大きいかによります。
同様に、カウントする必要があるとき、あなたのソリューションは、あなたが扱う数がどのくらい大きいか、いくつのCPUが同時実行して与えられた数を操作する必要があるか、その数がどのように使われるか、そしてあなたがどんなレベルの性能とスケーラビリティを必要とするかに依存します。
さらにこの問題は、ソフトウェアに固有ではありません。人が、小さな小川を歩いて渡るための橋の設計ならば、1枚の木の板くらいに単純です。しかし、何キロメートルもの幅のあるコロンビア川の河口に渡すのに板は使わないでしょうし、コンクリート車を通す橋の設計としてはそれはお勧めできません。ようするに、橋の設計が、幅と重さが増すにつれて変わらなくてはいけないように、ソフトウェアの設計はCPU数が増すにつれて変わらないといけないのです。
この章の例は、多数のCPUを関与させることを許す重要なツールは、分割であることを示しました。5.2節で議論した統計カウンタのように、カウンタは完全に分割してもよいです。あるいは、5.3と5.4節で議論した限界カウンタのように、部分的に分割してもよいです。分割一般については、6章ではるかに深く考察します。そして、特に、6.4節で述べる部分的並列化は、並列高速パスと呼ばれます。
クイッククイズ5.63:
しかし、なんでも分割しないといけないならば、なぜ、共用メモリマルチスレッドにこだわるのですか?なぜ、問題を完全に分割してしまって、それぞれが別のアドレス空間を持つ複数プロセスで実行したらどうですか?
部分的に分割されたカウンティングアルゴリズムはグローバルデータを保護するためにロックを使いました。そして、ロックは7章の主題です。それに対して、分割されたデータは完全に、対応するスレッドの制御の元にあるでしょうから、同期というものは何も必要ありません。データ所有は、6.3.4節で紹介され、8章でより深く議論されます。
最後に、5.2.3節で議論した結果整合の統計カウンタは、いかに、アクティビティ(このケースでは、グローバルカウンタを更新すること)を遅延させることが、多大な性能とスケーラビリティの利点をもたらすかを示しました。9章は、遅延が、性能、スケーラビリティ、そして実時間応答までもを改善することができる、これ以外の多くの方法を調べます。
まとめのまとめです。
1 分割は、性能とスケーラビリティを向上させます。
2 部分的分割、つまり、共通コードパスだけに適用された分割も、同様にうまく働きます。
3 部分的分割は、コード(5.2節の統計カウンタの分割更新と、分割されないリードのように)に適用することも、時間にわたって(5.3と5.4節の、限界カウンタが、限界から離れた時は高速に動き、限界に近いと遅くなるように)適用することもできます。
4 リードオンリーのコードパスは、リードオンリーのままであるべきです。共用メモリへの余分な同期ライトは性能とスケーラビリティを殺します。表5.1の count_end.c の列を参照。
5 賢明な遅延の使用は、性能とスケーラビリティを向上させます。5.2.3節を参照。
6 並列性能とスケーラビリティは通常はバランスの上にあります。ある点を超えると、あるコードパスを最適化するともう片方が劣化します。表5.1の count_stat.c と count_end_rcu.c の列はこの点を明らかにします。
7 性能とスケーラビリティのいろいろなレベルがアルゴリズムとデータ構造の設計に影響します。それ以外の多くのファクターも関係します。図5.3はこれを示します。アトミック加算は、2CPUシステムでは完全に許容できますが、8CPUシステムでは全く不適当です。
ようするに、この章の最初に述べたように、カウンティングの元となる概念が単純であるために、私達は、複雑なデータ構造や同期プリミティブに惑わされることなく、多くの同時実行の基本的問題を探検することができました。以降の章は、これら基本的問題をさらに深く掘り進みます。
以上