元記事：Dealing with Benign Data Races the C++ Way | Corensic, Bartosz Milewski氏, 2011/5/9
自分自身の理解のために日本語訳を行ったC++11のデータ競合に関する記事。
良性データ競合へのC++的対応
データ競合(data race)は未定義動作(undefined behavior)を引き起こします。でも、実際にはどれほどマズいことなのでしょうか？前回の記事では良性のデータ競合*1にふれて、Windowsカーネルでの実例をいくつか示しました。カーネルの場合は、特定プロセッサ向けに特定コンパイラを用いてコンパイルされるため、これらの実例は正しく動作していました。ただし一般論としては、コードをポータブルにしたいならば、データ競合を含んでいてはいけません。以上。
明確に“未定義(undefined)”と定義されたものに判断を下すことは出来ません。従って、当然ながら、データ競合を含むプログラムの正しさを証明することは出来ません。しかしながら、ごく一部の人々は正しさの証明に取り組み、そして大抵は議論後に（言葉少なに）「なぜ上手くいかないのか分からん。正しいに違いない。」とします。私はこれを“想像力の欠如による証明”と呼んでいます。並行性のエキスパートになりたいなら、常に想像力を膨らませなければいけません。それでは始めましょう。
前回記事の読者のひとりDuarate Nunesは、良性データ競合の興味深い例を投稿しました。コードを示します：
int owner = 0; int count = 0; Lock lock; bool TryEnter() { if (owner == /* get thread id */) { // RACY_READ count += 1; return true; } if (lock.TryEnter()) { owner = /* get thread id */; // LOCKED return true; // LOCKED } return false; } void Exit() { // LOCKED if (count != 0) { // LOCKED count -= 1; // LOCKED return; // LOCKED } // LOCKED owner = 0; // LOCKED lock.Exit(); // LOCKED }
ロックの中で実行されるコードをLOCKEDコメントで強調しました（正しいプログラムでは、'Exit'は常にロック取得の後で呼び出されます）。変数'count'は常にロックの中でアクセスされ、データ競合は生じない事に留意してください。しかし、変数'owner'はロックの外RACY_READコメント箇所でreadされる可能性があります。これが今回対象とするデータ競合です。
このコードを解析し、何がダメなのか想像してみましょう。ただ、コンパイラやプロセッサをあまり疑い過ぎないで。例えば競合するreadがロック内に置かれるなどしてデータ競合が取り除かれれば、コードはもちろん正しく動作します。
ここからは、正しさの“証明”を試みたものです。まず、Duarteは「'owner'変数の値を0とし、プロセスの各スレッドID」を観測しました。これは幾らか理にかなっていますよね？競合するreadが何らかの効果をもつのは、'owner'の値が現在のスレッドIDと等しいときだけです。ただし、その値はまさにロックの中の現スレッドによってwriteされた値です。
'owner'からreadするとき2つの可能性があります：まだロック取得中でありreadは競合しないか、または既にロックを解放済みかです。ただし、ロックの解放は現在のスレッドが'owner'を0クリアした後でしか起こりません。
これは単一スレッドを仮定した解析であり、シングルスレッド下では全イベントが必ず順序付けられることに注意してください（現時点ではメモリフェンスやacquire/releaseセマンティクスの議論は必要ありません）。同一スレッド上でのwriteに続くreadでは、write前の値を見ることはできません。もしそれができるとしたら、通常のシングルスレッドプログラムを壊してしまうでしょう。さらに、他スレッドは値0をそのスレッドIDで上書きするかもしれませんが、現在のスレッドID値には絶対になりえません。そういう事です...
さぁ気をしっかり持って。コンパイラやプロセッサがプログラムを“最適化”する例を示します：
void Exit() { if (count != 0) { count -= 1; return; } owner = 42; // OPTIMIZED owner = 0; lock.Exit(); }
こんなのは馬鹿げているし、正気のコンパイラなら起こり得ない？しかし事実であり、プログラムの正当な変換結果です*2。この変更の影響は、もちろん現在のスレッドからは観測できません。データ競合がなければ他スレッドからもまた観測不能です。いま、ちょうどIDが42の不幸なスレッドがこの値を観測すると間違いが起こります。ただし、値42を観測し得るのは競合するreadからのみです。例えば、ロックの中における'owner'のreadでは決してこの値を観測しません。さらに、変数'owner'が'atomic'として定義された場合も決して観測されません：
std::atomic<int> owner = 0
atomic変数に対するストア／ロード操作は、既定で逐次一貫(sequentially consistent)となります。残念ながら、逐次一貫性(sequentially consistency)のためには、x86アーキテクチャでさえ高コストなメモリフェンスを必要とします。私たちの例ではこれだとやり過ぎです。ここでトリックを使います：read／writeにおいて逐次一貫性は不要だとコンパイラに伝えるのです。つまり、何ら順序制約(ordering constraints)を課さずにatomic変数からreadするには：
owner.load(memory_order_relaxed)
少なくとも私が知る限りのプロセッサにおいて、この“relaxed（緩和された）”操作は何らメモリフェンス効果を持ちません。
オリジナルと等価であり、正しくかつポータブルなバージョンのコードを示します：
std::atomic<int> owner = 0; int count = 0; Lock lock; bool TryEnter() { if (owner.load(memory_order_relaxed) == /* get thread id */) { count += 1; return true; } if (lock.TryEnter()) { owner.store(/* get thread id */, memory_order_relaxed); return true; } return false; } void Exit() { if (count != 0) { count -= 1; return; } owner.store(0, memory_order_relaxed); lock.Exit(); }
何が変わったんでしょう？コンパイラが前と同様のひきょうな手段で、'owner'変数へ値42を一瞬でも格納することは無いのでしょうか？こんどは大丈夫！変数を'atomic'として宣言したため、コンパイラはもはやwriteが他スレッドから観測されないと仮定できません。（訳注：writeした値は常に他スレッドから観測される可能性があり、コンパイラは前回のようにwriteを勝手に挿入することができない。）
新しいバージョンにはデータ競合がありません。C++標準（のドラフト）では、最も制約が緩い形式のものでも'atomic'変数はデータ競合の要因にはならない、と明確に既定しています。（訳注：N3337 1.10/p5にも同一センテンスが存在する。）
C++ Draft Standard, (1.10.5):
[...] "Relaxed" atomic operations are not synchronization operations even though, like synchronization operations, they cannot contribute to data races.
この変更により、（何も示していませんが）C++メモリモデルの公理を用いることで、正しさの“証明”はより厳密な証明になったと信じています。これで正しくポータブルなコードと、高パフォーマンスの両方を得る事ができました。ちなみに、同じトリックは前回記事の誤り許容カウンタ(lossy counter)でも用いられています。
警告：オペレーティングシステムカーネルや並行ライブラリの開発者を除いて、このような弱い(weak) atomic変数を利用するコーディングスタイルを推奨しません。
謝辞
C++メモリモデルに関する私の仮定を検証し有益な意見を頂いた、Luis Ceze、Hans Boehm、Anthony Williamsに感謝します。
*1:訳注：同記事ではWindowsカーネルのデータ競合検知ツールを取り上げ、正しさと性能のトレードオフから“良性(benign)のデータ競合”が実際に存在すると言及している。例えば、誤り許容カウンタ(lossy counter)はパフォーマンス計測用にカウントアップを行うが、データ競合によるカウント欠落を許容する。もちろん高コストなatomic機構を利用すれば厳密値が求まるが、本処理に対してパフォーマンス上の悪影響を及ぼすため採用しない。
*2:訳注：元記事ではかなり極端な例示となっているが、もう少し現実的なシナリオは次の通り：あるプロセッサの“自然な”整数サイズが2バイトで、プログラムのint型が4バイトである場合、int型への代入文が複数の機械語命令へ変換される。
