操作系統(tǒng)課件4_2

1、第四章第四章 互斥、同步與通訊互斥、同步與通訊l并發(fā)進(jìn)程并發(fā)進(jìn)程(concurrent processes)l進(jìn)程互斥進(jìn)程互斥(mutual exclusion)l進(jìn)程同步進(jìn)程同步(synchronization)l進(jìn)程高級通訊進(jìn)程高級通訊(communication)l系統(tǒng)舉例系統(tǒng)舉例14.3 進(jìn)程同步進(jìn)程同步l進(jìn)程同步是進(jìn)程之間直接的相互作用形式進(jìn)程同步是進(jìn)程之間直接的相互作用形式, 是合作進(jìn)程之間有意識的行為是合作進(jìn)程之間有意識的行為，相互作用，相互作用只發(fā)生在相關(guān)進(jìn)程之間只發(fā)生在相關(guān)進(jìn)程之間l4.3.1 進(jìn)程同步的概念進(jìn)程同步的概念 l4.3.2 進(jìn)程同步機制進(jìn)程同步機制l4.3.3

2、信號燈與信號燈與PV操作操作24.3.1 進(jìn)程同步的概念進(jìn)程同步的概念例：司機例：司機-售票員問題售票員問題 34.3.1 進(jìn)程同步的概念進(jìn)程同步的概念l為安全起見為安全起見,，要求，要求l關(guān)車門后方能啟動車輛關(guān)車門后方能啟動車輛; l到站停車后方能開車門到站停車后方能開車門l“啟動車輛啟動車輛”應(yīng)在應(yīng)在“關(guān)車門關(guān)車門”之后之后, “開車門開車門”應(yīng)在應(yīng)在“到站停車到站停車”之后之后l如如P2未推進(jìn)到未推進(jìn)到, P1已推進(jìn)到已推進(jìn)到, 則則P1應(yīng)等待直應(yīng)等待直到到P2推進(jìn)到為止推進(jìn)到為止l如如P1未推進(jìn)到未推進(jìn)到, P2已推進(jìn)到已推進(jìn)到, 則則P2應(yīng)等待直應(yīng)等待直到到P1推進(jìn)到為止推進(jìn)到為止l

3、如如P1在處發(fā)生了等待在處發(fā)生了等待, 則則P2執(zhí)行到時應(yīng)將執(zhí)行到時應(yīng)將P1喚醒喚醒 l如如P2在處發(fā)生了等待在處發(fā)生了等待, 則則P1執(zhí)行到時應(yīng)將執(zhí)行到時應(yīng)將P2喚醒喚醒44.3.1 進(jìn)程同步的概念進(jìn)程同步的概念定義：一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點處需要定義：一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點處需要相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為進(jìn)進(jìn)程同步程同步。定義：一組進(jìn)程，如果它們單獨不能正常進(jìn)行定義：一組進(jìn)程，如果它們單獨不能正常進(jìn)行, 但并發(fā)可以正但并發(fā)可以正常進(jìn)行常進(jìn)行, 稱這種現(xiàn)象為稱這種現(xiàn)象為進(jìn)程合作進(jìn)程合作

4、(cooperation)。參與合作的。參與合作的進(jìn)程稱進(jìn)程稱合作進(jìn)程合作進(jìn)程(cooperating process) P1:P2:synchronize后先54.3.2 進(jìn)程同步機制進(jìn)程同步機制l用于實現(xiàn)進(jìn)程同步的工具稱為用于實現(xiàn)進(jìn)程同步的工具稱為同步機制同步機制（synchronization mechanism）l同步機制要求：同步機制要求：l描述能力夠用描述能力夠用;l可實現(xiàn)可實現(xiàn);l高效高效;l使用方便使用方便.6典型同步機制典型同步機制 l信號燈與信號燈與PV操作操作( (semaphore and PV operations) )l管程管程( (monitor) )l會合會合(

5、 (rendezvous) )l條件臨界區(qū)條件臨界區(qū)( (conditional critical region) )l路徑表達(dá)式路徑表達(dá)式( (path expression) )l事件事件( (traditional UNIX) )74.3.3 信號燈與信號燈與PV操作操作l信號量屬于軟件非忙等互斥方案信號量屬于軟件非忙等互斥方案，解決互斥和同，解決互斥和同步問題。步問題。l1965年由荷蘭數(shù)學(xué)家年由荷蘭數(shù)學(xué)家Dijkstra提出，是一種卓有提出，是一種卓有成效的同步工具，現(xiàn)已廣泛使用。成效的同步工具，現(xiàn)已廣泛使用。l信號量指一個僅能由同步原語對其進(jìn)行操作的整信號量指一個僅能由同步原語對其

6、進(jìn)行操作的整型變量型變量，Dijkstra將其命名為將其命名為P操作操作(發(fā)信號發(fā)信號)和和V操作操作（等待）。（等待）。l信號量按其用途分為：信號量按其用途分為：l二元信號量：僅允許取二元信號量：僅允許取0和和1，用做互斥變量，用做互斥變量l一般信號量：取非負(fù)整數(shù)，用做一般同步問題一般信號量：取非負(fù)整數(shù)，用做一般同步問題84.3.3 信號燈與信號燈與PV操作操作l信號燈類型定義信號燈類型定義 typedef semaphore struct int value; pointer_to_PCB queue; l信號燈變量說明如下信號燈變量說明如下: semaphore s;l一個信號燈變量包括

7、兩個部分一個信號燈變量包括兩個部分l值部分值部分s.value l指針部分指針部分s.queuel在任意時刻在任意時刻, s.queue可能指向空可能指向空, 也可能指向一個由也可能指向一個由進(jìn)程進(jìn)程PCB所構(gòu)成隊列的頭部所構(gòu)成隊列的頭部, 如圖如圖 45所示所示. 初始時初始時它指向空它指向空94.3.3 信號燈與信號燈與PV操作操作10P操作原語P操作原語：操作原語：void P(semaphore *s) s-value-; if(s-value queue); asleep(s-queue):(1) 執(zhí)行此操作進(jìn)程的執(zhí)行此操作進(jìn)程的PCB入入s.queue尾（狀態(tài)改為等待）；尾（狀態(tài)改

8、為等待）；(2) 轉(zhuǎn)處理機調(diào)度程序。轉(zhuǎn)處理機調(diào)度程序。11V操作原語V操作原語操作原語:void V(semaphore *s) s-value+; if(s-value queue); wakeup(s-queue): 將隊列將隊列s-queue頭部進(jìn)程的頭部進(jìn)程的PCB取出并排入就緒隊列取出并排入就緒隊列,狀態(tài)由等待轉(zhuǎn)為就緒狀態(tài)由等待轉(zhuǎn)為就緒12規(guī)定和結(jié)論規(guī)定和結(jié)論l對信號燈變量的規(guī)定：對信號燈變量的規(guī)定：l必須置一次初值，只能置一次初值，初值必須置一次初值，只能置一次初值，初值=0;l只能執(zhí)行只能執(zhí)行P操作和操作和V操作，操作，所有其它操作非法所有其它操作非法。l幾個有用的結(jié)論幾個有用的

9、結(jié)論：l當(dāng)當(dāng)s-value =0時，時，s.queue為空；為空；l當(dāng)當(dāng)s-value value初初=1時，可實現(xiàn)互斥時，可實現(xiàn)互斥，只需在進(jìn)入臨界區(qū)時執(zhí)行一次，只需在進(jìn)入臨界區(qū)時執(zhí)行一次P操作操作, 離開臨界區(qū)時執(zhí)行一次離開臨界區(qū)時執(zhí)行一次V操作操作 l當(dāng)當(dāng)s-value的初值為正整數(shù)時，可用來管理同種組合資源的初值為正整數(shù)時，可用來管理同種組合資源(具有具有多個實例的同種類資源，如多個實例的同種類資源，如5臺打印機臺打印機)l申請時執(zhí)行一次申請時執(zhí)行一次P操作操作l歸還時執(zhí)行一次歸還時執(zhí)行一次V 操作操作13信號燈與信號燈與PV操作的應(yīng)用操作的應(yīng)用 l進(jìn)程結(jié)構(gòu)進(jìn)程結(jié)構(gòu)(共享公用變量共享公

10、用變量 mutex) repeat P(mutex); 臨界區(qū)臨界區(qū); V(mutex); 剩余區(qū)剩余區(qū); until false;lP操作操作P(s)：將信號量將信號量s減減1，若結(jié)果小于，若結(jié)果小于0，則，則調(diào)用調(diào)用P(s)的進(jìn)程被置成等待信號。的進(jìn)程被置成等待信號。lV操作操作V(s)：將信號量將信號量s加加1，若結(jié)果不大于，若結(jié)果不大于0，釋放一個等待信號量釋放一個等待信號量s的進(jìn)程。的進(jìn)程。 14信號燈與信號燈與PV操作的應(yīng)用操作的應(yīng)用lP操作和操作和V操作可用軟件（或固件）和硬件操作可用軟件（或固件）和硬件來執(zhí)行，它們的執(zhí)行必須是一個不可被中來執(zhí)行，它們的執(zhí)行必須是一個不可被中斷的

11、整體。斷的整體。lP(s)操作的特點是：如果在操作的特點是：如果在S0時：時：l信號量數(shù)值表示該類資源的可用資源數(shù)，每信號量數(shù)值表示該類資源的可用資源數(shù)，每執(zhí)行一次執(zhí)行一次P操作就意味著請求分配一個單位的操作就意味著請求分配一個單位的該類資源給執(zhí)行該類資源給執(zhí)行P操作的進(jìn)程，描述為操作的進(jìn)程，描述為s:=s-116PV操作的物理含義操作的物理含義l當(dāng)當(dāng)s0時：時：l沒有該類資源可供分配，請求資源的進(jìn)程將沒有該類資源可供分配，請求資源的進(jìn)程將被阻塞在相應(yīng)的信號量被阻塞在相應(yīng)的信號量S的等待隊列中，的等待隊列中，S的的絕對值等于在該信號量絕對值等于在該信號量S上等待的進(jìn)程數(shù)上等待的進(jìn)程數(shù)l執(zhí)行一次

12、執(zhí)行一次V操作意味著進(jìn)程釋放一個單元的該操作意味著進(jìn)程釋放一個單元的該類可用資源，描述為類可用資源，描述為s:=s+1，l若若s=0表示信號量等待隊列中有因請求該資源而表示信號量等待隊列中有因請求該資源而被封鎖的進(jìn)程，需將等待隊列中的一個進(jìn)程（往往被封鎖的進(jìn)程，需將等待隊列中的一個進(jìn)程（往往是第一個）喚醒使之進(jìn)入就緒隊列中是第一個）喚醒使之進(jìn)入就緒隊列中17Var mutex: semaphore; (初值=1） shared x,y,z:integer; CR1 CR2 CRn18用信號燈實現(xiàn)進(jìn)程互斥用信號燈實現(xiàn)進(jìn)程互斥Var mutex: semaphore; (初值=1） shared

13、x,y,z:integer;P(mutex) P(mutex) P(mutex) CR1 CR2 CRnV(mutex) V(mutex) V(mutex)19使用使用PV操作操作l當(dāng)當(dāng)N個進(jìn)程個進(jìn)程p1、p2.共享某一資共享某一資源時，必須找出源時，必須找出n個進(jìn)程的臨界個進(jìn)程的臨界區(qū)，對每個進(jìn)程區(qū)，對每個進(jìn)程使用使用PV操作，程操作，程序：序： 20使用使用PV操作操作l粗心使用粗心使用PV操操作會產(chǎn)生錯誤作會產(chǎn)生錯誤l當(dāng)當(dāng)Ri=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; V(mutex) V(mutex) 借書借書 借書借書 End En

14、d Else V(mutex);無書無書; Else V(mutex);無書無書; End End22用信號燈實現(xiàn)進(jìn)程同步用信號燈實現(xiàn)進(jìn)程同步l進(jìn)程的同步進(jìn)程的同步：并發(fā)進(jìn)程之間存在一種制約：并發(fā)進(jìn)程之間存在一種制約關(guān)系，一個進(jìn)程的執(zhí)行依賴于另一個進(jìn)程關(guān)系，一個進(jìn)程的執(zhí)行依賴于另一個進(jìn)程的消息，當(dāng)一個進(jìn)程沒有得到另一個進(jìn)程的消息，當(dāng)一個進(jìn)程沒有得到另一個進(jìn)程的消息時應(yīng)等待，直到消息到達(dá)才被喚醒的消息時應(yīng)等待，直到消息到達(dá)才被喚醒 23用信號燈實現(xiàn)進(jìn)程同步用信號燈實現(xiàn)進(jìn)程同步 P(S)后動作后動作先動作先動作 V(S)P1:P2:24用信號燈實現(xiàn)進(jìn)程同步用信號燈實現(xiàn)進(jìn)程同步例子：司機例子：司機-

15、售票員問題：售票員問題：VAR s1,s2: semaphore; (initial value 0)司機活動：司機活動： 售票員活動：售票員活動： Repeat Repeat P(S1) 關(guān)車門關(guān)車門 啟動車輛啟動車輛 V(S1) 正常行駛正常行駛 售售 票票 到站停車到站停車 P(S2) V(S2) 開車門開車門 Until false Until false25Classical synchronization problems1. Producers and consumers problem2. Readers and writers problem3. Dining philoso

16、phers problem4. Cigarette smokers problem5. Sleepy barbers problemetc. 26例例1. 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題l組合資源：若干相對獨立的資源構(gòu)成的資源集合，組合資源：若干相對獨立的資源構(gòu)成的資源集合，其中每個相對獨立的資源稱為子資源。其中每個相對獨立的資源稱為子資源。l同種組合資源：相同類型子資源構(gòu)成的組合資源。同種組合資源：相同類型子資源構(gòu)成的組合資源。l管理：管理：lVar S:semaphore; (初值初值=子資源個數(shù)）子資源個數(shù)）l例子：例子：2臺打印機臺打印機lVar S:semaphore; S.va

17、lue=2;l申請：申請：P（S）；）；l釋放：釋放：V（S）；）；27例例1. 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題預(yù)備知識：預(yù)備知識：組合資源：若干相對獨立的資源構(gòu)成的資源集合，其中組合資源：若干相對獨立的資源構(gòu)成的資源集合，其中每個相對獨立的資源稱為子資源。每個相對獨立的資源稱為子資源。同種組合資源：相同類型子資源構(gòu)成的組合資源。同種組合資源：相同類型子資源構(gòu)成的組合資源。管理：管理：Var S:semaphore; (初值初值=子資源個數(shù)）子資源個數(shù)）例子：例子：2臺打印機臺打印機 Var S:semaphore; S.value=2; 申請：申請：P（S）；）； 釋放：釋放：V（S）；

18、）；28例例1. 生產(chǎn)者生產(chǎn)者/消費者問題消費者問題l生產(chǎn)者生產(chǎn)者消費者問題消費者問題(producers and consumers problem) 也稱有界緩沖區(qū)也稱有界緩沖區(qū)問題問題l問題問題1：設(shè)緩沖區(qū)每次只能存入一條記錄。：設(shè)緩沖區(qū)每次只能存入一條記錄。l問題問題2：設(shè)緩沖區(qū)能存入：設(shè)緩沖區(qū)能存入N條記錄。條記錄。l問題問題3：設(shè)：設(shè)m個生產(chǎn)者和個生產(chǎn)者和r個消費者共享個消費者共享N條記錄的緩沖區(qū)。條記錄的緩沖區(qū)。 29緩沖區(qū)每次只能存入一條記錄緩沖區(qū)每次只能存入一條記錄l設(shè)兩進(jìn)程設(shè)兩進(jìn)程A和和B，共享一個緩沖區(qū)，共享一個緩沖區(qū)lA（生產(chǎn)者）不斷地讀入記錄并送入緩沖器中（生產(chǎn)者）不

19、斷地讀入記錄并送入緩沖器中l(wèi)進(jìn)程進(jìn)程B（消費者）不斷地從緩沖區(qū)中取出記錄并且加（消費者）不斷地從緩沖區(qū)中取出記錄并且加工工l 約束約束l進(jìn)程進(jìn)程A送入數(shù)據(jù)時，應(yīng)等到送入數(shù)據(jù)時，應(yīng)等到B發(fā)來消息（發(fā)來消息（已將緩沖區(qū)中已將緩沖區(qū)中的數(shù)據(jù)取走的數(shù)據(jù)取走）才能把下一個數(shù)據(jù)送入緩沖區(qū)中）才能把下一個數(shù)據(jù)送入緩沖區(qū)中l(wèi)進(jìn)程進(jìn)程B也應(yīng)等到也應(yīng)等到A發(fā)來消息（發(fā)來消息（緩沖區(qū)已經(jīng)送入一條記錄緩沖區(qū)已經(jīng)送入一條記錄）才能將緩沖區(qū)中的數(shù)據(jù)去取走才能將緩沖區(qū)中的數(shù)據(jù)去取走 緩沖區(qū)緩沖區(qū)進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B生產(chǎn)產(chǎn)品放入緩沖區(qū)生產(chǎn)產(chǎn)品放入緩沖區(qū)從緩沖區(qū)取從緩沖區(qū)取 產(chǎn)品產(chǎn)品30緩沖區(qū)每次只能存入一條記錄緩沖區(qū)每次只能

20、存入一條記錄l問題：問題：l若兩個進(jìn)程不相互制約，可能出現(xiàn)若兩個進(jìn)程不相互制約，可能出現(xiàn)A不斷地送入數(shù)據(jù)不斷地送入數(shù)據(jù)導(dǎo)致覆蓋前一條記錄導(dǎo)致覆蓋前一條記錄lB重復(fù)讀一條記錄重復(fù)讀一條記錄l原因：原因：l執(zhí)行的速度不匹配，只有當(dāng)這兩個進(jìn)程按照一定的速度工執(zhí)行的速度不匹配，只有當(dāng)這兩個進(jìn)程按照一定的速度工作時才不會產(chǎn)生問題，作時才不會產(chǎn)生問題，這就是這就是A和和B的同步問題的同步問題 緩沖區(qū)緩沖區(qū)進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B生產(chǎn)產(chǎn)品放入緩沖區(qū)生產(chǎn)產(chǎn)品放入緩沖區(qū)從緩沖區(qū)取從緩沖區(qū)取 產(chǎn)品產(chǎn)品31緩沖區(qū)每次只能存入一條記錄緩沖區(qū)每次只能存入一條記錄lPV操作不僅可以解決互斥問題，也可以解操作不僅可以解決互斥問

21、題，也可以解決同步問題。定義兩個信號量：決同步問題。定義兩個信號量：lsp：表示是否可以將物品放入緩沖區(qū)中，由：表示是否可以將物品放入緩沖區(qū)中，由于緩沖區(qū)只能存放一個物品，于緩沖區(qū)只能存放一個物品，初值為初值為1。lsg：表示緩沖區(qū)中是否有數(shù)據(jù)，：表示緩沖區(qū)中是否有數(shù)據(jù)，初值為初值為0，表，表示無物品示無物品緩沖區(qū)緩沖區(qū)進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B生產(chǎn)產(chǎn)品放入緩沖區(qū)生產(chǎn)產(chǎn)品放入緩沖區(qū)sp從緩沖區(qū)取從緩沖區(qū)取 產(chǎn)品產(chǎn)品sg3233緩沖區(qū)能存入緩沖區(qū)能存入N條記錄條記錄 lsp的初值為的初值為n，表示可以存放，表示可以存放n件物品，件物品，l若若sg0表示緩沖區(qū)中已有物品數(shù)，初值為表示緩沖區(qū)中已有物品數(shù)，

22、初值為0。l指針指針k和和r分別表示生產(chǎn)者和消費者存取物分別表示生產(chǎn)者和消費者存取物品的相對位置品的相對位置3435m個生產(chǎn)者和個生產(chǎn)者和r個消費者共享個消費者共享N條記錄的緩沖區(qū)條記錄的緩沖區(qū) 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生產(chǎn)者生產(chǎn)者消費者消費者生產(chǎn)物品生產(chǎn)物品放入放入B中中B中取物品中取物品消費之消費之36環(huán)形緩沖區(qū)環(huán)形緩沖區(qū)10K-1in(in+1)mod kout(out+1)mod k37問題分析問題分析生產(chǎn)者活動生產(chǎn)者活動： 消費者活動消費者活動： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱

23、中 消耗這件物品消耗這件物品 while(1) while(1)資源：箱子（同種組合）資源：箱子（同種組合） 資源：物品（同種組合）資源：物品（同種組合）Var S1:semaphore; Var S2:semaphore; S1.value=k; S2.value=0;放前：放前：P（S1） 取前：取前：P（S2）放后：放后：V（S2） 取后：取后：V（S1）38同步同步生產(chǎn)者活動生產(chǎn)者活動： 消費者活動消費者活動： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) 消耗這件物品消耗這件物

24、品 Until false Until false對B和in,out的互斥：Var mutex:semaphore; (mutex.value=1)39互斥互斥生產(chǎn)者活動：生產(chǎn)者活動： 消費者活動：消費者活動： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品消耗這件物品 Until false Until false40程序程序Program producers_consumers;Var B:Array

25、0,k-1Of item; S1,S2,mutex:semaphore; in,out:0.k-1;Procedure producer cycle produce a product P(S1); P(mutex); Bin:=product; in:=(in+1)mod k; V(mutex); V(S2) endProcedure consumer cycle P(s2); P(mutex); x:=Bout; out:=(out+1)mod k; V(mutex); V(S1); consume x; end;41程序程序l并發(fā)進(jìn)程即要同步又要互斥，必須把互斥并發(fā)進(jìn)程即要同步又要互斥，

26、必須把互斥信號量上信號量上P操作放在同步信號量上操作放在同步信號量上P操作之操作之后后lV操作的次序只影響釋放哪個等待者的問操作的次序只影響釋放哪個等待者的問題，只關(guān)系到釋放的先后次序，不影響并題，只關(guān)系到釋放的先后次序，不影響并發(fā)進(jìn)程執(zhí)行的正確性。發(fā)進(jìn)程執(zhí)行的正確性。 42程序程序l本題本題P操作的次序非常重要操作的次序非常重要l對生產(chǎn)者，只有緩沖區(qū)沒有放滿物品對生產(chǎn)者，只有緩沖區(qū)沒有放滿物品(調(diào)用調(diào)用p(s1)才查看是否有進(jìn)程在訪問緩沖區(qū)才查看是否有進(jìn)程在訪問緩沖區(qū)(調(diào)用調(diào)用p(mutex)l若先調(diào)用若先調(diào)用p(mutex)，可能出現(xiàn)占有使用緩沖，可能出現(xiàn)占有使用緩沖區(qū)的權(quán)力但由于緩沖區(qū)滿

27、，在調(diào)用區(qū)的權(quán)力但由于緩沖區(qū)滿，在調(diào)用p(s1)時等時等待待l消費者想取物品卻得不到使用緩沖區(qū)的權(quán)力，消費者想取物品卻得不到使用緩沖區(qū)的權(quán)力，只好等待只好等待l任何一個進(jìn)程都不能訪問緩沖區(qū)。任何一個進(jìn)程都不能訪問緩沖區(qū)。 43程序程序Begin S1.value:=k; S2.value:=0; mutex.value:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: consumer; Coend;End.44并發(fā)性提高策略并發(fā)性提高策略只有生產(chǎn)者才訪問變量只有生產(chǎn)者才訪問變量in,只有消

28、費者才訪問變量只有消費者才訪問變量out為提高并發(fā)性為提高并發(fā)性, 可將互斥信號量可將互斥信號量mutex分為兩個：分為兩個：mutex1和和mutex2生產(chǎn)者的共享變量：生產(chǎn)者的共享變量： Bin， in消費者的共享變量消費者的共享變量： Bout，outin=out: 滿或空滿或空,Var mutex1,mutex2:semaphore; (init 1)45并發(fā)性提高策略并發(fā)性提高策略生產(chǎn)者活動：生產(chǎn)者活動： 消費者活動：消費者活動： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱

29、中物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗這件物品消耗這件物品 Until false Until false46例例2. 讀者讀者/寫者問題寫者問題P. T. Courtois 1971Communication of the ACM, Vol.14, 667-669.ACM: Association for Computing Machinery解法解法1：寫者可能餓死：寫者可能餓死解法解法2：寫者優(yōu)先：寫者優(yōu)先47例例2. 讀者讀者/寫者問題寫者問題l設(shè)有一組共享數(shù)據(jù)設(shè)有一組共享數(shù)據(jù)DB和兩組并發(fā)進(jìn)程和兩組并發(fā)進(jìn)程, 一組進(jìn)程一組進(jìn)程只對此組數(shù)據(jù)

30、執(zhí)行讀操作只對此組數(shù)據(jù)執(zhí)行讀操作, 另一組進(jìn)程可對此組另一組進(jìn)程可對此組數(shù)據(jù)執(zhí)行寫操作。將前一組進(jìn)程稱作讀者，后一數(shù)據(jù)執(zhí)行寫操作。將前一組進(jìn)程稱作讀者，后一組進(jìn)程稱作寫者組進(jìn)程稱作寫者 48例例2. 讀者讀者/寫者問題寫者問題Problem Statement: 一組公共數(shù)據(jù)一組公共數(shù)據(jù)DB R1 Rm W1 . Wn要求要求：（1）R-R可以同時可以同時 （2）R-W不可同時不可同時 （3）W-W不可同時不可同時accessing49Solution1: 不考慮不考慮R-R不互斥不互斥Var r_w_w:semaphore; (initial value: 1)Reader： Writer:

31、 P（r_w_w); P(r_w_w) 讀操作讀操作 寫操作寫操作 V（r_w_w); V（r_w_w)分析：（分析：（1）寫者活動正確；（）寫者活動正確；（2）R-R不能同時。不能同時。改進(jìn)：最先進(jìn)入的改進(jìn)：最先進(jìn)入的R執(zhí)行執(zhí)行P；最后離開的；最后離開的R執(zhí)行執(zhí)行V；50Solution2: 考慮考慮R-R不互斥不互斥Var read_count:integer; (initial value is 0)Reader: read_count:=read_count+1; If read_count=1 Then P(r_w_w); 讀操作讀操作 read_count:=read_count-

32、1; If read_count=0 Then V(r_w_w);問題：對問題：對Read_count操作的互斥問題。操作的互斥問題。51Solution3: 正確解法正確解法Var mutex:semaphore; (initial value is 1) Reader: P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); 讀操作讀操作 P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex); 讀

33、者等待在何處？讀者等待在何處？ 讀者如何被喚醒？讀者如何被喚醒？52程序程序Program readers_writers;Var r_w_w: semaphore; mutex:semaphore; read_count: integer;procedure writer;begin P(r_w_w); write ops V(r_w_w)end;53程序（程序（Cont.）begin read_count:=0; r_w_w.value:=1; mutex.value:=1; cobegin r1: reader; ; rm: reader; w1: writer; ,; wn: writ

34、er coendend.54C語言描述語言描述55分析：分析：問題問題：讀者源源不斷，：讀者源源不斷，read_count不歸不歸0，寫者，寫者會被餓死。會被餓死。策略策略：一旦有寫者等待，新到達(dá)讀者等待，正在：一旦有寫者等待，新到達(dá)讀者等待，正在讀的讀者都結(jié)束后，寫者進(jìn)入。讀的讀者都結(jié)束后，寫者進(jìn)入。 Further improvement is left to interested students.56例例3. 吸煙者問題吸煙者問題Cigarette Smokers ProblemlProblem lThere are four processes in this problem: th

35、ree smoker processes and an agent processlEach of the smoker processes will make a cigarette and smoke it.lTo make a cigarette requires tobacco, paper, and matches57例例3. 吸煙者問題吸煙者問題Cigarette Smokers ProblemlEach smoker process has one of the three items. lone process has tobaccolanother has paperland

36、 a third has matcheslThe agent has an infinite supply of all threelThe agent places two of the three items on the table, and the smoker that has the third item makes the cigarettelSynchronize the processes58例例3. 吸煙者問題吸煙者問題Cigarette Smokers ProblemlSolution lThe three smoker processes will make a cig

37、arette and smoke itlIf they cant make a cigarette, then they will go to sleeplThe agent process will place two items on the table, and wake up the appropriate smoker, and then go to sleeplAll semaphores except lock are initialized to 0. lock is initialized to 1, and is a mutex variable. 59吸煙者問題吸煙者問題

38、-problem statement3 supplier processes: X: supplies tobacco and match; Y: supplies match and wrapper; Z: supplies wrapper and tobacco.3 smoker processes: A: possess tobacco; B: possess match; C: possess wrapper.(1) only one of X,Y,Z can supply at a time;(2) X,Y,Z can proceed only after consumption.6

39、0Traditional semaphore:Var t,m,w,s:semaphore; (0,0,0,1)Process X process Y process Z P(s); P(s); P(s); V(t); V(m); V(w); V(m); V(w); V(t);Process A Process B process C P(m); P(w); P(t); P(w); P(t); P(m); smoke; smoke; smoke; V(s); V(s); V(s);61Simultaneous P-operationHeres the code for the agent pro

40、cess. 1 do forever 2 P( lock ); 3 randNum = rand( 1, 3 ); / Pick a random number from 1-3 4 if ( randNum = 1 ) 5 / Put tobacco on table 6 / Put paper on table 7 V( smoker_match ); / Wake up smoker with match 8 else if ( randNum = 2 ) 9 / Put tobacco on table10 / Put match on table11 V( smoker_paper

41、); / Wake up smoker with paper12 else 13 / Put match on table14 / Put paper on table15 V( smoker_tobacco ); / Wake up smoker with tobacco16 V( lock );17 P( agent ); / Agent sleeps18 / end forever loop62Simultaneous P-operation give code to one of the smokers. The others are analogous. 1 do forever 2 P( smoker_tobacco ); / Sleep right away 3 P( lock ); 4 / Pick up match 5 / Pick up paper 6 V( agent ); 7 V( lock ); 8 / Smoke (but dont inhale). 9 63Simultaneous P-operationlThe smoker immediately sleepslWhen the agent puts the two items on