2

2 プロセス ソリューション アルゴリズム 1 は次のとおりです。

turn = 0;
i = 0, j = 1;
do
{
    while (turn != i) ; //if not i's turn , wait indefinitely 
    // critical section

    turn = j; //after i leaves critical section, lets j in

    //remainder section
} while (1); //loop again

相互排除が満たされていることを理解しています。P0 がクリティカル セクションにあるとき、P1 はクリティカル セクションを出るまで待機するためです。そして、P0 の更新ターンの後、P1 はクリティカル セクションに入ります。このアルゴリズムで進歩が満たされない理由がわかりません。

進行状況は、プロセスがクリティカル セクションに待機しているプロセスがない場合、プロセスは待機せずにクリティカル セクションに入ることができるはずです。

P0 の更新はクリティカル セクションを出た後に順番に行われるため、while ループで待機している P1 はクリティカル セクションに入ることができるはずです。なぜ進展がないのか教えてください。

4

3 に答える 3

3

進行状況は次のように定義されます。

その CS でプロセスが実行されておらず、その CS に入るプロセスがいくつか存在する場合、次に CS に入るプロセスの選択を無期限に延期することはできません。

スレッドのバランスが取れていない場合、上記のコードはこれを満たしていません。次のシナリオを検討してください。

  1. P0 はクリティカル セクションに入り、それを終了し、ターンを P1 に設定しました。
  2. P1 はセクションに入り、それを完了し、ターンを P0 に戻します。
  3. P1 はすぐに残りのセクションを完了し、クリティカル セクションに再び入ることを望んでいます。ただし、P0 はまだターンを保持しています。
  4. P0 は、残りのセクションのどこかで無期限に失速します。P1 は飢えています。

つまり、このアルゴリズムは、プロセスの 1 つがはるかに高速に実行されるシステムをサポートできません。これは、クリティカル セクションが によって同じ順番で所有されることを強制しP0 -> P1 -> P0 -> P1 -> ..ます。前進のために、たとえば次のような方法で所有され、P0 -> P1 -> P1 -> ..P0 が再び入る準備ができていない間に P1 を続行するシナリオを許可したいと考えています。そうしないと、P1 が不足する可能性があります。

Petersons のアルゴリズムは、スレッドがクリティカル セクションに入る準備ができたことを示すフラグを追加することで、これを修正します。これにより、他のスレッドの非効率性によって誰も立ち往生しないことが保証され、他のスレッドが許可しない限り、誰も連続して複数回入ることができないことが保証されます。

于 2013-11-02T18:44:59.423 に答える
1

2 つのプロセスのコードが実行される順序を確認することはできません。最初の P1 が実行され、クリティカル セクションに入ろうとすると、P0 のターンであるため、許可されません。したがって、P1 はクリティカル セクションに他のプロセスがなくても、クリティカル セクションに入ることができません。したがって、進歩は達成されません。

于 2013-11-02T14:44:06.670 に答える
0

ここでの問題は、これが完全に下位レベルのプロセス スケジューリングに依存することです。OS は通常、スリープ状態のプロセスをウェイクアップするのに少し時間がかかります。これは、CPU で現在実行されているプロセスが、何らかのブロッキング システム コールを実行することによって自発的に制御を放棄した時点、またはタイム クォンタムが期限切れになったときにタイマー割り込みから解放された時点で行われます。完全な SMP システムでは、これには重要なカーネル内同期とシグナリングも必要です。

つまり、プロセス 0 は、プロセス 1 を実行する機会がなくても、クリティカル セクションを出たり入ったりするループを繰り返すことができるということです。

また、相互排除のために裸の整数変数に依存していないことを願っています。これらはコンパイラによってレジスタにキャッシュされる可能性があり、そうでない場合はプロセッサキャッシュが機能します。これは、test-and-set のような特別な CPU 命令で実行されるはずです。

于 2013-11-02T14:50:29.800 に答える