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