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

1、計(jì)算機(jī)操作系統(tǒng),中國(guó)民航大學(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)程的同步問(wèn)題 進(jìn)程通信 線程,2.4 經(jīng)典進(jìn)程的同步問(wèn)題,在多道程序環(huán)境下，進(jìn)程同步問(wèn)題是十分重要的，也是相當(dāng)有趣的問(wèn)題，因而吸引了不少學(xué)者對(duì)它進(jìn)行研究，由此而產(chǎn)了一系列經(jīng)典的進(jìn)程同步問(wèn)題。進(jìn)程同步：相互合作的進(jìn)程之間需要交換一定的信息，當(dāng)某進(jìn)程未獲得其合作進(jìn)程發(fā)來(lái)的信息之前，該進(jìn)程等待，直到該信息到來(lái)時(shí)才被喚醒繼續(xù)執(zhí)行，從而保證諸進(jìn)程的協(xié)調(diào)運(yùn)行。,2.4.1 生

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

4、ull”，為0表示緩沖區(qū)空,利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題,從資源的觀點(diǎn)很容易解這個(gè)問(wèn)題： 有空buf，生產(chǎn)者才能送數(shù)據(jù)，可設(shè)計(jì)數(shù)信號(hào)量empty，初值為n。 有裝滿數(shù)據(jù)的buf，消費(fèi)者才能取數(shù)據(jù)，故計(jì)數(shù)信號(hào)量full，初值為0。 對(duì)某個(gè)buf應(yīng)互斥使用，設(shè)互斥信號(hào)量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ǔ)所產(chǎn)生的新項(xiàng),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,存儲(chǔ)所要使用的項(xiàng),,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、可以將資源信號(hào)量和互斥信號(hào)量互換？,在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)在同一進(jìn)程中。對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。在每個(gè)程序中的多個(gè)signal操作的順序無(wú)關(guān)緊要，但wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。,記錄型

11、信號(hào)量生產(chǎn)者消費(fèi)者問(wèn)題的關(guān)鍵,利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題,對(duì)生產(chǎn)者——消費(fèi)者問(wèn)題，也可利用AND信號(hào)量來(lái)解決：用Swait(empty,mutex)來(lái)代替wait(empty)和wait(mutex)，用Ssignal(mutex,full)來(lái)代替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）,同步/互斥信號(hào)量的使用方法,互斥信號(hào)量必定成對(duì)出現(xiàn)：進(jìn)入臨界區(qū)——臨界區(qū)——退出臨界區(qū)同步信號(hào)量未必成對(duì)出現(xiàn)，依賴于同步關(guān)系的性質(zhì)同步信號(hào)量和互斥信號(hào)量的操作順序基本原則：互斥信號(hào)量永遠(yuǎn)緊鄰臨界區(qū),2.4.2 哲學(xué)家就餐問(wèn)題,問(wèn)題描述五個(gè)哲學(xué)家坐

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

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

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

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

20、家進(jìn)餐問(wèn)題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源 (筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。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 讀者-寫者問(wèn)題,問(wèn)題描述寫者向數(shù)據(jù)區(qū)放數(shù)據(jù)，讀者從數(shù)據(jù)區(qū)獲取數(shù)據(jù)多個(gè)讀者可同時(shí)讀取數(shù)據(jù)多個(gè)寫者不能同時(shí)寫數(shù)據(jù)讀者和寫者的控制策略變化多端保證一個(gè)writer進(jìn)程必須與其它進(jìn)程互斥地訪問(wèn)共享對(duì)象的同步問(wèn)題,互斥關(guān)系分

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

23、eadcount：表示正在讀的進(jìn)程數(shù)目。互斥信號(hào)量rmutex ：實(shí)現(xiàn)Writer進(jìn)程對(duì)臨界資源Readcount的訪問(wèn)。,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,利用信號(hào)量集機(jī)制解決讀者-寫者問(wèn)題,讀者—寫者問(wèn)題，增加了一條限制，即最多只允許RN個(gè)讀者同時(shí)讀。為此，又引人了一個(gè)信號(hào)量L，并賦予其初值為RN，通過(guò)執(zhí)行wait(L,1,1)操作，來(lái)控制讀者的數(shù)目，每當(dāng)有一個(gè)讀者進(jìn)入時(shí)，都要先執(zhí)行wait(L，1，1)操作，使L的值減1。當(dāng)有RN個(gè)讀者進(jìn)入讀后，L便減力0，第RN＋1個(gè)讀者要

27、進(jìn)入讀時(shí)，必然會(huì)因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,利用信號(hào)量集機(jī)制解決讀者-寫者問(wèn)題,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)志和自動(dòng)計(jì)數(shù)系統(tǒng)，A、B兩處設(shè)有信號(hào)燈，信號(hào)燈的管理要求如下：綠燈行，紅燈停，A、B兩端紅綠燈同時(shí)變換，一方紅變綠時(shí)另一方綠變紅。綠燈保持到同一方向進(jìn)入的車輛全部駛?cè)階B段,當(dāng)AB之

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

32、理發(fā)椅上只能有一位顧客等待座位是有限緩沖區(qū)同步關(guān)系分析只要存在顧客，理發(fā)師就不能睡覺(jué)信號(hào)量設(shè)計(jì)互斥信號(hào)量：實(shí)現(xiàn)對(duì)“等待顧客數(shù)”的互斥同步信號(hào)量1：理發(fā)師“睡眠”和“工作”的同步同步信號(hào)量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); /*若無(wú)顧客,理發(fā)師睡眠*/

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

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

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

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

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

39、慎小心嚴(yán)密的設(shè)計(jì),思考題,有橋如圖所示，車流方向如箭頭所示?；卮鹣铝袉?wèn)題：,假設(shè)：該橋上每次只能有一輛車行駛，試用信號(hào)量的P、V操作實(shí)現(xiàn)橋上的交通管理。假設(shè)：該橋上不允許兩車交會(huì)，但允許同方向多個(gè)車依次通過(guò)（即橋上可有多個(gè)同方向行駛的車）。試用信號(hào)量的P、V操作實(shí)現(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、下面是兩個(gè)并發(fā)執(zhí)行的進(jìn)程。試回答：1) 它們能正確執(zhí)行嗎（有唯一確定的結(jié)果）？若不能，試舉例說(shuō)明2)進(jìn)行適當(dāng)修改，使兩個(gè)并發(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、 對(duì)于諸如公共汽車上駕駛員和售票員的工作，如視其為2個(gè)進(jìn)程，試用P.V操作控制這類關(guān)系。（可直接在下面加P.V操作，并給出信號(hào)

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

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

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

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

48、據(jù)。管程由四部分組成：管程的名稱 局部于管程的共享變量說(shuō)明，該共享變量表示其相應(yīng)的共享資源的狀態(tài) (通常系統(tǒng)為每個(gè)共享資源設(shè)置一個(gè)管程)； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。,圖 2-11 管程的示意圖,管程的語(yǔ)法：,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)的過(guò)程所訪問(wèn)。局部于管程內(nèi)的過(guò)程只能訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。管程相當(dāng)于

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

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

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

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

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

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

56、ount來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時(shí)，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無(wú)可取用的產(chǎn)品， 消費(fèi)者應(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)者-消費(fèi)者問(wèn)題時(shí)， 其中的生產(chǎn)者和消費(fèi)者可描述為：,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)程的同步問(wèn)題 管程機(jī)制 進(jìn)程通信 線程,2.6 進(jìn)程通信（Inter-Process Communication）,進(jìn)程通信：進(jìn)程之間的信息交換。 (各進(jìn)程為了保持聯(lián)系而換信息)高級(jí)進(jìn)程通信：用戶可直接利用OS所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。低級(jí)進(jìn)程通信：所交換的信息量相對(duì)較少。例如進(jìn)程之間的互斥和同步。,信號(hào)量機(jī)制作為同步工具卓有成效，作為通信工具，不夠理想:效率低通信對(duì)用戶不透

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

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

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

66、 msgsize 整個(gè)消息的字節(jié)數(shù) msgtext 消息正文 end,消息頭,,,消息正文,管道(Pipe)通信,所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名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)一個(gè)進(jìn)程正在對(duì)pipe執(zhí)行讀/寫操作時(shí)，其它(另一)進(jìn)程必須等待。② 同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量的數(shù)據(jù)寫入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時(shí)，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。

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