操作系統(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í)通訊進(jìn)程高級(jí)通訊(communication)l系統(tǒng)舉例系統(tǒng)舉例14.3 進(jìn)程同步進(jìn)程同步l進(jìn)程同步是進(jìn)程之間直接的相互作用形式進(jìn)程同步是進(jìn)程之間直接的相互作用形式, 是合作進(jìn)程之間有意識(shí)的行為是合作進(jìn)程之間有意識(shí)的行為，相互作用，相互作用只發(fā)生在相關(guān)進(jìn)程之間只發(fā)生在相關(guān)進(jìn)程之間l4.3.1 進(jìn)程同步的概念進(jìn)程同步的概念 l4.3.2 進(jìn)程同步機(jī)制進(jìn)程同步機(jī)制l4.3.3

2、信號(hào)燈與信號(hào)燈與PV操作操作24.3.1 進(jìn)程同步的概念進(jìn)程同步的概念例：司機(jī)例：司機(jī)-售票員問題售票員問題 34.3.1 進(jìn)程同步的概念進(jìn)程同步的概念l為安全起見為安全起見,，要求，要求l關(guān)車門后方能啟動(dòng)車輛關(guān)車門后方能啟動(dòng)車輛; l到站停車后方能開車門到站停車后方能開車門l“啟動(dòng)車輛啟動(dòng)車輛”應(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í)行到時(shí)應(yīng)將執(zhí)行到時(shí)應(yīng)將P1喚醒喚醒 l如如P2在處發(fā)生了等待在處發(fā)生了等待, 則則P1執(zhí)行到時(shí)應(yīng)將執(zhí)行到時(shí)應(yīng)將P2喚醒喚醒44.3.1 進(jìn)程同步的概念進(jìn)程同步的概念定義：一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點(diǎn)處需要定義：一組進(jìn)程，為協(xié)調(diào)其推進(jìn)速度，在某些關(guān)鍵點(diǎn)處需要相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為相互等待與相互喚醒，進(jìn)程之間這種相互制約的關(guān)系稱為進(jìn)進(jìn)程同步程同步。定義：一組進(jìn)程，如果它們單獨(dú)不能正常進(jìn)行定義：一組進(jìn)程，如果它們單獨(dú)不能正常進(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ī)制進(jìn)程同步機(jī)制l用于實(shí)現(xiàn)進(jìn)程同步的工具稱為用于實(shí)現(xiàn)進(jìn)程同步的工具稱為同步機(jī)制同步機(jī)制（synchronization mechanism）l同步機(jī)制要求：同步機(jī)制要求：l描述能力夠用描述能力夠用;l可實(shí)現(xiàn)可實(shí)現(xiàn);l高效高效;l使用方便使用方便.6典型同步機(jī)制典型同步機(jī)制 l信號(hào)燈與信號(hào)燈與PV操作操作( (semaphore and PV operations) )l管程管程( (monitor) )l會(huì)合會(huì)合(

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

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

7、兩個(gè)部分一個(gè)信號(hào)燈變量包括兩個(gè)部分l值部分值部分s.value l指針部分指針部分s.queuel在任意時(shí)刻在任意時(shí)刻, s.queue可能指向空可能指向空, 也可能指向一個(gè)由也可能指向一個(gè)由進(jìn)程進(jìn)程PCB所構(gòu)成隊(duì)列的頭部所構(gòu)成隊(duì)列的頭部, 如圖如圖 45所示所示. 初始時(shí)初始時(shí)它指向空它指向空94.3.3 信號(hào)燈與信號(hào)燈與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)處理機(jī)調(diào)度程序。轉(zhuǎn)處理機(jī)調(diào)度程序。11V操作原語V操作原語操作原語:void V(semaphore *s) s-value+; if(s-value queue); wakeup(s-queue): 將隊(duì)列將隊(duì)列s-queue頭部進(jìn)程的頭部進(jìn)程的PCB取出并排入就緒隊(duì)列取出并排入就緒隊(duì)列,狀態(tài)由等待轉(zhuǎn)為就緒狀態(tài)由等待轉(zhuǎn)為就緒12規(guī)定和結(jié)論規(guī)定和結(jié)論l對信號(hào)燈變量的規(guī)定：對信號(hào)燈變量的規(guī)定：l必須置一次初值，只能置一次初值，初值必須置一次初值，只能置一次初值，初值=0;l只能執(zhí)行只能執(zhí)行P操作和操作和V操作，操作，所有其它操作非法所有其它操作非法。l幾個(gè)有用的結(jié)論幾個(gè)有用的

9、結(jié)論：l當(dāng)當(dāng)s-value =0時(shí)，時(shí)，s.queue為空；為空；l當(dāng)當(dāng)s-value value初初=1時(shí)，可實(shí)現(xiàn)互斥時(shí)，可實(shí)現(xiàn)互斥，只需在進(jìn)入臨界區(qū)時(shí)執(zhí)行一次，只需在進(jìn)入臨界區(qū)時(shí)執(zhí)行一次P操作操作, 離開臨界區(qū)時(shí)執(zhí)行一次離開臨界區(qū)時(shí)執(zhí)行一次V操作操作 l當(dāng)當(dāng)s-value的初值為正整數(shù)時(shí)，可用來管理同種組合資源的初值為正整數(shù)時(shí)，可用來管理同種組合資源(具有具有多個(gè)實(shí)例的同種類資源，如多個(gè)實(shí)例的同種類資源，如5臺(tái)打印機(jī)臺(tái)打印機(jī))l申請時(shí)執(zhí)行一次申請時(shí)執(zhí)行一次P操作操作l歸還時(shí)執(zhí)行一次歸還時(shí)執(zhí)行一次V 操作操作13信號(hào)燈與信號(hào)燈與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)：將信號(hào)量將信號(hào)量s減減1，若結(jié)果小于，若結(jié)果小于0，則，則調(diào)用調(diào)用P(s)的進(jìn)程被置成等待信號(hào)。的進(jìn)程被置成等待信號(hào)。lV操作操作V(s)：將信號(hào)量將信號(hào)量s加加1，若結(jié)果不大于，若結(jié)果不大于0，釋放一個(gè)等待信號(hào)量釋放一個(gè)等待信號(hào)量s的進(jìn)程。的進(jìn)程。 14信號(hào)燈與信號(hào)燈與PV操作的應(yīng)用操作的應(yīng)用lP操作和操作和V操作可用軟件（或固件）和硬件操作可用軟件（或固件）和硬件來執(zhí)行，它們的執(zhí)行必須是一個(gè)不可被中來執(zhí)行，它們的執(zhí)行必須是一個(gè)不可被中斷的

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

12、執(zhí)行一次V操作意味著進(jìn)程釋放一個(gè)單元的該操作意味著進(jìn)程釋放一個(gè)單元的該類可用資源，描述為類可用資源，描述為s:=s+1，l若若s=0表示信號(hào)量等待隊(duì)列中有因請求該資源而表示信號(hào)量等待隊(duì)列中有因請求該資源而被封鎖的進(jìn)程，需將等待隊(duì)列中的一個(gè)進(jìn)程（往往被封鎖的進(jìn)程，需將等待隊(duì)列中的一個(gè)進(jìn)程（往往是第一個(gè)）喚醒使之進(jìn)入就緒隊(duì)列中是第一個(gè)）喚醒使之進(jìn)入就緒隊(duì)列中17Var mutex: semaphore; (初值=1） shared x,y,z:integer; CR1 CR2 CRn18用信號(hào)燈實(shí)現(xiàn)進(jìn)程互斥用信號(hào)燈實(shí)現(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個(gè)進(jìn)程個(gè)進(jìn)程p1、p2.共享某一資共享某一資源時(shí)，必須找出源時(shí)，必須找出n個(gè)進(jìn)程的臨界個(gè)進(jìn)程的臨界區(qū)，對每個(gè)進(jìn)程區(qū)，對每個(gè)進(jìn)程使用使用PV操作，程操作，程序：序： 20使用使用PV操作操作l粗心使用粗心使用PV操操作會(huì)產(chǎn)生錯(cuò)誤作會(huì)產(chǎn)生錯(cuò)誤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用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步l進(jìn)程的同步進(jìn)程的同步：并發(fā)進(jìn)程之間存在一種制約：并發(fā)進(jìn)程之間存在一種制約關(guān)系，一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程關(guān)系，一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程的消息，當(dāng)一個(gè)進(jìn)程沒有得到另一個(gè)進(jìn)程的消息，當(dāng)一個(gè)進(jìn)程沒有得到另一個(gè)進(jìn)程的消息時(shí)應(yīng)等待，直到消息到達(dá)才被喚醒的消息時(shí)應(yīng)等待，直到消息到達(dá)才被喚醒 23用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步 P(S)后動(dòng)作后動(dòng)作先動(dòng)作先動(dòng)作 V(S)P1:P2:24用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步用信號(hào)燈實(shí)現(xiàn)進(jìn)程同步例子：司機(jī)例子：司機(jī)-

15、售票員問題：售票員問題：VAR s1,s2: semaphore; (initial value 0)司機(jī)活動(dòng)：司機(jī)活動(dòng)： 售票員活動(dòng)：售票員活動(dòng)： Repeat Repeat P(S1) 關(guān)車門關(guān)車門 啟動(dòng)車輛啟動(dòng)車輛 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)者/消費(fèi)者問題消費(fèi)者問題l組合資源：若干相對獨(dú)立的資源構(gòu)成的資源集合，組合資源：若干相對獨(dú)立的資源構(gòu)成的資源集合，其中每個(gè)相對獨(dú)立的資源稱為子資源。其中每個(gè)相對獨(dú)立的資源稱為子資源。l同種組合資源：相同類型子資源構(gòu)成的組合資源。同種組合資源：相同類型子資源構(gòu)成的組合資源。l管理：管理：lVar S:semaphore; (初值初值=子資源個(gè)數(shù)）子資源個(gè)數(shù)）l例子：例子：2臺(tái)打印機(jī)臺(tái)打印機(jī)lVar S:semaphore; S.va

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

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

19、斷地讀入記錄并送入緩沖器中l(wèi)進(jìn)程進(jìn)程B（消費(fèi)者）不斷地從緩沖區(qū)中取出記錄并且加（消費(fèi)者）不斷地從緩沖區(qū)中取出記錄并且加工工l 約束約束l進(jìn)程進(jìn)程A送入數(shù)據(jù)時(shí)，應(yīng)等到送入數(shù)據(jù)時(shí)，應(yīng)等到B發(fā)來消息（發(fā)來消息（已將緩沖區(qū)中已將緩沖區(qū)中的數(shù)據(jù)取走的數(shù)據(jù)取走）才能把下一個(gè)數(shù)據(jù)送入緩沖區(qū)中）才能把下一個(gè)數(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若兩個(gè)進(jìn)程不相互制約，可能出現(xiàn)若兩個(gè)進(jìn)程不相互制約，可能出現(xiàn)A不斷地送入數(shù)據(jù)不斷地送入數(shù)據(jù)導(dǎo)致覆蓋前一條記錄導(dǎo)致覆蓋前一條記錄lB重復(fù)讀一條記錄重復(fù)讀一條記錄l原因：原因：l執(zhí)行的速度不匹配，只有當(dāng)這兩個(gè)進(jìn)程按照一定的速度工執(zhí)行的速度不匹配，只有當(dāng)這兩個(gè)進(jìn)程按照一定的速度工作時(shí)才不會(huì)產(chǎn)生問題，作時(shí)才不會(huì)產(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、題，也可以解決同步問題。定義兩個(gè)信號(hào)量：決同步問題。定義兩個(gè)信號(hào)量：lsp：表示是否可以將物品放入緩沖區(qū)中，由：表示是否可以將物品放入緩沖區(qū)中，由于緩沖區(qū)只能存放一個(gè)物品，于緩沖區(qū)只能存放一個(gè)物品，初值為初值為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)者和消費(fèi)者存取物分別表示生產(chǎn)者和消費(fèi)者存取物品的相對位置品的相對位置3435m個(gè)生產(chǎn)者和個(gè)生產(chǎn)者和r個(gè)消費(fèi)者共享個(gè)消費(fèi)者共享N條記錄的緩沖區(qū)條記錄的緩沖區(qū) 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生產(chǎn)者生產(chǎn)者消費(fèi)者消費(fèi)者生產(chǎn)物品生產(chǎn)物品放入放入B中中B中取物品中取物品消費(fèi)之消費(fèi)之36環(huán)形緩沖區(qū)環(huán)形緩沖區(qū)10K-1in(in+1)mod kout(out+1)mod k37問題分析問題分析生產(chǎn)者活動(dòng)生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)消費(fèi)者活動(dòng)： 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)者活動(dòng)生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)消費(fèi)者活動(dòng)： 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)者活動(dòng)：生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)：消費(fèi)者活動(dòng)： 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、必須把互斥信號(hào)量上信號(hào)量上P操作放在同步信號(hào)量上操作放在同步信號(hào)量上P操作之操作之后后lV操作的次序只影響釋放哪個(gè)等待者的問操作的次序只影響釋放哪個(gè)等待者的問題，只關(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)時(shí)等時(shí)等待待l消費(fèi)者想取物品卻得不到使用緩沖區(qū)的權(quán)力，消費(fèi)者想取物品卻得不到使用緩沖區(qū)的權(quán)力，只好等待只好等待l任何一個(gè)進(jìn)程都不能訪問緩沖區(qū)。任何一個(gè)進(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、費(fèi)者才訪問變量只有消費(fèi)者才訪問變量out為提高并發(fā)性為提高并發(fā)性, 可將互斥信號(hào)量可將互斥信號(hào)量mutex分為兩個(gè)：分為兩個(gè)：mutex1和和mutex2生產(chǎn)者的共享變量：生產(chǎn)者的共享變量： Bin， in消費(fèi)者的共享變量消費(fèi)者的共享變量： Bout，outin=out: 滿或空滿或空,Var mutex1,mutex2:semaphore; (init 1)45并發(fā)性提高策略并發(fā)性提高策略生產(chǎn)者活動(dòng)：生產(chǎn)者活動(dòng)： 消費(fèi)者活動(dòng)：消費(fèi)者活動(dòng)： 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可以同時(shí)可以同時(shí) （2）R-W不可同時(shí)不可同時(shí) （3）W-W不可同時(shí)不可同時(shí)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）寫者活動(dòng)正確；（）寫者活動(dòng)正確；（2）R-R不能同時(shí)。不能同時(shí)。改進(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，寫者，寫者會(huì)被餓死。會(huì)被餓死。策略策略：一旦有寫者等待，新到達(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