基本介紹
- 中文名：Peterson算法
- 提出者：Gary L. Peterson
- 提出時間：1981年
- 套用學科：程式計算
算法概要,實現方法,說明,三個標準,
算法概要
Peterson算法是基於雙執行緒互斥訪問的LockOne與LockTwo算法而來。LockOne算法使用一個flag布爾數組，LockTwo使用一個turn的整型量，都實現了互斥，但是都存在死鎖的可能。Peterson算法把這兩種算法結合起來，完美地用軟體實現了雙執行緒互斥問題。
算法使用兩個控制變數flag與turn. 其中flag[n]的值為真，表示ID號為n的進程希望進入該臨界區.，變數turn保存有權訪問共享資源的進程的ID號。
實現方法
boolean flag[2];int turn;void procedure0(){while(true){flag[0]=true;turn=1;while(flag[1]&&turn==1) /*若flag[1]為false，P0就進入臨界區；若flag[1]為tureP0循環等待，只要P1退出臨界區，P0即可進入*/{/* donothing*/}visit();/*訪問臨界區*/flag[0]=false;/*訪問臨界區完成，procedure0釋放出臨界區*//*remainder section*/}}void procedure1(){while(true){flag[1]=true;turn=0;while(flag[0]&&turn==0){/* donothing*/ ;}visit();/*訪問臨界區*/flag[1]=false;/*訪問臨界區完成，procedure1釋放出臨界區*//*remainder section*/}}void main(){flag[0]=flag[1]=false;/*start procedure0 and procedure1*/ ;}說明
考慮進程P0，一旦它設定flag[0]=true，則P1不能進入臨界區。如果P1已經進入臨界區，那么flag[1]=true，P0被阻塞不能進入臨界區。
另一方面，互相阻塞也避免了。假設P0在while里被阻塞了，表示flag[1]為true且turn=1，則此時P1可以執行。
三個標準
該算法滿足解決臨界區問題的三個必須標準：互斥訪問, 進入， 有限等待。
- 互斥訪問
- P0與P1顯然不會同時在臨界區: 如果進程P0在臨界區內，那么或者flag[1]為假(意味著P1已經離開了它的臨界區)，或者turn為0(意味著P1隻能在臨界區外面等待，不能進入臨界區).
進入
- 進入(Progress)定義為：如果沒有進程處於臨界區內且有進程希望進入臨界區, 則只有那些不處於剩餘區(remainder section)的進程可以決定哪個進程獲得進入臨界區的許可權，且這個決定不能無限推遲。剩餘區是指進程已經訪問了臨界區，並已經執行完成退出臨界區的代碼，即該進程當前的狀態與臨界區關係不大。
有限等待
