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

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

k:integer;nextp,nextc:

item;buffer:array[0..k-1]

of

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

producer/*

將一個產(chǎn)品放入緩沖區(qū)*//*指針推進*//*緩沖內(nèi)產(chǎn)品數(shù)加1*/beginwhile(TRUE)

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

an

item

in

nextp;/*生產(chǎn)一個產(chǎn)品*/if(counter==k)sleep();/*

緩沖滿時，生產(chǎn)者睡眠*/buffer[in]:=nextp;in:=(in+1)

mod

k;counter:=counter+1;

if(counter==1)wakeup(consumer);/*

緩沖空了，加進一件產(chǎn)品并喚醒消費者*/end生產(chǎn)者-消費者問題算法描述(3)process

consumer/*取一個產(chǎn)品到nextc*//*指針推進*//*

取走一個產(chǎn)品，計數(shù)減1*/beginwhile(TRUE)

/*無限循環(huán)*/if(counter==0)sleep();/*

緩沖區(qū)空消費者睡眠*/nextc:=buffer[out];out:=(out+1)

mod

k;counter:=counter-1;

if(counter==k-1)wakeup(producer);/*

緩沖滿了，取走一件產(chǎn)品并喚醒生產(chǎn)者*/consume

thr

item

in

nextc;/*消耗產(chǎn)品*/end生產(chǎn)者-消費者問題的算法描述(4)生產(chǎn)者和消費者進程對counter的交替執(zhí)行會使其結(jié)果不唯一生產(chǎn)者和消費者進程的交替執(zhí)行會導(dǎo)致進程永遠等待記錄型信號量與PV操作(1)

前節(jié)種種方法解決臨界區(qū)調(diào)度問題的缺點:

1)對不能進入臨界區(qū)的進程，采用忙式等待測試法，浪費CPU時間。2)將測試能否進入臨界區(qū)的責(zé)任推給各個競爭的進程會削弱系統(tǒng)的可靠性，加重了用戶編程負擔(dān)。1965年E.W.Dijkstra提出了新的同步工具--信號量和P、V操作。記錄型信號量與PV操作(2)信號量：一種軟件資源原語：內(nèi)核中執(zhí)行時不可被中斷的過程P操作原語和V操作原語一個進程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應(yīng)的特殊變量值，這種特殊變量就是信號量(semaphore)，復(fù)雜的進程合作需求都可以通過適當(dāng)?shù)男盘柦Y(jié)構(gòu)得到滿足。記錄型信號量與PV操作(3)操作系統(tǒng)中，信號量表示物理資源的實體，它是一個與隊列有關(guān)的整型變量。實現(xiàn)時，信號量是一種記錄型數(shù)據(jù)結(jié)構(gòu)，有兩個分量：一個是信號量的值，另一

個是信號量隊列的隊列指針。信號量的值(-2)信號量隊列指針信號量分類信號量按其用途分為公用信號量：私有信號量：信號量按其取值分為二元信號量：一般信號量：整型信號量設(shè)s為一個整形量，除初始化外，僅能通過P、V操作訪問，P和V操作原語定義：P(s)：while

s≤0

do

null

operations：=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)的進程被置成等待信號量s的狀態(tài)。

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

semaphore

=

recordvalue:integer;queue:

list

of

process;Endprocedure

P(var

s:semaphore);begins

:=

s

–

1;if

s

<

0

then

W(s);/*把信號量減去1

*//*若信號量小于0，則調(diào)用P(s)的進程被置成等待信號量s的狀態(tài)*/end;procedure

V(var

s:semaphore);begins

:=

s

+

1;/*把信號量加1

*/if

s<=0

then

R(s);

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

V操作意味著釋放一個資源。在一定條件下，

P操作代表掛起進程操作，而V操作代表喚醒被掛起進程的操作二元信號量(1)設(shè)s為一個記錄型數(shù)據(jù)結(jié)構(gòu),一個分量為value,它僅能取值0和1,另一個分量為信號量隊列queue,把二元信號量上的P、V操作記為BP和BV,BP和BV操作原語的定義如下：二元信號量(2)type

binary

semaphore=record???value(0,1);queue:

list

of

processend;procedure

BP(vars:semaphore);

procedureBV(var

s:semaphore);beginif

s.queue

is

empty;beginif

s.value=1;??then

s.value=0;else

beginthen

s.value=1;else

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

:

semaphore;s

:=

1;cobegin……process

Pibegin……P(s);臨界區(qū)；

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

A

:

ARRAY[1..m]

OF

integer;mutex

:

semaphore;mutex:=

1;cobeginprocess

Pivar

Xi:integer;beginL1:按旅客定票要求找到A[j]；P(mutex)Xi

:=

A[j];if

Xi>=1then

beginXi:=Xi-1;

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

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

L1;end;??記錄型信號量和PV操作解決機票問題(2)Var

A

:

ARRAY[1..m]

OF

integer;s

:

ARRAY[1..m]

OF

semaphore;

s[j]

:=

1;cobeginprocess

Pivar

Xi:integer;beginL1:按旅客定票要求找到A[j]；P(s[j])Xi

:=

A[j];if

Xi>=1then

beginXi:=Xi-1;

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

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

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

forki

:array[0..4]

of

semaphore;forki

:=

1;cobegin//

i=0,1,2,3,4,process

PibeginL1:思考；P(fork[i])；P(fork[(i+1)mod

5])；吃通心面；V(fork[i])；V(fork[(i+1)mod

5])；goto

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

forki

:array[0..4]

of

semaphore;forki

:=

1;cobegin/*

i=0,1,2,3

*/processPibeginL1:思考；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]mod

5)；goto

L1;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ū)的解/*可以使用的空緩沖區(qū)數(shù)*//*緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*//*緩沖區(qū)內(nèi)允許放入一件產(chǎn)品*//*緩沖區(qū)內(nèi)沒有產(chǎn)品*/Produce

a

product;P(empty);B

:=

product;V(full);Goto

L1;process

consumerbeginL2:P(full);Product:=

B;;V(empty);Consume

a

product;Goto

L2;var

B

:

integer;empty:semaphore;full:semaphore;empty

:=

1;full

:=

0;cobeginProcess

producerbeginL1:?????end;end;coend多個生產(chǎn)者、多個消費者、共享多個緩沖區(qū)的解/*可以使用的空緩沖區(qū)數(shù)*//*緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*//*放入/取出緩沖區(qū)指針*/L1:produce

a

product;P(empty);P(mutex);B[in]

:=

product;in:=(in+1)

mod

k;V(mutex);V(full);Goto

L1;process

consumer_jbeginL2:P(full);P(mutex);Product:=

B[out];out:=(out+1)

mod

k;V(mutex);V(empty);Consume

a

product;Goto

L2;end;

end;var

B

:

array[0..k-1]

of

item;empty:semaphore:=k;full:semaphore:=0;mutex:semaphore:=1;in

,

out:integer:=

0;cobeginprocess

producer_iBegin?????????coend?蘋果桔子問題桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果(apple)，媽媽專向盤子中放桔于(orange)，一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子里的蘋果記錄型信號量解決蘋果桔子問題plate

:

integer;sp:semaphore；sg1:semaphore;sg2:semaphore;sp

:=

1;Sg1,

:=

0;sg2

:=

0;cobeginprocess

fatherbeginL1:削一個蘋果；P(sp);把蘋果放入plate；V(sg2);goto

L1;end;process

motherbeginend;/*盤子里可以放幾個水果*//*盤子里有桔子*//*盤子里有蘋果*//*盤子里允許放一個水果*//*盤子里沒有桔子*//*盤子里沒有蘋果*/process

sonbeginL3:P(sg1);從plate中取桔子；V(sp);吃桔子；goto

L3;end;process

daughterbeginL4:P(sg2);L2:剝一個桔子；從plate中取蘋果；P(sp);V(sp);把桔子放入plate；吃蘋果；V(sg1);goto

L4;goto

L2;end;coend讀者寫者問題有兩組并發(fā)進程：讀者和寫者，共享一個文件F，要求：允許多個讀者同時執(zhí)行讀操作任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ鲗懻邎?zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出記錄型信號量解決讀者寫者問題(1)var

rc

:

integer:=0;W，R:

semaphore;Rc:=0;/*讀進程計數(shù)*/W

:=

1;R

:=

1;記錄型信號量解決讀者寫者問題(2)procedure

write;beginP(W);寫文件;

V(W);end;procedure

read;beginP(R);rc

:=

rc

+

1;if

rc=1

then

P(W)；V(R);讀文件；P(R);rc

:=

rc

-

1;if

rc

=

0

then

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