信號量機制

1965年，荷蘭學者Dijkstra提出的信號量（Semaphores）機制是一種卓有成效的進程同步工具。在長期且廣泛的套用中，信號量機制又得到了很大的發展，它從整型信號量經記錄型信號量，進而發展為“信號量集”機制。現在，信號量機制已經被廣泛地套用於單處理機和多處理機系統以及計算機網路中。

基本介紹

• 中文名：信號量機制
• 提出時間：1965年
• 提出人：Dijkstra
• 作用：解決進程同步問題

信號量S是一個整數，S大於等於零是代表可供並發進程使用的資源實體數，當S小於零時則表示正在等待使用臨界區的進程數。

Dijkstra同時提出了對信號量操作的PV原語。

P原語操作的動作是：

（1）S減1；

（2）若S減1後仍大於或等於零，則進程繼續執行；

（3）若S減1後小於零，則該進程被阻塞後進入與該信號相對應的佇列中，然後轉進程調度。

V原語操作的動作是：

（1）S加1；

（2）若相加結果大於零，則進程繼續執行；

（3）若相加結果小於或等於零，則從該信號的等待佇列中喚醒一等待進程，然後再返回原進程繼續執行或轉進程調度。

PV操作對於每一個進程來說，都只能進行一次，而且必須成對使用。在PV原語執行期間不允許有中斷的發生。

信號量機制分 整型信號量機制、記錄型信號量機制、and型信號量機制、信號量集。

整型信號量是一種最簡單的信號量，主要用於解決並發程式互斥訪問臨界資源問題。

記號信號量在整型信號量的舉出上進行了改進，讓不能進入臨界區的進程“讓權等待”，即進程狀態有運行轉換為阻塞狀態，進程進入阻塞佇列中等待。

AND型信號量集是將進程在運行中所需要的臨界資源全部一次性分配給進程，等進程用完後再全部一次釋放。

信號量集的定義

1.用s1、s2、...sn分別表示有n類裂解資源信號量；

2.用d1、d2、...dn分別表示進程需要的每類臨界資源個數；

3.用t1、t2、...tn分別表示每類臨界資源分給進程的下限值；

信號量分類

1. 整型信號量
   最初Dijkstra把整型信號量定義為一個用於表示資源數目的整型量S，它與一般的整型量不同，除初始化外，僅能通過兩個標準原子操作（Atomic Operation）wait(S)和signal(S)操作可以描述為：
   wait(S): while S<=0 do no-op;
   S:=S-1;
   signal(S):S:=S+1;
   
2. 記錄型信號量
   在整型信號量機制中的wait操作，只要是信號量S<=0,就會不斷測試。因此，該機制並未遵循“讓權等待”準則，而是使進程處於“忙等”狀態。記錄型信號量機制則是一種不存在“忙等”現象的進程同步機制。
   但在採取了“讓權等待”的策略後，又會出現多個進程等待訪問同一個臨界資源的情況。為此，在信號量機制中，除了需要一個用於代表資源數目的整型變數value外，還應該增加一個進程鍊表指針L，用於連結上述的所有等待進程。記錄型信號量是由於它採用了記錄型的數據結構而得名的。它所包含的上述兩個數據項可以描述為：
   type semaphore=record
   value:integer
   L:list of process;
   end
   相應的，wait(S)和signal(S)的操作可描述為：
   procedure wait(S)
   var S: semaphore;
   begin
   S.value:=S.value-1;
   if S.value<0 then block(S.L);
   end
   procedure signal(S)
   var S: semaphore;
   begin
   S.value:=S.value+1;
   if S.value<=0 then wakeup(S.L);
   end
   
3. AND型信號量
   在一些套用場合，是一個進程需要先獲得兩個或者更多的共享資源後方能執行其任務。假定現在有兩個進程A和B，他們都要求訪問共享數據D和E。當然，共享數據都應該作為臨界資源。為此，可為這兩個數據分別設定用於互斥的信號量Dmutex和Emutex，並令他們的初值都是1。相應的，在兩個進程中都要包含兩個對Dmutex和Emutex的操作，即：
   process A: process B:
   wait(Dmutex); wait(Emutex);
   wait(Emutex); wait(Dmutex);
   若進程A和B處於僵持狀態。在無外力作用下，兩者都將無法從僵持狀態中解脫出來。我們稱此時的進程A 和B已經進入死鎖狀態。顯然，當進程同時要求的共享資源愈多時，發生進程死鎖的可能性就越大。
   AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部的分配給進程，待進程使用完後再一起釋放。只要尚有一個資源未能分配給進程，其它所有有可能為之分配的資源也不分配給它。亦即，對若干個臨界資源的分配，採取原子操作方式：要么把它所請求的資源全部分配給進程，要么一個也不分配。由死鎖理論可知，這樣就可以避免上述死鎖情況發生。為此，在wait操作中，增加一個“AND”條件，故稱為AND同步，或稱為同時wait操作，即Swait(Simultaneous wait)定義如下：
   Swait(S1,S2,......Sn)
   if Si>=1 and ....and Sn>=1 then
   for i:=1 to n do
   Si:=Si-1;
   endfor
   else
   place the process in the waiting queue associated with the first Si found with Si<1,and setthe program count of this process to the beginning of Swait operation
   endif
   Ssignal(S1,S2,...Sn)
   for i:=1 to n do
   Si:=Si+1;
   Remove all the process waiting in the queue associated with Si into the ready queue.
   endfor;
   
4. 信號量集
   在記錄型信號量機制中，wait(S)或signal(S)操作僅能對信號量施以加1或者減1操作，意味著每次只能獲得或釋放一個單位的臨界資源。而當一次需要N個某類臨界資源時，便要進行N次wait(S)操作，顯然這是低效的。此外，在有些情況下，當資源數量低於某一下限值時，便不予分配。因而，在每次分配前，都必須測試該資源數量，看其是否大於其下限值。基於上述兩點，可以對AND信號量機制加以擴充，形成一般化的“信號量集”機制。Swait操作可描述如下，其中S為信號量，d為需求值，而t為下限值。
   Swait(S1,t1,d1,......Sn,tn,dn)
   if Si>=t1 and ... and Sn>=tn then
   for i:=1 to n do
   Si:=Si-di;
   endfor
   else
   Place the ececuting process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation.
   endif
   Ssignal(S1,d1,......Sn,dn)
   for i:=1 to n do
   Si:=Si+di;
   Remove all the process waiting in the queue associated with Si into the ready queue
   endfor;