信號量機制
整型信號量
最初由Dijkstra把整型信號量定義為一個整型量除初始化外僅能通過兩個標准的原子操作(Atomic Operation) wait(S)和signal(S)來訪問這兩個操作一直被分別稱為PV操作wait和signal操作可描述為
wait(S): while S≤ do noop
S∶=S;
signal(S): S∶=S+;
記錄型信號量
在整型信號量機制中的wait操作只要是信號量S≤就會不斷地測試因此該機制並未遵循讓權等待的准則而是使進程處於忙等的狀態記錄型信號量機制則是一種不存在忙等現象的進程同步機制但在采取了讓權等待的策略後又會出現多個進程等待訪問同一臨界資源的情況為此在信號量機制中除了需要一個用於代表資源數目的整型變量value外還應增加一個進程鏈表L用於鏈接上述的所有等待進程記錄型信號量是由於它采用了記錄型的數據結構而得名的它所包含的上述兩個數據項可描述為
type semaphore=record
value:integer;
L:list of process;
end
相應地wait(S)和signal(S)操作可描述為
procedure wait(S)
var S: semaphore;
begin
Svalue∶=Svalue;
if Svalue＜ then block(SL)
end
procedure signal(S)
var S: semaphore;
begin
Svalue∶=Svalue+;
if Svalue≤ then wakeup(SL);
end
在記錄型信號量機制中Svalue的初值表示系統中某類資源的數目因而又稱為資源信號量對它的每次wait操作意味著進程請求一個單位的該類資源因此描述為Svalue∶=Svalue當Svalue＜時表示該類資源已分配完畢因此進程應調用block原語進行自我阻塞放棄處理機並插入到信號量鏈表SL中可見該機制遵循了讓權等待准則此時Svalue的絕對值表示在該信號量鏈表中已阻塞進程的數目對信號量的每次signal操作表示執行進程釋放一個單位資源故Svalue∶=Svalue+操作表示資源數目加若加後仍是Svalue≤則表示在該信號量鏈表中仍有等待該資源的進程被阻塞故還應調用wakeup原語將SL鏈表中的第一個等待進程喚醒如果Svalue的初值為表示只允許一個進程訪問臨界資源此時的信號量轉化為互斥信號量
AND型信號量
在兩個進程中都要包含兩個對Dmutex和Emutex的操作即
process A: process B:
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);
若進程A和B按下述次序交替執行wait操作
process A: wait(Dmutex); 於是Dmutex=
process B: wait(Emutex); 於是Emutex=
process A: wait(Emutex); 於是Emutex= A阻塞
process B: wait(Dmutex); 於是Dmutex= B阻塞
AND同步機制的基本思想是將進程在整個運行過程中需要的所有資源一次性全部地分配給進程待進程使用完後再一起釋放只要尚有一個資源未能分配給進程其它所有可能為之分配的資源也不分配給他亦即對若干個臨界資源的分配采取原子操作方式要麼全部分配到進程要麼一個也不分配由死鎖理論可知這樣就可避免上述死鎖情況的發生為此在wait操作中增加了一個AND條件故稱為AND同步或稱為同時wait操作即Swait(Simultaneous wait)定義如下
Swait(S S … Sn)
if Si≥ and … and Sn≥ then
for i∶= to n do
Si∶=Si;
endfor
else
place the process in the waiting queue associated with the first Si found with Si＜ and set the program count of this process to the beginning of Swait operation
endif
Ssignal(S S … Sn)
for i∶= to n do
Si=Si+;
Remove all the process waiting in the queue associated with Si into the ready queue
endfor;
信號量集
Swait(S t d … Sn tn dn)
if Si≥t and … and Sn≥tn then
for i∶= to n do
Si∶=Sidi;
endfor
else
Place the executing 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
signal(S d … Sn dn)
for i∶= to n do
Si∶=Si+di;
Remove all the process waiting in the queue associated with Si into the ready queue
endfor;
一般信號量集的幾種特殊情況() Swait(S d d)此時在信號量集中只有一個信號量S但允許它每次申請d個資源當現有資源數少於d時不予分配() Swait(S )此時的信號量集已蛻化為一般的記錄型信號量(S＞時)或互斥信號量(S=時)
() Swait(S )這是一種很特殊且很有用的信號量操作當S≥時允許多個進程進入某特定區當S變為後將阻止任何進程進入特定區換言之它相當於一個可控開關
了解更多計算機相關基礎課程視頻
[] [] []
From:http://tw.wingwit.com/Article/program/czxt/201311/24206.html
