2

P1 と P2 は、クラスタ内のプロセスまたはノードです。f1 と f2 はフラグです。強力なメモリ モデルがあり、両方のプロセスがいつでも再起動される可能性があり、プロセスを再起動するとそのフラグがクリアされると仮定すると、これは私が思いついたアルゴリズムであり、まだ破ることはできませんでしたが、理論的に証明されておらず、ピーターソンのものと比べると単純すぎるように見えます。

P1 start:
set f1
if f2 set then clear f1, wait some, goto start
else enter critical section
do whatever
clear f1

P2 start:
set f2
if f1 set then clear f2, wait some, goto start
else enter critical section
do whatever
clear f2

誰でも流れを見ることができますか？プロセスの1つがセクションにすばやく再入力することで他のプロセスを枯渇させる可能性があることを除いて?

4

3 に答える 3

5

「if X set then clear Y」操作がアトミックでない場合、競合状態が発生する可能性があり、どちらもクリティカル セクションに入ることができなくなります。以下の流れをまとめてみました。

P1: set f1
P2: set f2
P1: is f2 set?
P2: is f1 set?
P1: yes, clear f1
P2: yes, clear f2
P1: start wait
P2: start wait
P1: end wait
P2: end wait
P1: goto start
P2: goto start

これは、タスク スケジューラによって行われる割り当てに違いが生じるか、2 つの P の待機時間が互いに異なるまで、永遠に続く可能性があります。

于 2008-11-18T13:45:13.510 に答える
0

このアルゴリズムが相互排除を保証することを証明するのは簡単です。両方のプロセスが同時にクリティカルセクションにある場合は、両方のフラグが設定され、F1がF2の前に（P1のコードから）設定され、F2がF1の前に（P2のコードから）設定されたことを意味します。 ）。これは不可能であるため、相互排除が保証されます。

制限付き待機を保証しないため、ピーターソンのシナリオよりも単純です。別の回答のシナリオは、すぐにゼロに収束する確率はありますが、何度も繰り返すことができます（待機期間のランダム性が高いと仮定します）。

于 2008-11-18T17:13:28.440 に答える
0

ええと、飢餓の問題を除けば、他に問題は見当たりません。

ただし、Peterson のアルゴリズムは公平性を保証します。各プロセスは、クリティカル セクションが次に利用可能になるとすぐに取得することが保証されますが、このアルゴリズムでは提供されません。

ただし、ピーターソンのアルゴリズムがそれほど単純ではないとあなたが考える理由については興味があります。あなたが持っているものとそれほど違いはありません。

P1 start:
set f1
x = 2
while f2 and (x == 2) wait
enter critical section, etc.
clear f1
于 2008-11-18T14:08:42.387 に答える