信號(hào)量與PV操作

1、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ū)的有

2、界緩沖上。其中，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) var k:integer; nextp,nextc: item; buffer:array0.k-1 of item; in,out:integer:=0; coumter:integer:=0;生產(chǎn)者-消費(fèi)者問題算法描述(2) process producer begin while (TRUE) /* 無限循環(huán)*/ produce an item in nextp;/* 生產(chǎn)一個(gè)產(chǎn)品*/ if (count

3、er=k) sleep( );/* 緩沖滿時(shí)，生產(chǎn)者睡眠*/ bufferin:=nextp; /* 將一個(gè)產(chǎn)品放入緩沖區(qū)*/ in:=(in+1) mod k; /* 指針推進(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) process consumer begin while (TRUE) /* 無限循環(huán)*/ if (counter=0) sleep ( ); /* 緩沖區(qū)空消費(fèi)者睡眠*/ nextc:=bu

4、fferout; /*取一個(gè)產(chǎn)品到nextc*/ out:=(out+1) mod k; /* 指針推進(jìn)*/ counter:=counter-1; /* 取走一個(gè)產(chǎn)品，計(jì)數(shù)減1*/ if (counter=k-1) wakeup( producer); /* 緩沖滿了，取走一件產(chǎn)品并喚醒生產(chǎn)者*/ consume thr item in nextc;/* 消耗產(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ì)

5、不能進(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操作原語 一個(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操作(3) 操作系統(tǒng)中，信號(hào)量表示物理資源的實(shí)體，它是一個(gè)與隊(duì)列有關(guān)的整型變量。

6、 實(shí)現(xiàn)時(shí)，信號(hào)量是一種記錄型數(shù)據(jù)結(jié)構(gòu)，有兩個(gè)分量：一個(gè)是信號(hào)量的值，另一個(gè)是信號(hào)量隊(duì)列的隊(duì)列指針。信號(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)：while s0 do null operation s：=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，則

7、調(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)type semaphore = recordtype semaphore = record value:integer; value:integer; queue: list of process; queue: list of process;EndEndprocedure P(varprocedure P(var s:semaphore); s:semaphore);beginbegin s := s s := s 1; 1; /* 把信號(hào)量減去1 */

8、 if s 0 then W(s); if s 0 then W(s); /* 若信號(hào)量小于0，則調(diào)用P(s)的進(jìn) 程被置成等待信號(hào)量s的狀態(tài) */end;end;procedure V(varprocedure V(var s:semaphore); s:semaphore);beginbegins := s + 1;s := s + 1; /* 把信號(hào)量加1 */if s = 0 then R(s);if s =1 =1 then begin then begin Xi:=Xi-1; Aj:=Xi Xi:=Xi-1; Aj:=Xi; ; V(mutex V(mutex); );輸出一張票；

9、輸出一張票； end;end;else begin else begin V(mutex V(mutex); );輸出票已售完；輸出票已售完； end;end; goto goto L1; L1; end; end;記錄型信號(hào)量和PV操作解決機(jī)票問題(2) VarVar A : ARRAY1.m OF integer; A : ARRAY1.m OF integer; s : ARRAY1.m OF semaphore; sj := 1; s : ARRAY1.m OF semaphore; sj := 1;cobegincobeginprocess Piprocess Pivar Xivar

10、 Xi:integer;:integer;beginbeginL1:L1:按旅客定票要求找到按旅客定票要求找到AjAj；P(sj)P(sj)XiXi := Aj; := Aj;if Xiif Xi=1 =1 then begin then begin Xi:=Xi-1; Aj:=Xi Xi:=Xi-1; Aj:=Xi; ; V(sj); V(sj); 輸出一張票；輸出一張票； end;end;else begin else begin V(sj); V(sj);輸出票已售完；輸出票已售完； end;end; goto goto L1; L1;end;end;coendcoend; ; 哲學(xué)家吃

11、通心面問題問題(1)(1) 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子 哲學(xué)家吃通心面問題問題(2(2) ) 哲學(xué)家吃通心面問問題題(3)(3)var forki :array0.4 of semaphore; forki := 1;cobeginprocess Pi / i=0,1,2,3,4, beginL1:思考；P(forki)； P(fork(i+1)mod 5)； 吃通心面；V(forki)；V(fork(i+1)mod

12、5)； goto L1; end;coend;有若干種辦法可避免這類死鎖 上述解法可能出現(xiàn)永遠(yuǎn)等待，有若 干種辦法可避免死鎖：至多允許四個(gè)哲學(xué)家同時(shí)吃；奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先取右手邊的叉子；每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉子也不取。哲學(xué)家吃通心面問問題題的的一一種種正正確確解解 var forkvar forki i :array0.4 of semaphore;:array0.4 of semaphore; fork forki i := 1; := 1;cobegincobeginprocess Pi process Pi / /* * i=0,1,2,3 i=0,1

13、,2,3 * */ /beginbeginL1:L1:思考；思考；P(forki)P(forki)； / /* *i=4,P(fork0)i=4,P(fork0)* */ /P(forki+1 mod5) P(forki+1 mod5) / /* *i=4,P(fork4)i=4,P(fork4)* */ /吃通心面；吃通心面；V(forki)V(forki)；V(fork(i+ 1 mod 5)V(fork(i+ 1 mod 5)； gotogoto L1; L1; end; end;coendcoend; ;生產(chǎn)者消費(fèi)者問題一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū)一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)

14、緩沖區(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ū)的解解varvar B : integer; B : integer; empty:semaphore; empty:semaphore; / /* * 可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù) * */ / full:semaphore; full:semaphore; / /* * 緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) * */ / empty := 1; / empty := 1; /* *

15、緩沖區(qū)內(nèi)允許放入一件產(chǎn)品緩沖區(qū)內(nèi)允許放入一件產(chǎn)品 * */ / full := 0; / full := 0; /* * 緩沖區(qū)內(nèi)沒有產(chǎn)品緩沖區(qū)內(nèi)沒有產(chǎn)品 * */ /cobegincobeginProcess producer process consumer Process producer process consumer begin begin begin begin L1: L1: L2: L2:Produce a product; P(full);Produce a product; P(full);P(empty); P(empty); Product:= B; Product:

16、= B; B := product; B := product; V(empty); V(empty);V(full); V(full); Consume a product; Consume a product;Goto L1; Goto Goto L1; Goto L2;L2;end; end;end; end; coend coend多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者、共享多個(gè)緩沖區(qū)的解解varvar B : array0.k-1 of item; B : array0.k-1 of item; empty:semaphore:=k; /empty:semaphore:=k; /* * 可以使用的空

17、緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù) * */ / full:semaphore:=0; / full:semaphore:=0; /* * 緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) * */ / mutex mutex:semaphore:=1; :semaphore:=1; in , out:integer:= 0; / in , out:integer:= 0; /* * 放入放入/ /取出緩沖區(qū)指針取出緩沖區(qū)指針* */ / cobegin cobeginprocess producer_i process producer_i process consumer_j process c

18、onsumer_j Begin Begin begin beginL1:produce a product; L1:produce a product; L2:P(full); L2:P(full);P(empty); P(empty); P(mutex P(mutex); );P(mutexP(mutex); ); Product:= Bout; Product:= Bout;Bin := product; Bin := product; out:=(out+1) mod k; out:=(out+1) mod k;in:=(in+1) mod k; in:=(in+1) mod k; V(

19、mutex V(mutex); );V(mutexV(mutex); ); V(empty); V(empty);V(full); V(full); Consume a product; Consume a product;Goto L1; GotoGoto L1; Goto L2; L2;end; end; end; end;coendcoend蘋果桔子問題 桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔于(orange)，一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果 記記錄錄型型信信號(hào)號(hào)量量解解決決蘋蘋果果桔桔子子問問題題plate

20、: integer;sp:semaphore； /* 盤子里可以放幾個(gè)水果 */sg1:semaphore; /* 盤子里有桔子 */sg2:semaphore; /* 盤子里有蘋果 */sp := 1; /* 盤子里允許放一個(gè)水果*/Sg1, := 0; /* 盤子里沒有桔子 */sg2 := 0; /* 盤子里沒有蘋果*/cobeginprocess father beginL1:削一個(gè)蘋果；P(sp);把蘋果放入plate；V(sg2);goto L1;end;process mother beginL2:剝一個(gè)桔子；P(sp);把桔子放入plate；V(sg1);goto L2;end

21、;process son beginL3:P(sg1);從plate中取桔子；V(sp);吃桔子；goto L3;end;process daughter beginL4:P(sg2);從plate中取蘋果；V(sp);吃蘋果；goto L4;end;coend讀者寫者問題 有兩組并發(fā)進(jìn)程：讀者和寫者，共享一個(gè)文件F，要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ?寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出記錄型信號(hào)量解決讀者寫者問題(1) var rc : integer:=0; W，R: semaphore; Rc := 0; /* 讀進(jìn)程計(jì)數(shù) *

22、/ W := 1; R := 1; 記錄型信號(hào)量解決讀者記錄型信號(hào)量解決讀者寫者問題寫者問題(2)(2) procedure read; procedure read; procedure write; procedure write; begin begin begin begin P(R); P(R); P(W); P(W); rc := rc rc := rc + 1; + 1; 寫文件寫文件; ; if rc if rc=1 then P(W)=1 then P(W)； V(W);V(W); V(R); V(R); end; end; 讀文件；讀文件； P(R);P(R); rc := rc rc := rc - 1; - 1; if rc if rc = 0 then V(W) = 0 then V(W)； V(R);V(R); end;end;