計(jì)算機(jī)操作系統(tǒng)第三章處理機(jī)調(diào)度與死鎖

第三章處理機(jī)調(diào)度與死鎖主要內(nèi)容3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。對于批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度(又稱高級調(diào)度或長程調(diào)度)和進(jìn)程調(diào)度(又稱低級調(diào)度或短程調(diào)度)兩個(gè)過程后方能獲得處理機(jī)；對于終端型作業(yè)，則通常只需經(jīng)過進(jìn)程調(diào)度即可獲得處理機(jī)。3.1處理機(jī)調(diào)度的基本概念

3.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)高級調(diào)度(HighLevelScheduling)又稱為作業(yè)調(diào)度或長程調(diào)度(LongTermScheduling)，其主要功能是根據(jù)某種算法，把外存上處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，也就是說，它的調(diào)度對象是作業(yè)。在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。

1)接納多少個(gè)作業(yè)

2)接納哪些作業(yè)按照先來先服務(wù)、短作業(yè)優(yōu)先、作業(yè)優(yōu)先級三種調(diào)度算法。3.1.2低級調(diào)度通常也把低級調(diào)度(LowLevelScheduling)稱為進(jìn)程調(diào)度或短程調(diào)度(ShortTermScheduling)，它所調(diào)度的對象是進(jìn)程(或內(nèi)核級線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在多道批處理、分時(shí)和實(shí)時(shí)三種類型的OS中，都必須配置這級調(diào)度。進(jìn)程調(diào)度的基本概念進(jìn)程調(diào)度的實(shí)質(zhì):就是將處理器資源合理分配給適當(dāng)?shù)?，一方面確保任務(wù)的時(shí)間約束能被滿足，另一方面盡量提高處理器資源的利用率。進(jìn)程調(diào)度就是從就緒狀態(tài)的進(jìn)程中，挑選一個(gè)進(jìn)程到處理器上運(yùn)行。操作系統(tǒng)中負(fù)責(zé)進(jìn)程調(diào)度的程序稱為進(jìn)程調(diào)度器（scheduler）或分派器(dispatch）。調(diào)度調(diào)度要解決的問題WHAT：按什么原則分配CPU—調(diào)度算法WHEN：何時(shí)分配CPU—調(diào)度的時(shí)機(jī)HOW：如何分配CPU—調(diào)度過程及進(jìn)程的上下文切換調(diào)度實(shí)例：TaskschedulingofuCOSvoidOS_Sched(void){INT8Uy;OS_ENTER_CRITICAL();if((OSIntNesting==0)&&(OSLockNesting==0))

{/*Sched.onlyifallISRsdone¬locked*/

y=OSUnMapTbl[OSRdyGrp];/*GetpointertoHPTready*/OSPrioHighRdy=(INT8U)((y<<3)+OSUnMapTbl[OSRdyTbl[y]]);if(OSPrioHighRdy!=OSPrioCur)

{/*NoCtxSwifcurrenttaskishighestrdy

*/OSTCBHighRdy=OSTCBPrioTbl[OSPrioHighRdy];OSCtxSwCtr++;/*Incrementcontextswitchcounter*/

OS_TASK_SW();/*Performacontextswitch*/}}OS_EXIT_CRITICAL();}INT8UOSTaskSuspend(INT8Uprio){BOOLEANself;OS_TCB*ptcb;

OS_ENTER_CRITICAL();if(prio==OS_PRIO_SELF){

/*SeeifsuspendSELF*/prio=OSTCBCur->OSTCBPrio;self=TRUE;}elseif(prio==OSTCBCur->OSTCBPrio){/*Seeifsuspendingself*/self=TRUE;}else{self=FALSE;

/*Nosuspendinganothertask*/}ptcb=OSTCBPrioTbl[prio];if(ptcb==(OS_TCB*)0){

/*Tasktosuspendmustexist*/OS_EXIT_CRITICAL();return(OS_TASK_SUSPEND_PRIO);}if((OSRdyTbl[ptcb->OSTCBY]&=~ptcb->OSTCBBitX)==0x00){/*Maketasknotready*/OSRdyGrp&=~ptcb->OSTCBBitY;}ptcb->OSTCBStat|=OS_STAT_SUSPEND;/*Statusoftaskis'SUSPENDED'*/OS_EXIT_CRITICAL();if(self==TRUE){

/*ContextswitchonlyifSELF*/

OS_Sched();}return(OS_NO_ERR);}1．低級調(diào)度的功能低級調(diào)度的主要功能如下：(1)按某種算法選取進(jìn)程（調(diào)度）。(2)保存處理機(jī)的現(xiàn)場信息（上下文切換第一步驟）(3)把處理器分配給進(jìn)程（上下文切換第二步驟）。2．進(jìn)程調(diào)度中的三個(gè)基本機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制：(1)排隊(duì)器為了提高進(jìn)程調(diào)度的效率，應(yīng)事先將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列。(2)分派器(調(diào)度程序)分派器把由進(jìn)程調(diào)度程序所選定的進(jìn)程，從就緒隊(duì)列中取出該進(jìn)程,將處理機(jī)分配給它。(3)上下文切換機(jī)制當(dāng)對處理機(jī)進(jìn)行切換時(shí)，會(huì)發(fā)生兩對上下文切換操作。

1)非搶占方式(Non-preemptiveMode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。3.進(jìn)程調(diào)度方式

在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個(gè)：①正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；③在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、suspend原語等。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。2)搶占方式(PreemptiveMode)這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。搶占方式的優(yōu)點(diǎn)：可以防止一個(gè)長進(jìn)程長時(shí)間占用處理機(jī)，能為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足對響應(yīng)時(shí)間有著較嚴(yán)格要求的實(shí)時(shí)任務(wù)的需求。但搶占方式比非搶占方式調(diào)度所需付出的開銷較大。搶占的原則有：優(yōu)先權(quán)原則

通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。(2)短作業(yè)(進(jìn)程)優(yōu)先原則。(3)時(shí)間片原則。

3.中級調(diào)度(Intermediate-LevelScheduling)中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。三種調(diào)度的小結(jié)進(jìn)程調(diào)度的運(yùn)行頻率最高，在分時(shí)系統(tǒng)中通常是10～100ms便進(jìn)行一次進(jìn)程調(diào)度，因此把它稱為短程調(diào)度。為避免進(jìn)程調(diào)度占用太多的CPU時(shí)間，進(jìn)程調(diào)度算法不宜太復(fù)雜。作業(yè)調(diào)度往往是發(fā)生在一個(gè)(批)作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)(批)作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次，因此把它稱為長程調(diào)度。由于其運(yùn)行頻率較低，故允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。中級調(diào)度的運(yùn)行頻率基本上介于上述兩種調(diào)度之間，因此把它稱為中程調(diào)度。3.1.2調(diào)度隊(duì)列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型每個(gè)進(jìn)程在執(zhí)行時(shí)都可能出現(xiàn)以下三種情況：(1)任務(wù)在給定的時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；(2)任務(wù)在本次分得的時(shí)間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊(duì)列的末尾；(3)在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞螅籓S放入阻塞隊(duì)列。2.具有高級和低級調(diào)度的調(diào)度隊(duì)列模型圖3-2具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型作業(yè)調(diào)度按一定的作業(yè)調(diào)度算法，從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度按照一定的進(jìn)程調(diào)度算法選擇一個(gè)進(jìn)程，把處理機(jī)分配給該進(jìn)程。當(dāng)在OS中引入中級調(diào)度后，人們可把進(jìn)程的就緒狀態(tài)分為內(nèi)存就緒(表示進(jìn)程在內(nèi)存中就緒)和外存就緒(進(jìn)程在外存中就緒)。把阻塞狀態(tài)進(jìn)一步分成內(nèi)存阻塞和外存阻塞兩種狀態(tài)。在調(diào)出操作的作用下，可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，由內(nèi)存阻塞轉(zhuǎn)為外存阻塞；在中級調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。3.同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型

3.同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型圖3-3具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型3.1.3處理機(jī)調(diào)度算法的目標(biāo)1。調(diào)度算法的共同目標(biāo)：1、提高資源利用率

CPU利用率=CPU有效工作時(shí)間/(CPU有效工作時(shí)間+CPU空閑等待時(shí)間)2、公平性3、系統(tǒng)資源使用的平衡性4、策略強(qiáng)制執(zhí)行調(diào)度的原則：滿足用戶的需要和系統(tǒng)的需要。2。批處理系統(tǒng)的目標(biāo)（1）周轉(zhuǎn)時(shí)間短。

所謂周轉(zhuǎn)時(shí)間，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔（稱為作業(yè)周轉(zhuǎn)時(shí)間）。周轉(zhuǎn)時(shí)間包括四部分時(shí)間：①作業(yè)在外存后備隊(duì)列上等待調(diào)度的時(shí)間②進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間③進(jìn)程在CPU上執(zhí)行的時(shí)間④進(jìn)程等待I／O操作完成的時(shí)間。

平均周轉(zhuǎn)時(shí)間描述為：

作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間Ts之比，即W=T/Ts，稱為帶權(quán)周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:2。批處理系統(tǒng)的目標(biāo)（2）系統(tǒng)吞吐量高單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。盡量多選擇短作業(yè)運(yùn)行。（3）處理機(jī)利用率高選擇合適的調(diào)度方法和調(diào)度算法提高CPU利用率。選擇大作業(yè)運(yùn)行。3、分時(shí)系統(tǒng)的目標(biāo)（1）響應(yīng)時(shí)間快（2）均衡性系統(tǒng)響應(yīng)時(shí)間的快慢與用戶所請求的服務(wù)的復(fù)雜性相適應(yīng)。響應(yīng)時(shí)間快分時(shí)系統(tǒng)中，所謂響應(yīng)時(shí)間，是從用戶通過鍵盤（或者鼠標(biāo)）提交一個(gè)請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。響應(yīng)時(shí)間包括三部分時(shí)間：①從鍵盤輸入的請求信息傳送到處理機(jī)的時(shí)間。②處理機(jī)對請求信息進(jìn)行處理的時(shí)間。③將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。4、實(shí)時(shí)系統(tǒng)的目標(biāo)（1）截至?xí)r間的保證所謂截止時(shí)間，是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。（也叫做時(shí)限，即deadline）（2）可預(yù)測性保證任務(wù)執(zhí)行的連續(xù)性，執(zhí)行流程能夠事先確定。3.1.4引起進(jìn)程調(diào)度的因素：引起進(jìn)程調(diào)度的因素可歸結(jié)為：

正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行（包括：當(dāng)前執(zhí)行進(jìn)程被中斷、時(shí)間片用完了、掛起自己、退出等）；執(zhí)行中的進(jìn)程因提出I／O請求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P、V操作原語，Block原語，Wakeup原語等。就緒隊(duì)列中新進(jìn)入了進(jìn)程。（如創(chuàng)建了新的進(jìn)程，或者某個(gè)進(jìn)程被喚醒、某個(gè)進(jìn)程被激活）3.2進(jìn)程調(diào)度算法調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。3.5.3進(jìn)程調(diào)度算法1.先來先服務(wù)2.短進(jìn)程優(yōu)先3.時(shí)間片輪轉(zhuǎn)4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法實(shí)時(shí)調(diào)度算法最早截至?xí)r間優(yōu)先EDF算法1.先來先服務(wù)調(diào)度算法(FCFS)算法缺陷：對待短作業(yè)（進(jìn)程）不公平，如果他們排在隊(duì)列后面，則其等待時(shí)間遠(yuǎn)大于其執(zhí)行時(shí)間。短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。2．短進(jìn)程/作業(yè)優(yōu)先調(diào)度算法2．短進(jìn)程/作業(yè)優(yōu)先調(diào)度算法短進(jìn)程/作業(yè)優(yōu)先調(diào)度算法的缺點(diǎn)：(1)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16，其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。

短進(jìn)程/作業(yè)優(yōu)先調(diào)度算法的缺點(diǎn)：(2)不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。

(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶不一定對執(zhí)行時(shí)間估計(jì)那么準(zhǔn)確，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。3.時(shí)間片輪轉(zhuǎn)調(diào)度法在時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程。并令其執(zhí)行一個(gè)時(shí)間片。時(shí)間片處理過程：當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求，操作系統(tǒng)便根據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。3.時(shí)間片輪轉(zhuǎn)調(diào)度法以此保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間，換言之，系統(tǒng)能在給定的時(shí)間內(nèi)，響應(yīng)所有用戶的請求。內(nèi)核在滿足下列條件時(shí)，將把CPU交給下一個(gè)就緒態(tài)的進(jìn)程：當(dāng)前進(jìn)程因?yàn)槟撤N原因暫停執(zhí)行，如被阻塞；當(dāng)前進(jìn)程在時(shí)間片還沒有結(jié)束時(shí)已經(jīng)完成了；時(shí)間片結(jié)束。舉例:有四個(gè)進(jìn)程按時(shí)間片進(jìn)行輪轉(zhuǎn)調(diào)度(按1個(gè)時(shí)間片和4個(gè)時(shí)間片進(jìn)行調(diào)度).時(shí)間片輪轉(zhuǎn)調(diào)度法優(yōu)缺點(diǎn)1.時(shí)間片的大小對計(jì)算機(jī)性能的影響。時(shí)間片太大、太小都不好。2.存在的問題：未有效利用系統(tǒng)資源。對于短的、計(jì)算型進(jìn)程比較有利，因?yàn)樵撨M(jìn)程充分利用時(shí)間片，而I/O型進(jìn)程卻不利，因?yàn)樵趦纱蜪/O之間僅需很少的CPU時(shí)間，卻需要等待一個(gè)時(shí)間片。3.常用于分時(shí)系統(tǒng)及事務(wù)處理系統(tǒng)。4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先級最高的進(jìn)程。該算法分兩種類型：非搶占式優(yōu)先權(quán)算法和搶占式優(yōu)先權(quán)調(diào)度算法

（1）非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。（2）搶占式優(yōu)先權(quán)調(diào)度算法在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。（2）搶占式優(yōu)先權(quán)調(diào)度算法在采用這種調(diào)度算法時(shí)，是每當(dāng)系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程i時(shí)，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；如果是Pi＞Pj,則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。（2）搶占式優(yōu)先權(quán)調(diào)度算法

特點(diǎn)：能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對性能要求較高的批處理和分時(shí)系統(tǒng)中。缺點(diǎn)：系統(tǒng)開銷較大。優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)

靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。動(dòng)態(tài)優(yōu)先權(quán)

動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。

確定進(jìn)程優(yōu)先權(quán)的依據(jù)有三個(gè)方面

（1）進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。（2）進(jìn)程對資源的需求。對要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)。（3）用戶要求。按照各進(jìn)程的執(zhí)行流程和進(jìn)程的緊迫程度來指定進(jìn)程的優(yōu)先權(quán)。問題在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運(yùn)行得不到保證。有沒有什么辦法既考慮到短作業(yè)，又能夠估計(jì)長作業(yè)呢？如果我們能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時(shí)間的增加而以速率a提高，則長作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。高響應(yīng)比優(yōu)先調(diào)度算法(1)如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。

(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。

(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)。響應(yīng)比高者優(yōu)先該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會(huì)使長作業(yè)長期得不到服務(wù)。利用該算法時(shí)，每次調(diào)度之前，都須先做響應(yīng)比的計(jì)算，會(huì)增加系統(tǒng)開銷。由于在實(shí)時(shí)系統(tǒng)中都存在著若干個(gè)實(shí)時(shí)進(jìn)程或任務(wù)，實(shí)時(shí)進(jìn)程通常帶有某種程度的緊迫性；

需要引入一種新的調(diào)度解決實(shí)時(shí)進(jìn)程的調(diào)度，即實(shí)時(shí)調(diào)度。3.4實(shí)時(shí)調(diào)度1.實(shí)時(shí)系統(tǒng)與實(shí)時(shí)任務(wù)實(shí)時(shí)系統(tǒng)：計(jì)算機(jī)及時(shí)響應(yīng)外部事件的請求，在規(guī)定的時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致的運(yùn)行。2.實(shí)時(shí)調(diào)度的目標(biāo)及必要信息提供必要的信息（1）就緒時(shí)間。（2）開始截止時(shí)間和完成截止時(shí)間。（3）處理時(shí)間。（4）資源要求。（5）優(yōu)先級。3.系統(tǒng)處理能力強(qiáng)在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù)，它們的周期時(shí)間都是50ms，而每次的處理時(shí)間為10ms，則不難算出，此時(shí)是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。4．采用搶占式調(diào)度機(jī)制在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許暫停當(dāng)前任務(wù)，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對截止時(shí)間的要求。5.具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力：

(1)對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。

(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高任務(wù)切換的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時(shí)間開銷。6.最早截止時(shí)間優(yōu)先算法(EDF)最早截止時(shí)間優(yōu)先算法(EDF)該算法是根據(jù)任務(wù)的開始截止時(shí)間（或者結(jié)束截至?xí)r間）來確定任務(wù)的優(yōu)先級。截止時(shí)間愈早，其優(yōu)先級愈高。要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。任務(wù)調(diào)度EDF調(diào)度3.4進(jìn)程的切換當(dāng)一個(gè)進(jìn)程執(zhí)行完（或不能繼續(xù)執(zhí)行），則換另一個(gè)進(jìn)程占處理機(jī)執(zhí)行，稱為進(jìn)程切換。在進(jìn)程切換時(shí)，要保護(hù)執(zhí)行現(xiàn)場。執(zhí)行現(xiàn)場稱為進(jìn)程的上下文。包括CPU主要寄存器，如SP，PC，通用寄存器。進(jìn)程切換過程進(jìn)程1進(jìn)程2內(nèi)核調(diào)度程序保存進(jìn)程1的上下文到PCB1從PCB2恢復(fù)進(jìn)程2的上下文……保存進(jìn)程2的上下文到PCB2從PCB1恢復(fù)進(jìn)程1的上下文……時(shí)間進(jìn)程切換基本步驟1保存進(jìn)程上下文環(huán)境2更新當(dāng)前運(yùn)行進(jìn)程的控制塊內(nèi)容，將其狀態(tài)改為就緒或阻塞狀態(tài)3將進(jìn)程控制塊移到相應(yīng)隊(duì)列（就緒隊(duì)列或阻塞隊(duì)列）4改變需投入運(yùn)行進(jìn)程的控制塊內(nèi)容，將其狀態(tài)變?yōu)檫\(yùn)行狀態(tài)5恢復(fù)需投入運(yùn)行進(jìn)程的上下文環(huán)境Linux的進(jìn)程切換過程Linux進(jìn)程切換（context_switch()）本質(zhì)上兩步：1)

進(jìn)程頁表PGD切換；2)

內(nèi)核態(tài)堆棧和硬件上下文切換（包括CPU寄存器）；

context_switch()通過調(diào)用switch_mm()切換進(jìn)程空間，調(diào)用switch_to切換內(nèi)核上下文環(huán)境。作業(yè)1：分析Linux3.0源代碼中的switch_to函數(shù)。搞清楚進(jìn)程上下文切換的過程。3.5死鎖概述所謂死鎖（Deadlock），是指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局（Deadly-Embrace），當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。若系統(tǒng)出現(xiàn)死鎖，必須有相應(yīng)的措施進(jìn)行解除。當(dāng)然，如果能提前預(yù)防和避免死鎖的出現(xiàn)，將能提高系統(tǒng)的運(yùn)行效率。3.5.1、產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)：（1）競爭資源。（2）進(jìn)程間推進(jìn)順序非法。1．競爭資源引起進(jìn)程死鎖1）可剝奪和非剝奪性資源可搶占性資源:

是指某進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪。如CPU，對于這類資源是不會(huì)引起死鎖的。不可搶占性資源:

當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放。如打印機(jī)等，對于這類資源會(huì)引起死鎖。2）競爭不可搶占性資源在系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要，會(huì)使進(jìn)程在運(yùn)行過程中，因爭奪這些資源而陷入僵局。例如，系統(tǒng)中只有一臺打印機(jī)R1和一臺磁帶機(jī)R2，可供進(jìn)程P1和P2共享。處理不好，在P1與P2之間會(huì)形成僵局，引起死鎖。圖I/O設(shè)備共享時(shí)的死鎖情況此箭頭表示P1已經(jīng)獲得R1資源此箭頭表示P1申請R2資源3）競爭臨時(shí)性（可消耗性）資源臨時(shí)性資源，可以創(chuàng)造（生產(chǎn)）和撤消（消耗）的資源，也稱之為消耗性資源，它也可能引起死鎖。如信號量、消息、buffer中的數(shù)據(jù)等資源。例如：S1、S2和S3是臨時(shí)性資源，是由進(jìn)程P1、P2和P3產(chǎn)生的消息。如果消息通信處理順序不當(dāng)也會(huì)發(fā)生死鎖。圖3-13進(jìn)程之間通信時(shí)的死鎖產(chǎn)生接收2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1）進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序合法不會(huì)引起進(jìn)程死鎖的。2）進(jìn)程推進(jìn)順序非法

若并發(fā)進(jìn)程P1和P2推進(jìn)順序不合法，進(jìn)入不安全狀態(tài)，于是發(fā)生了進(jìn)程死鎖。2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1)進(jìn)程推進(jìn)順序合法

不安全區(qū)域D除了曲線4外，都是安全的

D2)進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。

此時(shí)P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因?yàn)椋@時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運(yùn)行到P1:Request(R2)時(shí)，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2:Request(R1)時(shí)，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。3.5.2產(chǎn)生死鎖的必要條件★死鎖的發(fā)生必須具備下列四個(gè)必要條件：（1）互斥條件：指進(jìn)程對所分配到的資源進(jìn)行排它性使用。（2）請求和保持條件：指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請求。（3）不可搶占條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。（4）環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈。3.5.3解決死鎖的方法（1）預(yù)防死鎖：是通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來預(yù)防發(fā)生死鎖。（2）避免死鎖：是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。（3）檢測死鎖：通過系統(tǒng)所設(shè)置的檢測機(jī)構(gòu)，及時(shí)地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源；（4）解除死鎖：當(dāng)檢測到系統(tǒng)中已發(fā)生死鎖時(shí)，須將進(jìn)程從死鎖狀態(tài)中解脫出來。常用的實(shí)施方法是撤消或掛起一些進(jìn)程。3.6預(yù)防死鎖的方法預(yù)防死鎖的方法是使四個(gè)必要條件中的第2、3、4條件之一不能成立，來避免發(fā)生死鎖。至于必要條件1，因?yàn)樗怯稍O(shè)備的固有屬性所決定的，不僅不能改變，還應(yīng)加以保證。系統(tǒng)規(guī)定所有進(jìn)程在開始運(yùn)行之前，都必須一次性地申請其在整個(gè)運(yùn)行過程所需的全部資源。從而進(jìn)程在整個(gè)運(yùn)行期間，便不會(huì)再提出資源要求，從而摒棄了請求和保持條件，由此可以避免發(fā)生死鎖。優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)且很安全。缺點(diǎn)：資源被嚴(yán)重浪費(fèi)，使進(jìn)程延遲運(yùn)行。

1）．摒棄“請求和保持”條件2）．破壞“不可搶占”條件當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程，再提出新的資源請求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持了的所有資源。待以后需要時(shí)再重新申請。從而破壞了“不剝奪”條件。缺點(diǎn)：這種預(yù)防死鎖的方法，實(shí)現(xiàn)起來比較復(fù)雜且要付出很大代價(jià)。因?yàn)橐粋€(gè)資源在使用一段時(shí)間后，它的被迫釋放可能會(huì)造成前段工作的失效。還會(huì)使進(jìn)程前后兩次運(yùn)行的信息不連續(xù)。3）．破壞“環(huán)路等待”條件這種方法中規(guī)定，系統(tǒng)將所有資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號。所有進(jìn)程對資源的請求必須嚴(yán)格按照資源序號遞增的次序提出。當(dāng)進(jìn)程以及獲取資源Ri，當(dāng)且僅當(dāng)F（Rj）>F(Ri)時(shí)，才允許其申請資源Rj。這樣，在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件。存在嚴(yán)重問題第一，為系統(tǒng)中各類資源分配的序號必須相對穩(wěn)定，這就限制了新設(shè)備類型的增加；第二，會(huì)經(jīng)常發(fā)生作業(yè)使用的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源浪費(fèi)；第三，增加了程序設(shè)計(jì)難度。

3）．摒棄“環(huán)路等待”條件3.7避免死鎖避免死鎖與預(yù)防死鎖的方法不同，不是實(shí)現(xiàn)采取某種限制措施，破壞產(chǎn)生死鎖的必要條件，而是在資源動(dòng)態(tài)分配過程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)，以避免發(fā)生死鎖。3.7.1系統(tǒng)安全狀態(tài)1．安全狀態(tài)所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序，如<P1，P2，…，Pn>，依次為n個(gè)進(jìn)程分配其所需資源，直至其最大需求，使每個(gè)進(jìn)程都可順利地完成，稱系統(tǒng)處于安全狀態(tài)。稱〈P1，P2，…，Pn〉序列為安全序列。否則，如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

舉例系統(tǒng)有三個(gè)進(jìn)程P1、P2和P3，共有12臺打印機(jī)。進(jìn)程P1總共要求10臺打印機(jī)，P2和P3分別要求4臺和9臺。假設(shè)T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺，尚有3臺空閑未分，如表2-7所示：進(jìn)程最大需求已分配還需要可用P11055

3P2422P3927T0時(shí)刻系統(tǒng)是安全的,存在一個(gè)安全序列<P2,P1,P3>只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換

如果不按照安全順序分配資源，則系統(tǒng)將由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻，P3又請求1臺打印機(jī)，若系統(tǒng)此時(shí)把剩余3臺中的1臺分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)。因?yàn)?，此時(shí)將找不到一個(gè)安全序列。

所以T0時(shí)刻，不能滿足P3的請求。3.6.3利用銀行家算法避免死鎖避免死鎖的關(guān)鍵在于如何準(zhǔn)確的預(yù)測是否會(huì)出現(xiàn)死鎖，從而避免死鎖。最有代表性的避免死鎖的算法是Dijkstra的銀行家算法。銀行家算法

問題描述：該算法可用于銀行發(fā)放一筆貸款前，預(yù)測該筆貸款是否會(huì)引起銀行資金周轉(zhuǎn)問題。這里，銀行的資金就類似于計(jì)算機(jī)系統(tǒng)的資源，貸款業(yè)務(wù)類似于計(jì)算機(jī)的資源分配。銀行家算法能預(yù)測一筆貸款業(yè)務(wù)對銀行是否是安全的，該算法也能預(yù)測一次資源分配對計(jì)算機(jī)系統(tǒng)是否是安全的。為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。銀行家算法的資源分配思想為實(shí)現(xiàn)銀行家算法，每個(gè)進(jìn)程在進(jìn)入系統(tǒng)時(shí)，它必須申明在運(yùn)行過程中，可能需要每種資源類型的最大單元數(shù)目，其數(shù)目不應(yīng)該超過系統(tǒng)所擁有的資源總量。當(dāng)進(jìn)程請求一組資源時(shí)，系統(tǒng)必須先確定是否有足夠的資源分配給該進(jìn)程。若有，再進(jìn)一步就算在將這些資源分配給進(jìn)程后，是否會(huì)使系統(tǒng)進(jìn)入不安全狀態(tài)。如果不會(huì)，才將資源分配給它，否則讓進(jìn)程等待。2.銀行家算法

(一).銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

（1）可利用資源向量Available：這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Available[j]=k,表示系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。（2）最大需求矩陣Max：這是一個(gè)n×m的矩陣，它定義了n個(gè)進(jìn)程中每一個(gè)進(jìn)程對m類資源的最大需求。Max[i,j]=K，表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。

（3）分配矩陣Allocation。這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。Allocation［i,j]=K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。Need[i,j]=K，表示進(jìn)程Pi還需要Rj類資源K個(gè)，方能完成其任務(wù)。

Need[i,j]＝Max[i,j]一Allocation[i,j](二)．銀行家算法設(shè)Requesti，是進(jìn)程Pi的請求向量，當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：（1）如果Requesti[j]≤Need[i,j],便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所聲明的最大值。（2）如果Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟（3）；否則，表示尚無足夠資源，Pi須阻塞等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]：＝Available[j]-Requesti[j]；

Allocation[i,j]:＝Allocation[i,j]＋Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j]；（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。

若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；

否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。

開始Requesti[j]≤Need[i,j],出錯(cuò)NRequesti[j]≤Available[j]Pi進(jìn)程等待Available[j]：＝Available[j]一Requesti[j]；Allocation[i,j]：＝Allocation[i,j]＋Requesti[j];Need[i,j]:=Need[i,j]一Requesti[j]；系統(tǒng)安全性檢查N安全不分配資源分配資源NY(三)．安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：（1）設(shè)置兩個(gè)向量：

①工作向量Work:

它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，初始值Work:＝Available.

②設(shè)置數(shù)組Finish[n]：

它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。初始值Finish[i]:=false； 當(dāng)Finish[i]:=true時(shí)，進(jìn)程pi可獲得其所需的全部資源，從而順利執(zhí)行完成。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：

①Finish[i]=false；②Need[i,j]≤work；若找到，執(zhí)行步驟（3),否則，執(zhí)行步驟（4）。（3）當(dāng)進(jìn)程pi獲得資源后，順利執(zhí)行直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work：=Work+Allocation[i,j]；

Finish[i]：=true;gotostep2；（4）如果所有進(jìn)程的Finish[i]＝true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。Work:=AvailableFinish[I]:=false從進(jìn)程集合中找能滿足下述條件的進(jìn)程：

①Finish[i]=false,②Need[i,j]≤work；Work[j]:=Work+Allocation[i,j];Finish[i]：=true;所有進(jìn)程都滿足:Finish[i]＝true系統(tǒng)不安全系統(tǒng)安全安全檢查開始安全檢查結(jié)束NyNY舉例

T0時(shí)刻的資源分配情況假定系統(tǒng)中有四個(gè)進(jìn)程P1,P2,P3,P4和三種類型的資源R1,R2,R3，每一種資源的數(shù)量分別為9、3、6，T0時(shí)刻的資源分配情況如下圖所示：進(jìn)程資源MaxAllocation

NeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613612001P3314211103P4422002420T0時(shí)刻的安全性利用安全性算法，分析T0時(shí)刻的資源分配情況，可得如下圖所示的信息。從T0時(shí)刻的安全性分析可知，T0時(shí)刻存在著一個(gè)安全序列<P2,P1，P4,P3>,故T0時(shí)刻系統(tǒng)是安全的。

進(jìn)程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623trueP1623222100723trueP4723420002725TrueP3725103211936True思考：你覺得還有那些安全序列？假設(shè)T0時(shí)刻，進(jìn)程P1申請資源，其請求向量為Request1(0,0,1),系統(tǒng)按銀行家算法進(jìn)行檢查：Request1(0,0,1)≤Need1(2,2,2)，且Request1(0,0,1)≤Available(0,1,1)故，系統(tǒng)試探性地為P1分配資源，并修改Available,Allocation1和Need1向量如表2.6所示。

利用安全性算法檢查此時(shí)系統(tǒng)是否安全:此時(shí)，系統(tǒng)的可用資源向量為Available（0,1,0），比較各進(jìn)程的需求向量Need，系統(tǒng)不能滿足任何進(jìn)程的資源請求，系統(tǒng)進(jìn)入不安全狀態(tài)。所以，P1請求的資源不能分配，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程P1阻塞等待。

進(jìn)程AllocationNeedAvailableR1R2R3R1R2R3R1R2R3

P1101221010

P2612001

P3211103

P4002420

假設(shè)T0時(shí)刻，進(jìn)程P4申請資源，其請求向量為Request4(1,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查：Request4(1,2,0)≤Need4(4,2,0)，且Request4(1,2,0)>Available(0,1,1)P4的請求向量超過系統(tǒng)的可用資源向量，故P4的請求不能滿足。進(jìn)程P4阻塞等待請考慮，如果T0時(shí)刻，進(jìn)程P4申請資源，其請求向量為Request4(0,1,0),系統(tǒng)是否能將資源分配給它？小結(jié)：避免死鎖不象預(yù)防死鎖那樣需要?jiǎng)儕Z進(jìn)程已獲得的資源，或重新執(zhí)行進(jìn)程。而且，避免死鎖比預(yù)防死鎖施加的限制條件要弱得多。避免死鎖的限制條件：a)

預(yù)先必須申明每個(gè)進(jìn)程需要的資源總量；b)

進(jìn)程之間相互獨(dú)立，其執(zhí)行順序取決于系統(tǒng)安全，而非進(jìn)程間的同步要求；c)

系統(tǒng)必須提供固定數(shù)量的資源供進(jìn)程使用；d)若進(jìn)程占有系統(tǒng)資源，則不能讓其退出系統(tǒng)。3.7死鎖的檢測與解除

如果系統(tǒng)不愿意附加太多約束條件預(yù)防死鎖，也不希望系統(tǒng)額外開銷預(yù)測并避免死鎖，那么，只能允許死鎖出現(xiàn)，然后，再解除它。因此，系統(tǒng)需要利用某種方法來檢測死鎖，下面給出了