第三章 處理機調(diào)度和死鎖

第三章處理機調(diào)度和死鎖第一頁，共六十八頁，編輯于2023年，星期四處理機調(diào)度進(jìn)程數(shù)目>處理機數(shù)目動態(tài)分配由處理機調(diào)度程序完成作業(yè)提交處理機調(diào)度獲得處理機,執(zhí)行第二頁，共六十八頁，編輯于2023年，星期四3.1處理機調(diào)度的層次

3.1.1高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度）

--把外存上處于后備隊列中的作業(yè)調(diào)入內(nèi)存。1．作業(yè)和作業(yè)步

(1)作業(yè)(Job)。程序和數(shù)據(jù)+作業(yè)說明書。

在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。

(2)作業(yè)步(JobStep)。順序加工步驟。相對獨立，相互關(guān)聯(lián)。例如：“編譯”作業(yè)步，“連結(jié)裝配”

“運行”作業(yè)步(3)作業(yè)流。輸入的作業(yè)流；處理作業(yè)流。

第三頁，共六十八頁，編輯于2023年，星期四2．作業(yè)控制塊JCB(JobControlBlock)每個作業(yè)設(shè)置一個作業(yè)控制塊，是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。作業(yè)創(chuàng)建JCB后備隊列作業(yè)調(diào)度進(jìn)入內(nèi)存結(jié)束回收資源撤銷JCB就緒隊列3.1.1高級調(diào)度第四頁，共六十八頁，編輯于2023年，星期四3．作業(yè)調(diào)度

作業(yè)調(diào)度的主要功能是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源。然后再將新創(chuàng)建的進(jìn)程插入就緒隊列，準(zhǔn)備執(zhí)行。調(diào)度特性1.接納作業(yè)數(shù)（內(nèi)存駐留數(shù)）太多―――> 周轉(zhuǎn)時間T長太少―――> 系統(tǒng)效率低2.接納策略：即采用何種調(diào)度算法：FCFS、短作業(yè)優(yōu)先等3.1.1高級調(diào)度第五頁，共六十八頁，編輯于2023年，星期四3.1.2低級調(diào)度（進(jìn)程調(diào)度或短程調(diào)度）1．低級調(diào)度的功能低級調(diào)度用于決定就緒隊列中的哪個進(jìn)程(或內(nèi)核級線程，為敘述方便，以后只寫進(jìn)程)應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進(jìn)程的具體操作。(1)保存處理機的現(xiàn)場信息。(2)按某種算法選取進(jìn)程。(3)把處理器分配給進(jìn)程。2．進(jìn)程調(diào)度中的三個基本機制為了實現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個基本機制：(1)排隊器。(2)分派器(分派程序)。(3)上下文切換機制。第六頁，共六十八頁，編輯于2023年，星期四3．進(jìn)程調(diào)度方式

1)非搶占方式(NonpreemptiveMode)不允許搶占正在運行進(jìn)程的處理機。實現(xiàn)簡單，系統(tǒng)開銷小難以滿足緊急任務(wù)的要求，不適合實時系統(tǒng)

2)搶占方式(PreemptiveMode)允許根據(jù)某種原則去暫停某個正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機重新分配給另一進(jìn)程。優(yōu)先權(quán)原則。短作業(yè)(進(jìn)程)優(yōu)先原則。時間片原則。3.1.2低級調(diào)度第七頁，共六十八頁，編輯于2023年，星期四3.1.3中級調(diào)度（中程調(diào)度）使那些暫時不能運行的進(jìn)程不再占用寶貴的內(nèi)存資源，將它們調(diào)至外存上去等待，把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運行條件且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的那些又具備運行條件的就緒進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進(jìn)程調(diào)度。中級調(diào)度實際上就是存儲器管理中的對換功能第八頁，共六十八頁，編輯于2023年，星期四3.2.1調(diào)度隊列模型一、僅有進(jìn)程調(diào)度的調(diào)度隊列模型就緒隊列CPU阻塞隊列交互用戶時間片完進(jìn)程調(diào)度等待事件事件出現(xiàn)進(jìn)程完成3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則

第九頁，共六十八頁，編輯于2023年，星期四二、具有高/低級調(diào)度的調(diào)度隊列模型就緒隊列CPU阻塞隊列時間片完進(jìn)程調(diào)度進(jìn)程完成等待事件1事件1出現(xiàn)阻塞隊列等待事件2事件2出現(xiàn)作業(yè)調(diào)度后備隊列N3.2.1調(diào)度隊列模型第十頁，共六十八頁，編輯于2023年，星期四三、具有三級調(diào)度的調(diào)度隊列模型就緒隊列CPU就緒、掛起隊列時間片完進(jìn)程調(diào)度進(jìn)程完成后備隊列阻塞、掛起隊列事件出現(xiàn)作業(yè)調(diào)度阻塞隊列等待事件掛起事件出現(xiàn)中級調(diào)度交互型作業(yè)3.2.1調(diào)度隊列模型第十一頁，共六十八頁，編輯于2023年，星期四3.2.2選擇調(diào)度方式和算法的若干準(zhǔn)則

一、面向用戶的準(zhǔn)則1．周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）概念：作業(yè)從提交――>完成的時間.分為：（1）駐外等待調(diào)度時間（2）駐內(nèi)等待調(diào)度時間（3）執(zhí)行時間（4）阻塞時間第十二頁，共六十八頁，編輯于2023年，星期四一、面向用戶的準(zhǔn)則平均周轉(zhuǎn)時間

平均帶權(quán)周轉(zhuǎn)時間

可見帶權(quán)W越小越好,Ts為實際服務(wù)時間。3.2.2選擇調(diào)度方式和算法的若干準(zhǔn)則

第十三頁，共六十八頁，編輯于2023年，星期四一、面向用戶的準(zhǔn)則2．響應(yīng)時間快：（對交互性作業(yè)）概念：鍵盤提交請求到首次響應(yīng)的時間（1）輸入傳送時間（2）處理時間（3）響應(yīng)傳送時間3．截止時間的保證（特別于實時系統(tǒng)）4．優(yōu)先權(quán)準(zhǔn)則：（即需要搶占調(diào)度）3.2.2選擇調(diào)度方式和算法的若干準(zhǔn)則

第十四頁，共六十八頁，編輯于2023年，星期四二、面向系統(tǒng)的準(zhǔn)則1．吞吐量高（特別于批處理）：單位時間完成作業(yè)數(shù)2．處理機利用率好：（因CPU貴，特別于大中型多用戶系統(tǒng)）3．各類資源的平衡利用。3.2.2選擇調(diào)度方式和算法的若干準(zhǔn)則

第十五頁，共六十八頁，編輯于2023年，星期四

3.3調(diào)度算法

——是一個資源分配問題

3.3.1先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

1.先來先服務(wù)調(diào)度算法FCFS特點：簡單，有利于長作業(yè)即CPU繁忙性作業(yè)進(jìn)程名到達(dá)時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99第十六頁，共六十八頁，編輯于2023年，星期四3.3.1先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法2.短作業(yè)進(jìn)程優(yōu)先調(diào)度算法：SJ(P)F選出估計運行時間最短的作業(yè)（進(jìn)程）提高了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）對長作業(yè)不利，有可能得不到服務(wù)（饑餓）未考慮作業(yè)的緊迫性估計時間不易確定第十七頁，共六十八頁，編輯于2023年，星期四圖3.4FCFS和SJF比較進(jìn)程名ABCDE平均到達(dá)時間01234服務(wù)時間43524FCFS完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.10417231241418ABCDEFCFS041923184613ABCDESJF第十八頁，共六十八頁，編輯于2023年，星期四3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法類型非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法，實時性更好。2.優(yōu)先權(quán)類型：1．靜態(tài)優(yōu)先權(quán)：進(jìn)程優(yōu)先權(quán)在整個運行期不變。確定優(yōu)先權(quán)依據(jù)（1）進(jìn)程類型（2）進(jìn)程對資源的需求；（3）根據(jù)用戶需求。特點：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度。第十九頁，共六十八頁，編輯于2023年，星期四3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法(2)2．動態(tài)優(yōu)先權(quán)：如：優(yōu)先權(quán)隨執(zhí)行時間而下降，隨等待時間而升高。響應(yīng)比Rp=（等待時間＋服務(wù)時間）/服務(wù)時間作為優(yōu)先權(quán)優(yōu)點：長短兼顧缺點：需計算Rp3.高響應(yīng)比優(yōu)先算法：特點：響應(yīng)比Rp=（tw+ts）/ts（1）短作業(yè)RP大。（2）ts（要求服務(wù)時間）相同的進(jìn)程間相當(dāng)于FCFS。（3）長作業(yè)等待一段時間仍能得到服務(wù)。第二十頁，共六十八頁，編輯于2023年，星期四3.3.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)時間片大小的確定太大：退化為FCFS；太小：系統(tǒng)開銷過大系統(tǒng)對響應(yīng)時間的要求；T=nq就緒隊列中進(jìn)程的數(shù)目；系統(tǒng)的處理能力：（應(yīng)保證一個時間片處理完常用命令）第二十一頁，共六十八頁，編輯于2023年，星期四2.多級反饋隊列調(diào)度

多個就緒隊列，不同優(yōu)先級新進(jìn)程首先進(jìn)入第一隊列尾，F(xiàn)CFS；時間片結(jié)束后未完成的進(jìn)入第二隊列尾…第一隊列空閑時才調(diào)度第二隊列，搶占式3.3.3基于時間片的輪轉(zhuǎn)調(diào)度算法（2）特點：長、短作業(yè)兼顧，有較好的響應(yīng)時間（1）短作業(yè)一次完成；（2）中型作業(yè)周轉(zhuǎn)時間不長；（3）大型作業(yè)不會長期不處理。第二十二頁，共六十八頁，編輯于2023年，星期四就緒隊列1至CPUS1就緒隊列2S2至CPU就緒隊列3S3至CPU就緒隊列nSn至CPU時間片：S1<S2<S3圖3－7多級隊列反饋調(diào)度算法第二十三頁，共六十八頁，編輯于2023年，星期四3.4.1實現(xiàn)實時調(diào)度的基本條件1．提供必要的調(diào)度信息（1）就緒時間；（2）開始/完成截止時間；（3）處理時間；（4）資源要求；（5）優(yōu)先級；2．系統(tǒng)處理能力強，滿足：3.4實時調(diào)度Ci為處理時間，Pi為周期時間（基于周期性實時任務(wù)）第二十四頁，共六十八頁，編輯于2023年，星期四3.采用搶占調(diào)度方式剝奪方式：一般都采用此非剝奪方式（實現(xiàn)簡單）：一般應(yīng)使實時任務(wù)較小，以及時放棄CPU。4.具有快速切換機制具有快速響應(yīng)外部中斷能力?？焖偃蝿?wù)分派能力3.4.1實現(xiàn)實時調(diào)度的基本條件第二十五頁，共六十八頁，編輯于2023年，星期四3.4.2實時調(diào)度算法的分類1非搶占式調(diào)度算法時間片輪轉(zhuǎn) 秒級非搶占優(yōu)先權(quán)（協(xié)同） 秒~毫秒級2搶占式調(diào)度算法時鐘中斷搶占優(yōu)先權(quán) 毫秒級基于搶占點搶占立即搶占搶占優(yōu)先權(quán)毫秒~微秒級只要不在臨界區(qū)即搶占（中斷引發(fā)）進(jìn)程1進(jìn)程2進(jìn)程n實時進(jìn)程調(diào)度時間實時進(jìn)程要求調(diào)度調(diào)度實時進(jìn)程運行a非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度當(dāng)前進(jìn)程運行完成b非搶占優(yōu)先權(quán)調(diào)度調(diào)度時間當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度搶占時刻（其它中斷）d立即搶占優(yōu)先權(quán)調(diào)度調(diào)度時間c基于時鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實時進(jìn)程實時進(jìn)程要求調(diào)度時鐘中斷到達(dá)時調(diào)度時間第二十六頁，共六十八頁，編輯于2023年，星期四3.4.3常用的幾種實時調(diào)度算法1.最早截止時間優(yōu)先EDF（earliestdeadlinefirst)算法根據(jù)任務(wù)的截止時間來確定任務(wù)的優(yōu)先級截止時間越早，優(yōu)先級越高就緒隊列中按個任務(wù)截止時間的早晚排序可以是搶占式或非搶占式第二十七頁，共六十八頁，編輯于2023年，星期四2最早截止時間優(yōu)先EDF例1341234t開始截止時間任務(wù)到達(dá)任務(wù)執(zhí)行EDF算法用于非搶占調(diào)度方式34213.4.3常用的幾種實時調(diào)度算法第二十八頁，共六十八頁，編輯于2023年，星期四2.最低松弛度優(yōu)先LLF算法松弛度：根據(jù)任務(wù)的緊急（松弛）程度確定優(yōu)先級，越緊急優(yōu)先級越高松弛度=必須完成時間-本身運行時間-當(dāng)前時間若A進(jìn)程需在200ms時完成，其本身運行需要100ms，當(dāng)前時刻是10ms，則A的松弛度為：200－100－10＝90按松弛度排序的實時任務(wù)就緒隊列主要用于可搶占的調(diào)度方式中3.4.3常用的幾種實時調(diào)度算法第二十九頁，共六十八頁，編輯于2023年，星期四最低松弛度優(yōu)先LLF算法(2)A1A2A3A4t01020304050607080B1B1B2B2t1t2t3t4t5t6t7t8A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t每20ms執(zhí)行一次，執(zhí)行時間10ms每50ms執(zhí)行一次，執(zhí)行時間25mst2--A2:20,B1:15t1--A1:10,B1:25t3--A2:0,B1:15t4--A3:10,B1:5t5—A3:5,B2:30t7—A4:0,B2:20第三十頁，共六十八頁，編輯于2023年，星期四進(jìn)程到達(dá)時間/s服務(wù)時間/s103226344465582請比較采用以下調(diào)度策略各進(jìn)程的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。1、先來先服務(wù)FCFS2、時間片輪轉(zhuǎn)RR（q=1和q=4）3、最短進(jìn)程優(yōu)先SPN4、最高響應(yīng)比優(yōu)先HRRN5、多級反饋隊列q=2n第三十一頁，共六十八頁，編輯于2023年，星期四3.5產(chǎn)生死鎖的原因和必要條件所謂死鎖(deadlock)，是指多個進(jìn)程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處在這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進(jìn)。第三十二頁，共六十八頁，編輯于2023年，星期四3.5.1產(chǎn)生死鎖的原因一、競爭資源引起死鎖。1．可剝奪（CPU、內(nèi)存）和非剝奪性（打印機，磁帶機）資源2．競爭非剝奪性資源——可造成死鎖3．競爭臨時性資源——也可能引起死鎖p1p2R1R2p1p3S3S1p2S2第三十三頁，共六十八頁，編輯于2023年，星期四二、進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序非法3.5.1產(chǎn)生死鎖的原因第三十四頁，共六十八頁，編輯于2023年，星期四213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.5.1產(chǎn)生死鎖的原因第三十五頁，共六十八頁，編輯于2023年，星期四3.5.2產(chǎn)生死鎖的必要條件1．互斥條件（資源的臨界性）2．請求和保持條件3．不剝奪條件4．環(huán)路等待第三十六頁，共六十八頁，編輯于2023年，星期四資源分配圖進(jìn)程

有4個實例的某類資源Pi

申請的一個實例RjPi持有Rj的一個實例

PiRjPiRj3.5.2產(chǎn)生死鎖的必要條件第三十七頁，共六十八頁，編輯于2023年，星期四Example第三十八頁，共六十八頁，編輯于2023年，星期四死鎖！第三十九頁，共六十八頁，編輯于2023年，星期四死鎖？第四十頁，共六十八頁，編輯于2023年，星期四BasicFacts圖中沒有環(huán)沒有死鎖.

圖中有環(huán)每個資源類型只有一個實例,那么一定死鎖.每個資源類型只有多個實例,那么可能死鎖.第四十一頁，共六十八頁，編輯于2023年，星期四3.5.3處理死鎖的基本方法

1．預(yù)防；破壞4個條件之一：有效，使資源利用率低。2．避免：防止進(jìn)入不安全態(tài)。3．檢測：檢測到死鎖再清除。4．解除：與“檢”配套。第四十二頁，共六十八頁，編輯于2023年，星期四3.6死鎖預(yù)防和避免

3.6.1死鎖預(yù)防

一、互斥條件是資源固有屬性，不能避免。二、摒棄請求和保持條件全分配，全釋放（AND）缺點：（1）延遲進(jìn)程運行 （2）資源嚴(yán)重浪費三、摒棄“不剝奪”條件 增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。第四十三頁，共六十八頁，編輯于2023年，星期四 四、摒棄“環(huán)路”條件有序資源分配法：為資源編號，申請時需按編號次序進(jìn)行。缺點：（1）新增資源不便（原序號已排定）（2）用戶不自由（3）資源與進(jìn)程使用順序不同造成浪費3.6.1死鎖預(yù)防第四十四頁，共六十八頁，編輯于2023年，星期四3.6.2系統(tǒng)的安全狀態(tài)在“避免死鎖”方法中的判斷條件1.安全狀態(tài)按某種順序并發(fā)進(jìn)程都能達(dá)到獲得最大資源的可順序完成的序列為安全序列。能找到安全序列的狀態(tài)為安全狀態(tài)，否則為不安全狀態(tài)。避免死鎖：資源分配時，使系統(tǒng)不進(jìn)入不安全狀態(tài)第四十五頁，共六十八頁，編輯于2023年，星期四2.安全狀態(tài)例進(jìn)程最大需求已分配可用P11053P242P392安全序列：p2p1p33.6.2系統(tǒng)的安全狀態(tài)第四十六頁，共六十八頁，編輯于2023年，星期四3.安全不安全的轉(zhuǎn)換不按照安全序列分配資源，可能轉(zhuǎn)入不安全狀態(tài)上例中，若P3再申請一臺，則不安全進(jìn)程最大需求已分配可用P11052P242P3933.6.2系統(tǒng)的安全狀態(tài)第四十七頁，共六十八頁，編輯于2023年，星期四安全/不安全&死鎖3.6.2系統(tǒng)的安全狀態(tài)第四十八頁，共六十八頁，編輯于2023年，星期四系統(tǒng)在安全狀態(tài)不會死鎖.

系統(tǒng)在不安全狀態(tài)可能死鎖.

避免保證系統(tǒng)不會進(jìn)入不安全狀態(tài).

3.6.2系統(tǒng)的安全狀態(tài)第四十九頁，共六十八頁，編輯于2023年，星期四3.6.3利用銀行家算法避免死鎖

1．?dāng)?shù)據(jù)結(jié)構(gòu)Available[j]=k:系統(tǒng)現(xiàn)有Rj類資源k個；Max[i,j]=k:進(jìn)程i需要Rj的最大數(shù)k個；Allocation[i,j]=k:進(jìn)程i已得到Rj類資源k個；

Need[i,j]=k: 進(jìn)程i需要Rj類資源k個有：Need[i,j]=Max[i,j]－Allocation[i,j]Requesti[j]=k

進(jìn)程i請求k個Rj類資源Work[j]=k:系統(tǒng)可提供進(jìn)程繼續(xù)運行所需要的資源數(shù)目finish[i]：布爾量，表進(jìn)程i能否順序完成。

第五十頁，共六十八頁，編輯于2023年，星期四銀行家算法之例五個進(jìn)程{P0,P1,P2,P3,P4},三種資源{A，B，C}，數(shù)量分別為10、5、7，在T0時刻的資源分配情況:MaxABCAllocABCNeedABCAvailABCP0753010743332P1332200122P2902302600P3222211011P44330024313.6.3利用銀行家算法避免死鎖

第五十一頁，共六十八頁，編輯于2023年，星期四2．銀行家算法（1）如果Requesti≤Need,則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。（2）如果Requesti≤Available,則轉(zhuǎn)向步驟（3）；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。（3）系統(tǒng)試探把要求的資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[j]:=Availablei[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)。

3.6.3利用銀行家算法避免死鎖

第五十二頁，共六十八頁，編輯于2023年，星期四3、安全性算法（1）設(shè)置兩個向量①工作向量Work。②Finish。（2）從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：①Finish[i]:=false②Need[i,j]≤Work[j]如找到，執(zhí)行步驟（3）；否則，執(zhí)行步驟（4）。（3）當(dāng)進(jìn)程P獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]:=Work[i]+Allocation[i,j];Finish[i]：=true;Gotostep2;（4）如果所有進(jìn)程的Finish[i]=true,則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。3.6.3利用銀行家算法避免死鎖

第五十三頁，共六十八頁，編輯于2023年，星期四銀行家算法之例五個進(jìn)程{P0,P1,P2,P3,P4},三種資源{A，B，C}，數(shù)量分別為10、5、7，在T0時刻的資源分配情況:MaxABCAllocABCNeedABCAvailABCP0753010743332P1332200122P2902302600P3222211011P4433002431Work[j]:=Work[i]+Alloc[i,j]Finish[i]：=true;532743745104710573.6.3利用銀行家算法避免死鎖

從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：①Finish[i]:=false②Need[i,j]≤Work[j]第五十四頁，共六十八頁，編輯于2023年，星期四（1）T0時刻的安全性利用安全性算法對T0時刻的資源分配情況進(jìn)行分析，可得下表所示的T0時刻的安全性分析，從中得知，T0時刻存在著一個安全序列{P1，P3，P4，P2，P0}，故系統(tǒng)是安全的:WorkABCNeedABCAllocABCWork+AvailABCFinishP1332122200532trueP3532011211743trueP4743432002745trueP27456003021047trueP010477430101057true3.6.3利用銀行家算法避免死鎖

第五十五頁，共六十八頁，編輯于2023年，星期四（2）P1請求資源P1發(fā)出請求向量Request(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查：(1)Request1(1,0,2)≤Need(1,2,2)(2)Request1(1,0,2)≤Available(3,3,2)(3)系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation和Need向量，由此形成的資源變化情況如圖MaxABCAllocABCNeedABCAvailABCP0753010743230P1332200122P2902302600P3222211011P44330024310203023.6.3利用銀行家算法避免死鎖

第五十六頁，共六十八頁，編輯于2023年，星期四（4）我們再利用安全性檢查此時系統(tǒng)是否安全。由所進(jìn)行的安全性檢查得知，可以找到一個安全序列{P1，P3，P4，P2，P0}。因此，系統(tǒng)是安全的，可以立即將P1所申請的資源分配給它。WorkABCNeedABCAllocABCWork+AvailABCFinishP1230020302532trueP3532011211743trueP4743432002745trueP0745743010755trueP210476003021057true3.6.3利用銀行家算法避免死鎖

第五十七頁，共六十八頁，編輯于2023年，星期四（3）P4請求資源P4發(fā)出請求向量Request(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查：(1)Request4(3,3,0)≤Need4(4,3,1)。(2)Request4(3,3,0)>Available(2,3,0)，讓P4等待。（4）P0請求資源P0發(fā)出請求向量Request0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查：(1)Request0(0,2,0)≤Need0(7,4,3));(2)Request0(0,2,0)≤Available(2,3,0)，(3)進(jìn)行安全性檢查可用資源Available{2,1,0}已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。

3.6.3利用銀行家算法避免死鎖

第五十八頁，共六十八頁，編輯于2023年，星期四3.7

死鎖的檢測和解除3.7.1、死鎖的檢測系統(tǒng)必須須提供檢測和解除死鎖的手段：（1）保存有關(guān)資源的請求和分配信息；（2）提供算法以利用這些信息來檢測系統(tǒng)是否進(jìn)入死鎖。1、資源分配圖（ResourceAilocationGraph）系統(tǒng)死鎖可利用資源分配圖來描述。G=（N，E）：（1）N分為兩個互斥的子集，進(jìn)程結(jié)點P=（P1，P2,…,Pn）,資源結(jié)點R={r1,r2,…,rn},N=P∪R。（2）E中的邊e∈E,都連接著P中的一個結(jié)點和R中的一個結(jié)點，e={pi,rj}是資源請求邊，由進(jìn)程pi指向資源rj,它表示進(jìn)程pi請求一個單位的rj資源。第五十九頁，共六十八頁，編輯于2023年，星期四p1p2R2R1分配請求3.7.1

死鎖的檢測第六十頁，共六十八頁，編輯于2023年，星期四2、死鎖定理簡化資源分配圖來檢測系統(tǒng)處于S狀態(tài)時，是否為死鎖狀態(tài)。簡化方法如下：（1）在資源分配圖中，找出一個既不阻塞又非獨立的進(jìn)程結(jié)點pi。在順利情況下，pi可獲得所需資源而繼續(xù)執(zhí)行，直至運行完畢，再釋放其所占有的全部資源。這相當(dāng)于消去pi所有的請求邊和分配邊，使之成為孤立的結(jié)點。p1p2R2R1p1p2R2R13.7.1

死鎖的檢測第六十一頁，共六十八頁，編輯