Peterson算法

Peterson算法是一個實現互斥鎖的並發程式設計算法,可以控制兩個執行緒訪問一個共享的單用戶資源而不發生訪問衝突。Gary L. Peterson於1981年提出此算法 。

算法概要

Peterson算法是基於雙執行緒互斥訪問的LockOne與LockTwo算法而來。LockOne算法使用一個flag布爾數組,LockTwo使用一個turn的整型量,都實現了互斥,但是都存在死鎖的可能。Peterson算法把這兩種算法結合起來,完美地用軟體實現了雙執行緒互斥問題。

算法使用兩個控制變數 flag與 turn. 其中 flag[n]的值為真,表示ID號為n的進程希望進入該臨界區.,變數 turn保存有權訪問共享資源的進程的ID號。  

實現方法

說明

考慮進程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)的進程可以決定哪個進程獲得進入臨界區的許可權,且這個決定不能無限推遲。剩餘區是指進程已經訪問了臨界區,並已經執行完成退出臨界區的代碼,即該進程當前的狀態與臨界區關係不大。

• 有限等待

• 有限等待(Bounded waiting)意味著一個進程在提出進入臨界區請求後,只需要等待臨界區被使用有上限的次數後,該進程就可以進入臨界區。即進程不論其優先權多低,不應該餓死(starvation)在該臨界區入口處。Peterson算法顯然讓進程等待不超過1次的臨界區使用,即可獲得許可權進入臨界區。

相關詞條

相關搜尋

熱門詞條

聯絡我們