Os-04-1_2同步及互斥

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

2、X 1 ) thenX := X - 1；WriteToFileA( X ) ；50ms (1)飛機(jī)訂票系統(tǒng)：位于武昌的某遠(yuǎn)程終端通過位于服務(wù)器主機(jī)中的進(jìn)程 T1 處理訂票業(yè)務(wù)；位于漢口的某遠(yuǎn)程終端通過位于服務(wù)器主機(jī)中的進(jìn)程 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 ) ；飛機(jī)訂票系統(tǒng)：71. 大量共享資源如只讀數(shù)據(jù)可以同時(shí)訪問，以提高資源的利用率；2. 部分資源（如外設(shè)、共享數(shù)據(jù)結(jié)構(gòu)），多個(gè)進(jìn)程在對(duì)其進(jìn)行訪問時(shí)（主要是進(jìn)行寫入或修改），可能出現(xiàn)無法預(yù)料的錯(cuò)誤。提高資源利用率的前提是要保證數(shù)據(jù)的完整性和安全性。進(jìn)程間的并發(fā)必須加以控制怎么控制？8進(jìn)程的互斥 Mutual Exclusion1.可以同時(shí)使用的2.不可以同時(shí)使用的由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程間的這種關(guān)系為進(jìn)程互斥。兩個(gè)概念：臨界資

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

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

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

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

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

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

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

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

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

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

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

15、同步：生產(chǎn)者消費(fèi)者 消費(fèi)者生產(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è)置一個(gè)公用信號(hào)量Mutex，初值為1（2）為同步設(shè)置兩個(gè)私用信號(hào)量Sempty，初值為n；Sfull，初值為0；43注意：P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起，那

16、么P操作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前而兩個(gè)V操作無關(guān)緊要44（1）為互斥設(shè)置一個(gè)公用信號(hào)量Mutex，初值為1（2）為同步設(shè)置兩個(gè)私用信號(hào)量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）只有 一個(gè) 盤子，盤子中只能放一個(gè)水果（2）父親削蘋果，放入盤中（3）母親剝

17、桔子，放入盤中（4）兒子從盤中拿蘋果，吃（5）女兒從盤中拿桔子，吃分析：多生產(chǎn)者、多消費(fèi)者、單緩沖區(qū) 模型(挑剔的消費(fèi)者)同步關(guān)系：父親兒子， 母親女兒，兒子（女兒） 父親（母親）46信號(hào)量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例:司機(jī)P1售票員P2while (true)啟動(dòng)車輛；正常運(yùn)行；到站停車；while (true)關(guān)門；售票；開門；1648信號(hào)量及P、V操作討論1) 信號(hào)量的物理含義：S0表示有S個(gè)資源可用S=0表示無資源可用S0則| S |表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S)：表示申請(qǐng)一個(gè)資源V(S)：表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于049進(jìn)程互斥和同步舉例50Windows NTMutex對(duì)象：互斥對(duì)象，相當(dāng)于互斥信號(hào)量，在一個(gè)時(shí)刻只能被一個(gè)線程使用。有關(guān)的API：CreateMutex創(chuàng)建一個(gè)互斥對(duì)象，返回對(duì)象句柄；OpenMutex返回一個(gè)已存在的互

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

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

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

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

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

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

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

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

27、用管程。管程的實(shí)現(xiàn)問題（續(xù)1）65管程的實(shí)現(xiàn)問題（續(xù)1）問題：多個(gè)進(jìn)程出現(xiàn)在管程中處理方法有三種：等待繼續(xù)，直到退出或等待（Hoare）等待繼續(xù)，直到等待或退出規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作66管程的實(shí)現(xiàn)問題（續(xù)1）如果進(jìn)程喚醒進(jìn)程，則等待繼續(xù)，如果進(jìn)程在執(zhí)行又喚醒進(jìn)程，則等待繼續(xù)， （Hoare）在管程內(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í)。67由于管程通常是用于管理資源的，因而在管程內(nèi)部，應(yīng)當(dāng)存在某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)使其等待。(* 資

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

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

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

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

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

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

34、r;count2 : integer;END;/* 等待調(diào)用的進(jìn)程個(gè)數(shù) */* 調(diào)用了管程中的過程且不處于等待狀態(tài)的進(jìn)程個(gè)數(shù) */80調(diào)用查看原語(yǔ)check如果管程是開放的，則執(zhí)行這條原語(yǔ)后關(guān)閉管程，相應(yīng)進(jìn)程繼續(xù)執(zhí)行；如果管程是關(guān)閉的，則執(zhí)行這條原語(yǔ)后相應(yīng)進(jìn)程被置成等待調(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開放原語(yǔ)release如果除了發(fā)出這

35、條原語(yǔ)的進(jìn)程外，不再有調(diào)用了管程中過程但又不處于等待狀態(tài)的進(jìn)程，那么就釋放一個(gè)等待者或開放管程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等待原語(yǔ)wait執(zhí)行這條原語(yǔ)后相應(yīng)進(jìn)程被置成等待狀態(tài)，同時(shí)開放管程，允許其它進(jìn)程調(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;釋放原語(yǔ)signal執(zhí)行這條原語(yǔ)后釋放指定等待進(jìn)程隊(duì)列中的一個(gè)進(jìn)程。如指定等待進(jìn)程隊(duì)列為空，本操作相當(dāng)于空操作varIM83procedure signal(var s:condition;interf);beginif s 0 thenbegins := s

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