2.6 影響のないデータの競合

マルチスレッドアプリケーションの中には、パフォーマンスを高めるためにデータの競合を意図的に許可する場合があります。影響のないデータの競合は、存在していてもプログラムの正確さには影響しない意図的なデータの競合です。次の例は、影響のないデータの競合を示します。

2.6.1 素数検索用のプログラム

prime_omp.c 内のスレッドは、関数 is_prime() を実行することによって、整数が素数かどうかをチェックします。

    16  int is_prime(int v)
    17  {
    18      int i;
    19      int bound = floor(sqrt(v)) + 1;
    20
    21      for (i = 2; i < bound; i++) {
    22          /* no need to check against known composites */
    23          if (!pflag[i])
    24              continue;
    25          if (v % i == 0) {
    26              pflag[v] = 0;
    27              return 0;
    28          }
    29      }
    30      return (v > 1);
    31  }

スレッドアナライザは、行 26 での pflag[ ] への書き込みと行 23 での pflag[ ] の読み取りとの間にデータの競合があることを報告します。ただし、このデータの競合は、最終的な結果の正確さには影響しないので影響のないものです。23 行で、スレッドは、所与の i の値で、pflag[i] が 0 に等しいかどうかをチェックします。pflag[i] が 0 に等しい場合、i が既知の合成数である (つまり、 i は素数でないとわかっている) ことを意味します。この結果、v が i で割り切れるかどうかをチェックする必要がなくなります。v がいずれかの素数で割り切れるかどうかだけをチェックすればよくなります。したがって、pflag[i] が 0 に等しい場合、スレッドは i の次の値に進みます。pflag[i] が 0 に等しくなく、v が i で割り切れる場合、スレッドは 0 を pflag[v] に割り当てて、v が素数でないことを示します。

正確さの観点からは、複数のスレッドが同じ pflag[ ] 要素をチェックし、同時にそれに書き込むかどうかは重要ではありません。pflag[ ] 要素の初期値は 1 です。スレッドはこの要素を更新するときに、0 の値を割り当てます。つまり、スレッドはその要素に対してメモリーの同じバイトの同じビットに 0 を格納します。現在のアーキテクチャーでは、このような格納は不可分であると想定することが安全です。つまり、その要素がスレッドによって読み取られるときに、読み取られる値は 1 か 0 のどちらかになります。スレッドは、0 の値を割り当てる前に所定の pflag[ ] 要素をチェックする場合 (行 23)、行 25 ~ 28 を実行します。その間に別のスレッドがその同じ pflag[ ] 要素に 0 を割り当てた場合も (行 26)、最終結果は変化しません。これは、基本的に、最初のスレッドが不必要に行 25 ~ 28 を実行したが、最終結果は同じであったことを意味します。

2.6.2 配列値の型を検証するプログラム

スレッドのグループが check_bad_array() を同時に呼び出して、配列 data_array の要素が「間違っている」かどうかをチェックします。各スレッドは配列の異なるセクションをチェックします。スレッドは、要素が間違っていることを検出した場合、グローバル共有変数 is_bad の値を true に設定します。

20  volatile int is_bad = 0;
 ...

 100  /* 
 101   * Each thread checks its assigned portion of data_array, and sets 
 102   * the global flag is_bad to 1 once it finds a bad data element.
 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 の読み取りと行 112 での is_bad への書き込みとの間にデータの競合があります。ただし、データの競合は最終結果の正確さに影響しません。

is_bad の初期値は 0 です。スレッドは is_bad を更新するときに、値 1 を割り当てます。つまり、スレッドは、is_bad に対してメモリーの同じバイトの同じビットに 1 を格納します。現在のアーキテクチャーでは、このような格納は不可分であると想定することが安全です。したがって、is_bad がスレッドで読み取られるときに、読み取られる値は 0 か 1 のどちらかになります。スレッドは、値 1 が割り当てられる前に is_bad をチェックする場合 (行 108)、for ループの実行を継続します。その間に別のスレッドが値 1 を is_bad に割り当てても (行 112)、最終結果は変化しません。スレッドが for ループを必要以上長時間実行したというだけのことです。

2.6.3 二重検査されたロックを使用したプログラム

シングルトンは、特定の種類のオブジェクトが、プログラム全体で 1 つしか存在しないようにします。二重検査されたロックは、マルチスレッドアプリケーションでシングルトンを初期化する一般的で効率的な方法です。次のコードは、この実装方法を示します。

100 class Singleton {
101     public:
102     static Singleton* instance();
103     ...
104     private:
105     static Singleton* ptr_instance;
106 };
107
108 Singleton* Singleton::ptr_instance = 0;
...

200 Singleton* Singleton::instance() {
201     Singleton *tmp;
202     if (ptr_instance == 0) {
203         Lock();
204         if (ptr_instance == 0) {
205             tmp = new Singleton;
206
207             /* Make sure that all writes used to construct new
208                Singleton have been completed. */
209             memory_barrier();
210
211             /* Update ptr_instance to point to new Singleton. */
212             ptr_instance = tmp;
213
214         }
215         Unlock();
216     }
217     return ptr_instance;

行 202 の ptr_instance の読み取りは、ロックによって意図的に保護されていません。このため、マルチスレッド環境で Singleton がすでにインスタンス化されているかどうかを判別するチェックが効率的になります。変数 ptr_instance の行 202 での読み取りと行 212 での書き込みとの間でデータの競合があるが、プログラムは正しく動作します。ただし、データの競合を許可する正しいプログラムを作成すると、余分な注意が必要になります。たとえば、上記の二重検査されたロックのコードで、行 209 での memory_barrier() の呼び出しは、Singleton を構築するためのすべての書き込みが完了するまで、ptr_instance がスレッドによって非 NULL として認識されないようにするために使用されます。