ロックに伴うオーバヘッドを避ける最も単純な方法の一つは、スレッド(あるいは、カーネルの場合 CPU)ごとにデータを分けて、あるデータ部分はただ1つのスレッドによってアクセス及び更新されるようにすることです。このアプローチはとても広く使われています。実際これは、初心者でさえ、ほぼ直感的に採用する使用パターンの一つです。これがとても広く使われているため、この章では新しい例は紹介せず、以前の章の例を再使用します。 クイッククイズ8.1:C あるいは C++ で共用メモリ並列プログラムを(例えば、 pthread を使って)作成するときに、避ける事がとても難しいデータ所有の形式とはどのようなものでしょう? データ所有には多くのアプローチがあります。8.1節はデータ所有の論理的極限を示します。そこでは、各スレッドが自分のプライベートなアドレス空間を持ちます。8.2節は逆の極限で、データは共有され、異なるスレッドが異なるアクセス権を持ちます。8.3節は関数シッピングです。これは特定のスレッドが所有するデータに他のスレッドが間接的にアクセスするのを可能とする方法です。8.4節は特定の関数と関連するデータに、どのように特定のスレッドを割り当てるかを示します。8.5節は、共用データを使うアルゴリズムをデータ所有を使うものに変換することで、性能を改善することについて議論します。最後に8.6節は、データ所有をファーストクラス市民として備えているいくつかのソフトウエア環境をリストします。
8.1 複数プロセス
4.1節で、以下の例をあげました。
1 compute_it 1 > compute_it.1.out &
2 compute_it 2 > compute_it.2.out &
3 wait
4 cat compute_it.1.out
5 cat compute_it.2.out
この例は、compute_it プログラムの2つのインスタンスを並列に走らせます。2つの独立したプロセスは、メモリを共用しません。なので、あるプロセスの全てのデータはそのプロセスが所有します。このため、前記の例では、ほぼ全てのデータが所有されています。このアプローチは、同期オーバーヘッドをほぼ完全に除きます。この結果得られる、素晴らしい単純さと、最適な性能の組み合わせは、もちろん、とても魅力的です。
クイッククイズ8.2 8.1節で示した例で、どのような同期がまだ残っていますか?
クイッククイズ8.3 8.1節で示した例で、共用データはありますか?
この同じパターンは、sh だけでなく、図4.2と4.3に示したように、C で書くこともできます。 次の節は、共用メモリ並列プログラムでの、データ所有の利用を述べます。
8.2 部分的データ所有と pthread
5章では、データ所有をたくさん使いました。が、ひねりを加えました。スレッドは、他のスレッドが所有するデータを変更することは許されませんが、それを読むことはできます。つまり、共用メモリの使用によって、より微妙な所有とアクセス権の概念が可能となりました。 例えば、57ページの図5.9で示される、スレッドごとの統計カウンタ実装を見ましょう。ここで、inc_count() は、対応するスレッドの counter インスタンスだけを 更新しますが、 read_count() は、すべてのスレッドの counter インスタンスをアクセスします。なお、変更はしません。
クイッククイズ8.4 それぞれのスレッドが、スレッドごと変数の自分のインスタンスだけを読むことができ、他のスレッドのインスタンスに書くことができるような、部分的データ所有というのは、いったい、意味がありますか?
純粋なデータ所有は、一般的で、かつ、役に足ちます。例えば、111ページの、6.4.3節で述べた、スレッドごとのメモリアロケータキャッシュなど。このアルゴリズムでは、それぞれのスレッドのキャッシュは、完全に、そのスレッドにプライベートです。
8.3 関数シッピング
前の節は、スレッドが、他のスレッドのデータに手が届く、データ所有の弱い形式を述べました。これは、データを、それを必要とする関数に届けると考えることができます。その代わりとなるアプローチは、関数をデータに送ることです。 74ページの5.4.3節に、そのアプローチが示されています。特に、76ページの図5.24の、flush_local_count_sig() と flush_local_count() 関数です。 flush_local_count_sig() 関数はシグナルハンドラで、送られた関数としてはたらきます。flush_local_count() の pthread_kill() 関数がシグナルを送り(関数をシップします)、送った関数が実行するのを待ちます。この送られた関数は、当然、全ての同時実行する、add_count() や sub_count() (77ページの図5.25と78ページの図5.26)と相互作用する必要があるという、余分な複雑さを持ちます。
クイッククイズ8.5 関数シッピングに、POSIX シグナル以外の機構を使うことができますか?
8.4 専用スレッド
これまでの節は、それぞれのスレッドが、データの自分専用のコピーあるいは、自分専用の部分を持つことを許す方法を述べてきました。それに対して、この節は、機能分割アプローチを述べます。ここでは、特別の専用スレッドが、自分の仕事をするために必要なデータへの権利を持ちます。5.2.3節で述べた、結果整合カウンタ実装が、その例です。この実装は、図5.8の15から32行目で示す、eventual() 関数を走らせる専用のスレッドを持ちます。eventual() スレッドは、定期的に、スレッドごとのカウントをグローバルなカウンタに吸い上げ、グローバルなカウンタへのアクセスが、名前のとおり、最終的には、実際の値に収束するようにします。
クイッククイズ8.6 でも、図5.8の15から32行目で示す、eventual() 関数のデータは、実際にはどれも、eventual() スレッドが所有していません!いったいどんな理由で、これがデータ所有なのですか???
8.5 プライベート化
共用メモリ並列プログラムの性能とスケーラビリティを改善する1つの方法は、共用データを特定のスレッドが所有するプライベートデータに変換することです。 この優れた例は、6.1.1節のクイッククイズの一つの答えにあります。そこでは、食事をする哲学者問題の答えを作るのに、プライベート化を使っています。そこでは、標準的な教科書の解答よりずっと良い性能とスケーラビリティが得られます。元の問題は、5人の哲学者がテーブルの周りにいて、哲学者の隣り合う対に1つのフォークがあります。このため、同時に最大2人の哲学者が食事ができます。 この問題をプライベート化するのは自明で、追加で5つのフォークを提供すれば良いです。そうすれば、哲学者は彼あるいは彼女のプライベートなフォークの対を持つことができます。これにより、全ての5人の哲学者は同時に食事ができますし、ある種の病気が蔓延することもありません。 他の場合には、プライベート化はコストを要求します。例えば、62ページの図5.12に示した単純な限界カウンタを見ましょう。これは、スレッドが、お互いのデータを読むことができるが、自分自身のデータだけを更新できるアルゴリズムの例です。アルゴリズムを簡単にレビューすると、スレッドをクロスするアクセスは、read_count() の合計ループだけにあることがわかります。もしこのループを除ければ、より効率的な純粋データ所有に移れますが、read_count() の結果はより不正確となるコストを払います。
クイッククイズ8.7 スレッドごとのデータの完全なプライバシーを保ちながら、より良い正確さを得ることは可能ですか?
つまり、プライベート化は並列プログラマの道具箱で強力なツールです。しかし、それだからこそ、注意して使わなくてはいけません。他の全ての同期プリミティブと同じように、複雑さを増し、性能とスケーラビリティを落とす潜在性を持ちます。
訳注。性能を増すけど、複雑になる。の方が、文脈で自然。
8.6 データ所有の他の使い方
データ所有は、データが分割できて、スレッドをクロスするアクセスや更新の必要が少しあるいは全くないときに最もうまくはたらきます。幸運にも、この状況は、十分に一般的で、並列プログラミング環境の広い領域で有効です。 データ所有の例は:
1 MPI や BOINC のような、メッセージパッシング環境の全て。
2 マップリデュース。
3 クライアントサーバシステム。これには、RPC, ウェブサービス、そして、バックエンドデータベースサーバーを持つとても多くの任意のシステムを含みます。
4 シェアードナッシングのデータベースシステム。
5 プロセスごとのアドレス空間を持つ、 fork-join システム。
6 Erlang 言語のような、プロセスベースの並列化。
7 プライベート変数。例えば、スレッド環境の C 言語のスタック上 auto 変数。
データ所有は、たぶん、存在する同期機構の中で、最も正当な評価がされていないものです。 正しく使えば、他にない単純性、性能そしてスケーラビリティが得られます。たぶん、それがあまりに単純なので、見合う尊敬を得られないのかもしれません。データ所有の巧みさと力がもっと評価され、より良い性能、スケーラビリティ、そして複雑さの削減につながることは言うまでもなく、より大きなレベルの尊敬を得られるようになることを祈ります。
以上