[このドキュメントは SMP Primer for Android を翻訳したものです。]
Android 3.0 およびそれ以降のプラットフォームバージョンは、 マルチプロセッサアーキテクチャをサポートするために最適化されています。 このドキュメントでは C、 C++ および Java プログラミング言語 (以降、簡潔に済ませるため単に Java と呼びます) で対称型マルチプロセッサシステム向けのコードを書く際に起き得る問題を紹介しています。 これはこの問題に対して完全に論じているわけではなく、 Android アプリ開発者のための入門書としての役割を意図しています。 主に ARM CPU アーキテクチャに焦点を当てています。
もし急いでいるのであれば、 理論 の節を飛ばして直接 実践 に行っても構いませんが、推奨されません。
SMP は “Symmetric Multi-Processor” (対称型マルチプロセッサ) の略です。 2 つ以上の同等な CPU コアがメインメモリへのアクセスを共有しているような設計を指します。 数年前まで、 Android デバイスは、すべて UP (Uni-Processor; シングルプロセッサ) でした。
ほとんどの (すべてではない) Android デバイスは、複数の CPU を搭載していますが、 通常、そのうちのひとつだけがアプリケーションを実行するために使われ、 残りはデバイスのハードウェアの様々な部分 (例えば無線) を管理するために使われています。 これらの CPU は、それぞれアーキテクチャからして異なっている場合があり、 動作しているプログラムは、お互い、メインメモリを使って通信することができません。
現在販売されているほとんどの Android デバイスは、 SMP 設計で作られています。 これはソフトウェア開発者にとって、少々厄介です。 マルチスレッドプログラムで起き得る競合状態の類は、 SMP においては、さらに悪化します。 2 つ以上のスレッドを使うと、それらが異なるコアで同時に実行されるのです。 その上、 ARM の SMP は、 x86 の SMP に比べて、難易度が上です。 x86 上で徹底的にテスト済みのコードが、 ARM 上では動作しない可能性があるのです。
このドキュメントの残りの部分では、なぜそのようなことが起きるのかを説明し、 コードが正常に動作することを保証するために、何をする必要があるのかについて述べます。
これは、複雑な問題を、駆け足でもっともらしく要約したものです。 いくつか不完全な部分もありますが、誤解や間違いは無いはずです。
このドキュメントの最後に、この問題に対するより完全な対処法へのポインタを 参考文献 として載せていますので、参照してください。
メモリ一貫性モデル (単に「メモリモデル」と呼ばれることもあります) とは、 ハードウェアアーキテクチャがメモリアクセスに関して保証する内容を述べたものです。 例えば、アドレス A にある値を書き込み、その後アドレス B にある値を書き込むと、 すべての CPU コアからその書き込みがその順序通りに見える、とかいったようなことです。
逐次一貫性 は、ほとんどのプログラマに馴染みのあるモデルです。 これは以下のようなものです。 (Adve & Gharachorloo)
あるコードがメモリの読み書きを実行している場合、 逐次一貫性のある CPU アーキテクチャにおいては、 それらの読み書きは期待通りの順序で行われるでしょう。 実際には、 CPU によって命令が並べ替えられ、読み書きが遅延される場合もありますが、 そのデバイス上で実行しているコードには、 CPU が順序通りに命令を実行する以外のことをしているなどと知る方法はありません。 (とりあえずメモリマップド I/O のことは無視します。)
このことを示すために、小さなコード片を考えるのがいいでしょう。 これは一般に リトマス試験 と呼ばれます。 このコード片は プログラム順序 で実行されると仮定します。 つまり、ここで示す命令の順序は、 CPU が実行する順序だということです。 コンパイラが行う命令の並べ替えはまだ考慮しません。
簡単な例を示しましょう。 2 つのスレッドでコードが実行されます。
| スレッド 1 | スレッド 2 |
|---|---|
A = 3 |
reg0 = B |
この例および以降のすべてのリトマスにおいて、 大文字 (A、B、C) はメモリの場所を表し、 “reg” で始まるものは CPU のレジスタを表します。 メモリの初期値はすべて 0 です。 命令は上から下に実行されます。 この例では、 スレッド 1 は値 3 を場所 A に書き込み、その後、値 5 を場所 B に書き込みます。 スレッド 2 は場所 B から reg0 に値を読み込み、その後、場所 A から reg1 に値を読み込みます。 (書き込む順序と読み込む順序が異なっていることに注意してください。)
スレッド 1 とスレッド 2 は異なる CPU コア上で実行されると仮定しています。 マルチスレッドコードについて考えるときは 常に この仮定を置くべきです。
逐次一貫性の保証の下では、 両方のスレッドが実行を終えた後、 レジスタが以下の状態のいずれかになります。
| レジスタ | 状態 |
|---|---|
| reg0=5, reg1=3 | 有り得る (スレッド 1 が先に実行された) |
| reg0=0, reg1=0 | 有り得る (スレッド 2 が先に実行された) |
| reg0=0, reg1=3 | 有り得る (同時に実行された) |
| reg0=5, reg1=0 | 有り得ない |
A に書き込まれる前に B=5 が見えるという状況になるためには、 読み込みか書き込みのどちらかが、アウトオブオーダーで実行されなければなりません。 逐次一貫性のあるマシンでは、これは有り得ません。
ほとんどのシングルプロセッサマシン (x86 や ARM を含む) には、逐次一貫性があります。 ほとんどの SMP システム (x86 や ARM を含む) には、ありません。
x86 の SMP には プロセッサ一貫性 があります。 これは逐次一貫性よりも若干弱いものです。 このアーキテクチャでは、 読み込みが他の読み込みによって並べ替えられないことと、 書き込みが他の書き込みによって並べ替えられないことは保証されますが、 書き込みの後に読み込みが続く場合は、それが期待通りの順序で見えることは保証されません。
以下の例を考えてみてください。 相互排他のためのデッカーのアルゴリズムの一部です。
| スレッド 1 | スレッド 2 |
|---|---|
A = true |
B = true |
意図としては、 A を使ってスレッド 1 が処理中であることを示し、 B を使ってスレッド 2 が処理中であることを示すというものです。 スレッド 1 は A をセットし、それから B がセットされているか調べます。 もしセットされていなければ、 クリティカルセクションへの排他アクセスを得たと安全に仮定できます。 スレッド 2 も同様のことを行います。 (もし A と B が両方セットされていれば、 公平性を保証するためのターン取得アルゴリズムが使われます。)
逐次一貫性のあるマシンでは、これは正しく動作します。 x86 や ARM の SMP では、 スレッド 1 が行う A への書き込みと B からの読み込みは、 スレッド 2 からは異なる順序で「見える」場合があります。 もしそれが起きた場合は、実際には以下の順序で実行されたように見えます。 (操作の見える順序をわかりやすくするために空行を入れています)
| スレッド 1 | スレッド 2 |
|---|---|
reg1 = B |
|
この結果、 reg1 と reg2 は両方とも “false” にセットされ、 両方のスレッドが同時にクリティカルセクションを実行してしまいます。 これがどのように起きるのかを理解するためには、 CPU のキャッシュについて少し知る必要があります。
これはこれ自体で結構大きな話題です。 以下で述べるのは非常に大雑把な要約です。 (この話題を扱う目的は、 なぜ SMP システムがそのように動作するのかを理解してもらうことです。)
最近の CPU には、プロセッサとメインメモリの間に 1 つかそれ以上のキャッシュがあります。 これらは L1、L2 などと呼ばれ、数字が大きいほど CPU から「遠い」ことを表します。 キャッシュメモリはハードウェアのサイズとコストを増加させ、また消費電力も増加させます。 そのため Android デバイスで使われる ARM CPU では、 通常、 L1 キャッシュは小さく、 L2/L3 はまったく無いか、あってもわずかなものです。
L1 キャッシュへの値の読み書きは非常に高速です。 メインメモリへの読み書きは、その 10～100 倍遅くなります。 そのため CPU は、可能な限りキャッシュを使い倒そうとします。 キャッシュに書き込んだデータがいつメインメモリに転送されるかは、 キャッシュの 書き込みポリシー によって決まります。 ライトスルー キャッシュでは、 メモリへの書き込みが直ちに開始されますが、 ライトバック キャッシュでは、 領域を使い切っていずれかのエントリを空ける必要が生じるまで待ちます。 いずれの場合でも、 CPU はその書き込み命令を超えて次の命令の実行を続けます。 その書き込みがメインメモリ上で見えるまでの間に数十もの命令を実行することもあるでしょう。 (ライトスルーキャッシュはデータを直ちにメインメモリに転送するポリシーですが、 それは書き込みを 開始 するだけです。 書き込みが終わるまで待つわけではありません。)
それぞれの CPU コアが独自のプライベートなキャッシュを持っている場合、 そのキャッシュの動作がこの議論に関連してきます。 単純なモデルでは、それらのキャッシュは、お互いに直接通信する手段はありません。 コア 1 のキャッシュが持つ値は、 コア 2 のキャッシュと共有しておらず、見ることができません。 メインメモリへの読み書きだけが共有の手段です。 メモリアクセスのレイテンシは長いため、スレッド間の通信は非常に低速です。 そのため、キャッシュ間にデータを共有する手段を設けると、役に立ちます。 こういった共有は キャッシュコヒーレンシ と呼ばれ、 CPU アーキテクチャの キャッシュコヒーレンシモデル によってそのルールが定義されます。
これを頭に置いて、デッカーの例に戻りましょう。 コア 1 が “A = 1” を実行すると、コア 1 のキャッシュにその値が書き込まれます。 コア 2 が “if (A == 0)” を実行すると、 その値はメインメモリから読み込まれるか、あるいはコア 2 のキャッシュから読み込まれます。 (コア 2 が以前に “A” を読み込んだことがあれば、 “A” がキャッシュにある可能性があります。) いずれにせよ、コア 1 の書き込んだ値は見えません。
もしメモリ一貫性モデルが逐次一貫性を持とうとするなら、 コア 1 は他のすべてのコアが “A = 1” を認識できるまで待ってから “if (B == 0)” を実行しなければなりません (厳格なキャッシュコヒーレンシルールを用いるか、 あるいはキャッシュを完全に無効化してすべての操作をメインメモリに対して行うことによって、 書き込みを他のコアに伝える必要があります)。 これでは、あらゆる書き込み操作に、性能上のペナルティーを課すことになってしまいます。 書き込みの後に読み込みが続く場合の順序について、ルールをいくらか緩めれば、性能を上げられます。 しかし、ソフトウェア開発者には負担がかかります。
プロセッサ一貫性モデルには他にもいくつか保証している事柄がありますが、 それらは比較的低コストなものです。 例えば、メモリへの書き込みが順序通りに見えることを保証するのは、 その書き込みが行われたのと同じ順序でそれを他のコアに公開するだけで済みます。 最初の書き込みが公開されるのを 完了 するまで、 次の書き込みの開始を待つ必要はありません。 最初の公開が完了する前に次の公開が完了しなければいいだけです。 これにより性能上の障害を回避できます。
保証をさらに緩めれば、 CPU の行う最適化の機会がさらに増えますが、 プログラマの期待通りにコードが動作しない機会もさらに増えます。
ひとつだけ追記すると、 CPU のキャッシュは個々のバイト単位で動作するわけではありません。 データは キャッシュライン 単位で読み書きされます。 これは ARM CPU の多くでは 32 バイトです。 メインメモリのある場所からデータを読み込むと、その付近にあるデータも同様に読み込まれます。 データを書き込むと、そのキャッシュラインがメモリから読み込まれ、そして更新されます。 その結果、 付近にあるものを読み書きした副作用として値がキャッシュに読み込まれるという、 不思議な現象が起きるわけです。
先へ進む前に、読み書きが「見える」の意味をもう少し厳密に定義した方がいいかもしれません。 コア 1 が “A = 1” を実行したとします。 この書き込みは、 CPU がその命令を実行したときに 開始 されます。 その後いくらか経つと、キャッシュコヒーレンシの働きにより、 その書き込みがコア 2 から 見える ようになります。 ライトスルーキャッシュでは、書き込みがメインメモリに到達するまでは本当に 完了 したとは言えませんが、 メモリ一貫性モデルでは、そういったことに関知しません。 ただ 見える ようになれば、完了したとみなします。
(メモリマップド I/O にアクセスするカーネルデバイスドライバでは、 物事が本当に完了したことを知るのが非常に重要な場合がありますが、 そこまでは深入りしません。)
可視性は以下のように定義することが出来ます。
もう少しくだけた言い方をすると、以下のようになります。 (「あなた」とか「私」とかは CPU コアだと思ってください。)
書き込みが見えるというのは直感的ですが、 読み込みが見えるというのは少し違和感があるかもしれません (心配せずとも、すぐに慣れます)。
ようやく ARM について説明する準備が出来ました。
ARM の SMP には弱いメモリ一貫性保証しかありません。 読み込みも書き込みもお互いの順序が保証されません。
| スレッド 1 | スレッド 2 |
|---|---|
A = 41 |
loop_until (B == 1) |
すべてのアドレスは初期値が 0 だということを思い出してください。 “loop_until” 命令は B を繰り返し読み込み、 B から 1 を読み込むまでループします。 スレッド 1 が A を更新するまでスレッド 2 を待たせたいわけです。 スレッド 1 が A をセットし、その後、 B を 1 にセットしてデータが有効であることを示します。
x86 の SMP では、これが動作することが保証されています。 スレッド 2 はスレッド 1 の書き込みがプログラム順序で行われるのが見え、 スレッド 1 はスレッド 2 の読み込みがプログラム順序で行われるのが見えます。
ARM の SMP では、読み書きが任意の順序で見えます。 すべてのコードが実行完了した後、 reg が 0 を保持していることが有り得ます。 41 を保持している可能性もあります。 明示的に順序付けを定義しない限り、どのような結果になるかは判りません。
(他のシステムの経験がある人向けに言うと、 ARM のメモリモデルはほとんどの点において PowerPC と同じです。)
メモリアクセスの順序が重要であることを CPU に伝える方法がメモリバリアです。 ARM/x86 のシングルプロセッサ環境では逐次一貫性があるので、メモリバリアは必要ありません。 (バリア命令を実行することは出来ますが、意味はありません。 バリアが非常に高く付くケースがあるため、 SMP 向けにビルドを分けることもあります。)
考慮すべき基本的な状況が 4 つあります。
以前の例を思い出してください。
| スレッド 1 | スレッド 2 |
|---|---|
A = 41 |
loop_until (B == 1) |
スレッド 1 は、 B への書き込みよりも前に確実に A の書き込みが行われるようにしなければなりません。 これは「書き込み/書き込み」の状況です。 同様にスレッド 2 は、 A の読み込みよりも前に確実に B の読み込みが行われるようにしなければなりません。 これは「読み込み/読み込み」の状況です。 以前述べたように、読み書きは任意の順序で見える可能性があります。
キャッシュの議論を思い出してください。 A と B は異なるキャッシュラインにあり、 最低限のキャッシュコヒーレンシしかないものと仮定します。 もし A への書き込みがローカルキャッシュに留まる一方、 B への書き込みが公開されてしまうと、 コア 2 には B=1 が見えるけれども、 A の更新は見ることができません。 他にも問題があります。 A の読み込みが以前に行われた、 あるいは A が最近読み込んだ別の何かと同じキャッシュラインにあったと仮定します。 すると、コア 2 は B の更新が見えるまでループした後、 ローカルキャッシュから A を読み込むことになります。 もちろん値は 0 のままです。
これは以下のようにすれば修正することが出来ます。
| スレッド 1 | スレッド 2 |
|---|---|
A = 41 |
loop_until (B == 1) |
書き込み/書き込みバリアの働きにより、 すべてのコア について、 B への書き込みが見える前に A への書き込みが見えることが保証されます。 スレッド 1 で行われる読み込みの順序については何の保証もありませんが、 特に何も読み込んでいないので、問題ありません。 スレッド 2 の読み込み/読み込みバリアも、読み込みについて同様の保証が行われます。
書き込み/書き込みバリアにより、 書き込みがプログラム順序でスレッド 2 に見えることが保証されるのなら、 なぜスレッド 2 の読み込み/読み込みバリアが必要なのでしょう？ それは、読み込みがプログラム順序でスレッド 1 に見えることも保証する必要があるからです。
書き込み/書き込みバリアは、例えば、 すべてのダーティエントリをローカルキャッシュから吐き出すことにより、 以降のどんな書き込みよりも前に現在の値が他のコアから見えることを保証します。 読み込み/読み込みバリアは、例えば、 ローカルキャッシュを完全に破棄し、 また「実行中」の読み込みが完了するまで待つことで、 以降の読み込みが以前の読み込みよりも後に見えることを保証します。 まぁ、適切な保証さえ行われていれば、 CPU が実際に何をしているかはどうでもいいことです。 もしコア 1 でバリアを張り、コア 2 で張らなければ、 コア 2 は自身のローカルキャッシュから A を読み込むことでしょう。
メモリモデルはアーキテクチャによって異なります。 そのため、これらのバリアは ARM の SMP では必要ですが、 x86 の SMP では必要ありません。
以前に示したデッカーのアルゴリズムの一部は、書き込み/読み込みバリアが必要な例です。 読み込み/書き込みバリアが必要な例は、以下に示します。
| スレッド 1 | スレッド 2 |
|---|---|
reg = A |
loop_until (B == 1) |
スレッド 2 は、スレッド 1 の A の読み込みが見える前に、 スレッド 1 の B=1 の書き込みが見える可能性があります。 その結果、スレッド 1 が A を読み込む前に、 A=41 を書き込んでしまう可能性があります。 この問題は、両方のスレッドに読み込み/書き込みバリアを入れると、解決します。
| スレッド 1 | スレッド 2 |
|---|---|
reg = A |
loop_until (B == 1) |
メインメモリへのアクセスは非常に低速なため、 メインメモリからの読み込みよりも前に、 ローカルキャッシュへの書き込みが見えることがあります。 このケースでは、 コア 1 のキャッシュには B のキャッシュラインは保持しているけれども A は保持していないと仮定します。 A からの読み込みが開始され、そしてそれが行われている間も実行は続けられます。 ローカルキャッシュ上で B への書き込みが発生し、 それが何らかの経路でコア 2 に見えるようになっても、 まだ A からの読み込みは終わっていません。 スレッド 1 の A からの読み込みが見える前に、 スレッド 2 はループを脱出してしまいます。
スレッド 2 のバリアは必要なのでしょうか？ CPU が投機的書き込みを行わないなら、 命令をアウトオブオーダー実行しないなら、 そしてスレッド 1 さえ読み込み/書き込み順序を保証していれば、 スレッド 1 が読み込むより前にスレッド 2 が A に書き込めるのでしょうか？ (答え: いいえ。) 第 3 のコアが A と B を監視していたら、どうでしょうか？ (答え: その場合は必要です。 さもなければ、第 3 のコアからは B==0 / A==41 が見える可能性があります。) 細かいことを気にせず両方にバリアを入れておくのが一番安全です。
以前述べたように、 x86 の SMP においては、 必要なのは書き込み/読み込みバリアの類だけです。
バリア命令の種類は CPU ごとに異なります。 例えば、
「フルバリア」は、 4 種類全部の効果を持っているという意味です。
バリア命令が保証しているのは順序だけだ、というのは重要なポイントです。 キャッシュコヒーレンシの「同期ポイント」や、同期的な「フラッシュ」命令として扱ってはいけません。 ARM の “dmb” 命令は他のコアに直接の影響を与えません。 これを理解することは、 バリア命令を発行する必要のある場所を探すときに重要になります。
(これはやや高度なトピックなので、飛ばしても構いません。)
ARM CPU には、読み込み/読み込みバリアを省略してもよい特別なケースがひとつあります。 以前のものを少し変えた、以下の例を考えてみてください。
| スレッド 1 | スレッド 2 |
|---|---|
[A+8] = 41 |
loop: |
ここでは新しい表記を導入しています。 “A” がメモリアドレスを参照しているとき、 “A+n” は A から n バイトずれたメモリアドレスを参照しています。 A がオブジェクト、または配列のベースアドレスであれば、 [A+8] はそのオブジェクトのフィールドか、その配列の要素になるでしょう。
以前の例にあった “loop_until” は、 B の reg0 への読み込みを示すために展開してあります。 reg1 には数値 8 が代入され、 reg2 にはアドレス [A+reg1] から読み込まれます (スレッド 1 がアクセスしているのと同じ場所です)。
これは、 [A+reg1] からの読み込みの後に B からの読み込みが見える可能性があるため、 正しく動作しないでしょう。 ループの後に読み込み/読み込みバリアを入れて修正することも出来ますが、 ARM では単に以下のようにすることも出来ます。
| スレッド 1 | スレッド 2 |
|---|---|
[A+8] = 41 |
loop: |
何をしたかというと、 reg1 に代入する値を、定数 (8) から、 B から読み込んだ値に依存する値に変更したのです。 このケースでは、値 0 とビットごとの AND を行い、その結果 (必ず 0 になります) を足しました。 つまり reg1 は値 8 のままです。 しかし、 ARM CPU は [A+reg1] からの読み込みが B からの読み込みに依存すると信じ込みます。 その結果、この 2 つの読み込みはプログラム順序で見えることが保証されます。
これは アドレス依存 と呼ばれます。 ある読み込みにより返された値を、後の読み書きのアドレス計算に使用するとき、 そこにはアドレス依存が存在しています。 これにより、特定の状況においては、明示的なバリアの必要を回避することができます。
ARM には 制御依存 の保証はありません。 これを示すためには、少し ARM コードの海に潜る必要があります。 (Barrier Litmus Tests and Cookbook)
LDR r1, [r0] CMP r1, #55 LDRNE r2, [r3]
r0 および r3 からの読み込みは、 仮に r0 が 55 を保持しておらず r3 からの読み込みがまったく実行されないとしても、 アウトオブオーダーで見える可能性があります。 AND r1, r1, #0 を挿入し、 最後の命令を LDRNE r2, [r3, r1] で置き換えれば、 明示的なバリアがなくても正しい順序が保証されます。 (これは、一貫性の問題を命令実行の視点で考えてはいけないという、主な例です。 常にメモリアクセスの視点で考えなければなりません。)
やや深入りしすぎているかもしれませんが、 ARM が 因果一貫性 を持たないことも示しておく価値があるでしょう。
| スレッド 1 | スレッド 2 | スレッド 3 |
|---|---|---|
A = 1 |
loop_until (A == 1) |
loop: |
この例では、スレッド 1 が A をセットし、スレッド 2 に知らせます。 スレッド 2 はそれを見て B をセットし、スレッド 3 に知らせます。 スレッド 3 はそれを見て A から読み込みます。 アドレス依存を使って、 B からの読み込みと A からの読み込みがプログラム順序で見えることを保証します。
実行終了後、 reg2 が 0 を保持している可能性があります。 スレッド 1 の書き込みによってスレッド 2 に何かが起こり、 それによってスレッド 3 に何かが起きたとしても、 一連の書き込みが順序通りにスレッド 3 から見える保証はありません。 (スレッド 2 に読み込み/書き込みバリアを入れると、正しく動作するようになります。)
異なる状況のために異なる種類のバリアがあります。 適切な種類のバリアを正しく使えば性能上の利点を得ることが出来ますが、 コードのメンテナンス性が犠牲になります。 コードを変更する人が完全にそれを理解していなければ、 間違った種類の操作を用い、不可思議なバグを発生させる可能性があります。 このため、また ARM にそれほど多様なバリアの選択肢が用意されていないため、 多くのアトミック操作ではバリアが必要なときにはフルバリア命令を使用しています。
バリアについて覚えておくべき重要なことは、順序を定義するものだということです。 一連の動作を発生させる「フラッシュ」命令だと考えてはいけません。 そうではなく、現在の CPU コアが行う操作に対する、時間的な分割線だと考えてください。
アトミック操作は、一連のステップが必要な操作を、 単一の命令であるかのように必ず振る舞うことを保証します。 例えば、同じ変数に対するアトミックでないインクリメント (“++A”) を、 2 つのスレッドで同時に実行することを考えてみましょう。
| スレッド 1 | スレッド 2 |
|---|---|
reg = A |
reg = A |
2 つのスレッドが同時に上から下へ実行した場合、 両方のスレッドが A から 0 を読み込み、それに 1 を加え、そして書き戻します。 最終結果は 1 になるでしょう。 アトミックなインクリメント操作を使用すれば、最終結果が 2 になることが保証されます。
最も基本的な操作 (32 ビット値の読み書き) は、 ARM においては、データが 32 ビット境界に配置されている限り、 元々アトミックです。
| スレッド 1 | スレッド 2 |
|---|---|
reg = 0x00000000 |
reg = 0xffffffff |
A が 0x00000000 と 0xffffffff のどちらかになることが保証されています。 0x0000ffff とかそういう、バイト列が中途半端に混ざるようなことはありません。
データの境界が合っていなければ、アトミック性の保証は失われます。 境界の合っていないデータはキャッシュラインをまたがる可能性があり、 上半分と下半分が別々に更新されるところが他のコアから見える可能性があります。 すべてのバイトアクセス、 ハーフワード境界に合っているハーフワードアクセス、 ワード境界に合っているワードアクセスに対して 「シングルコピーアトミック性」を持つことが、 ARMv7 のドキュメントで述べられています。 ダブルワード (64 ビット) アクセスは、アトミックでは ありません。 ただし、その位置がダブルワード境界に合っていて、 特別な読み書き命令が使用された場合は除きます。 複数のスレッドが同期せずに構造体や配列の更新を行う場合、 この動作を理解することは重要です。
ARM でも x86 でも、 32 ビットの「アトミック読み込み」や「アトミック書き込み」の関数は不要です。 完全を期すためそれらが提供されていたとしても、それは単に普通の読み書きを行うだけです。
メモリ上のデータに複雑な処理を行う操作は、 一般に read-modify-write (読み込み-変更-書き込み; RMW) 命令として知られています。 つまり、データを読み込み、その値に何らかの変更を行い、そして書き戻すわけです。 これらがどのように実装されているかは CPU によって様々です。 ARM では “Load Linked / Store Conditional” (リンク付き読み込み/条件付き書き込み) 略して LL/SC と呼ばれる技法を使います。
リンク付き 別名 ロック付き の読み込みは、 通常通りメモリからデータを読み込みますが、 その物理メモリアドレスに紐付いた予約を確立します。 この予約は、他のコアがそのアドレスに書き込みを行おうとすると、失効します。 LL/SC を使うときは、予約付きでデータを読み込み、変更を行い、 そして条件付き書き込み命令を使ってデータの書き戻しを試みます。 予約が未だ有効であれば、書き込みは成功します。 すでに失効していれば、失敗します。 LL/SC ベースのアトミック関数は通常、読み込み-変更-書き込みのシーケンス全体を、 割り込まれることなく成功するまで、繰り返します。
もし仮に、読み込み-変更-書き込み操作が古いデータに対して行われていれば、 それは正しく動作しないであろう、ということも、ここで述べておく価値があるでしょう。 2 つのコアが同じアドレスに対してアトミックインクリメントを実行する場合、 もし仮に、それぞれのコアがローカルキャッシュを読み書きしていて、 いずれかのコアが他のコアの値を見ることが出来なければ、 その操作は実際にはアトミックに行われないでしょう。 CPU のキャッシュコヒーレンシルールがあるおかげで、 アトミックな RMW 操作は SMP 環境でも同様にアトミックであることが保証されています。
これを、アトミックな RMW 操作はメモリバリアを張る、と解釈するべきではありません。 ARM においては、アトミックにはメモリバリアの効果はありません。 単一のアドレスに対する一連のアトミックな RMW 操作は、他のコアからプログラム順序で見えますが、 アトミックな操作とアトミックでない操作を混ぜたとき、その順序に関する保証はありません。
バリアとアトミック操作をペアにして一緒に使うのは意味のあることです。 次の節では、このことについて、より詳細に述べます。
いつも通り、例を示しながら議論を進めるのがいいでしょう。 今回は スピンロック と呼ばれる、簡単な相互排他の仕組みについて考えます。 考え方としては、あるメモリアドレス (「ロック」と呼ぶことにします) を 0 で初期化します。 あるスレッドがクリティカルセクション内のコードを実行しようとするとき、 そのロックを 1 にセットし、クリティカルなコードを実行し、終わったらそれを 0 に戻します。 もし他のスレッドが、そのロックをすでに 1 にセットしていた場合は、 そのロックが 0 に戻るまで、スピンして待ちます。
これを正しく動かすためには、 compare-and-swap と呼ばれるアトミックな RMW プリミティブを使います。 この関数は 3 つの引数を取ります。 メモリアドレス、期待する現在値、そして新しい値です。 メモリ内の現在の値が期待する値と一致すれば、新しい値に置き換えられ、古い値が返されます。 現在の値が期待する値と一致しなければ、変更は行われません。 これのマイナーな変種に、 compare-and-set と呼ばれるものもあります。 こちらは、古い値を返す代わりに、置換が成功したかどうかを表すブーリアンを返します。 どちらを使っても大丈夫ですが、 compare-and-set の方が、 例がいくらかシンプルになるので、そちらを使うことにします。 以降、これを “CAS” と呼びます。
スピンロックの取得処理は、以下のように書くことができます (Cっぽい言語を使っていると思ってください)。
do {
success = atomic_cas(&lock, 0, 1)
} while (!success)
full_memory_barrier()
クリティカルセクション
ロックを保持しているスレッドがなければ、ロックの値は 0 であり、 CAS 操作によって 1 にセットされます (ロックを保持したことを表します)。 もし他のスレッドがロックを保持していれば、ロックの値は 1 であり、 期待される現在値が実際の現在値と異なるため、 CAS 操作は失敗します。 その場合、繰り返しリトライします。 (このループは atomic_cas 関数の外側にあることに注意してください。 atomic_cas 関数の内部でも LL/SC コードのループが行われているはずです。)
SMP では、スピンロックは小さなクリティカルセクションを保護する便利な手段です。 もし他のスレッドが少数の命令を実行した後にロックを解放することがわかっているなら、 待っている間、多少 CPU サイクルを消費するのは、大したことではありません。 しかし、そのスレッドが同じコアで実行される予定であれば、 OS が再度スケジューリングを行う (スレッドを他のコアに移送するにせよ、現在のスレッドをプリエンプトするにせよ) まで、そのスレッドが動くことは出来ず、時間を無駄にするだけです。 まともなスピンロックの実装では、わずかな回数だけスピンしてみた後、 OS のプリミティブ (Linux の futex とか) にフォールバックし、 他のスレッドが処理を終えるまで待つ間、現在のスレッドをスリープさせるようになっています。 シングルプロセッサにおいては、スピンする価値はまったくありません。 話を簡単にするために、こういったことは一切無視しています。
メモリバリアは必要です。 他のスレッドにクリティカルセクション内の読み書きが見える前に、 ロックの取得が見えることを保証しなければなりません。 バリアがなければ、それらのメモリアクセスが、 ロックを保持していない間も見える可能性があります。
full_memory_barrier は、 実際には 2 つ の独立した操作を行います。 ひとつめは、 CPU のフルメモリバリア命令を発行します。 ふたつめは、バリアの周りのコードを並び替えてはいけないことをコンパイラに指示します。 これによって、 atomic_cas が、 クリティカルセクション内のいかなるコードよりも前に実行されます。 この コンパイラ並び替えバリア がなければ、 コンパイラのコード生成方法に非常に大きな自由度を与えることになり、 コンパイル後のコードの命令の順序は、 ソースコード上の順序とまったく違ったものになるでしょう。
もちろん、クリティカルセクション内で行うメモリアクセスが、 ロック解放後に見えることがないようにもしなければなりません。 シンプルなスピンロックの完全なバージョンは以下のようになります。
do {
success = atomic_cas(&lock, 0, 1) // 取得
} while (!success)
full_memory_barrier()
クリティカルセクション
full_memory_barrier()
atomic_store(&lock, 0) // 解放
クリティカルセクション内の読み書きがロックを解放する前に見えるように、 ロックを解放する 前 に、 CPU およびコンパイラに対する 2 つめのメモリバリアを実行しています。
以前述べたように、 atomic_store 操作は、 ARM および x86 においては単なる代入です。 アトミックな RMW 操作と異なり、 他のスレッドからこの値を直ちに見えるようにする保証を行っていません。 しかし、これは問題にはなりません。 必要なのは、他のスレッドが中に入れないようにすることだけです。 他のスレッドは、 0 の書き込みが見えるまで、中に入ることができません。 この値が見えるまでに少し時間がかかったとしても、 多少長くスピンすることになるかもしれませんが、 コードは正しく実行されます。
アトミック操作とバリアの呼び出しは、ひとつの関数にまとめると便利です。 便利以外にも、コードが分かりやすくなるという利点があります。
スピンロックを取得するときは、アトミック CAS を実行し、その後にバリアを張ります。 スピンロックを解放するときは、バリアを張り、その後にアトミック書き込みを実行します。 これに着想を得た、ある命名の慣習があります。 事後にバリアを張る操作を「取得」操作と呼び、 事前にバリアを張る操作を「解放」操作と呼びます。 (スピンロックの例は、しっかりと頭の中に入れておいた方がいいでしょう。 さもなければ、このネーミングは意味不明です。)
これを考慮に入れて、スピンロックの例を書き直します。
do {
success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)
クリティカルセクション
atomic_release_store(&lock, 0)
多少簡潔になり、読みやすくなりました。 しかし、このようなことをする本当の動機は、 いくつかの最適化が出来るようになる、というところにあります。
まず、 atomic_release_store について考えてみましょう。 ロックワードへの 0 の書き込みが、 その上にあるクリティカルセクションの中のいかなる読み書きよりも後に見えることを、 保証しなければなりません。 別の言い方をすると、 読み込み/書き込みバリアと書き込み/書き込みバリアが必要だということです。 以前の節で、 x86 の SMP にはこれらが必要ないことを学びました。 書き込み/読み込みバリアだけが要求されます。 従って、 x86 の atomic_release_store は、 コンパイラ並び替えバリアの後に、単なる書き込みを行うだけのものです。 CPU のバリアは必要ありません。
2 つめの最適化は、ほぼコンパイラに適用されるものです (Itanium のような一部の CPU にも、同様にこの利点を得られるものがあります)。 基本的な原理としては、 取得バリアや解放バリアを超えてコードを移動することができる、 というものです。 ただし、一方通行です。
ローカルに可視なメモリアクセスと、 グローバルに可視なメモリアクセス、 さらに雑多な計算処理を、 混ぜて行う状況を考えてみましょう。
local1 = arg1 / 41
local2 = threadStruct->field2
threadStruct->field3 = local2
do {
success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)
local5 = globalStruct->field5
globalStruct->field6 = local5
atomic_release_store(&lock, 0)
この例には、完全に独立した操作のグループが 2 つあります。 1 つめのグループはスレッドローカルなデータ構造を操作するもので、 他のスレッドと衝突することを考慮する必要がありません。 2 つめのグループはグローバルなデータ構造を操作するもので、 ロックによって保護する必要があります。
アトミック操作で使われるコンパイラ並び替えのフルバリアは、 ロック境界において、ソースコードの順序とプログラム順序が一致することを保証します。 しかし、コンパイラが命令列をインターリーブできれば、性能が上がる可能性があります。 メモリからの読み込みは低速ですが、 その読み込みの結果を必要としない命令に関しては、 読み込みが完了するのを待っている間にも、 CPU による実行を続けることが出来ます。 コードを以下のように書くことが出来れば、 先程のものよりも高速に実行できる可能性があります。
do {
success = atomic_acquire_cas(&lock, 0, 1)
} while (!success)
local2 = threadStruct->field2
local5 = globalStruct->field5
local1 = arg1 / 41
threadStruct->field3 = local2
globalStruct->field6 = local5
atomic_release_store(&lock, 0)
両方の読み込みを行い、 そして関係のない計算を実行し、 それから読み込んだ結果を使用します。 整数除算がどちらかの読み込みよりも短い時間しかかからなければ、 それは実質的にタダで行うことができます。 どのみち CPU は読み込みが完了するまで待たなければならず、 その間に計算してしまえるからです。
すべての 操作がクリティカルセクション内で実行されるようになりました。 “threadStruct” の操作は現在のスレッド以外には見せないので、 他の誰も最後までそれらを見ることは出来ず、 これらが発生する正確なタイミングは問題にはなりません。
一般的に言って、 操作をクリティカルセクションの 中へ 移動することは常に安全ですが、 操作をクリティカルセクションの 外へ 移動することはまったく安全ではありません。 別の言い方をすると、 操作を「下方向に」取得バリアを超えて移動することと、 「上方向に」解放バリアを超えて移動することが出来ます。 アトミック操作がフルバリアを使っている場合は、 この種の移動を行うことは出来ません。
以前の点に戻ると、 x86 においてはすべての読み込みが取得読み込みであり、 すべての書き込みが解放書き込みであると言うことが出来ます。 つまり、
よって、 x86 の SMP においては、書き込み/読み込みバリアだけが必要なわけです。
アトミック操作に「取得」または「解放」と付いている場合、 それは単にバリアがアトミック操作の前または後で実行されるというだけではなく、 コンパイラがどのようにコードを並べ替えることが許されるかということも含まれています。
メモリ一貫性の問題をデバッグすることは非常に困難です。 メモリバリアを忘れたことで、どこかのコードが古いデータを読み込んだ場合、 デバッガでメモリダンプを調査しても、原因を見つけることは出来ないでしょう。 デバッガに問い合わせている間に、 CPU コアはすべてのメモリアクセスが完全に見えるようになり、 メモリの内容と CPU のレジスタは「有り得ない」状態で表示されます。
ここでは間違ったコードの例をいくつか、簡単な修正方法と共に示します。 その前に、基本的な言語機能の使い方について議論する必要があります。
シングルスレッドのコードを書くときは、変数の “volatile” 宣言は非常に便利です。 コンパイラは volatile な場所へのアクセスを省略したり並び替えたりしません。 逐次一貫性を持つハードウェア上で実行すれば、 読み書きが期待通りの順序で起きることが保証されます。
しかし、 volatile なアクセスと volatile でないアクセスは、並び替えられる可能性があります。 そのため、シングルプロセッサ環境のマルチスレッドにおいては、気を付ける必要があります (明示的なコンパイラ並び替えバリアが必要な場合があるということです)。 アトミックである保証は無く、メモリバリアも張られないため、 SMP 環境のマルチスレッドにおいては、 “volatile” は全く役に立ちません。 最近の C および C++ 言語の標準規格は、 組み込みのアトミック操作関数を用意することでこの問題に対応する方向に改訂されつつあります。
もし何かを “volatile” 宣言する必要があると考えているなら、 それは代わりにアトミック操作を使うべきだという強いシグナルです。
ほとんどの場合においては、 アトミック操作よりも同期プリミティブ (例えば pthread の mutex) を使った方が良いです。 しかしここでは、実用的な状況での使い方を示すために、アトミック操作を使います。
説明を簡単にするため、 ここではコンパイラの最適化による効果は無視します。 中にはシングルプロセッサでさえ正しく動作しないコードもあります。 ここで挙げるすべての例は、 コンパイラが馬鹿正直にコードを生成するものと仮定してください (例えば gcc -O0 でコンパイルします)。 ここで示す修正方法は、 コンパイラの並び替えとメモリアクセス順序の問題を両方とも解決するものですが、 後者のみを論ずることにします。
MyThing* gGlobalThing = NULL;
void initGlobalThing() // スレッド 1 で実行
{
MyThing* thing = malloc(sizeof(*thing));
memset(thing, 0, sizeof(*thing));
thing->x = 5;
thing->y = 10;
/* 初期化完了したので公開 */
gGlobalThing = thing;
}
void useGlobalThing() // スレッド 2 で実行
{
if (gGlobalThing != NULL) {
int i = gGlobalThing->x; // 5、0、または未初期化データのいずれにも成り得る
...
}
}
意図としては、まず構造体を割り当て、そのフィールドを初期化し、 そして最後にそれをグローバル変数に書き込むことによって「公開」する、 というものです。 この時点で、他のスレッドからその値を見ることが出来るようになります。 しかし、これは大丈夫なのでしょうか。 構造体は完全に初期化されている？ 本当に？ 少なくとも、 x86 の SMP においては、あるいはシングルプロセッサ環境においては、大丈夫です (もう一度言いますが、 コンパイラの出力コードがソースと正確に一致しているという、 やや危険な仮定を置いています)。
ARM においては、メモリバリアがなければ、 gGlobalThing への書き込みがフィールドの初期化よりも前に見える可能性があります。 他のスレッドが thing->x を読み込むと、 5、0、または未初期化のデータを見る可能性すらあります。
これは最後の代入を以下のように変更すれば修正できます。
atomic_release_store(&gGlobalThing, thing);
これにより、他のすべてのスレッドに正しい順序で書き込みが見えるようになります。 しかし、読み込みに関してはどうでしょうか？ このケースでは、 ARM においては、問題ありません。 アドレス依存のルールにより、 gGlobalThing からのオフセット付き読み込みが gGlobalThing の読み込みよりも後に見えることが保証されます。 しかし、アーキテクチャの詳細に依存するのは得策ではありません。 そのコードは非常に微妙なところで移植性が無いということになるからです。 完全な修正としては、読み込みの後にもバリアが必要です。
MyThing* thing = atomic_acquire_load(&gGlobalThing);
int i = thing->x;
これにより、正しい順序になりました。 これではコードを書くのが面倒なように思えるかもしれません。 しかしこれこそが、 ロックを使わずに複数のスレッドからデータ構造をアクセスするために、 支払わなければならないコストです。 また、アドレス依存は常に役に立つわけではありません。
MyThing gGlobalThing;
void initGlobalThing() // スレッド 1 で実行
{
gGlobalThing.x = 5;
gGlobalThing.y = 10;
/* 初期化完了 */
gGlobalThing.initialized = true;
}
void useGlobalThing() // スレッド 2 で実行
{
if (gGlobalThing.initialized) {
int i = gGlobalThing.x; // 5 または 0 に成り得る
}
}
initialized フィールドと他のフィールドとの間には何の関係もないので、 読み書きはアウトオブオーダーで見えます。 (グローバルなデータは OS が 0 に初期化するので、 「ランダムな」未初期化データを読み込む可能性はありません。)
書き込みを以下のように変更し、
atomic_release_store(&gGlobalThing.initialized, true);
読み込みを以下のように変更する必要があります。
int initialized = atomic_acquire_load(&gGlobalThing.initialized);
同じ問題のもうひとつの例は、参照カウントを使ったデータ構造の実装時に起きます。 参照カウント自体は、アトミックなインクリメントおよびデクリメント操作を使っている限り、 一貫性が保たれるでしょう。 しかし、エッジケースではまだ問題が起きる可能性があります。 例えば
void RefCounted::release()
{
int oldCount = atomic_dec(&mRefCount);
if (oldCount == 1) { // 0 にデクリメントされた
recycleStorage();
}
}
void useSharedThing(RefCountedThing sharedThing)
{
int localVar = sharedThing->x;
sharedThing->release();
sharedThing = NULL; // このポインタはこれ以上使用できない
doStuff(localVar); // localVar の値は間違っている可能性がある
}
release() の呼び出しでは、 バリアなしのアトミックデクリメント操作を使って、 参照カウントを減らします。 これはアトミック RMW 操作であるため、正しく動きます。 参照カウントは 0 になり、記憶領域は回収されます。
useSharedThing() 関数は、 sharedThing から必要なものを取り出し、それから解放します。 しかし、メモリバリアを使っていないため、 アトミック操作とアトミックでない操作が並べ替えられる可能性があります。 他のスレッドに回収操作が見えた 後で、 そのスレッドに sharedThing->x の読み込みが見える可能性があります。 そのため「回収済みの」メモリから読み込んだ値が localVar に格納される可能性があります。 例えば、 release() が呼ばれた後、 他のスレッドが同じ場所に新しいオブジェクトを作成したとかです。
これは atomic_dec() の呼び出しを atomic_release_dec() に置き換えることで修正できます。 このバリアによりオブジェクトが回収される前に sharedThing からの読み込みが見えることが保証されます。
ほとんどの場合、上記の例は実際には失敗しません。 「回収」関数は通常、内部でバリアを張っているためです (mutex で保護されたオブジェクトプールや libc ヒープの free()/delete() など)。 ただし、回収関数がバリアを使わずに実装されるロックフリーなアルゴリズムを使用していれば、 ARM の SMP においては、上記のコードは失敗する可能性があります。
ここまで、関係のある Java の言語機能については述べてきませんでした。 まずはそれをざっと見ていきましょう。
“synchronized” キーワードは、 Java 言語に用意されている組み込みのロック機構です。 すべてのオブジェクトには「モニタ」が紐付けられており、 相互排他アクセスを行うために使うことが出来ます。
“synchronized” ブロックの実装は、スピンロックの例と同じ基本的な構造を持っています。 最初に取得 CAS を行い、最後に解放書き込みを行います。 つまりコンパイラとコードオプティマイザは、 自由にコードを “synchronized” ブロックの中に移動できるということです。 ひとつ重要なことがあります。 synchronized ブロック内のコードが、 それより上のコードよりも後に実行されるとか、 それより下のコードよりも前に実行されるなどと考えては いけません。 さらに言えば、 あるメソッドに 2 つの synchronized ブロックがあり、 それらが同じオブジェクトをロックしていて、 その間にあるコードが他のスレッドから見えるような操作を何もしていなければ、 コンパイラによって「ロック粗大化」が行われ、 それらがひとつのブロックに結合されてしまう可能性があります。
もうひとつ関係のあるキーワードは “volatile” です。 Java 1.4 およびそれ以前の仕様では、 volatile 宣言は C のそれと同じくらい弱いものでした。 Java 1.5 で仕様が改訂され、 モニタ同期のレベルに近い強い保証が得られるようになりました。
volatile アクセスの効果は例を用いて示すことが出来ます。 スレッド 1 が volatile フィールドに書き込みを行い、 その後スレッド 2 がその同じフィールドから読み込みを行った場合、 スレッド 2 はその書き込みに加え、 スレッド 1 によってそれ以前に行われたすべての書き込みが見えることが保証されます。 より一般的に言うと、 そのフィールドへの書き込みを行った時点までの いかなる スレッドが行った書き込みも、 スレッド 2 が読み込みを行った時点で見えるようになります。 実質的に、 volatile フィールドへの書き込みはモニタの解放と同様であり、 volatile フィールドからの読み込みはモニタの取得と同様です。
volatile でないアクセスは、 volatile アクセスに対して、 通常の方法で並び替えられる可能性があります。 例えば、コンパイラは volatile でない読み書きを volatile 書き込みの「上」に移動することは出来ますが、 「下」に移動することは出来ません。 volatile アクセス同士はお互いに並び替えることが出来ません。 VM が適切なメモリバリアを張ってくれます。
オブジェクト参照とほとんどのプリミティブ型の読み書きはアトミックですが、 long と double のフィールドは volatile が付いていない限りアトミックにアクセスされないことを述べておくべきでしょう。 volatile でない 64 ビットフィールドを複数のスレッドで更新するのは、 シングルプロセッサ環境であっても、問題が起きる可能性があります。
以下はシンプルな、正しくない、単調カウンタの実装です。 (Java theory and practice: Managing volatility)
class Counter {
private int mValue;
public int get() {
return mValue;
}
public void incr() {
mValue++;
}
}
get() と incr() は複数のスレッドから呼ばれるものと仮定します。 get() が呼ばれれば、現在の値をどのスレッドからも見れるようにしたいとします。 最も明らかな問題は、 mValue++ が実際には 3 つの操作であるということです。
reg = mValuereg = reg + 1mValue = reg2 つのスレッドが incr() を同時に実行した場合、 片方の更新は失われるでしょう。 インクリメントをアトミックにするためには、 incr() を “synchronized” にする必要があります。 この変更によって、 シングルプロセッサ環境では正しく動作するようになります。
しかし SMP ではまだダメです。 通常の読み込みで値を読み込んでいるので、 スレッドごとに get() の結果が違って見える可能性があります。 get() を synchronized にすれば、この問題を修正できます。 この変更によって、明らかに正しいコードになります。
残念なことに、ロックの奪い合いが起きるようになってしまいました。 これは性能に影響を与えます。 get() を synchronized にする代わりに、 mValue を “volatile” にすることも出来ます。 (incr() は synchronized のままです。 注意してください。) mValue への volatile 書き込みは、 以降の mValue からの volatile 読み込みで見えます。 incr() は多少遅くなりますが、 get() は速くなります。 そのため、読み込みの頻度が書き込みよりも多ければ、 仮に奪い合いが起きなくとも、こちらの方が有利です。 (AtomicInteger も参照してみてください。)
他の例も見てみましょう。 以前の C の例に近い形のものです。
class MyGoodies {
public int x, y;
}
class MyClass {
static MyGoodies sGoodies;
void initGoodies() { // スレッド 1 で実行
MyGoodies goods = new MyGoodies();
goods.x = 5;
goods.y = 10;
sGoodies = goods;
}
void useGoodies() { // スレッド 2 で実行
if (sGoodies != null) {
int i = sGoodies.x; // 5 または 0
....
}
}
}
これは C のコードと同じ問題があります。 つまり、 goods のフィールドを初期化する前に、 sGoodies = goods の代入が見える可能性があります。 sGoodies に volatile キーワードを付ければ、 読み込みが atomic_acquire_load() のよう振る舞い、 書き込みが atomic_release_store() のように振る舞うものと考えることが出来ます。
(sGoodies の参照自身だけが volatile であることに注意してください。 その中のフィールドは volatile ではありません。 z = sGoodies.x の文では、 MyClass.sGoodies の volatile 読み込みの後に sGoodies.x の volatile でない読み込みが行われます。 もしローカルな参照 MyGoodies localGoods = sGoodies を作ると、 z = localGoods.x は volatile 読み込みを一切行いません。)
Java プログラミングにおける、よりコモンなイディオムとして、 悪名高き “double-checked locking” があります。
class MyClass {
private Helper helper = null;
public Helper getHelper() {
if (helper == null) {
synchronized (this) {
if (helper == null) {
helper = new Helper();
}
}
}
return helper;
}
}
意図としては、 MyClass のインスタンスに Helper オブジェクトのインスタンスをひとつ紐付けて持ちたいというものです。 オブジェクトは 1 回だけしか作成したくありません。 そのため、専用の getHelper() 関数を使ってオブジェクトの作成と取得を行います。 2 つのスレッドがインスタンスを作ってしまう競合状態を避けるため、 オブジェクトの作成を synchronized する必要があります。 しかし、呼び出しのたびに “synchronized” のオーバーヘッドを支払いたくはないので、 helper が現在 null の場合に、 その部分だけ synchronized しているというわけです。
シングルプロセッサシステムにおいては、 Java の伝統的なソースコンパイラとインタプリタオンリーな VM を使わない限り、 これは正しく動作しません。 オシャレなコード最適化や JIT コンパイラを使った途端に崩れ去ります。 詳細は付録のリンクにある 『‘Double Checked Locking は壊れている’ 宣言』 や、 Joshua Bloch 著 Effective Java 第 2 版 の項目 71 (遅延初期化を注意して使用する) を参照してください。
SMP システムでこれを実行した場合は、さらに別の壊れ方をします。 同じコードを、 C っぽい言語にコンパイルしたものとして、少し書き直して考えてみましょう (Helper のコンストラクタの動作を表現するために、 整数フィールドをいくつか追加しています)。
if (helper == null) {
// スピンロックを使ってモニタを取得
while (atomic_acquire_cas(&this.lock, 0, 1) != success)
;
if (helper == null) {
newHelper = malloc(sizeof(Helper));
newHelper->x = 5;
newHelper->y = 10;
helper = newHelper;
}
atomic_release_store(&this.lock, 0);
}
問題は明らかでしょう。 helper への書き込みはメモリバリアの前に行われており、 x/y フィールドへの書き込みが行われる前に、 他のスレッドが helper の null でない値を見る可能性があるということです。
this.lock に対する atomic_release_store() の後に helper への書き込みが起きることを保証できるよう、 コードを調整してみたいところです。 しかし、それは役に立ちません。 コードを上方向に移動することは認められているため、 コンパイラによって、代入が、元の位置から atomic_release_store() の上へ、 移動させられる可能性があります。
これを修正する方法は 2 つあります。
次の例は volatile を使う際の重要な問題を示しています。
class MyClass {
int data1, data2;
volatile int vol1, vol2;
void setValues() { // スレッド 1 で実行
data1 = 1;
vol1 = 2;
data2 = 3;
}
void useValues1() { // スレッド 2 で実行
if (vol1 == 2) {
int l1 = data1; // OK
int l2 = data2; // 間違い
}
}
void useValues2() { // スレッド 2 で実行
int dummy = vol2;
int l1 = data1; // 間違い
int l2 = data2; // 間違い
}
useValues1() を見てみましょう。 スレッド 2 に vol1 の更新がまだ見えていない場合は、 data1 や data2 が設定済みかどうか、まだ判りません。 ひとたび vol1 の更新が見えれば、 data1 の変更も見えます。 data1 の変更は vol1 が変更される前に行われたからです。 しかし、 data2 については何も想定できません。 その書き込みは、 volatile 書き込みの後に行われているからです。
useValues2() のコードでは、 VM にメモリバリアを張らせたいという意図により、 別の volatile フィールド vol2 を使用しています。 これは一般的には動作しません。 正規の “happens-before” 関係を確立するためには、 両方のスレッドが同じ volatile フィールドを使ってやりとりする必要があります。 もうおわかりだと思いますが、 スレッド 1 で data1/data2 を設定した後、 vol2 も設定しなければなりません。 (これが動作しないという事実は、コードを見ればおそらく明らかでしょう。 ここでの注意点は、ちょっと賢いことをしようと思って、 一連のアクセス順序を作る代わりにメモリバリアを張ろうとするのは、 やめた方がよいということです。)
C/C++ では、 mutex やセマフォのような pthread の関数を使ってください。 これらの関数は適切なメモリバリアを張り、 すべての Android プラットフォームバージョンにおいて、 正しく効率的な動作をします。 これらは必ず、正しく使ってください。 例えば、対応する mutex を保持せずに条件変数を signal しないよう気をつけてください。
アトミック関数を直接使うのは避けた方が良いです。 pthread mutex のロックとアンロックは、 奪い合いが起きない状況であれば、 それぞれアトミック操作を 1 回ずつ行うだけです。 そのため、 mutex の呼び出しをアトミック操作に置き換えても、 大した節約にはならないでしょう。 もしロックフリー設計が必要なら、 それをやる前にこのドキュメント全体を完全に理解する必要があります (あるいは、さらに良い方法は、 ARM の SMP で正しく動くことが判っている既存のコードライブラリを探すことです)。
C/C++ の “volatile” には非常に注意が必要です。 並行的な問題が近々発生するというシグナルかもしれません。
Java では、 java.util.concurrent パッケージの適切なユーティリィクラスを使うというのが通常、ベストアンサーです。 このコードは良く書かれており、 SMP 上で十分にテストされています。
おそらく最も安全なのは、クラスを不変にすることです。 String や Integer といったクラスのオブジェクトは、 いったんオブジェクトが作成されれば、 保持しているデータを変更することは出来ません。 それにより、あらゆる同期の問題を回避出来ます。 書籍 Effective Java 第 2 版 の「項目15: 可変性を最小限にする」に、 やり方が掲載されています。 特に、フィールドの “final” 宣言の重要性には注意してください。 (Bloch)
いずれの選択肢も取れない場合は、 Java の “synchronized” 文を使って、 複数のスレッドからアクセスされる可能性がある、 あらゆるフィールドを保護するべきです。 mutex が状況的に使用できないなら、 共有フィールドを “volatile” にすることも出来ますが、 スレッド間のやりとりを理解するために多大な注意を払わなければなりません。 volatile 宣言は、よくある並行プログラミングの誤りからあなたを救ってくれるわけではありません。 しかし、コンパイラの最適化や SMP の問題に関連した不可思議なエラーを回避するためには役立つでしょう。
Java のメモリモデルにおいては、 final フィールドへの代入は、 コンストラクタが完了しさえすれば、 すべてのスレッドから見えるようになります。 これにより、不変クラスのフィールドの正しい同期が保証されます。 構築途中のオブジェクトが他のスレッドから見えるようになった場合には、 この保証は適用されません。 安全な初期化の慣習に従う必要があります。 (Safe Construction Techniques in Java)
pthread ライブラリや VM ではいくつか便利な保証がなされています。 あるスレッドが新しいスレッドを作ったとき、 前者のスレッドがそれまでに行ったすべてのアクセスは、 新しいスレッドが開始されると直ちに、 その新しいスレッドから見えるようになります。 また、終了したスレッドが行っていたすべてのアクセスは、 そのスレッドに対して join() をすると、 見えるようになります。 これは、新しいスレッドのためのデータの準備や、 join したスレッドの結果を得るために、 余計な同期を行う必要はないということです。
プールされているスレッドとのやりとりにこの保証が効くかどうかは、 そのスレッドプールの実装によります。
C/C++ においては、 あるスレッドが mutex をアンロックする前に行ったすべてのアクセスが、 その後に同じ mutex に対してロックした別のスレッドから見えることが、 pthread ライブラリによって保証されています。 また、 条件変数に対して signal() や broadcast() を呼ぶ前に行われたあらゆるアクセスが、 それによって起床したスレッドから見えることも保証されています。
Java 言語のスレッドとモニタにも、それぞれ対応する操作について、同様の保証があります。
C および C++ 言語の標準規格は、 アトミック操作の洗練されたセットが含まれる方向に進化しつつあります。 選択可能なメモリバリアのセマンティクス (relaxed、consume、acquire、release、acq_rel、seq_cst から選べます) を含む、共通のデータ型に対する操作が網羅的に定義されます。
参考文献 に仕様書へのポインタがあるので、参照してください。
このドキュメントは、 単に表面をなでる程度よりはいくらか踏み込んでいますが、 それほど深く潜り込んではいません。 これは非常に幅広く、そして深いトピックです。 いくつかの領域については、さらなる探索が必要でしょう。
付録の 参考文献 の節に、 これらのトピックに付いて説明しているもっと良いドキュメントやウェブサイトへのリンクがあります。
本ドキュメントでは、理論的には発生する可能性のある、 たくさんの「奇妙な」事柄について、説明しています。 これらが現実の問題なのかどうか確信が持てないのであれば、 実例を見るのが良いでしょう。
Bill Pugh の Java メモリモデルの ウェブサイト に、テストプログラムがいくつかあります。 ReadAfterWrite.java は興味深いテストのひとつで、 以下のようなものです。
| スレッド 1 | スレッド 2 |
|---|---|
for (int i = 0; i < ITERATIONS; i++) { |
for (int i = 0; i < ITERATIONS; i++) { |
ただし、 a と b は volatile int フィールドで、 AA と BB は普通の int 配列です。
これがやろうとしているのは、 値が volatile に書き込まれれば、 その volatile からの次の読み込みは新しい値が見える、 というのを VM が保証しているかどうか調べる、 というものです。 このテストコードは数百万かそれくらいの回数ループし、 完了後に結果を調べておかしなところを見つけます。
実行が終わると、 AA と BB は徐々に増加していく整数で埋められるはずです。 2 つのスレッドは、予測可能な方法でお互い交互に走るわけではありませんが、 2 つの配列の内容の間には一定の関係があることを assert できます。 例えば、以下の実行片を考えてみてください。
| スレッド 1 | スレッド 2 |
|---|---|
(初期状態 a == 1534) |
(初期状態 b == 165)
|
(ここでは、 片方のスレッドの結果が相手に見えることが解りやすいよう、 2 つのスレッドがお互い順序に実行されるかのように書いていますが、 実際のケースではそうではありません。)
スレッド 2 の AA[166] への代入を見てください。 スレッド 2 が 166 回目の繰り返しを行っていた時点において、 スレッド 1 が 1536 回目の繰り返しを行っていたことがスレッド 2 に見えている、 という事実がわかります。 ステップをひとつ未来に進めれば、 スレッド 1 の 1537 回目の繰り返し時点で、 スレッド 2 が 166 回目 (以降) であることをスレッド 1 が見ることができるはずです。 BB[1537] は 167 を保持しているので、 たしかに正常に動作していたことがわかります。
では、もし b への volatile 書き込みを見ることが出来なければどうなるか、 考えてみましょう。
| スレッド 1 | スレッド 2 |
|---|---|
(初期状態 a == 1534) |
(初期状態 b == 165) |
今回 BB[1537] は 165 を保持しており、これは期待したより小さな値です。 問題があることが分かると思います。 簡単に言うと、 i=166 に対して BB[AA[i]+1] < i です。 (a への書き込みをスレッド 2 から見ることによっても、 失敗を知ることが出来ます。 例えば、 更新と代入をミスって AA[166] = 1535 のようになれば、 BB[AA[166]+1] == 165 が得られます。)
SMP の ARM デバイス上の Dalvik (Android 3.0 “Honeycomb” またはそれ以降) を使ってこのテストプログラムを実行しても、失敗することはありません。 もし a と b の宣言から “volatile” キーワードを削除すれば、 テストは一貫して失敗するでしょう。 このプログラムは、 a と b のアクセスに逐次一貫性の順序付けが VM によって為されているかをテストしています。 変数が volatile であれば、正常な動作しか見ることは出来ません。 (このコードをシングルプロセッサデバイスで動かしたり、 他の何かが CPU をヘビーに使用していてカーネルがテストスレッドを別々のコアにスケジュールできない場合も、 同様に成功しか見ることが出来ません。)
変更したテストプログラムを何度か動かしてみると、 毎回同じ場所で失敗するわけではないことに気付くかもしれません。 テストは、同じ操作を百万回行っており、 そのうち一度でもアウトオブオーダーアクセスが見えただけで失敗となるので、 一貫して失敗しているのです。 実際のところ、失敗は滅多に起きず、見つけるのは困難です。 このテストプログラムは、 たまたま上手く動くだけの壊れた VM に対して、 非常に効果的です。
(これは、ほとんどのプログラマが自分で実装するものではありませんが、 議論の中身は理解に役立つでしょう。)
Java の volatile アクセスをもう一度考えてみましょう。 以前、取得読み込みや解放書き込みとの類似性について述べました。 これは開始点ではありますが、それで終わりではありません。
始めにデッカーのアルゴリズムの一部を見てみましょう。 flag1 と flag2 の初期値は両方とも false です。
| スレッド 1 | スレッド 2 |
|---|---|
flag1 = true |
flag2 = true |
これらを合わせて考えると、 上の例の volatile アクセスはすべてのスレッドにプログラム順序で見えることが保証されます。 そのため、 2 つのスレッドが「クリティカルな処理」を同時に実行することは、決してありません。
もうひとつこれについて考える方法は、 データ競合 の視点で見ることです。 順序付けされていない 2 つのスレッドが、 メモリ上の同じ場所に同時にアクセスを行い、 少なくとも片方がその場所への書き込みであり、 少なくとも片方が同期処理でない場合、 データ競合が起きます。 (Boehm and McKenney) Java のメモリモデルによれば、 データ競合が起きないプログラムは逐次一貫性のあるマシンで実行されたかのように振る舞わねばならないことになっています。 flag1 と flag2 は両方とも volatile であり、 volatile アクセスは同期処理であると見なされるので、 ここにデータ競合はなく、 このコードは逐次一貫性のある方法によって実行されなければなりません。
以前の節で見たように、 2 つの操作の間には書き込み/読み込みバリアを入れる必要があります。 VM で実行される volatile アクセスのコードは、 以下のような感じになるでしょう。
| volatile 読み込み | volatile 書き込み |
|---|---|
reg = A |
書き込み/書き込みバリア |
volatile 読み込みは、単なる取得読み込みです。 volatile 書き込みは、解放書き込みに似ていますが、 書き込み前の読み込み/書き込みバリアが無くなり、 書き込み後の書き込み/読み込みバリアが追加されています。
ここで実際に保証しようとしていることは何でしょうか。 それは、 (スレッド 1 を例にとると) flag2 の読み込みよりも前に flag 1 への書き込みが見えるようにすることです。 代わりに volatile 読み込みの前に書き込み/読み込みバリアを張っても同じ結果を得られますが、 読み込みの頻度は書き込みよりも多い傾向にあるので、 書き込み側にバリアを張った方が有利なのです。
アーキテクチャによっては、 volatile 書き込みの実装にアトミック操作を用いることで、 明示的な書き込み/読み込みバリアを省略できる場合があります。 例えば x86 では、アトミック操作によってフルバリアが張られます。 ARM の LL/SC 操作にはバリアが含まれていませんので、 ARM では明示的にバリアを張る必要があります。
(このほとんどは Doug Lea と彼の “JSR-133 Cookbook for Compiler Writers” のページのおかげです。)
より深くあるいはより幅広く扱っているウェブページやドキュメントを挙げておきます。 より一般的に役立つ記事がリストの上に来るように並べています。