【2012】第二章--進(jìn)程管理二-----計算機(jī)操縱系統(tǒng)--計算機(jī)科學(xué)與技術(shù)-操作系統(tǒng)-it

1、計算機(jī)操作系統(tǒng),中國民航大學(xué) 馮霞,In fact, P = Probeer ('Try') and V = Verhoog ('Increment', 'Increase by one'). These are the operations embracing the critical section. Dijkstra introduced these ops in 1963,第

2、二章 進(jìn)程管理,進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程的同步問題 進(jìn)程通信 線程,2.4 經(jīng)典進(jìn)程的同步問題,在多道程序環(huán)境下，進(jìn)程同步問題是十分重要的，也是相當(dāng)有趣的問題，因而吸引了不少學(xué)者對它進(jìn)行研究，由此而產(chǎn)了一系列經(jīng)典的進(jìn)程同步問題。進(jìn)程同步：相互合作的進(jìn)程之間需要交換一定的信息，當(dāng)某進(jìn)程未獲得其合作進(jìn)程發(fā)來的信息之前，該進(jìn)程等待，直到該信息到來時才被喚醒繼續(xù)執(zhí)行，從而保證諸進(jìn)程的協(xié)調(diào)運行。,2.4.1 生

3、產(chǎn)者－消費者問題,問題描述一個有限空間的共享緩沖區(qū)，負(fù)責(zé)存放貨物生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放消費者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿,生產(chǎn)者－消費者問題分析,互斥關(guān)系分析任何時刻，只能有一個進(jìn)程在緩沖區(qū)中操作引入互斥信號量信號量為0，表明已有進(jìn)程進(jìn)入臨界區(qū)；同步關(guān)系分析對于“生產(chǎn)者”而言，緩沖區(qū)滿則應(yīng)等待引入同步信號量“empty”，為0表示緩沖區(qū)滿對于“消費者”而言，緩沖區(qū)空則應(yīng)等待引入同步信號量“f

4、ull”，為0表示緩沖區(qū)空,利用記錄型信號量解決生產(chǎn)者—消費者問題,從資源的觀點很容易解這個問題： 有空buf，生產(chǎn)者才能送數(shù)據(jù)，可設(shè)計數(shù)信號量empty，初值為n。 有裝滿數(shù)據(jù)的buf，消費者才能取數(shù)據(jù)，故計數(shù)信號量full，初值為0。 對某個buf應(yīng)互斥使用，設(shè)互斥信號量mutex，初值為1。,Var mutex, empty, full:semaphore∶=1,n,0; buffer:array［0, …, n-

5、1］ of item; in, out: integer∶=0, 0; begin parbegin proceducer:begin repeat … producer an item nextp; … wait(empty);

6、 wait(mutex); buffer(in)∶=nextp; in∶=(in+1) mod n; signal(mutex); signal(full); until false; end,存儲所產(chǎn)生的新項,consumer:begin repeat

7、 wait(full); wait(mutex); nextc∶ =buffer(out); out∶ =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; un

8、til false; end parend end,存儲所要使用的項,,producer an item nextp; … wait(mutex); wait(empty); buffer(in)∶=nextp; in∶=(in+1) mod n; signal(mutex);

9、 signal(full); until false;,consumer:begin wait(full); wait(mutex); nextc∶=buffer(out); out∶ =(out+1) mod n; signal(mutex); signal(empty);,,互換,思考：是否

10、可以將資源信號量和互斥信號量互換？,在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)在同一進(jìn)程中。對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。在每個程序中的多個signal操作的順序無關(guān)緊要，但wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。,記錄型

11、信號量生產(chǎn)者消費者問題的關(guān)鍵,利用AND信號量解決生產(chǎn)者—消費者問題,對生產(chǎn)者——消費者問題，也可利用AND信號量來解決：用Swait(empty,mutex)來代替wait(empty)和wait(mutex)，用Ssignal(mutex,full)來代替signal(mutex)和signal(full)。,var mutex, empty, full:semaphore∶ =1, n, 0; buffer:a

12、rray［0, …, n-1］ of item; in out:integer∶ =0, 0; begin parbegin producer:begin repeat … produce an item in nextp; … Swait(emp

13、ty, mutex); buffer(in)∶=nextp; in∶=(in+1)mod n; Ssignal(mutex, full); until false; end,Wait（empty）,Wait（mutex）,Signal（mutex）,Signal（full）,consumer:begin

14、 repeat Swait(full, mutex); nextc∶=buffer(out); out∶=(out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false

15、; end parend end,Wait（full）,Wait（mutex）,Signal（mutex）,Signal（empty）,同步/互斥信號量的使用方法,互斥信號量必定成對出現(xiàn)：進(jìn)入臨界區(qū)——臨界區(qū)——退出臨界區(qū)同步信號量未必成對出現(xiàn)，依賴于同步關(guān)系的性質(zhì)同步信號量和互斥信號量的操作順序基本原則：互斥信號量永遠(yuǎn)緊鄰臨界區(qū),2.4.2 哲學(xué)家就餐問題,問題描述五個哲學(xué)家坐

16、在圓桌前，每人一份炒飯每個哲學(xué)家兩側(cè)各有一支筷子哲學(xué)家處于吃飯和思考兩種狀態(tài),互斥關(guān)系分析筷子：同一時刻只能有一個哲學(xué)家拿起筷子同步關(guān)系分析就餐：只有獲得兩個筷子后才能進(jìn)餐特殊情況考慮死鎖：如果每個哲學(xué)家都拿起一只筷子，都餓死并行程度：五只筷子允許兩人同時進(jìn)餐,利用記錄型信號量解決哲學(xué)家進(jìn)餐問題,經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷

17、子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下： Var chopstick: array［0 … 4］ of semaphore;,所有信號量均被初始化為1， 第i位哲學(xué)家的活動可描述為： repeat wait(chopstick［i］); wait(chopstick［(i+1) mod 5］);  … eat;

18、 … signal(chopstick［i］); signal(chopstick［(i+1) mod 5］);  … think; until false;,問題：如果哲學(xué)家各自拿起左邊的筷子時？,就會產(chǎn)生死鎖！,對于這樣的死鎖問題可采取以下幾種解決方法:1、至多只允許四個哲學(xué)家同時進(jìn)餐，以保證至少有一個哲學(xué)家

19、能夠進(jìn)餐，最終總會釋放出他所使用過的兩支筷子，而可使更多的哲學(xué)家進(jìn)餐。2、僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時，才允許他拿起筷子進(jìn)餐。3、規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿他右邊的筷子；而偶數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五個哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一個哲學(xué)家能獲得兩支筷子而進(jìn)餐。,利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題,在哲學(xué)

20、家進(jìn)餐問題中，要求每個哲學(xué)家先獲得兩個臨界資源 (筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機(jī)制可獲得最簡潔的解法。Var chopstick: array[0,…,4] of semaphore:=(1,1,1,1,1);Process i Repeat think; Swait(chopstick[(i+1) mod 5],chops

21、tick[i]); eat; Ssignal(chopstick[(i+1) mod 5],chopstick[i]); uniil false；,2.4.3 讀者-寫者問題,問題描述寫者向數(shù)據(jù)區(qū)放數(shù)據(jù)，讀者從數(shù)據(jù)區(qū)獲取數(shù)據(jù)多個讀者可同時讀取數(shù)據(jù)多個寫者不能同時寫數(shù)據(jù)讀者和寫者的控制策略變化多端保證一個writer進(jìn)程必須與其它進(jìn)程互斥地訪問共享對象的同步問題,互斥關(guān)系分

22、析讀者和寫者不能同時進(jìn)入共享數(shù)據(jù)區(qū)多個寫者不能同時進(jìn)入共享數(shù)據(jù)區(qū)多個讀者可以同時進(jìn)入共享數(shù)據(jù)區(qū)同步關(guān)系分析讀者進(jìn)入緩沖區(qū)，寫者必須等待寫者進(jìn)入緩沖區(qū)，讀者必須等待讀者優(yōu)先：一旦有讀者進(jìn)入，則后續(xù)讀者均可進(jìn)入合理順序：讀者在先來的寫者之后寫者優(yōu)先：只要有寫者等待，則后續(xù)讀者必須等待 ?,利用記錄型信號量解決讀者-寫者問題,互斥信號量Wmutex：為實現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r的互斥而設(shè)置；整型變量R

23、eadcount：表示正在讀的進(jìn)程數(shù)目?；コ庑盘柫縭mutex ：實現(xiàn)Writer進(jìn)程對臨界資源Readcount的訪問。,var rmutex, wmutex:semaphore∶=1,1; Readcount:integer∶=0; begin parbegin Reader:begin repeat wait(rmutex);

24、 if readcount=0 then wait(wmutex); readcount∶=readcount+1; signal(rmutex); … perform read operation; … wait(rmutex); readcount∶=readcount-1;

25、 if readcount=0 then signal(wmutex); signal(rmutex); until false; end,writer:begin repeat wait(wmutex); perform write operation; signal(wmut

26、ex); until false; end parendend,利用信號量集機(jī)制解決讀者-寫者問題,讀者—寫者問題，增加了一條限制，即最多只允許RN個讀者同時讀。為此，又引人了一個信號量L，并賦予其初值為RN，通過執(zhí)行wait(L,1,1)操作，來控制讀者的數(shù)目，每當(dāng)有一個讀者進(jìn)入時，都要先執(zhí)行wait(L，1，1)操作，使L的值減1。當(dāng)有RN個讀者進(jìn)入讀后，L便減力0，第RN＋1個讀者要

27、進(jìn)入讀時，必然會因wait(L，1，1)操作失敗而阻塞。,Var RN integer; L, mx:semaphore∶ =RN,1; begin parbegin reader:begin repeat Swait(L,1,1); Swait(mx,1,0); … pe

28、rform read operation; … Ssignal(L,1); until false; end,If L > =1 then L:=L-1 Else waiting endif,If mx > =1 then mx:=mx-0 Else waiting

29、endif,利用信號量集機(jī)制解決讀者-寫者問題,L :=L+1,writer:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end,If mx >

30、=1 and L>=RN then mx:=mx-1; L:=L-RN; Else waiting endif,mx :=mx+1,思考題[2010期末],有一南北向的單行車道，在車道A、B兩端以外一段距離處有減速標(biāo)志和自動計數(shù)系統(tǒng)，A、B兩處設(shè)有信號燈，信號燈的管理要求如下：綠燈行，紅燈停，A、B兩端紅綠燈同時變換，一方紅變綠時另一方綠變紅。綠燈保持到同一方向進(jìn)入的車輛全部駛?cè)階B段,當(dāng)AB之

31、間無車輛行駛時，允許到達(dá)A端(或B端)的車輛駛?cè)階B段，但只準(zhǔn)某一方的車輛進(jìn)入；一方最后一輛車進(jìn)入AB段后，雙向亮紅燈讓車輛全部通過(假設(shè)2分鐘)，然后讓已在等待的任何一方車輛駛?cè)搿Ｔ囉肞V操作管理AB路段車輛的行駛。,2.4.3 睡眠理發(fā)師問題,問題描述一把理發(fā)椅，N把等待座位理發(fā)師為理發(fā)椅上的顧客理發(fā)，沒有顧客就在理發(fā)椅上睡覺有一個顧客時需要叫醒理發(fā)師多個顧客時需要在等待座位上等候,睡眠理發(fā)師問題的信號量解法,互斥關(guān)系分析

32、理發(fā)椅上只能有一位顧客等待座位是有限緩沖區(qū)同步關(guān)系分析只要存在顧客，理發(fā)師就不能睡覺信號量設(shè)計互斥信號量：實現(xiàn)對“等待顧客數(shù)”的互斥同步信號量1：理發(fā)師“睡眠”和“工作”的同步同步信號量2：等待顧客與等待座位的同步,var waiting : integer; /*等候理發(fā)的顧客數(shù)*/ CHAIRS: integer; /*為顧客準(zhǔn)備

33、的椅子數(shù)*/ customers, barbers，mutex : semaphore; customers := 0; barbers := 0; waiting := 0; mutex := 1;,Procedure barber;beginwhile(TRUE); /*理完一人,還有顧客嗎?*/ P(cutomers); /*若無顧客,理發(fā)師睡眠*/

34、 P(mutex); /*進(jìn)程互斥*/ waiting := waiting – 1; /*等候顧客數(shù)少一個*/ V(barbers); /*理發(fā)師去為一個顧客理發(fā)*/ V(mutex); /*開放臨界區(qū)*/ cut-hair( ); /*正在理發(fā)*/en

35、d;,procedure customerbegin P(mutex); /*進(jìn)程互斥*/ if waiting<CHAIRS begin /*看看有沒有空椅子*/ waiting := waiting+1; /* 等候顧客數(shù)加1*/ V(customers); /*必要的話喚醒理發(fā)師*/

36、 V(mutex); /*開放臨界區(qū)*/ P(barbers); /*無理發(fā)師, 顧客坐著養(yǎng)神*/ get-haircut( ); /*一個顧客坐下等理發(fā)*/ end else V(mutex); /*人滿了,走吧!*/end;,2

37、011考研,某銀行提供1 個服務(wù)窗口和10 個供顧客等待的座位。顧客到達(dá)銀行時，若有空座位，則到取號機(jī)上領(lǐng)取一個號，等待叫號。取號機(jī)每次僅允許一位顧客使用。當(dāng)營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述如下：,請?zhí)砑颖匾男盘柫亢蚉、V（或wait()、signal()）操作，實現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。,【解析】Semaphore seets = 10;

38、//表示空余座位數(shù)量的資源信號量，初值為10Semaphore mutex = 1; //管理取號機(jī)的互斥信號量，初值為1，表示取號機(jī)空閑。Semaphore custom = 0; //表示顧客數(shù)量的資源信號量，初值為0,信號量模型匯總分析,優(yōu)點分析徹底解決忙等待弊端，提高OS的管理層次可實現(xiàn)復(fù)雜的同步與互斥情況，特別是多進(jìn)程間通信可最大限度的保證并發(fā)效率缺點分析實現(xiàn)機(jī)制復(fù)雜，互斥和同步關(guān)系分析困難存在死鎖陷阱，需要謹(jǐn)

39、慎小心嚴(yán)密的設(shè)計,思考題,有橋如圖所示，車流方向如箭頭所示?；卮鹣铝袉栴}：,假設(shè)：該橋上每次只能有一輛車行駛，試用信號量的P、V操作實現(xiàn)橋上的交通管理。假設(shè)：該橋上不允許兩車交會，但允許同方向多個車依次通過（即橋上可有多個同方向行駛的車）。試用信號量的P、V操作實現(xiàn)橋上的交通管理。,答案：,.,.,ParBegin Var x: integer; Process P1 Var y, z:integer;

40、 Begin x:=1; y:=0; If x≥1 then y:=y+1; z:=y; End; Process P2 Var t,u:integer; Begin x:=0; t:=0;

41、 If x<1 then t:=t+2; u:=t; End;ParEnd,1、下面是兩個并發(fā)執(zhí)行的進(jìn)程。試回答：1) 它們能正確執(zhí)行嗎（有唯一確定的結(jié)果）？若不能，試舉例說明2)進(jìn)行適當(dāng)修改，使兩個并發(fā)執(zhí)行的進(jìn)程能夠正確執(zhí)行。,課堂討論題,cobegin var x:integer;S;semaphore; S:=1; Process P1

42、 Var y,z:integer; Begin P(S); x:=1; y:=0; If x≥1 then y:=y+1; V(S); z:=y; end process P2 var t,u:integer;

43、 begin P(S); x:=0; t:=0; If x<1 then t:=t+2; V(S); u:=t; EndCoend,2、 對于諸如公共汽車上駕駛員和售票員的工作，如視其為2個進(jìn)程，試用P.V操作控制這類關(guān)系。（可直接在下面加P.V操作，并給出信號

44、量初值） 駕駛員售票員 L1：L2： 停車開車門 開車關(guān)車門goto L1goto L2,,,,,,,,,,,,,,,。。。。。。,。。。。,售票員,司機(jī),3、（北大97研題）某高校計算機(jī)系開設(shè)網(wǎng)絡(luò)課并安排上機(jī)實習(xí)，假設(shè)機(jī)房共有2m臺機(jī)器，有2n名學(xué)生選該課，規(guī)定： （1）每2個學(xué)生組成一組，各占一臺機(jī)器，合作完成上機(jī)實習(xí)。 （2

45、）只有一組2個學(xué)生到齊，并且此時機(jī)房有空閑機(jī)器時，該組學(xué)生才能進(jìn)入機(jī)房。 （3）上機(jī)實習(xí)由一名教師檢查，檢查完畢，一組學(xué)生同時離開機(jī)房，試設(shè)計相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并用P.V操作模擬上機(jī)實習(xí)過程。,4、（國防科大題）設(shè)有三個進(jìn)程P1，P2，P3共用一個緩沖池協(xié)同工作。P1和P2負(fù)責(zé)循環(huán)地分別從設(shè)備1和設(shè)備2上輸入數(shù)據(jù)，“加工”后送入緩沖池，P3負(fù)責(zé)循環(huán)地以任何順序從緩沖池中取數(shù)據(jù)在設(shè)備3上輸出。緩沖池中共有9個長度相等的緩沖區(qū)（進(jìn)程每次傳輸

46、的數(shù)據(jù)與緩沖區(qū)長度相同），初始均為空。利用兩個棧S1和S2分別記錄空，滿緩沖區(qū)始地址。 （1）試寫出各進(jìn)程工作流程示意圖； （2）進(jìn)程間是否存在臨界區(qū)問題，為什么？ （3）用P.V操作控制各進(jìn)程正確運行。,第二章 進(jìn)程管理,進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程的同步問題 管程機(jī)制 進(jìn)程通信 線程,2.5 管程機(jī)制,信號量機(jī)制是一種既方便又有效的進(jìn)程同步機(jī)制，但每個要訪問臨界資源的進(jìn)程部必須自

47、備同步操作wait(s)和signal(s)，必須成對出現(xiàn)，也不能顛倒。大量的同步操作分散在各個進(jìn)程中，不僅給系統(tǒng)的管理帶來麻煩，而且還會因同步操作的使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖。Hoare(1974)和Hansen(1975)提出了一種高級的同步原語，稱為管程。它與信號量機(jī)制功能等價，且更容易控制。,管程的定義,(Hansan)一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)

48、據(jù)。管程由四部分組成：管程的名稱 局部于管程的共享變量說明，該共享變量表示其相應(yīng)的共享資源的狀態(tài) (通常系統(tǒng)為每個共享資源設(shè)置一個管程)； 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。,圖 2-11 管程的示意圖,管程的語法：,type monitor-name=monitor variable declarations procedure entry P1(…); beg

49、in … end; procedure entry P2(…); begin … end;  … procedure entry Pn(…); begin … end; begin initialization code; end,局部于管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)只能被局部于管程內(nèi)的過程所訪問。局部于管程內(nèi)的過程只能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。管程相當(dāng)于

50、圍墻一樣把共享變量(數(shù)據(jù)結(jié)構(gòu))和對它進(jìn)行的若干操作過程圍了起來。進(jìn)程要共享資源(進(jìn)入圍墻使用某操作過程)就必須經(jīng)過管程(圍墻的門)才能進(jìn)入，進(jìn)程通過調(diào)用管程內(nèi)的一個過程而進(jìn)入管程。管程每次只允許一個進(jìn)程進(jìn)入管程內(nèi)，即互斥地訪問共享資源。即任一時刻只能有一個進(jìn)程在管程中執(zhí)行，其它想進(jìn)入管程的進(jìn)程阻塞，等待管程可用。,條件變量,在利用管程實現(xiàn)進(jìn)程同步時，必須設(shè)置兩個同步操作原語wait和signal。當(dāng)某進(jìn)程通過管程請求獲得臨界資源而

51、未能滿足時，管程便調(diào)用wait原語使該進(jìn)程等待，排在等待隊列；僅當(dāng)另一進(jìn)程訪問完成并釋放該資源之后，管程才調(diào)用signal原語，喚醒等待隊列的隊首進(jìn)程。,條件變量,考慮一種情況：當(dāng)一個進(jìn)程調(diào)用了管程，在管程中被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期間，如果該進(jìn)程不釋放管程，則其他進(jìn)程無法進(jìn)入管程，被迫長時間等待。為此，引入條件變量。表示方法：管程中對每個條件變量，都須予以說明其形式為：Var x, y:condition

52、該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal正在調(diào)用管程的進(jìn)程因X條件需要被阻塞或掛起,則調(diào)用X.wait將自己插入到X條件的等待隊列，并釋放管程，直到X條件變化正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)X條件發(fā)生了變化，則調(diào)用X.signal，重新啟動一個因X條件而阻塞或掛起的進(jìn)程。,與信號量的區(qū)別：X.signal操作的作用，是重新啟動一個被阻塞的進(jìn)程，但如果沒有被阻塞的進(jìn)程，則X.signal操作不產(chǎn)生任何后果

53、。而信號量總是要執(zhí)行s∶=s+1操作，從而改變信號量的狀態(tài)。,條件變量,互斥與同步,互斥：管程的特性，使它們能有效的完成互斥。進(jìn)入管程時的互斥由編譯器負(fù)責(zé)，寫管程的人無需關(guān)心同步：條件變量及兩個相關(guān)操作wait和signal條件變量（condition variables）x ：表示等待原因。x.wait：執(zhí)行該操作的進(jìn)程阻塞，直至其它進(jìn)程執(zhí)行x.signalx.signal：喚醒x等待隊列中的一個進(jìn)程。如果x等待隊列中無進(jìn)

54、程阻塞，該操作不產(chǎn)生任何作用。,說明：進(jìn)程Q因執(zhí)行x.wait處于阻塞狀態(tài)，后來進(jìn)程P執(zhí)行了x.signal而將進(jìn)程Q喚醒。為了避免管程中同時有兩個活躍進(jìn)程，需要有一條規(guī)則來決定讓P和Q誰執(zhí)行、誰等待。處理方式1：P執(zhí)行；Q等待。處理方式2：Q執(zhí)行；P等待。（Hoare采用）處理方式3：執(zhí)行signal的進(jìn)程必須立即退出管程，即signal語句只可能作為一個管程過程的最后一條語句。（Hansen建議）,互斥與同步,利用管程解決生

55、產(chǎn)者-消費者問題,使用有N個緩沖區(qū)的環(huán)形緩沖區(qū)，每個緩沖區(qū)可容納一個數(shù)據(jù)記錄。In是空緩沖區(qū)頭指針，Out是滿緩沖區(qū)頭指針。用notfull作為滿緩沖區(qū)的條件變量，notempty作為空緩沖區(qū)的條件變量。用Count作為當(dāng)前滿緩沖區(qū)數(shù)量。,建立一個管程，并命名為Proclucer-Consumer, 或簡稱為PC。其中包括兩個過程：,(1) put(item)過程。 生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中， 并用整型變量c

56、ount來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過程。消費者利用該過程從緩沖池中取出一個產(chǎn)品，當(dāng)count≤0時，表示緩沖池中已無可取用的產(chǎn)品， 消費者應(yīng)等待。,type producer-consumer=monitor var in,out,count:integer; buffer:array［0,…,n-1］ of

57、 item; notfull, notempty:condition; procedure entry put(item) begin if count≥n then notfull.wait; buffer(in)∶=nextp; in∶=(in+1) mod n; co

58、unt∶=count+1; if notempty.queue then notempty.signal; end procedure entry get(item) begin if count≤0 then notempty.wait; nextc∶=buffer(out);

59、 out∶=(out+1) mod n; count∶=count-1; if notfull.quene then notfull.signal; end begin in∶= out∶=0; count∶=0 end,PC管程描述：,在利用管程解決生產(chǎn)者-消費者問題時， 其中的生產(chǎn)者和消費者可描述為：,pro

60、ducer:begin repeat produce an item in nextp; PC.put(item); until false; end consumer:begin

61、 repeat PC.get(item); consume the item in nextc; until false; end,第二章 進(jìn)程管理,進(jìn)程的基本概念 進(jìn)程控制

62、進(jìn)程同步 經(jīng)典進(jìn)程的同步問題 管程機(jī)制 進(jìn)程通信 線程,2.6 進(jìn)程通信（Inter-Process Communication）,進(jìn)程通信：進(jìn)程之間的信息交換。 (各進(jìn)程為了保持聯(lián)系而換信息)高級進(jìn)程通信：用戶可直接利用OS所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。低級進(jìn)程通信：所交換的信息量相對較少。例如進(jìn)程之間的互斥和同步。,信號量機(jī)制作為同步工具卓有成效，作為通信工具，不夠理想:效率低通信對用戶不透

63、明高級進(jìn)程通信，隱藏了實現(xiàn)細(xì)節(jié)，對用戶透明，減少了通信程序編制的復(fù)雜性,2.6.1 進(jìn)程通信的類型（高級通信機(jī)制）,共享存儲器系統(tǒng)(Shared-Memory System)消息傳遞系統(tǒng)(Message passing system)管道(Pipe)通信,共享存儲器系統(tǒng),共享存儲器（shared-memory）方法的主要思想是：進(jìn)程之間通過共享某些數(shù)據(jù)結(jié)構(gòu)或存儲區(qū)實現(xiàn)信息傳送。有兩種類型：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 （例：生產(chǎn)

64、者—消費者問題中的有界緩沖區(qū)，屬于低級通信方式）基于共享存儲區(qū)的通信方式：在存儲器中劃出一塊共享存儲區(qū)，諸進(jìn)程通過對共享存儲區(qū)中數(shù)據(jù)的讀或?qū)憣崿F(xiàn)通信（傳輸大量數(shù)據(jù)，屬于高級通信）。,消息傳遞系統(tǒng),當(dāng)前應(yīng)用最廣泛的進(jìn)程間通信機(jī)制。系統(tǒng)提供發(fā)送消息Send(message)與接收消息Receive(message) 兩個操作，進(jìn)程間則通過使用這兩個操作進(jìn)行通訊，無需共享任何變量。我們稱這種由操作系統(tǒng)實現(xiàn)的通信方法為高級通信。實現(xiàn)方式

65、的不同分成直接通信方式和間接通信方式兩種。進(jìn)程間的數(shù)據(jù)交換，以格式化的消息為單位。所謂“信息”通常由消息頭和消息正文構(gòu)成。實現(xiàn)了大量數(shù)據(jù)的傳遞，隱藏了實現(xiàn)細(xì)節(jié)，簡化了程序編制復(fù)雜性，使用最廣泛。,type Msg = record msgsender 消息發(fā)送者 msgnext 下一個信息，鏈指針

66、 msgsize 整個消息的字節(jié)數(shù) msgtext 消息正文 end,消息頭,,,消息正文,管道(Pipe)通信,所謂“管道”，是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實現(xiàn)他們之間通信的一個共享文件，又名pipe文件；向管道提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)，以字符流形式將大量的數(shù)據(jù)送人管道；而接收進(jìn)程(即讀進(jìn)程)，可從管道中接收數(shù)

67、據(jù)；這種方式首創(chuàng)于UNIX系統(tǒng)，因它能傳送大量的數(shù)據(jù)，且很有效，故又被引入到許多其它操作系統(tǒng)中。,管道(Pipe)通信,管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力：① 互斥，即當(dāng)一個進(jìn)程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進(jìn)程必須等待。② 同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量的數(shù)據(jù)寫入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。

68、③ 確定對方是否存在，只有確定了對方已存在時，才能進(jìn)行通信。,2.6.2 消息傳遞通信的實現(xiàn)方法,1、直接通信方式發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對方的標(biāo)識符系統(tǒng)提供下述兩條通信命令(原語)： Send(Receiver, message) Receive(Sender, message)例： Send(P2, m1)， Receive(P1，m1),