Petersonアルゴリズムの理解

アルゴリズムコードを先に入力:

int turn;
int interested[2];

void enter_region(int process)//         
{
	int other = 1 - process;
	interested[process] = true;
	turn = process;
	while ( turn == process && interested[other] == true);
}

void leave_region(int process)//         
{
	interested[process] = false;
}

両方のプロセスP 0,P 1を考察し,P 0,P 1が臨界領域(すなわちinterested＝true)に入りたいと仮定した.P 0がすぐに処理するコードが最後のwhileループであることを直接考慮すると、P 0はまだ臨界領域に入っていないため、P 1が臨界領域にあるかどうかは関係ありません.
turn=0の場合、P 1はturn行までのみ実行されるか、より単純なP 1は臨界領域に入りたくないはずです.このときP 1がinterested行の前にあると、P 0は直接ループを飛び出して臨界領域に入る.この場合、P 1は臨界領域に入ることは不可能である(この場合interested[0]=trueであるため).P 1がinterested行を実行した場合、P 0は、P 1がturn行を実行するのをループ待ち、その後、ループを飛び出して臨界領域に入る(この場合、turn=1であり、ループ条件を満たさないため).P 0は先にturnするので,P 0は先に臨界領域に入り,このとき先着先着原則を満たす.
turn=1の場合は、P 0がturn=0のコードに実行されるとすぐにP 1に切り替わり、turn=1のコードに実行されることを示します.この場合、P 1はinterested[0]=trueのため、臨界領域に入ることはできないことに注意してください.したがって、P 0は安全に臨界領域に入ることができ、その後P 1はP 0が終了したことを知ってinterested[0]をfalseとすることができない.

このアルゴリズムは、プロセスがプリエンプトであり、優先度がある場合にデッドロックが発生する.例えば、2つのプロセスH,Lがあり、Lが臨界領域にあり、Hが入りたい場合、H優先度が高いため、Hが忙しい場合、Hが常に実行される.そこでLは臨界領域から離れられず,Hは臨界領域に入れない.この結果を優先度反転

と呼ぶ.