Android 用 SMP Primer

Android 3.0 以降のプラットフォーム バージョンは、マルチプロセッサ アーキテクチャをサポートするように最適化されています。このドキュメントでは、C、C++、Java プログラミング言語(以下、簡略化のために単に「Java」と呼びます)で対称型マルチプロセッサ システム用のマルチスレッド コードを作成する場合に生じる可能性がある問題を紹介します。このドキュメントは Android アプリのデベロッパーを対象とした入門書であり、テーマについて詳細に解説するものではありません。

はじめに

SMP は「Symmetric Multi-Processor(対称型マルチプロセッサ)」の頭字語です。2 つ以上のまったく同じ CPU コアがメインメモリへのアクセスを共有する設計を指します。数年前まで、Android デバイスはすべて UP(ユニプロセッサ)でした。

ほぼすべての Android デバイスには複数の CPU が搭載されていましたが、以前は、そのうちの 1 つだけがアプリの実行に使用され、その他は各種デバイス ハードウェア(無線通信など)の管理に使用されていました。CPU のアーキテクチャにはさまざまものがありましたが、その上で実行されるプログラムは、メインメモリを使用して相互に通信することができませんでした。

現在販売されているほとんどの Android デバイスは SMP 設計を中核として構築されているため、ソフトウェア デベロッパーにとって状況が少し複雑になっています。マルチスレッド プログラムにおける競合状態は、ユニプロセッサでは明白な問題を引き起こすことはありませんが、2 つ以上のスレッドが複数のコアで同時に実行されている場合は、定期的にエラーになる可能性があります。さらに、コードがさまざまなプロセッサ アーキテクチャ上で実行される場合や、同一アーキテクチャの各種実装で実行される場合には、程度の差はあるものの、エラーが発生しやすくなります。x86 で徹底的にテストされたコードが、ARM では動作しないかもしれません。また、コードを最新のコンパイラで再コンパイルすると、エラーが発生するようになることもあります。

以下では、その理由を説明し、コードが正しく動作できるようにするために必要な作業を紹介します。

メモリ一貫性モデル: SMP が一味違う理由

ここでは、複雑なテーマについて手短に概説します。不完全な内容もありますが、誤解を招くものや間違っているものではありません。次のセクションで説明するように、ここでの詳細は、通常は重要ではありません。

このテーマに関するさらに詳しい情報については、本ドキュメントの最後の参考資料をご覧ください。

メモリ一貫性モデル(単に「メモリモデル」と呼ばれることも多い)は、プログラミング言語またはハードウェア アーキテクチャによるメモリアクセスに関する保証を表します。たとえば、ある値をアドレス A に書き込んで、その次にある値をアドレス B に書き込む場合、メモリ一貫性モデルでは、すべての CPU コアにおいてこれらの書き込みがこの順序で行われることが保証されます。

多くのプログラマーがよく使用しているモデルは逐次一貫性です。このモデルは、Adve 氏、Gharachorloo 氏共著のレポートで次のように説明されています。

  • すべてのメモリ操作が一度に 1 つずつ実行されているように見える。
  • シングル スレッドのすべての操作が、そのプロセッサのプログラムで記述されている順序で実行されているように見える。

ここで、何の変哲もない非常にシンプルなコンパイラまたはインタープリタがあると仮定しましょう。これらは、ソースコード内の代入操作を、厳密に一致する順序で、アクセスごとに 1 命令ずつ、ロードおよびストア命令に変換します。また、簡素化のために、各スレッドが専用のプロセッサで実行されると仮定します。

コードを少し見ただけで、そのコードがメモリに対する読み取りと書き込みを行っていることがわかる場合、逐次一貫性のある CPU アーキテクチャでは、そのコードは読み取りと書き込みを期待される順序で行います。CPU が実際に命令の順序を変更することや、読み取りや書き込みを遅らせることはあり得ますが、CPU が命令をそのまま実行する以外のことを行っているかどうかをデバイスで実行中のコードが簡単に見分ける方法はありません(ここでは、デバイス ドライバのメモリマップド I/O は無視します)。

これらについて説明する場合、一般にリトマス試験と呼ばれる小規模なコード スニペットを考えると便利です。

以下の単純な例では、コードが 2 つのスレッドで実行されています。

スレッド 1 スレッド 2
A = 3
B = 5
reg0 = B
reg1 = A

これと今後すべてのリトマス試験の例では、メモリ位置を大文字(A、B、C)で表します。また、CPU レジスタを「reg」から始まる文字列で表します。すべてのメモリはゼロで初期化されます。命令は上から下に実行されます。上の例では、スレッド 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 を含む)には逐次一貫性があります。スレッドは OS カーネルによって切り替えられるため、インターリーブ方式で実行されているように見えます。ほとんどの SMP システム(x86 や ARM を含む)には逐次一貫性がありません。たとえば、ハードウェアがメモリに即座にアクセスして他のコアから参照可能になることがないよう、メモリにアクセスする途中でストアをバッファリングすることがよくあります。

ただし、詳細は大きく異なります。たとえば、x86 には逐次一貫性がありませんが、それでも、reg0=5 かつ reg1=0 となることは依然としてあり得ないことが保証されます。ストアはバッファリングされますが、その順序は維持されます。一方、ARM ではこのようにはなりません。ストアのバッファリング順序は維持されず、ストアが他のすべてのコアに同時に到達しない可能性があります。こうした違いはアセンブリ プログラマーにとって重要です。ただし、以下で説明するように、C、C++、Java プログラマーはこうしたアーキテクチャの違いを隠すようにプログラミングでき、またそのようにするべきです。

ここまでは、命令の順序を変更するのがハードウェアのみであるという非現実的な仮定を行いました。実際には、コンパイラもパフォーマンスの向上のために命令の順序を変更します。上の例では、スレッド 2 のその後のコードで reg0 が必要になる前に reg1 の値が必要になり、その結果、reg1 を先に読み込むようにコンパイラが判断するかもしれません。あるいは、それより前のコードで A がすでに読み込まれていて、A を再度読み込む代わりにその値を再利用するようにコンパイラが判断するかもしれません。いずれにしても、reg0 と reg1 の読み込み順序が変更される可能性があります。

ハードウェアまたはコンパイラで各メモリ位置へのアクセス順序を変更しても、シングル スレッドの実行には影響しないため、このような変更は可能です。しかも、パフォーマンスを大幅に向上させることができます。この後で説明するように、少し注意するだけで、こうした変更を行ってもマルチスレッド プログラムの結果に影響を及ぼさないようにすることができます。

コンパイラもメモリアクセスの順序を変更できるため、この問題は実際には、SMP にとって新しいものではありません。ユニプロセッサの場合でも、コンパイラは上の例の reg0 と reg1 の読み込み順序を変更でき、スレッド 1 のスケジュール設定を順序変更された命令間で行うことができます。しかし、コンパイラがたまたま順序変更を行わなければ、この問題は発生しないかもしれません。ほとんどの ARM SMP では、コンパイラによる順序変更が行われなかったとしても、たいていは順序変更が行われます。場合によっては、命令の実行に何度も成功した後に行われることもあります。アセンブリ言語でプログラミングしている場合を除き、SMP は一般に、元からあった問題を顕在化させる可能性を高めるだけです。

データ競合フリーのプログラミング

幸いなことに、これらの詳細について考えずに済む簡単な方法がたいていはあります。いくつかの簡単なルールに従えば、「逐次一貫性」の部分を除くこれまでのすべてのセクションの内容を忘れても、通常は問題ありません。しかし、これらのルールをうっかり破ってしまうと、他の面倒な問題が顕在化する可能性があります。

最近のプログラミング言語では、「データ競合フリー」と呼ばれるプログラミング スタイルが推奨されています。「データ競合」が発生しないようにし、コンパイラにデータ競合と認識される一部のコンストラクトの使用を回避しさえすれば、コンパイラおよびハードウェアにおいて逐次一貫性が実現される見込みがあります。これは実際には、メモリアクセスの順序変更が行われないようにするという意味ではありません。ルールに従った場合、メモリアクセスの順序が変更されていることを見分けるのが難しくなるという意味です。たとえるなら、ソーセージ工場の見学さえしなければ、ソーセージはおいしくて食欲をそそる食べ物であるというようなことです。データ競合とは、メモリアクセスの順序変更に関する醜い真実をあらわにするものなのです。

「データ競合」とは

データ競合は、2 つ以上のスレッドが同じ通常のデータに同時にアクセスし、そのうちの少なくとも 1 つがデータを変更する場合に発生します。「通常のデータ」とは、特にスレッド通信を目的とした同期オブジェクトではないものを表します。ミューテックス、条件変数、Java の volatile、C++ のアトミック オブジェクトは通常のデータではなく、これらへのアクセスは競合が許容されます。実際に、これらは他のオブジェクトでのデータ競合を防止するために使用されています。

2 つのスレッドが同じメモリ位置に同時にアクセスするかどうかを決定するにあたり、上記のメモリアクセスの順序変更に関する議論は無視して、逐次一貫性を前提とすることができます。次のプログラムでは、AB が初期状態で false に設定されている通常のブール変数の場合、データ競合は発生しません。

スレッド 1 スレッド 2
if (A) B = true if (B) A = true

処理の順序は変更されないため、両方の状態が false に評価され、どちらの変数も更新されません。したがって、データ競合は起こり得ません。スレッド 1 での A からのロードと B へのストアの順序がなんらかの理由で変更された場合に起き得ることについて考える必要はありません。コンパイラではスレッド 1 を「B = true; if (!A) B = false」と書き換えて、順序を変更することはできません。これは、真っ昼間に町中でソーセージを作るようなものです。

データ競合は、整数などの基本的な組み込み型と、参照またはポインタで正式に定義されています。int への割り当てと同時にそれを別のスレッドで読み取る操作は、明らかにデータ競合です。ただし、C++ の標準ライブラリと Java Collections ライブラリはどちらも、ライブラリ レベルでデータ競合について推測できるように作成されています。同じコンテナへの同時アクセスがあり、そのうちの少なくとも 1 つが更新を行う場合を除き、これらのライブラリを使用することでデータ競合が発生しないことが約束されます。あるスレッドで set<T> を更新すると同時に、別のスレッドでそれを読み取ると、ライブラリがデータ競合を引き起こします。そのためこのような操作は、非公式に「ライブラリ レベルのデータ競合」とみなすことができます。逆に、あるスレッドである set<T> を更新し、別のスレッドで別のものを読み取っても、データ競合は発生しません。この場合、ライブラリを使用することで(低レベルの)データ競合が発生しないことが約束されるためです。

通常、データ構造体内のさまざまなフィールドに同時にアクセスしても、データ競合が発生することはあり得ません。ただし、このルールには重要な例外が 1 つあります。それは、C または C++ ではビット フィールドの連続する並びが 1 つの「メモリ位置」として扱われるというものです。このような並びのビット フィールドへのアクセスは、データ競合の存在を確認するために、そのすべてに対するアクセスとして扱われます。これは、一般的なハードウェアでは、隣接するビットに対する読み取りと再書き込みを行わずに個々のビットを更新することができないことの表れです。Java のプログラミングでは類似の問題はありません。

データ競合の回避

最近のプログラミング言語は、データ競合を回避するためのさまざまな同期メカニズムを備えています。最も基本的な方法を以下に示します。

ロックまたはミューテックス
ミューテックス(C++11 の std::mutex、または pthread_mutex_t)、あるいは Java の synchronized ブロックを使用すると、特定のコード セクションが同じデータにアクセスする他のコード セクションと同時に実行されないようにすることができます。これらと他の同様の機能を総称して「ロック」と呼んでいます。共有データ構造体にアクセスする前に特定のロックを常に取得し、後で解放することにより、データ構造体にアクセスする際のデータ競合を防ぐことができます。また、更新とアクセスがアトミックであることが保証されます。つまり、更新やアクセスの最中にデータ構造体に対する他の更新を実行できないようにすることができます。当然ながら、これがデータ競合を防ぐための最も一般的な方法です。Java の synchronized ブロックや、C++ の lock_guard または unique_lock を使用すると、例外の発生時にロックを適切に解放できます。
volatile / atomic 変数
Java の volatile フィールドを使用すると、データ競合を発生させることなく同時アクセスが可能になります。2011 年以後、C および C++ では、同様のセマンティクスを持つ atomic 変数およびフィールドがサポートされています。これらは、1 つの変数に対する個々のアクセスがアトミックであることを保証するだけなので、一般にロックよりも使うのが難しいとされています(C++ では通常、インクリメントなどの単純な読み取り / 変更 / 書き込み操作もアトミックになります。Java では、そのための特別なメソッドの呼び出しが必要になります)。ロックとは異なり、他のスレッドが長いコード シーケンスに干渉するのを防ぐために volatile または atomic 変数を直接使用することはできません。

C++ と Java では volatile の意味が大きく異なることに注意する必要があります。C++ では、volatile を使用してもデータ競合を防ぐことはできませんが、古いコードでは atomic オブジェクトを使用できないため、回避策として使用されることがよくあります。この方法は、現在は推奨されていません。C++ では、複数のスレッドから同時にアクセス可能な変数として atomic<T> を使用してください。C++ の volatile は、デバイスのレジスタなどに適しています。

C / C++ の atomic 変数または Java の volatile 変数を使用すると、他の変数に対するデータ競合を防ぐことができます。flag が型 atomic<bool> または atomic_bool(C / C++)、あるいは volatile boolean(Java)を持つように宣言されており、初期状態で false に設定されている場合、次のスニペットではデータ競合は発生しません。

スレッド 1 スレッド 2
A = ...
  flag = true
while (!flag) {}
... = A

スレッド 2 は flag が設定されるまで待機するため、スレッド 2 での A へのアクセスは、スレッド 1 での A への割り当てと同時ではなく、その後に行う必要があります。したがって、A ではデータ競合は発生しません。volatile / atomic によるアクセスは「通常のメモリアクセス」ではないため、flag に対する競合はデータ競合とはみなされません。

前述のリトマス試験のようなコードを期待どおりに動作させるには、メモリアクセスの順序変更を十分に防ぐ、または隠すように実装する必要があります。このため通常は、volatile / atomic によるメモリアクセスのほうが通常のアクセスよりもかなりコストがかかります。

前述の例はデータ競合フリーですが、Java の Object.wait() または C / C++ の条件変数とロックを組み合わせることで、多くの場合、ループで待機する必要がなく、電池の消耗を抑えることができる優れたソリューションを実現できます。

メモリアクセスの順序変更が認識される状況

データ競合フリーのプログラミングにより、通常は、メモリアクセスの順序変更に関する問題を明示的に扱う必要がなくなります。ただし、順序変更が明白になる状況がいくつかあります。
  1. プログラムに意図しないデータ競合につながるバグがある場合、コンパイラおよびハードウェアによる変換が認識されるようになり、プログラムの動作を予期できなくなる可能性があります。たとえば、前述の例で flag を volatile として宣言するのを忘れた場合、スレッド 2 で A が初期化されない可能性があります。あるいは、スレッド 2 のループ中に flag を変更できない可能性があるとコンパイラが判断し、プログラムを次のように変換するかもしれません。
    スレッド 1 スレッド 2
    A = ...
      flag = true
    reg0 = flag; while (!reg0) {}
    ... = A
    デバッグでは、flag が true であるにもかかわらず、ループが永遠に続くことがあります。
  2. C++ には、競合が発生していない場合でも逐次一貫性を明示的に緩和する機能が用意されています。アトミック操作では、明示的な memory_order_ 引数を受け取ることができます。同様に、java.util.concurrent.atomic パッケージには、lazySet() をはじめとする、より制限の多い類似の機能セットが用意されています。また、Java プログラマーは、似たような効果を出すために意図的なデータ競合を使用することがあります。これらはすべて、プログラミングの複雑さの点で大きな犠牲を伴いますが、パフォーマンスの向上をもたらします。パフォーマンスの向上については、以下で簡単に説明します。
  3. C / C++ のコードには、最新の言語標準に完全に準拠しておらず、古いスタイルで作成されているものがあります。そのようなコードでは、atomic 変数ではなく volatile 変数が使用され、いわゆるフェンスまたはバリアを挿入することによってメモリの順序変更が明示的に禁止されています。このようなコードを作成するには、アクセスの順序変更に関する明示的な根拠が必要になるほか、ハードウェア メモリモデルを理解する必要があります。このようなコーディング スタイルは今でも Linux カーネルで使用されています。ただし、新しい Android アプリでは使用しないでください。このトピックについては、ここではこれ以上は説明しません。

実習

メモリの一貫性に関する問題のデバッグは非常に困難です。ロック、atomicvolatile の宣言が行われていないことが原因で一部のコードが古いデータを読み取っている場合、デバッガでメモリダンプを調べても問題の原因がわからないことがあります。デバッガのクエリを発行できるようになるまで、CPU コアがすべてのアクセスを監視した可能性があり、その場合、メモリと CPU レジスタの内容が「あり得ない」状態に見えるようになります。

C での禁止事項

ここでは、不適切なコードの例と、その簡単な修正方法を紹介します。その前に、基本的な言語機能の使い方について説明します。

C / C++ と「volatile」

C / C++ の volatile 宣言は、極めて特殊な用途のツールです。この宣言により、コンパイラが volatile アクセスの順序変更や削除を行わないようにすることができます。これは、ハードウェア デバイスのレジスタや複数の位置にマッピングされているメモリにアクセスするコード、setjmp に関連するコードで役に立つことがあります。ただし、C / C++ の volatile は Java の volatile とは異なり、スレッド通信に対応した設計になっていません。

C / C++ での volatile データへのアクセスは、非 volatile データへのアクセスとの間で順序変更されることがあり、アトミック性の保証はありません。そのため、ユニプロセッサの場合でも、移植可能なコードでのスレッド間のデータ共有のために volatile を使用することはできません。C の volatile は通常、ハードウェアによるアクセスの順序変更を防ぐことができないため、マルチスレッドの SMP 環境で単独で使用すると、その有用性がいっそう低くなります。これが、C11 と C++11 が atomic オブジェクトをサポートしている理由です。代わりにこのオブジェクトを使用してください。

C / C++ の古いコードの多くは今でも、スレッド通信用に volatile を濫用しています。このようなコードは、volatile が明示的なフェンスとともに使用されている場合、またはメモリアクセスの順序が重要でないケースで使用されている場合であれば、マシンレジスタに適合するデータに対してはたいてい正しく動作します。しかし、将来のコンパイラで正しく動作するとは限りません。

ほとんどの場合は、アトミック操作ではなく、ロック(pthread_mutex_t、C++11 の std::mutex など)を使用するほうがよいでしょう。ただし実習のソリューションでは、アトミック操作を使用し、その使い方を示しています。

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

上のコードのアイデアは、構造体を割り当ててそのフィールドを初期化し、最後にそれをグローバル変数にストアすることによって「公開」するというものです。この時点で、他のすべてのスレッドから構造体を参照できますが、完全に初期化されているため問題はないでしょう。

問題は、コンパイラまたはプロセッサが gGlobalThingthing->x へのストアの順序を変更したことが原因で、フィールドが初期化される前に gGlobalThing へのストアが行われる可能性があることです。thing->x で読み取りを行う別のスレッドが、5、0、あるいは初期化されていないデータさえ参照する可能性があります。

ここでの重要な問題は、gGlobalThing に対するデータ競合です。スレッド 2 が useGlobalThing() を呼び出している間にスレッド 1 が initGlobalThing() を呼び出すと、gGlobalThing に対する読み取りと書き込みが同時に行われる可能性があります。

これは、gGlobalThing をアトミックとして宣言することによって修正できます。C++11 では次のようになります。

atomic<MyThing*> gGlobalThing(NULL);

これにより、他のスレッドから適切な順序で書き込みを参照できるようになります。また、別の状況では許容される他のなんらかのエラーモードにならないようにすることが保証されます。ただし、実際の Android ハードウェアではそのモードになることはほとんどありません。たとえば、一部分だけ作成された gGlobalThing のポインタを参照することはできません。

Java での禁止事項

関連する Java 言語の機能についてまだ説明していなかったので、まずそれらについて簡単に見ていきましょう。

Java は技術的には、コードをデータ競合フリーにする必要はありません。また、データ競合が存在する場合でも正しく動作するように注意深く作成された Java コードもわずかに存在します。ただし、こうしたコードの作成は極めて慎重に行う必要があるため、以下では概要のみを説明します。さらに悪いことに、こうしたコードの趣旨を規定したエキスパートでさえも、この仕様が正しいとは思わないようになっています(この仕様は、データ競合フリーのコードには適しています)。

ここでは、データ競合フリーのモデルに準拠することにします。このモデルに関しては、Java は基本的に C / C++ と同じ保証を提供します。繰り返しになりますが、Java には、java.util.concurrent.atomiclazySet() および weakCompareAndSet() の呼び出しをはじめ、逐次一貫性を明示的に緩和するプリミティブ型がいくつか用意されています。C / C++ と同様に、ここではこれらを無視することにします。

Java の「synchronized」キーワードと「volatile」キーワード

「synchronized」キーワードは、Java 言語の組み込みロック メカニズムを提供します。すべてのオブジェクトに「モニター」が関連付けられており、これを使用することで相互に排他的なアクセスを実現できます。2 つのスレッドが同じオブジェクトに対して「同期」しようとする場合、そのうちの 1 つが、もう一方が完了するまで待機します。

前述のとおり、Java の volatile T は C++11 の atomic<T> に似ています。volatile フィールドへの同時アクセスが可能なため、データ競合は発生しません。lazySet() などやデータ競合を無視する場合でも、結果として逐次一貫性があるようにする責任は Java VM にあります。

特に、スレッド 1 が volatile フィールドへの書き込みを行い、その後にスレッド 2 が同じフィールドから読み取りを行って、新たに作成された値を参照する場合、以前にスレッド 1 で行われたすべての書き込みをスレッド 2 でも参照できることが保証されます。メモリへの影響に関しては、volatile への書き込みはモニターの解放に似ており、volatile からの読み取りはモニターの取得に似ています。

C++ の atomic との大きな違いが 1 つあります。それは、Java で volatile int x; のように書くと、x++x = x + 1 と同じになるという点です。このコードは、アトミックなロードを行い、その結果をインクリメントして、アトミックなストアを行います。C++ とは異なり、インクリメントは全体としてはアトミックではありません。アトミックなインクリメント操作は java.util.concurrent.atomic で提供されています。

以下に、単調カウンタのシンプルで不適切な実装を示しますJava の理論と実践: volatile を扱う

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

get()incr() が複数のスレッドから呼び出されると仮定すると、get() が呼び出されたときにすべてのスレッドが現在のカウントを参照できるようにする必要があります。最大の問題は、mValue++ が実際には以下の 3 つの操作を行うことです。

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

2 つのスレッドが incr() を同時に実行すると、いずれかの更新が失われる可能性があります。インクリメントをアトミックにするには、incr() を「synchronized」として宣言する必要があります。

特に SMP に関してはさらに問題があります。get()mValueincr() と同時にアクセスできるという点で、まだデータ競合が存在します。Java のルールでは、get() の呼び出しが他のコードに対して順序変更されているように見える可能性があります。たとえば、2 つのカウンタを連続して読み取ると、結果が一致しないように見えることがあります。これは、順序変更された get() がハードウェアとコンパイラのどちらかから呼び出されたためです。この問題を修正するには、get() を synchronized として宣言します。この変更により、コードが明らかに正しくなります。

残念なことに、パフォーマンスの低下を招く恐れがあるロック競合が発生する可能性もあります。get() を synchronized として宣言する代わりに、mValue を「volatile」として宣言することも可能です(incr() には引き続き synchronize を使用する必要があります。そうしないと、mValue++ が単一のアトミック操作にならないためです)。これにより、データ競合をすべて回避できるようになるため、逐次一貫性が維持されます。incr() は、モニターの開始および終了のオーバーヘッドと、volatile ストアに関連するオーバーヘッドの両方が発生するため、いくらか低速になり、get() のほうが高速になります。そのため、競合が発生しない場合でも、読み取り数が書き込み数よりも圧倒的に多いときには、後者を使用することをおすすめします(同期されたブロックを完全に削除する方法については、AtomicInteger をご覧ください)。

以下に別の例を示します。これは、以前の C の例に似た形式になっています。

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

このコードには C のコードと同じ問題があります。つまり、sGoodies に対するデータ競合が発生します。そのため、goods のフィールドが初期化される前に、割り当て sGoodies = goods が行われる可能性があります。volatile キーワードを使用して sGoodies を宣言すると、逐次一貫性が復元され、期待どおりの動作になります。

sGoodies の参照自体のみが volatile であることに注意してください。その内部のフィールドへのアクセスは volatile ではありません。sGoodiesvolatile として宣言され、メモリアクセスの順序が適切に維持されると、フィールドへの同時アクセスができなくなります。ステートメント z = sGoodies.x は、MyClass.sGoodies の volatile ロードを実行し、続いて sGoodies.x の非 volatile ロードを実行します。ローカル参照 MyGoodies localGoods = sGoodies を作成すると、その後の z = localGoods.x は volatile ロードを実行しなくなります。

Java プログラミングの一般的なイディオムとして、悪名高い「ダブルチェック ロック」があります。

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 つ作成しています。インスタンスを作成する必要があるのは 1 回だけのため、専用の getHelper() 関数でインスタンスを作成して返します。2 つのスレッドがインスタンスを作成する競合状態を回避するには、オブジェクトの作成を同期する必要があります。ただし、呼び出しのたびに「synchronized」ブロックのオーバーヘッドに対処することは避けたいので、helper がその時点で null の場合にのみその処理を行います。

このコードでは、helper フィールドに対するデータ競合が発生します。別のスレッドでも helper == null が成立した場合に同時に設定できます。

これがどうして失敗するかを確認するために、C に似た言語に編集したかのように、同じコードを少し書き換えてみました(Helper’s コンストラクタのアクティビティを表現するために 2 つの整数フィールドを追加しました)。

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

ハードウェアまたはコンパイラが helper へのストアと x / y フィールドへのストアの順序を変更しないようにする方法はありません。別のスレッドが、helper が null でないことを検出するかもしれませんが、そのフィールドはまだ設定されていないため、すぐに使用することはできません。詳細とエラーモードについては、付録の「ダブルチェック ロックの問題点」のリンク、または『Effective Java, 2nd Edition』(Josh Bloch 著)の項目 71(「Use lazy initialization judiciously」)をご覧ください。

この問題は、次の 2 つの方法によって解決できます。

  1. 簡単な操作を行って外部チェックを削除します。これにより、synchronized ブロックの外部で helper の値を調べる必要がなくなります。
  2. helper volatile を宣言します。この些細な変更を行うだけで、例 J-3 のコードが Java 1.5 以降で正しく動作するようになります(これが本当であることを納得していただくには少し時間がかかるかもしれません)。

以下に、volatile の動作の例をもう 1 つ示します。

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

useValues() を見ても、スレッド 2 で vol1 に対する更新がまだ確認されていない場合は、data1 または data2 が設定されているかどうかは判断できません。vol1 に対する更新が確認されると、data1 に安全にアクセスして、データ競合を発生させずに正しく読み取れると判断できるようになります。ただし、ストアは volatile ストアの後に行われたため、data2 についてなんらかの仮定をすることはできません。

volatile を使用しても、互いに競合する他のメモリアクセスの順序変更を防ぐことはできません。また、マシンのメモリフェンス命令が生成されるとは限りません。volatile を使用して、別のスレッドが特定の条件を満たしている場合にのみコードを実行することで、データ競合を防ぐことができます。

手順

C / C++ では、C++11 の同期クラス(std::mutex など)を優先します。そうしない場合は、対応する pthread の操作を使用します。これには適切なメモリフェンスが含まれ、すべての Android プラットフォーム バージョンで適切(特に指定がない限り、「逐次一貫性のある」)かつ効率的な動作を実現します。メモリフェンスは正しく使用してください。たとえば、条件変数の待機は通知されずに誤って戻ることがあるため、ループ内に記述する必要があります。

実装しているデータ構造体が非常にシンプルな場合(カウンタなど)を除き、アトミック関数は直接使用しないことをおすすめします。pthread ミューテックスのロックとロック解除では、それぞれアトミック操作が 1 回必要になり、競合がない場合は 1 回のキャッシュミスより低コストであることがほとんどです。そのため、ミューテックスの呼び出しをアトミック操作で置き換えても、あまり節約にはなりません。重要なデータ構造体のロックフリー設計は、データ構造体に対する高度な操作がアトミック(明らかにアトミックな部分だけでなく全体として)に見えるように慎重に行う必要があります。

アトミック操作を使用する場合、memory_order または lazySet() によって順序付けを緩和することで、パフォーマンス上のメリットが得られる場合がありますが、ここまでに説明した内容よりもさらに深い理解が必要になります。これらを使用している既存のコードの大部分で、後になってバグが見つかっています。可能であれば、これらは使用しないでください。ユースケースが次のセクションで説明するどのユースケースにも正確に合致しない場合は、ご自身がエキスパートであるか、エキスパートに相談する必要があります。

C / C++ では、スレッド通信用に volatile を使用しないでください。

Java では、java.util.concurrent パッケージの適切なユーティリティ クラスを使用することで、多くの場合、同時実行に関する問題を最適に解決できます。コードを適切に作成でき、SMP で十分にテストできます。

ご自分でできる最も安全な対策は、オブジェクトを変更できないようにすることでしょう。Java の String や Integer などのクラスのオブジェクトで、オブジェクトの作成後に変更できないデータを保持することで、それらのオブジェクトに対するデータ競合のあらゆる可能性を回避できます。詳しくは、『Effective Java, 2nd Edition』Bloch 著の項目 15「Minimize Mutability」をご覧ください。特に、Java の「final」フィールドを宣言することの重要性に注目してください。

オブジェクトが変更不能の場合でも、なんらかの同期を行わずに別のスレッドと通信すると、データ競合が発生します。これは、Java では許容されることもありますが(以下を参照)、細心の注意を払う必要があり、脆弱なコードが生成される可能性もあります。パフォーマンスがそれほど重要でない場合は、volatile 宣言を追加してください。C++ では、適切な同期を行わずにポインタや参照を変更不能なオブジェクトに渡すことは、データ競合と同様にバグです。この場合、たとえば、受信側のスレッドにおいてストアの順序変更が原因でメソッド テーブル ポインタが初期化されないことがあるため、断続的なクラッシュが発生する可能性がかなり高くなります。

既存のライブラリ クラスと変更不能なクラスのどちらも適切でない場合は、Java の synchronized ステートメントまたは C++ の lock_guard / unique_lock を使用して、複数のスレッドからアクセス可能なすべてのフィールドに対するアクセスを保護する必要があります。ミューテックスが状況に適した動作をしない場合は、共有フィールドを volatile または atomic として宣言する必要があります。ただし、細心の注意を払い、スレッド間のやり取りを理解する必要があります。こうした宣言は、並行プログラミングに関する一般的な誤りを防ぐことはできませんが、コンパイラの最適化に関連する不可解なエラーや SMP の不具合の発生を防止するのに役立ちます。

オブジェクトへの参照をコンストラクタで「公開」しないでください(他のスレッドから使用できるようにしないでください)。これは、C++ ではそれほど重要ではありません。また、Java の「データ競合禁止」のアドバイスに従っている場合も重要度は高くありません。ただし、このアドバイスは適切であり、Java セキュリティ モデルが重要な役割を果たす状況で Java コードが実行される場合や、信頼性の低いコードが「リークされた」オブジェクト参照にアクセスすることによってデータ競合を引き起こす可能性がある場合は重要になります。また、警告を無視して、次のセクションで紹介する手法を使用する場合にも重要になります。詳しくは、Java の安全なコーディング テクニックをご覧ください。

弱いメモリ順序付けの詳細

C++11 以降には、データ競合フリーのプログラムに対する逐次一貫性の保証を緩和するための明示的なメカニズムが用意されています。アトミック操作用の明示的な memory_order_relaxedmemory_order_acquire(ロード専用)、および memory_order_release(ストア専用)引数はそれぞれ、デフォルト(通常は暗黙的な memory_order_seq_cst)より弱い保証を提供します。memory_order_acq_rel は、読み取り / 変更 / 書き込みのアトミック操作に対する memory_order_acquirememory_order_release の両方の保証を提供します。memory_order_consume の規定や実装はまだ十分に有用なものではないため、今のところは無視してください。

Java.util.concurrent.atomiclazySet メソッドは、C++ の memory_order_release ストアに似ています。Java の通常の変数は、memory_order_relaxed アクセスの代わりとして使用されることがありますが、これらは実際にはさらに弱い変数です。C++ とは異なり、volatile として宣言されている変数に対して順序指定なしでアクセスするための実際のメカニズムはありません。

これらを使用するパフォーマンス上の差し迫った理由がない限り、通常はこれらを使用しないでください。ARM のような弱く順序付けられたマシン アーキテクチャでは、これらを使用することで、通常、1 回のアトミック操作で数十程度のマシンサイクルを節約できます。x86 では、パフォーマンス上のメリットはストアに限定され、たいていはそれほど顕著なものではありません。いくらか直感に反していますが、コア数の増加とともにメモリシステムがより大きな制限要因になり、パフォーマンス上のメリットが減少する可能性があります。

弱く順序付けられたアトミックの完全なセマンティクスは複雑です。一般に、これらを使用するには言語ルールを正確に理解する必要があります(ここでは、詳しくは説明しません)。次に例を示します。

  • コンパイラまたはハードウェアは、ロックの取得および解放によってバインドされたクリティカル セクションに memory_order_relaxed アクセスを移動できます(このセクションから移動することはできません)。つまり、2 つの memory_order_relaxed ストアがクリティカル セクションで区切られている場合でも、これらを順不同で参照できることがあります。
  • 通常の Java 変数は、共有カウンタとして濫用されている場合、他の 1 つのスレッドでインクリメントだけが行われているとしても、別のスレッドでは減少しているように見えることがあります。しかし、C++ のアトミックな memory_order_relaxed では、このようにはなりません。

ここでは、こうしたルールに注意しながら、いくつかのイディオムを紹介します。これらは、弱く順序付けられたアトミックのユースケースの多くをカバーします。これらの多くは、C++ にのみ適用されます。

競合のないアクセス

変数をアトミックにすることは珍しくありません。その理由は、読み取りと書き込みが同時に行われることがあるためです。ただし、すべてのアクセスでこの問題が発生するわけではありません。たとえば、変数がクリティカル セクションの外部で読み取られることが原因で、変数をアトミックにしなければならないこともありますが、すべての更新はロックによって保護されます。この場合、同じロックによってたまたま保護される読み取りでは、同時に書き込みが行われることはあり得ないため、競合が発生することはありません。こうしたケースでは、memory_order_relaxed を使用して競合のないアクセス(この場合はロード)に注釈を付けることができます。しかも、C++ コードの正確さは変わりません。ロックの実装では、他のスレッドからのアクセスに対して必要なメモリの順序付けがすでに適用されています。また、アトミック アクセスに対して適用する必要がある順序付けの制約が他には基本的にないことが memory_order_relaxed によって規定されます。

Java には、これによく似たものはありません。

結果は正確さとして信頼されない

ヒントを生成するためにのみ競合するロードを使用する場合、ロード用にメモリの順序付けを適用しなくても通常は問題ありません。また、値が信頼できない場合、他の変数について何かを推論するために、結果を信頼して使用することはできません。そのため、メモリの順序付けが保証されなくても問題ありません。ロードの指定には memory_order_relaxed 引数を使用します。

この一般的な例として、C++ の compare_exchange を使用して xf(x) にアトミックに置き換える方法があります。f(x) を計算する際の x の初期ロードでは、信頼性は必要ありません。間違った思い込みをすると、compare_exchange が失敗し、再試行することになります。x の初期ロードで memory_order_relaxed 引数を使用しても問題ありません。実際の compare_exchange のメモリの順序付けのみが重要になります。

アトミックに変更された未読のデータ

複数のスレッドからデータが同時に変更されることがときどきありますが、並列計算が完了するまでデータは確認されません。たとえばカウンタは、複数のスレッドから同時に(たとえば、C++ の fetch_add() または C の atomic_fetch_add_explicit() を使用して)アトミックにインクリメントされますが、これらの呼び出しの結果は常に無視されます。結果として得られる値は、すべての更新の完了後に、最後に読み取られるだけです。

この場合、このデータに対するアクセスの順序が変更されたかどうかを判断する方法はないため、C++ のコードで memory_order_relaxed 引数を使用することがあります。

この一般的な例として、単純なイベント カウンタがあります。これは非常に一般的なため、このケースについて所見を述べるだけの価値はあります。

  • memory_order_relaxed を使用することでパフォーマンスが向上しますが、すべての更新においてカウンタを保持するキャッシュ ラインに排他的にアクセスする必要があるという、最も重要なパフォーマンスの問題には対処できません。そのため、新しいスレッドがカウンタにアクセスするたびにキャッシュミスが発生します。更新がスレッド間で頻繁かつ交互に行われる場合、たとえば、スレッド ローカルなカウンタを使用して最後に合計することで、共有カウンタを毎回更新しないようにするほうがはるかに高速です。
  • この手法は前のセクションの方法と組み合わせることができます。つまり、すべての操作で memory_order_relaxed を使用することで、近似値と信頼できない値の更新中にそれらを同時に読み取ることが可能です。ただし、結果として得られた値をまったく信頼できない値として扱うことが重要です。カウントが 1 回インクリメントされたように見えるというだけで、別のスレッドで、インクリメントが実行された時点に達したとみなすことはできません。それより前のコードでインクリメントの順序が変更された可能性もあります(前述の類似のケースに関しては、C++ でこのようなカウンタをロードする場合、同一スレッドでの前回のロードより小さい値を返さないことが保証されます。もちろん、カウンタがオーバーフローした場合は除きます)。
  • カウンタの推定値を計算するコードでは、アトミックな(またはアトミックでない)個々の読み取りと書き込みを実行するものの、インクリメントを全体としてアトミックにしないようにすることがよくあります。よく議論になるのは、これがパフォーマンス カウンタなどにとって「十分に近似」かどうかという点です。通常はそうではありません。更新が十分頻繁に行われている場合(おそらく、皆様の関心があるケース)、通常はカウントの大部分が失われます。クアッドコア デバイスでは、半分以上のカウントが失われることも少なくありません(簡単なエクササイズ: カウンタが 100 万回更新されるが、カウンタの最終的な値が 1 になる、2 つのスレッドのシナリオを作成してください)。

フラグでの単純なやり取り

memory_order_release ストア(または読み取り / 変更 / 書き込み操作)では、書き込まれた値が memory_order_acquire ロード(または読み取り / 変更 / 書き込み操作)によって後で読み取られると、memory_order_release ストアより前に実行されたストア(通常またはアトミック)もすべて監視されます。逆に、memory_order_release より前に実行されるロードでは、memory_order_acquire ロードの後に実行されたストアは監視されません。このため、memory_order_relaxed とは異なり、こうしたアトミック操作を使用して、スレッドの進行状況を別のスレッドに伝えることができません。

たとえば、上の C++ でのダブルチェック ロックの例は、次のように書き換えることができます。

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

取得ロードおよび解放ストアでは、null でない helper を参照すると、その正しく初期化されたフィールドも参照します。また、競合のないロードで memory_order_relaxed を使用できるよう、事前の測定値も取り入れています。

Java プログラマーは、helperjava.util.concurrent.atomic.AtomicReference<Helper> として表し、lazySet() を解放ストアとして使用するかもしれません。ロード操作では、引き続き get() のプレーンな呼び出しを使用するでしょう。

どちらの場合も、パフォーマンスの調整は初期化パスに集中しましたが、これがパフォーマンス上重要になることはほとんどありません。より読みやすい妥協案は次のようになります。

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

このコードは同様の高速パスを提供しますが、パフォーマンスが重要でない低速パスでは逐次一貫性のあるデフォルトの操作を使用します。

helper.load(memory_order_acquire) はこのコードでも、helper へのプレーンな(逐次一貫性のある)参照と同じコードを Android が現在サポートしているアーキテクチャ上に生成する可能性があります。実のところ、このコードで最も有益な最適化は、myHelper を導入して 2 回目のロードを行わないようにすることかもしれません。ただし、将来のコンパイラではこの操作が自動化される可能性があります。

取得と解放の順序付けを行っても、ストアの視覚的な遅延を防ぐことはできません。また、ストアが他のスレッドから一貫した順序で参照できるようになるとは限りません。そのため、Dekker の相互排他アルゴリズムで例示されている、扱いにくいもののかなり一般的なコーディング パターンはサポートされません。このアルゴリズムでは、すべてのスレッドがまず、なんらかの処理を行う必要があることを示すフラグを設定します。スレッド t のフラグが設定されている場合、他のどのスレッドも処理を行おうとしておらず、スレッド t で処理を安全に続行できることが通知され、干渉が存在しないことを確認できます。t のフラグがまだ設定されているため、他のスレッドは処理を続行することができません。これは、取得と解放の順序付けを利用してフラグにアクセスすると失敗します。誤って続行された後では、スレッドのフラグの他のスレッドからの参照を防止できないためです。デフォルトの memory_order_seq_cst では防止されます。

変更不能なフィールド

オブジェクト フィールドが最初の使用時に初期化され、その後まったく変更されない場合、初期化の後で、弱く順序付けされたアクセスを使用した読み取りが可能になることがあります。C++ では、atomic として宣言し、memory_order_relaxed を使用してアクセスできます。Java では、volatile を使用せずに宣言し、特別な処置を行わずにアクセスできます。これには、以下のすべての条件が成立する必要があります。

  • フィールド自体の値からすでに初期化されているかどうかを判断できる必要があります。フィールドにアクセスするには、高速パスの test-and-return 値でフィールドを 1 回だけ読み取る必要があります。Java では、後者が極めて重要です。フィールドが初期化されているものとしてテストした場合でも、2 回目のロードでは、前に初期化された値が読み取られることがあります。C++ では、「1 回だけ読み取る」ルールを守ることをおすすめします。
  • 部分的な更新は参照できないようにする必要があるという点で、初期化とその後のロードの両方をアトミックにする必要があります。Java では、フィールドに long または double を指定してはなりません。C++ ではアトミックな割り当てが必要ですが、こうした割り当てを作成しても正しく機能しません。atomic の作成はアトミックでないためです。
  • 初期化されていない値を複数のスレッドが同時に読み取ることがあるため、初期化は繰り返し安全に行う必要があります。C++ の場合、これは一般に、すべてのアトミック型に対して課される「自明にコピー可能」の要件を満たすことで実現できます。ネストされた所有ポインタを持つ型は、コピー コンストラクタで割り当てを解除する必要があり、自明にコピー可能にはなりません。Java では、特定の参照型が許容されます。
  • Java の参照は、final フィールドのみを含む変更不能な型に制限されています。変更不能な型のコンストラクタでは、オブジェクトへの参照を公開してはなりません。この場合、Java final フィールドに関するルールにより、読み取り側が参照を参照する場合、初期化された final フィールドも参照できることが保証されます。C++ にはこれらのルールに類似するものがなく、(「自明にコピー可能」の要件の未達に加え)この理由からも所有オブジェクトを指すポインタは許容されません。

おわりに

本ドキュメントは表面をなぞるだけのものではありませんが、それほど深い内容を扱っているわけでもありません。本ドキュメントで扱っているのは、非常に幅広く深いトピックです。以下の内容についてさらに調べてみてください。

  • Java および C++ の実際のメモリモデルは、2 つのアクションが特定の順序で行われることが保証されるタイミングを規定する happens-before 関係の観点で表現されています。本ドキュメントでデータ競合について定義したときに、「同時」に行われる 2 つのメモリアクセスについてわかりやすく説明しました。「同時」は正式には、「どちらか一方が他方より前に行われることがない」のように定義されています。Java または C++ のメモリモデルの happens-before および synchronizes-with の実際の定義について学習することは有益です。「同時性」について直感的に理解することは一般には十分に有益ですが、特に、弱く順序付けされたアトミック操作を C++ で使用することを検討する場合は、こうした定義が役に立ちます(現在の Java の仕様では、lazySet() がくだけた表現で定義されているだけです)。
  • コードの順序変更の際にコンパイラでできることとできないことを調べます(JSR-133 仕様に、予期しない結果につながる法制的変革の好例がいくつか示されています)。
  • Java および C++ で変更不能なクラスを作成する方法を確認してください(「作成後に何も変更しない」以外にも方法はあります)。
  • 『Effective Java, 2nd Edition』の同時実行に関するセクションの推奨事項を取り入れます(たとえば、synchronized ブロック内では、オーバーライドされるメソッドは呼び出さないようにします)。
  • java.util.concurrent および java.util.concurrent.atomic API の詳細を読んで、使用可能な機能を確認します。(net.jcip.annotations の)@ThreadSafe@GuardedBy などの同時実行アノテーションを使用することを検討します。

付録の参考資料で、これらのトピックについて詳細に説明するドキュメントやウェブサイトのリンクを紹介しています。

付録

同期ストアの実装

(ほとんどのプログラマーは自分で同期ストアを実装することはありませんが、これについて議論することはすばらしいことです。)

int などの小さいサイズの組み込み型、および Android でサポートされているハードウェアでは、通常のロード命令とストア命令により、同じ位置をロードする別のプロセッサからストアの全体を参照できる場合と、まったく参照できない場合があります。そのため、「アトミック性」の基本概念が無料で提供されています。

すでに説明したように、これでは不十分です。また、逐次一貫性を確保するには、操作の順序変更が行われないようにし、メモリ操作が他のプロセスから一貫した順序で参照されるようにする必要もあります。賢明な選択を行い、操作の順序変更が行われないようにすれば、Android でサポートされているハードウェアでは、メモリ操作の参照が自動的かつ適切に行われるようになります。そのためここでは、逐次一貫性については大半を無視することにします。

メモリ操作の順序は、コンパイラとハードウェアによる順序変更を防止することによって保持できます。ここではハードウェアに注目します。

ARMv7、x86、MIPS でのメモリの順序付けは、「フェンス」命令によって行われます。フェンス命令は、フェンスより後に実行される命令がフェンスより先に実行される命令より前に参照できるようになるのをほぼ防止できます(これらは一般に「バリア」命令とも呼ばれますが、この命令よりはるかに多くの処理を行う pthread_barrier 方式のバリアと混同される恐れがあります)。フェンス命令の正確な意味はかなり複雑なトピックであり、複数の異なる種類のフェンスによって実現される保証がどのように相互作用するかや、それらの保証を通常はハードウェアによって実現される他の順序付けの保証とどのように組み合わせるかについて対処する必要があります。これは高度な概要であるため、詳細については軽く触れるだけにします。

最も基本的なタイプの順序付けの保証は、C++ の memory_order_acquirememory_order_release のアトミック操作によって実現されます。解放ストアより先に実行されるメモリ操作は、取得ロードの後で参照できる必要があります。そのため、ARMv7 の場合は以下を行います。

  • 適切なフェンス命令を使用して、ストア命令より先に実行する。これにより、優先するすべてのメモリアクセスの順序がストア命令によって変更されないようにすることができます(また、後でストア命令を使用すると、順序変更が不必要に防止されます)。
  • 適切なフェンス命令を使用して、ロード命令より後に実行する。これにより、ロードの順序がその後のアクセスによって変更されないようにすることができます(この場合も、少なくとも以前に実行されたロードによって不必要な順序付けが行われます)。

総合的に見て、C++ の取得と解放の順序付けについてはこれで十分です。Java の volatile、C++ の逐次一貫性のある atomic については、これらは必要ですが、十分ではありません。

他に必要なものを確認するために、すでに簡単に触れた Dekker のアルゴリズムの断片について考えてみましょう。flag1flag2 は C++ の atomic 変数または Java の volatile 変数で、どちらも最初は false に設定されています。

スレッド 1 スレッド 2
flag1 = true
if (flag2 == false)
    critical-stuff
flag2 = true
if (flag1 == false)
    critical-stuff

逐次一貫性とは、flagn に対する割り当てを最初に実行し、もう一方のスレッドのテストでそれを参照できる必要があることを意味します。したがって、これらのスレッドで「重要なこと」が同時に実行されることは決してありません。

ただし、取得と解放の順序付けに必要なフェンシングでは、各スレッドの最初と最後にフェンスを追加するだけで、ここでは役に立ちません。また、volatile / atomic ストアに続いて volatile / atomic ロードが実行される場合、この 2 つの順序が変更されないようにする必要があります。これは通常、フェンスを逐次一貫性のあるストアの前だけでなく後にも追加することによって実現できます(これも必要以上に強力な方法です。このフェンスは通常、それより前のすべてのメモリアクセスの順序付けを、それより後のすべてのメモリアクセスを基準として行うためです)。

代わりに、追加のフェンスを逐次一貫性のあるロードに関連付けることもできます。ストアはより低頻度のため、説明した規則は Android でよく使用されています。

前のセクションで説明したように、2 つの操作の間にストアまたはロードバリアを挿入する必要があります。VM で volatile アクセス用に実行されるコードは次のようになります。

volatile ロード volatile ストア
reg = A
fence for "acquire" (1)
fence for "release" (2)
A = reg
fence for later atomic load (3)

実際のマシン アーキテクチャは一般に、複数のタイプのフェンスを提供します。これらのフェンスによって各種のアクセスの順序付けが行われますが、フェンスのコストはそれぞれ異なる場合があります。フェンスの選択は複雑であり、ストアが他のコアから一貫した順序で参照できること、および複数のフェンスを組み合わせる場合に必要なメモリの順序付けが正しく構成されていることが必要かどうかに左右されます。詳しくは、ケンブリッジ大学のウェブページでアトミック操作と実際のプロセッサの関係のまとめをご覧ください。

x86 をはじめとする一部のアーキテクチャでは、「取得」および「解放」バリアは不要です。これは、ハードウェアが常に十分な順位付けを暗黙的に実行するためです。このため、x86 で実際に生成されるのは最後のフェンス(3)だけです。同様に、x86 では、読み取り / 変更 / 書き込みのアトミック操作に強力なフェンスが暗黙的に含まれます。このため、これらのアーキテクチャではフェンスが必要ありません。ARMv7 では、上記のすべてのフェンスが必要です。

ARMv8 では、Java の volatile、または C++ の逐次一貫性のあるロードおよびストアの要件を直接適用する LDAR および STLR 命令を使用できます。これらを使用することで、上記の不必要な順序変更に関する制約を回避できます。ARM の 64 ビット版の Android コードではこれらの命令を使用します。ここでは、ARMv7 のフェンスの配置に焦点を当てています(実際の要件を明らかにすることができるため)。

参考資料

より深く幅広い知識を得ることができるウェブページとドキュメントをご紹介します。リストの上にあるほうが一般に有用な記事になっています。

共有メモリ一貫性モデル: チュートリアル
1995 年に Adve と Gharachorloo によって執筆されたこの資料は、メモリ整合性モデルについてさらに深く掘り下げたい場合に適しています。
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
メモリバリア
問題を要約した短い記事です。
https://en.wikipedia.org/wiki/Memory_barrier
スレッドの基本
C++ および Java でのマルチスレッド プログラミングの入門書です(Hans Boehm 氏著)。データ競合や基本的な同期方法が解説されています。
http://www.hboehm.info/c++mm/threadsintro.html
Java Concurrency In Practice
2006 年に出版されたこの書籍では、さまざまなトピックが詳しく説明されています。Java でマルチスレッド コードを作成する場合はぜひお読みください。
http://www.javaconcurrencyinpractice.com
JSR-133(Java メモリモデル)に関するよくある質問
同期、volatile 変数、final フィールドの作成に関する説明を含め、Java メモリモデルがわかりやすく紹介されています(他の言語についての説明をはじめ、内容がやや古くなっています)。
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Java メモリモデルのプログラム変換の有効性
Java メモリモデルに残る問題についてのやや技術的な説明です。これらの問題は、データ競合フリーのプログラムでは発生しません。
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf
java.util.concurrent パッケージの概要
java.util.concurrent パッケージのドキュメントです。ページ下部の「Memory Consistency Properties」で、各種クラスによる保証が説明されています。
java.util.concurrent パッケージの概要
Java の理論と実践: Java の安全なコーディング テクニック
この記事では、オブジェクト作成時の参照のエスケープの危険性について詳しく説明し、スレッドセーフなコンストラクタのガイドラインを紹介します。
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Java の理論と実践: volatile を扱う
この記事では、Java の volatile フィールドでできることとできないことを説明しています。
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
ダブルチェック ロックの問題点
Bill Pugh 氏によって執筆されたこのドキュメントでは、volatile または atomic を使用せずにダブルチェック ロックを破る各種方法が詳しく説明されています。C / C++ および Java に関する内容が含まれています。
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] バリアのリトマス試験とクックブック
ARM SMP の問題が、ARM コードの短いスニペットを使用して説明されています。このページの例が具体的でない場合や、DMB 命令の正式な説明を確認したい場合は、こちらをお読みください。実行可能なコードでメモリバリア用に使用する命令についても説明されています(その場でコードを生成する場合にも役立つ可能性があります)。このドキュメントは ARMv8 より前から存在します。ARMv8 はメモリの順序付けに関するその他の命令もサポートしており、より強力なメモリモデルに移行されました(詳しくは、「ARM® Architecture Reference Manual ARMv8, for ARMv8-A architecture profile」をご覧ください)。
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Linux カーネルのメモリバリア
Linux カーネルのメモリバリアについてのドキュメントです。有用な例や ASCII アートが含まれています。
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21(C++ 標準)14882(C++ プログラミング言語)、1.10 節および 29 章(「アトミック操作ライブラリ」)
C++ のアトミック操作機能のドラフト標準です。このバージョンは C++14 標準に近く、C++11 からのこの内容に関する軽微な変更が含まれています。
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(概要: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf
ISO/IEC JTC1 SC22 WG14(C 標準)9899(C プログラミング言語)、7.16 節(「アトミックの <stdatomic.h>」)
ISO/IEC 9899-201x C のアトミック操作機能のドラフト標準です。詳細については、最近の不具合レポートもご確認ください。
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
C / C++11 とプロセッサの関係(ケンブリッジ大学)
C++ アトミックから一般的な各種プロセッサ命令セットへの変換がまとめられています(Jaroslav Sevcik 氏、Peter Sewell 氏共著)。
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
Dekker のアルゴリズム
「同時実行プログラミングにおける相互排除問題に対する最初の既知の正しい解決策」。Wikipedia の記事には完全なアルゴリズムが掲載されており、最新の最適化コンパイラと SMP ハードウェアと連携するためにどのように更新する必要があるかについて説明しています。
https://en.wikipedia.org/wiki/Dekker's_algorithm
ARM と Alpha の比較およびアドレス依存性に関するコメント
arm-kernel メーリング リストで Catalin Marinas 氏から送信されたメール。アドレスおよび制御依存性の概要がわかりやすく説明されています。
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
すべてのプログラマーがメモリに関して知っておくべきこと
Ulrich Drepper 氏による、さまざまな種類のメモリ、特に CPU キャッシュに関する非常に長く詳細な記事。
http://www.akkadia.org/drepper/cpumemory.pdf
ARM の弱い一貫性のメモリモデルに関する推論
この論文は ARM, Ltd. の Chong 氏と Ishtiaq 氏が執筆したもので、ARM SMP メモリモデルについて厳密かつわかりやすく説明されています。本ドキュメントでの「可観測性」の定義は、この論文から引用しています。このドキュメントも ARMv8 より前から存在します。
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711
コンパイラ作成者のための JSR-133 クックブック
Doug Lea 氏はこのクックブックを、JSR-133(Java メモリモデル)ドキュメントのガイドとして執筆しました。多くのコンパイラ作成者によって使用された Java メモリモデルの初歩的な実装ガイドラインが含まれており、いまだに広く引用されています。多くの場合、有用な情報が得られます。残念ながら、本ドキュメントで説明した 4 種類のフェンスは、Android でサポートされているアーキテクチャと相性がよくありません。前述の C++11 との関係は今では、Java にとっても、的確なソリューションを見つけるための有用な情報源になっています。
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO: x86 マルチプロセッサを対象とした、厳密かつ有用なプログラマー向けモデル
x86 メモリモデルが正確に説明されています。残念ながら、ARM メモリモデルの正確な説明は、非常にわかりにくい内容になっています。
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf