データ競合

インテル® Cilk™ Plus は古い機能 (非推奨) です。代わりに、OpenMP* またはインテル® TBB を使用してください。詳細は、「インテル® Cilk™ Plus の代わりに OpenMP* またはインテル® TBB を使用するためのアプリケーションの移行」を参照してください。

データ競合は、並列プログラムの問題の主な原因です。

決定性競合は、2 つの並列ストランドが同じメモリー位置にアクセスし、そのどちらかが書き込み操作を行うと発生します。プログラムの結果は、どちらのストランドが "競争に勝ち"、先にメモリーにアクセスするかによって異なります。

データ競合は、決定性競合の特殊なケースです。データ競合は、共通のロックを保持していない 2 つの並列ストランドが同じメモリー位置にアクセスし、そのどちらかが書き込み操作を行うと発生します。プログラムの結果は、どちらのストランドが "競争に勝ち"、先にメモリーにアクセスするかによって異なります。

並列アクセスがロックによって保護されている場合、データ競合は発生しません。ただし、ロックを使用するプログラムでは、決定性のある結果が得られないことがあります。ロックは、データ構造を保護して更新時に中間ステートから見えないようにすることで一貫性を保証しますが、決定性のある結果は保証しません。

例えば、次のようなプログラムについて考えてみます。

int a = 2; // 複数のスレッドがアクセス可能な変数を宣言

void Strand1()
{
   a = 1;
}

int Strand2()
{
   return a;
}

void Strand3()
{
   a = 2;
}
int main()
{
   int result;
   cilk_spawn Strand1();
   result = cilk_spawn Strand2();
   cilk_spawn Strand3();
   cilk_sync;
   std::cout << "a = " << a << ", result = "
             << result << std:endl;
}

Strand1()、Strand2()、Strand3() は並列で実行される可能性があるため、a と result の最終値は実行順序によって異なります。

Strand1() は Strand2() が a の値を読み取る前または後に書き込みを行う可能性があり、そのため Strand1() と Strand2() の間には読み取り/書き込み競合が存在します。

Strand3() は Strand1() が a の値を書き込む前または後に書き込みを行う可能性があり、そのため Strand3() と Strand1() の間には書き込み/書き込み競合が存在します。

データ競合によっては、害のないものもあります。つまり、競合が存在していても、プログラムの出力に影響しない場合があります。

次の簡単な例について考えてみます。

bool bFlag = false;
cilk_for (int i=0; i<N; ++i)
{
   if (some_condition()) bFlag = true;
}
if (bFlag) do_something();

このプログラムには、bFlag 変数に書き込み/書き込み競合があります。ただし、すべての書き込み操作は同じ値 (true) を書き込み、cilk_for ループの終了時に暗黙的に cilk_sync が行われるまで読み取り操作は行われません。

そのため、このデータ競合はプログラムの結果に影響を与えません。どのような順序でループの反復が実行されても、プログラムの結果は同じになります。