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

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

vark:integer;

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

in,out:integer:=0;

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

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

produceaniteminnextp;/*生產(chǎn)一個產(chǎn)品*/

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

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

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

counter:=counter+1;/*緩沖內(nèi)產(chǎn)品數(shù)加1*/

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

end

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

processconsumerbeginwhile(TRUE)

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

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

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

counter:=counter-1;/*取走一個產(chǎn)品，計數(shù)減1*/

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

consumethriteminnextc;/*消耗產(chǎn)品*/

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

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

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

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

一個進(jìn)程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應(yīng)的特殊變量值，這種特殊變量就是信號量(semaphore)，復(fù)雜的進(jìn)程合作需求都可以通過適當(dāng)?shù)男盘柦Y(jié)構(gòu)得到滿足。記錄型信號量與PV操作(5)

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

信號量的值(-2)

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

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

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

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

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

設(shè)s為一個記錄型數(shù)據(jù)結(jié)構(gòu),一個分量為整形量value,另一個為信號量隊列queue,P和V操作原語定義：

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

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

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

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

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

s:=s+1;

/*把信號量加1*/

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

設(shè)s為一個記錄型數(shù)據(jù)結(jié)構(gòu),一個分量為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記錄型信號量解決進(jìn)程互斥問題

s:semaphore;s:=1;cobegin

……

processPi begin …… P(s);

臨界區(qū)；

V(s); …… end; ……coend;記錄型信號量和PV操作解決機(jī)票問題(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操作解決機(jī)票問題(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;

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

哲學(xué)家吃通心面問題(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)永遠(yuǎn)等待，有若干種辦法可避免死鎖：?至多允許四個哲學(xué)家同時吃；?奇數(shù)號先取左手邊的叉子，偶數(shù)號先取右手邊的叉子；?每個哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉子也不取。哲學(xué)家吃通心面問題的一種正確解

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;生產(chǎn)者消費者問題①一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)②一個生產(chǎn)者、一個消費者共享多個緩沖區(qū)③多個生產(chǎn)者、多個消費者共享多個緩沖區(qū)④多個生產(chǎn)者、多個消費者共享一個緩沖區(qū)⑤多個生產(chǎn)者、一個消費者共享多個緩沖區(qū)⑥一個生產(chǎn)者、多個消費者共享多個緩沖區(qū)一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)的解varB:integer;

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

full:semaphore; /*緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*/

empty:=1;

/*緩沖區(qū)內(nèi)允許放入一件產(chǎn)品*/

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

beginL1:

L2: Produceaproduct;

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

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

GotoL1;GotoL2;end;end;

coend

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

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

full:semaphore:=0;

/*緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*/

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ā)進(jìn)程：讀者和寫者，共享一個文件F，要求：允許多個讀者同時執(zhí)行讀操作任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ鲗懻邎?zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出記錄型信號量解決讀者

寫者問題(1)

varrc:integer:=0;W，R:semaphore;Rc:=0;/*讀進(jìn)程計數(shù)*/

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ā)師正