__進(jìn)程同步與通信(第三版)

1、 第二章 進(jìn)程管理 -進(jìn)程的同步與通信主要內(nèi)容q 進(jìn)程同步的概念q 用硬件方法解決互斥問題q 信號(hào)量機(jī)制q 經(jīng)典進(jìn)程同步問題q 進(jìn)程通信并發(fā)有效地提高了系統(tǒng)資源的利用率但也帶來了一些問題? ?例子：誰買面包？媽媽查看冰箱，面包沒了去超市到達(dá)超市買好面包回家,把面包放入冰箱5:005:055:105:155:205:255:30爸爸查看冰箱，面包沒了去超市到達(dá)超市買好面包回家,把面包放入冰箱噢,Too Much進(jìn)程同步的概念n OS引入進(jìn)程后，由于進(jìn)程的異步性，可能會(huì)導(dǎo)致程序執(zhí)行結(jié)果的不確定性，使程序執(zhí)行時(shí)出現(xiàn)不可再現(xiàn)性。n 任務(wù)：對(duì)多個(gè)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，使并發(fā)執(zhí)行的進(jìn)程有效地共享資源和

2、相互合作，使程序的執(zhí)行具有可再現(xiàn)性。進(jìn)程A進(jìn)程B進(jìn)程同步的概念輸入計(jì)算打印buffer A bufferB等待這種關(guān)系是多個(gè)進(jìn)程在共享資源中形成的。此時(shí)同步的任務(wù)是保證進(jìn)程能互斥的訪問臨界資源。這種關(guān)系是多個(gè)進(jìn)程在合作完成某種工作中形成的。此時(shí)進(jìn)程的同步需要保證相互合作的進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。通知間接相互制約關(guān)系直接相互制約關(guān)系打印機(jī)n 兩種制約關(guān)系進(jìn)程同步概念例：司機(jī)與售票員協(xié)同工作 司機(jī) P1： 售票員 P2： REPEAT REPEAT 運(yùn)行 售票 到站停 開門 UNTIL FALSE 關(guān)門 UNTIL FALSE進(jìn)程同步概念(a) (b) (c) (d)n 臨界資源一次僅允許一個(gè)進(jìn)程

3、（互斥）訪問的資源稱為臨界資源：如輸入機(jī)、打印機(jī)，部分軟資源( (如變量、表格等) )。a=n; /n為剩余的票數(shù)if(a1) a=a-1; /售出一張 n=a;a=n; /n為剩余的票數(shù)if(a1) a=a-1; /售出一張 n=a;臨界資源處理不當(dāng)n 臨界區(qū)多個(gè)進(jìn)程訪問臨界資源的代碼稱為臨界區(qū)。 設(shè)計(jì)原則:q 每次至多允許一個(gè)進(jìn)程處于臨界區(qū)中;q 對(duì)于請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程,在有限時(shí)間內(nèi)只 允許一個(gè)進(jìn)入;q 進(jìn)程只在臨界區(qū)停留有限的時(shí)間;臨界區(qū)開始臨界資源被訪問？訪問臨界區(qū)退出臨界區(qū)執(zhí)行剩余操作未訪問正訪問repeatentry section;exit section;critical s

4、ection;remainder section;until false;臨界區(qū)的訪問流程訪問臨界資源的進(jìn)程描述進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)同步機(jī)制應(yīng)遵循的原則（實(shí)現(xiàn)互斥）q空閑讓進(jìn)：若臨界資源處于空閑狀態(tài)，允許 有進(jìn)入請(qǐng)求進(jìn)程立即進(jìn)入臨界區(qū)訪問q忙則等待：若臨界資源正被訪問，其它進(jìn)程 必須等待q有限等待：必須保證要求訪問臨界資源的進(jìn) 程在有效的時(shí)間內(nèi)進(jìn)入臨界區(qū)訪問，以免“死 等”q讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)釋 放處理機(jī)，以免進(jìn)程陷入“忙等”q 進(jìn)程同步問題描述begin parbegin Pi: Pj: parendend并發(fā)進(jìn)程并發(fā)進(jìn)程用軟件方法解決進(jìn)程互斥問題用硬件方法解決進(jìn)程互斥

5、問題 利用Test-and-Set指令Ts指令指令 function TS(var lock:boolean):boolean; begin TS:=lock; lock:=true; end lock=false時(shí)，資源空閑；lock=true時(shí)，表示資源正在使用。 while TS(lock) do no_op;lock:=false;remainder section;until false;critical section; TS指令實(shí)現(xiàn)互斥repeat用硬件方法解決進(jìn)程互斥問題Ts指令指令 function TS(var lock:boolean):boolean; begin TS

6、:=lock; lock:=true; end Swap指令swap指令(交換指令) procedure Swap(var a,b:boolean) var temp:boolean; begin temp:=a; a:=b; b:=temp; end;用硬件方法解決進(jìn)程互斥問題利用Swap指令實(shí)現(xiàn)進(jìn)程互斥key:=true;repeat swap(lock,key);until key=false; lock:=false;repeat critical section;remainder section;until false;用硬件方法解決進(jìn)程互斥問題練習(xí)： 我們?yōu)槟撑R界區(qū)設(shè)置一把鎖W，

7、當(dāng)W=1時(shí)，表示關(guān)鎖；W=0時(shí)，表示鎖已打開。寫出開鎖原語和關(guān)鎖原語，并利用它們?nèi)?shí)現(xiàn)互斥。critical section;進(jìn)入?yún)^(qū)退出區(qū)while(W=1) do no_op;W:=1;W:=0;lock(w)unlock(w)下面是兩個(gè)進(jìn)程P0、P1互斥使用臨界區(qū)的解決辦法，能否達(dá)到目的？說明原因。設(shè)變量是flag0=flag1=0進(jìn)程Pi：flagi=1;while (flag(i+1)%2=1); Pi的臨界區(qū)代碼；flagi=0;答案：如果執(zhí)行flag0=1,flag1=1 此時(shí)while(flag0=1)成立，無限循環(huán)； while(flag1=1)成立，無限循環(huán)；思考：P0: f

8、lag0=1; while(flag1=1) P0的臨界區(qū)代碼；的臨界區(qū)代碼； flag0=0;P1: flag1=1; while(flag0=1) P1的臨界區(qū)代碼；的臨界區(qū)代碼； flag1=0;整型信號(hào)量機(jī)制wait(s): while s0 do no_op; s:=s-1;signal(s): s:=s+1;整型信號(hào)量是一個(gè)整形量，僅能通過原子操作來訪問。這些操作被稱為P、V操作(wait/signal)(源于荷蘭文passeren /vrijgeven即通過/釋放 )。整型機(jī)制中s 0時(shí)，時(shí)，會(huì)不斷測(cè)試，違背“讓權(quán)等待”。記錄型信號(hào)量type semaphore = record

9、 Value:integer； L:list of process；endprocedure wait(s) 或或P(s) var s:semaphore; begin s.value=s.value-1； if s.value0 then block(s.L) endprocedure signal(s) 或或V(s) var s:semaphore; begin s.value:=s.value+1 if s.value0 then wakeup(s.L); end;L Value.入口入口(S)SS-1S0當(dāng)前進(jìn)程進(jìn)入當(dāng)前進(jìn)程進(jìn)入Q Q指向的等待隊(duì)列指向的等待隊(duì)列進(jìn)程調(diào)度原語進(jìn)程調(diào)度原語

10、返回返回P(S)入口入口(S)SS+1S0喚醒一個(gè)喚醒一個(gè)Q Q指向的指向的等待隊(duì)列中的進(jìn)程等待隊(duì)列中的進(jìn)程返回返回V(S)記錄型信號(hào)量記錄型信號(hào)量物理意義n s.value表示系統(tǒng)中可用的某類資源的數(shù)目；n 執(zhí)行wait（即P）操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的資源；n 當(dāng)s.value0時(shí)，表示資源已分配完畢，因而進(jìn)程調(diào)用 block原語，進(jìn)程自我阻塞，并插入信號(hào)量鏈表中。n s.value1時(shí)，記錄型信號(hào)量，或s=1時(shí)，互斥信號(hào)量；swait(s,1,0)。s1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)s=0時(shí)，將阻止任何進(jìn)程進(jìn)入特定區(qū)。相當(dāng)于可控開關(guān)。解決問題：需訪問N個(gè)某類臨界資源經(jīng)典進(jìn)程同步問題

11、 q生產(chǎn)者消費(fèi)者問題q讀者寫者問題q哲學(xué)者就餐問題生產(chǎn)者消費(fèi)者問題 123456Out Out inin滿緩沖區(qū)空緩沖區(qū)N = 6 個(gè)緩沖區(qū)消費(fèi)者將要取數(shù)據(jù)的位置生產(chǎn)者將要存放數(shù)據(jù)的位置354126Out Out in354126Out Out inin緩沖池問題分析：n 同步關(guān)系表現(xiàn)為：當(dāng)所有緩沖區(qū)均裝滿產(chǎn)品時(shí)，生 產(chǎn)者必須等待消費(fèi)者提供空緩沖區(qū)；當(dāng)所有緩沖區(qū) 全為空時(shí)，消費(fèi)者必須等待生產(chǎn)者提供滿緩沖區(qū)。 n 互斥關(guān)系表現(xiàn)為：由于緩沖池是臨界資源，所以任 何進(jìn)程在對(duì)緩沖區(qū)進(jìn)行存取操作時(shí)都必須和其他進(jìn) 程互斥進(jìn)行。 var mutex,empty,full:semaphore:=1,n,0;b

12、uffer:array0n-1 of item;in,out:integer:=0,0;說明：mutex ：互斥信號(hào)量Empty ：空緩沖區(qū)數(shù)量full：滿緩沖區(qū)數(shù)量生產(chǎn)者消費(fèi)者問題 outin滿空(in+1)mod n(out+1)mod nconsumer: begin repeat wait(full); /阻塞消費(fèi)進(jìn)程 wait(mutex); 取出產(chǎn)品 out:=(out+1) mod n; signal(mutex); signal(empty); /喚醒生產(chǎn)進(jìn)程 消費(fèi)產(chǎn)品 until false; end;producer: begin repeat 生產(chǎn)一個(gè)產(chǎn)品 wait(em

13、pty); /可分配一個(gè)空緩沖區(qū) wait(mutex); /關(guān)閉緩沖區(qū) 將產(chǎn)品放入緩沖區(qū) in:=(in+1) mod n; /輸入指針后移 signal(mutex); /打開緩沖區(qū) signal(full); /喚醒消費(fèi)進(jìn)程 until false; end;思考：q 如果少了signal(full)或signal(empty)， 會(huì)怎樣？q 將兩個(gè)wait(full)和wait(mutex)互換位 置，或?qū)ignal(full)與signal(mutex)互 換，結(jié)果怎樣？q 如果缺少了signal(full)，則消費(fèi)者進(jìn)程在wait(full）處阻 塞，并一直處于阻塞狀態(tài)；如果少了

14、signal(empty)，則生 產(chǎn)者進(jìn)程在產(chǎn)生n個(gè)數(shù)據(jù)后，即緩沖區(qū)滿時(shí)，產(chǎn)生阻塞， 無法生產(chǎn)數(shù)據(jù)?！痉治觥縬 consumer:wait(mutex) mutex:=0; wait(full) full:=-1 阻塞 producer: wait(empty) empty0 wait(mutex) 阻塞若互換signal(full)和signal(mutex)不會(huì)引起死鎖，只使得臨界資源的釋放推遲一點(diǎn)。生產(chǎn)者消費(fèi)者問題 【注意】q wait(mutex)和signal(mutex)必須成對(duì)出現(xiàn)。q empty和full 的P、V操作也需要成對(duì)出現(xiàn)，但 它們處于不同的程序中。q 進(jìn)程中的多個(gè)w

15、ait操作不能顛倒，先執(zhí)行對(duì)資 源信號(hào)量的 wait操作，然后執(zhí)行對(duì)互斥信號(hào)量 的wait操作，否則引起死鎖。讀者寫者問題 共享資源可被寫進(jìn)程和讀進(jìn)程共享。要求：多個(gè)讀進(jìn)程可同時(shí)讀一個(gè)共享對(duì)象，不允許寫進(jìn)程和其它讀進(jìn)程或?qū)戇M(jìn)程同時(shí)訪問共享對(duì)象。var rmutex,wmutex：semaphore:=1,1;readcount :integer:=0;writer: begin repeat wait(wmutex); 寫 signal(wmutex); until false; end;reader: begin repeat wait(rmutex); if readcount=0 the

16、n wait(wmutex); readcount:=readcount+1; signal(rmutex); 讀 wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end;無讀者時(shí)，判斷是否有寫者操作無讀者時(shí)，允許寫者操作讀者寫者問題 rmutex是控制讀者互斥地訪問readcountwmutex是控制讀或?qū)懙幕コ庥眯盘?hào)量集機(jī)制解決讀寫者問題 var RN: integer; /最多允許RN個(gè)讀者同時(shí)讀L,mx:semaphore:=RN

17、,1;reader: begin repeat Swait (L,1,1); Swait (mx,1,0); 讀 Ssignal (L,1); until false; endwriter: begin repeat Swait (mx,1,1;L,RN,0); 寫 Ssignal (mx,1); until false; endq Swait(L,1,1)：有讀者進(jìn)入時(shí)，使L值減1，L為0時(shí)，阻止讀者讀q Swait(mx,1,0)：起開關(guān)作用。mx=1時(shí)表明無寫者，讀進(jìn)程可以進(jìn)入讀。 mx=0，任何reader進(jìn)程就都無法進(jìn)入讀。q Swait(mx,1,1；L,RN,0) ：表示僅當(dāng)即無

18、writer進(jìn)程在寫（mx=1），又無 reader進(jìn)程在讀（L=RN）時(shí)，writer進(jìn)程才能進(jìn)入臨界區(qū)寫。哲學(xué)家進(jìn)餐問題 五個(gè)哲學(xué)家共用一張圓桌，平時(shí)思考問題，饑餓時(shí)拿其左、右最靠近他的筷子，只有兩支筷子都拿到時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子繼續(xù)思考問題。01234var chopstick:array0,4 of semaphore:=(1,1,1,1,1);哲學(xué)家哲學(xué)家i: repeat wait(chopsticki); wait(chopstick(i+1) mod 5; eat; signal(chopsticki); signal(chopstick(i+1) mod 5; thi

19、nk; until false;解決方法：q至多只允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，以保證至少有一個(gè)哲學(xué)家能進(jìn)餐。q僅當(dāng)哲學(xué)家的左、右兩支筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。q規(guī)定奇數(shù)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù) 哲學(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)餐。哲學(xué)家進(jìn)餐問題 若五個(gè)哲學(xué)家都成功持有左邊的筷子時(shí)，系統(tǒng)產(chǎn)生死鎖：var chopstick : array0,4 of semaphore :=(1,1,1,1,1);process

20、i: repeat think; Swait(chopstick(i+1) mod 5,chopsticki); eat; Ssignal(chopstick(i+1) mod 5,chopsticki); until false;：var sm:semaphore:=4; repeat wait(sm); wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal (chopsticki); signal (chopstick(i+1) mod 5); signal(sm); think; until false;哲學(xué)家進(jìn)餐問題 012

21、34philosopher i:repeatif(i%2=0) wait(chopstick(i+1) mod 5); wait(chopsticki); eat; signal (chopstick(i+1) mod 5); signal (chopsticki); think;else wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal (chopsticki); signal (chopstick(i+1) mod 5); think;until false;哲學(xué)家進(jìn)餐問題 【練習(xí)【練習(xí)】1.若信號(hào)量S的初值為10，當(dāng)前值為

22、-3，則表示有_個(gè)等待進(jìn)程。 A. 0 B. 3 C.7 D. 92.設(shè)有10個(gè)進(jìn)程共享同一互斥段，若最多允許有4個(gè)進(jìn)程進(jìn)入互斥段，則所用的互斥信號(hào)量的初值為_。 A. 4 B. 10 C. 7 D. 13.信號(hào)量的值具有明確的物理意義，其值大于等于0時(shí)，其值表示_ _；其值小于0時(shí)，其絕對(duì)值表示 _。等待信號(hào)的進(jìn)程數(shù)目可用資源數(shù)目【例1】：公共汽車上，司機(jī)和售票員各行其職，司機(jī)負(fù)責(zé)開車和到站停車；售票員負(fù)責(zé)售票和開、關(guān)門，當(dāng)售票員關(guān)好車門后，駕駛員才能開車行駛。用P、V操作實(shí)現(xiàn)司機(jī)與售票員間的同步。司機(jī)和售票員的信號(hào)量分別為var S1,S2:semaphore:=0,0司機(jī)： repeat

23、 開車； 停車； V(S2); P(S1); until false; 售票員：repeat 售票； P(S2); 開車門； 關(guān)車門； V(S1); until false;【例2】：用信號(hào)量實(shí)現(xiàn)4*100接力賽的同步過程 P操作:表示等待某個(gè)信號(hào)的到來。V操作:表示發(fā)出一個(gè)信號(hào)。 運(yùn)動(dòng)員運(yùn)動(dòng)員1 運(yùn)動(dòng)員運(yùn)動(dòng)員2 運(yùn)動(dòng)員運(yùn)動(dòng)員3 運(yùn)動(dòng)員運(yùn)動(dòng)員4S1(0)S2(0)S3(0)parbegin athlete1: begin athlete2: begin run； P(S1); V(S1); run; end; V(S2); end; athlete3: begin athlete4: begi

24、n P(S2); P(S3); run; run; V(S3); end; end;parend;【例3】：假設(shè)有3個(gè)并發(fā)進(jìn)程P、Q、R。其中P負(fù)責(zé)從輸入設(shè)備讀入信息并傳送給Q；Q將信息加后傳送給R；R則負(fù)責(zé)將信息打印輸出。進(jìn)程P、Q共享一個(gè)由m個(gè)緩沖區(qū)組成的緩沖池；進(jìn)程Q、R共享另一個(gè)n個(gè)緩沖區(qū)組成的緩沖池。寫出并發(fā)程序。 PQRvar mutex1,mutex2,S1,S2,S3,S4:semaphore:=1,1,m,0,n,0;S1/S2S3/S4P: Q: R: 讀信息；讀信息； P(S2); P(S4); P(S1); P(mutex1); P(mutex2); P(mutex1)

25、; 取數(shù)據(jù)取數(shù)據(jù); 打印數(shù)據(jù)；打印數(shù)據(jù)； 放入數(shù)據(jù)；放入數(shù)據(jù)； V(mutex1); V(mutex2); V(mutex1); V(S1); V(S3); V(S2); 數(shù)據(jù)處理；數(shù)據(jù)處理； P(S3); P(mutex2); 處理后的數(shù)據(jù)放入緩沖區(qū)；處理后的數(shù)據(jù)放入緩沖區(qū)； V(mutex2); V(S4);【作業(yè)】1.有一閱覽室，共有100個(gè)座位。讀者進(jìn)入時(shí)必須先在一張 登記表上登記，該表為每一座位列一表目，包括座號(hào)和讀 者姓名。讀者離開時(shí)要注銷掉登記內(nèi)容。用P、V操作描述 讀者進(jìn)程的同步結(jié)構(gòu)。2.計(jì)算進(jìn)程計(jì)算進(jìn)程打印進(jìn)程打印進(jìn)程單緩沖區(qū)能用從信號(hào)量的兩種不同角度去解決以上問題嗎？提示：

26、q S1:計(jì)算進(jìn)程把計(jì)算結(jié)果放入緩沖區(qū)，然后通知打印進(jìn) 程取走結(jié)果，并使自己處于等待狀態(tài)，等待計(jì)算進(jìn)程將 結(jié)果取走； S2:打印進(jìn)程取走結(jié)果，并向計(jì)算進(jìn)程發(fā)送信號(hào)，使之 繼續(xù)計(jì)算。q 從資源角度理解：sempty:計(jì)算進(jìn)程申請(qǐng)空的緩沖區(qū);打 印進(jìn)程申請(qǐng)帶數(shù)據(jù)的緩沖區(qū)，即sfull。1.var mutex,s:semaphore:=1,100; process readeri: begin P(s); P(mutex); 登記； V(mutex); 閱讀； P(mutex); 刪除登記項(xiàng)； V(mutex); V(s); end;【答案】 2. 第一種方法： var S1,S2:semaphor

27、e:=0,0; 計(jì)算進(jìn)程： repeat 計(jì)算； 將結(jié)果放入緩沖區(qū)； V(S1); P(S2); until false; 打印進(jìn)程： repeat P(S1); 從緩沖區(qū)中取出數(shù)據(jù)； V(S2); 打?。?until false;第二種方法： var Sempty,Sfull:semaphore:=1,0; 計(jì)算進(jìn)程計(jì)算進(jìn)程： repeat 計(jì)算 P(Sempty);將結(jié)果放入緩沖區(qū)； V(Sfull); until false; 打印進(jìn)程打印進(jìn)程： repeat P(Sfull); 從緩沖區(qū)中取出數(shù)據(jù)； V(Sempty); 打?。?until false;管程引入 采用PV同步機(jī)制來編寫

28、并發(fā)程序，對(duì)于共享變量及信號(hào)量變量的操作將被分散于各個(gè)進(jìn)程中。缺點(diǎn)：n 可讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作 是否正確，必須通讀整個(gè)并發(fā)程序。n 不利于修改和維護(hù)：任一組變量或一段代碼的修改都 可能影響全局。n 正確性難以保證：因?yàn)椴僮飨到y(tǒng)或并發(fā)程序通常很 大，要保證這樣一個(gè)復(fù)雜的系統(tǒng)沒有邏輯錯(cuò)誤是很難 的。管程概念 系統(tǒng)中的軟硬件資源都可用數(shù)據(jù)結(jié)構(gòu)加以抽象地描述，即用少量信息和對(duì)該資源所執(zhí)行的操作來表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。 管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)(資源)和能為并發(fā)進(jìn)程所執(zhí)行的一組操作(資源管理)。它包括四部分：管程名稱；局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明；對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)

29、行操作的過程；共享數(shù)據(jù)的初始化序列。 集中式同步機(jī)制，它的基本思想是將共享變量以及對(duì)共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中，并發(fā)程序由若干個(gè)這樣的模塊所構(gòu)成，由于一個(gè)模塊通常較短，模塊之間關(guān)系清晰，提高了可讀性，便于修改和維護(hù)且正確性易于保證。type monitor-name=monitor 定義，指定名稱 variable declarations 共享變量說明 procedure (); 操作定義 begin end; function ():值類型; begin end; begin Initialization code; 初始化序列 end;n局部于管程的數(shù)據(jù)結(jié)構(gòu)，僅能被管程的

30、過程訪問；n進(jìn)程通過調(diào)用管程的過程進(jìn)入管程；n每次僅允許一個(gè)進(jìn)程進(jìn)入管程(互斥訪問)。管程定義 管程是互斥進(jìn)入的，當(dāng)一個(gè)進(jìn)程試圖進(jìn)入一個(gè)已被占用的管程時(shí)它應(yīng)當(dāng)在管程的入口處等待，因此在管程的入口處應(yīng)當(dāng)有一個(gè)進(jìn)程等待隊(duì)列，稱作入口等待隊(duì)列。 如果進(jìn)程P喚醒進(jìn)程Q，則P等待Q繼續(xù)，而進(jìn)程Q在執(zhí)行又喚醒進(jìn)程R，則Q等待R繼續(xù)，因此，在管程內(nèi)部，由于執(zhí)行喚醒操作，可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程，因而還需要有一個(gè)進(jìn)程等待隊(duì)列，這個(gè)等待隊(duì)列被稱為緊急等待隊(duì)列。它的優(yōu)先級(jí)應(yīng)當(dāng)高于入口等待隊(duì)列的優(yōu)先級(jí)。 管程【問題】：多個(gè)進(jìn)程出現(xiàn)在管程中 當(dāng)一個(gè)管程中的進(jìn)程執(zhí)行等待操作時(shí)，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個(gè)進(jìn)入管程的進(jìn)程

31、執(zhí)行喚醒操作時(shí)（如P喚醒Q），管程中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程。處理方法：n P等待Q繼續(xù)，直到Q退出或等待n Q等待P繼續(xù)，直到P等待或退出管程條件變量 利用管程實(shí)現(xiàn)進(jìn)程同步時(shí)，必須設(shè)置同步操作原語wait和signal，當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)，調(diào)用wait使其等待。當(dāng)另一進(jìn)程訪問完并釋放后，調(diào)用signal喚醒等待進(jìn)程。為了描述不同的等待原因引入條件變量condition。 var x,y:condition; 定義條件變量x.wait：表示正在調(diào)用管程的進(jìn)程因x條件需要被阻塞或掛起，并插 入x條件的等待隊(duì)列中。x.signal：表示正在調(diào)用管程的進(jìn)程發(fā)現(xiàn)x

32、條件變化，重新啟動(dòng)因x而 阻塞或掛起的進(jìn)程。區(qū)分兩種signal操作：n 管程的signal操作，啟動(dòng)一個(gè)阻塞進(jìn)程，若沒有進(jìn)程阻塞，則不做 任何事情；n 信號(hào)量signal操作，若無阻塞進(jìn)程，總要執(zhí)行s:=s+1；管程解決生產(chǎn)者消費(fèi)者問題 type producer-consumer=monitor var in,out,count:integer; buffer:array0n-1 of item; notfull,notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(i

33、n):=nextp; in:=(in+1) mod n; count:=count+1; if notempty.queue then notempty.signal; end;procedure entry get(item) begin if count0 then notempty.wait; nextc:=buffer(out); out:=(out+1) mod n; count:=count-1; if notfull.queue then notfull.signal; end;begin in:=out:=0;count:=0;end producer:begin repeat

34、 produce an item in nextp; PC.put(item); until false; end;consumer:begin repeat PC.get(item); consumer the item in nextc; until false; end;管程解決生產(chǎn)者消費(fèi)者問題管程解決哲學(xué)家進(jìn)餐問題Type dining-philosophers=monitor var state:array04 of (thinking,hungry,eating); var self:array04 of condition; Procedure entry pickup(i:04

35、) begin statei:=hungry; test(i); if statei eating then selfi.wait end; Procedure entry putdown(i:04) begin statei:=thinking; test(i+4 mod 5); test(i+1 mod 5); end; Procedure test(k:04) begin if statek+4 mod 5 eating and statek=hungry and statek+1 mod 5 eating then begin statek:=eating; selfk.signal;

36、 end; end; Begin for i:=0 to 4 do statei:=thinking; End;Philosopher i:dining-philosophers.pickup(i)；eating;dining-philosophers.putdown(i);pickup(i:04)：若某哲學(xué)家處于饑餓，且他的左、右哲學(xué)家未進(jìn)餐時(shí)，便允許這位哲學(xué)家進(jìn)餐。否則，執(zhí)行self(i).wait推遲進(jìn)餐。putdown(i:04):當(dāng)哲學(xué)家進(jìn)餐畢，若其左、右的哲學(xué)家都在饑餓且都未用餐時(shí)，可讓他們進(jìn)餐。test(i:04)：測(cè)試哲學(xué)家是否已具備進(jìn)餐條件。管程 VS 進(jìn)程：n 設(shè)置目的不同

37、：管程是對(duì)共享資源進(jìn)行管理；進(jìn)程是資 源分配和執(zhí)行的基本單位。 n 數(shù)據(jù)結(jié)構(gòu)不同：管程定義公用數(shù)據(jù)結(jié)構(gòu)（隊(duì)列）；進(jìn)程 定義私有數(shù)據(jù)結(jié)構(gòu)（PCB）。 n 存在方式不同：管程是操作系統(tǒng)固有的部分，沒有生命 周期；進(jìn)程有生命周期。n 執(zhí)行方式不同：管程被進(jìn)程調(diào)用，沒有并發(fā)性；進(jìn)程具 有并發(fā)執(zhí)行性。 說一說說一說進(jìn)程通信n 低級(jí)通信： 如P、V操作 只能傳遞簡(jiǎn)單的信號(hào)，不能傳遞交換大量信息，效率低。 對(duì)用戶不透明。n 高級(jí)通信： 利用操作系統(tǒng)提供的一組操作命令，傳送數(shù)據(jù)量大。 對(duì)用戶透明。進(jìn)程通信類型（高級(jí)通信）n共享存儲(chǔ)器系統(tǒng)（共享數(shù)據(jù)結(jié)構(gòu)、共享存 儲(chǔ)區(qū)）n消息傳遞系統(tǒng)（直接通信、間接通信）n管道通

38、信消息傳遞通信的實(shí)現(xiàn)方法n直接通信方式Send(receiver,message); Receive(sender,message);n間接通信方式信箱發(fā)送進(jìn)程接收進(jìn)程管道通信管道機(jī)制的協(xié)調(diào)能力：n 互斥：進(jìn)程互斥地讀、寫pipe。n 同步：寫進(jìn)程把數(shù)據(jù)寫入pipe后，便去睡眠 等待，直到讀進(jìn)程把數(shù)據(jù)取走才被喚醒。n 對(duì)方是否存在：確定對(duì)方存在時(shí)，才能通信。pipe寫進(jìn)程讀進(jìn)程消息緩沖隊(duì)列通信機(jī)制（美.Hansan) 消息緩沖區(qū) PCB相關(guān)數(shù)據(jù)項(xiàng)Type message buffer=record Sender :發(fā)送者進(jìn)程標(biāo)識(shí)符 Size :消息長(zhǎng)度 Text :消息正文 Next :指向下

39、一個(gè)消息緩沖區(qū)的指針Type processcontrol block=record mq : 消息隊(duì)列隊(duì)首指針 mutex:消息隊(duì)列互斥信號(hào)量 sm : 消息隊(duì)列資源信號(hào)量PCB(B)發(fā)發(fā)送送區(qū)區(qū)接接收收區(qū)區(qū)消息緩沖區(qū)消息緩沖區(qū)Procedure send(receiver,a)begin getbuf(a.size,i);/根據(jù)a.size申請(qǐng)一個(gè)緩沖區(qū)i i.sender:=a.sender; i.size:=a.size; / 將發(fā)送區(qū)a中的消息 i.text:=a.text; 復(fù)制到消息緩沖區(qū)i中 i.next:=0; getid(PCB set,receiver,j); /獲得接收

40、進(jìn)程的內(nèi)部標(biāo)識(shí)符j wait(j.mutex); insert(j.mq,i); /將i掛在j.mq上 signal(j.mutex); signal(j.sm); end;Procedure receive(b) begin j:=internal name; wait(j.sm); wait(j.mutex); remove(j.mq,i); /從mq隊(duì)列中摘下緩沖區(qū)i signal(j.mutex); b.sender:=i.sender; b.size:=i.size; 數(shù)據(jù)復(fù)制到以b為首址的消息接 收區(qū)內(nèi) b.text:=i.text; end;進(jìn)程進(jìn)程A A進(jìn)程進(jìn)程B B本章小結(jié)桌

41、上有一空盤，只允許放入一個(gè)水果，爸爸專向盤中放蘋果，媽媽專向盤中放桔子，女兒專等著吃盤中的蘋果，兒子專等著吃盤中的桔子。試用P、V操作實(shí)現(xiàn)爸爸、媽媽、兒子、女兒間的同步。分析：盤子中一次只能放入一個(gè)水果，當(dāng)盤子為空時(shí)，爸爸可以放入蘋果，或者媽媽放入桔子。若放入蘋果，則允許女兒吃，若是桔子，則允許兒子吃。n 爸爸：放蘋果n 媽媽：放桔子n 兒子：取桔子、吃桔子n 女兒：取蘋果、吃蘋果作業(yè)Var mutex,S1,S2,S3,S4:semaphore:=1,0,0,0,0;ParbeginFather: Son: repeat repeat P(mutex); P(S4); 將蘋果放入果盤； P(

42、mutex); V(mutex); 取桔子； V(S3); V(mutex); P(S1); V(S1); until false; 吃桔子； until false;Mother: Daughter: repeat repeat P(mutex); P(S3); 將桔子放入果盤； P(mutex); V(mutex); 取蘋果; V(S4); V(mutex); P(S2); V(S2); until false; 吃蘋果； until false;Parend若按以下順序執(zhí)行：Father: P(mutex)； 放蘋果； V(mutex);Mother:P(mutex); 放桔子； V(m

43、utex);情況會(huì)怎樣？錯(cuò)誤分析Var Sempty,Sapple,Sorange:semaphore:=1,0,0;ParbeginFather: Son: begin begin repeat repeat P(Sempty); P(Sorange); 將蘋果放入果盤； 取桔子； V(Sapple); V(Sempty) V(Sempty); 吃桔子； until false; until false; end endMother: Daughter: begin begin repeat repeat P(Sempty); P(Sapple); 將桔子放入果盤； 取蘋果； V(Soran

44、ge); V(Sempty); V(Sempty); 吃蘋果； until false; until false; end endParend若V(Sempty)由Father或Mother自己來完成，會(huì)出現(xiàn)什么情況呢？Father: P(Sempty); 放蘋果； V(Sapple); V(Sempty);Mother: P(Sempty); 放桔子； V(Sorange); 錯(cuò)誤分析var Sempty,S1,S2,S3,S4:semaphore:=1,0,0,0,0;ParbeginFather: Son: repeat repeat P(Sempty); P(S3); 將蘋果放入果盤；

45、 取桔子； V(S1); V(S4); P(S2); V(Sempty); until false; 吃桔子；吃桔子； until false;Mother: Daughter: repeat repeat P(Sempty); P(S1); 將桔子放入果盤； 取蘋果； V(S3); V(S2); P(S4); V(empty); until false; 吃蘋果； until false;Parendvar Sempty,Sapple,Sorange:semaphore:=1,0,0;ParbeginFather: Son: repeat repeat P(Sempty); P(Sorang

46、e); 將蘋果放入果盤； 取桔子； V(Sapple); V(Sempty); until false; 吃桔子； until false;Mother: Daughter: repeat repeat P(Sempty); P(Sapple); 將桔子放入果盤； 取蘋果； V(Sorange); V(Sempty); until false; 吃蘋果； until false;Parend注意 n P(mutex)、V(mutex)在同一程序成對(duì)出現(xiàn)。而且放于訪問臨界資源代碼前后。 如:p(mutex) reader:=reader+1 V(mutex)n 一般信號(hào)量P操作、V操作也成對(duì)出現(xiàn)

47、，但出現(xiàn)在不同的 進(jìn)程中。n 信號(hào)量必須初始化，且其初值不同，其實(shí)現(xiàn)過程也有差別。n 出現(xiàn)連續(xù)兩個(gè)P操作，先后順序要注意。 理發(fā)店有幾位理發(fā)師，一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子，如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)顧客到來時(shí)，必須先喚醒一個(gè)理發(fā)師。如果理發(fā)師正在理發(fā)時(shí)又有顧客到來，則如果有空椅子坐，顧客就坐下來等，否則，離開。思考：Var Customers，barbers，mutex:semaphore:=0,0,1Var waiting:integer:=0理發(fā)師：Begin P(customers) P(mutex) waiting:=waiting-1 V(mutex) V(barbers) 理發(fā)End 顧客： Begin P(mutex) If waitingn then Begin waiting:=waiting+1 V(mutex) V(customer) P(barbers) 允許理發(fā) End Else V(mutex) End進(jìn)程(60年代)擁有資源的獨(dú)立單位獨(dú)立調(diào)度和分派單位線程(80年代)創(chuàng)建撤消切換線程的引入缺點(diǎn)：時(shí)間空間開銷大，限制并發(fā)度的提高。目的：減小上下文切換開銷；提高并