独立した更新

独立した更新は、複数のタスクがメモリー位置の最終的な値の決定に関与する場合に発生します。

基本パターン

複数のタスクがメモリー位置に値を書き込み、書き込まれる値はそれぞれのタスクがメモリー位置の以前の値を基に計算したものであり、タスクがメモリー位置を更新する順番は重要ではないと仮定します。

例えば、配列の値をすべて合計するループを考えてみます。

extern int x;
// ...
ANNOTATE_SITE_BEGIN(site1);
for (i = 0; i != n; ++i) { 
    ANNOTATE_ITERATION_TASK(task1);
    x = x + a[i];
}
ANNOTATE_SITE_END(site1);
printf("%d\n", x);

共有の問題は次のような場合に発生します。

タスク 0 が x を読み取ります。
タスク 1 が x を読み取ります。
タスク 0 が a[0] を x に加算してストアします。
タスク 1 は、a[1] を x に加算してストアします。タスク 0 が更新した値は上書きされます。

重要なことは、x の更新が任意の順番で行われることです。確実にすべきことは、タスクが x を読み取り x に書き込むまで、別のタスクが x への書き込みを行わないようにすることです。タスク内の x の使用はそれ以外は独立しています。

リダクション

リダクションは、独立した更新パターンの特殊ケースです。リダクション・パターンは、ループが可換で結合可能な機能を使用して値の集合を結合する際に発生します。

「プログラムに並列処理を追加」では、oneTBB と OpenMP* 並列フレームワークで利用可能な並列リダクションを記述する特殊な機能について説明しています。

トランザクション

このパターンの典型的な例は、複数のメモリー位置をまとめて更新する必要がある場合です。

void insert_node_in_list(T *new_node, T *insert_after) { 
     new_node->next = insert_after->next; 
     new_node->prev = insert_after->next->prev; 
     insert_after->next->prev = new_node; 
     insert_after->next = new_node; 
}

2 つの挿入は同時に行われてはなりませんが、最終的なリストの順番が重要でない限り、どの順番でも挿入できます。

まとめて行われる必要がある集合の更新は、トランザクションと呼ばれます。

ガード変数

特殊なケースとして、共有メモリーの位置を使用して追加コードを制御することがあります。更新とそれに依存するコードは、トランザクションとして扱われます。

bool initialized = false; 
void do_something() { 
     if (!initialized) { 
          do_the_initialization(); 
          initialized = true; 
     } 
     do_the_real_work(); 
}

do_something() が複数のタスクから呼び出されると、共有問題が発生します。

タスク 0 が initialized を読み取り、false であれば if 文を実行します。
タスク 1 が変数 initialized を読み取り、false であれば if 文を実行します。このため、do_the_initialization() は 2 度呼び出されます。

どのタスクが初期化を行うかは重要ではなく、問題は初期化が行われるまでほかのタスクが確実に待機するようにします。

独立した書き込み

これは、タスクが書き込むメモリー位置の値が、以前の値に依存しない場合に発生します。

bool found = false; 
ANNOTATE_SITE_BEGIN(site1); 
     for (i = 0; i != n; ++i) { 
     ANNOTATE_ITERATION_TASK(task1); 
          if (a[i] == b) found = true; 
     } 
     if (found) printf("found\n"); 
ANNOTATE_SITE_BEGIN(site1);

書き込みに対応する読み取りがなく、found への書き込み順序は任意であり、タスクは独立しており、制限なく同時に実行できます。タスクが found に書き込みを行うと、true 値が書き込まれます。

次のようなタスク本体の場合、この例はリダクション・パターンに適合します。

found = found || (a[i] == b);

どのスレッドが最後に書き込みを行うかにかかわらず、プログラムは常に同じ値を計算するため、これは無害な競合と呼ばれます。