第 2 章 データ競合のチュートリアル
スレッドアナライザを使用してデータ競合を検出および解決する方法を詳しく説明したチュートリアルです。このチュートリアルは、次の各節から構成されています。
2.1 チュートリアル用ソースファイル
このチュートリアルでは、ともにデータ競合を含む 2 つのプログラムを使用します。
-
最初のプログラムは素数を見つけます。C で記述され、OpenMP 指令を使用して並列化されています。ソースファイルの名前は omp_prime.c です。
-
2 つ目のプログラムも素数を見つけるプログラムで、C で記述されていますが、こちらは OpenMP 指令ではなく、POSIX スレッドを使用して並列化されています。ソースファイルの名前は pthr_prime.c です。
2.1.1 omp_prime.c の全コード
1 #include <stdio.h>
2 #include <math.h>
3 #include <omp.h>
4
5 #define THREADS 4
6 #define N 3000
7
8 int primes[N];
9 int pflag[N];
10
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 }
27
28 int main(int argn, char **argv)
29 {
30 int i;
31 int total = 0;
32
33 #ifdef _OPENMP
34 omp_set_num_threads(THREADS);
35 omp_set_dynamic(0);
36 #endif
37
38 for (i = 0; i < N; i++) {
39 pflag[i] = 1;
40 }
41
42 #pragma omp parallel for
43 for (i = 2; i < N; i++) {
44 if ( is_prime(i) ) {
45 primes[total] = i;
46 total++;
47 }
48 }
49 printf("Number of prime numbers between 2 and %d: %d\n",
50 N, total);
51 for (i = 0; i < total; i++) {
52 printf("%d\n", primes[i]);
53 }
54
55 return 0;
56 }
2.1.2 pthr_prime.c の全コード
1 #include <stdio.h>
2 #include <math.h>
3 #include <pthread.h>
4
5 #define THREADS 4
6 #define N 3000
7
8 int primes[N];
9 int pflag[N];
10 int total = 0;
11
12 int is_prime(int v)
13 {
14 int i;
15 int bound = floor(sqrt ((double)v)) + 1;
16
17 for (i = 2; i < bound; i++) {
18 /* 判定済み合成数のチェックは不要 */
19 if (!pflag[i])
20 continue;
21 if (v % i == 0) {
22 pflag[v] = 0;
23 return 0;
24 }
25 }
26 return (v > 1);
27 }
28
29 void *work(void *arg)
30 {
31 int start;
32 int end;
33 int i;
34
35 start = (N/THREADS) * (*(int *)arg) ;
36 end = start + N/THREADS;
37 for (i = start; i < end; i++) {
38 if ( is_prime(i) ) {
39 primes[total] = i;
40 total++;
41 }
42 }
43 return NULL;
44 }
45
46 int main(int argn, char **argv)
47 {
48 int i;
49 pthread_t tids[THREADS-1];
50
51 for (i = 0; i < N; i++) {
52 pflag[i] = 1;
53 }
54
55 for (i = 0; i < THREADS-1; i++) {
56 pthread_create(&tids[i], NULL, work, (void *)&i);
57 }
58
59 i = THREADS-1;
60 work((void *)&i);
61
62 printf("Number of prime numbers between 2 and %d: %d\n",
63 N, total);
64 for (i = 0; i < total; i++) {
65 printf("%d\n", primes[i]);
66 }
67
68 return 0;
69 }
2.1.2.1 omp_prime.c と pthr_prime.c 内のデータ競合
「2.1.1 omp_prime.c の全コード」 で記したように、コードに競合状態が含まれている場合、メモリーアクセスの順序は非決定的であり、実行のたびに演算結果は異なります。omp_prime.c のコードにはデータ競合があるため、実行のたびに不正な結果や矛盾する結果が出されます。次にその出力例を示します。
% cc -xopenmp=noopt omp_prime.c -lm % a.out | sort -n 0 0 0 0 0 0 0 Number of prime numbers between 2 and 3000: 336 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ... 2971 2999 % a.out | sort -n 0 0 0 0 0 0 0 0 0 Number of prime numbers between 2 and 3000: 325 3 5 7 13 17 19 23 29 31 41 43 47 61 67 71 73 79 83 89 101 ... 2971 2999
同様に、pthr_prime.c にもデータ競合があるため、プログラムの実行のたびに、次に示すような不正な結果や矛盾する結果が出されることがあります。
% cc pthr_prime.c -lm -mt . % a.out | sort -n Number of prime numbers between 2 and 3000: 304 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 ... 2999 2999 % a.out | sort -n Number of prime numbers between 2 and 3000: 314 751 757 761 769 773 787 797 809 811 821 823 827 839 853 859 877 881 883 907 911 ... 2999 2999
2.2 実験の作成
スレッドアナライザは、Sun Studio パフォーマンスアナライザが使用している「収集解析」モデルと同じモデルに従っています。スレッドアナライザの使用に必要な手順は、次の 3 つです。
2.2.1 ソースコードへの計測機構の組み込み
プログラム内のデータ競合を検出できるようにするには、まず、特殊なコンパイラオプションを付けてソースファイルをコンパイルします。C/C++ と Fortran 言語用のこの特殊オプションは、-xinstrument=datarace です。
プログラムのコンパイルに現在使用しているオプションに -xinstrument=datarace オプションを追加します。このオプションは、データ競合の疑いがあるソースファイルにのみ適用できます。
注 –
プログラムをコンパイルするときは、必ず -g を指定してください。競合を検出するためのプログラムのコンパイルでは、最適化レベルを高くしないでください。-xopenmp=noopt を使用して OpenMP プログラムをコンパイルしてください。最適化レベルを高くすると、報告される行番号や呼び出しスタックなどの情報が不正になることがあります。
次は、ソースコードに計測機構を組み込むコマンドの例です。
-
cc -xinstrument=datarace -g -mt pthr_prime.c
-
cc -xinstrument=datarace -g -xopenmp=noopt omp_prime.c
2.2.2 データ競合検出実験の生成
プログラムを実行して、プロセスの実行中にデータ競合検出実験を生成するには、collect コマンドに -r on フラグを付けて使用します。OpenMP プログラムの場合は、必ず使用するスレッド数を 1 より大きくします。次は、データ競合実験を生成するコマンドの例です。
-
collect -r race ./a.out
データ競合が検出されやすいようにするには、collect コマンドで -r race フラグを使用して、データ競合検出実験をいくつか生成することをお勧めします。実験ごとにスレッド数と入力データを変更します。
2.2.3 データ競合検出実験の検証
スレッドアナライザ、パフォーマンスアナライザ、または er_print ユーティリティーを使用して、データ競合検出実験を検証できます。スレッドアナライザとパフォーマンスアナライザはともに GUI インタフェースを提供します。 デフォルトタブ数が少ないことを除けば、スレッドアナライザはパフォーマンスアナライザと同じです。
スレッドアナライザの GUI は、メニューバー、ツールバー、および各種表示用のタブを含む分割区画で構成されます。左側のタブには、デフォルトで次の 3 つのタブが表示されます。
-
「競合」タブ - プログラム内で検出されたデータ競合の一覧です。デフォルトで選択されているタブです。
-
「デュアルソース」タブ - 選択されたデータ競合の 2 つの アクセスに対応する 2 つのソース位置を示します。データ競合の発生したソース行が強調表示されます。
-
「実験」タブ - 実験の負荷オブジェクトを示すとともに、エラーおよび警告メッセージを表示します。
スレッドアナライザ画面の右側の区画には、次の 2 つのタブが表示されます。
-
「概要」タブ - 「競合」タブで選択されたデータ競合アクセスに関する概要情報を表示します。
-
「競合の詳細」 - 「競合」タブで選択されたデータ競合アクセスに関する詳細情報を表示します。
一方、er_print ユーティリティーは、コマンド行インタフェースを提供します。次のサブコマンドは er_print ユーティリティーで競合を調べるときに有用です。
-
-races: 実験で検出されたすべてのデータ競合を報告します。
-
-rdetail race_id: 指定された race_id を持つデータ競合の詳細情報を表示します。race_id に「all」を指定した場合は、すべてのデータ競合に関する詳細情報が表示されます。
-
-header: 実験に関する説明を表示し、エラーと警告を報告します。
詳細は、collect.1、tha.1、analyzer.1、および er_print.1 のマニュアルページを参照してください。
2.3 実験結果について
この節では、er_print コマンド行インタフェースとスレッドアナライザ GUI の両方を使用して、検出されたすべてのデータ競合に関する次の情報を表示する方法を説明します。
-
データ競合の一意の ID。
-
データ競合に関係する仮想アドレス (
Vaddr)。 複数の仮想アドレスがある場合は、括弧で囲って複数のアドレスと表示されます。 -
2 つの異なるスレッドによる仮想アドレス (
Vaddr) へのメモリーアクセス。アクセスの種類 (読み取り/書き込み) が、ソースコード内のアクセスが発生した関数、オフセット、および行番号とともに表示されます。 -
データ競合に関係する総トレース数。各トレースは、2 つのデータ競合アクセスの発生した時点でのスレッド呼び出しスタックのペアを表します。GUI を使用している場合、個別にトレースを選択すると、「競合の詳細」タブに 2 つの呼び出しスタックが表示されます。er_print ユーティリティーを使用している場合は、rdetail コマンドによって 2 つの呼び出しスタックが表示されます。
2.3.1 omp_prime.c 内のデータ競合
% cc -xopenmp=noopt omp_prime.c -lm -xinstrument=datarace
% collect -r race a.out | sort -n
0
0
0
0
0
0
0
0
0
0
...
0
0
実験データベース test.1.er の作成中 ...
Number of prime numbers between 2 and 3000: 429
2
3
5
7
11
13
17
19
23
29
31
37
41
47
53
59
61
67
71
73
...
2971
2999
% er_print test.1.er
(er_print) races
総競合数: 4 実験: test.1.er
競合 #1, Vaddr: 0xffbfeec4
アクセス 1: 読み取り, main -- 行 42 からの MP doall [_$d1A42.main] + 0x00000060,
行 45 "omp_prime.c"
アクセス 2: 書き込み, main -- 行 42 からの MP doall [_$d1A42.main] + 0x0000008C,
行 46 "omp_prime.c"
総トレース数: 2
競合 #2, Vaddr: 0xffbfeec4
アクセス 1: 書き込み, main -- 行 42 からの MP doall [_$d1A42.main] + 0x0000008C,
行 46 "omp_prime.c"
アクセス 2: 書き込み, main -- 行 42 からの MP doall [_$d1A42.main] + 0x0000008C,
行 46 "omp_prime.c"
総トレース数: 1
競合 #3, Vaddr: (Multiple Addresses)
アクセス 1: 書き込み, main -- 行 42 からの MP doall [_$d1A42.main] + 0x0000007C,
行 45 "omp_prime.c"
アクセス 2: 書き込み, main -- 行 42 からの MP doall [_$d1A42.main] + 0x0000007C,
行 45 "omp_prime.c"
総トレース数: 1
競合 #4, Vaddr: 0x21418
アクセス 1: 読み取り, is_prime + 0x00000074,
行 18 "omp_prime.c"
アクセス 2: 書き込み, is_prime + 0x00000114,
行 21 "omp_prime.c"
総トレース数: 1
(er_print)
次のスクリーンショットは、omp_primes.c で検出された競合の、スレッドアナライザ GUI での表示例です。GUI を呼び出して、実験データを読み込むコマンドは tha test.1.er になっています。
図 2–1 omp_primes.c で検出されたデータ競合
omp_primes.c には、4 つのデータ競合があります。
-
競合番号 1: 行 45 の total の読み取りと行 46 の total への書き込みとのデータ競合。
-
競合番号 2: 行 46 の total への書き込みと同一行での total への別の書き込みとのデータ競合。
-
競合番号 3: 行 45 の
primes[]への書き込みと同一行でのprimes[]への別の書き込みとのデータ競合。 -
競合番号 4: 行 18 の
pflag[]の読み取りと行 21 のpflag[]への書き込みとのデータ競合。
2.3.2 pthr_prime.c 内のデータ競合
% cc pthr_prime.c -lm -mt -xinstrument=datarace .
% collect -r on a.out | sort -n
実験データベース test.2.er の作成中 ...
of type "nfs", which may distort the measured performance.
0
0
0
0
0
0
0
0
0
0
...
0
0
実験データベース test.2.er の作成中 ...
Number of prime numbers between 2 and 3000: 328
751
757
761
773
797
809
811
821
823
827
829
839
853
857
859
877
881
883
887
907
...
2999
2999
% er_print test.2.er
(er_print) races
総競合数: 6 実験: test.2.er
競合 #1, Vaddr: 0x218d0
アクセス 1: 書き込み, work + 0x00000154,
行 40 "pthr_prime.c"
アクセス 2: 書き込み, work + 0x00000154,
行 40 "pthr_prime.c"
総トレース数: 3
競合 #2, Vaddr: 0x218d0
アクセス 1: 読み取り, work + 0x000000CC,
行 39 "pthr_prime.c"
アクセス 2: 書き込み, work + 0x00000154,
行 40 "pthr_prime.c"
総トレース数: 3
競合 #3, Vaddr: 0xffbfeec4
アクセス 1: 書き込み, main + 0x00000204,
行 55 "pthr_prime.c"
アクセス 2: 読み取り, work + 0x00000024,
行 35 "pthr_prime.c"
総トレース数: 2
競合 #4, Vaddr: (Multiple Addresses)
アクセス 1: 書き込み, work + 0x00000108,
行 39 "pthr_prime.c"
アクセス 2: 書き込み, work + 0x00000108,
行 39 "pthr_prime.c"
総トレース数: 1
競合 #5, Vaddr: 0x23bfc
アクセス 1: 書き込み, is_prime + 0x00000210,
行 22 "pthr_prime.c"
アクセス 2: 書き込み, is_prime + 0x00000210,
行 22 "pthr_prime.c"
総トレース数: 1
競合 #6, Vaddr: 0x247bc
アクセス 1: 書き込み, work + 0x00000108,
行 39 "pthr_prime.c"
アクセス 2: 読み取り, main + 0x00000394,
行 65 "pthr_prime.c"
総トレース数: 1
(er_print)
次のスクリーンショットは、pthr_primes.c で検出された競合の、スレッドアナライザ GUI での表示例です。GUI を呼び出して、実験データを読み込むコマンドは tha test.2.er になっています。
図 2–2 pthr_primes.c で検出されたデータ競合
pthr_prime.c には、6 つのデータ競合があります。
-
競合番号 1: 行 40 の total への書き込みと同一行での total への別の書き込みとのデータ競合。
-
競合番号 2: 行 39 の total の読み取りと行 40 の total への書き込みとのデータ競合。
-
競合番号 3: 行 55 の i への書き込みと行 35 の i の読み取りとのデータ競合。
-
競合番号 4: 行 39 の
primes[]への書き込みと同一行でのprimes[]への別の書き込みとのデータ競合。 -
競合番号 5: 行 22 の
pflags[]への書き込みと同一行でのpflags[]への別の書き込みとのデータ競合。 -
競合番号 6: 行 39 の
primes[]への書き込みと行 65 のprimes[]の読み取りとのデータ競合。
GUI の利点は、データ競合に関係する 2 つのソース位置を横に並べて見られることです。たとえば「競合」タブで pthr_prime.c の競合番号 6 を選択し、「デュアルソース」タブをクリックすると、次のような画面になります。
図 2–3 データ競合のソース位置の詳細情報
競合番号 6 (行 39) の最初のアクセスが競合のソースの上の区画、同じデータ競合の 2 つ目のアクセスが下の区画に表示されます。このデータ競合アクセスが発生したソース行 39 および 65 は強調表示されます。デフォルトメトリック (「排他的競合アクセス」メトリック) は各ソース行の左側に表示されます。このメトリックは、その行についてデータ競合アクセスが報告された回数を示します。
2.4 データ競合の原因究明
この節では、データ競合の原因を究明する基本的な方法を説明します。
2.4.1 データ競合が誤検出 (false positive) かどうかの確認
誤検出データ競合とは、スレッドアナライザによって報告はされますが、実際には発生しなかったデータ競合です。スレッドアナライザは、報告する誤検出の数を減らそうと試みます。ただし、正確なジョブを実行できず、誤検出データ競合を報告することがあります。
誤検出データ競合は真のデータ競合ではなく、プログラムの動作に影響しないため、無視することができます。
誤検出データ競合例については、「2.5 誤検出 (False Positive)」を参照してください。レポートでの誤検出データ競合の解消方法については、「A.1 スレッドアナライザのユーザー API」を参照してください。
2.4.2 データ競合が良性かどうかの確認
良性のデータ競合は、その存在がプログラムの正確さに影響することのない意図的なデータ競合です。
マルチスレッドアプリケーションの中には、データ競合を起こす可能性があるコードが意図的に使用されているものがあります。そうしたデータ競合は意図的に存在しているため、修正する必要はありません。しかし、場合によっては、そうしたコードを正しく実行するのは難しく細心の注意が必要です。慎重に調査してください。
良性のデータ競合の詳細は、「2.5 誤検出 (False Positive)」を参照してください。
2.4.3 データ競合ではなくバグを修正する
スレッドアナライザはプログラム内のデータ競合の発見に役立てられますが、プログラム内のバグを自動的に発見することも、発見されたデータ競合を解消する方法の提案することもできません。データ競合がバグによって引き起こされている可能性があります。大切なのは、バグを見つけて修正することです。単にデータ競合を排除することは適切なアプローチではなく、以後のデバッグをさらに困難にすることもあります。データ競合ではなくバグを修正してください。
2.4.3.1 omp_prime.c 内のバグの修正
次に omp_prime.c のバグを修正する方法を示します。このファイルの全コードリストは、「2.1.1 omp_prime.c の全コード」にあります。
行 45 の total の read と行 46 の total への write とのデータ競合を解決するには、行 45 と 46 をクリティカルセクションに移動します。クリティカルセクションはこの 2 つの行を保護し、データ競合の発生を防ぎます。次に修正したコードを示します。
42 #pragma omp parallel for .
43 for (i = 2; i < N; i++) {
44 if ( is_prime(i) ) {
#pragma omp critical
{
45 primes[total] = i;
46 total++;
}
47 }
48 }
1 つのクリティカルセクションを追加することで、omp_prime.c 内のほかの 2 つのデータ競合も解決されます。行 45 の prime[] でのデータ競合だけでなく、行 46 の total でのデータ競合も解決します。4 つ目の、 行 18 の pflag[] の read と行 21 の pflag[] への write とのデータ競合は、不正な結果につながることはないため、実際には良性のデータ競合です。良性のデータ競合の解決は重要ではありません。
次に示すように行 45 と 46 をクリティカルセクションに移動することもできますが、この変更はプログラムの問題の解決になりません。
42 #pragma omp parallel for .
43 for (i = 2; i < N; i++) {
44 if ( is_prime(i) ) {
#pragma omp critical
{
45 primes[total] = i;
}
#pragma omp critical
{
46 total++;
}
47 }
48 }
スレッドが排他的ロックを使用して total へのアクセスを制御していないため、行 45 と 46 を含むこのクリティカルセクションによってデータ競合は解消されます。行 46 を含むクリティカルセクションは、total の演算値が必ず正しくなるようにします。しかし、依然としてプログラムは正しくありません。2 つのスレッドが、同じ total 値を使用して primes[] の同じ要素を更新する可能性があります。さらに、primes[] 内の一部要素にまったく値が代入されない可能性があります。
2.4.3.2 pthr_prime.c 内のバグの修正
次に pthr_prime.c のバグを修正する方法を示します。このファイルの全コードリストは、「2.1.2 pthr_prime.c の全コード」にあります。
pthr_prime.c 内の行 39 の total の read と行 40 の total への write とのデータ競合を解消するには、1 つの相互排他 (mutex) を使用します。この追加によって、pthr_prime.c 内のほかの 2 つのデータ競合、行 39 の prime[] でのデータ競合と行 40 の total でのデータ競合も解決します。
行 55 の i への write と行 35 の i の read とのデータ競合、また行 22 の pflag[] でのデータ競合は、異なるスレッドによる変数 i への共有アクセスの問題であることがわかります。pthr_prime.c 内の初期スレッドはループで子スレッドを作成して (ソース行 55 〜 57) 、その子スレッドをディスパッチして、関数 work() を操作します。ループのインデックスの i は、work() にアドレスで渡されます。すべてのスレッドが i について同じメモリー位置にアクセスするため、各スレッドに対する i の値が一意でなくなり、初期スレッドがループのインデックスをインクリメントするのに伴って値は変化します。異なるスレッドが同じ i 値を使用するため、データ競合が発生します。
この問題を解決する 1 つの方法は、i を work() に値渡しする方法です。この方法によって、すべてのスレッドが必ず一意の値を持つ専用の i のコピーを持つようになります。primes[] に関する行 39 の write アクセスと行 65 の read アクセスとのデータ競合の解消では、前述の行 39 と 40 に使用した相互排他ロックと同じロックを使用して行 65 を保護できます。しかし、これは正しい解決方法ではありません。真の問題は、子スレッドが work() で total および primes[] を更新している間に、メインスレッドが結果を報告する (行 50 〜 53) 可能性があることです。相互排他ロックを使用しても、スレッド間の適切な順序付けのための同期はとられません。1 つの正しい修正方法は、メインスレッドですべての子スレッドがジョインするまで待ってから結果を出力することです。
次に修正した pthr_prime.c を示します。
1 #include <stdio.h>
2 #include <math.h>
3 #include <pthread.h>
4
5 #define THREADS 4
6 #define N 3000
7
8 int primes[N];
9 int pflag[N];
10 int total = 0;
11 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
12
13 int is_prime(int v)
14 {
15 int i;
16 int bound = floor(sqrt(v)) + 1;
17
18 for (i = 2; i < bound; i++) {
19 /* 判定済み合成数のチェックは不要 */
20 if (!pflag[i])
21 continue;
22 if (v % i == 0) {
23 pflag[v] = 0;
24 return 0;
25 }
26 }
27 return (v > 1);
28 }
29
30 void *work(void *arg)
31 {
32 int start;
33 int end;
34 int i;
35
36 start = (N/THREADS) * ((int)arg) ;
37 end = start + N/THREADS;
38 for (i = start; i < end; i++) {
39 if ( is_prime(i) ) {
40 pthread_mutex_lock(&mutex);
41 primes[total] = i;
42 total++;
43 pthread_mutex_unlock(&mutex);
44 }
45 }
46 return NULL;
47 }
48
49 int main(int argn, char **argv)
50 {
51 int i;
52 pthread_t tids[THREADS-1];
53
54 for (i = 0; i < N; i++) {
55 pflag[i] = 1;
56 }
57
58 for (i = 0; i < THREADS-1; i++) {
59 pthread_create(&tids[i], NULL, work, (void *)i);
60 }
61
62 i = THREADS-1;
63 work((void *)i);
64
65 for (i = 0; i < THREADS-1; i++) {
66 pthread_join(tids[i], NULL);
67 }
68
69 printf("Number of prime numbers between 2 and %d: %d\n",
70 N, total);
71 for (i = 0; i < total; i++) {
72 printf("%d\n", primes[i]);
73 }
74 }
2.5 誤検出 (False Positive)
スレッドアナライザは、実際には発生しなかったデータ競合を報告することがときどきあります。それらを誤検出と呼んでいます。たいていの場合、誤検出は 「2.5.1 ユーザー定義の同期化機構」または 「2.5.2 異なるスレッドによって再利用されるメモリー」が原因です。
2.5.1 ユーザー定義の同期化機構
スレッドアナライザは、OpenMP 指令、POSIX スレッド、および Solaris スレッドの提供する大半の標準同期化 API および構造を認識できます。ただし、ユーザー定義の同期化機構は認識できず、コードにそうした同期化機構が含まれていると、実際にはそうではないデータ競合を報告することがあります。たとえば、スレッドアナライザは、CAS 命令や busy-waits を使用した post および wait 操作などによるロックの実装を認識できません。次に、POSIX スレッド条件変数が一般的な使われ方をしているプログラムでの誤検出データ競合の典型的な例を示します。
/* 初期状態では ready_flag は 0 */
/* スレッド 1: 生産者 */
100 data = ...
101 pthread_mutex_lock (&mutex);
102 ready_flag = 1;
103 pthread_cond_signal (&cond);
103 pthread_mutex_unlock (&mutex);
...
/* スレッド 2: 消費者 */
200 pthread_mutex_lock (&mutex);
201 while (!ready_flag) {
202 pthread_cond_wait (&cond, &mutex);
203 }
204 pthread_mutex_unlock (&mutex);
205 ... = data;
通常、pthread_cond_wait() 呼び出しは、プログラムエラーや間違った呼び起こしから保護するために、述語を評価するループの中で行われます。しばしば、述語の評価および代入は相互排他ロックで保護されます。前述のコードでは、スレッド 1 は行 100 で変数 data の値を生成し、行 102 で ready_flag の値を 1 に設定して、データが生成されたことを示します。そして、pthread_cond_signal() を呼び出して、消費者スレッドのスレッド 2 を呼び起こします。スレッド 2 は、ループ内で述語 (!ready_flag) を評価します。このスレッドは、フラグが設定されていることを検出すると、行 205 でデータを消費します。
行 102 の ready_flag の書き込みと行 201 の ready_flag の読み取りが同じ相互排他ロックで保護されているため、この 2 つのアクセスの間にデータ競合はなく、スレッドアナライザはそのことを正しく認識します。
行 100 の data の write と行 205 の data の read は、相互排他ロックによって保護されていません。しかし、プログラムのロジックでは、フラグ変数 ready_flag があるために、行 205 の read は必ず行 100 の write のあとに発生します。このため、データへのこれら 2 つのアクセスの間にはデータ競合はありません。ただし、pthread_cond_wait() への呼び出し (行 202) が実行時に実際に呼び出されなかった場合、スレッドアナライザは、この 2 つのアクセスの間にデータ競合が存在すると報告します。行 201 が実行されないうちに行 102 が実行されていて、行 201 が実行されると、ループの判定文の評価は偽となり、行 202 は実行されません。スレッドアナライザは、pthread_cond_signal() 呼び出しと pthread_cond_wait() 呼び出しを監視し、同期されていると認識するために、それらを対のものとしてみなすことができます。行 202 の pthread_cond_wait() が呼び出されない場合には、行 205 の読み取りの前に行 100 の書き込みが 必ず実行されることを認識しません。このため、同時に実行されたとみなし、両者の間にデータ競合があると報告します。
この種の誤検出データ競合をなくすために、スレッドアナライザには一群の API が用意をされており、ユーザー定義の同期化機構が実行されたことをスレッドアナライザに通知させることができます。詳細は、「A.1 スレッドアナライザのユーザー API」を参照してください。
2.5.2 異なるスレッドによって再利用されるメモリー
メモリー管理ルーチンには、別のスレッドが使用できるように、スレッドによって解放されたメモリーを再利用するものがあります。スレッドアナライザは、異なるスレッドによって使用される同じ位置のメモリーについて、使用される期間を正しく認識することができない場合があります。この時、スレッドアナライザは誤検出データ競合を報告します。次は、この種の誤検出データ競合の例です。
/*----------*/ /*----------*/
/* スレッド 1 */ /* スレッド 2 */
/*----------*/ /*----------*/
ptr1 = mymalloc(sizeof(data_t));
ptr1->data = ...
...
myfree(ptr1);
ptr2 = mymalloc(sizeof(data_t));
ptr2->data = ...
...
myfree(ptr2);
スレッド 1 と 2 は同時に実行され、それぞれ専用メモリーとして使用する大量のメモリーを割り当てます。ここで、mymalloc() ルーチンは、直前の myfree() の呼び出しによって解放されたメモリーを供給すると仮定します。スレッド 1 が myfree() を呼び出す前にスレッド 2 が mymalloc() を呼び出した場合、ptr1 と ptr2 は異なる値を取得し、2 つのスレッドの間にデータ競合はありません。ただし、スレッド 1 が myfree() を呼び出したあとでスレッド 2 が mymalloc() を呼び出した場合は、ptr1 と ptr2 は同じ値を持つ可能性があります。スレッド 1 はそのメモリーにアクセスしなくなっているため、データ競合はありません。しかし、mymalloc() がメモリーを再利用していることを認識していない場合、スレッドアナライザは ptr1 データの write と ptr2 データの書き込みの間にデータ競合があると報告します。この種の誤検出は、C++ アプリケーションで C++ ランタイムライブラリが一時変数用のメモリーを再利用する場合に起こることがよくあります。また、独自のメモリー管理ルーチンを実装しているユーザーアプリケーションでもよく起きます。現状では、スレッドアナライザは標準の malloc()、calloc()、および realloc() インタフェースを使用して実行されるメモリーの割り当てと解放操作を認識できます。
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