C++11のmemory_orderの使い分け (1)
C++11で高速な同期手法としてアトミック変数やメモリフェンス（普通はメモリバリアと呼ぶ）が追加されました。
これらの命令では memory_order を指定できるのですが、違いが分かりづらいのでまとめてみました。
なお、正確な名前は
memory_order_relaxed、
memory_order_acquire、
memory_order_release、
memory_order_consume、
memory_order_acq_rel、
memory_order_seq_cst
ですが、長いのでこれ以降 memory_order_ の部分は省略します。
アトミック変数で使われた場合
| memory_order | relaxed | acquire | release | consume | acq_rel | seq_cst |
|---|---|---|---|---|---|---|
| 可視性 | 保証 | |||||
| アトミック性 | 保証 | |||||
| 一貫性 | 保証なし | 因果一貫性の保証 | 順序一貫性の保証 | |||
アトミック変数は memory_order に関係なく可視性とアトミック性が保証されます。
つまり、
アトミック変数への最新の書き込みはいずれ他のスレッドからも読み取れることが保証され、
アトミック変数の操作中に他のスレッドから中途半端な値が読み取られないことが保証されます。
memory_order で変わるのは一貫性です。これは対象のアトミック変数だけでなく、他の変数の可視性やアトミック性にも関わってきます。
メモリモデルの定義では、
acquire, release の同期を用いるメモリモデルをリリース一貫性 (Release Consistency)、
seq_cst の同期を用いるメモリモデルを弱一貫性 (Weak Consistency)、
と呼ぶことになっているのですが、この呼び方では何が保証されるのか分からないので、メモリバリアを正しく使った時に「どのメモリモデルと同等になるのか」という視点で、「因果一貫性」と「順序一貫性」という名前を借用しています。
さて、memory_order の違いを因果一貫性と順序一貫性の違いに置き換えたわけですが、この2つの概念はやや難解なので順を追って詳しく説明します。
一貫性について
通常は他のスレッドのメモリ操作の順序を知る方法はありません。しかし、偶然メモリ操作の順序を知ってしまうことはあります。
// 初期値 int x = 0, y = 0; int a, b; // スレッド1 x = 1; y = 1; // スレッド2 a = y; b = x;
スレッド1とスレッド2を同時に実行したとき、以下の結果になることがあります。
a == 1; b == 0;
これは、
a = y が実行された時には y = 1 が実行されていたのに、
b = x が実行された時には x = 1 が実行されていなかったことを表しています。
ということは、スレッド2からは y = 1 を先、x = 1 を後に実行したように見えたわけです。
ただし、実際には x = 1 が先、y = 1 が後に実行された可能性はあります。
スレッド2の b = x が先、a = y が後に実行された場合です。
そのため、このようなやり方では実際の順序を知る方法はありません。
スレッド間通信での順序の問題を考える時には、「どのスレッドからどの順序で見えたか」という相対的な順序を考える必要があります。
そして、
どのスレッドからも同じ順序で見えるなら一貫している、
スレッド毎に違う順序で見えるなら一貫していない、
という考え方をします。
一貫性が無い場合
一貫性が無い場合、あるスレッドのメモリ操作が他のスレッドから同じ順序で見える保証がありません。また、一貫した順序で見える保証もありません。つまり、スレッド毎に違った順序で見える可能性があります。
// 初期値 int x = 0, y = 0; int a, b, c, d; // スレッド1 x = 1; y = 1; // スレッド2 a = y; b = x; // スレッド3 c = x; d = y;
一貫性が無い場合、以下の結果になることがありえます。
a == 1; b == 0; c == 1; d == 0;
上記の結果は、
スレッド2からは y = 1 → x = 1 の順で実行されたように見え、
スレッド3からは x = 1 → y = 1 の順で実行されたように見えたことを表しています。
一貫性が無いとこのような矛盾が起きる可能性があります。
PRAM一貫性 (PRAM Consistency)
PRAM一貫性はFIFO一貫性 (FIFO Consistency) とも呼ばれます。PRAM は pipelined random access memory、FIFO は first in, first out の略ですが、あまり気にしなくていいです。
PRAM一貫性はあるスレッドのメモリ操作の順序が他のスレッドからも一貫して同じ順序に見えることを保証します。これは、因果一貫性と順序一貫性よりも弱い一貫性です。因果一貫性と順序一貫性でもこれは保証されています。
一貫性が無い場合の説明に出てきたコードを簡略化して説明します。
// 初期値 int x = 0, y = 0; int a, b; // スレッド1 x = 1; y = 1; // スレッド2 a = y; b = x;
PRAM一貫性が保証される場合、上記のコードでは以下の結果は絶対に起こりません。
a == 1; b == 0;
スレッド1の x = 1 が先、y = 1 が後という順序が保証されるので、
a == y == 1 の時点で b == x == 1 が確定します。
ただし、複数のスレッドの操作順序には一貫性がありません。
// 初期値
int x = 0, y = 0;
int a, b;
// スレッド1
x = 1;
// スレッド2
if (x == 1) {
y = 1;
}
// スレッド3
a = y;
b = x;
PRAM一貫性だけでは上記のコードが以下の結果になることがあります。
a == 1; b == 0;
a == y == 1 になったということはスレッド2の y = 1 が実行されたはずなので、それより前にスレッド1の x = 1 も実行されたはずです。スレッド2は x = 1 → y = 1の順で実行されたことを知っていますが、x = 1 と y = 1 は別のスレッドで実行されているので、スレッド3からはその順序で見えることが保証されません。
因果一貫性 (Causal Consistency)
因果一貫性は、PRAM一貫性に加えて複数スレッドの操作でも因果があれば一貫した順序で見えることを保証します。
先ほどのコードを見ていきます。
// 初期値
int x = 0, y = 0;
int a, b;
// スレッド1
x = 1;
// スレッド2
if (x == 1) {
y = 1;
}
// スレッド3
a = y;
b = x;
因果一貫性では上記のコードが以下の結果にならないことを保証します。
a == 1; b == 0;
スレッド2は x == 1 が見えた後に y = 1 を実行するので x = 1 と y = 1 に因果関係が発生しています。そのため、スレッド3から y == 1 が見えたとき x == 1 も保証されます。
しかし、似たようなコードでも以下のコードでは矛盾が起きます。
// 初期値
int x = 0, y = 0;
int a = 0, b = 0;
// スレッド1
x = 1;
if (y == 1) {
a = 1;
}
// スレッド2
y = 1;
if (x == 1) {
b = 1;
}
これは以下の結果になることがあります。
a == 0; b == 0;
a == 1、b == 0 ならば、スレッド2が先、スレッド1が後に実行されています。
a == 0、b == 1 ならば、スレッド1が先、スレッド2が後に実行されています。
a == 1、b == 1 ならば、スレッド1とスレッド2が同時に実行されています。
しかし、a == 0、b == 0 は順序を説明できません。
スレッド1からは x = 1 の後に y == 1 が見えなかったので x = 1 → y = 1 の順で実行されたように見えています。
スレッド2からは y = 1 の後に x == 1 が見えなかったので y = 1 → x = 1 順で実行されたように見えています。
これは、x = 1 と y = 1 の間に因果関係がないために起こりました。
因果一貫性を理解するうえで重要なのは因果関係が発生する条件ですが、先にスレッド間通信を説明します。
まずスレッド間通信はメモリを通して行います。あるスレッドがメモリに値を書き込み、別のスレッドがメモリからその値を読み取ることでスレッド間通信が行われたことになります。スレッド間通信には「書き込み側→読み取り側」という向きがあり、「書き込み側が先、読み取り側が後」という順序があります。この順序が因果関係になります。
スレッドAが書き込んだ値をスレッドBが読み取ったとき、スレッドAとスレッドBの間で因果関係が発生しています。スレッドAが書き込んだ値をスレッドBが読み取り、その後スレッドBが書き込んだ値をスレッドCが読み取ったとき、スレッドA→スレッドB→スレッドCの因果関係が発生します。このときスレッドCはスレッドAの書き込みを読み取ることができます。
また、因果一貫性はPRAM一貫性も保証されるので、スレッドCはスレッドBが読み取ったスレッドAの値だけでなく、それより前にスレッドAが書き込んだ値も読み取ることができます。
順序一貫性 (Sequential Consistency)
順序一貫性は逐次一貫性と呼ばれることが多いです。ですが、何が一貫しているのか分かりづらいので順序一貫性と呼ぶことにします。
順序一貫性は全ての変数操作の順序がどのスレッドからも一貫して同じ順序に見える性質です。これは実行時の実際の順序が反映されます。ただし、書き込み命令に到達した順序とは限りません。実際に書き込まれて読み取れるようになった順序で決まります。
順序一貫性は因果一貫性も保証しています。
因果一貫性の説明に出てきたコードで説明します。
// 初期値
int x = 0, y = 0;
int a = 0, b = 0;
// スレッド1
x = 1;
if (y == 1) {
a = 1;
}
// スレッド2
y = 1;
if (x == 1) {
b = 1;
}
順序一貫性がある場合、上記のコードは以下の結果になることがありません。
a == 0; b == 0;
x = 1 と y = 1 の間には因果が発生しませんが、どのスレッドからも実際に書き込まれた順序で見えることが保証されます。そのため、順序の見え方に矛盾の起きる a == 0 かつ b == 0 という結果は起きません。ただし、同時に書き込まれる可能性はあるので a == 1 かつ b == 1 は起こります。
順序一貫性が保証される状況ではどんな書き込みも全てのスレッドで同じ順序で見えることが保証されるので矛盾が起こりません。無矛盾であることが保証されるので、バグの可能性を無くせるという意味では最強の保証です。
次回に続く
ここまでの説明でそれぞれのメモリバリアがどこまで保証できるかは説明できたと思います。次回、実際の使い方を紹介しようと思います。
