Os-04-1_2同步及互斥

1、1計算機操作系統(tǒng)教程(第2版)24.4 .1 進程間的互斥( Mutual Exclusion )為什么要討論互斥？3現(xiàn)代操作系統(tǒng)中進程執(zhí)行的特點：獨立性，異步性，并發(fā)并發(fā)帶來的影響:資源共享（提高資源利用率 如CPU）資源競爭（出現(xiàn)不希望出現(xiàn)的錯誤）4ReadFromFileA ( X ) ；if ( X 1 ) thenX := X - 1；WriteToFileA( X ) ；飛機訂票系統(tǒng)：遠程終端通過位于服務(wù)器主機中的進程Ti處理訂票業(yè)務(wù)；位于服務(wù)器主機中的文件FileA存放的數(shù)據(jù)表示剩余的票數(shù)和下一次即將賣出的座位號25ms50ms5T1ReadFromFileA(X) ；if (

2、X 1 ) thenX := X - 1；WriteToFileA( X ) ；50ms (1)飛機訂票系統(tǒng)：位于武昌的某遠程終端通過位于服務(wù)器主機中的進程 T1 處理訂票業(yè)務(wù)；位于漢口的某遠程終端通過位于服務(wù)器主機中的進程 T2 處理訂票業(yè)務(wù)；T2ReadFromFileA(X) ；if ( X 1 ) thenX := X - 1；WriteToFileA( X ) ；50ms (2)6T1ReadFromFileA(X) ；if ( X 1 ) then25ms (1)T2ReadFromFileA(X) ；if ( X 1 ) thenX := X - 1；25ms (3)WriteT

3、oFileA( X ) ；25ms (2)X := X - 1；25ms (4)WriteToFileA( X ) ；飛機訂票系統(tǒng)：71. 大量共享資源如只讀數(shù)據(jù)可以同時訪問，以提高資源的利用率；2. 部分資源（如外設(shè)、共享數(shù)據(jù)結(jié)構(gòu)），多個進程在對其進行訪問時（主要是進行寫入或修改），可能出現(xiàn)無法預(yù)料的錯誤。提高資源利用率的前提是要保證數(shù)據(jù)的完整性和安全性。進程間的并發(fā)必須加以控制怎么控制？8進程的互斥 Mutual Exclusion1.可以同時使用的2.不可以同時使用的由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程間的這種關(guān)系為進程互斥。兩個概念：臨界資

4、源：critical resource臨界區(qū) ：critical section9系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資源。臨界資源：critical resource10程序 段1程序 段2程序 段n共享變 量11臨界區(qū)（互斥區(qū)）：critical section在進程中涉及到臨界資源的程序段叫臨界區(qū)。多個進程關(guān)于同一臨界資源的一組臨界區(qū)稱為相關(guān)臨界區(qū)集合。12臨界區(qū)的訪問過程的抽象算法entry sectioncritical sectionexit sectionremainder section13進程間互斥問題的解決（P、V操作）P1P(mutex)V(

5、mutex)互斥區(qū)P2P(mutex)V(mutex)P3P(mutex)V(mutex)14進程互斥問題模擬演示有控的進程并發(fā)無控的進程并發(fā)具體實現(xiàn)？154.4 .2 互斥算法1 中斷屏蔽方法2 “測試并設(shè)置”指令3 上鎖原語4 信號量 (semaphore)16臨界區(qū)的訪問過程entry sectioncritical sectionexit sectionremainder section17中斷屏蔽方法“開關(guān)中斷”指令進入臨界區(qū)前執(zhí)行：執(zhí)行“關(guān)中斷”指令離開臨界區(qū)后執(zhí)行：執(zhí)行“開中斷”指令簡單，有效較高的代價，限制CPU并發(fā)能力（臨界區(qū)?。┎贿m應(yīng)多處理器“測試并設(shè)置”指令boolean

6、 TS (boolean*lock)boolean old;old = *lock;*lock = true;Return old;Test-and-Set指令lock表示資源的兩種狀態(tài)：TRUEFALSE占用空閑利用TS實現(xiàn)進程互斥：每個臨界資源設(shè)置一個公共布爾變量lock，初值為FALSE在進入?yún)^(qū)利用TS進行檢查：有進程在臨界區(qū)時，重復(fù)檢查；直到其它進程退出時，檢查通 1819互斥算法（TS指令）while TS(&lock);critical sectionlock = FALSE;remainder section20測試并設(shè)置”指令方法的缺點等待要耗費CPU時間，空轉(zhuǎn)，不能實現(xiàn)“讓權(quán)

7、等待”；每次獲得CPU都要重新測試可能“饑餓”：從等待進程中隨機選擇一個進入臨界區(qū)，有的進程可能一直選不上，不公平21上鎖原語Lock ( x )if( x=true)保護現(xiàn)行進程的CPU現(xiàn)場；現(xiàn)行進程進入x的等待隊列；設(shè)置該進程為等待狀態(tài)；轉(zhuǎn)進程調(diào)度；x=true;UnLock ( x )if (x等待隊列不空) 移出隊列首元素；將進程放入就緒隊列；設(shè)置該進程為就緒狀態(tài)；x=false;22上鎖原語PB remainder section Lock (key ) critical section UnLock (key ) remainder section 23優(yōu)點：不用空轉(zhuǎn)CPU ；缺點

8、：每次被喚醒獲得CPU,還要重新測試；可能會上當不公平現(xiàn)象；上鎖原語24Goto APA和PB反復(fù)使用臨界區(qū)的情況：PAA：lock(key)unlock(key)PBB：lock(key)unlock(key)Goto B25解決上述問題首先必須找到產(chǎn)生問題的原因。顯然，在用加鎖法解決進程互斥的問題時，一個進程能否進入臨界區(qū)是依靠進程自己調(diào)用lock過程去測試相應(yīng)的鎖定位。每個進程能否進入臨界區(qū)是依靠自己的測試判斷。這樣沒有獲得執(zhí)行機會的進程當然無法判斷，從而出現(xiàn)不公平現(xiàn)象。而獲得了測試機會的進程又因需要測試而損失一定的CPU 時間。上鎖原語26這正如某個學(xué)生想使用某個人人都可借用、且不規(guī)定

9、使用時間的教室時一樣，他必須首先申請獲得使用該教室的權(quán)利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復(fù)將持續(xù)到他進門后為止。27一種最直觀的辦法是，設(shè)置一個教室管理員。如果有學(xué)生申請使用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一打開則通知該學(xué)生進入。這樣，既減少了學(xué)生多次來去教室檢查門是否被打開的時間，又減少了因為學(xué)生自發(fā)地檢查造成的不公平現(xiàn)象。28信號量(semaphore)前面的互斥算法都存在問題，它們是平等進程間的一種協(xié)商機制，需要一個地位高于進程的管理者來解決公有資源的使用問題。OS可從進程管理者的角度來

10、處理互斥的問題，信號量就是OS提供的管理公有資源的有效手段。信號量代表可用資源實體的數(shù)量。29信號量和P、V原語1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語 Passeren 和Verhoog 的頭一個字母，相當于英文的Pass和Increment的意思)。P、V是一種卓有成效的進程同步機制。30每個信號量s除一個整數(shù)值s.count（計數(shù)）外，還有一個進程等待隊列s.queue，其中是阻塞在該信號量的各個進程的標識信號量只能通過初始化和兩個標準的原語來訪問作為OS核心代碼執(zhí)行，不受進程調(diào)度的打斷初始化指定一個非負整數(shù)值，表示空閑資源總數(shù)（又稱為資源信號量）若為非負值表示

11、當前的空閑資源數(shù)，若為負值其絕對值表示當前等待臨界區(qū)的進程數(shù)31在整數(shù)值s.count大于等于零時代表可供并發(fā)進程使用的資源實體數(shù)，在整數(shù)值s.count小于零時則表示正在等待使用臨界區(qū)的進程數(shù)。顯然，信號量s的初值應(yīng)該大于零。32原語操作功能原語操作功能331. P原語wait(s)-s.count; /表示申請一個資源;if (s.count 0) /表示沒有空閑資源;調(diào)用進程進入等待隊列s.queue;阻塞調(diào)用進程;342. V原語signal(s)V原語通常喚醒進程等待隊列中的頭一個進程+s.count; /表示釋放一個資源；if (s.count = 0)/表示有進程處于阻塞狀態(tài)；從

12、等待隊列s.queue中取出一個進程P;進程P進入就緒隊列;35重復(fù)或遺漏3. 利用信號量實現(xiàn)互斥P(mutex);critical sectionV(mutex);remainder section為臨界資源設(shè)置一個互斥信號量mutex(MUTualExclusion)，其初值為1；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、36用P、V操作解決進程間互斥問題P1P(mutex)V(mutex)互斥區(qū)P2P(mutex)V(m

13、utex)P3P(mutex)V(mutex)374. 利用信號量來描述前趨關(guān)系前趨關(guān)系：并發(fā)執(zhí)行的進程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成；為每個前趨關(guān)系設(shè)置一個互斥信號量S12，其初值為0P1C1V(S12);P2P(S12);C238經(jīng)典的生產(chǎn)者消費者問題消費者生產(chǎn)者39經(jīng)典的生產(chǎn)者消費者問題（續(xù)1）同步問題：P進程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為SemptyQ進程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量Sfull40Sempty初值為1，Sfull初值為0deposit(data) ：while (true) 生產(chǎn)一個產(chǎn)品;P(Sempty) ;送產(chǎn)品

14、到緩沖區(qū);V(Sfull);remove(data) ：while (true) P(Sfull);從緩沖區(qū)取產(chǎn)品;V(Sempty);消費產(chǎn)品;經(jīng)典的生產(chǎn)者消費者問題（續(xù)2）411 單生產(chǎn)者 單消費者 單緩沖區(qū)2 多生產(chǎn)者 多消費者 單緩沖區(qū)3 單生產(chǎn)者 單消費者 多緩沖區(qū)4 多生產(chǎn)者 多消費者 多緩沖區(qū)經(jīng)典的生產(chǎn)者消費者問題（續(xù)2）互斥：生產(chǎn)者消費者 （對緩沖區(qū)）同步：生產(chǎn)者消費者消費者生產(chǎn)者消費者消費者互斥：生產(chǎn)者消費者生產(chǎn)者生產(chǎn)者同步：生產(chǎn)者消費者消費者生產(chǎn)者互斥：生產(chǎn)者消費者 （對緩沖區(qū)隊列）同步：生產(chǎn)者消費者消費者生產(chǎn)者互斥：生產(chǎn)者消費者 （對緩沖區(qū)隊列）生產(chǎn)者生產(chǎn)者 消費者消費者

15、同步：生產(chǎn)者消費者 消費者生產(chǎn)者42deposit(data)P(Sempty) ;P(Mutex) ;Buf(x)data ;V(Mutex) ;V(Sfull) ;remove(data)P(Sfull) ;P(Mutex) ;dataBuf(x) ;V(Mutex);V(Sempty) ;（1）為互斥設(shè)置一個公用信號量Mutex，初值為1（2）為同步設(shè)置兩個私用信號量Sempty，初值為n；Sfull，初值為0；43注意：P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當為互斥操作時，它們同處于同一進程當為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那

16、么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關(guān)緊要44（1）為互斥設(shè)置一個公用信號量Mutex，初值為1（2）為同步設(shè)置兩個私用信號量empty，初值為n；full，初值為0；deposit(data)P(Mutex) ;P(Sempty) ;Buf(x)data ;V(Mutex) ;V(Sfull) ;remove(data)P(Mutex) ;P(Sfull) ;dataBuf(x) ;V(Mutex);V(Sempty) ;45一家人吃蘋果、桔子問題（1）只有 一個 盤子，盤子中只能放一個水果（2）父親削蘋果，放入盤中（3）母親剝

17、桔子，放入盤中（4）兒子從盤中拿蘋果，吃（5）女兒從盤中拿桔子，吃分析：多生產(chǎn)者、多消費者、單緩沖區(qū) 模型(挑剔的消費者)同步關(guān)系：父親兒子， 母親女兒，兒子（女兒） 父親（母親）46信號量Sapple=0，Sorange=0, Semptyplate=1；father()削蘋果；P(Semptyplate) ;放入盤中 ;V(Sapple) ; mother()剝桔子；P(Semptyplate) ;放入盤中 ;V(Sorange) ; son() P(Sapple) ;從盤中拿蘋果;V(Semptyplate) ;吃蘋果； daughter() P(Sorange) ;從盤中拿桔子;V(S

18、emptyplate) ;吃桔子； 47例:司機P1售票員P2while (true)啟動車輛；正常運行；到站停車；while (true)關(guān)門；售票；開門；1648信號量及P、V操作討論1) 信號量的物理含義：S0表示有S個資源可用S=0表示無資源可用S0則| S |表示S等待隊列中的進程個數(shù)P(S)：表示申請一個資源V(S)：表示釋放一個資源。信號量的初值應(yīng)該大于等于049進程互斥和同步舉例50Windows NTMutex對象：互斥對象，相當于互斥信號量，在一個時刻只能被一個線程使用。有關(guān)的API：CreateMutex創(chuàng)建一個互斥對象，返回對象句柄；OpenMutex返回一個已存在的互

19、斥對象的句柄，用于后續(xù)訪問；ReleaseMutex釋放對互斥對象的占用，使之成為可用；對象可用(signaled state)表示該對象不被任何線程使用或所有；1. NT支持的三種同步對象對象名稱是由用戶給出的字符串。不同進程中用同樣的名稱來創(chuàng)建或打開對象，從而獲得該對象在本進程的句柄。51Semaphore對象：相當于資源信號量，取值在0到指定最大值之間，用于限制并發(fā)訪問的線程數(shù)。有關(guān)的API：CreateSemaphore創(chuàng)建一個信號量對象，指定最大值和初值，返回對象句柄；OpenSemaphore返回一個已存在的信號量對象的句柄，用于后續(xù)訪問；ReleaseSemaphore釋放對信號

20、量對象的占用；52Event對象：事件對象，相當于觸發(fā)器，可通知一個或多個線程某事件的出現(xiàn)。有關(guān)的API：CreateEvent創(chuàng)建一個事件對象，返回對象句柄；OpenEvent返回一個已存在的事件對象的句柄，用于后續(xù)訪問；SetEvent和PulseEvent設(shè)置指定事件對象為可用狀態(tài)；ResetEvent設(shè)置指定事件對象為不可用狀態(tài)（nonsignaled）；手工復(fù)位，并喚醒所有等待線程；532. 同步對象等待(1) WaitForSingleObject在指定的時間內(nèi)等待指定對象為可用狀態(tài)(signaled state)；DWORD WaitForSingleObject( HANDLE

21、 hHandle,/ handle of object to wait for/ time-out interval in millisecondsDWORD dwMilliseconds);(2) WaitForMultipleObjects在指定的時間內(nèi)等待多個對象為可用狀態(tài)；DWORD WaitForMultipleObjects( DWORD nCount,/對象句柄數(shù)組中的句柄數(shù)；CONST HANDLE *lpHandles,/ 指向?qū)ο缶浔鷶?shù)組的指針，數(shù)組中可包括多種對象句柄；BOOL bWaitAll,/ 等待標志：TRUE表示所有對象同時可用，F(xiàn)ALSE表示至少一個對象可用；

22、DWORD dwMilliseconds / 等待超時時限；);544. 其他同步方法Critical Section對象：只能在同一進程內(nèi)使用的臨界區(qū)，同一進程內(nèi)各線程對它的訪問是互斥進行的。把變量說明為CRITICAL_SECTION類型，就可作為臨界區(qū)使用。有關(guān)的API：InitializeCriticalSection對臨界區(qū)對象進行初始化；EnterCriticalSection等待占用臨界區(qū)的使用權(quán)，得到使用權(quán)時返回；TryEnterCriticalSection非等待方式申請臨界區(qū)的使用權(quán)；申請失敗時，返回0；LeaveCriticalSection釋放臨界區(qū)的使用權(quán)；Delet

23、eCriticalSection釋放與臨界區(qū)對象相關(guān)的所有系統(tǒng)資源；55互鎖變量訪問：相當于硬件指令，對一個整數(shù)（進程內(nèi)的變量或進程間的共享變量）進行操作。其目的是避免線程間切換的影響。有關(guān)的API：InterlockedExchange進行32位數(shù)據(jù)的先讀后寫原子操作；InterlockedCompareExchange依據(jù)比較結(jié)果進行賦值的原子操作；InterlockedExchangeAdd先加后存結(jié)果的原子操作；InterlockedDecrement先減1后存結(jié)果的原子操作；InterlockedIncrement先加1后存結(jié)果的原子操作；56管程管程和條件變量霍爾方法實現(xiàn)管程漢森方

24、法實現(xiàn)管程57管程PV操作：分散式同步機制：共享變量操作，PV操作，分散在整個系統(tǒng)中或各個進程中。缺點：可讀性差；正確性不易保證；不易修改。優(yōu)點：高效，靈活。管程：集中式同步工具：共享變量及其所有相關(guān)操作集中在一個模塊中。優(yōu)點：可讀性好；正確性易于保證；易于修改。缺點：不甚靈活，效率略低。58管程：一種同步機制(管程-進程)管程定義:指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作593.4.1 什么是管程為什么要引入管程把分散在各進程中的臨界區(qū)集中起來進行管理 ；防止進程有意或無意的違法同步操作，便于用高級語言來書寫程序，也便于程序正確性驗證。管程的屬性共享性安全性

25、互斥性60管程的形式TYPE monitor_name = MONITOR;共享變量說明define 本管程內(nèi)所定義、本管程外可調(diào)用的過程（函數(shù)）名字表use本管程外所定義、本管程內(nèi)將調(diào)用的過程（函數(shù)）名字表PROCEDURE 過程名（形參表）；過程局部變量說明；BEGIN語句序列；END;.61管程的形式（續(xù)）FUNCTION 函數(shù)名（形參表）：值類型；函數(shù)局部變量說明；BEGIN語句序列；END;.BEGIN共享變量初始化語句序列；END;管程的四個組成部分：名稱共享數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程/函數(shù)初始化語句62管程有如下幾個要素：（一）管程中的共享變量在管程外部是不可見的

26、，外部只能通過調(diào)用管程中所說明的外部過程（函數(shù)）來間接地訪問管程中的共享變量（二）為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入（三）管程通常是用來管理資源的，因而在管程中應(yīng)當設(shè)有進程等待隊列以及相應(yīng)的等待及喚醒操作管程的要素63因為管程是互斥進入的，所以當一個進程試圖進入一個巳被占用的管程時它應(yīng)當在管程的入口處等待，因而在管程的入口處應(yīng)當有一個進程等待隊列，稱作入口等待隊列。管程的實現(xiàn)問題64問題：多個進程出現(xiàn)在管程中當一個進入管程的進程執(zhí)行等待操作時，它應(yīng)當釋放管程的互斥權(quán)；當一個進入管程的進程執(zhí)行喚醒操作時（如喚醒），管程中便存在兩個同時處于活動狀態(tài)的進程，兩者必須有一個退出或停止使

27、用管程。管程的實現(xiàn)問題（續(xù)1）65管程的實現(xiàn)問題（續(xù)1）問題：多個進程出現(xiàn)在管程中處理方法有三種：等待繼續(xù)，直到退出或等待（Hoare）等待繼續(xù)，直到等待或退出規(guī)定喚醒為管程中最后一個可執(zhí)行的操作66管程的實現(xiàn)問題（續(xù)1）如果進程喚醒進程，則等待繼續(xù)，如果進程在執(zhí)行又喚醒進程，則等待繼續(xù)， （Hoare）在管程內(nèi)部，由于執(zhí)行喚醒操作，可能會出現(xiàn)多個等待進程，因而還需要有一個進程等待隊列，這個等待隊列被稱為緊急等待隊列。它的優(yōu)先級應(yīng)當高于入口等待隊列的優(yōu)先級。67由于管程通常是用于管理資源的，因而在管程內(nèi)部，應(yīng)當存在某種等待機制。當進入管程的進程因資源被占用等原因不能繼續(xù)運行時使其等待。(* 資

28、源等待而非管程等待 *)(入口等待隊列和緊急等待隊列都是需要管程)為此在管程內(nèi)部可以說明和使用一種特殊類型的變量，稱作條件變量：VAR C:condition;對于條件型變量，可以執(zhí)行wait和signal操作：管程的實現(xiàn)問題（續(xù)2）68管程的條件變量條件變量當調(diào)用管程過程的進程無法運行時，用于阻塞進程的一種信號量同步原語wait,signal當一個管程過程發(fā)現(xiàn)無法繼續(xù)時，它在某些條件變量condition上執(zhí)行wait，這個動作引起調(diào)用進程阻塞另一個進程可以通過對其伙伴在等待的同一個條件變量condition上執(zhí)行同步原語signal操作來喚醒等待進程。69管程的實現(xiàn)問題（續(xù)3）wait（c

29、）：如果緊急等待隊列非空，則喚醒第一個等待者；否則釋放管程的互斥權(quán)，執(zhí)行此操作的進程的PCB入c鏈尾部signal（c）：如果c鏈為空，則相當于空操作，執(zhí)行此操作的進程繼續(xù)；否則喚醒第一個等待者，執(zhí)行此操作的進程的PCB入緊急等待隊列的尾部70管程的實現(xiàn)問題（續(xù)3）使用signal釋放等待進程時，可能出現(xiàn)兩個進程同時停留在管程內(nèi)解決方法執(zhí)行signal的進程等待，直到被釋放進程退出管程或等待另一個條件被釋放進程等待，直到執(zhí)行signal的進程退出管程或等待另一個條件霍爾采用了第一種辦法漢森選擇了兩者的折衷，規(guī)定管程中的過程所執(zhí)行的signal操作是過程體的最后一個操作71wait(c1)con

30、dition cnwait(cn)urgent queuesignal入口管程等待調(diào)用的進程隊列局部數(shù)據(jù)管程的結(jié)構(gòu)管程等待區(qū)域condition c1條件變量過程1過程k初始化代碼出口72Hoare方法實現(xiàn)管程霍爾方法使用P和V操作原語來實現(xiàn)對管程中過程的互斥調(diào)用，及實現(xiàn)對共享資源互斥使用的管理。不要求signal操作是過程體的最后一個操作，且wait和signal操作可被設(shè)計成可以中斷的過程。73Hoare管程數(shù)據(jù)結(jié)構(gòu)公用信號量mutex對每個管程，使用用于管程中過程互斥調(diào)用的信號量mutex（初值為1）。進程調(diào)用管程中的任何過程時，應(yīng)執(zhí)行P(mutex)；進程退出管程時應(yīng)執(zhí)行V(mutex

31、)開放管程，以便讓其他調(diào)用者進入。為了使進程在等待資源期間，其他進程能進入管程，故在wait操作中也必須執(zhí)行V(mutex)，否則會妨礙其他進程進入管程，導(dǎo)致無法釋放資源。74urgent和urgent-count信 號 量 urgent （ 初 值 為 0 ） ， 凡 發(fā) 出signal操作的進程應(yīng)該用P(urgent)掛起自己，直到被釋放進程退出管程或產(chǎn)生其他等待條件。進程在退出管程的過程前，須檢查是否有別的進程在信號量urgent上等待，若有，則用V(urgent)喚醒它。urgent-count（初值為0），用來記錄在urgent上等待的進程個數(shù)。75x-sem和 x-count引入信

32、號量x-sem（初值為0），申請資源得不到滿足時，執(zhí)行P(x-sem)掛起。用計數(shù)器x-count（初值為0）記錄等待資源的進程數(shù)。執(zhí)行signal操作時，應(yīng)讓等待資源的諸進程中的某個進程立即恢復(fù)運行，而不讓其他進程搶先進入管程，這可以用V(x-sem)來實現(xiàn)。76每個管程定義如下數(shù)據(jù)結(jié)構(gòu)TYPE interf = RECORDmutex:semaphore; /*進程調(diào)用管程過程前使用的互斥信號量*/urgent:semaphore; /*發(fā)出signal的進程掛起自己的信號量*/urgent_count:integer;/*在next上等待的進程數(shù)*/END;77Hoare管程的外部過程形

33、式任何一個調(diào)用管程中過程的外部過程應(yīng)組織成下列形式，確保互斥地進入管程。P(IM.mutex);if IM.urgent_count 0 then V(IM.urgent);else V(IM.mutex);78漢森方法實現(xiàn)管程漢森方法的管程中的過程所執(zhí)行的signal操作一定是過程體的最后一個操作，一個進程當所調(diào)用的過程執(zhí)行了signal操作后，便立即退出了管程。漢森方法使用四條原語WaitSignalCheckre1ease79每個管程使用的一個數(shù)據(jù)類型TYPE interf = RECORDintsem : condition; /* 開放管程的信號量 */count1 : intege

34、r;count2 : integer;END;/* 等待調(diào)用的進程個數(shù) */* 調(diào)用了管程中的過程且不處于等待狀態(tài)的進程個數(shù) */80調(diào)用查看原語check如果管程是開放的，則執(zhí)行這條原語后關(guān)閉管程，相應(yīng)進程繼續(xù)執(zhí)行；如果管程是關(guān)閉的，則執(zhí)行這條原語后相應(yīng)進程被置成等待調(diào)用狀態(tài)procedure check(var IM interf);beginif IM.count2 = 0then IM.count2 := IM.count2 + 1;elsebeginIM.count1 := IM.count1 + 1;W(IM.intsem);end;end;81開放原語release如果除了發(fā)出這

35、條原語的進程外，不再有調(diào)用了管程中過程但又不處于等待狀態(tài)的進程，那么就釋放一個等待者或開放管程procedure release(var IM interf);beginIM.count2 := IM.count2 - 1;if IM.count2 = 0 and IM.count1 0 thenbeginIM.count1 := IM.count1 - 1;IM.count2 := IM.count2 + 1;R(IM.intsem);end;end;82等待原語wait執(zhí)行這條原語后相應(yīng)進程被置成等待狀態(tài)，同時開放管程，允許其它進程調(diào)用管程中的過程procedure wait(var s:

36、condition; var IM interf);begins := s + 1;IM.count2 := IM.count2 1;if IM.count1 0 thenbeginIM.count1 := IM.count1 1;IM.count2 := IM.count2 + 1;R(IM.intsem);end;W(s);end;釋放原語signal執(zhí)行這條原語后釋放指定等待進程隊列中的一個進程。如指定等待進程隊列為空，本操作相當于空操作varIM83procedure signal(var s:condition;interf);beginif s 0 thenbegins := s

37、1;IM.count2 := IM.count2 + 1;R(s);end;end;84利用漢森方法實現(xiàn)的管程實現(xiàn)進程同步時，進程應(yīng)按下列次序工作請求資源使用資源釋放資源85TYPE one_instance=RECORDmutex:semaphore;（初值1）urgent:semaphore;（初值0）urgent_count:integer;（初值0）END;TYPEmonitor_elements=MODULE;define enter,leave,wait,signal;mutex（入口互斥隊列）urgent（緊急等待隊列）urgent_count（緊急等待隊列計數(shù)）86PROCED

38、URE enter(VAR instance:one_instance);BEGINP(instance.mutex)END;87PROCEDURE leave(VARinstance:one_instance);BEGINIF instance.urgent_count 0 THENBEGIN instance.urgent-;V(instance.urgent)ENDELSEV(instance.mutex)END;88PROCEDURE wait(VAR instance:one_instance;VARs:semephore;VAR count:integer);BEGINcount+;IF instance.urgent_count0 THENBEGINinstance.urgent_count-;V(instance.urgent)ENDELSEV(instance. mutex);P(s);END;89PROCEDUREsignal(VAR instance:one_instance;VAR s:semaphore;VAR count:integer);BEGINIF count0 THENBEGINcount-;instance.urgent_count+;V(s);P(instance.urgent)ENDEND;90例子