Peterson算法

維基百科,自由的百科全書
前往: 導覽搜尋

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

算法概要[編輯]

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

算法使用兩個控制變量flagturn. 其中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) {
    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變量則是阻塞(忙等待)的線程隊列,這個隊列只需要容納一個元素。

參考文獻[編輯]

  1. ^ G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
  2. ^ As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
  3. ^ Maurice Herlihy, Nir Shavit: The art of multiprocessor programming,§2.3.3 Peterson Lock, Elsevier Publisher, 2008.
  4. ^ 4.0 4.1 Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194


參見[編輯]