•  03-07-2019
  •  | 
  •  

質問

次の擬似コードをご覧ください：

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
}

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

ご協力いただければ幸いです！

役に立ちましたか？

解決

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

次の状況から始めます：

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

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

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

状況は次のとおりです。

blocked {false, true}
turn = 0;

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

ところで、この方法はもともとハイマンによって発明されました。彼はそれを1966年にAcmのコミュニケーションに送りました

他のヒント

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

次の状況から始めます：

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);

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

blockedを宣言してvolatileにする必要があるかもしれませんが、プログラミング言語を指定しないと、知る方法がありません。

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

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)

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

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top