信號量機制

整型信號量最初Dijkstra把整型信號量定義為一個用於表示資源數目的整型量S，它與一般的整型量不同，除初始化外，僅能通過兩個標準原子操作（Atomic Operation）wait(S)和signal(S)操作可以描述為：wait(S): while S<=0 do no-op;S:=S-1;signal(S):S:=S+1;

記錄型信號量在整型信號量機制中的wait操作，只要是信號量S<=0,就會不斷測試。因此，該機制並未遵循“讓權等待”準則，而是使進程處於“忙等”狀態。記錄型信號量機制則是一種不存在“忙等”現象的進程同步機制。但在採取了“讓權等待”的策略後，又會出現多個進程等待訪問同一個臨界資源的情況。為此，在信號量機制中，除了需要一個用於代表資源數目的整型變量value外，還應該增加一個進程鏈表指針L，用於鏈接上述的所有等待進程。記錄型信號量是由於它採用了記錄型的數據結構而得名的。它所包含的上述兩個數據項可以描述為：type semaphore=recordvalue:integerL:list of process;end相應的，wait(S)和signal(S)的操作可描述為：procedure wait(S)var S: semaphore;beginS.value:=S.value-1;if S.value<0 then block(S.L);endprocedure signal(S)var S: semaphore;beginS.value:=S.value+1;if S.value<=0 then wakeup(S.L);end

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 thenfor i:=1 to n doSi:=Si-1;endforelseplace the process in the waiting queue associated with the first Si found with Si<1,and set the program count of this process to the beginning of Swait operationendifSsignal(S1,S2,...Sn)for i:=1 to n doSi:=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;

信號量集在記錄型信號量機制中，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 thenfor i:=1 to n doSi:=Si-di;endforelsePlace 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.endifSsignal(S1,d1,......Sn,dn)for i:=1 to n doSi:=Si+di;Remove all the process waiting in the queue associated with Si into the ready queueendfor; ^[1]