操作系統(tǒng)課件zgsos64,27-31處理機調(diào)度與死鎖

123二月2023北京交通大學計算機學院翟高壽主講教師：翟高壽（副教授）聯(lián)系電話：(辦)電子郵件：制作人：翟高壽制作單位：北京交通大學計算機學院《操作系統(tǒng)》223二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法323二月2023北京交通大學計算機學院翟高壽多道程序環(huán)境與處理機調(diào)度作業(yè)類型與處理機獲得過程批量型作業(yè)、終端型作業(yè)基于操作系統(tǒng)類型的調(diào)度分類批處理/分時/實時調(diào)度及多處理機調(diào)度調(diào)度是多道程序系統(tǒng)的關鍵所在系統(tǒng)運行性能（如吞吐量大小、周轉(zhuǎn)時間長短、響應及時性等）在很大程度上都取決于調(diào)度，特別是處理機調(diào)度一個作業(yè)從提交到執(zhí)行，通常都要經(jīng)歷高級、中級、低級及I/O等多級調(diào)度423二月2023北京交通大學計算機學院翟高壽多級調(diào)度示意圖523二月2023北京交通大學計算機學院翟高壽高級調(diào)度（作業(yè)/長程/宏觀調(diào)度）概念用于決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程和分配必要資源；然后，再將新創(chuàng)建進程插入到就緒隊列上準備執(zhí)行操作系統(tǒng)配置作業(yè)調(diào)度機制分析批處理系統(tǒng)分時系統(tǒng)、實時系統(tǒng)及時性要求作業(yè)調(diào)度機制要領作業(yè)量確定多道程序度(DegreeofMultiprogramming)作業(yè)選擇調(diào)度算法623二月2023北京交通大學計算機學院翟高壽低級調(diào)度（進程/短程調(diào)度）概念用來決定就緒隊列中的哪個進程將獲得處理機，然后再由分派程序（Dispatcher）執(zhí)行把處理機分配給該進程的具體操作操作系統(tǒng)配置進程調(diào)度機制分析基本調(diào)度，所有類型操作系統(tǒng)均需配置調(diào)度方式分類非搶占方式（僅適用于批處理系統(tǒng)）搶占方式（分時、實時及批處理系統(tǒng)均可）723二月2023北京交通大學計算機學院翟高壽非搶占與搶占調(diào)度方式比較非搶占調(diào)度方式(Non-preemptiveMode)處理機分配給進程直至完成或阻塞引起進程調(diào)度的因素：當前進程執(zhí)行完畢或因發(fā)生事件、提出I/O請求、執(zhí)行原語操作而阻塞實現(xiàn)簡單、系統(tǒng)開銷小，但難以滿足緊急任務要求，故不宜在實時系統(tǒng)中采用搶占調(diào)度方式(PreemptiveMode)允許暫停正在執(zhí)行進程和重新分配處理機搶占原則（優(yōu)先權(quán)/短作業(yè)優(yōu)先/時間片原則）823二月2023北京交通大學計算機學院翟高壽中級調(diào)度（中程調(diào)度）概念為提高內(nèi)存利用率和系統(tǒng)吞吐量，應使那些暫時不能運行的進程放棄占用內(nèi)存資源，即調(diào)至外存上去等待；當內(nèi)存稍有空閑時，可將外存中那些重又具備運行條件的就緒進程重新調(diào)入內(nèi)存，修改其狀態(tài)和掛到就緒進程隊列等待進程調(diào)度實質(zhì)存儲器管理中的對換功能923二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法1023二月2023北京交通大學計算機學院翟高壽僅有進程調(diào)度的調(diào)度隊列模型就緒隊列阻塞隊列交互作業(yè)進程調(diào)度CPU進程完成等待事件時間片完事件出現(xiàn)1123二月2023北京交通大學計算機學院翟高壽具有高級和低級調(diào)度的調(diào)度隊列模型就緒隊列阻塞隊列1作業(yè)調(diào)度進程調(diào)度CPU進程完成等待事件1時間片完事件1出現(xiàn)后備隊列阻塞隊列2等待事件2事件2出現(xiàn)阻塞隊列n等待事件n事件n出現(xiàn)……批量作業(yè)交互作業(yè)1223二月2023北京交通大學計算機學院翟高壽同時具有三級調(diào)度的調(diào)度隊列模型就緒隊列就緒掛起隊列作業(yè)調(diào)度進程調(diào)度CPU進程完成事件出現(xiàn)時間片完中級調(diào)度后備隊列阻塞掛起隊列掛起阻塞隊列等待事件事件出現(xiàn)批量作業(yè)交互作業(yè)掛起1323二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法1423二月2023北京交通大學計算機學院翟高壽選擇調(diào)度方式和算法的若干準則面向用戶的準則（與操作系統(tǒng)類型有關）周轉(zhuǎn)時間短（平均周轉(zhuǎn)/帶權(quán)周轉(zhuǎn)時間）響應時間快截至時間的保證優(yōu)先權(quán)準則面向系統(tǒng)的準則系統(tǒng)吞吐量高處理機利用率好各類資源的平衡利用1523二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法1623二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法1723二月2023北京交通大學計算機學院翟高壽先來先服務調(diào)度算法FCFS基本思想先來先服務作業(yè)調(diào)度算法先來先服務進程調(diào)度算法算法特點有利于長作業(yè)（進程）而不利于短作業(yè)（進程）有利于CPU繁忙型作業(yè)（進程）而不利于I/O繁忙型作業(yè)（進程）1823二月2023北京交通大學計算機學院翟高壽先來先服務調(diào)度算法舉例分析進程名到達時間服務時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間ABCD0123110011000110110211011022021100100199111001.991923二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法2023二月2023北京交通大學計算機學院翟高壽短進程優(yōu)先調(diào)度算法舉例分析進程名ABCDE平均到達時間01234服務時間43524完成時間47121418周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間1225.53.52.8完成時間4918613周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.1作業(yè)情況先來先服務短進程優(yōu)先2123二月2023北京交通大學計算機學院翟高壽短作業(yè)(進程)優(yōu)先調(diào)度算法SJ(P)F基本思想短作業(yè)優(yōu)先調(diào)度算法短進程優(yōu)先調(diào)度算法算法特點能有效降低作業(yè)（進程）平均等待時間和提高系統(tǒng)吞吐量不利于長作業(yè)（進程）完全未考慮作業(yè)（進程）的緊迫程度作業(yè)（進程）執(zhí)行時間估計的不準確性2223二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法2323二月2023北京交通大學計算機學院翟高壽高優(yōu)先權(quán)優(yōu)先調(diào)度算法FPF基本思想照顧緊迫型作業(yè)（進程）算法分類非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)類型靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)進程優(yōu)先權(quán)確定依據(jù)：進程類型、資源需求及用戶要求2423二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法2523二月2023北京交通大學計算機學院翟高壽高響應比優(yōu)先調(diào)度算法基本思想短作業(yè)優(yōu)先調(diào)度算法+動態(tài)優(yōu)先權(quán)機制優(yōu)先權(quán)（響應比RP）（等待時間+要求服務時間）/要求服務時間算法特點短作業(yè)與先后次序的兼顧，且不會使長作業(yè)長期得不到服務響應比計算系統(tǒng)開銷2623二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法2723二月2023北京交通大學計算機學院翟高壽時間片輪轉(zhuǎn)調(diào)度算法基本思想按先來先服務原則排隊時間片及時鐘中斷時間片大小的確定系統(tǒng)對響應時間的要求就緒隊列中進程的數(shù)目系統(tǒng)的處理能力2823二月2023北京交通大學計算機學院翟高壽時間片輪轉(zhuǎn)調(diào)度算法舉例分析待續(xù)01234567891011121314151617ABCDEABCDEABCEACEtABCDEq=1q=42923二月2023北京交通大學計算機學院翟高壽時間片輪轉(zhuǎn)調(diào)度算法舉例分析續(xù)完進程名ABCDE平均到達時間01234服務時間43424完成時間151216917周轉(zhuǎn)時8帶權(quán)周轉(zhuǎn)時間3.753.673.533.253.43完成時間47111317周轉(zhuǎn)時間46910138.4帶權(quán)周轉(zhuǎn)時間122.2553.252.61q=4q=1作業(yè)情況3023二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法3123二月2023北京交通大學計算機學院翟高壽多級隊列調(diào)度算法引入的必要性多操作系統(tǒng)類型配置批量型作業(yè)和交互性作業(yè)性質(zhì)的不同基本思想作業(yè)性質(zhì)分類排列，不同隊列不同調(diào)度算法隊列間關系處理優(yōu)先權(quán)方式前/后臺比例方式3223二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法3323二月2023北京交通大學計算機學院翟高壽多級反饋隊列調(diào)度算法引入的必要性各類進程調(diào)度算法均有一定的局限性基本思想設置多個就緒隊列并賦予各個隊列不同優(yōu)先權(quán)不同隊列中進程執(zhí)行的時間片大小各不相同先來先服務調(diào)度算法與時間片輪轉(zhuǎn)調(diào)度算法相結(jié)合隊列間調(diào)度準則和搶占式優(yōu)先權(quán)調(diào)度算法性能能較好地滿足各種類型用戶（終端型作業(yè)用戶、短批處理作業(yè)用戶、長批處理作業(yè)用戶）的要求3423二月2023北京交通大學計算機學院翟高壽3.4調(diào)度算法（資源分配算法）3.4.1先來先服務調(diào)度算法3.4.2短作業(yè)（進程）優(yōu)先調(diào)度算法3.4.3高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.4.4高響應比優(yōu)先調(diào)度算法3.4.5時間片輪轉(zhuǎn)調(diào)度算法3.4.6多級隊列調(diào)度算法3.4.7多級反饋隊列調(diào)度算法3523二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法3623二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除3723二月2023北京交通大學計算機學院翟高壽死鎖的基本概念死鎖（Deadlock）在多道程序系統(tǒng)中，并發(fā)執(zhí)行的多個進程因爭奪資源而造成的一種若無外力作用有關進程都將永遠不能向前推進的僵持狀態(tài)或僵局資源分類可剝奪資源與不可剝奪資源永久性資源與臨時性資源3823二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除3923二月2023北京交通大學計算機學院翟高壽死鎖產(chǎn)生原因之一：競爭資源I/O設備共享時的死鎖情況（A）競爭非剝奪性資源進程間通信時的死鎖情況（B）競爭臨時性資源P1P2R1R2P1P3S1S3P2S24023二月2023北京交通大學計算機學院翟高壽死鎖產(chǎn)生原因之二：進程推進次序非法P1Request(R1)P1Request(R2)P1Release(R1)P1Release(R2)P2Request(R2)P2Request(R1)P2Release(R2)P2Release(R1)12344123二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除4223二月2023北京交通大學計算機學院翟高壽產(chǎn)生死鎖的必要條件互斥條件資源排它性使用請求和保持條件請求資源未果進程雖阻塞但保持占有資源不放不剝奪條件進程已獲資源未使用完之前不能被剝奪環(huán)路等待條件進程-資源環(huán)形鏈{P0,P1,P2,…,Pn}4323二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除4423二月2023北京交通大學計算機學院翟高壽處理死鎖的基本方法預防死鎖設置某些限制前提以破壞產(chǎn)生死鎖必要條件避免死鎖資源動態(tài)分配過程中，利用某種方法去防止系統(tǒng)進入不安全狀態(tài)檢測死鎖運行過程中通過系統(tǒng)設置的檢測機構(gòu)及時檢測死鎖的發(fā)生，并精確確定相關進程和資源解除死鎖撤銷或掛起一些進程以回收資源和再分配4523二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除4623二月2023北京交通大學計算機學院翟高壽死鎖的預防策略之一摒棄“請求和保持”條件系統(tǒng)要求所有進程在開始運行之前，都必須一次性地申請其在整個運行過程所需的全部資源和進行一次性分配簡單、安全且易于實現(xiàn)資源浪費、進程延遲4723二月2023北京交通大學計算機學院翟高壽死鎖的預防策略之二摒棄“不剝奪”條件進程在需要資源時才提出請求，且得不到滿足時應釋放其已占有資源實現(xiàn)復雜，代價很大（反復地申請與釋放資源、進程周轉(zhuǎn)時間延長、系統(tǒng)吞吐量降低、系統(tǒng)開銷增加）4823二月2023北京交通大學計算機學院翟高壽死鎖的預防策略之三摒棄“環(huán)路等待”條件所有資源按類型進行線性排隊，所有進程對資源的請求嚴格按資源序號遞增次序提出資源次序的不靈活性（新設備、程序邏輯設計與編程限制及資源浪費）4923二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除5023二月2023北京交通大學計算機學院翟高壽資源分配圖G=(P∪R,E)資源請求邊e=<Pi,Rj>資源分配邊e=<Rj,Pi>P1P2R1R2P1P2○○○R2R1○○5123二月2023北京交通大學計算機學院翟高壽死鎖定理系統(tǒng)狀態(tài)S為死鎖狀態(tài)的充要條件是當且僅當該狀態(tài)下的資源分配圖是不可完全化簡的P1P2○○○R2R1○○P1P2○○○R2R1○○P1P2○○○R2R1○○5223二月2023北京交通大學計算機學院翟高壽死鎖檢測算法1令Work

=AvailableIsolatedSet={Pi∣Allocation[i]=0∧Requesti=0}2forallPi

IsolatedSet

dobeginforallRequesti≦Work

dobegin

Work

=Work+Allocation[i];IsolatedSet=IsolatedSet∪{Pi}

endend3deadlock=～(IsolatedSet={P1,

P2,

…

,

Pn});5323二月2023北京交通大學計算機學院翟高壽死鎖的解除基本方法剝奪其它進程足夠數(shù)量資源給死鎖進程撤消死鎖進程（全部撤銷或逐個撤銷）死鎖解除策略評價指標為解除死鎖所需撤消的進程數(shù)目最小撤消死鎖進程所付出的代價最小5423二月2023北京交通大學計算機學院翟高壽死鎖解除策略實例評析SP1(CU1)U1U2UkP2(CU2)Pk(CUk)…P1V21V23V2kP3Pk…P1Vk1Vk2Vkk-1P2Pk-1…P2V12V13V1kP3Pk…P3W123W124W12kP4Pk……P1W231W234W23kP4Pk………P1Wkk-11Wkk-12Wkk-1k-2P2Pk-2……兩種死鎖解除策略評析Cost=AverageCostForCancelProcess×∏KCost=∑min{CostForCancelProcessi}5523二月2023北京交通大學計算機學院翟高壽3.5死鎖產(chǎn)生及處理策略3.5.1死鎖的基本概念3.5.2死鎖產(chǎn)生的原因3.5.3死鎖產(chǎn)生的必要條件3.5.4處理死鎖的基本方法3.5.5死鎖的預防3.5.6死鎖的檢測與解除5623二月2023北京交通大學計算機學院翟高壽第三章處理機調(diào)度與死鎖3.1高級、中級與低級調(diào)度3.2調(diào)度隊列模型3.3調(diào)度方式與算法選擇準則3.4調(diào)度算法3.5死鎖產(chǎn)生及處理策略3.6死鎖避免與銀行家算法5723二月2023北京交通大學計算機學院翟高壽死鎖避免基本思想允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應首先就資源分配的安全性進行檢查，且僅當確認此次分配不會導致系統(tǒng)進入不安全狀態(tài)時才可分配，否則予以拒絕5823二月2023北京交通大學計算機學院翟高壽死鎖避免基本概念安全狀態(tài)指系統(tǒng)可按某種進程序列<P1,P2,…,Pn>（稱之為安全分配序列）來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程均能順利完成不安全狀態(tài)系統(tǒng)無法找到一個安全分配序列的系統(tǒng)狀態(tài)死鎖與狀態(tài)安全性之間的關系并非所有不安全狀態(tài)都是死鎖狀態(tài)當系統(tǒng)進入不安全狀態(tài)后，便可能陷入死鎖只要保證系統(tǒng)處于安全狀態(tài)，便可避免死鎖5923二月2023北京交通大學計算機學院翟高壽安全狀態(tài)及向不安全狀態(tài)的轉(zhuǎn)換T0時刻存在安全分配序列<P2,P1,P3>若在T0時刻應進程請求將所剩磁帶機中的1臺分配給P3，則系統(tǒng)進入不安全狀態(tài)資源名稱資源總數(shù)可用資源量可用資源量磁帶機1232進程最大需求已分配(尚需)已分配(尚需)P1105（5）5（5）P242（2）2（2）P392（7）3（6）6023二月2023北京交通大學計算機學院翟高壽銀行家算法之數(shù)據(jù)結(jié)構(gòu)可利用資源向量/請求向量[m]Available[j]=k表示系統(tǒng)現(xiàn)有k個Rj類資源Requesti[j]=k表示進程Pi請求k個Rj類資源最大需求矩陣/分配矩陣/需求矩陣[n,m]Max[i,j]=k表示進程Pi最多需要k個Rj類資源Allocation[i,j]=k表示進程Pi已有k個Rj類資源Need[i,j]=k表示進程Pi尚需k個Rj類資源工作向量[m]/Finish布爾向量[n]Work[j]=k表示系統(tǒng)“可”提供k個Rj類資源Finish[i]表示進程Pi可否擁有足夠資源完成運行6123二月2023北京交通大學計算機學院翟高壽銀行家算法之主體算法1進程Pi發(fā)出資源請求Requesti2若非Requesti≤Need[i]，出錯返回3若非Requesti≤Available，則應使Pi等待并返回4系統(tǒng)試探性地滿足Pi請求，并作以下修改：Available

=Available–

RequestiAllocation[i]

=Allocation[i]+RequestiNeed[i]=Need[i]–

Requesti5系統(tǒng)調(diào)用安全性算法進行資源分配檢查，若安全則執(zhí)行分配，否則恢復試探分配前狀態(tài)，并使Pi等待6223二月2023北京交通大學計算機學院翟高壽銀行家算法之安全性子算法1令Work

=Available，F(xiàn)inish=FALSE2從進程集合中查找一個滿足Finish[i]=FALSE且Need[i]<=Work的進程Pi

。若找到，則可假定Pi能獲得所需資源并順利執(zhí)行，故有：Work

=Work+

Allocation[i]

Finish[i]

=True

然后重復執(zhí)行第2步；否則轉(zhuǎn)至第3步執(zhí)行3如果Finish=TRUE，則表示系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)6323二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一A(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P1322200122P2902302600P3222211011P44330024316423二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一B(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P1322200122332532①TrueP2902302600P3222211011P44330024316523二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一C(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P1322200122332532①TrueP2902302600P3222211011532743②TrueP44330024316623二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一D(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P1322200122332532①TrueP2902302600P3222211011532743②TrueP4433002431743745③True6723二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一E(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743745755④TrueP1322200122332532①TrueP2902302600P3222211011532743②TrueP4433002431743745③True6823二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之一F(待續(xù))系統(tǒng)資源總量Available[A,B,C]={10,5,7}T0時刻Available[A,B,C]={3,3,2}安全分配序列<P1,P3,P4,P0,P2>進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743745755④TrueP1322200122332532①TrueP29023026007551057⑤TrueP3222211011532743②TrueP4433002431743745③True6923二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之二A(待續(xù))進程P1發(fā)出資源請求Request1(1,0,2)<Need1(1,2,2)T1時刻Available[A,B,C]={3,3,2}=>{2,3,0}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P13222+10+00+21-12-02-2P2902302600P3222211011P44330024317023二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之二B(待續(xù))進程P1發(fā)出資源請求Request1(1,0,2)<Need1(1,2,2)T1時刻Available[A,B,C]={3,3,2}=>{2,3,0}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P13222+10+00+21-12-02-2230532①TrueP2902302600P3222211011P44330024317123二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之二C(待續(xù))進程P1發(fā)出資源請求Request1(1,0,2)<Need1(1,2,2)T1時刻Available[A,B,C]={3,3,2}=>{2,3,0}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P13222+10+00+21-12-02-2230532①TrueP2902302600P3222211011532743②TrueP44330024317223二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之二D(待續(xù))進程P1發(fā)出資源請求Request1(1,0,2)<Need1(1,2,2)T1時刻Available[A,B,C]={3,3,2}=>{2,3,0}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743P13222+10+00+21-12-02-2230532①TrueP2902302600P3222211011532743②TrueP4433002431743745③True7323二月2023北京交通大學計算機學院翟高壽銀行家算法應用舉例之二E(待續(xù))進程P1發(fā)出資源請求Request1(1,0,2)<Need1(1,2,2)T1時刻Available[A,B,C]={3,3,2}=>{2,3,0}安全分配序列?

進程MAXABCAllocationABCNeedABCWorkABCAllocation+WorkABCFinishP0753010743745755④