Peterson算法

適用于兩個(gè)進(jìn)程之間的互斥

//i j 是兩個(gè)進(jìn)程的id
#define i 0 
#define j 1

//flag[] 數(shù)組 進(jìn)入臨界區(qū)意愿標(biāo)記，每個(gè)進(jìn)程都有自己的意愿，所以要兩個(gè)。
//turn   變量 第二標(biāo)記，只有當(dāng)兩個(gè)進(jìn)程都有意愿時(shí)，
//           就需要這個(gè)?？梢岳斫獬蛇t到標(biāo)志。注意條件。
//~~~~~~~~~~~~~~~~~~~~上鎖
flag[i] = true;  //打標(biāo)記給另一個(gè)進(jìn)程看，表明我打算進(jìn)臨界區(qū)啦。
turn = i;        //先簽到，turn指向的后來者。
while(flag[j] && turn == i); 
//1、另一個(gè)進(jìn)程是否也有意愿；
//2、自己是否是后來者；
//如果兩個(gè)條件都滿足就等吧。

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

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

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

面包店算法

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

#define n 10 //最大進(jìn)程數(shù)
//choosing[] 數(shù)組 進(jìn)程是否取號(hào)
//num[] 數(shù)組 進(jìn)程取得的號(hào)碼 0表示未取號(hào)
//~~~~~~~~~~~~~~~~~~~~上鎖
choosing[i] = true;
//取號(hào)碼，取到的號(hào)碼可能會(huì)相同。
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、存在同樣已取號(hào)的進(jìn)程；
//2、存在號(hào)碼比自己小的進(jìn)程。
//   或者當(dāng)最小的號(hào)碼和自己相同時(shí)，自己的id比同號(hào)的大。
//同時(shí)滿足兩個(gè)條件時(shí)，則等待。
}

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

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

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

??因?yàn)榧偃鐚?duì)于進(jìn)程i，遍歷到k時(shí)，小于k的進(jìn)程加入取到的號(hào)碼一定是大于進(jìn)程i的號(hào)碼，所以對(duì)于進(jìn)程i來說就不需要考慮了。如圖所示：

面包店算法1

??當(dāng)兩個(gè)進(jìn)程取到相同的號(hào)碼時(shí)，在一開始就會(huì)建立好等待關(guān)系。如圖所示

面包店算法2.png

總結(jié)

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