1、第四章第四章 互斥、同步與通訊互斥、同步與通訊l并發(fā)進(jìn)程并發(fā)進(jìn)程(concurrent processes)l進(jìn)程互斥進(jìn)程互斥(mutual exclusion)l進(jìn)程同步進(jìn)程同步(synchronization)l進(jìn)程高級(jí)通訊進(jìn)程高級(jí)通訊(communication)l系統(tǒng)舉例系統(tǒng)舉例14.3.5 管程（管程（Monitor）lPV操作：操作： l分散式同步機(jī)制：共享分散式同步機(jī)制：共享變量操作，變量操作，PV操作，操作，分散在整個(gè)系統(tǒng)中或各分散在整個(gè)系統(tǒng)中或各個(gè)進(jìn)程中。個(gè)進(jìn)程中。l缺點(diǎn)：缺點(diǎn)：l可讀性差；可讀性差；l正確性不易保證；正確性不易保證；l不易修改。不易修改。l優(yōu)點(diǎn)：優(yōu)點(diǎn)：l高效

2、，靈活。高效，靈活。l管程：管程：l集中式同步工具：共集中式同步工具：共享變量及其所有相關(guān)享變量及其所有相關(guān)操作集中在一個(gè)摸塊操作集中在一個(gè)摸塊中。中。l優(yōu)點(diǎn)：優(yōu)點(diǎn)：l可讀性好；可讀性好；l正確性易于保證；正確性易于保證；l易于修改。易于修改。l缺點(diǎn)：缺點(diǎn)：l不甚靈活，效率略不甚靈活，效率略低。低。24.3.5.1 管程的提出管程的提出l前面各種互斥手段，雖能有效地實(shí)現(xiàn)互斥，前面各種互斥手段，雖能有效地實(shí)現(xiàn)互斥，但仍存在著一些缺點(diǎn)：但仍存在著一些缺點(diǎn)：l1) 進(jìn)程同時(shí)進(jìn)入臨界區(qū)：將進(jìn)程同時(shí)進(jìn)入臨界區(qū)：將P(s)和和V(s)操作顛操作顛倒：倒：l V(S) 臨界區(qū)臨界區(qū) P(S)l可能幾個(gè)進(jìn)程同

3、時(shí)進(jìn)入臨界區(qū)，錯(cuò)誤僅在幾個(gè)進(jìn)程可能幾個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，錯(cuò)誤僅在幾個(gè)進(jìn)程同時(shí)活躍在臨界區(qū)內(nèi)才可能發(fā)現(xiàn)，且這種情況并非同時(shí)活躍在臨界區(qū)內(nèi)才可能發(fā)現(xiàn)，且這種情況并非總是可再現(xiàn)的?？偸强稍佻F(xiàn)的。34.3.5.1 管程的提出管程的提出l2) 產(chǎn)生死鎖：將產(chǎn)生死鎖：將V(s)誤寫(xiě)為誤寫(xiě)為P(s)l P(S) 臨界區(qū)臨界區(qū) P(S)l S被出錯(cuò)的進(jìn)程連續(xù)兩次執(zhí)行被出錯(cuò)的進(jìn)程連續(xù)兩次執(zhí)行P變成變成-1。使任何其。使任何其它進(jìn)程不能進(jìn)入臨界區(qū)它進(jìn)程不能進(jìn)入臨界區(qū)l不會(huì)有其它進(jìn)程執(zhí)行不會(huì)有其它進(jìn)程執(zhí)行V操作，從而發(fā)生死鎖操作，從而發(fā)生死鎖l3) 同時(shí)進(jìn)入臨界區(qū)，永遠(yuǎn)不會(huì)喚醒：同時(shí)進(jìn)入臨界區(qū)，永遠(yuǎn)不會(huì)喚醒：l如

4、遺漏如遺漏P操作，使得多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)操作，使得多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)l遺漏遺漏V操作，使其它進(jìn)程無(wú)法進(jìn)入臨界區(qū)，永遠(yuǎn)不操作，使其它進(jìn)程無(wú)法進(jìn)入臨界區(qū)，永遠(yuǎn)不會(huì)喚醒。會(huì)喚醒。44.3.5.1 管程的提出管程的提出l基于上述問(wèn)題基于上述問(wèn)題l1971年由年由E.W.Dijkstra提出把所有進(jìn)程對(duì)提出把所有進(jìn)程對(duì)某某一臨界資源的同步操作集中一臨界資源的同步操作集中，構(gòu)成一個(gè)，構(gòu)成一個(gè)“秘秘書(shū)書(shū)”進(jìn)程進(jìn)程l凡要訪(fǎng)問(wèn)臨界資源的都需先報(bào)告凡要訪(fǎng)問(wèn)臨界資源的都需先報(bào)告“秘書(shū)秘書(shū)”，由秘書(shū)，由秘書(shū)來(lái)實(shí)現(xiàn)諸進(jìn)程的同步來(lái)實(shí)現(xiàn)諸進(jìn)程的同步l1973年年P(guān).B.Hansan和和C.A.R.Hoare將將“秘

5、書(shū)秘書(shū)”發(fā)展為發(fā)展為管程管程概念，將同步操作分別集中于相概念，將同步操作分別集中于相應(yīng)的管程中應(yīng)的管程中 54.3.5.1 管程的提出管程的提出l背景背景: Structured programmingl基于管程的語(yǔ)言基于管程的語(yǔ)言lConcurrent Pascal (Hansen)lModula (With)lMesalMod*lConcurrent EuclidlXCY64.3.5.2 管程形式管程形式l把一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過(guò)程一并稱(chēng)為管把一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過(guò)程一并稱(chēng)為管程程。lHansan定義：一個(gè)管程定義了一個(gè)定義：一個(gè)管程定義了一個(gè)數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行和能為并發(fā)

6、進(jìn)程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)在該數(shù)據(jù)結(jié)構(gòu)上上)的的一組操作一組操作，這組操作能同步進(jìn)程并改，這組操作能同步進(jìn)程并改變管程中的數(shù)據(jù)。變管程中的數(shù)據(jù)。l管程由管程由三部分組成三部分組成：l1）局部于管程的共享變量的說(shuō)明）局部于管程的共享變量的說(shuō)明l2）對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行的一組操作）對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行的一組操作l3）對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句）對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句74.3.5.2 管程形式管程形式l管程是管理進(jìn)程間同步的機(jī)制管程是管理進(jìn)程間同步的機(jī)制，保證進(jìn)程，保證進(jìn)程互斥地訪(fǎng)問(wèn)共享變量互斥地訪(fǎng)問(wèn)共享變量l管程每次僅允許一個(gè)進(jìn)程進(jìn)入，提供方便的管程每次僅允許一個(gè)進(jìn)程進(jìn)入，提供方便的阻塞

7、和喚醒進(jìn)程的機(jī)構(gòu)。阻塞和喚醒進(jìn)程的機(jī)構(gòu)。l管程提出時(shí)，管程提出時(shí)，C語(yǔ)言尚未流行，管程大多語(yǔ)言尚未流行，管程大多采用擴(kuò)展的采用擴(kuò)展的pascal語(yǔ)言描述語(yǔ)言描述84.3.5.2 管程形式管程形式Type monitor_name=MONITOR 共享變量說(shuō)明共享變量說(shuō)明 define 本管程內(nèi)定義，本管程外使用的子程序名本管程內(nèi)定義，本管程外使用的子程序名表；表； use 本管程外定義，本管程內(nèi)使用的子程序名表；本管程外定義，本管程內(nèi)使用的子程序名表；Procedure 過(guò)程名（形參表）；過(guò)程名（形參表）； 局部變量說(shuō)明局部變量說(shuō)明 Begin 語(yǔ)句序列語(yǔ)句序列 End; 94.3.5.2 管

8、程形式管程形式(Cont.)Function 函數(shù)名（形參表）函數(shù)名（形參表）:返回值類(lèi)型；返回值類(lèi)型； 局部變量說(shuō)明局部變量說(shuō)明 Begin 語(yǔ)句序列語(yǔ)句序列 End; . . . . . .Begin 共享變量初始化語(yǔ)句序列共享變量初始化語(yǔ)句序列 End;104.3.5.2 管程形式管程形式(Cont.)l管程三個(gè)主要的特性管程三個(gè)主要的特性:l模塊化模塊化：一個(gè)管程是一個(gè)模塊：一個(gè)管程是一個(gè)模塊l抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型：管程是一種特殊的數(shù)據(jù)類(lèi)型：管程是一種特殊的數(shù)據(jù)類(lèi)型, 不僅有數(shù)據(jù)不僅有數(shù)據(jù), 還有對(duì)數(shù)據(jù)進(jìn)行操作的代碼還有對(duì)數(shù)據(jù)進(jìn)行操作的代碼l信息掩蔽信息掩蔽：管程是半透明的：管程是

9、半透明的, 管程的內(nèi)部過(guò)程管程的內(nèi)部過(guò)程(函數(shù)函數(shù))實(shí)現(xiàn)了某些功能實(shí)現(xiàn)了某些功能, 這些功能是怎樣實(shí)現(xiàn)這些功能是怎樣實(shí)現(xiàn)的在外部是不可見(jiàn)的的在外部是不可見(jiàn)的114.3.5.3 管程語(yǔ)義管程語(yǔ)義l管程的共享變量在管程外部不可見(jiàn)管程的共享變量在管程外部不可見(jiàn)，外部只能外部只能通過(guò)調(diào)用管程中的外部子程序訪(fǎng)問(wèn)共享變量通過(guò)調(diào)用管程中的外部子程序訪(fǎng)問(wèn)共享變量l為保證對(duì)共享變量操作的數(shù)據(jù)完整性，規(guī)定管程為保證對(duì)共享變量操作的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入互斥進(jìn)入124.3.5.3 管程語(yǔ)義管程語(yǔ)義l管程用來(lái)管理資源，在管程中設(shè)有進(jìn)程等管程用來(lái)管理資源，在管程中設(shè)有進(jìn)程等待隊(duì)列和相應(yīng)的等待及喚醒操作待隊(duì)列和相應(yīng)

10、的等待及喚醒操作l當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行等待操作時(shí)當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行等待操作時(shí), 它應(yīng)當(dāng)釋放管程的互斥權(quán)它應(yīng)當(dāng)釋放管程的互斥權(quán)l(xiāng)當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(shí)當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(shí)(如如P喚醒喚醒Q)，管程中同時(shí)有兩個(gè)處于活動(dòng)狀，管程中同時(shí)有兩個(gè)處于活動(dòng)狀態(tài)的進(jìn)程，有三種處理方法：態(tài)的進(jìn)程，有三種處理方法：lP等待，等待，Q繼續(xù)，直到繼續(xù)，直到Q退出或等待退出或等待(Hoare)lQ等待，等待，P繼續(xù)，直到繼續(xù)，直到P退出或等待退出或等待(Java)l喚醒是管程中可執(zhí)行的最后一個(gè)操作喚醒是管程中可執(zhí)行的最后一個(gè)操作(Hansen)134.3.5.3 管程語(yǔ)義管程語(yǔ)義l管

11、程互斥進(jìn)入，當(dāng)進(jìn)程試圖進(jìn)入已被占用管程互斥進(jìn)入，當(dāng)進(jìn)程試圖進(jìn)入已被占用的管程時(shí)應(yīng)在管程入口處等待的管程時(shí)應(yīng)在管程入口處等待l在管程的入口處有一個(gè)進(jìn)程等待隊(duì)列在管程的入口處有一個(gè)進(jìn)程等待隊(duì)列, 稱(chēng)稱(chēng)作入口等待隊(duì)列。作入口等待隊(duì)列。14Hoare管程設(shè)施管程設(shè)施lHoare管程設(shè)施：管程設(shè)施： l入口等待隊(duì)列：入口等待隊(duì)列：l每個(gè)管程變量一個(gè)，用于排隊(duì)進(jìn)入；每個(gè)管程變量一個(gè)，用于排隊(duì)進(jìn)入；l緊急等待隊(duì)列：緊急等待隊(duì)列：l每個(gè)管程變量一個(gè)，用于喚醒等待；每個(gè)管程變量一個(gè)，用于喚醒等待；l內(nèi)部等待隊(duì)列：內(nèi)部等待隊(duì)列：lvar c: condition; 條件變量條件變量l可根據(jù)需要定義多個(gè)，用于設(shè)置等

12、待條件?？筛鶕?jù)需要定義多個(gè)，用于設(shè)置等待條件。15條件變量操作條件變量操作l利用管程實(shí)現(xiàn)進(jìn)程同步，必須設(shè)置利用管程實(shí)現(xiàn)進(jìn)程同步，必須設(shè)置PV操作操作l等待的原因有多個(gè)，為了區(qū)別，引入條件等待的原因有多個(gè)，為了區(qū)別，引入條件變量變量conditionl管程中對(duì)每個(gè)條件變量給出說(shuō)明：管程中對(duì)每個(gè)條件變量給出說(shuō)明： lVar c:condition;16內(nèi)部等待隊(duì)列內(nèi)部等待隊(duì)列l(wèi)wait(c)l如緊急隊(duì)列非空，喚醒第一個(gè)等待者，否則如緊急隊(duì)列非空，喚醒第一個(gè)等待者，否則釋放管程互斥權(quán)釋放管程互斥權(quán);l執(zhí)行此操作進(jìn)程的執(zhí)行此操作進(jìn)程的PCB（線(xiàn)程）進(jìn)入（線(xiàn)程）進(jìn)入c鏈尾。鏈尾。相當(dāng)于相當(dāng)于P操作。操作

13、。 lsignal(c)lc鏈空，相當(dāng)空操作。否則喚醒第一個(gè)鏈空，相當(dāng)空操作。否則喚醒第一個(gè)l執(zhí)行此操作進(jìn)程的執(zhí)行此操作進(jìn)程的PCB（線(xiàn)程）進(jìn)入緊急隊(duì)（線(xiàn)程）進(jìn)入緊急隊(duì)列。相當(dāng)于列。相當(dāng)于V操作。操作。1718進(jìn)入與離開(kāi)進(jìn)入與離開(kāi)l進(jìn)入管程：進(jìn)入管程：l申請(qǐng)管程互斥權(quán)。申請(qǐng)管程互斥權(quán)。l離開(kāi)管程：離開(kāi)管程：l如緊急等待隊(duì)列非空，喚醒第一個(gè)等待者；如緊急等待隊(duì)列非空，喚醒第一個(gè)等待者；否則開(kāi)放管程。否則開(kāi)放管程。194.3.5.4 管程的使用管程的使用l讀者讀者/寫(xiě)者問(wèn)題（寫(xiě)優(yōu)先）寫(xiě)者問(wèn)題（寫(xiě)優(yōu)先）l生產(chǎn)者和消費(fèi)者問(wèn)題生產(chǎn)者和消費(fèi)者問(wèn)題 l哲學(xué)家就餐問(wèn)題（哲學(xué)家就餐問(wèn)題（another appr

14、oach) lDisk head scheduler lSingle resource managementlSleepy barbers problem 20例例1. 讀者讀者/寫(xiě)者問(wèn)題寫(xiě)者問(wèn)題(寫(xiě)者優(yōu)先寫(xiě)者優(yōu)先)lrq:讀隊(duì)列，讀隊(duì)列，wq：寫(xiě)隊(duì)列：寫(xiě)隊(duì)列l(wèi)reading_count,write_count：讀寫(xiě)進(jìn)程：讀寫(xiě)進(jìn)程個(gè)數(shù)個(gè)數(shù)lType reaers_writers = Monitor; Var rq,wq: condition; reading_count,write_count:integer; Define start_read,finish_read, start_writ

15、e,finish_write;21例例1. 讀者讀者/寫(xiě)者問(wèn)題寫(xiě)者問(wèn)題Procedure start_read; Begin If write_count0 Then wait(rq); reading_count+; signal(rq); End;Procedure finish_read; Begin reading_count-; If reading_count=0 Then signal(wq) End;22例例1. 讀者讀者/寫(xiě)者問(wèn)題寫(xiě)者問(wèn)題Procedure start_write Begin write_count+; If (write_count1) or (readin

16、g_count0) Then wait(wq) End; Procedure finish_write; Begin write_count-; If write_count0 Then signal(wq) Else signal(rq) End;23例例1. 讀者讀者/寫(xiě)者問(wèn)題寫(xiě)者問(wèn)題Begin reading_count:=0; write_count:=0;End;Var rw: readers_writers;讀者：讀者： 寫(xiě)者：寫(xiě)者：rw.start_read; rw.start_write;reading writingrw.finish_read; rw.finish_writ

17、e;24例例2. 生產(chǎn)者和消費(fèi)者問(wèn)題生產(chǎn)者和消費(fèi)者問(wèn)題lnotFull：表示是否允許將產(chǎn)品放入緩沖區(qū)中：表示是否允許將產(chǎn)品放入緩沖區(qū)中l(wèi)notEmpty：表示是否允許消費(fèi)產(chǎn)品：表示是否允許消費(fèi)產(chǎn)品25例例2. 生產(chǎn)者和消費(fèi)者問(wèn)題生產(chǎn)者和消費(fèi)者問(wèn)題26例例2. 生產(chǎn)者和消費(fèi)者問(wèn)題生產(chǎn)者和消費(fèi)者問(wèn)題27例例3. 磁頭引臂調(diào)度問(wèn)題磁頭引臂調(diào)度問(wèn)題l某單磁頭磁盤(pán)系統(tǒng)共有某單磁頭磁盤(pán)系統(tǒng)共有200個(gè)磁道個(gè)磁道(柱面柱面)，由外向內(nèi)依次編號(hào)為由外向內(nèi)依次編號(hào)為0,199，如圖，如圖4-10所示所示. 當(dāng)有多個(gè)磁盤(pán)塊的當(dāng)有多個(gè)磁盤(pán)塊的I/O請(qǐng)求時(shí)，采用請(qǐng)求時(shí)，采用電梯算法調(diào)度，試用管程給出解法電梯算法調(diào)度，

18、試用管程給出解法 28例例3. 磁頭引臂調(diào)度問(wèn)題磁頭引臂調(diào)度問(wèn)題0 1 199updown磁頭磁頭引臂引臂扇區(qū)扇區(qū)29調(diào)度算法調(diào)度算法lFCFS（first come first serve）l公平公平l效率低效率低lSSTF（shortest seek time first）l效率高效率高l磁道歧視磁道歧視lSCAN（elevator algorithm）l效率較高，較公平效率較高，較公平30Hansen管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法外部過(guò)程：外部過(guò)程： 申請(qǐng)：申請(qǐng)：require(dest:0.199) 釋放：釋放：release()使用方式：使用方式： require(dest); I

19、O操作操作 -(管程外操作管程外操作) release31Hansen管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法l資源狀態(tài)用資源狀態(tài)用busy描述描述l磁頭引臂當(dāng)前位置和移動(dòng)方向分別用磁頭引臂當(dāng)前位置和移動(dòng)方向分別用headpos和和direction描述描述l算法的關(guān)鍵是為每個(gè)磁道算法的關(guān)鍵是為每個(gè)磁道(柱面柱面)設(shè)置一個(gè)設(shè)置一個(gè)等待隊(duì)列等待隊(duì)列cylinder，同時(shí)記錄等待在每個(gè)，同時(shí)記錄等待在每個(gè)隊(duì)列上進(jìn)程的個(gè)數(shù)隊(duì)列上進(jìn)程的個(gè)數(shù) 32管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法Type diskhead=MONITOR Var busy:boolean; headpos:0.199; direction:(u

20、p,down); cylinder:Array0.199Of condition; count:Array0.199Of integer; Define require, release;33管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法 Procedure require(dest:0.199); Begin If busy Then Begin countdest:=countdest+1; wait(cylinderdest) End busy:=true; If destheadpos Then direction:=up; headpos:=dest End; 34管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法

21、 Procedure upscan; Var I:0.200; Begin I:=headpos; While (I=199)and(countI=0) Do I:=I+1; If I=0)and(countI=0) Do I:=I-1; If I=0 Then Begin countI:=countI-1; signal(cylinderI) End End;36管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法Procedure release; Begin busy:=false; If direction=up Then Begin upscan; downscan End Else Begin dow

22、nscan; upscan End End;37管程實(shí)現(xiàn)管程實(shí)現(xiàn)SCAN算法算法Procedure initialize; Var I: 0.199; Begin busy:=false; headpos:=0; direction:=up; For I:=0 To 199 Do countI:=0 EndBegin initialize End; 38例例4. 單一資源管理單一資源管理Type single_resource=MONITOR; Var busy:boolean; q:condition; Define require,release; Procedure require; B

23、egin If busy Then wait(q); busy:=true End;39例例4. 單一資源管理單一資源管理Procedure release; Begin busy:=false; signal(q); End;Begin busy:=false End;Var lp, tape:single_resource;Busyqlp:BusyqTape:申請(qǐng)申請(qǐng)lp: lp.require釋放釋放lp: lp.release申請(qǐng)申請(qǐng)tape: tape.require;釋放釋放tape: tape.release40例例5. 嗜眠理發(fā)師問(wèn)題嗜眠理發(fā)師問(wèn)題 l理發(fā)店如圖理發(fā)店如圖4-1

24、1所示所示l店中有一位理發(fā)師和一把理發(fā)椅，理發(fā)時(shí)顧店中有一位理發(fā)師和一把理發(fā)椅，理發(fā)時(shí)顧客坐在此椅子上，不理發(fā)時(shí)理發(fā)師在此椅子客坐在此椅子上，不理發(fā)時(shí)理發(fā)師在此椅子上睡覺(jué)上睡覺(jué)l室內(nèi)有室內(nèi)有N個(gè)凳子，供顧客們等待理發(fā)時(shí)用個(gè)凳子，供顧客們等待理發(fā)時(shí)用.l如果一位顧客進(jìn)入理發(fā)店后發(fā)現(xiàn)所有凳子均如果一位顧客進(jìn)入理發(fā)店后發(fā)現(xiàn)所有凳子均已被占用，則他退出理發(fā)店已被占用，則他退出理發(fā)店l理發(fā)店只有一扇門(mén)，理發(fā)店只有一扇門(mén)， 一次只能進(jìn)出一位顧客一次只能進(jìn)出一位顧客 41例例5. 嗜眠理發(fā)師問(wèn)題嗜眠理發(fā)師問(wèn)題42例例5. 嗜眠理發(fā)師問(wèn)題嗜眠理發(fā)師問(wèn)題lchair ：理發(fā)師是否可以理發(fā)：理發(fā)師是否可以理發(fā)ls

25、tool ：是否有人等待理發(fā)：是否有人等待理發(fā)4344例例5. 嗜眠理發(fā)師問(wèn)題嗜眠理發(fā)師問(wèn)題454.3.5.5 管程與管程與PV操作的等價(jià)性操作的等價(jià)性用用PV操作可以構(gòu)造管程操作可以構(gòu)造管程用管程可以構(gòu)造用管程可以構(gòu)造PV操作操作46用管程構(gòu)造用管程構(gòu)造PV操作操作TYPE semaphore=MONITOR(init_value) VAR c:condition; count: integer;DEFINE P,V;PROCEDURE P; BEGIN count:=count-1; IF count0 THEN wait(c); END;PROCEDURE V; BEGIN count:

26、=count+1; IF count 0 THEN BEGIN urgent_count:=urgent_count-1; V(urgent) ELSE V(mutex);P(s);49用用PV操作構(gòu)造管程操作構(gòu)造管程管程管程信號(hào)燈與信號(hào)燈與PV操作操作喚醒操作喚醒操作Signal(c)IF count0 THEN BEGIN count:=count-1; urgent_count:=urgent_count+1; V(s); P(urgent) END進(jìn)入管程進(jìn)入管程P(mutex);離開(kāi)管程離開(kāi)管程IF urgent_count0 THEN BEGIN urgent_count:=urg

27、ent_count-1; V(urgent) ENDELSE V(mutex);504.3.5.6 管程的嵌套調(diào)用問(wèn)題管程的嵌套調(diào)用問(wèn)題Wait(c)P:M1M2MnMn-1.問(wèn)題：?jiǎn)栴}：1. 是否允許嵌套；是否允許嵌套； 2. 若允許，如何處理互斥權(quán)。若允許，如何處理互斥權(quán)。方法：方法：1. 禁止嵌套（禁止嵌套（Modula) 2. 允許嵌套，等待時(shí)釋放當(dāng)前管程互斥權(quán)允許嵌套，等待時(shí)釋放當(dāng)前管程互斥權(quán)； 3. 允許嵌套，等待時(shí)釋放所有管程互斥權(quán)；允許嵌套，等待時(shí)釋放所有管程互斥權(quán)； 4. 允許嵌套，調(diào)用時(shí)釋放路經(jīng)管程互斥權(quán)允許嵌套，調(diào)用時(shí)釋放路經(jīng)管程互斥權(quán)51Java語(yǔ)言中的語(yǔ)言中的“管程管

28、程”l類(lèi)似管程的對(duì)象類(lèi)似管程的對(duì)象objectl每個(gè)每個(gè)object有一個(gè)互斥鎖有一個(gè)互斥鎖lock，一般未用；，一般未用；l說(shuō)明為說(shuō)明為synchronized的的method啟用互斥鎖；啟用互斥鎖；l每個(gè)每個(gè)object內(nèi)部有一個(gè)等待隊(duì)列；內(nèi)部有一個(gè)等待隊(duì)列；lwait() method: l釋放釋放lock, 狀態(tài)改為狀態(tài)改為blocked, 進(jìn)入進(jìn)入wait set.lnotify() method:l在在wait set中取任意線(xiàn)程，移到中取任意線(xiàn)程，移到entry set,狀態(tài)改為狀態(tài)改為runnable. (Signal and continue)lnotifyAll() met

29、hod:lWait set所有線(xiàn)程移到所有線(xiàn)程移到entry set, 狀態(tài)改為狀態(tài)改為runnable.52Entry set and wait setlObjectlLock lownerlEntry setlwait setlwaitlAcquire locklnotify, notifyAll53Entry set and wait setl鎖的持有者執(zhí)行鎖的持有者執(zhí)行wait操作操作, 狀態(tài)改為狀態(tài)改為blocked,釋放所持有的鎖釋放所持有的鎖, 進(jìn)入進(jìn)入wait set; 若若entry set非空非空,選擇其一進(jìn)入同步方法選擇其一進(jìn)入同步方法.l鎖的持有者執(zhí)行鎖的持有者執(zhí)行no

30、tify操作操作, 任選任選wait set上的一個(gè)線(xiàn)程上的一個(gè)線(xiàn)程, 入入entry set, 狀態(tài)改為狀態(tài)改為runnable. l鎖的持有者執(zhí)行鎖的持有者執(zhí)行notifyAll操作操作, wait set上上的所有線(xiàn)程出的所有線(xiàn)程出wait set, 入入entry set, 狀態(tài)狀態(tài)改為改為runnable.54例子：生產(chǎn)例子：生產(chǎn)/消費(fèi)問(wèn)題消費(fèi)問(wèn)題-Javalpublic synchronized void enter(Object item) l while (count=BUFFER_SIZE) l try wait(); /被喚醒后重新檢測(cè)等待條件被喚醒后重新檢測(cè)等待條件l c

31、atch (InterruptedException e) l l +count;l bufferin=item;l in=(in+1)% BUFFER_SIZE;l notify();l 55例子：生產(chǎn)例子：生產(chǎn)/消費(fèi)問(wèn)題消費(fèi)問(wèn)題-javal public synchronized Object remove() l while (count=0) l try wait();l catch (InterruptedException e) l l -count;l item=bufferout;l out=(out+1)% BUFFER_SIZE;l notify();l return(it

32、em);l 56例子：生產(chǎn)例子：生產(chǎn)/消費(fèi)問(wèn)題消費(fèi)問(wèn)題-javal private static final int NAP_TIME=5;l private static final int BUFFER_SIZE=5;l private int count in,out;l private Object buffer;l57讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題-Java solutionlMultiple notificationlnotifyAll() - 喚醒喚醒wait set集合中所有線(xiàn)程集合中所有線(xiàn)程, 進(jìn)入進(jìn)入entry set。lpublic class Database l publi

33、c Database() l Readcount=0;l dbReading=false;l dbWriting=false;l l public synchronized int startRead() l / l 58讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題-Java solutionl public synchronized int endRead() l /l l public synchronized startWrite() l /l l public synchronized endWrite() l /l l private int readerCount;l private boolean

34、dbReading;l private boolean dbWriting;l59讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題-Java solutionlpublic synchronized void startRead() l while (dbWriting=true) l try l wait();l catch(InterruptedException e)l +readCount;l if (readCount=1)l dbReading=true;l60讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題-Java solutionl public synchronized void endRead() l -readCount;l if(readCount=0)l dbReading=false;l notifyAll();l61讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題-Java solutionl public synchronized void startWrite() l while(dbReading=true|dbWriting=true) l try l wait();l catch(InterruptedException e) l l dbWriting=true;l l public synchronized void endWrite()l dbWriting=false;l n