4

次のような単純なバリアをコードに実装しようとしました。

void waitOnBarrier(int* barrier, int numberOfThreads) {
    atomicIncrement(barrier); // atomic increment implemented in assembly
    while(*barrier < numberOfThreads);
}

そして、コードにはバリアの使用法があります。

int g_barrier = 0; // a global variable

waitOnBarrier(&g_barrier, someKnownNumberOfThreads);

ここまでは順調ですが、g_barrier変数をどこでゼロにリセットすればよいでしょうか? のようなものを書くと

g_barrier = 0;

waitOnBarrier呼び出しの直後に、スレッドの 1 つが他のスレッドよりも速くバリアから解放され、他のすべてのスレッドがまだループ命令を実行している間にg_barrierを無効にすると問題が発生するため、最終的にはバリアに永久にスタックします。 .

説明: waitOnBarrierは次のようなものにコンパイルされます (疑似コード):

1: mov rax, numberOfThreads
2: mov rbx, [barrier]
3: cmp rax, rbx
4: jmp(if smaller) to 2

したがって、バリアで同期している 2 つのスレッドがあり、thread_1が命令 3 または 4 のどこかで遅く、高速のthread_2がバリアに到達し、それを渡し、g_barrier無効化フローに進むとします。つまり、thread_1が命令 2 に到達した後、[barrier] でゼロの値が表示され、永久にバリアにスタックすることになります!

問題は、どのようにg_barrierを無効化する必要があるかということです。その時点までにすべてのスレッドがバリアを離れたことを確認できる「十分に」コード内のどこにあるのでしょうか。または、バリアを実装するより正しい方法はありますか?

4

4 に答える 4

3

バリアを実際に実装するのは非常に困難です。主な理由は、すべての古いウェイターが実行される前に新しいウェイターが到着し始める可能性があるためです。これにより、あらゆる種類の単純なカウントベースの実装が妨げられます。私の推奨する解決策は、バリア オブジェクト自体が、バリアに到着する最初のスレッドのスタック上に存在する「現在のバリア インスタンス」を指すだけで、最後に終了するスレッドになることです (他のスレッドが終了している間は終了できないため)。スレッドはまだそのスタックを参照しています)。pthread プリミティブに関する非常に優れたサンプル実装 (C11 ロック プリミティブまたは使用する必要のあるものに適合させることができます) は、このトピックに関する私の過去の質問に対する Michael Burr の回答に含まれています。

https://stackoverflow.com/a/5902671/379897

はい、大変な作業のように見えますが、実際にバリアのコントラクトを満たすバリア実装を作成することは簡単ではありません。

于 2014-10-07T11:28:10.870 に答える
0

この本で説明されている Barrier ソリューションを実装してみてください。

セマフォの小さな本

于 2014-10-07T09:10:10.237 に答える