Geekly Articles each Day

Linuxメモリアクセスの障壁

この記事は、Linuxドキュメント（Documentation / memory-barriers.txt オンラインバージョン ）の一部として配布されているDavid HowellsとPaul E. McKenneyによる包括的なガイドの部分的な翻訳です。

カーネル/ドライバー開発者向けに読む必要があり、アプリケーションプログラマーにとって非常に有益です。

汎用メモリアクセスモデル。


次のシステムモデルを検討してください。
: : : : : : +-------+ : +--------+ : +-------+ | | : | | : | | | | : | | : | | | CPU 1 |<----->| Memory |<----->| CPU 2 | | | : | | : | | | | : | | : | | +-------+ : +--------+ : +-------+ ^ : ^ : ^ | : | : | | : | : | | : v : | | : +--------+ : | | : | | : | | : | | : | +---------->| Device |<----------+ : | | : : | | : : +--------+ : : :


各プロセッサは、一連のメモリアクセス操作を生成するプログラムを実行します。 抽象プロセッサには、メモリへのアクセスを整理する弱いモデルがあるため、実行可能コードに埋め込まれた因果関係に違反しない場合、実際にはアクセス操作をランダムな順序で実行できます。 同様に、このコードの実行結果がプログラムのソースコードと一致する場合、コンパイラは生成されたコードを自由に編成できます。

上の図では、プロセッサによって実行されるメモリ操作は、このプロセッサとシステムの境界を越える操作（破線で示されている）のように、システムの他のコンポーネントによって監視されます。

外部デバイスでの操作。


多くのデバイスには、メモリ内の特定のアドレスを持つ一連のレジスタ形式の制御インターフェイスがあります。 制御レジスタへのアクセス順序は、適切な動作のために重要です。 たとえば、ネットワークアダプタには、アドレスレジスタ（A）とデータレジスタ（D）を介してアクセスされる内部レジスタのセットがあります。 次のコードを使用して、内部レジスタ5を読み取ることができます。

  *A = 5; x = *D;

このコードは、次のメモリアクセスシーケンスを生成できます。

 1  *A = 5, x =  *D 2 x =  *D,  *A = 5

アドレスレジスタはデータレジスタの読み取り後に設定されるため、2番目のシーケンスはほぼ間違いなく間違った結果を返します。

保証。


プロセッサは、少なくとも以下を保証します。



さらに：


メモリアクセスの障壁とは何ですか？


上記のように、独立したメモリアクセス操作をランダムな順序で実行できます。これは、プロセッサ間またはプロセッサと外部デバイス間の相互作用の問題になる可能性があります。 コンパイラとプロセッサに順序を維持するよう指示するメカニズムが必要です。

メモリアクセスバリアはそのようなメカニズムです。 これにより、バリアの両側でメモリアクセス操作の部分的な順序付けが行われます。

プロセッサやその他のシステムデバイスは、操作の並べ替え、メモリアクセス操作の遅延と組み合わせ、早期データ読み取り、分岐予測、さまざまなタイプのキャッシュなど、多くのトリックを使用してパフォーマンスを向上させます。 メモリアクセスバリアは、これらのメカニズムを抑制するのに役立ちます。

バリアの種類。


バリアには主に4つのタイプがあります。

  1. 侵入障壁。

    書き込みバリアは、他のシステムコンポーネントの観点から、バリアに先行する命令に対するメモリへのすべての書き込み操作が、バリアに続く命令に対するメモリへの書き込み操作の前にプロセッサによって実行されることを保証します。

    書き込みバリアは、メモリへの書き込み操作のみを順序付けます;読み取り操作に影響を与える可能性があると想定しないでください。

    注：書き込みバリアには、読み取りバリアまたはデータ依存バリアのペアが必要です。 「SMPの場合のペアリングバリア」セクションを参照してください 。
  2. データ依存関係の障壁。

    データ依存関係バリアは、読み取りバリアの弱体化バージョンです。 2番目の操作が最初の操作の結果に依存するように2つの読み取り操作が実行される場合（たとえば、最初の操作が2番目の読み取り元のアドレスを受け取る場合）、データ依存関係バリアは、2番目の読み取り操作のアドレスのデータがその時点で最新であることを保証しますこの操作を実行します。

    データ依存性バリアは、相互依存の読み取り操作にのみ影響します;書き込み操作、独立した読み取り操作、または重複する読み取り操作に影響を与えると想定するべきではありません。

    他のプロセッサはメモリ内の書き込み操作のシーケンスを生成し、その結果は問題のプロセッサで確認できます。 データ依存性バリアにより、他のプロセッサが書き込みを行っていたアドレスからバリアの前に読み取り操作がある場合、その前にある他のすべての書き込み操作の結果も、その通過の終わりにバリアを通過するプロセッサで利用できるようになります。

    注：読み取り値間の関係は、データに従って有効でなければなりません。 2番目の読み取り操作のアドレスが最初の結果に依存するが、直接ではなく、たとえば条件演算子によって最初の読み取りの結果に基づいて計算される場合、これは制御依存関係であり、その場合は読み取りバリアまたはアクセスバリアを使用する必要があります 「管理依存障壁」を参照してください。

    注：データ依存性バリアには、書き込みバリアがペアになっている必要があります。 「SMPの場合のペアリングバリア」セクションを参照してください 。
  3. 読書の障壁。

    読み取りバリアは、他のシステムコンポーネントの観点から、バリアに先行する命令のすべての読み取り操作が、バリアに続く命令の読み取り操作の前にプロセッサによって実行されることを保証するデータ依存関係のバリアです。

    読み取りバリアは、メモリからの読み取り操作のみを順序付けます;書き込み操作に影響を与えると想定しないでください。

    注：読み取りバリアにはペア書き込みバリアが必要です。 「SMPの場合のペアリングバリア」セクションを参照してください 。
  4. 一般化されたメモリアクセスバリア。

    メモリアクセスバリアは、他のシステムコンポーネントの観点から、バリアに先行する命令のすべての読み取りおよび書き込み操作が、バリアに続く命令の読み取りまたは書き込み操作の前に実行されることを保証します。

    メモリアクセスバリアは、読み取り操作と書き込み操作の両方を合理化します。

    メモリアクセスバリアは読み取りおよび書き込みバリアを意味し、両方の代わりに使用できます。

そして、いくつかの暗黙的なタイプの障壁：

  1. ロックキャプチャ操作（LOCK）。

    このような操作は、片側透過性のバリアのように動作します。 これらは、ロックキャプチャ操作に続く命令のすべてのメモリアクセス操作が、システムコンポーネントの残りの観点から、ロックキャプチャの後に実行されることを保証します。

    ロックキャプチャに先行する命令のメモリアクセス操作は、キャプチャの前後に実行できます。

    ロックキャプチャ操作には、ほぼ必ずペアのロック解放操作が必要です。
  2. ロック解除操作（UNLOCK）。

    このような操作は、片側透過性のバリアとしても動作します。 システムの他のコンポーネントの観点から、ロックを解除する前に、ロックを解除する前の命令のすべてのメモリアクセス操作が実行されることを保証します。

    ロックの解放に続く命令のメモリアクセス操作は、解放の前後に実行できます。

    ロックのキャプチャとリリースの操作が並べ替えられないことが保証されています。

    ロックキャプチャおよびリリース操作を使用すると、基本的に他の種類のメモリアクセスバリアが不要になります。


メモリアクセスバリアは、プロセス間通信の場合、またはプロセッサと外部デバイスとの相互作用の場合にのみ必要です。 これらのタイプの相互作用に関係しないコードでは、メモリアクセスバリアは必要ありません。

注：記載されている保証は最小限です。 プロセッサアーキテクチャが異なれば、バリアに対する強力な保証が提供される場合がありますが、アーキテクチャに依存しないコードではそれらを信頼すべきではありません。

障壁が保証しないもの。




データ依存関係の障壁。


データに応じて依存関係の障壁を使用するモデルには多くの微妙な点がありますが、その必要性は必ずしも明らかではありません。
次の一連のイベントを検討してください。

  CPU 1 CPU 2 =============== =============== { A == 1, B == 2, C = 3, P == &A, Q == &C } B = 4; < > P = &B Q = P; D = *Q;

コードでは、データに明示的な依存関係があり、シーケンスの最後にQは＆Aまたは＆Bのいずれかに等しくなり、（Q ==＆A）は（D == 1）、および（Q ==＆B ）は（D == 4）を意味します。

ただし、CPU2の観点からは、PはBよりも早く更新され、（Q ==＆B）および（D == 2）（o_O）になります。

そのような振る舞いは、因果関係の違反、または一貫性の問題であると思われるかもしれませんが、そうではありません。 この動作は、一部の種類のプロセッサ（DEC Alphaなど）で見られます。

状況を修正するには、アドレスの読み取りとこのアドレスでのデータの読み取りとの間にデータ依存性バリア（またはそれ以上）が必要です。

  CPU 1 CPU 2 =============== =============== { A == 1, B == 2, C = 3, P == &A, Q == &C } B = 4; < > P = &B Q = P; <   > D = *Q;

この場合、3番目の結果（（Q ==＆B）および（D == 2））は不可能です。

注：このような不自然な状況は、たとえば、1つのキャッシュバンクが偶数で他の奇数のキャッシュラインが機能する場合、共有キャッシュを備えたマシンで最も簡単に再現されます。 PとBが異なるパリティの行に分類される場合、キャッシュバンクの不均一な負荷は、説明された効果につながる可能性があります。

依存関係管理の障壁。


管理依存関係が存在する場合、読み取りバリアを使用する必要がありますが、データ依存バリアは不十分です。 次のコードを検討してください。

  q = &a; if (p) q = &b; <   > x = *q;

この例のバリアは、実際には（p）と（x = * q）の間にデータ依存関係はありませんが、制御依存関係があるため、望ましい効果はありません。 プロセッサは結果の予測を試みる場合があります。
この状況で本当に必要なもの：

  q = &a; if (p) q = &b; < > x = *q;


SMPの場合のバリアのペア。


プロセス間通信を整理する場合、特定の種類のバリアを常にペアで使用する必要があります。 ペアリングの欠如は間違いなく間違いです。

書き込みバリアには、常にデータ依存性バリア、読み取りバリア、または一般化メモリアクセスバリアの形式のペアが必要です。 同様に、データ依存関係バリアと読み取りバリアには、書き込みバリアまたは一般化されたメモリアクセスバリアの形式のペアが必要です。

  CPU 1 CPU 2 =============== =============== a = 1; < > b = 2; x = b; < > y = a;

または：

  CPU 1 CPU 2 =============== =============================== a = 1; < > b = &a; x = b; <   > y = *x;

読み取り障壁は常に存在している必要があります。唯一の問題は、プリミティブがどの強度を選択するかです。

注：通常、書き込みバリアの前の書き込み操作には、読み取りバリアまたはデータ依存関係の反対側でペアの読み取り操作があり、その逆も同様です。

  CPU 1 CPU 2 =============== =============== a = 1; }---- --->{ v = c b = 2; } \ / { w = d < > \ < > c = 3; } / \ { x = a; d = 4; }---- --->{ y = b;


バリアを使用したメモリアクセス操作の例。


まず、書き込みバリアは書き込み操作に半順序を導入します。 次の一連のイベントを検討してください。

  CPU 1 =======================  A = 1  B = 2  C = 3 < >  D = 4  E = 5

このシーケンスは、システムの残りがレコードの順序なしセット{RECORD A、RECORD B、RECORD C}として観察できる順序でメモリ一貫性サポートシステムに到達し、レコードの順序なしセット{RECORD D、RECORD E}の前に発生します。

  +-------+ : : | | +------+ | |------>| C=3 | } /\ | | : +------+ }----- \ ----->   | | : | A=1 | } \/    | | : +------+ } | CPU 1 | : | B=2 | } | | +------+ } | | wwwwwwwwwwwwwwww } <---      | | +------+ }  ,      | | : | E=5 | }    ""    | | : +------+ } ,    | |------>| D=4 | } | | +------+ +-------+ : : | | ,     |    CPU 1 V


2番目：データ依存性の障壁により、データ依存性の読み取り操作に部分的な順序付けが導入されます。 次の一連のイベントを検討してください。

  CPU 1 CPU 2 ======================= ======================= { B = 7; X = 9; Y = 8; C = &Y }  A = 1  B = 2 < >  C = &B  X  D = 4  C ( &B)  *C ( B)

バリアがない場合、CPU 2は、CPU 1が書き込みバリアを使用しているにもかかわらず、CPU 1が生成したイベントをランダムな順序で監視できます。

  +-------+ : : : : | | +------+ +-------+ |   | |------>| B=2 |----- --->| Y->8 | |  | | : +------+ \ +-------+ | CPU 2 | CPU 1 | : | A=1 | \ --->| C->&Y | V | | +------+ | +-------+ | | wwwwwwwwwwwwwwww | : : | | +------+ | : : | | : | C=&B |--- | : : +-------+ | | : +------+ \ | +-------+ | | | |------>| D=4 | ----------->| C->&B |------>| | | | +------+ | +-------+ | | +-------+ : : | : : | | | : : | | | : : | CPU 2 | | +-------+ | |   ---> | | B->7 |------>| |  B | +-------+ | | | : : | | | +-------+ | |   ---> \ | X->9 |------>| |   \ +-------+ | |  B ----->| B->2 | +-------+ +-------+ : :

上記の例では、CPU 2は値B == 7を観察しますが、Cを読み取った後に* C（Bを返す必要があります）が読み取られます。
ただし、CPU 2でCの読み取りと* Cの読み取り（つまりB）の間にデータ依存性の障壁がある場合、

  CPU 1 CPU 2 ======================= ======================= { B = 7; X = 9; Y = 8; C = &Y }  A = 1  B = 2 < >  C = &B  X  D = 4  C (gets &B) <   >  *C (reads B)

写真は次のようになります。

  +-------+ : : : : | | +------+ +-------+ | |------>| B=2 |----- --->| Y->8 | | | : +------+ \ +-------+ | CPU 1 | : | A=1 | \ --->| C->&Y | | | +------+ | +-------+ | | wwwwwwwwwwwwwwww | : : | | +------+ | : : | | : | C=&B |--- | : : +-------+ | | : +------+ \ | +-------+ | | | |------>| D=4 | ----------->| C->&B |------>| | | | +------+ | +-------+ | | +-------+ : : | : : | | | : : | | | : : | CPU 2 | | +-------+ | | | | X->9 |------>| | | +-------+ | | ,   --> \ ddddddddddddddddd | |  ,  \ +-------+ | |  C   ----->| B->2 |------>| |  +-------+ | | : : +-------+


第三に、読み取りバリアは読み取り操作を部分的に合理化します。 次の一連のイベントを検討してください。

  CPU 1 CPU 2 ======================= ======================= { A = 0, B = 9 }  A=1 < >  B=2  B  A

バリアがない場合、CPU 1の書き込みバリアを使用しているにもかかわらず、CPU 2はCPU 1によって生成されたイベントを任意の順序で監視できます。

  +-------+ : : : : | | +------+ +-------+ | |------>| A=1 |------ --->| A->0 | | | +------+ \ +-------+ | CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 | | | +------+ | +-------+ | |------>| B=2 |--- | : : | | +------+ \ | : : +-------+ +-------+ : : \ | +-------+ | | ---------->| B->2 |------>| | | +-------+ | CPU 2 | | | A->0 |------>| | | +-------+ | | | : : +-------+ \ : : \ +-------+ ---->| A->1 | +-------+ : :

ただし、CPU 2で読み取りBと読み取りAの間に読み取りバリアがある場合、

  CPU 1 CPU 2 ======================= ======================= { A = 0, B = 9 }  A=1 < >  B=2  B < >  A

CPU 1が提供する半順序は、CPU 2を正しく監視します。

  +-------+ : : : : | | +------+ +-------+ | |------>| A=1 |------ --->| A->0 | | | +------+ \ +-------+ | CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 | | | +------+ | +-------+ | |------>| B=2 |--- | : : | | +------+ \ | : : +-------+ +-------+ : : \ | +-------+ | | ---------->| B->2 |------>| | | +-------+ | CPU 2 | | : : | | | : : | |    -> \ rrrrrrrrrrrrrrrrr | |     \ +-------+ | |   B ---->| A->1 |------>| |   CPU 2 +-------+ | | : : +-------+


読み取りと投機のロードの障壁。


多くのプロセッサアーキテクチャは事前にメモリから読み取ることができます：プロセッサがパイプラインのメモリから読み取りコマンドを認識し、他のコマンドに外部バスを使用しない場合、コマンド実行のフローが読み取り命令に達していない場合でも、事前に読み取りコマンドを発行できます。 これにより、読み取り命令は非常に迅速に完了することができます。実行されるまでに、プロセッサは既にメモリから読み取られた値を受け取っている可能性があるためです。

読み取り値が必要ない場合があります-たとえば、読み取りコマンドの前にジャンプコマンドが検出された場合。 そのような場合、読み取られた値は破棄またはキャッシュされます。

次の例を考えてみましょう。

  CPU 1 CPU 2 ======================= =======================  B  }  , ,  }      A

次のコマンドを生成できます。

  : : +-------+ +-------+ | | --->| B->2 |------>| | +-------+ | CPU 2 | : :| | +-------+ | |   , ---> --->| A->0 |~~~~ | |     +-------+ ~ | |   A : : ~ | | : :| | : : ~ | |     --> : : ~-->| |     : : | |    : : +-------+ 



  CPU 1 CPU 2 ======================= =======================  B   < >  A

, . , :

  : : +-------+ +-------+ | | --->| B->2 |------>| | +-------+ | CPU 2 | : :| | +-------+ | |   , ---> --->| A->0 |~~~~ | |     +-------+ ~ | |   A : : ~ | | : :| | : : ~ | | : : ~ | | rrrrrrrrrrrrrrrr~ | | : : ~ | | : : ~-->| | : : | | : : +-------+

, , :

  : : +-------+ +-------+ | | --->| B->2 |------>| | +-------+ | CPU 2 | : :| | +-------+ | |   , ---> --->| A->0 |~~~~ | |     +-------+ ~ | |   A : : ~ | | : :| | : : ~ | | : : ~ | | rrrrrrrrrrrrrrrrr | | +-------+ | |    ---> --->| A->1 |------>| |     +-------+ | | : : +-------+


.


Linux , :


.


:

  barrier();

.

, .

.


8 Linux:

      SMP ===================== ======================= ===========================   mb() smp_mb()  wmb() smp_wmb()  rmb() smp_rmb()    read_barrier_depends() smp_read_barrier_depends()


, , .

: , (, a[b] b, — a[b]), .

, SMP- , .

: SMP- SMP-, .

SMP, . — / .

/ (MMIO).


/ :

  mmiowb();

MMIO. .

.


, , .

, ; , :

  <--- CPU ---> : <-----------  -----------> : +--------+ +--------+ : +--------+ +-----------+ | | | | : | | | | +--------+ |  | | | : |  | | | | | | CPU |--->| |----->| CPU |<-->| | | | | | | | : | | | |--->|  | | | | | : | | | | | | +--------+ +--------+ : +--------+ | | | | : |  | +--------+ : |  | : | - | +--------+ +--------+ +--------+ : +--------+ |  | | | | | | | : | | |  | | | |  | | | : |  | | |--->| -| | CPU |--->| |----->| CPU |<-->| | |  | | | | | : | | | | | | | | | | : | | | | +--------+ +--------+ +--------+ : +--------+ +-----------+ : :

, , - , , .

, , - . , . , - .

, , , .

Source: https://habr.com/ru/post/J155517/

More articles:


All Articles