mutex - 相互排除問題

Question

次の疑似コードを見てください。

boolean blocked[2];
int turn;
void P(int id) {
      while(true) {
             blocked[id] = true;
             while(turn != id) {
                    while(blocked[1-id])
                    /* do nothing */;
                    turn = id;
             }
             /* critical section */
             blocked[id] = false;
             /* remainder */
      }
}
void main() {
      blocked[0] = false;
      blocked[1] = false;
      turn = 0;
      parbegin(P(0), P(1)); //RUN P0 and P1 parallel
}

上記のコードを使用して、単純な相互除外ソリューションを実装できると思いました。しかし、それは機能していません。誰かが理由を知っていますか？

どんな助けでも本当に感謝します!

score 5 · Accepted Answer

この例では、次の理由により、相互排除は保証されません。

次の状況から始めます。

blocked = {false, false};
turn = 0;

P1 が実行され、スキップされます

  blocked[id] = false; // Not yet executed.

現在の状況は次のとおりです。

blocked {false, true}
turn = 0;

ここで P0 が実行されます。2 番目の while ループを通過し、クリティカルセクションを実行する準備が整います。そして、P1 が実行されると、ターンを 1 に設定し、クリティカルセクションを実行する準備も整います。

ところで、この方法はもともとハイマンによって発明されました。彼は 1966 年に Acm の通信にそれを送った

score 2 · Accepted Answer

相互排除は、次の理由で保証されていないこの例に含まれています。

次の状況から始めます。

turn= 1;
blocked = {false, false};

実行は次のように実行されます。

P0: while (true) {
P0:   blocked[0] = true;
P0:   while (turn != 0) {
P0:     while (blocked[1]) {
P0:     }
P1: while (true) {
P1:   blocked[1] = true;
P1:   while (turn != 1) {
P1:   }
P1:   criticalSection(P1);
P0:     turn = 0;
P0:   while (turn != 0)
P0:   }
P0:   critcalSection(P0);

score 0 · Accepted Answer

これは宿題ですか、それとも組み込みプラットフォームですか? pthreads または Win32 (関連する) 同期プリミティブを使用できない理由はありますか?

score -1 · Accepted Answer

特にマルチプロセッサ（またはマルチコア）環境では、このように同時実行を実装することはできません。コア/プロセッサが異なれば、キャッシュも異なります。これらのキャッシュはコヒーレントではない可能性があります。以下の擬似コードは、示されている順序で実行され、結果が示されます。

get blocked[0] -> false   // cpu 0
set blocked[0] = true     // cpu 1 (stored in CPU 1's L1 cache)
get blocked[0] -> false   // cpu 0 (retrieved from CPU 0's L1 cache)
get glocked[0] -> false   // cpu 2 (retrieved from main memory)

同時実行を実装するには、ハードウェアの知識が必要です。

score -1 · Accepted Answer

コンパイラは、「空の」while ループを最適化した可能性があります。変数を volatile として宣言すると役立つ場合がありますが、マルチプロセッサシステムでは十分であるとは限りません。

score -1 · Accepted Answer

ブロックされたと宣言し、揮発性として回転する必要があるかもしれませんが、プログラミング言語を指定しないと知る方法はありません.

mutex - 相互排除問題

6 に答える 6

Related

Reference