volatile変数とマルチスレッドとの関係についての押し問答（後編）

プログラミング言語C++のvolatile変数がスレッド間の同期機構として機能するか否かという論点について、有りそうな質問とその答えについての簡易メモの続きの続き。（自身の思考整理用）

ある変数がスレッド間の同期機構として機能するためには、下記3つの性質が保証されることが要求される。volatile変数ではこれらのいずれも保証されないため、同期機構としては利用できない。

原子性(atomicity) → id:yohhoy:20121016
可視性(visibility) → id:yohhoy:20131009
順序性(ordering)

順序性の保証

注意：簡単のため、atomic変数への逐次一貫性(sequential consistency)アクセスのみを対象とする。これはC++11 atomicアクセス操作における既定動作である。

説明のためコード例示に番号[A]〜[D]を追加付与している。

順序性(ordering)の保証とは、「あるスレッド上で行われた複数変数に対する書き込み結果が、別スレッドから観測したときも同一順序で観測できる」ことを意味する。下記コードではスレッド間の同期機構として変数flagを利用し、かつ “[A]dataの値を更新→[B]flagの値を更新→[C]flag更新結果を観測→[D]data更新結果を観測” という実行順を期待している。volatile変数flagを用いたこのようなプログラムでは順序性が保証されず、その結果として未定義動作を引き起こす。
int data = 0;
volatile int flag = 0;

// 生産側スレッド
void producer_thread()
{
  data = 42;  // [A]
  flag = 1;   // [B] ???
}

// 消費側スレッド
void consumer_thread()
{
  while ( !flag ) {}   // [C]
  assert(data == 42);  // [D] ???
}
volatile変数とマルチスレッドとの関係についての押し問答（中編）

順序性とは何か: プログラム上の任意の操作と、他操作との間の前後関係（発生の順序）のこと。ここでの “操作” とは、「変数への書き込み」もしくは「計算式の評価」のいずれかを指す。変数からの値の読み出しは、計算式の評価に含まれる。なお、あらゆる操作間で前後関係が定義されるのではなく、どちらが先に生じると定義できない、つまり同時に起こりえるという関係（並行処理）も存在する。
プログラムは “書いた通りの順序” で動くべきだ: 同一スレッド上で行われる任意の2つの操作について、両者の前後関係はソースコード上での出現順と一致する（＝書いた通りの順序）。一方、異なるスレッド上で行われる2つの操作間では、特別な仕組み（同期機構）を用いない限りは前後関係が定義されない。つまり異なるスレッドをまたぐ操作、すなわち変数の書き込み／読み出しにおいて、プログラムはもはや “書いた通りの順序” で動作する保証がない。なおC++11言語仕様において、volatile変数を同期機構とみなすという定義は存在しない。
コンパイラ最適化のバグではないのか: コンパイラが行う “最適化” 処理は、「シングルスレッド実行で同じ結果が得られる限り、途中計算は自由に行ってよい」＋「同期機構を介した異スレッド間操作のみ順序性を維持する」というルール（as-ifルール）に従う。これは、標準でスレッド非サポートのC++03以前から用いられてきた最適化技法を、スレッドを追加導入したC++11以降でも最大限活用するための前提条件といえる。ソースコード上に同期機構が出現しない限り、コンパイラにはシングルスレッド実行のみを考慮した最適化を行う自由度がある。
volatile変数＝最適化抑制ではなかったのか: この解釈は正しくもあり、また大きな誤解でもある。コンパイラにとってソースコード上は冗長に見えるvolatile変数操作を、勝手に削除・移動しないという意味において、volatile変数は最適化抑制という効果をもつ。ただし、該当のvolatile変数単体のみが対象、かつシングルスレッド実行を前提とすることに注意。つまり、volatile変数（flag）と非volatile変数（data）との間では、この意味での最適化抑制効果はもたないため、コンパイラが2つの操作の実行順を入れ替える可能性がある。また既に述べたとおり、異なるスレッドからの同一変数（flag）操作間の順序性には影響を及ぼさない。
順序性保証がないと何が起こるのか: 目的のために保証するべき前後関係は “[A]dataの値を更新” と “[D]data更新結果を観測” との間の順序性である。各スレッド上での順序性 “[A]→[B]” および “[C]→[D]” は期待通り保証される。ただし、volatile変数ではこの間をつなぐ “[B]flagの値を更新” と “[C]flag更新結果を観測” の前後関係は定義できず、全体として最終的に期待する順序性 “[A]→[B]→[C]→[D]” つまり “[A]→[D]” を導けない。ひとたび異なるスレッド上での “[B]” と “[C]” との順序性が定義できないとなると、単一スレッド上の “[A]→[B]” や “[C]→[D]” には前掲のas-ifルールを適用できる。as-ifルール下でのシングルスレッド実行では、実行順[A], [B]、実行順[B], [A]の両者とも同じ結果をもたらすため、実行順の入れ替えが生じうる。同様の観点で、コンパイラは[C]と[D]の実行順も入れ替え可能であると判断する。
atomic変数を用いるとどうなる？: 前掲コードの場合、flagをatomic変数(std::atomic<int> flag;)に修正すればよい。異なるスレッド上でのatomic変数書き込み／読み出し操作間には順序性が保証される*1、つまり “[B]flagの値を更新→[C]flag更新結果を観測” の順序性が保証されるため、“[A]→[B]→[C]→[D]” から “[A]dataの値を更新→[D]data更新結果を観測” を導くことができる。このとき処理系（コンパイラ／プロセッサ）では、各スレッド上における “[A]→[B]” や “[C]→[D]” の順序性に従って、実行順[A], [B]および実行順[C], [D]を保証する必要がある。また異なるスレッド間の “[B]→[C]” の順序性に従って、実行順[B], [C]も保証する。
順序性＝実行順ではないのか: ここまでの議論において、2つの単語「順序性」と「実行順」を注意深く使い分けてきた。「順序性」は抽象的かつ形式的な定義であり、プログラムを構成する操作間に課される前後関係という拘束条件である。つまり、順序性によってソースコードが表すプログラムの動作セマンティクスが定義される。一方、「実行順」は処理系上で命令が実行された順番を意味しており、C++言語仕様ではas-ifルールを満たす限り、すなわち順序性のセマンティクスを変えない範囲でのあらゆる実行順を許容する。
処理系による実行順の保証とは？: 処理系によるC++プログラムの実行は2つのフェーズ、1)コンパイラによるソースコードから機械語命令列への変換処理、2)プロセッサによる機械語命令列の実行へと分解できる。実行順を保証するには、両フェーズを考慮して操作の順序性を維持する必要がある。1)コンパイラによる順序性の維持では、単に2つの操作の順序入れ替えを禁止すればよい（＝ソースコード上の出現順を維持する）。2)プロセッサによる順序性の維持では、複数プロセッサ間のキャッシュ同期機構および単一プロセッサ内のOut of Order実行機構を制御する必要がある。プロセッサの命令セットアーキテクチャでは、これらを制御する専用のメモリバリア命令が用意される*2。プロセッサでの実行時には機械語命令列しか見えないため、ソースコード上での順序性を表現する手段として、コンパイラでは機械語命令列へ適切なメモリバリア命令を挿入する。
よくわからん／日本語でOK: Enjoy ISO/IEC 14882:2011 §1.9[intro.execution], §1.10[intro.multithread].

yohhoyの日記

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

volatile変数とマルチスレッドとの関係についての押し問答（後編）

順序性の保証