22

最近のCPUアーキテクチャでは、パフォーマンスの最適化が採用されているため、実行が順不同になる可能性があります。シングルスレッドアプリケーションでは、メモリの並べ替えも発生する可能性がありますが、プログラムの順序でメモリにアクセスしたかのように、プログラマーには見えません。また、SMPの場合、ある種のメモリ順序を強制するために使用されるメモリバリアが救いの手を差し伸べます。

よくわからないのは、ユニプロセッサでのマルチスレッドについてです。次の例を考えてみましょう。スレッド1が実行されると、tofのストアがtoのストアの前に発生する可能性がありxます。fが書き込まれた後、および書き込まれる直前にコンテキストスイッチが発生するとしますx。これでスレッド2が実行を開始し、ループを終了して0を出力します。これはもちろん望ましくありません。

// Both x, f are initialized w/ 0.
// Thread 1
x = 42;
f = 1;

// Thread 2
while (f == 0)
  ;
print x;

上記のシナリオは可能ですか?または、スレッドコンテキストの切り替え中に物理メモリがコミットされるという保証はありますか?

このウィキによると、

プログラムがシングルCPUマシンで実行される場合、ハードウェアは必要な簿記を実行して、すべてのメモリ操作がプログラマーによって指定された順序(プログラム順序)で実行されたかのようにプログラムが実行されるようにします。したがって、メモリバリアは必要ありません。

ユニプロセッサマルチスレッドアプリケーションについては明示的に言及されていませんが、このケースが含まれています。

それが正しい/完全かどうかはわかりません。これはハードウェア(弱い/強いメモリモデル)に大きく依存する可能性があることに注意してください。したがって、回答に知っているハードウェアを含めることをお勧めします。ありがとう。

PS。ここでは、デバイスのI/Oなどは私の関心事ではありません。そして、それはシングルコアユニプロセッサです。

編集:リマインダーをくれたNitsanに感謝します。ここではコンパイラの並べ替えはなく(ハードウェアの並べ替えのみ)、スレッド2のループは最適化されていないと想定しています。繰り返しになりますが、悪魔は詳細にあります。

4

8 に答える 8

20

C++ の質問として、答えはプログラムにデータ競合が含まれているため、動作は未定義です。実際には、それは 42 以外のものを出力できることを意味します。

これは、基盤となるハードウェアに依存しません。指摘されているように、ループを最適化して取り除くことができ、コンパイラはスレッド 1 で割り当てを並べ替えることができるため、ユニプロセッサ マシンでも結果が発生する可能性があります。

[「ユニプロセッサ」マシンとは、単一のコアとハードウェア スレッドを備えたプロセッサを意味すると仮定します。]

あなたは今、コンパイラの並べ替えやループの排除が起こらないと仮定したいと言っています。これで、私たちは C++ の領域を離れ、対応する機械語命令について本当に質問しています。コンパイラの並べ替えをなくしたい場合は、おそらく、あらゆる形式の SIMD 命令を除外し、一度に 1 つのメモリ位置で動作する命令のみを考慮することもできます。

したがって、基本的にスレッド 1 には store-to-x store-to-f の順序で 2 つのストア命令があり、スレッド 2 には test-f-and-loop-if-not-zero があります (これは複数の命令である可能性がありますが、load-from が含まれます)。 -f) に続いて load-from-x を実行します。

私が認識している、または合理的に想像できるハードウェア アーキテクチャでは、スレッド 2 は 42 を出力します。

理由の 1 つは、単一のプロセッサによって処理される命令が順番に一貫していない場合、プログラムの効果についてほとんど何も主張できないからです。

ここで干渉する可能性がある唯一のイベントは、割り込みです (プリエンプティブなコンテキスト スイッチをトリガーするために使用されます)。割り込み時に現在の実行パイプライン状態の全体の​​状態を保存し、割り込みからの復帰時にそれを復元する架空のマシンは、異なる結果を生成する可能性がありますが、そのようなマシンは非現実的であり、私の知る限り存在しません。これらの操作は、かなりの追加の複雑さを生み出し、および/または追加の冗長バッファーまたはレジスターを必要としますが、すべて正当な理由はありません-プログラムを壊すことを除いて. 実際のプロセッサは、割り込み時に現在のパイプラインをフラッシュまたはロールバックします。これは、単一のハードウェア スレッド上のすべての命令のシーケンシャルな一貫性を保証するのに十分です。

また、心配するメモリ モデルの問題はありません。より弱いメモリ モデルは、別々のハードウェア プロセッサをメイン メモリまたは実際に共有する n レベル キャッシュから分離する別々のバッファとキャッシュに由来します。単一のプロセッサには、同様に分割されたリソースがなく、それらを複数の (純粋にソフトウェアの) スレッドに使用する正当な理由はありません。繰り返しになりますが、これらのリソースをビジー状態に保つための個別の処理リソース (プロセッサ/ハードウェア スレッド) がない場合、プロセッサやメモリ サブシステムに個別のスレッド コンテキストなどを認識させるために、アーキテクチャを複雑にし、リソースを浪費する理由はありません。

于 2013-01-10T01:38:47.617 に答える
5

強力なメモリ順序付けでは、プログラムで定義されている順序とまったく同じ順序でメモリ アクセス命令が実行されます。これは、「プログラム順序付け」と呼ばれることがよくあります。

パフォーマンスを向上させるためにプロセッサがメモリ アクセスを再順序付けできるようにするために、より弱いメモリ順序付けが採用される場合があります。これは、「プロセッサ順序付け」と呼ばれることがよくあります。

私の知る限り、上記のシナリオはIntel ia32アーキテクチャでは不可能であり、そのプロセッサの順序付けはそのようなケースを禁止しています。関連するルールは次のとおりです (intel ia-32 ソフトウェア開発マニュアル Vol3A 8.2 メモリの順序付け):

書き込みは、ストリーミング ストア、CLFLUSH、および文字列操作を除いて、他の書き込みと並べ替えられません。

ルールを説明するために、次のような例を示します。

0 に初期化されたメモリ位置 x、y。

スレッド 1:

mov [x] 1
mov [y] 1

スレッド 2:

mov r1 [y]
mov r2 [x]

r1 == 1 および r2 == 0 は許可されていません

あなたの例では、スレッド 1はx を格納する前に f を格納できません。

@Eric がコメントに返信します。

高速文字列ストア命令「stosd」は、その操作で文字列を順不同で格納する場合があります。マルチプロセッサ環境では、プロセッサが文字列「str」を格納すると、別のプロセッサが str[0] の前に str[1] が書き込まれているのを観察する場合がありますが、論理順序では str[0] が str[1] の前に書き込まれていると想定されます。

ただし、これらの指示は、他のストアでの再注文ではありません。正確な例外処理が必要です。stosd の途中で例外が発生した場合、コンテキスト スイッチの前にすべての順不同のサブストア (必ずしも stosd 命令全体を意味するわけではありません) をコミットする必要があるように、実装はそれを遅らせることを選択できます。

これがC++の質問であるかのように行われた主張に対処するために編集されました:

これも C++ のコンテキストで考慮されます。私が理解しているように、標準の確認コンパイラは、スレッド 1 で x と f の割り当てを並べ替えるべきではありません。

$1.9.14 完全な式に関連付けられたすべての値の計算と副作用は、評価される次の完全な式に関連付けられたすべての値の計算と副作用の前に並べられます。

于 2013-01-09T21:30:27.183 に答える
2

両方の言語のコンパイラが完全に許可されているロード/ストアの再順序付けを明示的に想定していないため、これは実際には C または C++ の質問ではありません。

議論のためにその仮定を許可しますが、次のいずれかでない限り、ループはとにかく終了しないことに注意してください。

  • 変更される可能性があるとコンパイラに信じる何らかの理由を与えます (たとえば、そのアドレスをインライン化できfない関数に渡して、変更する可能性があります) 。
  • 揮発性とマークする、または
  • 明示的にアトミック型にしてリクエスト取得セマンティクスにする

ハードウェア側では、コンテキストの切り替え中に物理メモリが「コミット」される心配はありません。両方のソフトウェア スレッドが同じメモリ ハードウェアとキャッシュを共有するため、コア間の一貫性/一貫性プロトコルに関係なく、不整合のリスクはありません。

両方のストアが発行され、メモリ ハードウェアがそれらの再注文を決定したとします。これはどういう意味ですか?おそらく、f のアドレスは既にキャッシュにあるため、すぐに書き込むことができますが、x のストアはそのキャッシュ ラインがフェッチされるまで延期されます。x からの読み取りは同じアドレスに依存するため、次のいずれかになります。

  • フェッチが発生するまでロードは発生しません。その場合、正常な実装では、キューに入れられたロードの前にキューに入れられたストアを発行する必要があります。
  • または、ロードがキューを覗いて、書き込みを待たずに x の値をフェッチすることができます

とにかく、スレッドを切り替えるために必要なカーネルのプリエンプション自体が、カーネル スケジューラの状態の一貫性のために必要なロード/ストア バリアを発行することを考慮してください。この状況では、ハードウェアの並べ替えが問題にならないことは明らかです。


(回避しようとしている) 本当の問題は、コンパイラの並べ替えがないという仮定です。これは単に間違っています。

于 2013-01-12T22:37:56.997 に答える
2

必要なのはコンパイラ フェンスだけです。メモリ バリアに関する Linux カーネル ドキュメントから(リンク):

SMP メモリ バリアは、ユニプロセッサ コンパイル システムのコンパイラ バリアに縮小されます。これは、CPU が自己一貫性を持っているように見え、それ自体に関してオーバーラップ アクセスを正しく順序付けすることが想定されているためです。

さらに詳しく説明すると、ハードウェア レベルで同期が必要ない理由は次のとおりです。

  1. ユニプロセッサ システム上のすべてのスレッドは同じメモリを共有するため、SMP システムで発生する可能性のあるキャッシュ コヒーレンシの問題 (伝搬レイテンシなど) はありません。

  2. CPU の実行パイプライン内の順不同のロード/ストア命令は、プリエンプティブ コンテキスト スイッチが原因でパイプラインがフラッシュされた場合、完全にコミットまたはロールバックされます。

于 2013-05-29T10:20:07.117 に答える
1

x86に関する限り、プログラムフローに関して実行コードの観点から、アウトオブオーダーストアは一貫性があります。この場合、「プログラムフロー」は、プロセッサが実行する命令のフローであり、「スレッドで実行されているプログラム」に制約されるものではありません。コンテキストの切り替えなどに必要なすべての命令は、このフローの一部と見なされるため、スレッド間で一貫性が維持されます。

于 2013-01-06T14:46:36.930 に答える
1

このコードは、(スレッド 2 で) 終了しない可能性があります。これは、コンパイラが式全体をループから引き上げることを決定できるためです (これは、揮発性ではない isRunning フラグを使用するのと似ています)。とはいえ、ここでは 2 種類の並べ替えについて心配する必要があります。コンパイラと CPU です。どちらもストアを自由に移動できます。例については、http: //preshing.com/20120515/memory-reordering-caught-in-the-actを参照してください。この時点で、上記のコードは、コンパイラ、コンパイラ フラグ、および特定のアーキテクチャに翻弄されています。引用された wiki は誤解を招く可能性があります。内部の並べ替えが CPU/コンパイラに左右されないことを示唆している可能性があるためです。

于 2013-01-06T13:20:17.503 に答える
0

コンテキストスイッチは、中断されたスレッドが実行を再開する前に復元できるように、完全なマシン状態を保存する必要があります。マシンステートにはプロセッサレジスタが含まれますが、プロセッサパイプラインは含まれません。

コンパイラの並べ替えがないと想定した場合、これは、「オンザフライ」であるすべてのハードウェア命令を、コンテキストスイッチ(つまり、割り込み)が発生する前に完了する必要があることを意味します。そうしないと、失われ、コンテキストスイッチによって保存されません。機構。これは、ハードウェアの並べ替えとは無関係です。

この例では、プロセッサが2つのハードウェア命令「x=42」と「f=1」を交換した場合でも、命令ポインタはすでに2番目の命令の後にあるため、コンテキストスイッチを開始する前に両方の命令を完了する必要があります。そうでない場合、パイプラインとキャッシュのコンテンツは「コンテキスト」の一部ではないため、それらは失われます。

つまり、IPレジスタが「f = 1」に続く命令を指しているときにctxスイッチを引き起こす割り込みが発生した場合、そのポイントより前のすべての命令はすべての効果を完了している必要があります。

于 2013-01-10T12:00:43.143 に答える
0

私の見解では、プロセッサは命令を 1 つずつフェッチします。あなたの場合、「f = 1」が「x = 42」の前に投機的に実行された場合、これら2つの命令の両方がすでにプロセッサのパイプラインにあることを意味します。現在のスレッド アウトをスケジュールする唯一の可能な方法は、割り込みです。ただし、プロセッサ (少なくとも X86 では) は、割り込みを処理する前にパイプラインの命令をフラッシュします。したがって、ユニプロセッサでの並べ替えについて心配する必要はありません。

于 2015-07-21T07:20:01.393 に答える