信號量機(jī)制及實現(xiàn)進(jìn)程的互斥筐摘、同步

??進(jìn)程互斥的四種軟件實現(xiàn)方式（單標(biāo)志法沐绒、雙標(biāo)志先檢查法俩莽、雙標(biāo)志后檢查法、以及Peterson算法）乔遮，三種硬件實現(xiàn)方式（中斷屏蔽方法扮超、TSL指令、Swap指令）蹋肮。在所有的解決方案中都無法實現(xiàn)讓權(quán)等待問題出刷。

1 信號量機(jī)制

??信號量機(jī)制是一種可以實現(xiàn)進(jìn)程互斥、同步的有效方法坯辩。
??信號量其實就是一個變量（可以是一個整數(shù)馁龟，也可以是更復(fù)雜的記錄型變量），可以用一個信號量來表示系統(tǒng)中某種資源的數(shù)量漆魔。如系統(tǒng)中只有一臺打印機(jī)坷檩，就可以設(shè)置一個初值為1的信號量。如所有的臨界資源在同一時刻只能被一個進(jìn)程訪問改抡，所以臨界資源的信號量為1矢炼。
??用戶進(jìn)程可以通過使用操作系統(tǒng)提供的一對原語來對信號量進(jìn)行操作，從而很方便的實現(xiàn)了進(jìn)程的互斥和同步阿纤。
??一對原語：wait(S)原語和signal(S)原語句灌，S表示信號量。wait阵赠、signal原語通常稱為P涯塔、V 操作肌稻。

2 信號量機(jī)制——整型信號量

??用一個整數(shù)型的變量作為信號量，用來表示系統(tǒng)某種資源的數(shù)量匕荸。
??如：某計算機(jī)系統(tǒng)中只有一臺打印機(jī)...

int S = 1; //初始化整型信號量S爹谭，表示當(dāng)前系統(tǒng)中可用的打印機(jī)資源。
void wait(int S){ //wait原語榛搔，相當(dāng)于“進(jìn)入?yún)^(qū)”
  while(S <= 0));    // 如果資源不夠诺凡，就一直循環(huán)等待
   S = S - 1;      // 如果資源數(shù)夠，則占用一個資源
}

void signal(int S){ // signal原語践惑，相當(dāng)于“退出區(qū)”
  S = S + 1;          // 使用完資源后腹泌，在退出區(qū)釋放資源
}

??使用原語將檢查和上鎖變成了原子性操作，避免了并發(fā)尔觉、異步導(dǎo)致的問題凉袱。
??存在問題：不滿足讓權(quán)等待原則，會發(fā)生忙等侦铜。

3 信號量機(jī)制——記錄型信號

??整型信號量的缺點是存在忙等的問題专甩，所以又提出了記錄型信號量。

/*記錄型信號量的定義*/
typedef struct{
  int value;         // 剩余資源
  struct process *L;  // 等待隊列钉稍，當(dāng)沒有資源剩余時涤躲，新來的進(jìn)程將會被放在這個阻塞隊列中
} semaphore

/* 某進(jìn)程需要使用資源時，通過wait原語申請*/
void wait(semaphore S) {
  S.value--;
  if(S.value < 0)   // 如果剩余資源不夠贡未，使用block原語使進(jìn)程從運行態(tài)進(jìn)入阻塞態(tài)种樱，
      block(S.L);  // 并掛到信號量的等待隊列中。
}

/* 進(jìn)程使用完資源后俊卤，通過signal原語釋放*/
void signal(semaphore S) {
  S.value++;
  if(S.value <= 0) // 如果value的值小于0嫩挤，表示有新的進(jìn)程在等待資源，所以要喚醒等待隊列中的進(jìn)程
      wakeup(S.L);
}

(1) 對信號量S的一次P操作意味著進(jìn)程請求一個單位該類的資源瘾蛋，需要執(zhí)行S.value--俐镐，表示資源數(shù)減1矫限，當(dāng)S.value < 0時表示該類資源已經(jīng)分配完畢哺哼，因此進(jìn)程應(yīng)該調(diào)用block原語進(jìn)行自我阻塞（當(dāng)前運行的進(jìn)程從運行態(tài)—>阻塞態(tài)），主動放棄處理機(jī)叼风，并插入到該類資源的等待隊列S.L中取董。可見无宿，該機(jī)制遵循了“讓權(quán)等待”原則茵汰，不會出現(xiàn)忙等現(xiàn)象。
(2) 對信號量S的一次V操作意味著進(jìn)程釋放了一個單位的該類資源孽鸡，因此需要執(zhí)行S.value++蹂午，表示該類資源加1栏豺，若加1后仍是S.value <= 0，表示依然有進(jìn)程在等待該類資源豆胸，因此應(yīng)調(diào)用wakeup原語喚醒等待隊列中第一個進(jìn)程（被喚醒進(jìn)程從阻塞態(tài)—>就緒態(tài)）奥洼。

4 信號量機(jī)制實現(xiàn)進(jìn)程互斥

(1) 確定臨界區(qū)（如對臨界資源打印機(jī)的訪問就應(yīng)放在臨界區(qū)）
(2) 設(shè)置互斥信號量（mutex）。
(3) 在臨界區(qū)之前執(zhí)行P(mutex)
(4) 在臨界區(qū)之后執(zhí)行V(mutex)

/* 信號量機(jī)制實現(xiàn)互斥 */
semaphore mutex = 1; // 初始化信號量

P1(){
  ...
  P(mutex);   // 使用臨界資源前需要加鎖
  臨界區(qū)代碼段.....
  V(mutex);   // 使用臨界資源后需要解鎖
  ...
}

P2(){
  ...
  P(mutex);  
  臨界區(qū)代碼段.....
  V(mutex);   
  ...
}
.....

5 信號量機(jī)制實現(xiàn)進(jìn)程同步

??進(jìn)程同步：就是要讓并發(fā)進(jìn)程按要求有序的推進(jìn)晚胡。
??用信號量實現(xiàn)進(jìn)程同步：

(1) 分析需要同步的兩個操作灵奖，即必須保證一前一后的執(zhí)行順序的操作。
(2) 設(shè)置同步信號量S估盘，初始為0瓷患。
(3) 在前操作之后執(zhí)行V(S)。
(4) 在后操作之前執(zhí)行P(S)遣妥。

??如P1擅编、P2并發(fā)執(zhí)行，假設(shè)需要保證代碼4必須要代碼1和代碼2的運行結(jié)果才能執(zhí)行箫踩，那么就必須保證代碼4必須在代碼2之后執(zhí)行沙咏。

P1(){
  代碼1;
  代碼2;
  代碼3;
}

P2(){
  代碼4;
  代碼5;
  代碼6;
}

??使用信號量機(jī)制實現(xiàn)同步

semaphore S = 0; //初始化同步信號量，初始值為0;
P1(){                           P2(){
    代碼1;                        P(s)
    代碼2;                        代碼4;
    V(S);                         代碼5;
    代碼3;                        代碼6;
}                               }

(1) 若先執(zhí)行到V(S)操作班套，則S++后S=1,肢藐。之后執(zhí)行到P(S)時，由于S=1吱韭，表示有資源吆豹，執(zhí)行S--后，S的值為0理盆，P2不會執(zhí)行block原語痘煤，而是繼續(xù)往下執(zhí)行代碼4。
(2) 若先執(zhí)行到P(S)操作猿规，由于S=0衷快，S--后S=-1，表示沒有資源姨俩，因此P操作會執(zhí)行block原語蘸拔，主動請求阻塞。之后當(dāng)執(zhí)行完代碼2环葵，繼而執(zhí)行V(S)操作调窍，S++，S的值變?yōu)?张遭，由于此時有進(jìn)程在該信號量的阻塞隊列中邓萨，因此V操作會執(zhí)行wakeup原語，喚醒P2進(jìn)程，這樣P2進(jìn)程就可以繼續(xù)執(zhí)行代碼4了缔恳。
無論是哪種情況宝剖，都可以保證代碼4一定在代碼2之后執(zhí)行。