yohhoyの日記

技術的メモをしていきたい日記

(翻訳)良性データ競合は有害である

元記事:Benign Data Races Considered Harmful | Corensic, Bartosz Milewski氏, 2011/6/7

自分自身の理解のために日本語訳を行ったC++11でのデータ競合に関する記事。(タイトルはいわゆる"〜 Considered Harmful"ネタ)

良性データ競合は有害である

最近、本ブログで大いに論争を巻き起こした良性データ競合(訳注:同記事の拙訳)に関する一連の投稿があり、また多数のディスカッションが行われました。2つの陣営が形成され、一方はデータ競合は良性たりえないと主張し、他方はデータ競合はパフォーマンスを得るために必要だと主張しています。そしてデータ競合の定義すらも合意できていないと分かりました。特に、C++11での定義は従来の概念からは逸しているようです。

データ競合っていったい何?

まず初めに、議論の対象を明確にしましょう。ここでのデータ競合は低レベルでのデータ競合を意味しており、複数のメモリ位置やスレッド毎の複数アクセスが関係するような高レベルな競合とは対極にあります。データ衝突(data conflict)の意味は、同一メモリ位置に複数スレッドがアクセスし、そのうち少なくとも1つはwriteである、と皆合意しています。ただしデータ衝突はデータ競合の必要条件ではありません。競合が生じるには、もう一つの条件が真となる必要があります:アクセスが“同時(simultaneous)”に生じることです。

残念ながら、並行システムにおける同時性(simultaneity)はwell-definedな用語ではありません。Leslie Lamportは初めて分散システムについて、ガリレオ力学のような絶対時間ではなく、特殊相対性理論のような同時性の非独立概念*1による観察を行いました。つまり、データ競合を定義するのは同時性の概念に依るのです。

同時がどのようなものであるかと定義するのではなく、どのようなものでないと定義する方が簡単ですよね?実際、あるイベントが他のイベントよりも前に起こると言えるならば、両イベントは同時でないと確信できます。そのため、データ競合の定義においては有名な“happened before”関係が用いられるのです*2特殊相対性理論におけるこの種の関係性は、光速よりは速く伝搬されないメッセージの交換によって規定されます。メッセージの送信行為は、常に同メッセージの受信よりも前に生じ(happens before)ます。並行プログラムにおけるこの種の通信は、同期アクションによって行われます。従ってデータ競合のもう一つの定義は:同期(synchronization)を介さないメモリ上の衝突です。

同期アクションの最も単純な例はロックの取得/解放です。このコードを実行する2つのスレッドを想像してください:

mutex.lock();
x = x + 1;
mutex.unlock();

どんな実際の実行においても、両スレッドの共有変数xへのアクセスは同期により分離されます。Happens-before(HB)矢印は、常にロック解放スレッドからロック獲得スレッドに向いています(訳注:ここでの“矢印”は有向グラフのエッジのこと)。例えば:

# スレッド1 スレッド2
1 mutex.lock();
2 x = x + 1;
3 mutex.unlock();
4 mutex.lock();
5 x = x + 1;
6 mutex.unlock();

HB矢印は3から4を指しており、2と5での衝突するアクセスは明確に分離されます。

慎重に選んだ“実際の実行(actual execution)”という語に気をつけてください。ミューテックス(mutex)が相互排他を保証するため、データ競合を生じる次の実行は決して起こり得ません。

# スレッド1 スレッド2
1 mutex.lock();
2 mutex.lock();
3 x = x + 1; x = x + 1;
4 mutex.unlock();
5 mutex.unlock();

データ競合の定義においては、起こり得る実行の選択が重要な役割を果たすことが分かりました。私が知る限りのあらゆるメモリモデルでは、逐次一貫性実行(sequentially consistent executions)のみがデータ競合の検証に用いられます。逐次一貫でない実行(non-sequentially-consistent executions)も現実には起こり得ますが、データ競合の検証では考慮されません。

実際多くのプログラミング言語では、データ競合フリーな(data-race-free)プログラムのあらゆる実行に逐次一貫性があるとする、DRF保証を提供しようとします。議論のループにびっくりしないで:逐次一貫性実行を用いたデータ競合フリーの証明からスタートし、もしデータ競合が一切見つからなければ、あらゆる実行に逐次一貫性があると結論付けます。しかし、この方法でデータ競合が見つかったならば、逐次一貫でない実行もあり得ると分かります。

逐次一貫性/データ競合なし 逐次一貫でない/不可能!
逐次一貫性/データ競合あり 逐次一貫でない/可能

DRF保証。もし逐次一貫性実行においてデータ競合が無ければ、逐次一貫でない実行は存在し得ません。しかし、逐次一貫性実行においてデータ競合があるならば、逐次一貫でない実行が存在し得ます。

ここまで述べた通り、データ競合の定義には“同時(simultaneous)”や“同期(synchronization)”が意味するところを正確に規定し、かつ、どのような実行が行われるかを明確にする必要があります。

Javaメモリモデル

Java言語では“synchronized”メソッドによる伝統的な排他制御に加え、volatile変数と呼ばれる別の同期手段が存在します。volatile変数への任意のアクセスは同期アクションとして扱われます。つまり同一オブジェクトに対する連続したアンロック/ロック間だけではなく、あるvolatile変数への連続するアクセス間にもhappens-before矢印を描くことができます。この拡張を考慮して、Javaは伝統的なDRF保証を提供します。データ競合フリーなプログラムのセマンティクスは、逐次一貫性の観点から明確に定義され、そして全てのJavaプログラマを幸せにします。

ただしJava言語ではこれに留まらず、データ競合のあるプログラムのセマンティクスも一部与えようとします。アイデアとしては高尚です;プログラマも人間である以上、誤ったプログラムを書いてしまいます。データ競合のあるプログラムは全て未定義動作と宣言するのは簡単ですが、もし未定義動作が深刻なセキュリティホールになるとしたら、皆をひどく神経質にさせてしまいます。そこでJavaメモリモデルではDRFに加えて、データ競合による未定義動作がプログラムのどこからか勝手に値をもってこない事を保証します(例えば、侵入者に対するセキュリティ認証を想像してください)。

データ競合のセマンティクスを定義する試みは失敗していると今日では広く認識されており、つまりJavaメモリモデルは壊れているのです(これはHans Boehmの引用)。

C++メモリモデル

なぜデータ競合の良い定義がそれほど重要なのでしょう?DRF保証のため?Javaメモリモデルに遅れをとったことが動機のようです。データ競合の不在は逐次一貫性プログラムのサブセットを定義し、それゆえにwell-definedなセマンティクスを持ちます。ただし2つの性質:逐次一貫性とwell-definedセマンティクスを持つことは、必ずしも同義ではありません。結局のところ、Javaでは逐次一貫でないプログラムのセマンティクスを(たとえ不必要でも)定義しようとしました。

さて、C++言語はちょっと違うアプローチをとります。C++メモリモデルは下記3カテゴリへの分類に基づいています:

  • 逐次一貫性をもつもの
  • 逐次一貫ではないが、セマンティクスを定義するもの
  • 未定義のセマンティクスによる間違ったプログラム

最初のカテゴリは競合フリーなJavaプログラムに良く似ています。Javavolatileには、C++11では既定のatomicがとって代わります。すぐ後で述べるとおり、この単語“既定の”には重要な意味があります。Java同様、DRF保証はプログラム全体で保たれます。

全ての論争の元凶は2番目のカテゴリです。こちらはセキュリティ上の理由ではなく、パフォーマンス上の理由から導入されました。逐次一貫性は多くのマルチプロセッサシステムで高コストです。これが今や多くのC++プログラマが、未定義動作のリスクを冒しても“良性”データ競合を用いる理由です。Hans Boehmの論文「How to miscompile programs with "benign" data races」は、このアプローチに完全に叩き潰しました。彼はコンパイラ最適化器がいかに合理的に“良性”データ競合のプログラムを台無しにするかを、例示を重ねて示しました。

幸いC++11では逐次一貫性を緩和する方法を提供しており、これにより高パフォーマンスと(複雑だが)well-definedなセマンティクスの安全性を達成できます。つまりC++プログラムにおける2番目のカテゴリでは、relaxed memory ordering(緩和されたメモリ順序)セマンティクスをもつatomic変数を利用します。前回記事から引用した典型構文を示します:

std::atomic<int> owner = 0;
...
owner.load(memory_order_relaxed);

そして、ここが意見が分かれる点です:C++メモリモデルによれば、上記loadのような緩和された(relaxed)メモリ操作は、同期アクションとみなされないにも関わらず、データ競合の一因とはなりません*3。データ競合の定義を思い出してください:同期を介しない衝突するアクション?もはや定義が成り立ちません。

C++標準はこのように決定しました;セマンティクスが定義されない衝突のみをデータ競合と呼ぶと*4

一部のatomic操作は同期を導入することに留意ください。例えば、memory_order_releaseによるwriteアクセスは、他方のmemory_order_acquireアクセスより前に生じ(happens before)ます。ただし、ある実行において後者が前者に続いた場合のみです(もし逆順なら同期にはなりません)。(訳注:実際に"happens before"関係が成り立つか否かは、起こり得る実行の選択肢のうち現実に実行されたものに依存する。)

結論

結局のところC++11プログラマにとって何を意味するのでしょう?データ競合に対する言い訳はもはや存在しません。パフォーマンスのために良性データ競合が必要なら、弱い(weak) atomicを使ってコードを書き換えてください。弱いatomicならばwell-definedなセマンティクスを持たせつつ、良性データ競合に相当するパフォーマンスを達成できます。伝統的な“良性の”競合は、コンパイラによる最適化やトリッキーなアーキテクチャ上では壊れたも同然です。しかし弱いatoimcを使うなら、コンパイラは正しいセマンティクスを維持し、プログラムは常に正しく実行されるでしょう。また当然ながらatomic変数はreadとwriteの分解を避けるように配置されるでしょう。(訳注:変数アライメントのこと。そのアーキテクチャにおいて“自然な”アドレス境界に配置される。)

しかも、C++11からはwell-definedなメモリセマンティクスが存在するため、コンパイラ製作者は最適化において保守的である必要がなくなりました。プログラマが共有変数を明示的にatomicとしなければ、シングルスレッドプログラムでさえ、コンパイラには最適化の自由度が与えられます。つまり従来の良性データ競合による巧妙なトリックは、x86のような比較的シンプルなアーキテクチャ上でさえ、もはや動作保証されません。たとえばコンパイラは、後でちゃんと書き戻しを行う限り、誤り許容カウンタ(lossy counter)や2値フラグ(binary flag)で一時領域を利用する自由度があります。他スレッドが競合するコードを通じてこれらの変数にアクセスしたら、“未定義動作”の結果として気まぐれな値が見えるでしょう。注意してください!

*1:訳注:Lamportの論理クロック。http://d.hatena.ne.jp/ita-wasa/20081119/1227061296 などを参考。本記事の後でふれる逐次一貫性(sequential consistency)はLeslie Lamportが定義したモデル。唐突に“ガリレオ力学”や“特殊相対性理論”が登場したのは、Lamport氏がこれらの理論(絶対時間 vs 相対時間)から着想を得たことによる(っぽい)。

*2:訳注:C++11規格での厳密な用語は“happens before”(N3337 1.10/p12)

*3:訳注:N3337 1.10/p5のNoteより引用:"'Relaxed' atomic operations are not synchronization operations even though, like synchronization operations, they cannot contribute to data races."

*4:訳注:C++11規格での表現は"The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other."(N3337 1.10/p21)