C++ の release sequence の意味と役割
C++ の release sequence とはアトミック変数の読み書きに関するルールです。release sequence は release store を先頭とし，それに続く read-modify-write の列です。先頭の store，または後続の read-modify-write によって書き込まれた値を acquire load した際に store と load 間に happens-before 関係を付与するためのルールが release sequence です。この記事では release sequence が何を表すのかと，どんな時に役立つのかを解説します。
想定読者
- 最小限のオーバーヘッドで異なるスレッド間の操作に happens-before 関係を付けたい人
- C++ のメモリモデルを深く理解するために release sequence を理解しようとしている人
概要
release sequence は 1 つの store を先頭とし，それに続く read-modify-write の列です。 store から load までの間に read-modify-write が割り込んでも，ちゃんと store と load の間に happens-before 関係を付与するためのルールです。
このルールが活躍するのは，例えばデータ構造を初期化してから初期化完了ビットを立て，他のスレッドがそのビットを読む場合です。release store で初期化完了ビットを書いてから acquire load によりそのビットを読むまでの間に，read-modify-write 操作（fetch_or など）によって同じワード中の他のビットが操作されるかもしれません。release sequence のルールが無い場合，store と load の間に happens-before 関係が付与されなくなってしまいます。
release sequence
C++20 規格の release sequence の定義 によれば，release sequence とは，あるアトミック変数に対する 1 つの release 操作を先頭とする read-modify-write 操作の列からなる，副作用の列です。
例えば，次のような操作列が release sequence を構成します。各操作は別のスレッドで動いても構いません。
x.store(1, std::memory_order::release);
x.fetch_or(2, std::memory_order::relaxed);
x.fetch_or(4, std::memory_order::relaxed);
あるスレッドが acquire 操作を実行し，release sequence のいずれかの値（0b001，0b011，0b111 のいずれか）を読めた場合，その acquire 操作と，release sequence 先頭の store 操作の間に synchronizes-with 関係が付きます。 synchronizes-with 関係が付く 2 つの操作には自動的に happens-before も付きます。
happens-before による同期
C++ Concurrency in Action1 の "5.3.4 Release sequences and synchronizes-with" から例題 "Listing 5.11" を持ってきて説明します。ソースコードは一部改変しています。
#include <atomic>
#include <chrono>
#include <thread>
#include <vector>
std::vector<int> queue_data;
std::atomic<int> count;
void populate_queue() {
unsigned const number_of_items = 20;
queue_data.clear();
for (unsigned i = 0; i < number_of_items; ++i) {
queue_data.push_back(i);
}
count.store(number_of_items, std::memory_order_release);
}
void process(int data);
void consume_queue_items() {
while (true) {
int item_index = count.fetch_sub(1, std::memory_order_acquire);
if (item_index <= 0) {
std::this_thread::sleep_for(std::chrono::milliseconds{100});
continue;
}
process(queue_data[item_index - 1]);
}
}
プログラムの大まかな構造は，populate_queue() が queue_data にデータをセットし，consume_queue_items() が queue_data からデータを読み出します。
count はアトミック変数で，queue_data に含まれる要素の数を管理します。
まず consume_queue_items() が 1 つのスレッドのみで動く場合を考えます。
populate_queue() がスレッド 1 で，consume_queue_items() がスレッド 2 で動くとします。
consume_queue_items() は queue_data[item_index - 1] というように，アトミック変数ではないデータ構造 queue_data にアクセスしていますが，これは安全でしょうか？
はい，安全です。理由を説明します。
count.fetch_sub は，populate_queue() が初期データを入れ終わるまでずっと 0 を返します。
populate_queue() が初期データを入れ終わり，count.store を実行した後，初回の count.fetch_sub は 20 を返します。
acquire 操作である count.fetch_sub が release 操作である count.store が書いた値を読めたとき，2 つの操作の間に happens-before 関係が成り立ちます。
すなわち「count.store happens before count.fetch_sub」です。
count.store →HB count.fetch_sub が成り立つ場合，happens-before の推移律により queue_data.push_back(i) →HB queue_data[item_index - 1] も成り立ちます。
happens-before 関係のおかげで，スレッド 2 が queue_data[item_index - 1] を実行する時点で queue_data.push_back(i) による副作用（メモリへの書き込み）が見えることが保証されます。
したがって，スレッド 2 から安全に queue_data の要素にアクセスできる，というわけです。
release sequence の役割
count の値は最初に count.store により書かれ，その後は count.fetch_sub により 1 ずつ減っていきます。
count.fetch_sub はアトミックな read-modify-write 操作ですから，release sequence は count.store を先頭とする count.fetch_sub の列となります。
ここで consume_queue_items() が 2 つのスレッドで動く場合を考えます。
どちらのスレッドの count.fetch_sub が先に実行されるか，あるいは何回連続して同じスレッドの count.fetch_sub が呼ばれるかはスレッドの動作順により変わります。
確実に言えるのは，2 回目の count.fetch_sub が読む値は 1 回目の count.fetch_sub が書いた値だということです。
そう，count.store が書いた値 ではない のです。
release sequence のルールが無い場合，2 回目の count.fetch_sub(acquire) が読む値は count.store(release) が書いた値ではないため，
2 回目の count.store(release) はいかなる操作とも happens-before 関係で結ばれません。
したがってデータ競合があることになってしまいます。
実際は，2 回目の count.fetch_sub(acquire) が読む値は count.store(release) を先頭とする release sequence に含まれるいずれかの値，ということになります。
release sequence のルールにより，2 回目の count.fetch_sub(acquire) と count.store(release) の間に happens-before 関係が付きます。
これでめでたく，スレッド 2，3 の両方で queue_data を安全にアクセスできるようになりました。
ここで注意すべきは，happens-before 関係が付くのはあくまで先頭の release 操作とその後の acquire 操作だけである，ということです。 依然としてスレッド 2 と 3 はいかなる happens-before 関係によっても結ばれません。
C++20 以前での release sequence
上記の話は C++20 での release sequence に基づいています。 C++20 以前とは若干定義が変わっていますので，簡単に説明します。（変更の提案は P0982R1 による）
C++20 以前では，release sequence を構成する操作は read-modify-write のほかに，release store 操作と同じスレッドで実行される relaxed store 操作も含まれていました。 なぜなら，規格が制定された当時（つまり C++11 当時）の CPU では，それは必ず満たされる性質だったからです。 どんな CPU でも追加のコスト無しに「release store 操作と同じスレッドで実行される relaxed store 操作」を release sequence に含められるのであれば，含めちゃった方がお得だろうということですね。
C++ のメモリモデルの仕様が普及するにつれ，C++ のメモリモデルに合わせて CPU を設計するケースが増え，その結果，その性質を満たすことが追加の制約となる事例が出てきたそうです。 どんな CPU でも追加コスト無しに実現できると思われていた性質の実現に，実は追加コストがかかってしまう， そして，その満たそうとしていた性質（relaxed store を release sequence に含める）はほとんど役に立たないことから， C++20 で制約の緩和が提案され，取り込まれたようですね。
