1、管程-操作系統教程(第3版)什么是?(1)為什么要引入管程把分散在各進程中的臨界區集中起來進行管理 ；防止進程有意或無意的違法同步操作， 便于用高級語言來書寫程序，也便于程序正確性驗證。 什么是管程?(2)管程是由局部于自己的若干公共變量及其說明和所有訪問這些公共變量的過程所組成的軟件模塊 管程有以下屬性共享性：安全性：互斥性：管程的基本形式TYPE = MONITOR ; define ; use ； procedure (); begin ； end; procedure (); begin ； end; begin ； end;管程的結構condition c1wait(c1)condi

2、tion cn wait(cn)Urgent queue signal局部數據條件變量過程1過程k出口初始化代碼入口管程等待調用的進程隊列管程等待區域管程的示例TYPE SSU = MONITOR var busy : boolean; nobusy : semaphore; define require, return; use wait, signal； procedure require; begin if busy then wait(nobusy); /*調用進程加入等待隊列*/ busy := ture； end; procedure return; begin busy := f

3、alse； signal(nobusy); /*從等待隊列中釋放進程*/ end; begin /*管程變量初始化*/ busy := false； end;管程的條件變量(1)條件變量：當調用管程過程的進程無法運行時，用于阻塞進程的一種信號量同步原語wait：當一個管程過程發現無法繼續時，它在某些條件變量condition上執行wait，這個動作引起調用進程阻塞管程的條件變量(2)另一個進程可以通過對其伙伴在等待的同一個條件變量condition上執行同步原語signal操作來喚醒等待進程。條件變量與P、V操作中信號量的區別? 管程的問題討論 使用signal釋放等待進程時，可能出現兩個進程

4、同時停留在管程內。解決方法：執行signal的進程等待，直到被釋放進程退出管程或等待另一個條件被釋放進程等待，直到執行signal的進程退出管程或等待另一個條件霍爾采用了第一種辦法；漢森選擇了兩者的折衷，規定管程中的過程所執行的signal操作是過程體的最后一個操作 管程與進程作比較(1)管程定義的是公用數據結構，而進程定義的是私有數據結構；管程把共享變量上的同步操作集中起來，而臨界區卻分散在每個進程中；管程是為管理共享資源而建立的，進程主要是為占有系統資源和實現系統并發性而引入的；管程與進程作比較(2)管程是被欲使用共享資源的進程所調用的，管程和調用它的進程不能并行工作，而進程之間能并行工作

5、，并發性是其固有特性；管程是語言或操作系統的成分，不必創建或撤銷，而進程有生命周期，由創建而產生至撤銷便消亡。管程實現：Hoare方法霍爾方法使用P和V操作原語來實現對管程中過程的互斥調用，及實現對共享資源互斥使用的管理。不要求signal操作是過程體的最后一個操作，且wait和signal操作可被設計成可以中斷的過程。 Hoare管程數據結構(1) 1. mutex對每個管程，使用用于管程中過程互斥調用的信號量mutex（初值為1）。進程調用管程中的任何過程時，應執行P(mutex)；進程退出管程時應執行V(mutex)開放管程，以便讓其他調用者進入。為了使進程在等待資源期間，其他進程能進入

6、管程，故在wait操作中也必須執行V(mutex)，否則會妨礙其他進程進入管程，導致無法釋放資源。Hoare管程數據結構(2) 2. next和next-count對每個管程，引入信號量next（初值為0），凡發出signal操作的進程應該用P(next)掛起自己，直到被釋放進程退出管程或產生其他等待條件。進程在退出管程的過程前，須檢查是否有別的進程在信號量next上等待，若有，則用V(next)喚醒它。next-count（初值為0），用來記錄在next上等待的進程個數。 Hoare管程數據結構(3) 3. x-sem和 x-count引入信號量x-sem（初值為0），申請資源得不到滿足時，

7、執行P(x-sem)掛起。由于釋放資源時，需要知道是否有別的進程在等待資源，用計數器x-count（初值為0）記錄等待資源的進程數。執行signal操作時，應讓等待資源的諸進程中的某個進程立即恢復運行，而不讓其他進程搶先進入管程，這可以用V(x-sem)來實現。 Hoare管程數據結構 每個管程定義如下數據結構 ：TYPE interf = RECORD mutex:semaphore; /*進程調用管程過程前 使用的互斥信號量*/ next:semaphore; /*發出signal的進程掛起 自己的信號量*/ next_count:integer;/*在next上等待的進 程數*/ END

8、; Hoare的wait操作Procedure wait(var x_sem:semaphore,x_count:integer, IM:interf);begin x_count := x_count + 1; if IM.next_count 0 then V(IM.next); else V(IM.mutex); P(x_sem); X_count := x_count 1;end;Hoare的signal操作procedure signal(var x_sem:semaphore,x_count:integer, IM:interf);begin if x_count 0 then b

9、egin IM.next_count := IM.next_count + 1; V(x_sem); P(IM.next); IM.next_count := IM.next_count - 1; end;end;Hoare的外部過程形式 任何一個調用管程中過程的外部過程應組織成下列形式，確保互斥地進入管程。P(IM.mutex); ;if IM.next_count 0 then V(IM.next); else V(IM.mutex);霍爾方法實現五個哲學家吃通心面問題(1)TYPE dining-philosophers = MONITORvar state : array0.4 of

10、(thinking, hungry, eating); s : array0.4 of semaphore; s-count : array0.4 of integer; define pickup, putdown; use wait, signal；霍爾方法實現五個哲學家吃通心面問題(2)procedure test(k : 0.4);beginif state(k-1) mod 5eating and statek=hungry and state(k+1) mod 5eating then begin statek := eating; signal(sk, s-countk, IM)

11、; end;end; 霍爾方法實現五個哲學家吃通心面問題(3)procedure pickup(i:0.4);begin statei := hungry; test(i); if stateieating then wait(si,s-counti,IM)；end;霍爾方法實現五個哲學家吃通心面問題(4)procedure putdown(i:0.4);begin statei := thinking; test(i-1) mod 5); test(i+1) mod 5);end;begin for i := 0 to 4 do statei := thinking； end;霍爾方法實現五

12、個哲學家吃通心面問題(6)cobegin process philosopher-ibegin P(IM.mutex); call dining-philosopher.pickup(i); if IM.next-count 0 then V(IM.next); else V(IM.mutex); 吃通心面； P(IM.mutex); call dining-philosopher.putdown(i); if IM.next-count 0 then V(IM.next); else V(IM.mutex); end;coend; 管程實現：漢森方法(1)漢森方法的管程中的過程所執行的sig

13、nal操作一定是過程體的最后一個操作，一個進程當所調用的過程執行了signal操作后，便立即退出了管程。漢森方法使用四條原語：wait，signal，check，re1ease實現對管程的控制。管程的實現：漢森方法(2) 每個管程使用的一個數據類型：TYPE interf = RECORD intsem : semaphore; /* 開放管程的信號量 */ count1 : integer; /* 等待調用的進程個數 */ count2 : integer; /* 調用了管程中的過程且不END; 處于等待狀態的進程個數 */管程的實現：漢森方法(3)調用查看原語check： 如果管程是開放的

14、，則執行這條原語后關閉管程，相應進程繼續執行；如果管程是關閉的，則執行這條原語后相應進程被置成等待調用狀態管程的實現：漢森方法(4)procedure check(var IM interf); begin if IM.count2 = 0 then IM.count2 := IM.count2 + 1; else begin IM.count1 := IM.count1 + 1; W(IM.intsem); end; end;管程的實現：漢森方法(5)開放原語release： 如果除了發出這條原語的進程外，不再有調用了管程中過程但又不處于等待狀態的進程，那么就釋放一個等待者或開放管程管程的實

15、現：漢森方法(6)procedure release(var IM interf); begin IM.count2 := IM.count2 - 1; if IM.count2 = 0 and IM.count1 0 then begin IM.count1 := IM.count1 - 1; IM.count2 := IM.count2 + 1; R(IM.intsem); end; end;管程的實現：漢森方法(7)等待原語wait： 執行這條原語后相應進程被置成等待狀態，同時開放管程，允許其它進程調用管程中的過程管程的實現：漢森方法(8)procedure wait(var s:sem

16、aphore; var IM interf); begin s := s + 1; IM.count2 := IM.count2 1; if IM.count1 0 then begin IM.count1 := IM.count1 1; IM.count2 := IM.count2 + 1; R(IM.intsem); end; W(s); end;管程的實現：漢森方法(9)釋放原語signal： 執行這條原語后釋放指定等待進程隊列中的一個進程。如指定等待進程隊列為空，本操作相當于空操作管程的實現：漢森方法(10)procedure signal(var s:semaphore; var I

17、M interf); begin if s 0 then begin s := s 1; IM.count2 := IM.count2 + 1; R(s); end; end;管程的實現：漢森方法(11) 用管程實現進程同步時，進程應按下列次序工作： 請求資源。 使用資源。 釋放資源。漢森方法實現讀者寫者問題(1) 有兩組并發進程：讀者與寫者，共享一個文件，要求：1）允許多個讀者同時執行讀操作；2）任一寫者在完成寫操作之前不允許其他讀者和寫者工作；3）寫者欲工作，要等待已存在的讀者完成讀操作，新的讀者與寫者均被拒絕漢森方法實現讀者寫者問題(2)type read-writer = MONITO

18、R var rc, wc : integer; R, W : semaphore; define start-read, end-read, start-writer, end-writer; use wait, signal, check, release;漢森方法實現讀者寫者問題(3)procedure start-read; begin check(IM); if wc0 then wait(R,IM); rc := rc + 1; signal(R, IM); release(IM); end;procedure end-read;begin check(IM); rc := rc -

19、 1; if rc=0 then signal(W,IM); release(IM);end;漢森方法實現讀者寫者問題(4)procedure start-write;begin check(IM); wc := wc + 1; if rc0 or wc1 then wait(W,IM); release(IM);end;procedure end-write;begin check(IM); wc := wc - 1; if wc0 then signal(W,IM); else signal(R, IM); release(IM);end; 漢森方法實現讀者寫者問題(5)初始化語句begi

20、n rc := 0; wc := 0; R := 0; W := 0; end;漢森方法實現讀者寫者問題(6)cobegin process readerbegin call read-writer.start-read; read; call read-writer.end-read;end; process writerbegin call read-writer.start-write; write; call rear-writer.end-write;end;coend;漢森方法實現蘋果橘子問題(1) 桌上有一只盤子，每次只能放入一只水果，爸爸專向盤中放蘋果，媽媽專向盤中放橘子，一個兒子專吃盤中橘子，一個女兒專吃盤中蘋果漢森方法實現蘋果橘子問題(2)TYPE FMSD = MONITOR var plate : (apple, orange); full : boolean; SP, SS, SD : semaphore; define put, get; use wait, signal, check, release; 漢森方法實現蘋果橘子問題(3)procedure put(var fruit:(apple, orange);begin check(IM); if