C++11のmemory_orderの使い分け (3)

2014/10/29 20:40
誤解を招きそうな部分があったので修正しました。修正場所は脚注から辿れます。

前回はアトミック変数に memory_order を指定した場合について解説しました。
今回はフェンスで指定した場合について解説します。

その前に前回のアトミック変数にメモリバリアを用いたときの説明で relaxed バリアの説明を忘れていたのでここで説明しておきます。

relaxedバリア

relaxed バリアは順序に関して何も保証しません。アトミック変数の中途半端な値が読み取られない保証と、いつか読み取れるようになる保証だけで十分な時に使います。

ところで他のサイトで shared_ptr などのポインタの参照カウントの増減に relaxed が使えるという記述がありましたが、それは間違いです。それだとデータを読み取る前に参照カウントを減らす処理が他のスレッドに見える可能性があり、データを読み取る前に他のスレッドに delete される可能性があります。実際 shared_ptr の参照カウントの増減には release / acquire バリアが使われています。

ここからがフェンスの解説です。

フェンスはアトミック変数と組み合わせて使う

アトミック変数の、中途半端な値が読み取られない保証と、いつか読み取れるようになる保証は、スレッド間通信の最初にどうしても必要です。そして、フェンスはアトミック変数の読み書きによってスレッド間通信が成功した時に効果が保証されます。なので、フェンスとアトミック変数は組み合わせて使います。

フェンスはアトミック変数の relaxed を指定した読み書きと組み合わせて使うと考えても構いません。

relaxedフェンス

relaxed をフェンスに指定しても何も起きません。

もしかしたら、あえて relaxed をフェンスで使うことで、メモリバリアが不要なことを明示するような使い方があるのかもしれません。

consumeフェンス

consume をフェンスに指定すると acquire と同じ効果になります。なので、普通は acquire を使います。

consume の本来の効果はアトミック変数で使った場合にしか発生しません。

release/acquireフェンス

release フェンスと aquire フェンスはセットで使います。

release フェンス後のアトミック変数への書き込みが別のスレッドで acquire フェンス前に読み取れたとき、release フェンス前の書き込みが aquire フェンス後に読み取れることが保証されます。このとき、aquire フェンス後の書き込みは release フェンス前に読み取れていないことも保証されます。（これはアトミック変数で release / acquire バリアを使った時にも保証されるのですが説明するのを忘れていました。）

release フェンス後のアトミック変数への書き込みが別のスレッドで acquire フェンス前に読み取れた時、release フェンス前の読み書きが先、acquire フェンス後の読み書きが後になることが保証されていると考えて構いません。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
std::atomic_thread_fence(std::memory_order_release);
x.store(10, std::memory_order_relaxed);

// スレッド 2
int r = x.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);
if (r == 10) {
	data;	// data == 100 が保証される
}

スレッド 1 の release フェンス後の x への書き込み (10) がスレッド 2 の aquire フェンス前に読み取れた時、スレッド 1 の release フェンス前の data へ書き込み (100) がスレッド 2 の aquire フェンス後に読み取れます。

また、release / acquire フェンスは read-modify-write 命令の読み書きでも効果があります。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
std::atomic_thread_fence(std::memory_order_release);
x.fetch_add(1, std::memory_order_relaxed);

// スレッド 2
int r = x.fetch_add(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);
if (r == 1) {
	data;	// data == 100 が保証される
}

スレッド 1 の x に 1 を足した値 (1) がスレッド 2 で読み取れた時、data も読み取れることが保証されます。

acq_relフェンス

acq_rel フェンスは acquire フェンスと release フェンスの両方の効果があります。
acquire フェンスや release フェンスと組み合わせて使うことも可能です。

release / acq_rel フェンス後のアトミック変数への書き込みが別のスレッドの acquire / acq_rel フェンス前に読み取れたとき、release / acq_rel フェンス前の書き込みが acquire / acq_rel フェンス後に読み取れることが保証されます。また、このとき aquire / acq_rel フェンス後の書き込みは release / acq_rel フェンス前に読み取れていないことも保証されます。

これは、release / acq_rel フェンス後のアトミック変数への書き込みが別のスレッドの acquire / acq_rel フェンス前に読み取れたとき、release / acq_rel フェンス前の読み書きが先、acquire / acq_rel フェンス後の読み書きが後になることが保証されていると考えて構いません。

// 初期値
std::atomic_int x(0), y(0);

// プロトタイプ宣言
void fire();

// スレッド 1
int r = x.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acq_rel);
y.store(1, std::memory_order_relaxed);
if (r == 1) {
	fire();
}

// スレッド 2
int r = y.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acq_rel);
x.store(1, std::memory_order_relaxed);
if (r == 1) {
	fire();
}

上記のコードは fire() が呼ばれない可能性と1回だけ呼ばれる可能性はありますが、2回呼ばれる可能性はありません。

スレッド 1 の x の読み取りでスレッド 2 の x への書き込み (1) が読み取れたとき、それより前にスレッド 2 の y の読み取りは完了しているので、スレッド 2 の y の読み取りは 0 になります。

同様に、スレッド 2 の y の読み取りでスレッド 1 の y への書き込み (1) が読み取れたとき、それより前にスレッド 1 の x の読み取りは完了しているので、スレッド 1 の x の読み取りは 0 になります。

スレッド 1 の x の読み取りとスレッド 2 の y の読み取りで、両方とも 0 になる可能性はありますが、両方とも 1 になる可能性はありません。よって fire() が 2 回呼ばれることはありません。

しかし、次の例では fire() が呼ばれない時、1回だけ呼ばれる時、2回呼ばれる時の全てがあり得ます。

// 初期値
std::atomic_int x(0), y(0);

// プロトタイプ宣言
void fire();

// スレッド 1
x.store(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acq_rel);
int r = y.load(std::memory_order_relaxed);
if (r == 1) {
	fire();
}

// スレッド 2
y.store(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acq_rel);
int r = x.load(std::memory_order_relaxed);
if (r == 1) {
	fire();
}

フェンス後の書き込みもフェンス前の読み取りもありません。なので、フェンスが効果を発揮する条件を満たしていません。これはフェンスが無いのと同じです。

アトミック変数のバリアをフェンスで置き換える

アトミック変数の release / acquire / acq_rel バリアを指定した命令は、アトミック変数の relaxed を指定した命令と release / acquire / acq_rel フェンスで置き換えることができます。

分かりやすいように release を指定した書き込みを release store、aquire を指定した読み取りを acquire load 、acq_rel を指定した read-modify-write 命令を acq_rel read-modify-write と呼ぶことにします。relaxed を指定した場合も relaxed ○○ という呼び方をすることにします。
（最初からこの呼び方をしていた方が分かりやすかったかもしれませんね。）

release フェンスへの置き換え

// release store
x.store(1, std::memory_order_release);

↑↓

// release fence + relaxed store
std::atomic_thread_fence(std::memory_order_release);
x.store(1, std::memory_order_relaxed);

acquire フェンスへの置き換え

// acquire load
x.load(std::memory_order_acquire);

↑↓

// relaxed load + acquire fence
x.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);

release フェンスと acquire フェンスへの置き換え

// acq_rel read-modify-write
x.fetch_add(1, std::memory_order_acq_rel);

↑↓

// release fence + read-modify-write + acquire fence
std::atomic_thread_fence(std::memory_order_release);
x.fetch_add(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);

acq_rel フェンスへの置き換え

// acquire load + release store
x.load(std::memory_order_acquire);
y.store(1, std::memory_order_release);

↑↓

// relaxed load + acq_rel fence + relaxed store
x.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acq_rel);
y.store(1, std::memory_order_relaxed);

read-modify-wirte は内部で load と store の両方を行っていると考えて構いません。

このような置き換えは自由に組み合わせて使えます。置き換えは、release 側と acquire 側の両方を同時に行う必要はありません。片方だけ置き換えることも可能です。store や load でメモリバリアを指定するパターンと、relaxed を指定したstore や load をメモリバリアを指定したフェンスで補うパターンは、自由に組み合わせて使えます。（ただし、フェンスを使ったパターンは、store や load で指定するパターンにいつでも置き換えられるわけではありません。特に次回説明するフェンスを減らしたパターンからは置き換えられません。置き換えができるのは上記のようにメモリバリアの release 効果が store に、acquire 効果が load に、それぞれ 1 対 1 で対応している時だけです。）*1

例えば、release store と acquire fence + relaxed load でも効果があります。

// 初期値
int data;
std::atomic_int x(0);

// スレッド 1
data = 100;
x.store(10, std::memory_order_release);

// スレッド 2
int r = x.load(std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_acquire);
if (r == 10) {
	data;	// data == 100 が保証される
}

フェンスをまとめる

release / acquire / acq_rel フェンスが連続する場合、フェンスの順序に関係なく 1 つの acq_rel フェンスにまとめることが出来ます。

std::atomic_thread_fence(std::memory_order_acquire);
std::atomic_thread_fence(std::memory_order_release);

↓

std::atomic_thread_fence(std::memory_order_acq_rel);

このようなフェンスをまとめる作業はコンパイラがやってくれるのでプログラマがやる必要は無いですが、知っておいた方が理解しやすいです。

seq_cst フェンス

seq_cst フェンスは acq_rel の効果に加えて、フェンス自体に順序一貫性があります。つまり、seq_cst フェンスが複数のスレッドで使われたとき、フェンス自体の実行順序がどのスレッドからも同じに見えます。

そして、先に実行されたフェンス前の書き込みは、後に実行されたフェンス後に読み取れることが保証されます。また、後に実行されたフェンス後の書き込みは、先に実行されたフェンス前に読み取られていないことが保証されます。

この保証は アトミック変数で seq_cst バリアを指定した時の store や load と保証が少し違います。

アトミック変数で保証されていたのは、seq_cst store で書き込まれた値を seq_cst load で読み取れた時に seq_cst store 前の読み書きが先、seq_cst load 後の読み書きが後になるという保証と、seq_cst store や seq_cst load や seq_cst read-modify-wirte が実行された順序がどのスレッドからも同じに見えるという保証でした。seq_cst store で書き込まれた値を seq_cst load でまだ読み取れなかった時、seq_cst load 前の読み書きが先、seq_cst store 後の読み書きが後という保証はありません。

イメージとしては、
seq_cst store = release store + store に順序一貫性
seq_cst load = acquire load + load に順序一貫性
seq_cst read-modify-write = acq_rel read-modify-write + read-modify-write に順序一貫性
seq_cst fence = acq_rel fence + fence に順序一貫性
となります。

順序一貫性があるもの同士を組み合わせた場合、組み合わせたもの全てで順序一貫性が保たれます。しかし、先に実行された方に release の効果、後に実行された方に acquire の効果が無いと順序一貫性以外の保証が無いことに注意してください。

このような違いがあるため、seq_cst な store や load を、relaxed な store や load + seq_cst fence に単純に置き換えることはできません。

// 初期値
std::atomic_int x(0), y(0);

// プロトタイプ宣言
void fire();

// スレッド 1
x.store(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
int r = y.load(std::memory_order_relaxed);
if (r == 1) {
	fire();
}

// スレッド 2
y.store(1, std::memory_order_relaxed);
std::atomic_thread_fence(std::memory_order_seq_cst);
int r = x.load(std::memory_order_relaxed);
if (r == 1) {
	fire();
}

上記のコードではスレッド 1 とスレッド 2 で seq_cst フェンスが使われています。
seq_cst フェンスの順序一貫性により、それぞれのフェンスに順序付けがなされ、どちらのフェンスが先に実行され、どちらのフェンスが後に実行されたのかが、どのスレッドから見ても同じになることが保証されます。

スレッド1 のフェンスが先、スレッド 2 のフェンスが後に実行された場合、スレッド 1 の フェンス前の x への書きこみ (1) がスレッド 2 のフェンス後の x の読み取りで読み取れることが保証されます。このとき、スレッド 1 の y の読み取りが 0 と 1 のどちらになるのかは分かりません。

スレッド2 のフェンスが先、スレッド 1 のフェンスが後に実行された場合、スレッド 2 の フェンス前の y への書きこみ (1) がスレッド 1 のフェンス後の y の読み取りで読み取れることが保証されます。このとき、スレッド 2 の x の読み取りが 0 と 1 のどちらになるのかは分かりません。

どちらの場合でも、x と y の少なくとも片方は 1 が読み取れます。x と y の両方で 0 を読み取ることはありません。つまり、最低でも 1 回は fire() が呼ばれます。

ところで、seq_cst fence の挙動は acq_rel read-modify-write に似ています。この場合は置き換えることが可能です。

// 初期値
std::atomic_int count(0);
std::atomic_int x(0), y(0);

// プロトタイプ宣言
void fire();

// スレッド 1
x.store(10, std::memory_order_relaxed);
count.fetch_add(1, std::memory_order_acq_rel);
int r = y.load(std::memory_order_relaxed);
if (r == 10) {
	fire();
}

// スレッド 2
y.store(10, std::memory_order_relaxed);
count.fetch_add(1, std::memory_order_acq_rel);
int r = x.load(std::memory_order_relaxed);
if (r == 10) {
	fire();
}

スレッド 1 が先に count に 1 を足した場合、スレッド 1 が足した値 (1) をスレッド 2 で読み取れるので、スレッド 1 のそれより前に書き込まれた x の値 (10) が スレッド 2 で読み取れます。
スレッド 2 が先に count に 1 を足した場合、スレッド 2 が足した値 (1) をスレッド 1 で読み取れるので、スレッド 2 のそれより前に書き込まれた y の値 (10) が スレッド 1 で読み取れます。
その結果、最低でも 1 回は fire() が呼ばれます。

read-modify-write は seq_cst フェンスよりも負荷が大きいので置き換えるメリットは全くありませんが、この考え方は重要です。

同一変数に対する read-modify-write は順序一貫性があります。seq_cst の複数の変数に対する順序一貫性と比べると弱い保証ですが、使い方によっては同じことが出来る場合があります。

次回に続く

これまでの解説で、アトミック変数とフェンスでの memory_order の基本的な使い方を全て解説しました。

次回はメモリバリアを減らして高速化する手法について解説します。

C++11のmemory_orderの使い分け (4)

*1:2014/10/29 20:40 修正