yohhoyの日記(別館)

もうちょい長めの技術的メモをしていきたい日記

メモリモデル?なにそれ?おいしいの?

この記事はC++ Advent Calendar 2014の21日目にエントリしています。
内容はC++メモリモデルと逐次一貫性についての概説記事となっています。

f:id:yohhoy:20141221014421j:plain
flickr / nomadic_lass
もくじ

  1. 忙しい人のための「C++メモリモデル」
    1. C++メモリモデル一問一答
  2. ソフトウェアからみた「C++メモリモデル」
    1. “メモリ”という共有リソース
    2. C++ソースコードが実行されるまで
    3. メモリの一貫性と整合性
    4. 逐次一貫性モデル is Easy
  3. ハードウェアからみた「C++メモリモデル」
    1. ハードウェア・メモリ一貫性モデル
    2. C++コンパイラの責任と自由
    3. 強いメモリモデル vs. 弱いメモリモデル
    4. 逐次一貫性モデル is Hard

(本文のみ約9600字)

まえがき

When your hammer is C++, everything begins to look like a thumb.

突然ですが、「メモリモデル(memory model)」という単語を聞いたことはありますか?プログラミング関連の用語として様々な文脈で言及されますが、その正体は曖昧ではっきりせず、まるで神秘のベールに包まれているかのようです。プログラミング言語C++でもマルチスレッド処理が標準サポートされ、同時に「C++メモリモデル」と呼ばれる何かが導入されました。

本記事ではこのC++メモリモデル」について、大まかな雰囲気を掴めるような概要説明を試みます。C++メモリモデルの細部にまで深入りすると、C++言語仕様の深淵を覗き込む話題になってしまうため、とても詳細な解説までは行えません。そのためhappens-before関係をはじめ形式的な定義への言及を避けながら説明をしていきます。

C++メモリモデルの説明に入る前に、曖昧な単語「メモリモデル」の用法について整理しておきましょう。主に下記4パターンのいずれかで用いられるようです。*1

メモリ・アドレッシング・モデル
低レイヤでのプログラミングにおいて、あるメモリ番地を指定(addressing)する方式。古のIntelプロセッサ・リアルモードや、DSP(digital signal processor)などの文脈で用いられる。
メモリ・マネジメント・モデル
仮想マシン(VM)実装において、オブジェクト配置に関連するメモリ管理(management)の方式。Java VM実装の文脈で用いられる。
ハードウェア・メモリ一貫性モデル
プロセッサ・アーキテクチャにおいて、特にマルチプロセッサ・システムからの共有メモリ・アクセス順序に関するモデル。一般にIntel x86(IA-32, x86-64)やSPARC TSOなどは“強いメモリモデル”、ARMやPower PC, Itanium(IA-64)などは“弱いメモリモデル”と紹介される。
ソフトウェア・メモリ一貫性モデル
プログラミング言語において、特にマルチスレッド・プログラムからの共有メモリ・アクセス順序に関するモデル。主要なところではJava言語[Java1.5以降]*2, C++言語[C++11以降], C言語[C11以降], Go言語、他にもPOSIX Threads(Pthreads), OpenMP, LLVM IRなど、マルチスレッド対応のプログラミング言語ではメモリモデルが定義される。*3

本記事ではメモリモデルという単語を、後者「メモリ一貫性モデル(memory consistency model)」の意で扱います。まずはソフトウェア・メモリ一貫性モデルとしてのC++メモリモデルを説明し、続いてハードウェア・メモリ一貫性モデルとの関連性と相違点をみていきます。

1. 忙しい人のための「C++メモリモデル」

今北産業

C++メモリモデル?
そんなものは
無かった

低レイヤなatomic変数(std::atomic)やミューテックス(std::mutex)、生のC++スレッド(std::thread)も全部忘れて、高レイヤな並列処理ライブラリを活用しましょう!

1.1. C++メモリモデル一問一答

Q. C++でマルチスレッド・プログラムを書くために、C++メモリモデルの知識が必要ですか?
A. いいえ。スレッドもミューテックスも、プログラマが知っている通りに動作します。

Q. atomic変数を使ったロックフリー(lock-free)なアルゴリズム記述には必要ですよね?
A. いいえ。C++メモリモデルを知らなくても、正しく動作するロックフリー処理は記述できます。(もちろん別の知識が要求されますが!)

Q. ミューテックスやatomic変数とC++メモリモデルって無関係なの?
A. いいえ、とても深い関係があります。C++メモリモデルは、あらゆるC++実行環境においてミューテックスや“既定の”atomic変数アクセスが、プログラマの期待通りに振る舞うことを保証します。

Q. “既定の”atomic変数アクセスとは?
A. C++ atomic変数への書き出し/読み取りでは、その振る舞い(memory_order列挙型)を制御できます。ただし、特に何も指定せずatomic変数を使うぶんには、普通のプログラマが考える通りに動作するため、C++メモリモデルを理解している必要はありません。

Q. プログラマが考える通りに動作しないことがある?
A. C++ atomic変数アクセスの振る舞いを変更すると、多くのプログラマの直観とは合致しなくなります。C++メモリモデルでは、既定(memory_order_seq_cst)でないatomic変数アクセスの振る舞いもちゃんと定義しますが、それらを正しく理解し使いこなすのは相当にハードルが高いです。

Q. 結局、C++メモリモデルって誰得なの?
A. OSカーネル開発者や高度にチューニングされた並行/並列処理ライブラリ開発者、C++コンパイラ・バックエンド最適化器の開発者、あとは言語法律家(language lawyer)あたりでしょうか。C++メモリモデルは、C++言語の基盤を支える重要な概念ですが、全てのC++プログラマが理解すべきものではありません。

Q. マルチスレッド・アプリケーションの開発者には、関係ないってこと?
A. はい。C++メモリモデルのような低レイヤについて悩むよりも、高レイヤでの並行/並列処理設計を気に掛けるべきです。

という訳で、本記事の要旨はこれだけです。この先は抽象的で退屈な話題がつづきますが、それでも大丈夫という方は続きをどうぞ。

おことわり:以降の説明では、C++マルチスレッド・プログラミングにおいてミューテックスを適切に使用したり、atomic変数がどのようなものか分かる程度の経験があること、また今どきのプロセッサ・アーキテクチャやメモリ・キャッシュ機構の仕組みを概要程度は理解していること、を前提とします。

2. ソフトウェアからみた「C++メモリモデル」

C++メモリモデルは、C++11でのマルチスレッド処理サポートと同時に導入された、“メモリ”の扱いに関する形式的なルールです。まずは、マルチスレッド・プログラムにおけるメモリの扱いを整理します。つづいて普段はあまり気にかけない、C++ソースコードC++コンパイラや実行環境との関係、そもそもC++言語仕様では何を定義するかを確認します。最後に、プログラマ視点では最も重要となる「逐次一貫性モデル」を紹介します。

2.1. “メモリ”という共有リソース

マルチスレッド・プログラムはその名前が示す通り、複数の「実行スレッド(thread of execution)」(一般に「スレッド(thread)」と呼ぶ)、つまり同時並行に動作可能な実行主体を複数個もちます。スレッドを軽量プロセスと呼ぶこともありますが、メモリの扱いはプロセスとスレッドで大きく異なります。通常のプロセスはそれぞれ独立したメモリ空間を管理し、互いのメモリ空間に直接干渉することはできません。一方のスレッドでは同じメモリ空間を共有するため、メモリを介したデータ通信や同期制御が可能です。つまり、マルチプロセス処理は分散型メモリ・並行処理システム、マルチスレッド処理は共有型メモリ・並行処理システムと解釈可能です。

マルチスレッド・プログラムにおけるメモリ空間は、概念的には複数スレッドから利用される共有リソースといえます。このようにメモリ空間を1つの共有リソースとみなし、各スレッドからメモリに書き出す値/メモリから読み取る値に関して、スレッド間で共有される“メモリ”というリソースがどのように振る舞うかを定義したものが「ソフトウェア・メモリ一貫性モデル」です。ここでいう“メモリ”とは、1個の変数に対応したメモリ領域のみを指すのではなく、あらゆる変数が配置されたメモリ空間全体を指すことに留意ください。つまり「C++メモリモデル」は、C++で記述されたマルチスレッド・プログラムにおいて、複数の変数アクセスにより書き出す値/読み取る値の振る舞いを定義します。

2.2. C++ソースコードが実行されるまで

C++メモリモデルはC++言語仕様の一部ですが、最初に“C++言語仕様とは何を定義するか”を確認しておくべきでしょう。2014年12月現在のC++言語仕様は、正式名称 ISO/IEC 14882:2011 という国際標準規格にて定義されます*4GCCLLVM/ClangやMicrosoft Visual C++など全てのC++コンパイラは、この標準規格が定めるC++言語仕様に則って実装されており*5、入力C++ソースコードから出力機械語プログラムへの変換処理を行います。では、C++言語仕様は“C++ソースコードからどのような機械語へ変換するか”を定義するのでしょうか。C++言語は多種多様なプロセッサ・アーキテクチャを対象としており、このアプローチは現実的ではなさそうです。

実際のC++言語仕様では、まず抽象機械(abstract machine)と呼ばれる仮想的な実行環境を定義し、C++ソースコードが抽象機械上でどのように動作するかを記述します。C++11でマルチスレッド対応したというのは、この抽象機械にスレッドという概念が導入されたことを意味します。この抽象機械上での動作定義は、C++コンパイラによるC++ソースコードから機械語プログラムへの変換処理と、プロセッサ上での機械語プログラムの実行処理の両方を包含します。つまり、C++言語仕様では“入力C++ソースコードはどのように動作すべきか”のみを定義し、具体的な変換処理(コンパイル処理)や実行時処理は、C++コンパイラと対象プロセッサ・アーキテクチャに任せているのです。*6
f:id:yohhoy:20141221005030p:plain

これだけだとコンパイル処理には自由度など無いように聞こえますが、現実のC++コンパイラはさまざまな「最適化」を行います。最適化とは処理の省略や変形によって動作の高速化を図るものですが、C++言語仕様でC++ソースコードのあるべき動作が決められているのに、どこに省略や変形の余地が残っているのでしょうか。実は抽象機械による動作定義には続きがあり、“最終結果が同じである限りどんな変形を行ってもよい”という特別ルールが設けられています(通称、as-ifルールと呼ぶ)。抽象機械上でのマルチスレッド・プログラムの“最終的な結果が等価である”こと、つまり処理の省略や変形を行っても等価なプログラムとは何かということを、厳密に仕様記述するために「C++メモリモデル」が存在します。*7 *8

2.3. メモリの一貫性と整合性

異なるスレッドから“同時に”アクセス可能なのはatomic変数に限られており、C++マルチスレッド・プログラム上から通常の変数に同時アクセスした場合は、データ競合(data race)による未定義動作を引き起こします。「C++メモリモデル」では、まさにこの別スレッドからの操作が“同時でなくなる”条件を、各スレッドからの“操作間に順序付け(ordering)が保証される”という形で表現します。「C++メモリモデル」の本質はこの“操作間の順序付け”を定義することであり、atomic変数だけでなくC++標準ライブラリ提供同期プリミティブの振る舞いも包括的に記述します。例えばミューテックス(std::mutex)オブジェクトが排他制御として機能することは、lock/unlock操作間での順序付け保証として表現されます。*9

C++メモリモデル」はソフトウェア・メモリ一貫性モデルであると説明してきましたが、似た意味の単語"Coherency"と"Consistency"との違いを明確化しておきましょう。辞書によっては両者とも“一貫性”と訳されてしまいますが、C++メモリモデルでは下記の通り区別されます。なお、整合性は一貫性の議論対象を限定したものとみなせ、一般にメモリ一貫性モデルは整合性に関する定義を内包します。

整合性(Coherency)
異なるスレッドから単一のatomic変数にアクセスしたとき、各スレッドが書き出す値/読み取る値の関係を定義する。
一貫性(Consistency)
異なるスレッドから異なるatomic変数にアクセスしたとき、各スレッドが書き出す値/読み取る値の関係を定義する。

“整合性(Coherency)”は同一atomic変数(M)からの読み/書きを対象とし、その振る舞いは下記リストの通りとなります。少し読みづらいと思いますが、一度は丁寧に追ってみてください。

  • A:M = 1 → B:M = 2 と順序付けられるとき、最終的なMの値は Bで書き出した値2 となる。
  • A:r0 = M → B:M = 2 と順序付けられるとき、最終的なMの値は Bで書き出した値2 となる。なお、Aでは Bで書き出した値2 を読み取ることはない。
  • A:r0 = M → B:r1 = M と順序付けられるとき、Bでは Aが読み取った値r0 を再び読み取る。
  • A:M = 1 → B:r1 = M と順序付けられるとき、Bでは Aで書き出した値1 を読み取る。

あまりに当然のことで退屈に感じるでしょうが、このようにプログラマが当然期待するメモリ・アクセスの振る舞いを、C++メモリモデルでは形式的に定義していきます。*10

2.4. 逐次一貫性モデル is Easy

“整合性(Coherency)”では単一atomic変数が対象でしたが、“一貫性(Consistency)”の対象は複数atomic変数へと拡大されます。マルチスレッド・プログラム頭の体操ということで、下記コードの実行結果がどうなるか考えてみてください。関数th1, th2は異なるスレッドからそれぞれ1回だけ呼ばれるものとします。

#include <atomic>
std::atomic<int> x = 0;
std::atomic<int> y = 0;
int r1, r2;

void th1() {
  y = 1;
  r1 = x;
}
void th2() {
  x = 1;
  r2 = y;
}
// 各スレッドが読み取った r1, r2 の値は?

正解は{r1,r2}={0,1}, {1,0}, {1,1}の3パターンのいずれかです。マルチスレッド・プログラムでは、このように実行結果が一意に定まらない(非決定的動作)ことがあるため、ちゃんと3パターンとも回答してくださいね*11。では{0,0}という実行結果は起こりえるでしょうか?

“結果{0,0}なんて起きるわけないだろ!”と考えた方、おめでとうございます。あなたはもう「逐次一貫性(sequential consistency)」を理解しています。そんな自覚は無かったというなら、無意識に逐次一貫性モデルを適用したのです。“いや、もしかしたらありえるかも”と考えたあなたは、…天が落ち地が崩れるのを心配するタイプですか?杞の国の人は別にして、このように逐次一貫性モデルはプログラマの直感とよく合致しており、「C++メモリモデル」では“既定の”atomic変数アクセスの振る舞いが逐次一貫性モデルに従うことを保証しています。

逐次一貫性モデルに従って、前掲マルチスレッド・プログラムの実行結果を確認してみましょう。Wikipediaでは逐次一貫性を次のように説明しています。(Lamport氏オリジナル論文からの引用訳)

どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること。

本記事ではC++メモリモデルの議論にあわせて、下記説明に改変します。*12

マルチスレッド並行処理の結果は、各スレッド上のatomic変数操作をシングル・スレッドで任意にインターリーブ実行した結果と一致すること。

この説明なら少しは分かり易くなったでしょうか。3パターンの結果を導くインターリーブ実行例を挙げてみます。

// {r1,r2}={0,1}のインターリーブ実行例
y = 1;   // th1-1
r1 = x;  // th1-2
x = 1;   // th2-1
r2 = y;  // th2-2
// {r1,r2}={1,0}のインターリーブ実行例
x = 1;   // th2-1
r2 = y;  // th2-2
y = 1;   // th1-1
r1 = x;  // th1-2
// {r1,r2}={1,1}のインターリーブ実行例
y = 1;   // th1-1
x = 1;   // th2-1
r1 = x;  // th1-2
r2 = y;  // th2-2

f:id:yohhoy:20141221005652p:plain

結果{0,0}が生じるには、最初にatomic変数x, yからの読み取りが行われる必要がありますが、これだと関数th1, th2内でのオリジナル処理順序を壊しています。

// NG: 逐次一貫でない
r1 = x;  // th1-2
r2 = y;  // th2-2
y = 1;   // th1-1
x = 1;   // th2-1

f:id:yohhoy:20141221005709p:plain
上記のような入れ替えは直感的にも許されませんし、もちろん逐次一貫性モデルでも許容されません。このように「C++メモリモデル」が“既定の”atomic変数アクセスに対して逐次一貫性を保証するため、プログラマは安心してatomic変数を使ったマルチスレッド処理を記述できます。

ところで“既定でない”atomic変数アクセスでは一体何が起きるのでしょう?前掲サンプルコードを少し変更してみます。*13

#include <atomic>
std::atomic<int> x = 0;
std::atomic<int> y = 0;
int r1, r2;

void th1() {
  y.store(1, std::memory_order_release);
  r1 = x.load(std::memory_order_acquire);
}
void th2() {
  x.store(1, std::memory_order_release);
  r2 = y.load(std::memory_order_acquire);
}
// 各スレッドが読み取った r1, r2 の値は?

この変更後コードの実行結果は、{r1,r2}={0,1}, {1,0}, {1,1}, {0,0}の4パターンのいずれかになります。“既定の”atomic変数アクセスでは起こりえなかった{0,0}も含まれる通り、逐次一貫性よりも“弱い”順序付けの振る舞いは、プログラマの直観とは合致しない結果をもたらします!

さて、本当の「C++メモリモデル」の話題はここから始まるのです。…が、これ以上は本記事の範囲(と私の理解度と説明力)を超えています。あしからずご了承ください。

では、説明内容をまとめておきましょう。「C++メモリモデル」とは:

  • メモリ空間全体を複数スレッド間での共有リソースとみなします。
  • 複数スレッドからメモリへの書き出し/読み取りの振る舞いを定義します。
  • C++ソースコードが抽象機械でどのように動作するかを定義します。
  • as-ifルールに基づく等価なプログラム変換(許される最適化)を定義します。
  • 操作が“同時でない”とは何かを順序付けにより定義します。
  • 同期プリミティブの振る舞いを順序付けにより記述します。
  • 単一のatomic変数に対するアクセスの整合性を保証します。
  • 複数のatomic変数に対する既定アクセスの逐次一貫性を保証します。



3. ハードドウェアからみた「C++メモリモデル」

ここまで「C++メモリモデル」をソフトウェア視点で説明してきましたが、C++言語で書かれたプログラムは実在のプロセッサで動く以上、ハードウェア視点でも見ていく必要があるでしょう。プロセッサ・アーキテクチャは固有のハードウェア・メモリ一貫性モデルを持つため、まずは「C++メモリモデル」との関係性を整理します。また、いわゆる“強いメモリモデル”や“弱いメモリモデル”のプロセッサ・アーキテクチャと、C++メモリモデルが既定で提供する逐次一貫性モデルとの関係を説明します。

3.1. ハードウェア・メモリ一貫性モデル

マルチプロセッサ・システムでは各プロセッサがメインメモリに直結されるのではなく、一般的には何段かのメモリ・キャッシュ機構を経由します。さらに単体プロセッサのスループット性能を向上させるため、命令発行順序を入れ替えるアウト・オブ・オーダー(OoO; Out-of-Order)実行も行います。これらの技術によって処理性能向上が図られてきましたが、一方で機械語プログラムに“書いてある順序”でメモリ・アクセスが行われなくなるという問題を引き起こします。さすがに何の保証もされないシステムでは正しいプログラムが成立しえないため、プロセッサ・アーキテクチャとしてメモリ・アクセス順序に関する一定の保証、つまり「ハードウェア・メモリ一貫性モデル」が必要とされます。このような順序保証を与えるために、メモリ・ストア(store)やロード(load)命令に順序付け制約効果を持たせたり、命令発行順序の入れ替えを禁止するメモリバリア(memory barrier)命令などが提供されています。

C++メモリモデル」が定義する順序付けと、ハードウェア・メモリ一貫性モデルが定義する順序付けでは、その意味合いが少し異なります。C++メモリモデルでは、異なるスレッド上でのメモリ・アクセス操作間に対して、維持すべき順序関係を定義します。ハードウェア・メモリ一貫性モデルでは、同一スレッド上のメモリ・ストア/ロード命令間で、先行命令の追い越し禁止を表現します。前者は抽象的な操作の関係性に着目し、後者は具体的な制限事項に落とし込んだ定義といえます。

3.2. C++コンパイラの責任と自由

C++ソースコードマルチプロセッサ・システムで実行されるまでのステップは、ご存知のようにコンパイル処理と実行時処理に分割されています。既に説明した通り、各ステップではメモリ・アクセスに関する順序入れ替えが発生します。

コンパイル処理
C++コンパイラによるC++ソースコードから機械語プログラムへの変換。コンパイラの最適化により命令配置順序の入れ替えが行われる。
実行時処理
マルチプロセッサ・システムによる機械語プログラムの解釈実行。メモリ・キャッシュ機構やOoO実行によりメモリ・アクセス順序の入れ替えが行われる。

f:id:yohhoy:20141221012549p:plain
C++メモリモデル」は、C++言語仕様という仮想世界の抽象機械に対してメモリ・アクセスの振る舞いを定義しており、対応する現実世界ではコンパイル処理および実行時処理のメモリ・アクセスの振る舞いにそれぞれ影響を及ぼします。「C++メモリモデル」により記述される自由度と制約条件に従って、C++ソースコードから機械語プログラムへの変換時に、C++コンパイラは命令配置順序の並び替えやメモリバリア命令挿入を行います。マルチプロセッサ・システムは自身のハードウェア・メモリ一貫性モデルに従って、C++コンパイラが生成した機械語プログラムを解釈実行します。そして、このコンパイル処理と実行時処理の組合せによって得られる最終結果は、as-ifルールの下で抽象機械の動作結果と一致しなければなりません。

プロセッサによる機械語プログラムの解釈実行ステップでは、元のC++ソースコードが表現していた順序付け関係を直接知ることはできません。C++コンパイラの責任とは、C++ソースコードが表現するプログラム動作セマンティクスを維持できるよう、ハードウェア・メモリ一貫性モデルに従う機械語プログラムへと翻訳することなのです。一方、as-ifルールの下でプログラム動作セマンティクスが等価である限り、コンパイル時のあらゆるメモリ・アクセス命令の入れ替え(最適化)や、実行時のメモリ・キャッシュ機構やOoO実行によるメモリ・アクセス順序入れ替えが許容されるとも言えます。

3.3. 強いメモリモデル vs. 弱いメモリモデル

世の中には多様なプロセッサ・アーキテクチャが存在しており、それぞれが固有のハードウェア・メモリ一貫性モデルを持ちます。よく強いメモリモデル/弱いメモリモデルと分類されますが、これはメモリ・アクセス命令が持っているメモリ・アクセス順序保証の度合いを強弱で言い表したものです。強いメモリモデルでは順序保証の度合いが強く、ほぼ機械語プログラムに記載された順番のままメモリ・アクセスが行われます。弱いメモリモデルでは、実行時のメモリ・アクセス順序が機械語プログラム中のメモリ・アクセス命令順と一致するとは限りません。つまり「ハードウェア・メモリ一貫性モデル」とは、そのプロセッサ・アーキテクチャで最低限保証されるメモリ・アクセスの振る舞いに関する順序保証を表します。たとえ弱いメモリモデルであっても、明示的なメモリバリア命令と組み合わせれば順序保証を行えることに留意ください。

一般的なプロセッサ・アーキテクチャのハードウェア・メモリ一貫性モデルは、「C++メモリモデル」が既定で提供する逐次一貫性よりも“弱い”順序保証しか与えません。強いメモリモデルを持つと言われるIntel x86アーキテクチャ・ファミリ(IA-32, x86-64)でさえ、マルチプロセッサ・システムでは逐次一貫性モデルよりも“弱い”メモリモデルなのです。これはプロセッサ・アーキテクチャ逐次一貫性を実現するには、追加のオーバーヘッドを伴うことを意味します。特にマルチプロセッサ・システムではメモリ・キャッシュ機構の存在が問題となります。

3.4. 逐次一貫性モデル is Hard

マルチプロセッサ・システムで全てのプロセッサがメインメモリに直結されると仮定した場合、あるプロセッサからのメモリ書き出し/読み取りはすぐに他プロセッサから“見える”ため、逐次一貫性を実現するのは難しくありません。実際にはメモリとプロセッサの間にメモリ・キャッシュ機構が介在し、メモリ書き出し/読み取りではメインメモリ内容と“全ての”プロセッサのメモリ・キャッシュ内容の辻褄を合わせる(キャッシュ・コヒーレンシ制御)必要があります。このようなメモリ・キャッシュの制御は、プロセッサとメモリを物理的につなぐインターコネクトやバス上での通信によって実現されます。マルチプロセッサ・システムのような共有型メモリ・並行処理システムでは、プロセッサ数が増えると通信量が指数的に増大してしまうため、現実のマルチプロセッサ・システムにとって逐次一貫性モデルを保証するのはコストが大きいのです。

ソフトウェア視点での結論とは逆に、ハードウェア視点では残念な結論となってしまいましたが、メジャーなプロセッサ・アーキテクチャ固有の話も少しだけ言及しておきます。*14

Intel x86(IA-32, x86-64)
逐次一貫性にかなり近いハードウェア・メモリ一貫性モデルのため、追加のオーバーヘッドはほとんどありません。atomic変数への書き出し処理だけが若干のペナルティを受けます(lock xchg命令)。
ARM(ARMv7, ARMv8)
弱いメモリモデルのハードウェア・メモリ一貫性モデルのため、逐次一貫性の実現にはメモリバリア命令発行が必要です(dmb命令)。ARMv8では専用のメモリ・ストア/ロード命令が追加され(stlr/ldar命令)、メモリバリア命令発行が不要になります。

弱いメモリモデルを持つマルチプロセッサ・システム性能を最大限引き出すには、対象プロセッサ・アーキテクチャのハードウェア・メモリ一貫性モデルを理解し、かつC++ atomic変数アクセスにおいて逐次一貫性より“弱い”順序付けを指定する必要があります。とはいえ一般にマルチスレッド・アプリケーションでは、そもそもatomic変数のような低レイヤ同期プリミティブを頻繁には利用しません。OSカーネル開発者や並行/並列処理ライブラリ開発者を別にすれば、アプリケーション・プログラマがこの領域まで踏み込む必要はないと思います。

おわりに

本記事では「C++メモリモデル」が何のためにあり、どのような意義を持つかをトップダウン式アプローチで説明しました。C++言語仕様では厳密かつ形式的な定義を行いますが*15ボトムアップにそれらを理解するのは骨の折れる作業です。本記事がこれからC++言語仕様を読んでみようというイカれた暇人知的好奇心旺盛な方への参考情報となれば幸いです。

C++ Advent Calendar 2014 は 22日目 hgodai さんの記事へと続きます。
f:id:yohhoy:20141221014550j:plain
flickr / ed_welker

はしがき:昨年に引き続いて、手書き画像には"Paper by FiftyThree"を使いました。ズーム機能があることに気付いたので、今年の方が文字は読みやすいかも?(そもそも字が汚いのはアレ)

*1:Internet上でのオレオレ調査による。各用語は本記事のために独自定義しており、対象文脈における一般的な用語とは異なる可能性があります。

*2:プログラミング言語におけるソフトウェア・メモリ一貫性モデルの重要性は、Java 1.4以前での“Double-Checked Locking問題”を発端に見直されました。後発のC++メモリモデル定義は、Java言語での実績や改善を反映したものとなっています。

*3:C#言語(別名 ECMA-334)もマルチスレッド対応した主要プログラミング言語といえますが、2014年12月現在もそのメモリモデルは言語仕様として厳密定義されておらず、Microsoft CLR実装=マルチスレッド動作仕様というお寒い状況のようです。

*4:本記事では2014-12-21現在の標準規格を“C++14”ではなく“C++11”としています。2014年8月にはisocpp.org記事"We have C++14!"とアナウンスがありましたが、ISO公式サイトによると2014-12-17付けでStage 60.00(International Standard under publication)であり、国際標準規格としては正式発行の寸前という状況のようです。2014年内に間にあうんですかね?

*5:もちろん、各コンパイラベンダによる独自仕様拡張や、標準規格への準拠度合いの違いはあります。

*6:本文中ではC++ソースコードから機械語プログラムに変換するC++コンパイラを前提としていますが、C++ソースコードから直接実行するC++インタプリタも存在しえます。C++言語仕様はどちらの実装形態も許容します。

*7:過去のC++言語仕様においても、副作用完了点(sequence point)という形で「C++メモリモデル」相当の定義は存在します。ただしC++03時点ではスレッドという概念が存在しないため、C++マルチスレッド・プログラムの意味はC++コンパイラベンダ依存や、POSIX Threadsなどの外部システム依存とされていました。

*8:C++言語仕様に沿った厳密な解釈をすると、一般に「C++メモリモデル」と呼ばれる言い回しは正確ではありません。C++11言語仕様でメモリモデルを探すと1.7節 The C++ memory model [intro.memory]が見つかりますが、ここは“バイト(byte)”や“メモリ位置(memory location)”を定義しているに過ぎません。本記事では「C++メモリモデル」=ソフトウェア・メモリ一貫性モデルと解釈していますので、対応する規格文面は1.9節 Program execution [intro.execution]、1.10節 Multi-threaded executions and data races [intro.multithread]、およびatomic変数を定義する29章 Atomic operations library [atomics]が該当します。

*9:C++標準ライブラリ提供のミューテックス仕様では、“前のunlock操作からlock操作へのsynchronize-with関係が成立する”とだけ記述されます。この簡素な定義とC++メモリモデルをもとに解釈すると、プログラマが期待する通りの排他制御が実現されます。

*10:単一atomic変数アクセスに関する整合性は、最も弱い順序付けであるrelaxdアクセスを含む全てのmemory_orderで保証されます。

*11:たまに誤解されていますが、マルチスレッド・プログラムでは必ず非決定的動作(indeterminate behavior)となるわけではありません。並列処理設計によっては、入力値に対応した一意な結果が求まる“決定的動作のマルチスレッド処理”を構築可能です。なお、データ競合による未定義動作(undefined behavior)とマルチスレッド処理の非決定的動作には直接的な関係はありません。データ競合を一切含まないマルチスレッド・アプリケーションであっても、例示コードのように非決定的動作になることはあります。一方でデータ競合を含むマルチスレッド・アプリケーションでは、C++言語仕様上は何ら保証がされないものの、未定義動作による現実の帰結として非決定的動作となるケースがあります。

*12:Lamport定義に照らし合わせると、「すべてのプロセッサがある順序で逐次的に実行」=シングル・スレッドで任意にインターリーブ実行、「個々のプロセッサの処理順序がプログラムで指定された通り」=関数内でのオリジナル処理順序は維持される、という対応付けになっています。

*13:C++標準ライブラリatomicクラステンプレートでは演算子オーバーロードを行うため、“既定の”atomic変数アクセスであれば通常変数と同じように取り扱うことができます。atomic変数アクセスの振る舞いを指定するときは、明示的にstore/loadメンバ関数を呼び出さなければなりません。

*14:情報源: http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

*15:C++メモリモデルではあらゆる順序付けについて厳密な定義を行いますが、それでもmemory_order_relaxedによるout-thin-air-value問題や、memory_order_consumeと関連属性に関する合意などの未解決課題が残っています。