[OS]簡述信号量機制

首先先來認識一下程序排程過程中經常用到的概念，臨界資源和臨界區。

臨界資源：系統中某些資源一次隻允許一個程序使用。

臨界區：不管是硬體臨界資源還是軟體臨界資源，多個程序必須互斥對其進行通路，每個程序中通路臨界資源的代碼稱為臨界區。

/**
*  通路臨界資源的循環程序描述
**/
while(true){
  進入區    //檢查是否能夠通路臨界資源的代碼
  臨界區		 //對臨界資源進行互斥通路
  退出區		 //結束通路臨界資源的代碼	 
  剩餘區  	 //臨界區及退出區以外的代碼
}
           

同步機制應遵循的規則：

1. 空閑讓進
2. 忙則等待
3. 有限等待（應該保證在有限時間内能夠進入）
4. 讓權等待（當程序不能進入自己的臨界區時，立即釋放處理機，以免程序陷入“忙等”狀态

信号量機制

Dijstktra提出整型信号量以來，信号量機制得到了很大的發展：

從整型信号量經記錄型信号量，進而發展為**“信号集”機制**

信号量機制是一種有效的程序同步機制。

**整型信号量：**并未遵循 “讓權等待” 的原則，使程序處于 “忙等” 狀态

//P, V操作是原子操作，在一個程序修改信号量時，另一個程序不能進行修改
//整型信号量表示一個用于表示資源數目的整形量S
//P操作是「通過」
wait(S){
 while(S <= 0);
  S--;
}
//V操作是「釋放」
signal(S){
  S++;
}
           

記錄型信号量：不存在 ”忙等“，采取 ”讓權等待“ 原則

using semaphore = struct{
  int value;  //value表示某類資源的數量，如果value的值是1的話，表示隻允許一個程序通路臨界資源，此時信号量為互斥信号量
  struct process_control_block * list;     //程序指針連結清單，存儲等待程序，「記錄型信号量」由此得名
};

wait(semaphore * S){
  S->value--;     //使某一類資源數量減1
  if(S->value < 0) block(S->list);  //當S->value < 0時，表示已配置設定完成，此時調用block原語進行自我阻塞，并放棄處理機，将程序插入到信号量連結清單S中
}

signal(semaphore * S){
  S->value++;     //釋放某一類資源，使其數量加1
  if(S->value <= 0) wakeup(S->list);   //S->value <= 0意味着此時等待連結清單還有任務等待中，喚醒第一個等待程序
}
           

AND型信号量：AND同步機制的基本思想是：将程序在整個運作過程中需要的所有資源，一次性全部配置設定給程序，待程序使用完之後再一起釋放，以避免死鎖。

Swait(S1, S2, ..., Sn){
  while(true)
    if(S1 >= 1 && S2 >= 1 && ... && Sn >= 1){
      for(int i = 1; i <= n; ++i)
        	Si --;
      break;
    }
  else{
    	放到等待隊列中等待
  }
}


Signal(S1, S2, ..., Sn){
  while(true){
    for(int i = 1; i <= n; ++i)
      	Si++;
     将程序從等待隊列移出，使其進行
  }
}
           

信号量集：對AND機制進行擴充，對程序申請的所有資源以及每類資源的不同的資源需求量，在一次P，V原語操作中完成

Swait(S1, t1, d1, ..., Sn, tn, dn)
Ssignal(S1, t1, d1, ..., Sn, tn, dn)  
           

使用信号量機制實作程序互斥：為該資源設定一互斥信号量

mutex

，設定初值為1，将個程序通路該資源的臨界區CS置于

wait(mutex)

和

signal(mutex)

中

//P操作和V操作必須成對出現,否則：
//1. 缺少wait(mutex)将會導緻系統混亂，不能保證對臨界資源的互斥通路
//2. 缺少signal(mutex)将會使臨界資源得不到釋放
semaphore mutex = -1;
P(){
  while(true){
    wait(mutex);
    臨界區;
    signal(mutex);
    剩餘區;
  }
}