操作系統(tǒng)課件4-3

第四章互斥、同步與通訊并發(fā)進(jìn)程(concurrentprocesses)進(jìn)程互斥(mutualexclusion)進(jìn)程同步(synchronization)進(jìn)程高級通訊(communication)系統(tǒng)舉例14.3.5管程（Monitor）PV操作：分散式同步機(jī)制：共享變量操作，PV操作，分散在整個系統(tǒng)中或各個進(jìn)程中。缺點(diǎn)：可讀性差；正確性不易保證；不易修改。優(yōu)點(diǎn)：高效，靈活。管程：集中式同步工具：共享變量及其所有相關(guān)操作集中在一個摸塊中。優(yōu)點(diǎn)：可讀性好；正確性易于保證；易于修改。缺點(diǎn)：不甚靈活，效率略低。24.3.5.1管程的提出前面各種互斥手段，雖能有效地實(shí)現(xiàn)互斥，但仍存在著一些缺點(diǎn)：1)進(jìn)程同時進(jìn)入臨界區(qū)：將P(s)和V(s)操作顛倒：

V(S)

臨界區(qū)

P(S)可能幾個進(jìn)程同時進(jìn)入臨界區(qū)，錯誤僅在幾個進(jìn)程同時活躍在臨界區(qū)內(nèi)才可能發(fā)現(xiàn)，且這種情況并非總是可再現(xiàn)的。34.3.5.1管程的提出2)產(chǎn)生死鎖：將V(s)誤寫為P(s)

P(S)

臨界區(qū)

P(S)

S被出錯的進(jìn)程連續(xù)兩次執(zhí)行P變成-1。使任何其它進(jìn)程不能進(jìn)入臨界區(qū)不會有其它進(jìn)程執(zhí)行V操作，從而發(fā)生死鎖3)同時進(jìn)入臨界區(qū)，永遠(yuǎn)不會喚醒：如遺漏P操作，使得多個進(jìn)程同時進(jìn)入臨界區(qū)遺漏V操作，使其它進(jìn)程無法進(jìn)入臨界區(qū)，永遠(yuǎn)不會喚醒。44.3.5.1管程的提出基于上述問題1971年由E.W.Dijkstra提出把所有進(jìn)程對某一臨界資源的同步操作集中，構(gòu)成一個“秘書”進(jìn)程凡要訪問臨界資源的都需先報告“秘書”，由秘書來實(shí)現(xiàn)諸進(jìn)程的同步1973年P(guān).B.Hansan和C.A.R.Hoare將“秘書”發(fā)展為管程概念，將同步操作分別集中于相應(yīng)的管程中54.3.5.1管程的提出背景:Structuredprogramming基于管程的語言ConcurrentPascal(Hansen)Modula(With)MesaMod*ConcurrentEuclidXCY64.3.5.2管程形式把一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過程一并稱為管程。Hansan定義：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操作能同步進(jìn)程并改變管程中的數(shù)據(jù)。管程由三部分組成：1）局部于管程的共享變量的說明2）對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行的一組操作3）對局部于管程的數(shù)據(jù)設(shè)置初始值的語句74.3.5.2管程形式管程是管理進(jìn)程間同步的機(jī)制，保證進(jìn)程互斥地訪問共享變量管程每次僅允許一個進(jìn)程進(jìn)入，提供方便的阻塞和喚醒進(jìn)程的機(jī)構(gòu)。管程提出時，C語言尚未流行，管程大多采用擴(kuò)展的pascal語言描述84.3.5.2管程形式Typemonitor_name=MONITOR

共享變量說明

define

本管程內(nèi)定義，本管程外使用的子程序名表；

use

本管程外定義，本管程內(nèi)使用的子程序名表；Procedure過程名（形參表）；

局部變量說明

Begin

語句序列

End;…94.3.5.2管程形式(Cont.)Function

函數(shù)名（形參表）:返回值類型；局部變量說明

Begin

語句序列

End;...Begin

共享變量初始化語句序列End;104.3.5.2管程形式(Cont.)管程三個主要的特性:模塊化：一個管程是一個模塊抽象數(shù)據(jù)類型：管程是一種特殊的數(shù)據(jù)類型,不僅有數(shù)據(jù),還有對數(shù)據(jù)進(jìn)行操作的代碼信息掩蔽：管程是半透明的,管程的內(nèi)部過程(函數(shù))實(shí)現(xiàn)了某些功能,這些功能是怎樣實(shí)現(xiàn)的在外部是不可見的114.3.5.3管程語義管程的共享變量在管程外部不可見，外部只能通過調(diào)用管程中的外部子程序訪問共享變量為保證對共享變量操作的數(shù)據(jù)完整性，規(guī)定管程互斥進(jìn)入124.3.5.3管程語義管程用來管理資源，在管程中設(shè)有進(jìn)程等待隊(duì)列和相應(yīng)的等待及喚醒操作當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行等待操作時,它應(yīng)當(dāng)釋放管程的互斥權(quán)當(dāng)一個進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(如P喚醒Q)，管程中同時有兩個處于活動狀態(tài)的進(jìn)程，有三種處理方法：P等待，Q繼續(xù)，直到Q退出或等待(Hoare)Q等待，P繼續(xù)，直到P退出或等待(Java)喚醒是管程中可執(zhí)行的最后一個操作(Hansen)134.3.5.3管程語義管程互斥進(jìn)入，當(dāng)進(jìn)程試圖進(jìn)入已被占用的管程時應(yīng)在管程入口處等待在管程的入口處有一個進(jìn)程等待隊(duì)列,稱作入口等待隊(duì)列。14Hoare管程設(shè)施Hoare管程設(shè)施：入口等待隊(duì)列：每個管程變量一個，用于排隊(duì)進(jìn)入；緊急等待隊(duì)列：每個管程變量一個，用于喚醒等待；內(nèi)部等待隊(duì)列：varc:condition;條件變量可根據(jù)需要定義多個，用于設(shè)置等待條件。15條件變量操作利用管程實(shí)現(xiàn)進(jìn)程同步，必須設(shè)置PV操作等待的原因有多個，為了區(qū)別，引入條件變量condition管程中對每個條件變量給出說明：

Varc:condition;

16內(nèi)部等待隊(duì)列wait(c)如緊急隊(duì)列非空，喚醒第一個等待者，否則釋放管程互斥權(quán);執(zhí)行此操作進(jìn)程的PCB（線程）進(jìn)入c鏈尾。相當(dāng)于P操作。

signal(c)c鏈空，相當(dāng)空操作。否則喚醒第一個執(zhí)行此操作進(jìn)程的PCB（線程）進(jìn)入緊急隊(duì)列。相當(dāng)于V操作。1718進(jìn)入與離開進(jìn)入管程：申請管程互斥權(quán)。離開管程：如緊急等待隊(duì)列非空，喚醒第一個等待者；否則開放管程。194.3.5.4管程的使用讀者/寫者問題（寫優(yōu)先）生產(chǎn)者和消費(fèi)者問題哲學(xué)家就餐問題（anotherapproach)DiskheadschedulerSingleresourcemanagementSleepybarber’sproblem20例1.讀者/寫者問題(寫者優(yōu)先)rq:讀隊(duì)列，wq：寫隊(duì)列reading_count,write_count：讀寫進(jìn)程個數(shù)Typereaers_writers=Monitor;Varrq,wq:condition;reading_count,write_count:integer;Definestart_read,finish_read,start_write,finish_write;21例1.讀者/寫者問題Procedurestart_read;BeginIfwrite_count>0Thenwait(rq);reading_count++;signal(rq);End;Procedurefinish_read;Beginreading_count--;Ifreading_count=0Thensignal(wq)End;22例1.讀者/寫者問題Procedurestart_writeBeginwrite_count++;If(write_count>1)or(reading_count>0)Thenwait(wq)End;Procedurefinish_write;Beginwrite_count--;Ifwrite_count>0Thensignal(wq)Elsesignal(rq)End;23例1.讀者/寫者問題Beginreading_count:=0;write_count:=0;End;Varrw:readers_writers;讀者：寫者：rw.start_read;rw.start_write;{reading}{writing}rw.finish_read;rw.finish_write;24例2.生產(chǎn)者和消費(fèi)者問題notFull：表示是否允許將產(chǎn)品放入緩沖區(qū)中notEmpty：表示是否允許消費(fèi)產(chǎn)品25例2.生產(chǎn)者和消費(fèi)者問題26例2.生產(chǎn)者和消費(fèi)者問題27例3.磁頭引臂調(diào)度問題某單磁頭磁盤系統(tǒng)共有200個磁道(柱面)，由外向內(nèi)依次編號為0,…,199，如圖4-10所示.當(dāng)有多個磁盤塊的I/O請求時，采用電梯算法調(diào)度，試用管程給出解法28例3.磁頭引臂調(diào)度問題01……199updown磁頭引臂扇區(qū)29調(diào)度算法FCFS（firstcomefirstserve）公平效率低SSTF（shortestseektimefirst）效率高磁道歧視SCAN（elevatoralgorithm）效率較高，較公平30Hansen管程實(shí)現(xiàn)SCAN算法外部過程：申請：require(dest:0..199)

釋放：release()使用方式：

require(dest);{IO操作}--(管程外操作)release31Hansen管程實(shí)現(xiàn)SCAN算法資源狀態(tài)用busy描述磁頭引臂當(dāng)前位置和移動方向分別用headpos和direction描述算法的關(guān)鍵是為每個磁道(柱面)設(shè)置一個等待隊(duì)列cylinder，同時記錄等待在每個隊(duì)列上進(jìn)程的個數(shù)32管程實(shí)現(xiàn)SCAN算法Typediskhead=MONITORVarbusy:boolean;headpos:0..199;direction:(up,down);cylinder:Array[0..199]Ofcondition;count:Array[0..199]Ofinteger;

Definerequire,release;33管程實(shí)現(xiàn)SCAN算法Procedurerequire(dest:0..199);BeginIfbusyThenBegincount[dest]:=count[dest]+1;wait(cylinder[dest])Endbusy:=true;Ifdest<headposThendirection:=downElseIfdest>headposThendirection:=up;headpos:=destEnd;34管程實(shí)現(xiàn)SCAN算法Procedureupscan;VarI:0..200;BeginI:=headpos;While(I<=199)and(count[I]=0)DoI:=I+1;IfI<=199ThenBegincount[I]:=count[I]-1;signal(cylinder[I])EndEnd;35管程實(shí)現(xiàn)SCAN算法Proceduredownscan;VarI:-1..199;BeginI:=headpos;While(I>=0)and(count[I]=0)DoI:=I-1;IfI>=0ThenBegincount[I]:=count[I]-1;signal(cylinder[I])EndEnd;36管程實(shí)現(xiàn)SCAN算法Procedurerelease;Beginbusy:=false;Ifdirection=upThenBeginupscan;downscanEndElseBegindownscan;upscanEndEnd;37管程實(shí)現(xiàn)SCAN算法Procedureinitialize;VarI:0..199;Beginbusy:=false;headpos:=0;direction:=up;ForI:=0To199Docount[I]:=0EndBegininitializeEnd;38例4.單一資源管理Typesingle_resource=MONITOR;Varbusy:boolean;q:condition;Definerequire,release;Procedurerequire;BeginIfbusyThenwait(q);busy:=trueEnd;39例4.單一資源管理Procedurerelease;Beginbusy:=false;signal(q);End;Beginbusy:=falseEnd;Varlp,tape:single_resource;Busyqlp:BusyqTape:申請lp:lp.require釋放lp:lp.release申請tape:tape.require;釋放tape:tape.release40例5.嗜眠理發(fā)師問題理發(fā)店如圖4-11所示店中有一位理發(fā)師和一把理發(fā)椅，理發(fā)時顧客坐在此椅子上，不理發(fā)時理發(fā)師在此椅子上睡覺．室內(nèi)有N個凳子，供顧客們等待理發(fā)時用.如果一位顧客進(jìn)入理發(fā)店后發(fā)現(xiàn)所有凳子均已被占用，則他退出理發(fā)店理發(fā)店只有一扇門，一次只能進(jìn)出一位顧客41例5.嗜眠理發(fā)師問題42例5.嗜眠理發(fā)師問題chair：理發(fā)師是否可以理發(fā)stool：是否有人等待理發(fā)

4344例5.嗜眠理發(fā)師問題454.3.5.5管程與PV操作的等價性用PV操作可以構(gòu)造管程用管程可以構(gòu)造PV操作46用管程構(gòu)造PV操作TYPEsemaphore=MONITOR(init_value)VARc:condition;count:integer;DEFINEP,V;PROCEDUREP;BEGINcount:=count-1;IFcount<0THENwait(c);END;PROCEDUREV;BEGINcount:=count+1;IFcount<=0THENsignal(c);END;BEGINcount:=init_value;END;47用管程構(gòu)造PV操作(Cont.)信號燈與PV操作管程VARs:semaphore;VARs:semaphore;s.value:=init_value;Inits(init_value);P(s);s.P;V(s);s.V;48用PV操作構(gòu)造管程管程信號燈與PV操作一個管程實(shí)例一個入口等待隊(duì)列mutex:semaphore(1)一個緊急等待隊(duì)列urgent:semaphore(0)一個緊急等待計數(shù)urgent_count:integer(0)一個條件變量c:condition;一個信號燈變量s:semaphore(0)一個計數(shù)變量count:integer(0)等待操作wait(c)count:=count+1;IFurgent_count>0THENBEGINurgent_count:=urgent_count-1;V(urgent)ELSEV(mutex);P(s);49用PV操作構(gòu)造管程管程信號燈與PV操作喚醒操作Signal(c)IFcount>0THENBEGINcount:=count-1;urgent_count:=urgent_count+1;V(s);P(urgent)END進(jìn)入管程P(mutex);離開管程IFurgent_count>0THENBEGINurgent_count:=urgent_count-1;V(urgent)ENDELSEV(mutex);504.3.5.6管程的嵌套調(diào)用問題Wait(c)P:M1M2MnMn-1...問題：1.是否允許嵌套；

2.若允許，如何處理互斥權(quán)。方法：1.禁止嵌套（Modula)2.允許嵌套，等待時釋放當(dāng)前管程互斥權(quán)；

3.允許嵌套，等待時釋放所有管程互斥權(quán)；

4.允許嵌套，調(diào)用時釋放路經(jīng)管程互斥權(quán)51Java語言中的“管程”類似管程的對象object每個object有一個互斥鎖lock，一般未用；說明為synchronized的method啟用互斥鎖；每個object內(nèi)部有一個等待隊(duì)列；wait()method:釋放lock,狀態(tài)改為blocked,進(jìn)入waitset.notify()method:在waitset中取任意線程，移到entryset,狀態(tài)改為runnable.(Signalandcontinue)notifyAll()method:Waitset所有線程移到entryset,狀態(tài)改為runnable.52EntrysetandwaitsetObjectLockownerEntrysetwaitsetwaitAcquirelocknotify,notifyAll53Entrysetandwaitset鎖的持有者執(zhí)行wait操作,狀態(tài)改為blocked,釋放所持有的鎖,進(jìn)入waitset;若entryset非空,選擇其一進(jìn)入同步方法.鎖的持有者執(zhí)行notify操作,任選waitset上的一個線程,入entryset,狀態(tài)改為runnable.鎖的持有者執(zhí)行notifyAll操作,waitset上的所有線程出waitset,入entryset,狀態(tài)改為runnable.54例子：生產(chǎn)/消費(fèi)問題--Javapublicsynchronizedvoidenter(Objectitem){while(count==BUFFER_SIZE){try{wait();//被喚醒后重新檢測等待條件

}catch(InterruptedExceptione){}}++count;buffer[in]=item;in=(in+1)%BUFFER_SIZE;notify();}55例子：生產(chǎn)/消費(fèi)問題--java

publicsynchronizedObjectremove(){while(count==0){try{wait();}catch(InterruptedExceptione){}}--count;item=buffer[out];out=(out+1)%BUFFER_SIZE;notify();return(item);}56例子：生產(chǎn)/消費(fèi)問題--java

privatestaticfinalintNAP_TIME=5;privatestaticfinalintBUFFER_SIZE=5;privateintcountin,out;privateObject[]buffer;}57讀者／寫者問題-JavasolutionMultiplenotificationnotifyAll()--喚醒waitset集合中所有線程,進(jìn)入entryset。publicclassDatabase{publicDatabase(){Readcount=0;dbReading=false;dbWriting=false;}publicsynchronizedintstartRead(){//}58讀者／寫者問題-Javasolution

publicsynchronizedintendRead(){//}publicsynchronizedstartWrite(){//}publicsynchronizedendWrite(){//}privateintreaderCount;privatebooleandbReading;privatebooleandbWriting;}59讀者／寫者問題-JavasolutionpublicsynchronizedvoidstartRead(){while(dbWriting==true){try{wait();}catch(InterruptedExceptione){}++readCount;if(readCount==1)dbReading=true;}60讀者／寫者問題-Javasolution

publicsynchronizedvoidendRead(){--readCount;if(readCount==0)dbReading=false;notifyAll();}61讀者／寫者問題-Javasolution

publicsynchronizedvoidstartWrite(){while(dbReading==true||dbWriting==true){try{wait();}catch(InterruptedExceptione){}}