Peterson演算法
Peterson演算法是一個實現互斥鎖的並行程式設計演算法,可以控制兩個行程訪問一個共享的單使用者資源而不發生訪問衝突。蓋瑞·L·彼得森(Gary L. Peterson)於1981年提出此演算法[1] [2]。
演算法概要
Peterson演算法是基於雙執行緒互斥訪問的LockOne與LockTwo演算法而來。[3]LockOne演算法使用一個flag
布林列表,LockTwo使用一個turn
的整型量,都實現了互斥,但是都存在死結的可能。Peterson演算法把這兩種演算法結合起來,完美地用軟體實現了雙執行緒互斥問題。
演算法使用兩個控制變數flag
與turn
。其中flag[n]
的值為真,表示ID號為n
的行程希望進入該臨界區。變數turn
儲存有權訪問共享資源的行程的ID號。
//flag[] is boolean array; and turn is an integer
flag[0] = false;
flag[1] = false;
int turn;
| |
P0: flag[0] = true;
turn = 1;
while (flag[1] == true && turn == 1)
{
// busy wait
}
// critical section
...
// end of critical section
flag[0] = false;
|
P1: flag[1] = true;
turn = 0;
while (flag[0] == true && turn == 0)
{
// busy wait
}
// critical section
...
// end of critical section
flag[1] = false;
|
該演算法滿足解決臨界區問題的三個必須標準:互斥訪問,進入(即不死結),有限等待(即不餓死)。[4]
互斥訪問
P0與P1顯然不會同時在臨界區:如果行程P0在臨界區內,那麼或者flag[1]
為假(意味著P1已經離開了它的臨界區),或者turn
為0
(意味著P1隻能在臨界區外面等待,不能進入臨界區)。
空閒讓進
進入(Progress)定義為:如果沒有行程處於臨界區內且有行程希望進入臨界區, 則只有那些不處於剩餘區(remainder section)的行程可以參與到哪個行程獲得進入臨界區這個決定中,且這個決定不能無限推遲。剩餘區是指行程已經訪問了臨界區,並已經執行完成退出臨界區的代碼,即該行程當前的狀態與臨界區關係不大。
有限等待
有限等待(Bounded waiting)意味著一個行程在提出進入臨界區請求後,只需要等待臨界區被使用有上限的次數後,該行程就可以進入臨界區。[4]即行程不論其優先級多低,不應該餓死(starvation)在該臨界區入口處。Peterson演算法顯然讓行程等待不超過1次的臨界區使用,即可獲得權限進入臨界區。
註解
Peterson演算法不需要原子(atomic)操作,即它是純軟體途徑解決了互斥鎖的實現。但需要注意限制CPU對主記憶體的訪問順序的最佳化改變。
擴充到N個執行緒互斥訪問一個資源的filter演算法
// initialization
level[N] = { -1 }; // current level of processes 0...N-1
waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2
// code for process #i
for(l = 0; l < N-1; ++l) { // go through each level
level[i] = l;
waiting[l] = i;
while(waiting[l] == i &&
(there exists k ≠ i, such that level[k] ≥ l)) {
// busy wait
}
}
// critical section
level[i] = -1; // exit section
陣列level
表示每個執行緒的等待級別,最小為0
,最高為N-1
,-1
表示未設定。陣列waiting
類比了一個阻塞(忙等待)的執行緒佇列,從位置0為入佇列,位置越大則入佇列的時間越長。每個執行緒為了進入臨界區,需要在佇列的每個位置都經過一次,如果沒有更高優先級的執行緒(考察陣列level
),cd或者被後入佇列的執行緒推著走(上述程式waiting[l]
≠ i
),則當前執行緒在佇列中向前走過一個位置。可見該演算法滿足互斥性。
由filter演算法去反思Peterson演算法,可見其中的flags
陣列表示兩個行程的等待級別,而turn
變數則是阻塞(忙等待)的執行緒佇列,這個佇列只需要容納一個元素。
參考文獻
- ^ G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
- ^ As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
- ^ Maurice Herlihy, Nir Shavit: The art of multiprocessor programming,§2.3.3 Peterson Lock, Elsevier Publisher, 2008.
- ^ 4.0 4.1 Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194