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

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

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

vark:integer;

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

in,out:integer:=0;

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

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

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

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

buffer[in]:=nextp;/*將一個(gè)產(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)品并喚醒消費(fèi)者*/

end

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

processconsumerbeginwhile(TRUE)

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

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

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

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

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

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

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

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

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

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

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

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

信號(hào)量的值(-2)

信號(hào)量隊(duì)列指針信號(hào)量分類

信號(hào)量按其用途分為?公用信號(hào)量：?私有信號(hào)量：信號(hào)量按其取值分為

?二元信號(hào)量：?一般信號(hào)量：整型信號(hào)量

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

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

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

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

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

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

s:=s–1;/*把信號(hào)量減去1*/

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

s:=s+1;

/*把信號(hào)量加1*/

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

設(shè)s為一個(gè)記錄型數(shù)據(jù)結(jié)構(gòu),一個(gè)分量為value,它僅能取值0和1,另一個(gè)分量為信號(hào)量隊(duì)列queue,把二元信號(hào)量上的P、V操作記為BP和BV,BP和BV操作原語的定義如下：二元信號(hào)量(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記錄型信號(hào)量解決進(jìn)程互斥問題

s:semaphore;s:=1;cobegin

……

processPi begin …… P(s);

臨界區(qū)；

V(s); …… end; ……coend;記錄型信號(hào)量和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;

記錄型信號(hào)量和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)有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每兩人之間放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(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)等待，有若干種辦法可避免死鎖：?至多允許四個(gè)哲學(xué)家同時(shí)吃；?奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先取右手邊的叉子；?每個(gè)哲學(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)者消費(fèi)者問題①一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)②一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)③多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)④多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)⑤多個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)⑥一個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū)一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(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

多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者、共享多個(gè)緩沖區(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)，一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果記錄型信號(hào)量解決蘋果桔子問題plate:integer;sp:semaphore；/*盤子里可以放幾個(gè)水果*/sg1:semaphore;/*盤子里有桔子*/sg2:semaphore;/*盤子里有蘋果*/sp:=1;/*盤子里允許放一個(gè)水果*/Sg1,:=0;/*盤子里沒有桔子*/sg2:=0;/*盤子里沒有蘋果*/cobeginprocessfatherbegin L1:削一個(gè)蘋果；

P(sp);

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

gotoL1;end;processmotherbegin L2:剝一個(gè)桔子；

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

寫者問題(1)

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

W:=1;

R:=1;記錄型信號(hào)量解決讀者

寫者問題(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ā)椅上睡覺一個(gè)顧客到來時(shí)，它必須叫醒理發(fā)師如果理發(fā)師正