Peterson算法

適用于兩個進程之間的互斥

//i j 是兩個進程的id
#define i 0 
#define j 1

//flag[] 數(shù)組 進入臨界區(qū)意愿標記，每個進程都有自己的意愿，所以要兩個。
//turn   變量 第二標記，只有當兩個進程都有意愿時，
//           就需要這個。可以理解成遲到標志。注意條件。
//~~~~~~~~~~~~~~~~~~~~上鎖
flag[i] = true;  //打標記給另一個進程看，表明我打算進臨界區(qū)啦。
turn = i;        //先簽到，turn指向的后來者。
while(flag[j] && turn == i); 
//1、另一個進程是否也有意愿；
//2、自己是否是后來者；
//如果兩個條件都滿足就等吧。

//~~~~~~~~~~~~~~~~~~~~臨界區(qū)

//~~~~~~~~~~~~~~~~~~~~開鎖
flag[0] = false;//離開了臨界區(qū)，當然要解除自己的意愿咯。方便另一個進程進入。

問題1：如何更好的理解turn變量的作用？
??如果沒有turn變量肯定是錯誤的。如果去除，那么在兩個進程同時表明進入臨界區(qū)的意愿時，會導致兩個進程都進不入臨界區(qū)。
??turn變量只有在兩個進程都有意愿的時候，才能啟到控制流量的作用。可以將turn理解成遲到標記，當然這種理解要結合while循環(huán)里的turn==i條件。同樣也可以將turn理解成早到標志，這樣的話就要將while循環(huán)里的turn==j改成turn==j。

面包店算法

有限個進程之間的互斥
定義偽代碼(a, b) < (c, d)等價于(a<c) || (a == c && b < d)

#define n 10 //最大進程數(shù)
//choosing[] 數(shù)組 進程是否取號
//num[] 數(shù)組 進程取得的號碼 0表示未取號
//~~~~~~~~~~~~~~~~~~~~上鎖
choosing[i] = true;
//取號碼，取到的號碼可能會相同。
num[i] = max(num[0],...,num[n-1])+1;
choosing[i] = false;
for(j = 0 ; j < n ; j++){
  while(choosing[j]);
  while( num[j]!=0 && (num[j],j) < (num[i],i) );
//1、存在同樣已取號的進程；
//2、存在號碼比自己小的進程。
//   或者當最小的號碼和自己相同時，自己的id比同號的大。
//同時滿足兩個條件時，則等待。
}

//~~~~~~~~~~~~~~~~~~~~臨界區(qū)

//~~~~~~~~~~~~~~~~~~~~開鎖
num[i] = 0;

問題1：為什么只要從頭開始for循環(huán)遍歷一遍就可以了？如果等待過程中前面再次取號會怎么樣？

??因為假如對于進程i，遍歷到k時，小于k的進程加入取到的號碼一定是大于進程i的號碼，所以對于進程i來說就不需要考慮了。如圖所示：

面包店算法1

??當兩個進程取到相同的號碼時，在一開始就會建立好等待關系。如圖所示

面包店算法2.png

總結

??兩個算法有一個共同的思路：在進入臨界區(qū)之前，都是先標記自己想進入臨界區(qū)的意愿，在退出臨界區(qū)后取消標記。
??每個進程都是只在乎自己，在標記的時候，不會去考慮別人，所以這個時候就有可能有多個進程同時標記自己的意愿。解決方法都是人為規(guī)定一個執(zhí)行順序。
??例如：Peterson算法是按誰先搶到旗幟（turn變量），就誰先執(zhí)行，另一個則等待。
??面包店算法是也是按照誰先取號，就誰先執(zhí)行。由于不對號碼進行保護，所以可能會出現(xiàn)相同的號碼，這個時候按照進程id號的大小進行排序。