uchan note

プログラミングや電子工作の話題を書きます

データ競合と happens-before 関係

プログラム解析 C++

この記事は，マルチスレッドのプログラムでしばしば見る，そして発見が困難であるバグ「データ競合」と，それを見つけるのによく使われる「happens-before 関係」について解説します。 筆者は特に x86-64 アーキテクチャにおけるバグ検出に興味がありますので，一般的な話というよりは x86-64 に寄せた話になります。

想定読者

  • データ競合バグの発生原理やアトミック変数を使ったバグの防止方法を知りたいと思っているプログラマ
  • データ競合バグを検出する手法，特に happens-before 関係を勉強したいプログラム解析手法の研究者

x86-64 & C++ を例に説明しますが，その他のアーキテクチャや言語にも通じる話もたくさんあります。

記事の概要

データ競合，アトミック変数，逐次一貫性，happens-before 関係などの用語に興味がありますか？

この記事はマルチスレッドで良く問題となるデータ競合という種類のバグに詳しくなり，データ競合バグを起こさないために重要となる happens-before 関係とは何かを学ぶ記事です。 それらと関連の深いアトミック変数や逐次一貫性についても説明しました。

2020/07/16 追記：本記事の内容を解説した講義動画をアップロードしました。是非ご覧ください。 youtu.be

目次

  • データ競合
    • データ競合の定義を確認します
    • ある論文での定義，Java での定義，C++ の定義を比較します
  • データ競合とアトミック性
    • データ競合がある場合にメモリ書き込みのアトミック性が崩壊することを確認します
  • リオーダと並行性バグ
    • マルチスレッド・プログラムにおいてリオーダが致命的な問題を引き起こすことを確認します
    • リオーダとはプログラムの命令順が入れ替わることです
  • データ競合とリオーダ
    • データ競合がリオーダを引き起こすことを説明します
    • std::memory_order::seq_cst を使うとリオーダが防げることを確認します
  • 逐次一貫性
    • 逐次一貫性モデルを説明し，サンプルコードがどんな機械語にコンパイルされるかを見ます
  • acquire/release
    • 逐次一貫性より弱い acquire/release 制約を使うとコンパイルがどう変化するか確認します
  • happens-before 関係
    • acquire/release と紐づけて happens-before 関係を説明します
    • メモリ読み書き命令の間に happens-before 関係が成り立つとデータ競合が起きないことを見ます

データ競合

データ競合（data race）とは直感的に言えば共有変数の値が変な値になってしまうことです。 定義はいろいろあるようですが，1 では次のように定義しています（訳は筆者による）。

同一のメモリ位置に対する 2 つのアクセスαとβは，αとβが異なるスレッド上で実行され，同期されておらず（すなわち並行），少なくとも片方が書き込みであれば外見上のデータ競合があると言う。

もう少し噛み砕くと「共有変数を並行に読み書きする場合に外見上のデータ競合がある」ということです。

ここでいう「外見上のデータ競合」は an apparent data race を筆者が訳した言葉です。 このニュアンスは，本当は起こらないかもしれないけど，同期の有無だけを頼りに機械的に判定すると「存在する」と判定されるデータ競合，といった感じです 2。 本当に起こり得るデータ競合に対し，もしかしたら発生しないかもしれないので「外見上の」ということになります。 一見するとデータ競合があるように思える，と捉えてもいいでしょう。

そして「同期されておらず（すなわち並行）」とは，2 つのアクセスαとβが happens-before 関係によって順序付けられていない，という意味です。 happens-before 関係は後で詳しく説明します。

Java SE 14 の仕様書にあるデータ競合の定義 も見てみます（訳は筆者による）。

プログラムが happens-before 関係によって順序付けられない 2 つの競合アクセスを持つとき，データ競合を含む，と言う。

「競合アクセス」は conflicting accesses を筆者が訳した言葉です。 競合アクセスの定義 を紹介します（訳は筆者による）。

同じ変数に対する 2 つのアクセス（読み，および書き）は，少なくとも 1 つが書き込みの場合に「競合している」と言う。

この定義には「2 つの異なるスレッドからアクセスする」という記述がありませんが，この定義が書かれている項目が複数のスレッドで共有される変数に関する項目ですから， 「同じ変数に対する 2 つのアクセス」は 2 つの異なるスレッドから行われると解釈できます。

データ競合と競合アクセスの定義を合わせて考えれば，Java での「データ競合」は，先ほどの「外見上のデータ競合」と同じ定義であることが分かります。

最後に C++ でのデータ競合の定義を見てみます。N4861 6.9.2.1 Data races の 21 段落目 に定義があります。 この定義は Java のそれとほとんど同じです。ただ，C++ はシグナルハンドラの仕組みをサポートしているため，スレッドに加えてシグナルハンドラでもデータ競合が発生しうる点が少し違います。

C++ では Java とは異なり，未定義動作というものがあります。21 段落目にこのように書いてあります（訳は筆者による）。

そのようなデータ競合はいずれも未定義動作を引き起こす。

未定義動作ですので，鼻から悪魔 が出てきても文句は言えないということです。 未定義動作が無い Java に比べると，データ競合の深刻度がちょっと違うように思えてきます。

データ競合とアトミック性

データ競合がもたらす問題として，ぱっと思い付くのは不整合なデータが読めてしまうことです。 共有変数に値を書く動作がアトミックではない場合に，その変数のもともとの値でも，今書こうとした値でもない値が読み出せてしまう，というものです。

スレッド 1 スレッド 2
A = 0xdeadbeef; r1 = A;

初期値が A == 1 だったとします。変数 r1 には何が読まれるでしょうか？1 でしょうか。0xdeadbeef でしょうか。 実はそれ以外の値が読まれ得るのです。 それが起こるのは A への書き込みがアトミックでないときです。

アトミック性（原子性，不可分性）とは，その操作の途中状態が外部（例えば，他のスレッド）から観測できないことです。 ここでいう「観測できない（見えない）」は，ハードウェア的にどう頑張っても観測できないように作られている仕組みを使うのはもちろん，ロックなどの同期機構を用いて「見ないようにする」ことでも達成できます。

変数へ値が完全に書かれたか，あるいはまったく書かれていないかのどちらかの状態しか観測できないとき，その変数への書き込みはアトミックです。 逆に，アトミック性が無い場合は外部から途中状態が観測できてしまいます。

1 回のメモリ書き込み操作で 2 バイトしか書けない CPU があったとすると，上記の A への書き込みは 2 回に分割されます。 すなわち 0xdead と 0xbeef です。 CPU が仮に 0xdead から書き込みを行ったとすると，メモリの値は一瞬だけ 0xdead0001 となるでしょう。 この時にスレッド 2 が変数の読み込みをすると 1 でも 0xdeadbeef でもない，0xdead0001 という値が読み出せるかもしれません。 （キャッシュの動作なども関係してくるため，もっと別の値になるかもしれません。CPU の仕様に依存します。） あるいは，メモリからの読み出しがアトミックではない場合にも同様の問題が生じます。

多くの CPU ではアラインされていないメモリ領域のアクセスはアトミックになりません。 x86-64 アーキテクチャでは，2 バイト変数であれば 2 の倍数のアドレスに，4 バイト変数であれば 4 の倍数のアドレスに，8 バイト変数であれば 8 の倍数のアドレスに置かれていれば，それらの変数への（mov 命令による）アクセスはアトミックです。 しかし，それら以外の場所に置いてある変数へのアクセスはアトミックではありませんから，データ競合がある場合に予想外のデータが読めてしまう可能性があるのです。

x86-64 アーキテクチャではアラインされたメモリ領域へのアクセスがアトミックになります。 x86-64 向けの C/C++ コンパイラは，変数を自動的にアラインされたメモリ領域に配置してくれるため， 先ほど紹介したような定義によるデータ競合があったとしても，実際には不整合なデータが読めてしまうことはないのです。 （もちろん，mov 命令 1 つで読み書きできないような大きな変数はその限りではありませんが。）

では x86-64 においてはデータ競合という概念は不要でしょうか？ いいえ，依然として重要です。 なぜならデータ競合は意図しないリオーダの原因となるからです。

リオーダと並行性バグ

リオーダとはプログラムのステートメントや命令を入れ替えることです。

Java でも C/C++ でも，コンパイラはプログラムの実行に影響が出ない範囲で命令を入れ替えることができます。 コンパイラだけでなく，CPU も機械語レベルのリオーダを行います。 もしかしたら，メモリ階層の構造（キャッシュの構成）によってあたかもリオーダされたかのように見えることもあり得ます。

Java でのリオーダ例

Java のメモリモデル に紹介されている例は，データ競合がある場合に直感的ではない動作が発生することを示します。 簡単に説明します（訳は筆者による）。

Table 17.4-A. ステートメントの並べ替えによる驚くべき結果 - 元のコード

スレッド 1 スレッド 2
1: r2 = A; 3: r1 = B;
2: B = 1; 4: A = 2;

r1 と r2 はローカル変数です。A と B は共有変数で，初期値は A == B == 0 です。

2 つのスレッドがどのような順番で動作しようとも r2 == 2 かつ r1 == 1 とはなり得ないと思うでしょう。 しかし，実際には起こり得ます。 なぜなら，Java コンパイラはスレッド単体の動作に影響を及ぼさない範囲で命令を入れ替えても良いことになっているからです。

スレッド 1 だけを取り出して考えると，操作 1（r2 = A;）と操作 2（B = 1;）はどちらを先に実行しても大丈夫です。スレッド 2 の操作 3，4 に関しても入れ替えが可能です。 仮に次のように操作の入れ替えが発生したとします。

Table 17.4-B. ステートメントの並べ替えによる驚くべき結果 - 合法なコンパイラ変換

スレッド 1 スレッド 2
B = 1; r1 = B;
r2 = A; A = 2;

入れ替え後の表をじっくり眺めると r2 == 2 かつ r1 == 1 になるようなスレッドの動作順が分かると思います。 そう，スレッド 1 が少し動作して B = 1; を実行した後スレッド 2 が動作し，その後スレッド 1 に戻ってくるパターンですね。

上記のコードがこんな変な動きをしたのはデータ競合があるからです。 共有変数 A，B に着目すると，同期することなく 2 つのスレッドから書き込みと読み込みが行われていることが分かります。 これはまさにデータ競合の定義に当てはまっています。

コンパイラが命令を並べ替える前のコード，つまりプログラマが見ているコードはあくまで Table 17.4-A. に示したものです。 このコードを実行したときに r2 == 2 かつ r1 == 1 になったとすると， A の初期値が 0 なのにも関わらず 勝手に A == 2 になった ，あるいは，B の初期値が 0 なのにも関わらず 勝手に B == 1 になった ように見えるでしょう。 データ競合があるとこのようなバグが発生し得ることが分かりました。

C++ でのリオーダ例

リオーダは最適化のために重要な技術です。例えば次のコード片を見てみます。

int f() {
  int r1 = A;
  if (B) {
    return r1;
  }
  return 1234;
}

A と B はグローバル変数です。このコード片では if 文の中でしか r1 を使っていませんので，A の読み込み処理を if 文の中に移動することで無駄なメモリ読み込みを減らせます。ですから，コンパイラは A の読み込みをリオーダし，内部的に次のようなコードに変換する可能性があります。筆者の Clang 10 に最適化オプション -O3 を指定したところ，実際にそうなりました。

int f() {
  if (B) {
    int r1 = A;
    return r1;
  }
  return 0;
}

一見，これは妥当な最適化に思えます。何しろ A の読み込みを移動したところで関数 f の実行には何の影響も無いでしょう。しかし，これがマルチスレッドのプログラムの一部だった場合に意図しないバグをもたらすことになるのです。

仮に A は何らかの値を表す変数，B はその値が生存していることを表すフラグとします。初期値は A == 42 かつ B == 1 とします。生存フラグが真の間，A の値は削除されておらず有効な値が格納されている，ということを意味します。A の値を無効な値に書き換える 前 に生存フラグを偽に設定することにします。

// A の削除処理
void g() {
  B = 0;
  A = 0;
}

関数 f，g をそれぞれスレッド 1，2 で動かすとします。A と B の読み書きに着目して処理を整理すると次の表の通りです。関数 f はリオーダが発生する前のコードに基づいた処理の順にしてあります。

スレッド 1（関数 f） スレッド 2（関数 g）
int r1 = A; B = 0;
if (B) A = 0;

スレッド 1 では B を読むより前に A を読んでいるため，r1 と（if 文の条件部で読み込んだ）B の値の組み合わせは次のいずれかになり，決して r1 == 0 かつ B == 1 にならないと期待します。

r1 B
42 1
42 0
0 0

r1 == 0 かつ B == 1 という組み合わせは A が生存しているはずなのに実際は無効値 という異常な状況を表していて，この状況が絶対に発生しないことを保証したいわけです。関数 g の実装を見ると，B が 1 の間は A = 0; も実行されていないはずだから，これは保証できているように見えます。

しかし，先ほど書いたようにコンパイラはステートメントや命令をリオーダすることがあります。Java や C/C++ のコンパイラは一般に，スレッド単体の実行に影響を与えない限り自由にリオーダする権利を持っていて，この場合も例外ではありません。int r1 = A; の処理が if 文内部にリオーダされた場合の命令の実行順を表すと次の通りです。

スレッド 1（関数 f） スレッド 2（関数 g）
1: if (B) 3: B = 0;
2: int r1 = A; 4: A = 0;

リオーダされた処理では異常な状況（r1 == 0 かつ B == 1）となるスレッドのスケジューリングが存在します。

スレッド 1              スレッド 2
1: `if (B)`
                        3: `B = 0;`
                        4: `A = 0;`
2: `int r1 = A;`

このように，コード上は問題なさそうに見えるのに，コンパイルされた機械語レベルでは問題がある処理になることがあります。このようなマルチスレッドの並行性に起因するバグは，スレッドスケジューリングに依存して確率的に顕在化するためとても見つけにくいです。

データ競合とリオーダ

この記事の主題はデータ競合です。それなのに，なぜリオーダを詳しく説明したのでしょうか？それは，データ競合があることとリオーダされ得ることに密接な関係があるからなのです。

ここで改めて[^1]におけるデータ競合の定義を見てみます。

同一のメモリ位置に対する 2 つのアクセスαとβは，αとβが異なるスレッド上で実行され，同期されておらず（すなわち並行），少なくとも片方が書き込みであれば外見上のデータ競合があると言う。

リオーダとデータ競合の関係において重要なのは「同期されておらず」という部分です。データ競合がある→共有変数のアクセスが同期されていない→リオーダ可能，ということになるからです。というより，ロックやアトミック変数など，コンパイラが用意している同期機構はリオーダを防ぐことを主目的にしていると言っても過言ではありません。同期機構を使いデータ競合を防ぐことと，コンパイラおよび CPU によるリオーダを防ぐことはほぼ同じ意味なのです。

上記のコードをアトミック変数を使って同期してみましょう。

std::atomic_int A{42}, B{1};

int f() {
    int r1 = A;
    if (B) {
        return r1;
    }
    return 0;
}

void g() {
    B = 0;
    A = 0;
}

std::atomic_int は C++ の標準ライブラリが提供する int 型のアトミック変数です。x86-64 においては，std::atomic_int のメモリ上の表現は普通の int と差が無く，同じビット幅，同じビット表現です。

では int と std::atomic_int で何が違うのかというと，コンパイラのリオーダや機械語の選択が変わってきます。 std::atomic_int は複数のスレッドから読み書きされる変数だとコンパイラが認識してくれるため，例えば読み書きの処理をリオーダしなくなったり，CPU レベルのリオーダを防止するために必要な配慮をしてくれたりします。

以降の議論にはそれほど重要な関連はありませんが，参考のために int と std::atomic_int の差を具体的に見てみます。まずは 2 つの変数 A と B を int 型とした場合の，関数 f，g のコンパイル結果を示します。使用したコンパイラは Clang 10 です。

_Z1fv:                                  # @_Z1fv
        mov     eax, dword ptr [rip + B]
        test    eax, eax
        je      .LBB0_2
        mov     eax, dword ptr [rip + A]
.LBB0_2:
        ret

_Z1gv:                                  # @_Z1gv
        mov     dword ptr [rip + B], 0
        mov     dword ptr [rip + A], 0
        ret

C++ の名前マングルの影響で読みにくいですが，関数 f が _Z1fv，関数 g が _Z1gv です。関数 f の中身を見てみると，変数 A，B の読み込みの順序が入れ替わっていることが分かります。コンパイラが命令をリオーダしたのです。

一方，A と B の型を std::atomic_int としたバージョンのコンパイル結果は次のようになりました。

_Z1fv:                                  # @_Z1fv
        mov     eax, dword ptr [rip + A]
        mov     ecx, dword ptr [rip + B]
        test    ecx, ecx
        cmove   eax, ecx
        ret

_Z1gv:                                  # @_Z1gv
        xor     eax, eax
        xchg    dword ptr [rip + B], eax
        xor     eax, eax
        xchg    dword ptr [rip + A], eax
        ret

関数 f での A，B の読み込み順が保存されているのと，関数 g での書き込み命令が mov から xchg になったことが分かりますね。C++ のアトミック変数はデフォルトの一貫性モデルとして逐次一貫性（Sequential Consistency）を採用しています。アトミック変数の読み書きを = で行うと逐次一貫性モデルが適用されます。逐次一貫性を達成するためにアトミック変数の読み書き順が保たれ，書き込みが xchg によって行われるようになります。

xchg 命令は指定したレジスタとメモリの内容を交換する命令ですが，重要なのは xchg が lock プレフィクスを暗黙的に含む命令であることです。メモリアクセスのある命令に lock プレフィクスを付けると，その命令が完了するまで，その命令がメモリアクセスを独占します。つまり，その命令がアトミックに実行されます。それなら lock mov でいいじゃないかと思うかもしれませんが，mov には lock プレフィクスを付けられないのです。

逐次一貫性が保たれているプログラムにはデータ競合がありません。逐次一貫性を考えることはデータ競合への理解を深めることに繋がりますので，次節で詳しく説明します。

逐次一貫性

逐次一貫性3とは，並行システムの安全特性の一種で，比較的強い安全性を達成するものです。Jepsen という並行・分散システムの安全性を向上する取り組みをしているサイトにおける逐次一貫性の記事 によれば，逐次一貫性とはすべての操作（operations）に何らかの全順序が付き，加えてその全順序が個々のプロセッサ（≒CPU コア）における処理の順序に矛盾しないということだそうです。

これをぱっと理解するのは難しいと思います。順を追って説明します。まずは「操作に何らかの全順序が付く」という部分に取り組みます。

大前提として，現代的な CPU ではいくつもの機械語命令が同時に処理されることを理解する必要があります。代表的な仕組みに命令パイプラインがあります。これは，命令の実行を細かいステージに分け，複数の命令を同時並行的に進めていく方式です。例えば命令の実行をフェッチ，デコード，エクゼキュート，メモリアクセスなどの段階に分けます。先頭の命令のフェッチが完了したら，その命令をデコードしつつ次の命令をフェッチする，といったように段階毎に命令の実行を行うことで，ステージの数だけ命令を同時に処理できます。

命令パイプラインの他には，メモリ読み書きの遅さをカバーする仕組みもあります。CPU が 1 つの命令を実行する速度に比べてメインメモリ（DRAM）のアクセスは非常に遅いため，単なる命令パイプラインだけではメモリアクセスが発生するたびに命令の実行が長時間ストップしてしまうのです。これをどう解決するかというと，CPU コア内部にメモリ読み書きが完了するのを待っている命令を一時的に置いておくバッファを用意する方法があります。

    mov  dword ptr [rip + x], 1    # write
    mov  eax, dword ptr [rip + y]  # read

そのようなバッファがあることで，上記のような機械語列があったときに CPU は read 操作（2 つ目の mov）を事実上コストを掛けずに実行できる可能性があります。変数 y の値がキャッシュに載っている場合，write 操作（1 つ目の mov）の完了より早く read 操作が完了するでしょう（下図）。

f:id:uchan_nos:20200619185553p:plain
readはwriteを追い越し得る

このように，互いにデータの依存関係が無い命令同士を入れ替えて効率よく実行することをアウトオブオーダー実行と呼びます。アウトオブオーダーに関連する技術にレジスタリネーミングなどもあります。筆者は残念ながら CPU の最適化に関する専門家ではなく，この辺りの話には詳しくないため，深入りは避けます。

少し込み入った話をしましたが，伝えたいのは CPU が命令の実行順を入れ替えたり，1 つの命令の完了を待つ間に他の命令を実行したりすることです。現代の CPU は機械語の順序を積極的に入れ替え，可能な限り大量の命令を同時に実行するようになっているのです。

さて，逐次一貫性の「操作に何らかの全順序が付く」の説明に戻ります。今までの説明から，CPU はいくつもの命令を同時並行に処理することが分かりました。これはすなわち，CPU が実行する命令（=操作）には基本的に順序を付けられないことを意味します。2 つの近くにある命令を比べたとき，どちらの命令が先に実行されたかは決められないのです。

ここで言う「実行」とは，その命令の処理を始めてから完了するまでのことです。「命令の処理を始めた瞬間」になら順序を付けることは可能でしょう。命令をフェッチした順番を記録すれば，それがそのまま順序になるでしょうから。ただ，重要なのは処理の開始から完了までの幅を持った「実行」に関する順序を考えることです。

先ほどの例で変数 x，y がどちらもアトミック変数であり，逐次一貫性のもとで読み書きするように C++ のコードが書かれているとします。その場合，C++ コンパイラは 2 つのメモリ読み書き操作に順序を付けねばなりません。そうでなければ逐次一貫性が担保できないからです。そこでコンパイラは次のような機械語を出力します。

    mov  eax, 1
    xchg dword ptr [rip + x], eax  # write
    mov  eax, dword ptr [rip + y]  # read

xchg 命令を使うことで x の write 操作が実行中に y の read 操作が行われることがなくなります。つまり xchg と mov の実行に順序が付くことになります（下図）。

f:id:uchan_nos:20200619185648p:plain
xchgが完了するまでmovが待たされる

逐次一貫性を達成するためには，他のプロセッサから観測できる操作，つまり共有変数の読み書きについて順序を決められる必要があります。これが「操作に何らかの全順序が付く」の意味です。共有変数のすべての読み書き操作を，1 本の数直線上に互いに重ならせずに乗せられる，と言い換えることもできますね。

さて，逐次一貫性の次の条件「その全順序が個々のプロセッサ（≒CPU コア）における処理の順序に矛盾しない」について考えます。これは簡単です。あるプロセッサによる共有変数の読み書き命令の実行順序が，他のプロセッサが観察した順序と矛盾しない，ということです。共有変数の読み書きによりメモリの状態が変わっていきます。共有変数の読み書きを行ったプロセッサが思っている読み書きの順序と，他のプロセッサがメモリ状態を観測したときの変化の順序が整合していれば OK です。

acquire/release

逐次一貫性はプログラム中のすべての操作（共有変数の読み書きに関するもの）に順序が付けられるというモデルでした。C++ のアトミック変数の読み書きにはデフォルトの逐次一貫性の代わりに個別に順序制約を指定できます。この節では acquire/release という順序制約を紹介します。

#include <atomic>
int data{0};
std::atomic_bool ready{false};

int UseData() {
  if (ready.load(std::memory_order::acquire)) {
    return data;
  }
  return 0;
}
void SetData() {
  data = 42;
  ready.store(true, std::memory_order::release);
}

acquire/release を説明するサンプルとして上記のコードを使います。SetData と UseData は別スレッドで動作します。便宜的に SetData スレッドと UseData スレッドと呼ぶことにします。この 2 つのスレッド間で共有される変数は data と ready の 2 つがあります。data がアトミック変数になっていないのは意図的です。

SetData スレッド上の release 操作によって書いた値（ready.store(true, release)）が UseData スレッド上の acquire 操作で読み込めたとします。このとき，SetData スレッド上の release 操作より前にある副作用がすべて，UseData スレッド側で見えることが保証されます。release 操作より前にある副作用とは具体的には data = 42; ですから，ready.load(acquire) で true が読めたら data = 42; の結果を UseData スレッド側で利用できるということです。感覚的な理解では，そこまでの副作用をすべて release（放流）し，それを acquire（取得）することで副作用をすべて見ることができる，という感じです。

変数 data はアトミック変数ではありません。データ競合の定義に照らし合わせると，2 つのスレッドにおける data の読み書きには外見上のデータ競合があると言えるのではないでしょうか。外見上のデータ競合の定義を改めて掲載します。

同一のメモリ位置に対する 2 つのアクセスαとβは，αとβが異なるスレッド上で実行され，同期されておらず（すなわち並行），少なくとも片方が書き込みであれば外見上のデータ競合があると言う。

α= data = 42;，β= return data; とすると

  • αとβが異なるスレッド上で実行され
  • 少なくとも片方が書き込みである

は満たされます。そして，data を読み書きする前後でロックを取っているわけではありませんから，同期していないような気もします。仮に if 文で ready の値をチェックすることなく return data; を実行したとしたら，データ競合があることになります。

しかし，実際には data の読み書きはデータ競合を引き起こさないのです。これは ready というアトミック変数を介した release→acquire 操作によって，2 つのスレッドが同期されるからです。

上記のコードをコンパイルした結果を示します。C++ の名前マングルにより UseData は _Z7UseDatav に，SetData は _Z7SetDatav に変換されています。

_Z7UseDatav:                            # @_Z7UseDatav
        mov     cl, byte ptr [rip + ready]   ; ready.load()
        xor     eax, eax
        test    cl, 1
        je      .LBB0_2
        mov     eax, dword ptr [rip + data]  ; data の read 操作
.LBB0_2:
        ret

_Z7SetDatav:                            # @_Z7SetDatav
        mov     dword ptr [rip + data], 42   ; data の write 操作
        mov     byte ptr [rip + ready], 1    ; ready.store()
        ret

コンパイル結果を見ると ready.load(acquire) より後に data の read 操作が来ていること，ready.store(true, release) より前に data の write 操作が来ていることが分かります。これは偶然ではなく，acquire/release がもたらす順序制約による必然の結果です。C++ コンパイラは，C++ のコード上で release 操作より前にある副作用はコンパイル後でも release 操作より前に配置しなければなりません。同様に C++ のコード上で acquire 操作より後ろにある副作用はコンパイル後でも acquire 操作より後ろに配置されます。

CPU のリオーダ

CPU が実行する命令の中でも，その順序が重要なのはメモリ読み書き命令です。なぜなら，メモリ読み書きはコア間で影響しあうからです。レジスタ読み書きだけで処理が完了するような命令（例えば xor rcx, rcx）はコア内部で閉じてしまい，他のコアに影響を及ぼさず，また他のコアから影響されることがありません。したがって，処理の順序がどうであろうと，逐次一貫性には影響を与えません。

CPU によるメモリ読み書き命令のリオーダの仕方は CPU の仕様で決まっています。x86-64 は TSO（Total Store Ordering）を採用しており，read 同士，write 同士，read に続く write は順序が入れ替わりません。ただし，異なるメモリ領域への read は write を追い越して実行されることがあります。この辺りは x86/x64におけるメモリオーダーの話 が詳しいです。

上記のコード例で注目したいのは，逐次一貫性を用いた write では xchg が使われ，acquire/release を使った write では mov が使われているということです。SetData にあるこの 2 つの mov の実行順序が入れ替わってしまっては acquire/release の仕様を満たさなくなってしまいます。CPU はこの 2 つの mov を入れ替えないのでしょうか？

はい，入れ替わりません。x86-64 は TSO ですから，write 同士は入れ替わらないのです。だから SetData の 2 つの mov 命令はその通りの順序で実行されます。そのため release の仕様（release 操作より前にある副作用はコンパイル後でも release 操作より前に配置しなければならない）はちゃんと満たされます。

happens-before 関係

happens-before 関係は 2 つの操作のどちらが 先に起きたか を表します。英語の "A happens before B" を日本語にすると「A は B より前に起きる」となります。先ほど説明した acquire/release は，1 つの共有変数に関する読み書き操作に happens-before 関係を付けるためのものです。

SetData 側の release 操作によって書いた値が UseData 側の acquire 操作で読み込めたとき，release 操作と acquire 操作の間に happens-before 関係が付きます。ready.store(true, release) happens before ready.load(acquire) ということですね。

happens-before 関係は，先に起きた操作の影響が後の操作から見える，可視である，ということを保証するものです。注意したいのは，A happens before B は「A は B の前に必ず起きる」と言っているわけではないということです。仮に A が B の先に起きたとき，B から A の影響（メモリ書き込みの結果など）が見えることを保証するのが happens-before 関係なのです。UseData と SetData は別スレッドで動きますが，スレッドの動作順（スレッドスケジューリング）によって ready.load(acquire) と ready.store(true, release) のどちらが先に実行されるかが変わります。

f:id:uchan_nos:20200619185721p:plain
happens-before関係が付くスレッドスケジューリングの例

上図は ready.store(true, release) が ready.load(acquire) の先に起きたときに両者が happens-before 関係で結ばれることを示します。A happens-before B を A →HB B と表現しています。

happens-before 関係が付与される操作の組は次のようなものがあります。

  • 同一スレッド上の命令列
  • アトミック変数の acquire/release による読み書き
  • ロックの取得と解放
  • スレッドの生成と開始
  • スレッドの終了と join

プログラムに潜む外見上のデータ競合を発見する道具として happens-before 関係が良く使われます。典型的には，複数のスレッド間のメモリ読み書きが happens-before 関係によって順序付けられていないときに外見上のデータ競合がある，と判定します。どの操作の組を happens-before 関係として採用するかは手法により異なります。Java 向けのデータ競合検出ツール FastTrack4 では，happens-before 関係を規定する操作として同一スレッド上の命令列，ロックの取得と解放，スレッドの生成と開始，スレッドの終了と join を用います。アトミック変数の読み書きは無視します。

久々に関数 f，g の例を引っ張り出し，happens-before 関係がどう付くかを考えてみます。関数 f，g のサンプルコードにおいて，A，B の読み書きの順序制約を acquire/release に変更したものを示します。

std::atomic_int A{42}, B{1};

int f() {
  int r1 = A.load(std::memory_order::acquire);
  if (B.load(std::memory_order::acquire)) {
    return r1;
  }
  return 1234;
}

void g() {
  B.store(0, std::memory_order::release);
  A.store(0, std::memory_order::release);
}

これをコンパイルすると次の結果になりました。

_Z1fv:                                  # @_Z1fv
        mov     eax, dword ptr [rip + A]
        mov     ecx, dword ptr [rip + B]
        test    ecx, ecx
        cmove   eax, ecx
        ret

_Z1gv:                                  # @_Z1gv
        mov     dword ptr [rip + B], 0
        mov     dword ptr [rip + A], 0
        ret

acquire/release なのでアトミック変数への write に xchg ではなく mov が用いられています。そして，読み書きの順が保たれていることも分かります。このプログラムを実行したときのあり得るスレッド実行パターンをすべて列挙し，r1 の値と if 文での B の値がどうなるかを見てみます。

A と B の読み書きに happens-before 関係が付く場合

パターン 1：r1 == 0 かつ B == 0

f()                 g()
                    B.store(0, release)
                    A.store(0, release)
A.load(acquire)
B.load(acquire)

if 文の時点で B == 0 となるため，A の値は削除されたものとして処理します。実際，A からは無効な値が読めているため，この判定は正しいです。

B の読み書きだけに happens-before 関係が付く場合

パターン 2：r1 == 42 かつ B == 0

f()                 g()
                    B.store(0, release)
A.load(acquire)
                    A.store(0, release)
B.load(acquire)

パターン 3：r1 == 42 かつ B == 0

f()                 g()
                    B.store(0, release)
A.load(acquire)
B.load(acquire)
                    A.store(0, release)

パターン 4：r1 == 42 かつ B == 0

f()                 g()
A.load(acquire)
                    B.store(0, release)
B.load(acquire)
                    A.store(0, release)

パターン 5：r1 == 42 かつ B == 0

f()                 g()
A.load(acquire)
                    B.store(0, release)
                    A.store(0, release)
B.load(acquire)

いずれのパターンでも if 文の時点で B == 0 となるため，A の値は削除されたものとして処理します。しかし，実際は A からは有効な値が読めています。安全側に倒した正しい判定ですが，もったいない判定ではありますね。

どちらにも happens-before 関係が付かない場合

パターン 6：r1 == 42 かつ B == 1

f()                 g()
A.load(acquire)
B.load(acquire)
                    B.store(0, release)
                    A.store(0, release)

if 文の時点で B == 1 となるため，A からは有効な値が読めたものとして処理します。実際，有効な値が読めていますので，この判定は正しいです。

パターン 1 から 6 のいずれでも安全な判定となっています。適切にアトミック変数を使うことでデータ競合を防ぎ，命令のリオーダを防ぐことでバグのないプログラムが作れました。

  1. Pozniansky, E., & Schuster, A. (2003). Efficient on-the-fly data race detection in multithreaded C++ programs. Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003, 179–190. https://doi.org/10.1109/IPDPS.2003.1213513↩

  2. Netzer, R. H. B., & Miller, B. P. (1992). What Are Race Conditions?: Some Issues and Formalizations. ACM Letters on Programming Languages and Systems (LOPLAS), 1(1), 74–88. https://doi.org/10.1145/130616.130623↩

  3. Lamport, L. (1979). How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, C–28(9), 690–691. https://doi.org/10.1109/TC.1979.1675439↩

  4. Flanagan, C., & Freund, S. N. (2010). FastTrack: Efficient and precise dynamic race detection. Communications of the ACM, 53(11), 93–101. https://doi.org/10.1145/1839676.1839699↩