読者です 読者をやめる 読者になる 読者になる

yohhoyの日記(別館)

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

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

C++

この記事は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と関連属性に関する合意などの未解決課題が残っています。

条件変数 Step-by-Step入門

C++ C POSIX Boost

多くのプログラミング言語では、マルチスレッド処理向け同期プリミティブとして「ミューテックス(mutex)」と「条件変数(condition variable)」を提供しています*1 *2ミューテックス排他制御機構として有名ですし、その動作もロック(lock)/アンロック(unlock)と比較的理解しやすいため、不適切に利用されるケースはあまり無いと思います*3。一方、条件変数の動作仕様はしばしば誤解され、不適切な利用による並行性バグに悩まされるケースが多いようです。

本記事では、スレッドセーフなFIFO(First-In-First-Out)キューを段階的に実装していく事例を通して、条件変数の適切な使い方について説明していきます。例示コードではC++11標準ライブラリを用いますが、Pthreads(POSIX Threads)やC11標準ライブラリへは単純に読み替え可能です(→Pthreads/C++11/C11対比表)。また、C++11標準ライブラリからBoost.Threadライブラリへの対応関係は自明なはずです。

本記事中のソースコードはBoost Software License 1.0で公開しています。

Pthreadsに馴染みがある人向けの補足:pthread_cond_signalnotify_onepthread_cond_broadcastnotify_allへと読み替えてください。

さっそく

次の仕様を満たす、スレッドセーフ・FIFOキューmt_queueを実装していきます。

クラス仕様
int型要素を最大10個まで格納可能なFIFO操作コンテナ。各メンバ関数を異なるスレッドから同時に呼び出してもよい(スレッドセーフ)。*4
push操作
キューに新しい要素を1つ追加する。キューに空き容量が無ければ、空きができるまで呼び出し元スレッドをブロッキングする。
pop操作
キューから最も古い要素を1つ取り出す。キュー内に要素が存在しなれば、要素が追加されるまで呼び出し元スレッドをブロッキングする。

とりあえずロジックだけ実装すると、下記のような感じでしょうか。

#include <queue>

class mt_queue {
  static const int capacity = 10;
  std::queue<int> q_;
public:
  void push(int data) {
    while (q_.size() == capacity)
      ;
    q_.push(data);
  }
  int pop() {
    while (q_.empty())
      ;
    int data = q_.front();
    q_.pop();
    return data;
  }
};

このコードはマルチスレッド動作について一切考慮していないため、異なるスレッドからpush()/pop()メンバ関数が同時に呼び出されると、データ競合(data race)により正常に動作しません(データ競合についてはこちらの記事も参照下さい)。偶然に正常動作する可能性もゼロではありませんが、本質的に“壊れた”コードであると認識すべきです。マルチスレッド処理プログラミングでは並行処理設計が何よりも重要です。1万回に1回といった低頻度でのプログラムクラッシュ、システム高負荷状態でのみ発生するデッドロックデバッグビルドは問題無いのにリリースビルドだと処理ストールといった、ステキなデバッグ体験をしたいのでない限り、“とりあえず動けばOK”という方針はお勧めできません。

Step0: ミューテックス+ビジーループ

マルチスレッド処理プログラミングでは、ミューテックスによる排他制御が全ての基本となります。複数スレッドから同時更新される可能性のある変数アクセスは、ミューテックスによるロックで全て保護する必要があります。まずは、最も単純なビジーループ(busy-loop; busy-wait)方式で仕様通り実装してみましょう。[mt_queue0.cpp

// mt_queue0.cpp抜粋
#include <mutex>

class mt_queue {
  //...
  std::mutex mtx_;  // ★ミューテックスを導入
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);  // ロック獲得
    while (q_.size() == capacity) {
      lk.unlock();  // ロック一時解放
      std::this_thread::yield();
      lk.lock();    // ロック再獲得
    }
    q_.push(data);
  }  // ロック解放
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);  // ロック獲得
    while (q_.empty()) {
      lk.unlock();  // ロック一時解放
      std::this_thread::yield();
      lk.lock();    // ロック再獲得
    }
    int data = q_.front();
    q_.pop();
    return data;
  }  // ロック解放
};

メンバ関数実装のwhileループ中で、ロック一時解放lk.unlock()→ロック再獲得lk.lock()を忘れずに記述しましたか?このロック一時解放を行わないと、push()/pop()の同時呼び出しでデッドロックが発生します。例えば、1)キューが空っぽのときpop()呼び出し→2)ロックを保持したままwhile (q_.empty())ループ→3)別スレッドのpush()呼び出し先頭で永久にロック獲得待ちという状況です。もう1パターン自明なデッドロックシナリオがありますが、こちらは練習問題として考えてみて下さい。ヒント:push/popの状況を逆転
また、ロック一時解放領域でyield()を呼び出していますが、この処理を省略してもmt_queueクラスは仕様通り動きます。処理系によってはyield()の有無で動作性能が改善するでしょうが、ビジーループがCPUリソースを浪費する非効率な方式であることに変わりはありません。(ビジーループが常に不適切ということではなく、OSカーネルやハードウェア制御ドライバなどの低レイヤ・プログラミングでは有用なケースもあります。ただし、通常のアプリケーションプログラミングでは基本的に避けるべきでしょう。)

Step1: 条件変数による待機/通知処理

それでは、さっそく条件変数を使っていきましょう。排他制御用のミューテックスはそのままに、新しく条件変数を追加することに注意してください。ここはよく誤解されるポイントなのですが、セマフォのようにそれ単体で機能する同期プリミティブと異なり、条件変数は必ずミューテックスと紐付けて利用しなければ意味をなしません。[mt_queue1.cpp

// mt_queue1.cpp抜粋
#include <mutex>
#include <condition_variable>
 
class mt_queue {
  //...
  std::mutex mtx_;
  std::condition_variable cv_;  // ★条件変数を追加
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    while (q_.size() == capacity) {
      cv_.wait(lk);    // 要素数変更があるまで待機
    }
    q_.push(data);
    cv_.notify_all();  // 要素数変更を通知
  }
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);
    while (q_.empty()) {
      cv_.wait(lk);    // 要素数変更があるまで待機
    }
    int data = q_.front();
    q_.pop();
    cv_.notify_all();  // 要素数変更を通知
    return data;
  }
};

このコードでは条件変数オブジェクトcv_を、「キュー内の要素数に何らかの変更があった」イベントの待機/通知処理に利用しています。このときCPUリソース利用の観点からは、条件変数を用いた待機ループwhile (条件式) { cv_.wait(lk); }は、ビジーループの効率的な実装と解釈できます。つまりクラス利用者の視点からは、ビジーループ実装と条件変数実装とでFIFOキューの動作仕様に違いはなく、プログラム実行時の振る舞いだけが異なるものとなります。

// Step0(mt_queue0.cpp)
while (条件式) {
  lk.unlock();
  std::this_thread::yield();
  lk.lock();
}
// Step1(mt_queue1.cpp)
while (条件式) {
  cv_.wait(lk);
}

条件変数に対する待機cv_.wait(lk)は、内部的には“ロック一時解除lk.unlock()+条件変数へ通知があるまで自スレッドを休止+ロック再取得lk.lock()”処理を行います。ビジーループ版では他スレッドに実行機会のヒントを与える(yield())だけの処理が、条件変数版では論理的に意味のあるイベントが起きるまで、つまり明示的に条件変数への通知が行われるまで自スレッドを休止状態とし、CPUリソースを他スレッドへ明け渡す処理となります。*5

Step2: 実行時オーバーヘッドの削減

Step1では待機処理に条件変数を利用する事で、CPUリソースの浪費を抑えることができました。Step2では、より効率的な条件変数の利用について検討しましょう。ここでは下記4つを順番に適用していきます。

  1. イベント種別に応じた条件変数の分離
  2. 冗長な条件変数通知の削減
  3. 条件変数通知先スレッドの限定
  4. 条件変数待機を述語(Predicate)版に書き換え

Step2-1: 条件変数の分離

Step1では条件変数オブジェクトcv_を、「キュー内の要素数に何らかの変化があった」イベントに対応付けていました。この設計では、あらゆるキュー操作によって条件変数への通知が発生するため、必要のない冗長な通知処理が行われています。push操作は「キューが満杯でない」状態を/pop操作は「キューが空でない」状態を待機すれば良いので、両イベントに直接対応する条件変数に分離しましょう。新しい設計では1つのミューテックスmtx_に対して、2つの条件変数オブジェクトcv_nofull_, cv_noempty_を紐付けます。

// Step1(mt_queue1.cpp)
std::mutex mtx_;
std::condition_variable cv_;
// Step2-1
std::mutex mtx_;
std::condition_variable cv_nofull_;   // 満杯でなくなった
std::condition_variable cv_noempty_;  // 空キューでなくなった

条件変数の設計では、待機側でどんなデータ状態を満たすべきかに基づいて抽出することをお勧めします。

Step2-2: 冗長な条件変数通知の削減

push()実装の通知処理に着目すると、Step1では条件変数への通知を無条件に行っていました。本質的には、push操作では「キューが空でなくなった=少なくとも1個要素が存在する」イベントのみをpop操作へ通知すれば十分なため、通知の発火条件を限定することで無駄な処理を減らし、より効率的な実装とできます。同様にpop操作では「キューが満杯でなくなった=少なくとも1要素を追加できる」イベントのみを通知すれば十分です。

// Step1: push()メンバ関数
q_.push(data);
cv_.notify_all();  // 要素数変更を通知
// Step2-2: push()メンバ関数
bool do_signal = q_.empty();  // 操作前が空キューのときのみ
q_.push(data);
if (do_signal)
  cv_noempty_.notify_all();   // 「空キューでなくなった」通知

条件変数への通知処理は、待機側の条件式を満足するよう変更を行ったタイミングを抽出すると、実行時オーバーヘッドを最小化することができます。

Step2-3: 通知先スレッドの限定

Step1では条件変数への通知処理にnotify_all()(broadcast)を用いていました。空キューへの1回のpush操作によって、pop操作を待機中の全スレッドが起こされますが、実際に要素の取り出しに成功するのは1スレッドだけで、それ以外のpop操作要求スレッドは全て待機処理に再突入します。つまり、push操作が通知すべきpop操作待機スレッドは1つで十分であり、それ以上のスレッドへ通知が行われても冗長ということです。このようなケースではnotify_one()(signal)を利用することで、通知先スレッドを限定して実行効率の改善をはかることができます。

// Step1: push()メンバ関数
cv_.notify_all();  // 待機中の全スレッドへ通知
// Step2-3: push()メンバ関数
cv_noempty_.notify_one();  // pop()待機中の任意の1スレッドへ通知

このようなnotify_all()からnotify_one()への変更は、i)通知先が最大で1スレッド かつ ii)通知を受信するスレッドの待機条件を常に満たす場合 にのみ安全に行えます。本記事で設計したFIFOキューの場合、push操作からの通知を受信した任意のpop操作スレッドは、必ず待機ループを抜けてpop操作を完了すると保証できるため、notify_one()へと安全に変更できます。特に条件ii)を正しく考慮していないと、デッドロックといった並行性バグの原因となるため十分注意してください。*6

追記:notify_one()により生じるデッドロックについては、おまけ記事「条件変数とデッドロック・パズル(出題編)(解答編)」も参考にしてください。

Step2-4: 条件変数待機の書き換え

最後に、条件変数の待機処理wait()を述語(Predicate)をとる2引数オーバーロードに書き換えておきます。この変更は効率化とは無関係ですが、条件変数オブジェクトの名前(cv_nofull_, cv_noempty_)と、待機条件式(q_.size() < capacity, !q_.empty())の意味を一致させることができます。また後述Step3でFIFOキュー機能拡張を行うときに、待機条件の論理式を拡張しやすいというメリットもあります。

// Step1: push()メンバ関数
while (q_.size() == capacity) {
  cv_.wait(lk);
}
// Step1: pop()メンバ関数
while (q_.empty()) {
  cv_.wait(lk);
}
// Step2-4: push()メンバ関数
cv_nofull_.wait(lk, [&]{
  return (q_.size() < capacity);
});
// Step2-4: pop()メンバ関数
cv_noempty_.wait(lk, [&]{
  return !q_.empty();
});

Step2のまとめ

Step2での最終的なコードは次の通りです。[mt_queue2.cpp

// mt_queue2.cpp抜粋
class mt_queue {
  //...
  std::mutex mtx_;
  std::condition_variable cv_nofull_;   // 満杯でなくなった条件
  std::condition_variable cv_noempty_;  // 空キューでなくなった条件
public:
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{     // 「満杯でない」ことを待機
      return (q_.size() < capacity);
    });
    bool do_signal = q_.empty();
    q_.push(data);
    if (do_signal)
      cv_noempty_.notify_one();  // 「空キューでなくなった」通知
  }
  int pop() {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{   // 「空キューではない」ことを待機
      return !q_.empty();
    });
    bool do_signal = (q_.size() == capacity);
    int data = q_.front();
    q_.pop();
    if (do_signal)
      cv_nofull_.notify_one();  // 「満杯でなくなった」通知
    return data;
  }
};

さらなる改善策として、通知処理をミューテックスのロック解放後まで遅延させるという手法もあります。ただし、この変更によりコードが壊れるコーナーケースが存在すること、また処理系の実装品質が十分ならばあまり効果を期待できないため、本記事では適用しないこととします。詳細はこちらの記事を参考にしてください。

Step3: 提供機能の再考

Step2までで、性能面について十分考慮されたスレッドセーフ・FIFOキューを実装できました。Step3では機能面について改めて考えてみましょう。ここでは下記2点を検討します。

  1. データ列の終端処理
  2. 強制的な処理中断

Step3-1: データ列の終端処理

最初に設定したFIFOキュー仕様では、pushデータ列の終端処理について特別の考慮をしませんでした。いくぶん不恰好ですが、例えば-1を特殊な“データ終端マーカ”値とみなすことも出来るでしょう。

// mt_queueクラス利用コード
void producer_thread(mt_queue& mq) {
  for (int i = 1; i <= N; ++i)
    mq.push(i);
  mq.push(-1);  // データ終端を通知
}
void consumer_thread(mt_queue& mq) {
  int v;
  while ((v = mq.pop()) > 0)
    process_data(v);
}

生産者スレッド(producer_thread)と消費者スレッド(consumer_thread)が1つづつのSingle-Producer/Single-Consumerモデルならこの設計でも十分ですが、Multi-Producer/Multi-Consumerモデルでは面倒な問題が浮上します。例えば2生産者スレッド+3消費者スレッドで動作させた場合、FIFOキューには終端マーカが2個しかpushされないため、3番目の消費者スレッドはデータ終端到達を知ることが出来ません。生産者/消費者スレッド数が動的に変化する場合はもはやお手上げです。
結局、“終端マーカ”方式のようなクラス利用側コード設計に頼るのではなく、FIFOキュー自体に終端到達通知close()メンバ関数を追加するのが良いでしょう。これに伴って、push()は終端到達検知時に例外closed_queueを送出し、またpop()は終端到達状態を返すよう関数シグニチャを変更します。

class mt_queue {
  //...
  bool closed_ = false;  // 終端到達通知を保持
public:
  void close() {  // ★終端到達通知
    std::lock_guard<std::mutex> lk(mtx_);
    closed_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_;  // 条件追加
    });
    if (closed_)
      throw closed_queue();  // 例外送出
    //...
  }
  bool pop(int& data) {      // 関数シグニチャ変更
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{
      return !q_.empty() || (q_.empty() && closed_);  // 条件追加
    });
    if (q_.empty() && closed_)
      return false;          // 終端到達を返す
    data = q_.front();
    //...
    return true;             // 終端ではない
  }
};

pop()実装の待機条件では... || (q_.empty() && closed_)、つまり“キューが空でかつ終端通知がされているとき”に始めてデータ終端と判定すべきです。またclose()実装では、全ての条件変数に対してnotify_all()通知が必要になります。

Step3-2: 強制的な処理中断

終端到達通知close()によって通常のデータ終端処理を表現できるようになりましたが、ブロッキング中のpush/pop操作に対する処理中断要求abort()があるとより実用的になります。push()/pop()では中断要求検知時に例外abort_exceptionを送出するよう拡張します。なおclose()ブロッキング操作ではないため、中断すべき処理をもちません。*7

class mt_queue {
  //...
  bool aborted_ = false;  // 処理中断要求を保持
public:
  void abort() {  // ★処理中断要求
    std::lock_guard<std::mutex> lk(mtx_);
    aborted_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void push(int data) {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_ || aborted_;  // 条件追加
    });
    if (closed_)
      throw closed_queue();
    if (aborted_)
      throw abort_exception();  // 例外送出
    q_.push(data);
    //...
  }
  //...
};

push()実装の待機条件式(q_.size() < capacity) || closed_ || aborted_と、後続の条件分岐式とを比べてみてください。下記の対応関係を読み取れたでしょうか?1つの条件変数オブジェクトに複合的な条件を設定する場合、この構造が基本形となるはずです。

条件変数.wait(lk, [&]{
  return 条件A || 条件B || 条件C;
}):
if (条件A) { 処理A; }
if (条件B) { 処理B; }
if (条件C) { 処理C; }

ゴール!

本記事で実装したスレッドセーフ・FIFOキューの最終コードは次の通りです。[mt_queue3.cpp

// mt_queue3抜粋
struct closed_queue : std::exception {};
struct abort_exception : std::exception {};

class mt_queue {
  static const int capacity = 10;
  std::queue<int> q_;
  std::mutex mtx_;
  std::condition_variable cv_nofull_;
  std::condition_variable cv_noempty_;
  bool closed_ = false;
  bool aborted_ = false;
public:
  void push(int data)
  {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_nofull_.wait(lk, [&]{
      return (q_.size() < capacity) || closed_ || aborted_;
    });
    if (closed_)
      throw closed_queue();
    if (aborted_)
      throw abort_exception();
    bool do_signal = q_.empty();
    q_.push(data);
    if (do_signal)
      cv_noempty_.notify_one();
  }
  bool pop(int& data)
  {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_noempty_.wait(lk, [&]{
      return !q_.empty() || (q_.empty() && closed_) || aborted_;
    });
    if (q_.empty() && closed_)
      return false;
    if (aborted_)
      throw abort_exception();
    bool do_signal = (q_.size() == capacity);
    data = q_.front();
    q_.pop();
    if (do_signal)
      cv_nofull_.notify_one();
    return true;
  }
  void close()
  {
    std::lock_guard<std::mutex> lk(mtx_);
    closed_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
  void abort()
  {
    std::lock_guard<std::mutex> lk(mtx_);
    aborted_ = true;
    cv_nofull_.notify_all();
    cv_noempty_.notify_all();
  }
};

これでもう条件変数は怖くありません…よね?

*1:スレッド間での通知/待機を行う同期プリミティブとしては、A)「セマフォ(semaphore)」に代表されるイベント変数方式、B)ミューテックス+条件変数ペアによる方式があり、これらを提供する/しないはライブラリ設計ポリシーに依存します。ただし、比較的新しいライブラリ仕様では方式B)条件変数のみを提供する事が多いようです。例えばBoost.Threadライブラリではその設計論拠に基づき、セマフォ同期プリミティブを提供しません。Boost.Threadをベースに標準化されたC++11標準ライブラリも、同様に条件変数のみを提供します。なお、セマフォを用いて条件変数を実装する/条件変数を用いてセマフォを実装することが可能なため、両同期プリミティブは本質的には互換性があるといえます。

*2:スレッド間の排他制御は2値セマフォ(binary semapohore)を用いても実現可能ですが、一般的にミューテックスではスレッド間“排他”処理という目的に合わせて、スレッドによる“ロックの所有”という概念が導入されます。このため、あるスレッドがミューテックスのロック処理(所有権を獲得)を行った場合、必ず同じスレッドでアンロック処理(ロック所有を解放)を行う必要があります。一方でセマフォには所有権という概念は無く、制約のあるミューテックスよりも便利に思えるかもしれません。しかし、特にマルチスレッド処理プログラミングにおいては、バグ検知可能性や実行時効率などの観点から、セマフォのように自由度の高い原始的な機構よりも、ミューテックスのように目的に特化した専用機構を用いるべきです。

*3:ミューテックスの不適切な利用の一例として、“ロック獲得のFIFO動作を期待したスレッド・スケジューリング”が挙げられます。これは、複数スレッドから同時にロック獲得要求を行い、ロック獲得成功順序がFIFO動作であると仮定し、各スレッドが順次実行されることを期待した処理を指します。通常、ミューテックスのロック獲得はFIFO順を保証しないため(unfair)、このような利用は適切ではありません。

*4:オブジェクト破棄処理をスレッドセーフとするには大きな制限事項を伴うため、通常、スレッドセーフの議論からはクラスのデストラクタを除外します。つまりオブジェクト破棄時には、他のあらゆるメンバ関数と同時に呼び出さないことを、クラス利用側が保証すべきです。

*5:条件変数の動作仕様では“Spurious Wakeup”が起こりうると明記されており、誰も通知を行っていないのに待機が解除されることがあります。本記事のようにビジーループを起点に考えた場合は、既にループ構造+条件変数の待機処理となっており、Spurious Wakeupも考慮済みとなるため、本文中では特に言及しません。詳細は条件変数とspurious wakeupを参照ください。

*6:具体例:片方は奇数のみを/もう一方は偶数のみを取り出す選択的pop操作に対して、1)pop要求で2スレッドとも待機→2)偶数値をpushし任意1スレッドへ通知→3)奇数待機スレッドが通知受信して再待機→4)偶数待機スレッドは休眠状態のまま。

*7:close処理の内部実装では、ロック獲得のために呼び出しスレッドがブロッキングされる場合があります。この排他制御FIFOキューのデータ一貫性を維持するため機構であり、いずれのスレッドも有限ステップ内にロック獲得することが保証できます。このため、クラス利用者視点ではcloseメンバ関数はノンブロッキング操作とみなせます。

Boost.勉強会 #14に参加しました

C++

2014/3/1に開催されたイベント Boost.勉強会 #14 東京 にて、“新しい並列for構文のご提案”というタイトルで30分ほど話す機会をいただきました。(1年7ヶ月ぶり2回目

感想とか

今回作ったスライド資料では、現行の並列化技術10種類とC++1y ParallelTSを広く浅く紹介というテーマで、前回よりも枚数を増やし進行テンポを速くしてみました。また前回の反省点として、概念と仕様のみ紹介だと理解されにくいかなと思ったこともあり、今回は導入部をシナリオ的にし(1/3)+“今日から使える”技術の紹介(1/3)+将来のC++1y動向の紹介(1/3)という構成にしています。Twitterでの皆様の反応を後から眺めてみると、思ったよりC++1y ParallelTSが注目されていたようでした(並列処理はTransactional Memoryよりも身近で分かり易いという側面はあるでしょうけど)。当日は少しぼやけてしまった感がありますが、「並列処理の"仕組み"を自分で書こうとしないで!*1」「並列化技術はいろいろあるから、適材適所で選んでね!*2」という主張でした。

並列処理は目に見える効果が大きく面白く感じられる反面、正しく動作するコード記述や適切な速度性能を引き出すのは一筋縄ではいきません。また昨今のハードウェア進化の方向性を鑑みるに、ソフトウェア側での並行処理・並列処理への対応は避けられそうもありません。今回紹介した並列化技術は“処理を並列実行する枠組み”部分を提供するため、この点ではプログラマのコーディング負担を下げてくれるはずです。ぜひ並列処理プログラミングの世界に足を踏み入れてみてください。


P.S. 勉強会の終了後に行われたじゃんけん大会で幸運にも勝ち残り、書籍版プログラミングの魔導書 〜Programmers' Grimoire〜 Vol.3 "Parallel, Concurrent, and Distributed Programming"を頂いてしまいました(もうおひと方と私の2冊)。@cpp_akiraさん、ありがとうございます!

*1:安易に、スレッドを自前で作り制御するような並列処理コードを書くべきでないと考えます。特殊な事情がある場合はこの限りではありませんが、安定性/スケーラビリティ/拡張性/保守性などの観点から、適切な実装手段を選択すべきです。(よくある標準ライブラリvs自前コードの比較ですね。)

*2:今回の文脈では 並列化=実行速度の高速化(最適化) のため、良い結果が得られなければ特定技術にこだわるのは無意味です。また、単一の並列化技術だけでは十分でないケースも多々ありますので、複数の並列化技術を組み合わせることも検討してみてください。

gistにソースコードを放っておいたらOSSプロジェクトで活用されていた件

C

タイトル通り。

プログラミング言語Cの最新規格C11で採用されたスレッドサポートのエミュレーションライブラリをgistに放置していたら、汎用OpenGL実装The Mesa 3D Graphics Libraryに取り込まれました(2014年2月現在のGit版として)。

2014-05-07追記:MesaLib-10.1.0からinclude/c11以下にとりこまれたようです。

対応プラットフォームが多岐にわたるMesa 3Dでは、その差異を吸収するスレッドサポート実装をもっていましたが、4つのサブモジュールでそれぞれ独立に行われていたそうです。つまり、4種類のエミュレーション用コードがばらばらに存在する状態でした。そこで、C11標準ライブラリのAPI仕様に則りかつWindowsPOSIX環境に対応していたgistのコードが拾われて、プロジェクト内の重複実装を整理する目的で採用されたようです。

ライブラリ内部実装としては、Pthreadの薄っぺらいラッパとBoost.InterprocessライブラリC++言語)からC言語への移植です。作成動機はC11標準スレッドサポート機能の調査と、条件変数プリミティブの実装調査でした。

(コードをBoostライセンスで公開していたのもあってか、Phoronix記事ではBoostライブラリの一部と勘違いされている?)

ま、そういうOSS貢献(?)の形もあったという事で一つ。

スレッドセーフという幻想と現実

C++

この記事はC++ Advent Calendar 2013の15日目にエントリしています。
内容はC++標準ライブラリとスレッドセーフに関する解説になります。

f:id:yohhoy:20111211120104j:plain
flickr / rennasverden
もくじ

  1. What's スレッドセーフ?
    1. スレッドセーフという幻想
    2. 基本型とデータ競合
    3. C++標準ライブラリとデータ競合
    4. C++標準ライブラリ:シーケンスコンテナ編
    5. C++標準ライブラリ:連想コンテナ編
  2. スレッドセーフ RELOADED
    1. 基本的なスレッドセーフ保証
    2. std::shared_ptr<T>
    3. std::rand()
    4. std::cout

(本文のみ約9000字)

はじめに

マルチスレッド対応の点では他言語に遅れを取っていたプログラミング言語C++ですが、C++11ではようやく標準ライブラリにスレッドサポートが追加されました。C++11スレッドサポートではスレッドクラスstd::threadをはじめとし、ミューテックスstd::mutexや条件変数std::condition_variableなどの基本的な同期機構、Future/Promiseパターンを実現するstd::future, std::promise、少しマニアックなところではアトミック変数std::atomicなどがC++標準ライブラリに追加されました。Happy Multithreading Programming!

という風に、C++11スレッドサポートの文脈では新規クラス追加ばかりが注目されています。このような華やかな表舞台の裏側では、以前からあるstd::stringstd::vectorといったクラス群に対して、スレッドサポートに関連する重要なルールが明確化されたことは知っていますか?マルチスレッドプログラム中でC++標準ライブラリを利用するとき、それらのスレッドセーフ性(thread safety)*1について理解し、適切に使えているでしょうか?

本記事では、プログラミング言語C++におけるスレッドセーフの観点から、C++11スレッドサポート追加クラス以外C++標準ライブラリをいくつか紹介したいと思います。その中でも、たまに論争ネタになっているstd::shared_ptrstd::coutのスレッドセーフ性についても説明を加えていきたいと思います。

1. What's スレッドセーフ?

複数スレッドを扱うプログラミングについて学び始めると、必ず「スレッドセーフ(thread safe)」という概念が出てくると思います。曰く、

  • △△ライブラリはスレッドセーフだから、マルチスレッドプログラム中でも安全に使える。
  • クラス○○はスレッドセーフじゃないから、スレッドと一緒には使えない。

どうやら“スレッドセーフなC++ライブラリ=マルチスレッド対応”という雰囲気のようです。スレッドセーフなんて簡単ですね!

…でも、本当にそんなに単純な話でしょうか。次の「スレッドセーフ」に関する質問に答えられますか?(Q&Aサイトでよく見かける質問の変形です)

  • Q1. std::map<K,V>クラスはスレッドセーフですか?
  • Q2. std::vector<T>クラスはスレッドセーフですか?
  • Q3. std::stringクラスはスレッドセーフですか?
  • Q4. 基本型intはスレッドセーフですか?
  • Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか?

これらに回答できるなら、プログラミング言語C++の文脈での「スレッドセーフ」という概念について、ちゃんと理解していると言っても差し支えないでしょう。本記事の前半では、逆順にてそれぞれの質問に答えていきたいと思います。

1.1. スレッドセーフという幻想

Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか?

いきなり出鼻をくじくようですが、プログラミング言語C++の言語仕様としては「スレッドセーフ」という用語は直接定義されていません。ただし、スレッドセーフを考える上で重要な用語「データ競合(data race)」は、C++言語仕様の一部として厳密に定義されます。C++11におけるデータ競合とは、次の3条件を全て満たすときに発生します。*2

  • (1) 同一メモリ位置に対するアクセスにおいて、
  • (2) 少なくとも一方が変更(modify)操作であり、
  • (3) 異なるスレッド上から同時に行われるとき。

f:id:yohhoy:20131211204648j:plain

そして、C++言語仕様では「プログラム中で何らかのデータ競合が発生した場合には、未定義の動作(undefined behavior)を引き起こす」と明言しています。つまり、ひとつでもデータ競合を含むマルチスレッドプログラムの動作結果について、C++言語仕様としては何も保証しないことを意味します。ここでの“何も保証しない”とは、本当に何も保証されていことに注意してください。例えば、データ競合を含むプログラムは偶然正しく動くかもしれないし、運悪く期待する結果とならないかもしれないし、はたまたプログラム実行中に突然異常終了するかもしれないという意味です。*3

残念ながら原典をあたっても「スレッドセーフ」についての明確な答えは得られませんでしたが、少なくともデータ競合を含まないプログラムとなっていればよい事は分かりました。

Q5. そもそもC++言語での「スレッドセーフ」は何を意味しますか?
A5. 厳密には「スレッドセーフ」は定義されない。一方、妥当なC++プログラムはデータ競合を一切含まないことが求められる。

と、このままでは話が終わってしまいますので、厳密なC++言語仕様から少し離れてみたいと思います。ある対象の「スレッドセーフ」について言及するときは、その利用者視点から議論するのが一般的と考えられます。本記事でもそれにならい“利用側コードからどのように扱えばデータ競合が生じないか”、より具体的には“いつ排他制御すれば良いのか”という観点から、基本型やクラスの「スレッドセーフ」の議論を続けていきます。

1.2. 基本型とデータ競合

Q4. 基本型intはスレッドセーフですか?

charintなどの基本型*4は、C++プログラムを構成する最も原始的なデータ構造です。このような基本型変数は、一定サイズのメモリ領域にマッピングされます(例:sizeof(int) == 4な環境ではint型変数は連続した4バイトメモリ位置を占める)。つまり、基本型に関するスレッドセーフの議論は、前述「データ競合」の定義から単純に読み替えが可能です。

ところで「データ競合」は3つの発生要因から構成されますが、逆に言うと、これらの要因のうち1つでも排除できれば回避できます。

  • (1') 異なる変数に対する同時アクセスは、データ競合とはなりません。
  • (2') 同一変数に対して同時読み込み(read)操作のみならば、データ競合とはなりません。
  • (3') 同一変数に対するアクセスが同時でなければ、データ競合とはなりません。

(1')はアクセスする変数自体が別々となるため、最も直感的に理解できるかと思います。(以降のコード例では、関数th1(), th2()等は異なるスレッドからそれぞれ同時に呼び出されるとします。)

// 異なる変数に対する同時アクセス
int x, y;
void th1() {
  x = 1;  // OK
}
void th2() {
  y = 2;  // OK
}

また(3')はマルチスレッドプログラムの定番、ミューテックスstd::mutexなどを用いた排他制御により同一変数へのアクセスが同時に生じないよう制御します。これも、マルチスレッドプログラミングの基本ですね。

// 同一変数に対するアクセスが同時でない
std::mutex mtx;
int x;
void th1() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  x = 1;  // OK
}
void th2() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  x = 2;  // OK
}

一番馴染みが薄いのは(2')でしょうか?C++における「データ競合」の定義に従うと、同一変数に対する読み込み操作のみであれば安全に同時アクセスが可能なのです(変数x)。ただし、1つでも変更操作が発生するケース(変数y)では、データ競合を回避するために排他制御が必要となることに注意してください。

// 同一変数に対して同時読み込み操作のみ
int x = 0;
void th1() {
  int r1 = x; // OK
}
void th2() {
  int r2 = x; // OK
}
// 同一変数に対して片方が変更操作
int y = 2;
void th1() {
  int r2 = y; // NG: データ競合
}
void th2() {
  y = 42;     // NG: データ競合
}

利用者視点で考えると、上記ルール“全てが読み込み操作ならば排他制御は不要である”というのが、C++基本型が提供するスレッドセーフ保証と解釈できます。

Q4. 基本型intはスレッドセーフですか?
A4. 「同時アクセスが全て読み込み操作であれば安全」というスレッドセーフ性レベルが保証される。

1.3. C++標準ライブラリとデータ競合

Q3. std::stringクラスはスレッドセーフですか?

さて基本型のスレッドセーフ保証は分かりましたが、C++標準ライブラリ提供のクラスではどうでしょう。例えば文字列型std::stringクラスでは、明らかにprivateなメンバ変数として複数の基本型(文字列ポインタやバッファ長など)を内包しているはずです。一方でC++11以前のプログラム動作との互換性を考慮すると、クラス内部実装にミューテックスなど排他制御の仕組みがこっそり追加されたとは考えにくいですね。そうなると、マルチスレッドプログラムからこれらのクラスを安全に利用するには、利用者側にて全てのメンバ関数呼び出しを排他制御しないとダメなのでしょうか…?

std::string s = "hello";
void th1()
{
  // ここに排他制御は必要?
  bool b = s.empty();
}
void th2()
{
  // ここに排他制御は必要?
  char& c = s.at(0);
}

実は、C++11における重要な(そして地味な)スレッドサポートとして、C++標準ライブラリ提供クラスのデータ競合に関する基本ルールが明確化されました。

  • クラスオブジェクトのconstメンバ関数呼び出しは、オブジェクトに対する読み込み操作とみなす。
  • クラスオブジェクトのconstメンバ関数呼び出しは、オブジェクトに対する変更操作とみなす。(一部例外事項あり)

このルールはC++標準ライブラリ提供のクラスに対して適用される、最低限かつ基本的なスレッドセーフ保証となっています。また追加的な例外事項として、begin, endatなどの一部の非constメンバ関数ではオブジェクト自身の内部状態を変更しないため、これらもデータ競合に関してはconstメンバ関数相当(=読み込み操作)とみなします。

std::string s = "hello";
void th1()
{
  if ( !s.empty() )             // OK: constメンバ関数呼び出し
    printf("%s\n", s.c_str());  // OK: constメンバ関数呼び出し
}
void th2()
{
  size_t n = s.length();  // OK: constメンバ関数呼び出し
  char& c = s.at(0);      // OK: constメンバ関数相当呼び出し
}

つまり、データ競合を回避する3つの方法は次のように拡張できます。

  • (1') 異なるオブジェクトに対する同時アクセス/メンバ関数呼び出しは、データ競合とはなりません。
  • (2') 同一オブジェクトに対して同時読み込み操作=constメンバ関数相当呼び出しのみならば、データ競合とはなりません。
  • (3') 同一オブジェクトに対するアクセス/メンバ関数呼び出しが同時でなければ、データ競合とはなりません。

こちらも利用者視点の表現では、上記ルール“全てconstメンバ関数相当呼び出しならば排他制御は不要である”というのが、C++標準ライブラリが提供するスレッドセーフ保証と解釈できます。

Q3. std::stringクラスはスレッドセーフですか?
Q3. 「同時アクセスが全て読み込み操作(constメンバ関数相当呼び出し)であれば安全」というスレッドセーフ性レベルが保証される。

1.4. C++標準ライブラリ:シーケンスコンテナ編

Q2. std::vector<T>クラスはスレッドセーフですか?

他の型を内包するシーケンスコンテナ(sequence containers)クラスはどうでしょうか(説明のためT=intとする)。コンテナクラスのデータ競合を考える場合、コンテナオブジェクト(vector<int>)と格納された各要素(int)は異なるオブジェクトであると認識することが重要です。

コンテナ要素へアクセスする最も一般的な方式はvector<T>::operator[]メンバ関数呼び出しでしょう。このoperator[]にはconst・非constメンバ関数の2つが存在しますが、前掲の「基本的なスレッドセーフ保証」により両者ともconstメンバ関数(相当)として扱われます。このため、コンテナオブジェクトの他constメンバ関数と同時に呼び出してもデータ競合とはなりません。

std::vector<int> v = { 1, 2, 3, 4, 5 };
void th1()
{
  size_t n = v.size();  // OK: v.size()は、vに対する読み込み操作
}
void th2()
{
  v[1] *= 2;  // OK: v[1]つまりv.operator[](1)は、vに対する読み込み操作
  // v[1] *= 2は、vの2番目要素に対する変更操作
}

operator[]や他メンバ関数イテレータ経由やatなど)を介して得られた各コンテナ要素オブジェクトへのアクセスについては、既に説明してきたデータ競合の考え方と同じになります。つまり、異なるコンテナ要素オブジェクトへのアクセスであれば、同時に変更操作を行ってもデータ競合とはなりません。((このコンテナ要素アクセスに関するデータ競合に関して、1つだけ例外ケースが存在します。特殊化されたstd::vector<bool>だけは、異なる要素へのアクセスであってもデータ競合が発生する可能性があります。同テンプレート特殊化版の仕様が要請するメモリ空間最適化のために、異なるboolオブジェクトが“同一メモリ位置(バイト)”の異なるビットとして配置される可能性があるためです。))

std::vector<int> v = { 1, 2, 3, 4, 5 };
void th1()
{
  // v[1]つまりv.operator[](1)は、vに対する読み込み操作
  ++v[1];    // OK: vの2番目要素に対する変更操作
}
void th2()
{
  // v[3]つまりv.operator[](3)は、vに対する読み込み操作
  v[3] = 0;  // OK: vの4番目要素に対する変更操作
}

f:id:yohhoy:20131211204717j:plain

Q2. std::vector<T>クラスはスレッドセーフですか?
A2. コンテナ自身std::vector<T>および各要素Tに対して、個別に「同時アクセスが全て読み込み操作(constメンバ関数相当呼び出し)であれば安全」というスレッドセーフ性レベルが保証される。

1.5. C++標準ライブラリ:連想コンテナ編

Q1. std::map<K,V>クラスはスレッドセーフですか?

最後に、より複雑な連想コンテナ(associative containers)クラスをみていきましょう(説明のためK=int, V=std::stringとする)。既に説明してきた通り、コンテナオブジェクト(map<int,string>)と格納されるキー(int)-値(string)をそれぞれ異なるオブジェクトと考える必要があります。これらのクラス/型はそれぞれで基本的なスレッドセーフ保証を提供しますから、もう説明しなくても分かりますよね。

std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  size_t n = m.size();  // OK: m.size()は、mに対する読み込み操作
}
void th2()
{
  m.at(2) += "x";  // OK: m.at(2)は、mに対する読み込み操作
  // m.at(2) += "x"は、mの要素{2,"b"}の値に対する変更操作
}

ところで、上記コードでは意図的にmap<int,string>::operator[]の利用を避けました。実は“連想コンテナクラスのoperator[]メンバ関数は変更操作”と解釈するため、下記コードへ単純に置き換えるとデータ競合を引き起こしてしまうのです((連想コンテナstd::map, std::unordered_mapでは非constoperator[]メンバ関数のみが提供され、そもそもconstoperator[]メンバ関数は存在しません。))。少々不便に見えるかもしれませんが、このメンバ関数は“与えられたキー値が存在しなければ新要素を追加する”という動作仕様となっており、これはコンテナ自身の内部状態を変更しないことには実現できないからです。

std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  size_t n = m.size();  // NG: データ競合
}
void th2()
{
  m[2] += "x";  // NG: データ競合
  // m[2]つまりm.operator[](2)は、mに対する変更操作
}

つまりmap<int,string>::operator[]を安全に使うには、ミューテックスによる排他制御が必要となるのです。

std::mutex mtx;
std::map<int,std::string> m = { {1,"a"}, {2,"b"} };
void th1()
{
  std::lock_guard<decltype(mtx)> lk(mtx);
  size_t n = m.size();  // OK
}
void th2()
{
  std::lock_guard<decltype(mtx)> lk(mtx);
  m[2] += "x";  // OK
}

C++標準ライブラリでは、連想コンテナstd::map<K,V>, std::unordered_map<K,V>の2つで本ルールが当てはまります。

Q1. std::map<K,V>クラスはスレッドセーフですか?
A1. コンテナ自身std::map<K,V>および各要素キーKと値Vに対して、別個に「同時アクセスが全て読み込み操作(constメンバ関数相当呼び出し)であれば安全」というスレッドセーフ性レベルが保証される。ただしoperator[]はコンテナに対する変更操作であることに注意。

2. スレッドセーフ RELOADED

いかがでしょう。5つの質問には答えられましたか?ここでは、改めてC++標準ライブラリの基本的なスレッドセーフ保証について整理し、またこの考え方が特段目新しいものでないことを紹介します。さらに、しばしばスレッドセーフ論争を引き起こすクラスや関数をいくつか挙げて、追加的な解説を行いたいと思います。

2.1. 基本的なスレッドセーフ保証

前節の繰り返しとなりますが、C++言語仕様およびC++標準ライブラリでは次の「基本的なスレッドセーフ保証」を提供します。これは、C++標準ライブラリ提供のクラス/関数が提供する、最低限のスレッドセーフ性の保証となっています。ちなみに、ここで“最低限の”と表現しているのは、C++標準ライブラリの一部クラスではもっと強いスレッドセーフ保証(=同時に変更操作を行っても安全)を提供するためです。

  • 同一オブジェクトにする同時アクセスが全て読み込み操作であれば、排他制御なしでもデータ競合を引き起こさない。
  • C++標準ライブラリ提供のクラスでは、constメンバ関数(およびオブジェクトを変更しない非constメンバ関数)呼び出しは読み込み操作とみなす。
  • これ以外のケース(少なくとも片方が変更操作)の場合、同一オブジェクトへの同時アクセスを排他制御する必要がある。

さて、この「基本的なスレッドセーフ保証」ですが、実はC++11で新たに作られた考え方ではありません。C++98以前から存在しており、また現C++標準ライブラリの源流でもあるSGI STLライブラリでも、同等のスレッドセーフ保証を提供すると明言していました。*5

The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe. If multiple threads access a single container, and at least one thread may potentially write, then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.

Standard Template Library Programmer's Guide, Thread-safety for SGI STL

さらにC言語の時代にまでさかのぼると、POSIXシステムにおいても同等のスレッドセーフ保証が明言されていました。(こちらは対象がC言語のためconstメンバ関数は存在しません。)

(略)They usually cannot determine when memory operation order is important and generate the special ordering instructions. Instead, they rely on the programmer to use synchronization primitives correctly to ensure that modifications to a location in memory are ordered with respect to modifications and/or access to the same location in other threads. Access to read-only data need not be synchronized. The resulting program is said to be data race-free.

The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition

2.2. std::shared_ptr<T>

C++11では所有権共有スマートポインタstd::shared_ptr<T>C++標準ライブラリ入りしました。ここでは同一intオブジェクトを参照する2つのスマートポインタが存在し、同時にp1, p2を操作するケースを考えてみます(説明のためT=intとする)。各スレッド上での操作により参照カウント更新が同時に行われるため、これまでの延長線上で考えると排他制御が必要に思えます。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  // ここに排他制御は必要?
  p1.reset();   // 参照カウントを-1
}
void th2() {
  // ここに排他制御は必要?
  auto q = p2;  // 参照カウントを+1
}

一方で、局所的な観点ではp1p2はあくまで“異なるstd::shared_ptr<int>オブジェクト”です。仮に両スマートポインタが異なるintオブジェクト/異なる参照カウントを参照するなら、C++標準ライブラリの基本的なスレッドセーフ保証より明らかに排他制御は不要です。とはいえ、その参照先が同一か否かで必要有無が変わるようでは、結局は保守的に排他制御をせざるを得なくなります。

std::shared_ptr<int> p1 = /* ??? */;
std::shared_ptr<int> p2 = /* ??? */;
// p1とp2は同一オブジェクトor異なるオブジェクトを参照
void th1() {
  // ここに排他制御は必要?
  p1.reset();   // 参照カウントを-1
}
void th2() {
  // ここに排他制御は必要?
  auto q = p2;  // 参照カウントを+1
}

この問題に対して、C++標準ライブラリでは「異なるstd::shared_ptrオブジェクトに対するメンバ関数呼び出しは、その参照先に関わらずデータ競合を引き起こさない」と明確に保証しています。つまり、利用者からは見えないオブジェクト内部状態を気にすることなく、基本的なスレッドセーフ保証の通り“異なるオブジェクトへの同時アクセスは安全”と扱ってして良いのです。これは裏を返すと、スマートポインタstd::shared_ptrの内部実装では、参照カウント更新はatomic変数操作(または排他制御あり変数更新)にて行われることを意味します。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  p1.reset();   // OK: 参照カウント-1は安全に行われる
}
void th2() {
  auto q = p2;  // OK: 参照カウント+1は安全に行われる
}

f:id:yohhoy:20131211204745j:plain

ただし、両スマートポインタp1, p2が同一オブジェクトを参照している状況で、shared_ptr<int>::operator*メンバ関数を介して得られた参照先intオブジェクトにアクセスする時には、intに対する基本的なスレッドセーフ保証に留意する必要があります。

std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  *p1 += 1;     // NG: 参照先においてデータ競合
  // 参照先オブジェクトに対する変更操作
}
void th2() {
  int r = *p2;  // NG: 参照先においてデータ競合
  // 参照先オブジェクトに対する読み込み操作
}
std::shared_ptr<int> p1 = std::make_shared(42);
std::shared_ptr<int> p2 = p1;
// p1とp2は同一オブジェクトを参照
void th1() {
  int r = *p1;  // OK: 参照先オブジェクトに対する読み込み操作
}
void th2() {
  int r = *p2;  // OK: 参照先オブジェクトに対する読み込み操作
}

2.3. std::rand()

続いて、C言語時代の標準ライブラリから引きついだ乱数生成関数std::rand()を取り上げてみましょう((例示コードでは整数0~9を得るために剰余演算(%)を利用していますが、この実装では望ましい一様分布とはなりません。定数RAND_MAXを利用すればもう少しまともな一様分布が得られますが、C++11以降では後述の乱数ライブラリ<random>を利用すべきです。))。C++11では、この関数を複数スレッドから同時に呼び出した場合、データ競合を引き起こすか否かは処理系定義(implementation-defined)と定めています。つまり、コンパイラやライブラリに任せるとしか言っていないのです。

void th1() {
  // 処理系によっては排他制御が必要
  int r1 = std::rand() % 10;
}
void th2() {
  // 処理系によっては排他制御が必要
  int r2 = std::rand() % 10;
}

(スレッドセーフの議論に関わらず)C++11以降では、C++標準ライブラリに追加された乱数ライブラリを用いるべきでしょう。この新しい乱数ライブラリ<random>であれば乱数生成器をスレッド別に持つことができるため、データ競合について悩む必要が無くなります。((例示コードでは乱数生成エンジンstd::mt19937を引数なしで構築しているため、常に同一の疑似乱数列が得られることに注意してください。実行のたびに異なる乱数列が必要な場合、std::random_deviceなどで適当なシード値を与える必要があります。))

void th1() {
  std::mt19937 rng;
  std::uniform_int_distribution<int> dist(0, 9);
  int r1 = dist(rng);  // OK
}
void th2() {
  std::mt19937 rng;
  std::uniform_int_distribution<int> dist(0, 9);
  int r2 = dist(rng);  // OK
}

もちろん、下記コードのように単一の乱数生成器を複数スレッド間で共有し、アクセス時には排他制御を行うという実装でもOKです。ただし、この設計では“(a)高頻度で乱数生成を行う状況で、排他制御により他スレッドが停止するためプログラム処理速度に悪影響を与える”、“(b)各スレッドで取得する乱数列は実行時(OS)スレッドスケジューリングに依存するため、再現性のある乱数列を生成できない”という問題が生じます。最終的にはアプリケーションの目的によりますが、一般にはスレッド別に乱数生成器を保持する設計の方が好ましいと思います。

std::mutex mtx;
std::mt19937 rng;
std::uniform_int_distribution<int> dist(0, 9);
// 単一の乱数生成器を排他制御ありで利用
int next_rand() {
  std::lock_guard<decltype(mtx)> lk(mtx);
  return dist(rng);
}

void th1() {
  int r1 = next_rand();  // OK
}
void th2() {
  int r2 = next_rand();  // OK
}

今回はrand()関数をとりあげましたが、C++標準ライブラリに取り込まれたC標準ライブラリの関数のうち、strtok(), localtime(), setlocale()などの一部関数は複数スレッドから同時に呼び出すとデータ競合となる可能性があります。できるだけC++標準ライブラリを使いましょう!

2.4. std::cout

最後に、おそらく一番論争を引き起こすであろう、標準出力ストリームstd::coutのスレッドセーフ保証について整理します。C++標準ライブラリの基本的なスレッドセーフ保証に照らして考えると、各スレッドから同時にstd::coutへ出力するとき排他制御は必要でしょうか?

void th1() {
  // ここに排他制御は必要?
  std::cout << "I'm #1 thread." << std::endl;
}
void th2() {
  // ここに排他制御は必要?
  std::cout << "Hello, Multithreading World!" << std::endl;
}

この質問に対する回答は、2段階で考える必要があるでしょう。まず、C++11の標準ライブラリ仕様では「標準入出力ストリームオブジェクトに対する入力/出力操作は、排他制御を行わなくてもデータ競合を引き起こさない」と定めています。という訳で、上記コードはデータ競合なしに正常動作することが保証されています。つまり、標準入出力ストリームオブジェクトstd::cin, std::cout, std::cerr, std::clog(と対応するwide文字版)では、C++標準ライブラリの基本的なスレッドセーフ保証よりも強いスレッドセーフ性を提供しています。((このような強いスレッドセーフ保証が行われるのは、あくまで標準入出力ストリームオブジェクトのみです。std::fstreamstd::stringstreamでは、基本的なスレッドセーフ保証しか提供しないのでご注意を。))

ただし、C++標準ライブラリでは「データ競合は起こさないが、複数スレッドからの出力が混ざる(interleave)可能性がある」とも言及しています。例えば標準出力には次のような文字列が出力されるかもしれませんが、これもプログラムが正常動作した結果なのです。

I'm #1
Hello,thread Multit
hreading World!

一般的には前掲コードを書いたプログラマが期待するのは、下記いずれかのように“行単位で出力されること”と考えられます。結局のところ標準出力ストリームstd::coutであっても、実用上は排他制御を行わない限りはまともな出力結果が得られないのです。

I'm #1 thread.
Hello, Multithreading World!
Hello, Multithreading World!
I'm #1 thread.

まとめ

これで今回の解説はおしまいです。最後にもう一度、本記事での要点をまとめてみましょう。

  • C++11における基本型とC++標準ライブラリ提供クラスでは、少なくとも下記「基本的なスレッドセーフ保証」を提供します。
  • 単一オブジェクトに対する同時アクセスが、全て“読み込み操作”=“const関数相当呼び出し”のみであれば、複数スレッド間での排他制御は不要です。
  • このルールは、複数オブジェクト間で内部共有されるデータがあったとしても維持されます。(例:std::shared_ptr
  • std::cout等の標準入出力ストリームを使う場合も、複数スレッド間での排他制御が必要になります。

I Hope You Have A Nice Multithreading C++ Programming Life!!

C++ Advent Calendar 2013 は 16日目 disktnk さんの記事へと続きます。
f:id:yohhoy:20131215154349j:plain
flickr / applebymatt

参考記事

本文中では次の記事をもとにした解説を行いました。より詳細についてはそれぞれの記事もご参考にください。

はしがき:本文中でゆるふわ手書き画像を使っていますが、当初はInkscapeで描こうと思いつつ心が折れた結果です。字が汚いことを横に置けば、手書きも悪くないですね!

*1:本記事中では thread safe=スレッドセーフ との対比から thread safety=スレッドセーフ性 と記述します。なお、後者の対訳語としては「スレッド安全性」の方が一般的かと思います。

*2:厳密にはもう1つの条件“(0) 対象がatomic変数でないとき”が追加されます。これを裏返すと、atomic変数に対するアクセスはデータ競合を引き起こさないことを意味します。本文中ではatomicでない通常の変数のみを対象とするため、この条件については言及していません。

*3:「データ競合」によるプログラム異常終了というのは直感に反するかもしれませんが、これは「未定義の動作」の結果としてあり得る動作の一つです。ちなみに、マルチスレッド分野でC++言語に大きな影響を与えたJava言語では、もう少し穏やかな定義「データ競合が生じると何らかの状態になる(が異常停止はしない)」となっています。

*4:組込み型やプリミティブ型と呼ばれることもあります。なお、C++言語仕様での正式名称はスカラ型(scalar type)です。

*5:id:y-hamigakiさんのHamigaki C++ライブラリでは、SGI STLより明快にスレッドセーフ保証について記載しています。