メモリの順序

メモリ順序とは、 CPUによるコンピュータメモリへのアクセス順序のことである。メモリ順序は、コンパイル時にコンパイラによって生成される命令の順序と、実行時に CPU が実行する順序の両方に依存する。^{[1] [2]ただし、メモリ順序は}マルチスレッドとメモリマップド I/O以外ではほとんど問題にならない。コンパイラまたは CPU が操作の順序を変更する場合、その順序変更によって通常のシングルスレッドコードの出力が変更されないことを必ず確認する必要があるためである。^{[1] [2] [3]}

メモリ順序は、操作の順序が変更できないか、変更してもどのスレッドにも目に見える影響がない場合、強いまたは逐次的に一貫していると言われます。 ^{[1] [4]}逆に、あるスレッドが別のスレッドから発生する操作の順序を予測できない場合、メモリ順序は弱いまたは緩和されていると言われます。 ^{[1] [4]}多くの単純に書かれた並列アルゴリズムは、弱いメモリ順序でコンパイルまたは実行すると失敗します。^{[5] [6]}この問題は、プログラムにメモリバリア命令を挿入することで解決されることがよくあります。 ^{[6] [7]}

キャッシュやメモリバンクなどの異なるタイプのメモリの帯域幅を最大限に活用するために、完全に強い順序付けを保証するコンパイラやCPUアーキテクチャはほとんどありません。^{[1] [5]}一般的に使用されているアーキテクチャの中で、x86-64プロセッサは最も強いメモリ順序を備えていますが、メモリストア命令をメモリロード命令の後まで延期する場合があります。^{[5] [8]}その一方で、DEC Alphaプロセッサはメモリ順序について実質的に保証しません。^[5]

ほとんどのプログラミング言語には、定義された順序でステートメントを実行する実行スレッドの概念があります。従来のコンパイラは、高レベルの式を、基礎となるマシン レベルのプログラム カウンターを基準とした一連の低レベルの命令に変換します。

実行の影響は、2 つのレベルで確認できます。高レベルではプログラム コード内、高レベルではマシン レベル、並行プログラミングで他のスレッドや処理要素から見た場合、またはマシン状態にアクセスできるハードウェア デバッグ補助機能を使用したデバッグ中 (このサポートの一部は、実行コアとは別に機能的に独立した回路として CPU またはマイクロコントローラに直接組み込まれていることが多く、実行コア自体は実行状態の静的検査のために停止している場合でも動作し続けます) です。コンパイル時のメモリ順序は前者に関係し、これらの他のビューには関係しません。

コンパイル時に、ハードウェア命令は、高レベル コードで指定されているよりも細かい粒度で生成されることがよくあります。手続き型プログラミング言語で観察できる主な効果は、名前付き変数に新しい値を割り当てることです。

  合計 = a + b + c;
  print(合計);

print 文は、変数 sum に割り当てる文の後に続くため、print 文が計算された変数を参照する場合、sumこの結果は、前の実行シーケンスの観察可能な効果として参照されます。プログラム シーケンスの規則で定義されているように、print関数呼び出しが を参照する場合sum、 の値は、sum変数に対して最後に実行された割り当てsum(この場合は直前の文) の値である必要があります。

マシン レベルでは、1 つの命令で 3 つの数値を加算できるマシンはほとんどないため、コンパイラはこの式を 2 つの加算演算に変換する必要があります。プログラム言語のセマンティクスによって、コンパイラが式を左から右の順序で変換するように制限されている場合 (例)、生成されたコードは、プログラマが元のプログラムで次のステートメントを記述したように見えます。

  合計 = a + b;
  合計 = 合計 + c;

コンパイラが加算の結合法則を利用することを許可されている場合、代わりに次のコードが生成される場合があります。

  合計 = b + c;
  合計 = a + 合計;

コンパイラが加算の交換法則を利用することも許可されている場合、代わりに次のコードが生成される場合があります。

  合計 = a + c;
  合計 = 合計 + b;

ほとんどのプログラミング言語の整数データ型は、整数オーバーフローがない場合に数学の整数の代数にのみ従い、ほとんどのプログラミング言語で使用できる浮動小数点データ型の浮動小数点演算は丸め効果において可換ではなく、式の順序の影響が計算結果の小さな違いに現れることに注意してください (ただし、小さな初期の違いは、より長い計算では任意の大きな違いに連鎖する可能性があります)。

プログラマーが整数オーバーフローや浮動小数点の丸め効果を懸念している場合、同じプログラムを次のように元の高レベルでコーディングできます。

  合計 = a + b;
  合計 = 合計 + c;

多くの言語では、ステートメントの境界をシーケンス ポイントとして扱い、次のステートメントが実行される前に 1 つのステートメントのすべての効果が完了するように強制します。これにより、コンパイラは、表現されたステートメントの順序に対応するコードを生成するように強制されます。ただし、ステートメントはより複雑になることが多く、内部関数呼び出しが含まれる場合があります。

  合計 = f(a) + g(b) + h(c); 

マシン レベルでは、関数の呼び出しには通常、関数呼び出し用のスタック フレームのf設定が含まれ、これにはマシン メモリへの多数の読み取りと書き込みが含まれます。ほとんどのコンパイル言語では、コンパイラは関数呼び出し、g、 をh都合の良いように自由に順序付けることができるため、プログラム メモリの順序が大幅に変更されます。純粋な関数型プログラミング言語では、関数呼び出しが目に見えるプログラム状態 (戻り値以外) に副作用をもたらすことは禁止されており、関数呼び出しの順序によるマシン メモリの順序の違いは、プログラムの意味には重要ではありません。手続き型言語では、呼び出された関数に、 I/O 操作 の実行 や、グローバル プログラム スコープでの変数の更新 などの副作用がある場合があり、どちらもプログラム モデルに目に見える影響を及ぼします。

繰り返しになりますが、これらの効果を気にするプログラマーは、元のソース プログラムを次のように表現する際に、より細心の注意を払うことができます。

  合計 = f(a);
  合計 = 合計 + g(b);
  合計 = 合計 + h(c);

ステートメント境界がシーケンス ポイントとして定義されているプログラミング言語では、関数はf、、を呼び出しg、hその正確な順序で実行する必要があります。

ここで、ポインタをサポートする C や C++ などの言語で、ポインタ間接参照を使用して表現された同じ合計を考えてみましょう。

  合計 = *a + *b + *c; 

式を評価することは、ポインタ*xの「逆参照」と呼ばれ、 の現在の値によって指定された場所のメモリからの読み取りを伴いますx。 ポインタからの読み取りの影響は、アーキテクチャのメモリ モデルによって決まります。 標準プログラム ストレージから読み取る場合、メモリ読み取り操作の順序による副作用はありません。組み込みシステムのプログラミングでは、メモリ マップされた I/Oが非常に一般的であり、メモリの読み取りと書き込みによって I/O 操作がトリガーされたり、プロセッサの動作モードが変更されたりするなど、非常に目立つ副作用があります。 上記の例では、今のところ、ポインタがこれらの副作用のない通常のプログラム メモリを指していると仮定します。 コンパイラは、これらの読み取りをプログラムの順序で適切に並べ替えることができ、プログラムから見える副作用はありません。

割り当てられた値もポインタ間接である 場合はどうなるでしょうか?

  *合計 = *a + *b + *c; 

ここで、言語定義では、コンパイラがこれを次のように分割することを許可する可能性は低いです。

  // コンパイラによって書き換えられたもの
  // 一般的に禁止されている
  *合計 = *a + *b;
  *合計 = *合計 + *c;

これはほとんどの場合効率的とは見なされず、ポインタ書き込みは目に見えるマシン状態に潜在的な副作用をもたらします。コンパイラはこの特定の分割変換を許可されていないsumため、値の式での 3 つのポインタ読み取りの後に のみ、メモリ位置への書き込みが論理的に続く必要があります。

しかし、プログラマーが整数オーバーフローの目に見えるセマンティクスを懸念し、次のようにステートメントをプログラム レベルで分割するとします。

  // プログラマーが直接作成したもの
  // エイリアシングの懸念あり
  *合計 = *a + *b;
  *合計 = *合計 + *c;

最初の文は 2 つのメモリ読み取りをエンコードします*sum。この読み取りは、 への最初の書き込みに先行する必要があります (順序は問いません)。2 番目の文は 2 つのメモリ読み取りをエンコードします (順序は問いません)。この読み取りは、 の 2 番目の更新に先行する必要があります*sum。これにより、2 つの加算操作の順序が保証されますが、アドレスエイリアシングという新しい問題が発生する可能性があります。つまり、これらのポインターはいずれも、同じメモリ位置を参照する可能性があります。

たとえば、この例では、*cと が同じメモリ位置にエイリアスされていると仮定し、両方の代わりに *sumを使ってプログラムの両方のバージョンを書き直します。*sum

  *合計 = *a + *b + *合計; 

ここでは問題はありません。 として最初に書いた の元の値は*cへの代入時に失われ*sum、 の元の値も同様に失われます*sumが、これはそもそも上書きされているため、特に問題にはなりません。

  // *c と *sum をエイリアスするとプログラムは次のようになります
  *合計 = *a + *b;
  *合計 = *合計 + *合計;

ここで、 の元の値は*sum最初のアクセスの前に上書きされ、代わりに次の代数的等価値が得られます。

  // 上記のエイリアスケースの代数的同等物
  *合計 = (*a + *b) + (*a + *b);

*sumステートメントの並べ替えにより、 にまったく異なる値が割り当てられます。

エイリアシング効果の可能性があるため、目に見えるプログラム効果を危険にさらすことなくポインター式を再配置することは困難です。一般的なケースでは、エイリアシングは効果がない可能性があるため、コードは以前と同様に正常に実行されているように見えます。しかし、エイリアシングが存在するエッジケースでは、重大なプログラムエラーが発生する可能性があります。これらのエッジケースが通常の実行ではまったく存在しない場合でも、悪意のある攻撃者がエイリアシングが存在する入力を考案する道が開かれ、コンピューターのセキュリティ侵害につながる可能性があります。

前のプログラムを安全に並べ替えると次のようになります。

  // 適切な型の一時ローカル変数'temp'を宣言します
  温度 = *a + *b;
  *合計 = 温度 + *c;

最後に、関数呼び出しを追加した間接的なケースを考えてみましょう。

  *合計 = f(*a) + g(*b); 

*aコンパイラは、どちらかの関数呼び出しの前にと を評価することを選択すること*bも、 の評価を*b関数呼び出しの後まで延期することfも、 の評価を*a関数呼び出しの後まで延期することもできますg。関数fと にgプログラムから見える副作用がない場合、3 つの選択肢はすべて同じプログラム効果を持つプログラムを生成します。fまたはの実装に、ポインタまたはgとのエイリアシングの対象となるポインタ書き込みの副作用が含まれる場合、3 つの選択肢はそれぞれ異なるプログラム効果を持つ可能性があります。 ab

一般に、コンパイル言語の仕様は、どのポインタが潜在的にエイリアス化されるか、どのポインタがそうでないか、コンパイラがコンパイル時に正式に判断できるほど詳細ではありません。最も安全な対処方法は、すべてのポインタが常に潜在的にエイリアス化されるとコンパイラが想定することです。このレベルの保守的な悲観主義は、エイリアスがまったく存在しないという楽観的な想定に比べて、ひどいパフォーマンスを生み出す傾向があります。

その結果、C/C++ などの多くの高水準コンパイル言語は、可能な限り最高のパフォーマンスを追求するためにコンパイラがコードの並べ替えで楽観的な仮定を行える場所と、セマンティック ハザードを回避するためにコンパイラがコードの並べ替えで悲観的な仮定を行える場所について、複雑で洗練されたセマンティック仕様を持つように進化しました。

現代の手続き型言語における副作用の最大のクラスは、メモリ書き込み操作を伴うため、メモリ順序に関するルールは、プログラム順序セマンティクスの定義における主要な要素です。上記の関数呼び出しの順序変更は、別の考慮事項のように見えるかもしれませんが、これは通常、関数呼び出しを生成する式内のメモリ操作と相互作用する、呼び出された関数の内部のメモリ効果に関する懸念に発展します。

最近のコンパイラは、 as-if ルールによってこれをさらに一歩進めて、目に見えるプログラムの意味に影響がなければ、どのような並べ替えも（ステートメント間であっても）許可されることがあります。このルールでは、変換されたコード内の演算の順序は、指定されたプログラム順序から大きく異なる場合があります。そのようなエイリアスが実際に存在する場合（これは通常、 未定義の動作 を示す不正な形式プログラムとして分類されます）、コンパイラが、個別のポインタ式にエイリアスの重複がないという楽観的な仮定を行うことが許可されている場合、コードの実行前または直接のコード検査の前に、積極的なコード最適化変換の悪影響を推測することは不可能です。未定義の動作の領域には、ほぼ無限の現れがあります。

正当なコンパイラ最適化の結果としてセマンティクスが変更される可能性のある不正なプログラムを記述しないように、言語仕様を参照するのはプログラマーの責任です。Fortranでは伝統的に、これらの問題を認識することがプログラマーに大きな負担となっており、システム プログラミング言語の C および C++ もそれに劣りません。

一部の高級言語では、ポインタ構造を完全に排除しています。これは、プロのプログラマーの間でも、このレベルの注意力と細部への注意を確実に維持するには高すぎると考えられるためです。

メモリ順序セマンティクスを完全に理解することは、この分野に精通しているプロのシステム プログラマーの間でも難解な専門分野であると考えられています。ほとんどのプログラマーは、自分のプログラミングの専門知識の範囲内でこれらの問題を適切に理解すれば十分です。メモリ順序セマンティクスの専門分野が最も深いのは、並行コンピューティングモデルをサポートするソフトウェア フレームワークを作成するプログラマーです。

ローカル変数へのポインタが外部に漏れた場合、その変数はエイリアシングがないとは想定できないことに注意してください。

  合計 = f(&a) + g(a); 

f関数が、提供された へのポインタを使用して何を行ったかはわかりません。これには、a関数が後にアクセスするグローバル状態にコピーを残すことも含まれますg。最も単純なケースでは、はf変数 に新しい値を書き込みa、この式は実行順序で不明確になってしまいます。は、ポインタ引数の宣言にconst 修飾子をf適用することで、これを明確に防止でき、式が適切に定義されます。したがって、C/C++ の現代の文化では、すべての実行可能なケースで関数引数の宣言に const 修飾子を提供することにやや強迫観念的になっています。

fC および C++ では、の内部で、危険な方法として const 属性を型キャストで削除することfを許可しています。が上記の式を破る可能性がある方法でこれを行う場合、そもそもポインタ引数の型を const として宣言すべきではありません。

他の高水準言語は、言語自体に提供されているこの保証に違反する抜け穴のない強力な保証に相当する宣言属性に傾いています。アプリケーションが別のプログラミング言語で記述されたライブラリをリンクする場合、この言語保証はまったく役に立ちません (ただし、これはひどく悪い設計であると見なされます)。

これらのバリアは、コンパイル時にコンパイラが命令を並べ替えることを防ぎます。実行時に CPU によって命令が並べ替えられることを防ぐものではありません。

• これらのGNUインラインアセンブラステートメントは、GCCコンパイラが読み取りコマンドと書き込みコマンドの順序を変更することを禁止します。^[9]

asm volatile("" ::: "メモリ");
__asm__ __volatile__ ("" ::: "メモリ");

• このC11/C++11関数は、コンパイラが読み取りコマンドと書き込みコマンドの順序を変更することを禁止します。^[10]

アトミックシグナルフェンス(メモリオーダー取得解放)

• Intel C++コンパイラ（ICC/ICL）は「フルコンパイラフェンス」組み込み関数を使用する：^{[11] [12]}

__メモリバリア()

• Microsoft Visual C++コンパイラ（MSVC）はx86/x64のみでいくつかの組み込み関数をサポートしています（これらはすべて非推奨です）: ^[13]

_ReadBarrier()
_WriteBarrier()
_ReadWriteBarrier()

多くのプログラミング言語では、さまざまな種類のバリアを他の操作 (ロード、ストア、アトミック インクリメント、アトミック コンペア、スワップなど) と組み合わせることができるため、その前または後 (またはその両方) に追加のメモリ バリアは必要ありません。対象となる CPU アーキテクチャに応じて、これらの言語構造は、ハードウェア メモリの順序保証に応じて、特別な命令、複数の命令 (バリアとロードなど)、または通常の命令に変換されます。

SMPシステム にはいくつかのメモリ一貫性モデルがあります。

• シーケンシャル一貫性（すべての読み取りとすべての書き込みが順序どおりに行われる）
• 緩やかな一貫性（一部の種類の並べ替えは許可されます）
  • ロード後にロードを並べ替えることができます（キャッシュの一貫性とスケーリングの向上のため）
  • 荷物は保管後に再注文できる
  • 店舗は店舗後に再注文可能
  • ロード後にストアを並べ替えることができます
• 弱い一貫性（読み取りと書き込みは任意に並べ替えられ、明示的なメモリバリアによってのみ制限されます）

一部のCPUでは

• アトミック操作はロードとストアによって順序を変更できます。^[14]
• 非一貫性の命令キャッシュ パイプラインが存在する可能性があり、これにより、特別な命令キャッシュ フラッシュ/リロード命令なしでは自己変更コードが実行されなくなります。
• 従属ロードは並べ替えることができます (これは Alpha に特有の機能です)。プロセッサが最初に何らかのデータへのポインタをフェッチし、次にデータをフェッチする場合、データ自体はフェッチされず、すでにキャッシュされていてまだ無効化されていない古いデータが使用されます。この緩和を許可すると、キャッシュ ハードウェアはよりシンプルで高速になりますが、読み取り側と書き込み側のメモリ バリアが必要になります。^{[15] Alpha ハードウェア (マルチプロセッサ}Alpha 21264システムなど) では、他のプロセッサに送信されたキャッシュ ラインの無効化は、従属ロード間で処理するように明示的に要求されない限り、デフォルトで遅延処理されます。Alpha アーキテクチャ仕様では、他の形式の従属ロードの並べ替えも許可されています。たとえば、実際のポインタが参照解除される前に推測によるデータ読み取りを行うなどです。

RISC-V メモリ順序モデル

世界気象機関

弱いメモリ順序（デフォルト）

TSO

店舗合計注文数（Ztso 拡張機能でのみサポートされます）

SPARC メモリ順序モード

TSO

店舗合計注文数（デフォルト）

RMO

リラックスメモリ順序（最近の CPU ではサポートされていません）

ピジョン

部分ストア順序（最近の CPU ではサポートされていません）

SMP をサポートする多くのアーキテクチャには、実行時に読み取りと書き込みをフラッシュするための特別なハードウェア命令があります。

• x86、x86-64

lfence (アセンブリ)、void _mm_lfence(void)
sfence (asm)、void _mm_sfence(void) [18] 
mfence (asm)、void _mm_mfence(void) [19]

• パワーPC

同期 (アセンブリ)

• ミップス

同期（アセンブリ）[20] [21]

• アイタニウム

mf (アズム)

• 力

dcs (アセンブリ)

• ARMv7 ^[22]

dmb (アセンブラ)
dsb (アセンブラ)
isb（アズム）

一部のコンパイラは、ハードウェア メモリ バリア命令を発行する 組み込みをサポートしています。

• GCC ^[23]バージョン4.4.0以降^[24]にはがあります__sync_synchronize。
• C11 および C++11 以降ではatomic_thread_fence()コマンドが追加されました。
• Microsoft Visual C++コンパイラにはWindows APIMemoryBarrier()ヘッダーにマクロがあります（非推奨）。^{[25] [13]}
• Sun Studio Compiler Suite ^[26]__machine_r_barrierには、、__machine_w_barrierおよびがあります__machine_rw_barrier。

• メモリモデル（プログラミング）

• 共有メモリ一貫性モデル: Sarita V Adve および Kourosh Gharachorloo によるチュートリアル
• 現代のマイクロプロセッサにおけるメモリ順序付け (Paul E McKenney 著)
• 弱い記憶モデルと強い記憶モデル (Jeff Preshing 著)
• Jade Alglave らによる正式なカーネル メモリ順序付けモデル。
• YouTubeでの IA (Intel アーキテクチャ) メモリ順序- Richard L Hudson による Google Tech Talk
• コンピュータアーキテクチャ - 定量的アプローチ。第 4 版。J Hennessy、D Patterson、2007 年。第 4.6 章