Peterson演算法（解決臨界區問題）詳解

本節說明一個經典的基於軟體的臨界區問題的解決方案，稱為 Peterson 演算法。

Peterson 演算法提供了解決臨界區問題的一個很好的演算法，並能說明滿足互斥、進步、有限等待等要求的軟體設計的複雜性。

Peterson演算法適用於兩個進程交錯執行臨界區與剩餘區。兩個進程為 P₀ 和 P₁。為了方便，當使用 P_i 時，用 P_j 來表示另一個進程，即 j == 1 - i。

Peterson演算法要求兩個進程共用兩個資料項：

int turn;
boolean flag[2];

變數 turn 表示哪個進程可以進入臨界區。即如果 turn == i，那麼進程 P_i 允許在臨界區內執行。陣列 flag 表示哪個進程準備進入臨界區。例如，如果 flag[i] 為 true，那麼進程 P_i 準備進入臨界區。

在解釋了這些資料結構後，就可以分析如圖 1 所示的演算法。

---