2.6 良性のデータ競合
マルチスレッドアプリケーションの中には、パフォーマンスを高めるために意図的にデータ競合を許容しているものがあります。良性のデータ競合とは、その存在がプログラムの正確さに影響することのない意図的なデータ競合です。次は、良性のデータ競合の具体例です。
注 –
規模の大きいアプリケーションは、正しく設計することが難しい、ロックフリーおよび待機状態のないアルゴリズムに依存しているため、良性のデータ競合に加え、真性のデータ競合も許容しています。スレッドアナライザは、そうしたアプリケーションのデータ競合の発生場所の特定に役立てることができます。
2.6.1 素数を発見するためのプログラム
次のファイル omp_prime.c のスレッドは、is_prime() 関数を実行することによって整数が素数であるかどうかをチェックします。
11 int is_prime(int v)
12 {
13 int i;
14 int bound = floor(sqrt ((double)v)) + 1;
15
16 for (i = 2; i < bound; i++) {
17 /* 判定済み合成数のチェックは不要 */
18 if (!pflag[i])
19 continue;
20 if (v % i == 0) {
21 pflag[v] = 0;
22 return 0;
23 }
24 }
25 return (v > 1);
26 }
スレッドアナライザは、行 21 の pflag[] への write と行 18 の pflag[] の read
との間にデータ競合があると報告します。ただし、このデータ競合は、最終結果の正確さに影響しないため良性です。行 18 では、スレッドが、与えられた i 値について、pflag[i] がゼロかどうかをチェックします。pflag[i] がゼロの場合は、i は既知の合成数 (言い換えると、i は非素数になることで知られている) であることを意味します。このため、v が i で割り切れるかどうかをチェックする必要はなく、v が何らかの素数で割り切れるかどうかをチェックすればよいだけです。その結果、pflag[i] がゼロの場合、スレッドは次の i 値に進みます。pflag[i] がゼロでなく、かつ v が i で割り切れる場合、スレッドは pflag[v] にゼロを代入して、v が素数ではないことを示します。
正確さの観点からは、複数のスレッドが同じ pflag[] 要素をチェックし、その要素に同時に書き込みを行うことは重要ではありません。pflag[] 要素の初期値は 1 です。スレッドは要素の更新時に、その要素にゼロを代入します。すなわち、スレッドは、その要素用の同じメモリーバイト内の同じビットにゼロをストアします。現在のアーキテクチャーでは、そうしたストアは不可分 (アトミック) とみなして差し支えありません。このことは、スレッドによるその要素の読み取り時、読み取られる値は 1 かゼロのいずれかであることを意味します。 pflag[] 要素に値ゼロが代入される前に、要素のチェックが行われる (行 18) と、スレッドは行 20 〜 23 を実行します。その間、別のスレッドが同じ pflag[] 要素にゼロを代入しても (行 21)、最終結果は変わりません。基本的に、このことは、最初のスレッドによる行 20 〜 23 の実行が不必要だったことを意味します。
2.6.2 配列値の型を検査するプログラム
一群のスレッドが check_bad_array() を同時に呼び出し、配列 data_array に壊れている要素がないかどうかをチェックします。各スレッドはそれぞれ配列の異なる部分をチェックします。スレッドは要素が壊れれていることを発見すると、大域共有変数 is_bad の値を true に設定します。
20 volatile int is_bad = 0;
...
100 /*
102 * それぞれのスレッドは、割り当てられた data_array の一部をチェックし、
102 * 不正なデータ要素が見つかったら大域フラグ is_bad に 1 を代入します。
103 */
104 void check_bad_array(volatile data_t *data_array, unsigned int thread_id)
105 {
106 int i;
107 for (i=my_start(thread_id); i<my_end(thread_id); i++) {
108 if (is_bad)
109 return;
110 else {
111 if (is_bad_element(data_array[i])) {
112 is_bad = 1;
113 return;
114 }
115 }
116 }
117 }
行 108 の is_bad の read と行 112 の is_bad への write との間にデータ競合があります。ただし、このデータ競合が最終結果の正確さに影響することはありません。
is_bad の初期値はゼロです。スレッドは is_bad の更新時に、この変数に値 1 を代入します。すなわち、スレッドは is_bad 用の同じメモリーバイト内の同じビットに 1 をストアします。現在のアーキテクチャーでは、そうしたストアは不可分 (アトミック) とみなして差し支えありません。このため、スレッドによる is_bad の読み取り時、読み取られる値は 1 かゼロのいずれかです。is_bad に値 1 が代入される前に 、is_bad のチェックが行われる (行 108) と 、スレッドは for ループの実行を継続します。その間、別のスレッドが is_bad に 1 を代入しても (行 112)、最終結果は変わりません。このことは、スレッドが必要以上に長い時間 for ループを実行したことを意味するだけです。
2.6.3 二重チェックロックを使用するプログラム
シングルトンは、プログラム全体を通じて特定の 1 つの型のオブジェクトが 1 つだけ存在するようにします。二重チェックロックは、マルチスレッドアプリケーションでシングルトンを初期化するための一般的で効率的な手段です。次のコードは、その実装例を示しています。
100 class Singleton {
101 public:
102 static Singleton* instance();
103 ...
104 private:
105 static Singleton* ptr_instance;
106 };
...
200 Singleton* Singleton::ptr_instance = 0;
...
300 Singleton* Singleton::instance() {
301 Singleton *tmp = ptr_instance;
302 memory_barrier();
303 if (tmp == NULL) {
304 Lock();
305 if (ptr_instance == NULL) {
306 tmp = new Singleton;
307 memory_barrier();
308 ptr_instance = tmp;
309 }
310 Unlock();
311 }
312 return tmp;
313 }
ptr_instance の read (行 301) は、ロックによる保護は意図的に行なっていません。そうすることで、マルチスレッド環境でシングルトンがすでにインスタンス化されているかどうかの判定チェックを効率的にします。変数 ptr_instance について、行 301 の read と行 308 の write との間にデータ競合がありますが、プログラムは正しく機能します。しかし、データ競合を許容するプログラムを正しく記述するのは、難しい作業です。たとえば、前述の二重チェックロックのコードで、行 302 と 307 の memory_barrier() 呼び出しは、シングルトンと ptr_instance が必ず適切な順序で設定、読み取られるようにすることを目的に使用されています。そうすることで、すべてのスレッドが整合性を損なうことなくそれらを読み取ります。この memory_barrier() で実現されている機能を使用しないと、このプログラム手法は機能しません。
- © 2010, Oracle Corporation and/or its affiliates