操作系統教程第三版南通大學

1、3.4 管程 3.4.1 管程和條件變量3.4.2 管程的實現3.4.3 管程解決進程同步問題3.4.1管程和條件變量 為什么要引入管程v把分散在各進程中的臨界區(qū)集中起來進行管理 ；v防止進程有意或無意的違法同步操作， v便于用高級語言來書寫程序，也便于程序正確性驗證。 管程定義和屬性v管程的定義 管程是由局部于自己的若干公共變量及其說明和所有訪問這些公共變量的過程所組成的軟件模塊。 v管程的屬性 共享性： 安全性： 互斥性：管程的形式vtype 管程名=monitor v 局部變量說明；v 條件變量說明；v 初始化語句；vdefine 管程內定義的，管程外可調用的過程或函數名列表；vuse

2、管程外定義的，管程內將調用的過程或函數名列表；v過程名/函數名(形式參數表) v;v v . v過程名/函數名(形式參數表) v;v v管程的結構condition c1wait(c1)condition cn wait(cn) 局部數據 條件變量 過程/函數1 過程/函數k出口 初始化代碼入口管程等待調用過程的進程隊列管程等待區(qū)管程的條件變量v條件變量-是出現在管程內的一種數據結構，且只有在管程中才能被訪問，它對管程內的所有過程是全局的，只能通過兩個原語操作來控制它。vwait( )-掛起調用進程并釋放管程，直到另一個進程在該條件變量上執(zhí)行signal( )。vsignal( )-如果存在其

3、他進程由于對條件變量執(zhí)行wait( )而被掛起，便釋放之；如果沒有進程在等待，那么，信號不被保存。v條件變量與P、V操作中信號量的區(qū)別?管程問題討論 使用signal釋放等待進程時，可能出現兩個進程同時停留在管程內。解決方法：執(zhí)行signal的進程等待，直到被釋放進程退出管程或等待另一個條件被釋放進程等待，直到執(zhí)行signal的進程退出管程或等待另一個條件v霍爾采用第一種辦法，v漢森選擇兩者的折衷，規(guī)定管程中的過程所執(zhí)行的signal操作是過程體的最后一個操作。 管程與進程作比較管程定義的是公用數據結構，而進程定義的是私有數據結構；管程把共享變量上的同步操作集中起來，而臨界區(qū)卻分散在每個進程中

4、；管程是為管理共享資源而建立的，進程主要是為占有系統資源和實現系統并發(fā)性而引入的；管程是被欲使用共享資源的進程所調用的，管程和調用它的進程不能并行工作，而進程之間能并行工作，并發(fā)性是其固有特性；管程是語言或操作系統的成分，不必創(chuàng)建或撤銷，而進程有生命周期，由創(chuàng)建而產生至撤銷便消亡。3.4.2管程的實現：Hoare方法v霍爾方法使用P和V操作原語來實現對管程中過程的互斥調用，及實現對共享資源互斥使用的管理。v不要求signal操作是過程體的最后一個操作，且wait和signal操作可被設計成可以中斷的過程。 Hoare管程數據結構(1) 1. mutexv對每個管程，使用用于管程中過程互斥調用的

5、信號量mutex（初值為1）。v進程調用管程中的任何過程時，應執(zhí)行P(mutex)；進程退出管程時應執(zhí)行V(mutex)開放管程，以便讓其他調用者進入。v為了使進程在等待資源期間，其他進程能進入管程，故在wait操作中也必須執(zhí)行V(mutex)，否則會妨礙其他進程進入管程，導致無法釋放資源。Hoare管程數據結構(2) 2. next和next-countv對每個管程，引入信號量next（初值為0），凡發(fā)出signal操作的進程應該用P(next)掛起自己，直到被釋放進程退出管程或產生其他等待條件。v進程在退出管程的過程前，須檢查是否有別的進程在信號量next上等待，若有，則用V(next)喚

6、醒它。next-count（初值為0），用來記錄在next上等待的進程個數。 Hoare管程數據結構(3) 3.x-sem和 x-countv引入信號量x-sem（初值為0），申請資源得不到滿足時，執(zhí)行P(x-sem)掛起。由于釋放資源時，需要知道是否有別的進程在等待資源，用計數器x-count（初值為0）記錄等待資源的進程數。v執(zhí)行signal操作時，應讓等待資源的諸進程中的某個進程立即恢復運行，而不讓其他進程搶先進入管程，這可以用V(x-sem)來實現。 Hoare管程數據結構(4) 每個管程定義如下數據結構 ：vtypedef struct InterfaceModulev /Inter

7、faceModule是結構體的名字vsemaphore mutex; v /進程調用管程過程前使用的互斥信號量vsemaphore next; /發(fā)出signal的進程掛起自己的信號量vint next_count; /在next上等待的進程數v;vmutex=1;next=0;next_count=0;/初始化語句Hoare管程的enter( )操作vvoid enter(InterfaceModule &IM) v P(IM.mutex); /互斥進入管程vHoare管程的leave( )操作vvoid leave(InterfaceModule &IM) v /判有否發(fā)出

8、過signal的進程? vif(IM.next_count0) v V(IM.next); v/有就釋放一個發(fā)出過signal的進程v elsev V(IM.mutex); /否則開放管程vHoare管程的wait( )操作vvoid wait(semaphore &x_sem,int &x_count,InterfaceModule &IM) v x_count+;/等資源進程個數加1，x_count初始化為0vif(IM.next_count0)/判有否發(fā)出過signal的進程v V(IM.next); /有就釋放一個velse v V(IM.mutex); /否則

9、開放管程vP(x_sem); /等資源進程阻塞自己，x_sem初始化為0vx_count-; /等資源進程個數減1 vHoare管程的signal( )操作vvoid signal(semaphore &x_sem,int &x_count,InterfaceModule &IM) v if(x_count0) /有等資源進程嗎?vIM.next_count+; /發(fā)出signal進程個數加1v V(x_sem); /釋放一個等資源的進程v P(IM.next); /發(fā)出signal進程阻塞自己v IM.next_count-; /發(fā)出signal進程個數減1v vHo

10、are管程的wait( )操作vvoid wait(semaphore &x_sem,int &x_count,InterfaceModule &IM) v x_count+; v if(IM.next_count0) v V(IM.next); v else v V(IM.mutex); v P(x_sem); v x_count-; vHoare管程的signal( )操作vvoid signal(semaphore &x_sem,int &x_count,InterfaceModule &IM) v if(x_count0) v IM.ne

11、xt_count+; v V(x_sem); v P(IM.next); v IM.next_count-;v v3.4.3 使用管程解決進程同步問題 1霍爾管程解決五個哲學家吃通心面問題(1)vtype dining_philosophers=monitorv enum thinking,hungry,eating state5;v semaphore self5;v int self_count5;v InterfaceModule IM;v for (int i=0;i5;i+)/初始化，i為進程號v statei=thinking;v define pickup,putdown;v u

12、se enter,leave,wait,signal；霍爾管程解決五個哲學家吃通心面問題(2)vvoid pickup(int i) /i=0,1,.,4v enter(IM);vstatei=hungry;vtest(i);vif(statei!=eating)v wait(selfi,self_counti,IM);v leave(IM);vvvoid putdown(int i) /i=0,1,2,.,4v enter(IM);v statei=thinking;v test(i-1)%5);v test(i+1)%5);v leave(IM);v霍爾管程實現五個哲學家吃通心面問題(3)

13、vvoid test(int k) /k=0,1,.,4vif(state(k-1)%5!=eating)&(statek=hungry)v&(state(k+1)%5!=eating) vstatek=eating;vsignal(selfk,self_countk,IM);v v v2管程解決生產者-消費者問題(1)vtype producer_consumer=monitorvitem Bk; /緩沖區(qū)個數vint in,out; /存取指針vint count; /緩沖中產品數vsemaphore notfull,notempty; /條件變量vint notfull_count,notempty_count;vInterfaceModule IM;vdefine append,take;vuse enter,leave,wait,signal；管程解決生產者-消費者問題(2)vvoid append(item x) v enter(IM);vif(count=k) /緩沖已滿v wait(notfull,notfull_count,IM);vBin=x;vin=(in+1)%k;vcount+; /增加一個產品vsignal(notempty,notempty_count,IM); v /喚醒等