操作系統(tǒng)ch33信號量與PV操作

3.3信號量與PV操作3.3.1同步與同步機制3.3.2記錄型信號量與PV操作3.3.3用記錄型信號量實現(xiàn)互斥3.3.4記錄型信號量解決生產者-消費者問題3.3.5記錄型信號量解決讀者-寫者問題3.3.6記錄型信號量解決理發(fā)師問題3.3.1同步和同步機制著名的生產者--消費者問題是計算機操作系統(tǒng)中并發(fā)進程內在關系的一種抽象，是典型的進程同步問題。在操作系統(tǒng)中，生產者進程可以是計算進程、發(fā)送進程；而消費者進程可以是打印進程、接收進程等等。解決好生產者--消費者問題就解決好了一類并發(fā)進程的同步問題。生產者--消費者問題表述

有界緩沖問題有n個生產者和m個消費者，連接在一個有k個單位緩沖區(qū)的有界緩沖上。其中，pi和cj都是并發(fā)進程，只要緩沖區(qū)未滿，生產者pi生產的產品就可投入緩沖區(qū)；只要緩沖區(qū)不空，消費者進程cj就可從緩沖區(qū)取走并消耗產品。生產者-消費者問題算法描述(1)

vark:integer;

nextp,nextc:item;buffer:array[0..k-1]ofitem;

in,out:integer:=0;

coumter:integer:=0;生產者-消費者問題算法描述(2)

processproducerbeginwhile(TRUE)/*無限循環(huán)*/

produceaniteminnextp;/*生產一個產品*/

if(counter==k)sleep();/*緩沖滿時，生產者睡眠*/

buffer[in]:=nextp;/*將一個產品放入緩沖區(qū)*/

in:=(in+1)modk;/*指針推進*/

counter:=counter+1;/*緩沖內產品數加1*/

if(counter==1)wakeup(consumer);/*緩沖空了，加進一件產品并喚醒消費者*/

end

生產者-消費者問題算法描述(3)

processconsumerbeginwhile(TRUE)

/*無限循環(huán)*/

if(counter==0)sleep();/*緩沖區(qū)空消費者睡眠*/

nextc:=buffer[out];/*取一個產品到nextc*/out:=(out+1)modk;/*指針推進*/

counter:=counter-1;/*取走一個產品，計數減1*/

if(counter==k-1)wakeup(producer);/*緩沖滿了，取走一件產品并喚醒生產者*/

consumethriteminnextc;/*消耗產品*/

end生產者-消費者問題的算法描述(4)

生產者和消費者進程對counter的交替執(zhí)行會使其結果不唯一生產者和消費者進程的交替執(zhí)行會導致進程永遠等待記錄型信號量與PV操作(1)前節(jié)種種方法解決臨界區(qū)調度問題的缺點:1)對不能進入臨界區(qū)的進程，采用忙式等待測試法，浪費CPU時間。2)將測試能否進入臨界區(qū)的責任推給各個競爭的進程會削弱系統(tǒng)的可靠性，加重了用戶編程負擔。1965年E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。

記錄型信號量與PV操作(2)信號量：一種軟件資源原語：內核中執(zhí)行時不可被中斷的過程P操作原語和V操作原語記錄型信號量與PV操作(3)

信號量和P、V操作，將交通管制中多種顏色的信號燈管理交通的方法引入操作系統(tǒng)，讓兩個或多個進程通過特殊變量展開交互。記錄型信號量與PV操作(4)

一個進程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應的特殊變量值，這種特殊變量就是信號量(semaphore)，復雜的進程合作需求都可以通過適當的信號結構得到滿足。記錄型信號量與PV操作(5)

通過信號量傳送信號，進程使用P、V兩個特殊操作來發(fā)送和接收信號，如果進程相應的信號仍然沒有送到，進程被掛起直到信號到達為止。記錄型信號量與PV操作(6)操作系統(tǒng)中，信號量表示物理資源的實體，它是一個與隊列有關的整型變量。實現(xiàn)時，信號量是一種記錄型數據結構，有兩個分量：一個是信號量的值，另一個是信號量隊列的隊列指針。記錄型信號量與PV操作(7)

信號量的值(-2)

信號量隊列指針信號量分類

信號量按其用途分為?公用信號量：?私有信號量：信號量按其取值分為

?二元信號量：?一般信號量：整型信號量

設s為一個整形量，除初始化外，僅能通過P、V操作訪問，P和V操作原語定義：

P(s)：whiles≤0donulloperations：=s-1；V(s)：s：=s+1；記錄型信號量(1)

設s為一個記錄型數據結構,一個分量為整形量value,另一個為信號量隊列queue,P和V操作原語定義：

P(s)；將信號量s減去l，若結果小于0，則調用P(s)的進程被置成等待信號量s的狀態(tài)。

V(s)：將信號量s加1，若結果不大于0，則釋放一個等待信號量s的進程。記錄型信號量(2)

typesemaphore=recordvalue:integer;queue:listofprocess;EndprocedureP(vars:semaphore);begin

s:=s–1;/*把信號量減去1*/

ifs<0thenW(s);/*若信號量小于0，則調用P(s)的進程被置成等待信號量s的狀態(tài)*/end;procedureV(vars:semaphore);begin

s:=s+1;

/*把信號量加1*/

ifs<=0thenR(s);/*若信號量小于等于0，則釋放一個等待信號量s的進程*/end;記錄型信號量(3)推論1：若信號量s為正值，則該值等于在封鎖進程之前對信號量s可施行的P操作數、亦等于s所代表的實際還可以使用的物理資源數記錄型信號量(4)推論2：若信號量s為負值，則其絕對值等于登記排列在該信號量s隊列之中等待的進程個數、亦即恰好等于對信號量s實施P操作而被封鎖起來并進入信號量s隊列的進程數記錄型信號量(5)推論3：通常，P操作意味著請求一個資源，V操作意味著釋放一個資源。在一定條件下，P操作代表掛起進程操作，而V操作代表喚醒被掛起進程的操作二元信號量(1)

設s為一個記錄型數據結構,一個分量為value,它僅能取值0和1,另一個分量為信號量隊列queue,把二元信號量上的P、V操作記為BP和BV,BP和BV操作原語的定義如下：二元信號量(2)

typebinarysemaphore=recordvalue(0,1);queue:listofprocessend;procedureBP(vars:semaphore);procedure

BV(vars:semaphore);beginbeginifs.value=1;ifs.queueisempty;thens.value=0;thens.value=1;else

begin

elsebeginW(s.queue);R(s.queue);end;end;endend3.3.3記錄型信號量解決進程互斥問題

s:semaphore;s:=1;cobegin

……

processPi begin …… P(s);

臨界區(qū)；

V(s); …… end; ……coend;記錄型信號量和PV操作解決機票問題(1)

VarA:ARRAY[1..m]OFinteger;mutex:semaphore;mutex:=1;cobeginprocessPi varXi:integer;begin L1:

按旅客定票要求找到A[j]； P(mutex) Xi:=A[j]; ifXi>=1

thenbegin

Xi:=Xi-1;A[j]:=Xi;V(mutex);輸出一張票；

end; elsebeginV(mutex);輸出票已售完；

end;gotoL1;end;

記錄型信號量和PV操作解決機票問題(2)

VarA:ARRAY[1..m]OFinteger;

s:ARRAY[1..m]OFsemaphore;s[j]:=1;cobeginprocessPi varXi:integer;begin L1:

按旅客定票要求找到A[j]； P(s[j]) Xi:=A[j]; ifXi>=1thenbegin

Xi:=Xi-1;A[j]:=Xi;V(s[j]);輸出一張票；

end; elsebeginV(s[j]);輸出票已售完；

end;gotoL1;end;coend;

哲學家吃通心面問題(1)有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子哲學家吃通心面問題(2)

哲學家吃通心面問題(3)varforki

:array[0..4]ofsemaphore;

forki:=1;cobeginprocessPi//i=0,1,2,3,4,begin L1:

思考；

P(fork[i])； P(fork[(i+1)mod5])；

吃通心面；

V(fork[i])； V(fork[(i+1)mod5])；

gotoL1;end;coend;有若干種辦法可避免這類死鎖

上述解法可能出現(xiàn)永遠等待，有若干種辦法可避免死鎖：?至多允許四個哲學家同時吃；?奇數號先取左手邊的叉子，偶數號先取右手邊的叉子；?每個哲學家取到手邊的兩把叉子才吃，否則一把叉子也不取。哲學家吃通心面問題的一種正確解

varforki

:array[0..4]ofsemaphore;

forki:=1;cobeginprocessPi//*i=0,1,2,3*/begin L1:

思考；

P(fork[i])；//*i=4,P(fork[0])*/ P(fork[i+1]mod5)//*i=4,P(fork[4])*/

吃通心面；

V(fork[i])； V(fork([i+1]mod5)；

gotoL1;end;coend;生產者消費者問題①一個生產者、一個消費者共享一個緩沖區(qū)②一個生產者、一個消費者共享多個緩沖區(qū)③多個生產者、多個消費者共享多個緩沖區(qū)④多個生產者、多個消費者共享一個緩沖區(qū)⑤多個生產者、一個消費者共享多個緩沖區(qū)⑥一個生產者、多個消費者共享多個緩沖區(qū)一個生產者、一個消費者共享一個緩沖區(qū)的解varB:integer;

empty:semaphore; /*可以使用的空緩沖區(qū)數*/

full:semaphore; /*緩沖區(qū)內可以使用的產品數*/

empty:=1;

/*緩沖區(qū)內允許放入一件產品*/

full:=0;/*緩沖區(qū)內沒有產品*/cobeginProcessproducerprocessconsumerbegin

beginL1:

L2: Produceaproduct;

P(full); P(empty);Product:=B;; B:=product;

V(empty); V(full);Consumeaproduct;

GotoL1;GotoL2;end;end;

coend

多個生產者、多個消費者、共享多個緩沖區(qū)的解varB:array[0..k-1]ofitem;

empty:semaphore:=k;/*可以使用的空緩沖區(qū)數*/

full:semaphore:=0;

/*緩沖區(qū)內可以使用的產品數*/

mutex:semaphore:=1;in,out:integer:=0;/*放入/取出緩沖區(qū)指針*/

cobeginprocessproducer_iprocessconsumer_jBeginbegin L1:produceaproduct;L2:P(full); P(empty);P(mutex); P(mutex);Product:=B[out]; B[in]:=product;out:=(out+1)modk; in:=(in+1)modk;V(mutex); V(mutex);V(empty); V(full);Consumeaproduct; GotoL1;GotoL2; end;end;coend

蘋果桔子問題

桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔于(orange)，一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子里的蘋果記錄型信號量解決蘋果桔子問題plate:integer;sp:semaphore；/*盤子里可以放幾個水果*/sg1:semaphore;/*盤子里有桔子*/sg2:semaphore;/*盤子里有蘋果*/sp:=1;/*盤子里允許放一個水果*/Sg1,:=0;/*盤子里沒有桔子*/sg2:=0;/*盤子里沒有蘋果*/cobeginprocessfatherbegin L1:削一個蘋果；

P(sp);

把蘋果放入plate； V(sg2);

gotoL1;end;processmotherbegin L2:剝一個桔子；

P(sp);

把桔子放入plate； V(sg1);

gotoL2;end;processsonbegin L3: P(sg1);

從plate中取桔子；

V(sp);

吃桔子；

gotoL3;end;processdaughterbegin L4: P(sg2);

從plate中取蘋果；

V(sp);

吃蘋果；

gotoL4;end;coend讀者寫者問題

有兩組并發(fā)進程：讀者和寫者，共享一個文件F，要求：允許多個讀者同時執(zhí)行讀操作任一寫者在完成寫操作之前不允許其它讀者或寫者工作寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部退出記錄型信號量解決讀者

寫者問題(1)

varrc:integer:=0;W，R:semaphore;Rc:=0;/*讀進程計數*/

W:=1;

R:=1;記錄型信號量解決讀者

寫者問題(2)

procedureread;procedurewrite;beginbeginP(R);P(W);

rc:=rc+1;

寫文件;

ifrc=1thenP(W)；V(W);V(R);end;

讀文件；

P(R);rc:=rc-1;ifrc=0thenV(W)；V(R);end;理發(fā)師問題理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個顧客到來時，它必須叫醒理發(fā)師如果理發(fā)師正