信號量與PV操作

1、操操作作系系統(tǒng)統(tǒng)3.3 信號量與PV操作3.3.1同步與同步機制同步與同步機制3.3.2信號量與信號量與PV操作操作3.3.3信號量實現(xiàn)互斥信號量實現(xiàn)互斥3.3.4信號量解決五個哲學家就餐問題信號量解決五個哲學家就餐問題3.3.5信號量解決生產(chǎn)者信號量解決生產(chǎn)者-消費者問題消費者問題3.3.6信號量解決讀者信號量解決讀者-寫者問題寫者問題3.3.7信號量解決理發(fā)師問題信號量解決理發(fā)師問題1操操作作系系統(tǒng)統(tǒng)3.3.1 同步和同步機制著名的生產(chǎn)者著名的生產(chǎn)者-消費者問題（消費者問題（Producer-consumer Problem)是計算機操作系統(tǒng)中并發(fā)進程內(nèi)在關系是計算機操作系統(tǒng)中并發(fā)進程內(nèi)在

2、關系的一種抽象，是典型的進程同步問題。的一種抽象，是典型的進程同步問題。在操作系統(tǒng)中，生產(chǎn)者進程可以是計算進程、發(fā)在操作系統(tǒng)中，生產(chǎn)者進程可以是計算進程、發(fā)送進程；而消費者進程可以是打印進程、接收進送進程；而消費者進程可以是打印進程、接收進程等等。程等等。解決好生產(chǎn)者解決好生產(chǎn)者-消費者問題就解決好了一類并發(fā)消費者問題就解決好了一類并發(fā)進程的同步問題。進程的同步問題。2操操作作系系統(tǒng)統(tǒng)生產(chǎn)者-消費者問題表述 有界緩沖問題有界緩沖問題有有n個生產(chǎn)者和個生產(chǎn)者和m個消費者，連接在一個有個消費者，連接在一個有k個個單位緩沖區(qū)的有界緩沖上。其中，單位緩沖區(qū)的有界緩沖上。其中，pi和和cj都是并都是并發(fā)

3、進程，只要緩沖區(qū)未滿，生產(chǎn)者發(fā)進程，只要緩沖區(qū)未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)生產(chǎn)的產(chǎn)品就可投入緩沖區(qū)；只要緩沖區(qū)不空，消費者品就可投入緩沖區(qū)；只要緩沖區(qū)不空，消費者進程進程cj就可從緩沖區(qū)取走并消耗產(chǎn)品。就可從緩沖區(qū)取走并消耗產(chǎn)品。3操操作作系系統(tǒng)統(tǒng)生產(chǎn)者-消費者問題算法描述(1)int k;typedef anyitem item; /item類型類型item bufferk;int in=0,out=0,counter=0;4操操作作系系統(tǒng)統(tǒng)生產(chǎn)者-消費者問題算法描述(2)process producer(void) while (true) /無限循環(huán)無限循環(huán)produce an item i

4、n nextp;/生產(chǎn)一個產(chǎn)品生產(chǎn)一個產(chǎn)品if (counter=k) /緩沖滿時，生產(chǎn)者睡眠緩沖滿時，生產(chǎn)者睡眠 sleep(producer);bufferin=nextp;/將一個產(chǎn)品放入緩沖區(qū)將一個產(chǎn)品放入緩沖區(qū)in=(in+1)%k; /指針推進指針推進counter+; /緩沖內(nèi)產(chǎn)品數(shù)加緩沖內(nèi)產(chǎn)品數(shù)加1if(counter=1) /緩沖為空，加進一件產(chǎn)品緩沖為空，加進一件產(chǎn)品 wakeup(consumer);/并喚醒消費者并喚醒消費者 5操操作作系系統(tǒng)統(tǒng)生產(chǎn)者-消費者問題算法描述(3)process consumer(void) while (true) /無限循環(huán)無限循環(huán)if

5、(counter=0) /緩沖區(qū)空，消費者睡眠緩沖區(qū)空，消費者睡眠 sleep(consumer); nextc=bufferout;/取一個產(chǎn)品到取一個產(chǎn)品到nextc out=(out+1)%k; /指針推進指針推進 counter-; /取走一個產(chǎn)品，計數(shù)減取走一個產(chǎn)品，計數(shù)減1if(counter=k-1) /緩沖滿了，取走一件產(chǎn)品并喚緩沖滿了，取走一件產(chǎn)品并喚 wakeup(producer); /醒生產(chǎn)者醒生產(chǎn)者consume the item in nextc;/消耗產(chǎn)品消耗產(chǎn)品 6操操作作系系統(tǒng)統(tǒng)生產(chǎn)者-消費者問題的算法描述(4)生產(chǎn)者和消費者進程對生產(chǎn)者和消費者進程對coun

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

7、tra提出新的同步工具提出新的同步工具-信號量和信號量和P、V操作。操作。 8操操作作系系統(tǒng)統(tǒng)信號量與PV操作(2)信號量：一種軟件資源信號量：一種軟件資源原語：內(nèi)核中執(zhí)行時不可被中斷的過程原語：內(nèi)核中執(zhí)行時不可被中斷的過程P操作原語和操作原語和V操作原語操作原語一個進程在某一特殊點上被迫停止執(zhí)行直到接收一個進程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應的特殊變量值，這種特殊變量就是到一個對應的特殊變量值，這種特殊變量就是信信號量號量(semaphore)，復雜的進程合作需求都可以通過，復雜的進程合作需求都可以通過適當?shù)男盘柦Y構得到滿足。適當?shù)男盘柦Y構得到滿足。信號量的值只能通過信號量的值只

8、能通過P、V操作改變。操作改變。9操操作作系系統(tǒng)統(tǒng)信號量與PV操作(3)操作系統(tǒng)中，信號量表示操作系統(tǒng)中，信號量表示物理資源物理資源的實體，它是的實體，它是一個與隊列有關的整型變量。一個與隊列有關的整型變量。實現(xiàn)時，信號量是一種實現(xiàn)時，信號量是一種記錄型記錄型數(shù)據(jù)結構，有兩個數(shù)據(jù)結構，有兩個分量：一個是信號量的分量：一個是信號量的值值，另一個是信號量隊列，另一個是信號量隊列的的隊列指針隊列指針。信號量的值信號量的值(-2)(-2) 信號量隊列指針信號量隊列指針10操操作作系系統(tǒng)統(tǒng)信號量分類信號量按其用途分為：信號量按其用途分為：公用信號量公用信號量：聯(lián)系一組并發(fā)進程，：聯(lián)系一組并發(fā)進程，相關的

9、進程相關的進程均可在此信均可在此信號量上執(zhí)行號量上執(zhí)行P、V操作，初值通常為操作，初值通常為1，用于實現(xiàn)互斥；用于實現(xiàn)互斥；私有信號量私有信號量：聯(lián)系一組并發(fā)進程，僅允許此信號量的：聯(lián)系一組并發(fā)進程，僅允許此信號量的擁有擁有進程進程執(zhí)行執(zhí)行P操作，而操作，而其它其它相關進程執(zhí)行相關進程執(zhí)行V操作，初值往往為操作，初值往往為0或正整數(shù)，常用于實現(xiàn)同步；或正整數(shù)，常用于實現(xiàn)同步；信號量按其取值分為信號量按其取值分為： 二元信號量二元信號量：值僅取：值僅取0和和1，主要用于實現(xiàn)主要用于實現(xiàn)互斥互斥 一般信號量一般信號量：計數(shù)信號量，主要用于實現(xiàn)：計數(shù)信號量，主要用于實現(xiàn)同步同步11操操作作系系統(tǒng)統(tǒng)一

10、般信號量(1)設設s為一個記錄型數(shù)據(jù)結構為一個記錄型數(shù)據(jù)結構,一個分量為整形一個分量為整形量量value，另一個為信號量隊列另一個為信號量隊列queue，P和和V操作操作原語定義：原語定義： P(s)：將信號量：將信號量s減去減去l，若結果小于，若結果小于0，則，則調(diào)用調(diào)用P(s)的進程被置成的進程被置成等待等待信號量信號量s的狀態(tài)。的狀態(tài)。 V(s)：將信號量：將信號量s加加1，若結果不大于，若結果不大于0，則，則釋放釋放一個等待信號量一個等待信號量s的進程。的進程。12操操作作系系統(tǒng)統(tǒng)一般信號量(2)typedef struct semaphore int value; /信號量值信號量值

11、struct pcb *list; /信號量隊列指針信號量隊列指針 ; void P(semaphore &s) s.value-; if(s.value0) sleep(s.list); void V(semaphore &s) s.value+; if(s.value=0) wakeup(s.list); 13操操作作系系統(tǒng)統(tǒng)一般信號量(3)推論推論1：若信號量：若信號量s為為正值正值，則該值等于在封鎖進程之前對信，則該值等于在封鎖進程之前對信號量號量s可施行的可施行的P操作數(shù)，亦等于操作數(shù)，亦等于s所代表的實際還可以使用所代表的實際還可以使用的的物理資源數(shù)物理資源數(shù)推論推

12、論2：若信號量：若信號量s為為負值負值，則其，則其絕對值絕對值等于登記排列在該信等于登記排列在該信號量號量s隊列之中等待的進程個數(shù)，亦即恰好等于對信號量隊列之中等待的進程個數(shù)，亦即恰好等于對信號量s實實施施P操作而被封鎖起來并進入信號量操作而被封鎖起來并進入信號量s隊列的隊列的進程數(shù)進程數(shù)推論推論3：通常，：通常，P操作意味著請求一個資源，操作意味著請求一個資源，V操作意味著釋操作意味著釋放一個資源。在一定條件下，放一個資源。在一定條件下，P操作代表掛起進程操作，而操作代表掛起進程操作，而V操作代表喚醒被掛起進程的操作操作代表喚醒被掛起進程的操作14操操作作系系統(tǒng)統(tǒng)二元信號量(1)設設s為一個

13、記錄型數(shù)據(jù)結構為一個記錄型數(shù)據(jù)結構，一個分量為一個分量為value，它它僅能取值僅能取值0和和1，另一個分量為信號量隊列另一個分量為信號量隊列queue， 把二元信號量上的把二元信號量上的P、V操作記為操作記為BP和和BV，BP和和BV操作原語的定義如下：操作原語的定義如下：15操操作作系系統(tǒng)統(tǒng)二元信號量(2) typedef struct binary_semaphore int value; /value取值取值0 or 1 struct pcb *list; ;void BP(binary_semaphore &s) if(s.value=1) s.value=0;else sl

14、eep (s.list);void BV(binary_semaphore &s) if(s.list is empty( ) s.value=1;else wakeup(s.list);16操操作作系系統(tǒng)統(tǒng)3.3.3信號量實現(xiàn)互斥semaphore mutex; mutex=1; cobegin process Pi( ) /i=1,n P(mutex); 臨界區(qū)臨界區(qū); V(mutex); coend17操操作作系系統(tǒng)統(tǒng)信號量解決哲學家就餐問題有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤子，每兩人之間放一把叉子。

15、每個哲學每人面前有一只空盤子，每兩人之間放一把叉子。每個哲學家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須家思考、饑餓、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子 18操操作作系系統(tǒng)統(tǒng)哲學家就餐問題(3)semaphore fork5;for (int i=0;i5;i+) forki=1;cobeginprocess philosopher_i( ) /i= 0,1,2,3,4while(true) think( ); P(forki); P(fork(i+1)%5); eat( );

16、V(forki); V(fork(i+1)%5); coend19操操作作系系統(tǒng)統(tǒng)有若干種辦法可避免這類死鎖上述解法可能出現(xiàn)上述解法可能出現(xiàn)永遠等待永遠等待，有若干種辦法可避，有若干種辦法可避免死鎖：免死鎖：至多允許四個哲學家同時吃；至多允許四個哲學家同時吃；奇數(shù)號先取左手邊的叉子，偶數(shù)號先取右手邊的奇數(shù)號先取左手邊的叉子，偶數(shù)號先取右手邊的叉子叉子；每個哲學家取到手邊的兩把叉子才吃，否則一把每個哲學家取到手邊的兩把叉子才吃，否則一把叉子也不取。叉子也不取。20操操作作系系統(tǒng)統(tǒng)哲學家就餐問題的一種正確解 semaphore fork5;for (int i=0;i5;i+) forki= 1;

17、cobeginprocess philosopher_i( )/*i=0,1,2,3 */ while(true) think( )；P(forki； /*i=4,P(fork0)*/P(fork(i+1)%5 )；/*i=4,P(fork4)*/eat( )；V(forki)；V(fork(i+ 1 % 5)； coend21操操作作系系統(tǒng)統(tǒng)3.3.5信號量解決生產(chǎn)者消費者問題一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)一個生產(chǎn)者、一個消費者共享多個緩沖區(qū)一個生產(chǎn)者、一個消費者共享多個緩沖區(qū)多個生產(chǎn)者、多個消費者共享多個緩沖區(qū)多個生產(chǎn)者、多個消費者共享多個緩沖區(qū)2

18、2操操作作系系統(tǒng)統(tǒng)一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)的解int B;semaphore empty; /可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù)semaphore full; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)empty=1; /緩沖區(qū)內(nèi)允許放入一件產(chǎn)品緩沖區(qū)內(nèi)允許放入一件產(chǎn)品full=0; /緩沖區(qū)內(nèi)沒有產(chǎn)品緩沖區(qū)內(nèi)沒有產(chǎn)品cobeginprocess producer() while(true) produce( ); P(empty); append( ) to B; V(full); coend23process consumer() while(true) P(fu

19、ll);take( ) from B;V(empty);consume( ); 操操作作系系統(tǒng)統(tǒng)一個生產(chǎn)者、一個消費者共享多個緩沖區(qū)item Bk;semaphore empty; empty=k; /可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù)semaphore full; full=0; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)int in=0; /放入緩沖區(qū)指針放入緩沖區(qū)指針int out=0; /取出緩沖區(qū)指針取出緩沖區(qū)指針 cobeginprocess producer ( ) while(true) produce( ); P(empty); append to Bin; i

20、n=(in+1)%k; V(full); coend 24process consumer ( ) while(true) P(full); take( ) from Bout; out=(out+1)%k; V(empty); consume( ); 操操作作系系統(tǒng)統(tǒng)多個生產(chǎn)者/消費者、共享多個緩沖區(qū)的解item Bk;semaphore empty; empty=k; /可以使用的空緩沖區(qū)數(shù)可以使用的空緩沖區(qū)數(shù)semaphore full; full=0; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)semaphore mutex; mutex=1; /互斥信號量互斥信號量int i

21、n=0; /放入緩沖區(qū)指針放入緩沖區(qū)指針int out=0; /取出緩沖區(qū)指針取出緩沖區(qū)指針 cobeginprocess producer_i ( ) while(true) produce( ); P(empty); P(mutex); append to Bin; in=(in+1)%k; V(mutex); V(full); coend 25process consumer_j ( ) while(true) P(full); P(mutex); take( ) from Bout; out=(out+1)%k; V(mutex); V(empty); consume( ); 操操作作

22、系系統(tǒng)統(tǒng)3.3.6 信號量解決讀者-寫者問題(1) 有兩組并發(fā)進程：讀者和寫者，共享有兩組并發(fā)進程：讀者和寫者，共享一個文件一個文件F F，要求：，要求：允許多個讀者同時執(zhí)行讀操作允許多個讀者同時執(zhí)行讀操作任一寫者在完成寫操作之前不允許其它讀者或寫任一寫者在完成寫操作之前不允許其它讀者或寫者工作者工作寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部退出退出26操操作作系系統(tǒng)統(tǒng)信號量解決讀者寫者問題(2)int readcount=0;/讀進程計數(shù)讀進程計數(shù)semaphore writeblock,mutex;writeblock=1;mutex=1;cobe

23、ginprocess reader_i( ) P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex);讀文件讀文件; P(mutex);readcount-; if(readcount=0) V(writeblock);V(mutex);coend27process writer_j( ) P(writeblock); 寫文件寫文件; V(writeblock);操操作作系系統(tǒng)統(tǒng)3.3.7信號量解決理發(fā)師問題(1)理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候把供等候理發(fā)的顧客坐的椅子理發(fā)的顧客

24、坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個顧客到來時，它必須叫醒理發(fā)師一個顧客到來時，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開椅子可坐，就坐下來等待，否則就離開28操操作作系系統(tǒng)統(tǒng)29信號量解決理發(fā)師問題(2)我走了，誰愛來誰來！操操作作系系統(tǒng)統(tǒng)信號量解決理發(fā)師問題(3)int waiting=0;/等候理發(fā)顧客坐的椅子數(shù)等候理發(fā)顧客坐的椅子數(shù)int CHAIRS=N; /為顧客準備的椅子數(shù)為顧客準備的椅子數(shù)semaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;cobeginprocess barber( ) while(true) P(customers); /有顧客嗎？若無顧客，理發(fā)師睡眠有顧客嗎？若無顧客，理發(fā)師睡眠P(mutex); /若有顧客時，進入臨界區(qū)若有顧客時，進入臨界區(qū)waiting-; /等候顧客數(shù)少一個等候顧客數(shù)少一個 V(ba