第4章 調(diào)度和死鎖new

內(nèi)容調(diào)度的類型和模型調(diào)度算法實時系統(tǒng)中的調(diào)度多處理機調(diào)度調(diào)度算法舉例死鎖的基本概念死鎖的預防和避免死鎖的檢測和解除第四章 調(diào)度和死鎖目的及要求了解進程調(diào)度的類型，領(lǐng)會調(diào)度隊列模型，領(lǐng)會并理解選擇調(diào)度方式和算法的準則；掌握先來先服務、短作業(yè)（進程）優(yōu)先、時間片輪轉(zhuǎn)和優(yōu)先權(quán)調(diào)度算法，領(lǐng)會和理解高響應比優(yōu)先、多級隊列調(diào)度和多級反饋隊列調(diào)度算法；了解實時系統(tǒng)中調(diào)度要求和調(diào)度算法；了解多處理機系統(tǒng)中的進程調(diào)度算法；領(lǐng)會并掌握死鎖的基本概念，理解產(chǎn)生死鎖的原因、產(chǎn)生死鎖的必要條件；領(lǐng)會和理解死鎖的預防的各種方法；領(lǐng)會系統(tǒng)的安全狀態(tài)，理解并掌握掌握銀行家算法；了解和領(lǐng)會死鎖檢測的算法和死鎖解除的方法。第四章 調(diào)度和死鎖重點先來先服務、短作業(yè)（進程）優(yōu)先、時間片輪轉(zhuǎn)調(diào)度算法；死鎖的基本概念，產(chǎn)生死鎖的必要條件；預防死鎖的方法；銀行家算法。難點調(diào)度隊列模型；銀行家算法；死鎖的檢測算法。第四章 調(diào)度和死鎖4.1.1調(diào)度類型4.1.2調(diào)度隊列模型4.1.3選擇調(diào)度方式和算法的若干準則4.1 調(diào)度的類型與模型高級調(diào)度(HighLevelScheduling)

又稱作業(yè)調(diào)度、宏觀調(diào)度、長程調(diào)度(Long-TermScheduling)或接納調(diào)度(AdmissionScheduling)。

作業(yè)調(diào)度用于決定把外存上處于作業(yè)后備隊列上的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后再將新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。在批處理系統(tǒng)中，作業(yè)是先駐留在外存上的，因此需要有作業(yè)調(diào)度。然而在分時系統(tǒng)中，通過鍵盤輸入的命令和數(shù)據(jù)直接進入內(nèi)存，無需作業(yè)調(diào)度。接納多少個作業(yè)（多道程序度）接納哪些作業(yè)4.1.1調(diào)度類型低級調(diào)度(LowLevelScheduling)

又稱進程調(diào)度、微觀調(diào)度或短程調(diào)度(Short-TermScheduling)。

進程調(diào)度決定就緒隊列中哪個進程將獲得處理機，然后由分派程序執(zhí)行把處理機分配給該進程的操作。進程調(diào)度是最基本的調(diào)度，任何操作系統(tǒng)都有進程調(diào)度。4.1.1調(diào)度類型非搶占方式(Non-PreemptiveMode)

采用這種調(diào)度方式時，一旦把處理機分配給某進程后，便讓進程一直執(zhí)行，直到該進程完成或發(fā)生某事件而被阻塞時，才把處理機分配給其它進程，決不允許某進程搶占已經(jīng)分配出去的處理機。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)環(huán)境。缺點是難以滿足緊急任務的要求，不適用于實時、分時系統(tǒng)要求。4.1.1調(diào)度類型搶占方式(PreemptiveMode)

這種調(diào)度方式，允許進程調(diào)度程序根據(jù)某個原則，去停止某個正在執(zhí)行的進程，將已分配給進程的處理機，重新分配給另一個進程。搶占的原則有：時間片原則。各進程按時間片運行，當一個時間片用完后，便停止進程的執(zhí)行而重新進行調(diào)度。這個原則適用于分時系統(tǒng)、大多數(shù)實時系統(tǒng)以及要求較高的批處理系統(tǒng)。優(yōu)先權(quán)原則。通常是對一些重要的和緊急的進程賦予較高的優(yōu)先權(quán)。當這種進程進入就緒隊列時，如果其優(yōu)先權(quán)比正在執(zhí)行的進程優(yōu)先權(quán)高，便停止正在執(zhí)行的進程，將處理機分配給優(yōu)先權(quán)高的進程，使之執(zhí)行。短作業(yè)（進程）優(yōu)先原則。當新到達的作業(yè)（進程）比正在執(zhí)行的作業(yè)（進程）明顯地短時，將剝奪長作業(yè)（進程）的執(zhí)行，將處理機分配給短作業(yè)（進程），使之優(yōu)先執(zhí)行。4.1.1調(diào)度類型中級調(diào)度(IntermediateLevelScheduling)

又稱中程調(diào)度(Medium-TermScheduling)。 引入中級調(diào)度的目的是為了提高主存利用率和系統(tǒng)吞吐量。由于在進程并發(fā)執(zhí)行過程中，為了充分發(fā)揮內(nèi)存的效能，需將那些暫時不能運行的進程從內(nèi)存調(diào)到外存去等待（就緒掛起），而當內(nèi)存空閑時，進行中級調(diào)度，將那些在外存的等待的進程調(diào)入內(nèi)存，插入就緒隊列（激活、解掛），等待進程調(diào)度。 中級調(diào)度就是存儲管理中的對換，采用虛擬存儲技術(shù)的分時系統(tǒng)往往設(shè)立中級調(diào)度。4.1.1調(diào)度類型處理機三級調(diào)度：4.1.1調(diào)度類型外存作業(yè)后備狀態(tài)作業(yè)提交狀態(tài)就緒態(tài)阻塞態(tài)主存 進程調(diào)度運行態(tài)就緒態(tài)阻塞態(tài)中級調(diào)度作業(yè)調(diào)度作業(yè)完成狀態(tài)外存4.1.1調(diào)度類型僅有進程調(diào)度的調(diào)度隊列模型 在分時系統(tǒng)中通常僅設(shè)置了進程調(diào)度。此時系統(tǒng)有一個就緒隊列，每個進程運行一個時間片，進程運行一個時間片后如未完成，則被放在就緒隊列末尾。如進程運行中因等待某事件（例如申請I/O而等待I/O完成），則需排入阻塞隊列，系統(tǒng)因阻塞的原因不同可設(shè)幾個阻塞隊列。4.1.2調(diào)度隊列模型事件出現(xiàn)CPU交互用戶時間片完進程完成就緒隊列等待事件阻塞隊列進程調(diào)度具有高級調(diào)度和低級調(diào)度的調(diào)度隊列模型 在多道批處理系統(tǒng)中，一般處理機管理設(shè)置作業(yè)和進程兩級調(diào)度。它比第一個模型增加了高級調(diào)度。模型增加了在磁盤的作業(yè)后備隊列，作業(yè)調(diào)度的任務是從作業(yè)后備隊列中選一個作業(yè)為它創(chuàng)建至少一個進程，并分配資源，將它排入內(nèi)存進程就緒隊列末尾。

4.1.2調(diào)度隊列模型CPU時間片完進程完成就緒隊列等待事件1阻塞隊列1作業(yè)調(diào)度后備作業(yè)隊列等待事件n阻塞隊列n進程調(diào)度事件出現(xiàn)1事件出現(xiàn)n同時具有三級調(diào)度的調(diào)度隊列模型

在通用系統(tǒng)的多模式OS中，一般采用具有三級調(diào)度的調(diào)度隊列模型，由于多模式OS同時支持批處理、分時和實時處理，所以它必須具有以上模型4.1.2調(diào)度隊列模型中級調(diào)度調(diào)出CPU交互型作業(yè)時間片完等待事件完成就緒隊列就緒，掛起隊列阻塞，掛起隊列阻塞隊列事件出現(xiàn)作業(yè)調(diào)度后備作業(yè)隊列批量作業(yè)中級調(diào)度調(diào)入中級調(diào)度調(diào)出事件出現(xiàn)面向用戶的準則

為滿足用戶需求應遵循的一些準則：周轉(zhuǎn)時間短（批處理系統(tǒng)）周轉(zhuǎn)時間，是指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔（稱為作業(yè)周轉(zhuǎn)時間）它包括：作業(yè)在外存后備隊列上等待（作業(yè)）調(diào)度的時間；進程在就緒隊列上等待進程調(diào)度的時間；進程在CPU上執(zhí)行的時間；等待I/O操作完成的時間。 其中后三項在一個作業(yè)的處理過程中，可能發(fā)生多次。4.1.3

選擇調(diào)度方式和算法的若干準則提交作業(yè)后備隊列就緒隊列CPU作業(yè)調(diào)度進程調(diào)度周轉(zhuǎn)時間等待I/O完成4.1.3選擇調(diào)度方式和算法的若干準則對每個用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時間最短。但作為計算機系統(tǒng)的管理者，總是希望能使平均周轉(zhuǎn)時間最短；這不僅會有效地提高資源利用率，而且還可使大多數(shù)用戶感到滿意平均周轉(zhuǎn)時間可描述為：作業(yè)的周轉(zhuǎn)時間Ti與系統(tǒng)為它提供的實際服務時間Tsi之比，即W=T/Ts稱為帶權(quán)周轉(zhuǎn)時間,而平均帶權(quán)周轉(zhuǎn)時間可表示為：響應時間快（分時系統(tǒng)）響應時間常用于評價分時操作系統(tǒng)的性能，是選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一。響應時間是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應為止的時間，或說直到在屛幕上顯示出結(jié)果為止的一段時間間隔。它包括：從鍵盤輸入的請求信息傳送到處理機的時間；處理機對請求信息進行處理的時間；將所形成的響應回送到終端顯示器的時間。4.1.3

選擇調(diào)度方式和算法的若干準則鍵入請求顯示器顯示請求響應響應時間CPU處理請求截止時間的保證（實時系統(tǒng)）它是用來評價實時系統(tǒng)性能的重要指標，因而是選擇實時調(diào)度算法的重要準則。所謂截止時間，是指某任務必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。優(yōu)先權(quán)準則（批處理、分時和實時系統(tǒng)）

在選擇批處理、分時和實時系統(tǒng)的調(diào)度算法時，都可引用優(yōu)先權(quán)準則，以便讓那些緊急的作業(yè)（或事件），得到及時的處理。在要求較嚴格的場合，往往還需選擇搶占調(diào)度方式，才能保證緊急作業(yè)得到及時的處理。4.1.3

選擇調(diào)度方式和算法的若干準則面向系統(tǒng)的準則系統(tǒng)吞吐量高

這是用來評價批處理系統(tǒng)的重要指標。系統(tǒng)吞吐量是單位時間內(nèi)完成的作業(yè)數(shù)，它與批處理作業(yè)的平均長度具有密切關(guān)系。處理機利用率好

對于大中型多用戶系統(tǒng)，由于CPU價格十分昂貴，所以處理機利用率成為衡量大、中型系統(tǒng)性能的十分重要指標，但對單用戶微機或某些實時系統(tǒng)，該準則就不那么重要。各類資源的平衡利用

在大中型系統(tǒng)中，有效地利用各類資源（包括CPU、外存、I/O設(shè)備等）也是一個重要指標，對于微型機和某些實時系統(tǒng)，該準則也不重要。4.1.3

選擇調(diào)度方式和算法的若干準則4.2.1先進先服務調(diào)度算法4.2.2短作業(yè)（進程）優(yōu)先調(diào)度算法4.2.3時間片輪轉(zhuǎn)調(diào)度算法4.2.4優(yōu)先權(quán)調(diào)度算法4.2.5高響應比優(yōu)先調(diào)度算法4.2.6多級隊列調(diào)度算法4.2.7多級反饋隊列調(diào)度算法4.2調(diào)度算法調(diào)度算法

先進先服務FCFS(First-Come-First-Served)調(diào)度算法是一種最簡單的調(diào)度算法。 當在作業(yè)調(diào)度中采用該算法時，每次調(diào)度是從后備作業(yè)隊列中，選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放人就緒隊列。

在進程調(diào)度中，采用FCFS調(diào)度算法時，則每次調(diào)度是從就緒隊列中，選擇一個最先進入該隊列的進程，把處理機分配給它，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后，才放棄處理機。

該算法比較有利于長作業(yè)（進程），不利于短作業(yè)（進程）。4.2.1先進先服務調(diào)度算法

4.2.1先進先服務調(diào)度算法

實例

據(jù)此可知：FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)（進程），而不利于I／O繁忙型的作業(yè)（進程）。CPU繁忙型作業(yè)，是指該類作業(yè)需要大量的CPU時間進行計算，而很少請求I／（通常的科學計算便屬于CPU繁忙型作業(yè))。I／O繁忙型作業(yè)，是指CPU進行處理時，又需頻繁地請求I／O，而每次I／O的操作時間卻又很短。目前的大多數(shù)的事務處理，都屬于I/O繁忙型作業(yè)。

先進先出算法比較簡單，但很少作為一個獨立的調(diào)度算法被使用，一般總是作為其他算法的一種輔助手段，例如在優(yōu)先級調(diào)度算法中，對擁有相同的優(yōu)先級的進程進行調(diào)度時，可采用先進先出算法。

短作業(yè)（進程）優(yōu)先調(diào)度算法SJF（ShortestJobFirst）/SPF(ShortestProcessFirst）是對短作業(yè)或短進程優(yōu)先調(diào)度的算法。

SJF是從后備作業(yè)中選擇一個或多個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。

SPF是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并直到完成，或有事件發(fā)生而被阻塞放棄處理機，而重新調(diào)度。4.2.2短作業(yè)（進程）優(yōu)先調(diào)度算法4.2.2短作業(yè)（進程）優(yōu)先調(diào)度算法

優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量；缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。4.2.2短作業(yè)（進程）優(yōu)先調(diào)度算法

基本原理 時間片輪轉(zhuǎn)Round-Robin（RR）調(diào)度算法將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列。

每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms。 在一個時間片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，等待分配下一時間片再執(zhí)行。 然后把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內(nèi)，均能獲得一時間片處理機執(zhí)行時間。在RR算法中，時間片的大小對系統(tǒng)性能有很大的影響。4.2.3時間片輪轉(zhuǎn)調(diào)度算法

時間片大小的確定時間片長度變化的影響過長－>退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應時間長。過短－>用戶的一次請求需要多個時間片才能處理完，進程切換次數(shù)增加，系統(tǒng)開銷增大，響應時間長?？紤]因素對響應時間的要求

T(響應時間)=N(進程數(shù)目)*q(時間片)就緒進程的數(shù)目 數(shù)目越多，時間片越?。ó旐憫獣r間一定時）系統(tǒng)的處理能力 應當使用戶輸入的常用命令通常在一個時間片內(nèi)能處理完，否則使響應時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。4.2.3時間片輪轉(zhuǎn)調(diào)度算法

優(yōu)先權(quán)(Priority)調(diào)度算法的基本思想是系統(tǒng)為每個進程設(shè)置一個優(yōu)先數(shù)（對應一個優(yōu)先級），把所有的就緒進程按優(yōu)先級從高到低排序，調(diào)度時從就緒隊列中選擇優(yōu)先級最高的進程投入運行。

優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法

僅當占用CPU的進程運行結(jié)束或因某種原因不能繼續(xù)運行時，系統(tǒng)才進行重新調(diào)度。 進程切換次數(shù)少，系統(tǒng)開銷小，但可能導致優(yōu)先級低的進程長期搶占不到CPU。 主要用于批處理、實時性不高的實時系統(tǒng)。4.2.4優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)算法

當系統(tǒng)中有另一優(yōu)先級更高的進程變成就緒狀態(tài)時，系統(tǒng)應立即剝奪現(xiàn)運行進程占用CPU的權(quán)力，使該優(yōu)先級更高的進程投入運行。 系統(tǒng)能及時處理緊急事件，但系統(tǒng)開銷較大。 主要用于實時性高的實時系統(tǒng)、性能高的批處理以及分時系統(tǒng)。4.2.4優(yōu)先權(quán)調(diào)度算法

優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且規(guī)定它在進程的整個運行期間保持不變。一般，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示。例如，0～7，或0～255中的某一整數(shù)，又稱該整數(shù)為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示優(yōu)先權(quán)最高，數(shù)值愈大其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。4.2.4優(yōu)先權(quán)調(diào)度算法 確定進程優(yōu)先權(quán)的依據(jù)有： （1）進程類型。通常，系統(tǒng)進程（如接收進程、對換進程、磁盤I/O進程）的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。 （2）進程對資源的需求。如進程的估計執(zhí)行時間及內(nèi)存需要量少的進程，應賦予較高的優(yōu)先權(quán)。 （3）根據(jù)用戶要求。這是由用戶進程的緊迫程度及用戶所付費用的多少來確定進程的優(yōu)先權(quán)。

靜態(tài)優(yōu)先權(quán)法簡單易行、系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進程），長期沒有被調(diào)度的情況，因此，僅在要求不太高的系統(tǒng)中，才使用靜態(tài)優(yōu)先權(quán)。4.2.4優(yōu)先權(quán)調(diào)度算法動態(tài)優(yōu)先權(quán)

動態(tài)優(yōu)先權(quán)是指在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，可以隨進程的推進而改變，以便獲得更好的調(diào)度性能。

在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行；進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU。4.2.4優(yōu)先權(quán)調(diào)度算法4.2.5高響應比優(yōu)先調(diào)度算法

在批處理系統(tǒng)中，用以作業(yè)調(diào)度的短作業(yè)優(yōu)先算法是一個比較好的算法。其主要缺點是長作業(yè)的運行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)機制，并使之以速率a增加，則長作業(yè)在等待一定的時間后，必然有機會分配到處理機，即高響應比優(yōu)先

HighestResponseRatioNext(HRRN)(作業(yè))調(diào)度算法，該優(yōu)先權(quán)的變化可描述為： 由于等待時間加上要求服務時間，就是系統(tǒng)對該作業(yè)的響應時間，故該優(yōu)先權(quán)又相當于響應比Rp。據(jù)此，又可表示為: HRRN算法實際上是FCFS算法和STF算法的折衷。4.2.5高響應比優(yōu)先調(diào)度算法

作業(yè)號ABCDE平均到達時間01234運行時間43524完成時間4①7②12③14④18⑤周轉(zhuǎn)時間461011149FCFS帶權(quán)周轉(zhuǎn)時間1225.53.52.8完成時間4①9③18⑤6②13④周轉(zhuǎn)時間4816398SJF帶權(quán)周轉(zhuǎn)時間22.673.21.52.252.1完成時間15③12②18⑤9①17④周轉(zhuǎn)時4RR帶權(quán)周轉(zhuǎn)時間3.753.673.233.253.37完成時間4①7②14④9③18⑤周轉(zhuǎn)時間46126148.4HRRN帶權(quán)周轉(zhuǎn)時間122.433.52.384.2.5高響應比優(yōu)先調(diào)度算法

高響應比優(yōu)先(HRRN)(作業(yè))調(diào)度算法計算：

T=0：只有作業(yè)A已到達，調(diào)度作業(yè)A運行。

T=4：作業(yè)A完成，作業(yè)B、C、D、E已到達，計算作業(yè)B、C、 D、E響應比RP分別為：1+3/3、1+2/5、1+1/2、1+0/4，作業(yè)B響應比最大調(diào)度運行。

T=7：作業(yè)B完成，作業(yè)C、D、E已到達，計算作業(yè)C、D、E響應比RP分別為：1+5/5、1+4/2、1+3/4，作業(yè)D響應比最大調(diào)度運行。

T=9：作業(yè)D完成，作業(yè)C、E已到達，計算作業(yè)C、E響應比RP分別為：1+7/5、1+5/4，作業(yè)C響應比最大調(diào)度運行。

T=14：作業(yè)C完成，只有作業(yè)E未完成，調(diào)度作業(yè)E運行。

4.2.6多級隊列調(diào)度算法

多隊列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將就緒隊列再分為若干個子隊列，所有的作業(yè)（或進程）按其性質(zhì)排入相應的隊列中，而不同的就緒隊列采用不同的調(diào)度算法。 例如前后臺系統(tǒng)可以建立兩個就緒隊列，批處理作業(yè)所建立進程進入后臺就緒隊列；交互型作業(yè)所建立的進程進入前臺就緒隊列。前臺采用時間片輪轉(zhuǎn)算法，進程按FCFS等策略排序，后臺采用優(yōu)先權(quán)高優(yōu)先的調(diào)度算法或者短作業(yè)優(yōu)先的調(diào)度算法。 對多級就緒隊列調(diào)度策略有兩種，一種是各就緒隊列按進程性質(zhì)賦予不同的優(yōu)先權(quán)，優(yōu)先權(quán)高的就緒隊列的進程優(yōu)先被調(diào)度，例如上例中前臺就緒隊列的優(yōu)先權(quán)比后臺就緒隊列的優(yōu)先權(quán)高，所以前臺隊列中的進程優(yōu)先被調(diào)度。而只有當優(yōu)先權(quán)高的就緒隊列空時，方才調(diào)度優(yōu)先權(quán)其次的就緒隊列進程，在上例中只有前臺隊列空時，才調(diào)度后臺就緒隊列。這樣，只有較高優(yōu)先權(quán)的就緒隊列都空時才調(diào)度最低優(yōu)先權(quán)就緒隊列的進程。另一種調(diào)度就緒隊列的方式是為每個隊列分配一定的占用CPU時間的比例。上例中為前臺隊列分配80％的CPU時間，給后臺隊列分配20％的CPU時間。4.2.7多級反饋隊列調(diào)度算法

前面介紹的各種用作進程調(diào)度的算法，都有在一定的局限性，如短進程優(yōu)先算法僅照顧了短進程而怠慢了長進程。況且對進程運行的長短，往往難以正確估計，所以短進程優(yōu)先的調(diào)度算法無法正確使用。 而多級反饋(Feedback)隊列調(diào)度算法，則不必事先知道各種進程所需的執(zhí)行時間，仍能基本滿足短進程優(yōu)先和I/O頻繁的進程優(yōu)先的需要，因而是目前公認的較好的一種進程調(diào)度算法。 在UNIX系統(tǒng)、WindowsNT、OS/2中都采用了類似的調(diào)度算法4.2.7多級反饋隊列調(diào)度算法

調(diào)度算法設(shè)置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低，隊列1的優(yōu)先級最高。每個隊列執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級越低則時間片越長，如逐級加倍。新進程進入內(nèi)存后，先投入隊列1的末尾，按FCFS算法調(diào)度；若按隊列1一個時間片未能執(zhí)行完，則降低投入到隊列2的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊列，則按“時間片輪轉(zhuǎn)”算法調(diào)度直到完成。僅當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。4.2.7多級反饋隊列調(diào)度算法

就緒隊列1時間片S1時間片完時間片完就緒隊列2時間片S2>S1運行運行運行就緒隊列n時間片Sn>Sn-1完成完成完成時間片完阻塞隊列i阻塞阻塞阻塞事件發(fā)生4.3實時系統(tǒng)中的調(diào)度

實時系統(tǒng)是指那些時間因素非常關(guān)鍵的系統(tǒng)。通?？煞譃橛矊崟r系統(tǒng)和軟實時系統(tǒng)。 前者是指系統(tǒng)必須滿足時間的約束。 后者則意味著偶爾超過時間限制也是可以容忍的。

4.3.1對實時系統(tǒng)的要求4.3.2實時調(diào)度算法4.3.1對實時系統(tǒng)的要求提供必要的調(diào)度信息

如，就緒時間、開始或完成截止時間、處理時間、資源要求、絕對或相對優(yōu)先級（硬實時或軟實時）。調(diào)度方式 采用搶先式調(diào)度?？焖僦袛囗憫?在中斷處理時（硬件）關(guān)中斷的時間盡量短。快速上下文切換 相應地采用較小的調(diào)度單位（如線程）。4.3.2實時調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法非搶占優(yōu)先級調(diào)度算法基于時鐘中斷搶占的優(yōu)先級調(diào)度算法立即搶占的優(yōu)先級調(diào)度算法4.4多處理機調(diào)度

4.4.1與單處理機調(diào)度的區(qū)別4.4.2對稱式多處理系統(tǒng)(SMP)4.4.3非對稱式多處理系統(tǒng)(ASMP)的處理機調(diào) 度4.4.4成組調(diào)度(GangScheduling)4.4.5專用處理機調(diào)度(DedicatedProcessor Assignment)4.4.1與單處理機調(diào)度的區(qū)別注重整體運行效率（而不是個別處理機的利用率）更多樣的調(diào)度算法多處理機訪問OS數(shù)據(jù)結(jié)構(gòu)時的互斥（對于共享內(nèi)存系統(tǒng)）調(diào)度單位廣泛采用線程4.4.2對稱式多處理系統(tǒng)(SMP)

按控制方式，SMP調(diào)度算法可分為集中控制和分散控制。下面所述靜態(tài)和動態(tài)調(diào)度都是集中控制，而自調(diào)度是分散控制。靜態(tài)分配(staticassignment)：每個CPU設(shè)立一個就緒隊列，進程從開始執(zhí)行到完成，都在同一個CPU上。優(yōu)點：調(diào)度算法開銷小。缺點：容易出現(xiàn)忙閑不均。動態(tài)分配(dynamicassignment)：各個CPU采用一個公共就緒隊列，隊首進程每次分派到當前空閑的CPU上執(zhí)行。分散控制

自調(diào)度(self-scheduling)：各個CPU采用一個公共就緒隊列，每個處理機都可以從隊列中選擇適當進程來執(zhí)行。需要對就緒隊列的數(shù)據(jù)結(jié)構(gòu)進行互斥訪問控制。是最常用的算法，實現(xiàn)時易于移植采用單處理機的調(diào)度技術(shù)。4.4.3非對稱式多處理系統(tǒng)(ASMP)主－從處理機系統(tǒng)，由主處理機管理一個公共就緒隊列，并分派進程給從處理機執(zhí)行。各個處理機有固定分工，如執(zhí)行OS的系統(tǒng)功能，I/O處理，應用程序。4.4.4成組調(diào)度(gangscheduling)

將一個進程中的一組線程，每次分派時同時到一組處理機上執(zhí)行，在剝奪處理機時也同時對這一組線程進行。優(yōu)點:通常這樣的一組線程在應用邏輯上相互合作，成組調(diào)度提高了這些線程的執(zhí)行并行度，有利于減少阻塞和加快推進速度，最終提高系統(tǒng)吞吐量。每次調(diào)度可以完成多個線程的分派，在系統(tǒng)內(nèi)線程總數(shù)相同時能夠減少調(diào)度次數(shù)，從而減少調(diào)度算法的開銷4.4.5 專用處理機調(diào)度

(dedicatedprocessorassignment)

為進程中的每個線程都固定分配一個CPU，直到該線程執(zhí)行完成。缺點：線程阻塞時，造成CPU的閑置。優(yōu)點：線程執(zhí)行時不需切換，相應的開銷可以大大減小，推進速度更快。適用場合：CPU數(shù)量眾多的高度并行系統(tǒng)，單個CPU利用率已不太重要。4.5調(diào)度算法舉例4.5.1傳統(tǒng)UNIX的進程調(diào)度4.5.2Windows2000的進程調(diào)度4.5.1傳統(tǒng)UNIX的進程調(diào)度

未設(shè)置作業(yè)調(diào)度，進程調(diào)度采用基于時間片的多級反饋隊列算法，進程優(yōu)先級分為核心優(yōu)先級和用戶優(yōu)先級。調(diào)度時機調(diào)度由0號進程完成（始終在核心態(tài)執(zhí)行，與其他進程并不完全一樣）。時機：進程由核心態(tài)轉(zhuǎn)入用戶態(tài)時：在每次執(zhí)行核心代碼之后返回用戶態(tài)之前，檢查各就緒進程的優(yōu)先級并進行調(diào)度。如中斷――進程回到就緒隊列進程主動放棄處理機時：進程申請系統(tǒng)資源而未得到滿足（如read），或進行進程間同步而暫停（如wait或pause），進程退出（如exit）――進程進入阻塞隊列或exit狀態(tài)。4.5.1傳統(tǒng)UNIX的進程調(diào)度調(diào)度標志

UNIXSystemV中有三個與調(diào)度有關(guān)的標志：runrun

表示要求進行調(diào)度，當發(fā)現(xiàn)有就緒進程優(yōu)先級高于當前進程時，設(shè)置該標識。在wakeup,setrun,setpri（設(shè)置優(yōu)先級）過程和時鐘中斷處理例程進行設(shè)置。runin

表示內(nèi)存中沒有適當?shù)倪M程可以換出或內(nèi)存無足夠空間（內(nèi)存緊張）runout

表示外存交換區(qū)中沒有適當?shù)倪M程可以換入。（交換區(qū)緊張）4.5.1傳統(tǒng)UNIX的進程調(diào)度用戶優(yōu)先級 進程在用戶態(tài)和核心態(tài)的優(yōu)先級是不同的，這里說的是用戶態(tài)進程的優(yōu)先級。它是基于執(zhí)行時間的動態(tài)優(yōu)先級，進程優(yōu)先級可為0~127之間的任一整數(shù)。優(yōu)先數(shù)越大，優(yōu)先級越低。0~49之間的優(yōu)先級為系統(tǒng)內(nèi)核保留用戶態(tài)下的進程優(yōu)先級為50~127之間

4.5.1傳統(tǒng)UNIX的進程調(diào)度 在UNIXSystemV中，進程優(yōu)先數(shù)：

P_pri=P_CPU/2+PUSER+P_nice+NZERO系統(tǒng)設(shè)置部分：PUSER和NZERO是基本用戶優(yōu)先數(shù)的閾值，分別為25和20CPU使用時間部分：P_CPU表示該進程最近一次CPU使用時間。每次時鐘中斷則該值加1（最多可達80）。如果時鐘中斷的周期為16.6ms，則每秒鐘過后將該值為60。新創(chuàng)建進程的P_CPU值為0，因而具有較高的優(yōu)先級。不同系統(tǒng)對P_CPU的計算方法有所不同。有的固定一個因子，有的會考慮系統(tǒng)負荷。用戶設(shè)置部分：P_nice是用戶可以通過系統(tǒng)調(diào)用設(shè)置的一個優(yōu)先級偏移值。默認為20。超級用戶可以設(shè)置其在0到39之間，而普通用戶只能增大該值（即降低優(yōu)先級）。4.5.1傳統(tǒng)UNIX的進程調(diào)度

核心優(yōu)先級內(nèi)核把進程阻塞事件與一個睡眠優(yōu)先級（0~49）聯(lián)系起來；當進程從阻塞中醒來時，可及時進行處理。如：磁盤I/O操作對應的睡眠優(yōu)先級為20終端輸入操作對應的睡眠優(yōu)先級為29。核心優(yōu)先級分為可中斷和不可中斷兩類優(yōu)先級。當一個軟中斷信號到達時，若進程正在可中斷優(yōu)先級上阻塞，則進程立即被喚醒；若正在不可中斷優(yōu)先級上，則繼續(xù)阻塞。其中：不可中斷優(yōu)先級：對換，等待磁盤I/O，等待緩沖區(qū)，等待文件索引結(jié)點－－關(guān)鍵操作，應該很快完成可中斷優(yōu)先級：等待tty（虛終端）I/O，等待子進程退出4.5.1傳統(tǒng)UNIX的進程調(diào)度

調(diào)度的實現(xiàn)：分三個階段檢查是否作上下文切換（runrun標志）和核心是否允許作上下文切換（對核心的各種數(shù)據(jù)結(jié)構(gòu)的操作都已經(jīng)完成，核心處于正確的狀態(tài)）。如果允許作上下文切換，則保存當前進程的上下文。恢復0號進程的上下文，然后執(zhí)行0號進程，尋找最高優(yōu)先級的就緒進程，如果沒有這樣的進程存在，則執(zhí)行idle過程。如果有這樣的進程存在，則該進程作為當前進程分派處理機，保存0號進程的上下文?；謴彤斍斑M程的上下文，執(zhí)行該進程。4.5.2Windows2000的進程調(diào)度

Windows2000的線程調(diào)度概述

調(diào)度單位是線程而不是進程，采用嚴格的搶先式動態(tài)優(yōu)先級調(diào)度，依據(jù)優(yōu)先級和分配時間片來調(diào)度。每個優(yōu)先級的就緒線程排成一個先進先出隊列；當一個線程狀態(tài)變成就緒時，它可能立即運行或排到相應優(yōu)先級隊列的尾部?？傔\行優(yōu)先級最高的就緒線程；4.5.2Windows2000的進程調(diào)度完全的事件驅(qū)動機制，在被搶先前沒有保證的運行時間沒有形式的調(diào)度循環(huán)；時間片用完事件；等待結(jié)束事件；主動掛起事件；在同一優(yōu)先級的各線程按時間片輪轉(zhuǎn)算法進行調(diào)度；在多處理機系統(tǒng)中多個線程并行運行；4.5.2Windows2000的進程調(diào)度Windows2000的中斷優(yōu)先級4.5.2Windows2000的進程調(diào)度NT線程的優(yōu)先級

從0到31，數(shù)值越大，優(yōu)先級越高。分為兩類實時(real-time)：從16到31，如設(shè)備監(jiān)控線程。可變優(yōu)先級(variable-priority)：從1到15（級別0保留為系統(tǒng)使用）。線程的基本優(yōu)先級=[進程的基本優(yōu)先級-2，進程的基本優(yōu)先級+2]，由應用程序控制線程的動態(tài)優(yōu)先級=[進程的基本優(yōu)先級-2,31]，由NT核心控制4.5.2Windows2000的進程調(diào)度NT的線程優(yōu)先級（BasePriority）由進程優(yōu)先級類（PriorityClass）和線程優(yōu)先級偏移（PriorityLevel）構(gòu)成，分別由相關(guān)函數(shù)控制。4.5.2Windows2000的進程調(diào)度進程優(yōu)先級類4.5.2Windows2000的進程調(diào)度線程優(yōu)先級偏移4.5.2Windows2000的進程調(diào)度4.5.2Windows2000的進程調(diào)度與線程優(yōu)先級控制有關(guān)的API進程優(yōu)先級類函數(shù)：GetPriorityClass（讀取）SetPriorityClass（設(shè)置）線程優(yōu)先級偏移：GetThreadPriority（讀?。㏒etThreadPriority（設(shè)置）4.5.2Windows2000的進程調(diào)度線程調(diào)度數(shù)據(jù)結(jié)構(gòu)

4.5.2Windows2000的進程調(diào)度就緒位圖(KiReadySummary)

為了提高調(diào)度速度，Windows2000維護了一個稱為就緒位圖(KiReadySummary)的32位量。就緒位圖中的每一位指示一個調(diào)度優(yōu)先級的就緒隊列中是否有線程等待運行。B0與調(diào)度優(yōu)先級0相對應，B1與調(diào)度優(yōu)先級1相對應，等待。空閑位圖(KiIdleSummary) Windows2000還維護一個稱為空閑位圖(KiIdleSummary)的32位量?？臻e位圖中的每一位指示一個處理機是否處于空閑狀態(tài)。調(diào)度器自旋鎖(KiDispatcherLock)

為了防止調(diào)度器代碼與線程在訪問調(diào)度器數(shù)據(jù)結(jié)構(gòu)時發(fā)生沖突，處理機調(diào)度僅出現(xiàn)在DPC/調(diào)度層次。但在多處理機系統(tǒng)中，修改調(diào)度器數(shù)據(jù)結(jié)構(gòu)需要額外的步驟來得到內(nèi)核調(diào)度器自旋鎖(KiDispatcherLock)，以協(xié)調(diào)各處理機對調(diào)度器數(shù)據(jù)結(jié)構(gòu)的訪問。4.5.2Windows2000的進程調(diào)度與線程調(diào)度相關(guān)的內(nèi)核變量。4.5.2Windows2000的進程調(diào)度Windows2000中的start命令

可指定進程啟動時的優(yōu)先級；

start/highmyprog4.6死鎖的基本概念4.6死鎖的基本概念 所謂死鎖（Deadlock），是指多個進程因競爭資源造成的一種僵局（Deadly－Embrace），若無外力作用，這些進程都將永遠不能再向前推進。4.6.1產(chǎn)生死鎖的原因4.6.2產(chǎn)生死鎖的必要條件4.6.3處理死鎖的基本方法

4.6.1

產(chǎn)生死鎖的原因競爭資源引起死鎖可剝奪和非剝奪性資源 在多道程序系統(tǒng)，多個進程共享系統(tǒng)的資源。系統(tǒng)資源分為二類一類是不可搶占的資源，如打印機、磁帶機等。當系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自動釋放。另一類是可搶占的資源，如CPU、內(nèi)存等。由于系統(tǒng)擁有的不可搶占的資源有限，多個進程共享競爭不可搶占的資源就可能引起死鎖。4.6.1

產(chǎn)生死鎖的原因競爭非剝奪性資源

死鎖發(fā)生：雙方都擁有部分資源，同時在請求對方已占有的資源。如次序：P1<a>P2<a>P1<b>P2<b>P1BAP24.6.1

產(chǎn)生死鎖的原因競爭臨時性資源永久性資源：可順序重復使用的資源，又稱可重用資源；臨時性資源：由一個進程產(chǎn)生，被另一個進程使用一個短暫時間后便無用的資源，又稱消耗性資源。P1:Send(S1);Receive(S3); P2:Send(S2);Receive(S1); P3:Send(S3);Receive(S2);

不可能發(fā)生死鎖P1:Receive(S3);Send(S1); P2:Receive(S1);Send(S2); P3:Receive(S2);Send(S3);

可能產(chǎn)生死鎖S2S3P2S1P1P34.6.1

產(chǎn)生死鎖的原因進程推進順序不恰當

P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)死鎖點危險區(qū)4.6.1

產(chǎn)生死鎖的原因4.6.2產(chǎn)生死鎖的必要條件互斥（Mutualexclusion

）條件 一個資源一次只能被一個進程所使用，即是排它性使用，當有進程在使用某個資源時，其他想使用該資源的進程必須等待，直到使用資源者歸還資源后才允許另一進程使用該資源請求和保持（Hold-and-wait

）條件 進程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對已經(jīng)獲得的其它資源保持不放。4.6.2產(chǎn)生死鎖的必要條件不可搶占（Nopreemption

）條件 一個資源僅能被占有它的進程所釋放，而不能被別的進程搶占。環(huán)路等待（Circularwait

）條件

存在一組進程P1，P2，…，Pn，其中每一個進程都在等待另一個進程占用的資源，即p1等待p2占用的資源，P2等待P3占用的資源，…，P（n-1）等待Pn占用的資源，而Pn又等待P1所占用的資源。4.6.3處理死鎖的基本方法死鎖的預防靜態(tài)方法：在進程執(zhí)行前采取的措施，通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件之一，防止發(fā)生死鎖死鎖的避免動態(tài)的方法：在進程執(zhí)行過程中采取的措施，不需事先采取限制措施破壞產(chǎn)生死鎖的必要條件，而是在進程申請資源時用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖。死鎖的檢測和解除這種方法預先并不采用任何限制措施，允許系統(tǒng)在運行過程中發(fā)生死鎖，但可通過系統(tǒng)設(shè)置的檢測機構(gòu)及時檢測死鎖的發(fā)生，如檢測到死鎖，則采用撤消進程等死鎖解除方法使系統(tǒng)正常工作。4.6.3處理死鎖的基本方法4.7死鎖的預防與避免4.7.1死鎖的預防4.7.2系統(tǒng)的安全狀態(tài)4.7.3利用銀行家算法避免死鎖

4.7.1死鎖的預防擯棄“互斥”條件

只有允許進程共享使用設(shè)備才能使互斥使用資源條件不成立，而計算機系統(tǒng)中大多數(shù)資源必須互斥使用，所以無法使互斥條件不成立而防止死鎖，相反還必須嚴格遵守互斥使用資源的要求。 擯棄“請求和保持”條件 系統(tǒng)可采用資源靜態(tài)預分配方式來破壞請求保持條件。系統(tǒng)要求所有進程一次性地申請在整個運行過程中全部資源，若系統(tǒng)有足夠資源滿足給進程，則在運行前，一次性將其所需要的所有資源分配給該進程。這樣該進程在整個運行期間，便不再提出資源要求，從而摒棄了請求條件。這種預防死鎖的方法，優(yōu)點是簡單、易予實現(xiàn)且很安全，但其資源利用率很低，進程也延遲運行。4.7.1

死鎖的預防擯棄“不剝奪”條件 采用搶奪式分配資源法：如果一個進程已經(jīng)占有了某些資源又要申請新資源，而新資源不能滿足必須等待時，系統(tǒng)可以搶奪該進程已占有的資源。

搶占式調(diào)度法主要用于處理機和存貯器資源調(diào)度，它們的狀態(tài)容易保存和恢復。但此法對外部設(shè)備和私存數(shù)據(jù)不宜使用。P1占有R1，P2在申請R1時，P1不釋放，產(chǎn)生死鎖；破壞不可剝奪條件，系統(tǒng)強行剝奪R1---P2，P1以后執(zhí)行時，需退回申請R1之前，造成P1執(zhí)行產(chǎn)生死尸。

實現(xiàn)復雜，延長進程的周轉(zhuǎn)時間，還增加系統(tǒng)的開銷，降低系統(tǒng)吞吐量4.7.1

死鎖的預防擯棄“環(huán)路等待”條件 采用按序分配資源法：具體做法是把系統(tǒng)中所有資源排一個順序，對每一個資源確定編號，規(guī)定任何一個進程申請兩個以上的資源時，總是先申請編號最小的資源，再申請編號大的資源。 例如，系統(tǒng)共有m個資源，假定編號為1，2…，m，于是這m個資源是

r1，r2，……rm

任何一個過程在得到了資源ri之后，若再申請資源rj，則必定是i＜j。可以證明按這種策略分配資源時不會出現(xiàn)循環(huán)等待資源的情況。 這種預防死鎖的策略可以提高資源利用率，但在進程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時會造成資源浪費的情況。4.7.2系統(tǒng)的安全狀態(tài) 該方法允許進程動態(tài)地申請資源，系統(tǒng)在進行資源分配之前，先計算資源分配的安全性。若此次分配不會導致系統(tǒng)從安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換，便可將資源分配給進程；否則不分配資源，進程必須阻塞等待。從而避免發(fā)生死鎖。安全狀態(tài)

安全狀態(tài)是指系統(tǒng)的一種狀態(tài)，在此狀態(tài)下系統(tǒng)能按某種順序（例如P1、P2……Pn）來為各個進程分配其所需資源，直至最大需求，使每個進程都可順序地一個個地完成。這個序列（P1、P2…….Pn）稱為安全序列。若系統(tǒng)此狀態(tài)不存在一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)4.7.2系統(tǒng)的安全狀態(tài)安全狀態(tài)之例（12臺打印機）

進程 最大需求已分配還需請求可用

P1 10 5 5 3 P2 4 2 2 P3 9 2 7

分析T0狀態(tài)，可以找到一個安全序列（P2、P1、P3）,即系統(tǒng)按此進程序列分配資源，每個進程都可順利完成，其步驟如下：先將可用的3臺磁帶機中2臺分配給P2，P2滿足了最大的資源需求，在有限時間內(nèi)運行完畢，釋放它占有的全部資源，使可用資源數(shù)量增至5臺。再將可用的5臺磁帶機分配給P1，最后將可用10臺中7臺磁帶機分配給P3。

這樣三進程可按照（P2、P1、P3）序列順序地一個個執(zhí)行完成，則（P2、P1、P3）序列是安全序列，T0時刻狀態(tài)也是安全狀態(tài)。4.7.2系統(tǒng)的安全狀態(tài)由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果在T0

狀態(tài)不按安全序列進行分配，可能會導致系統(tǒng)進入一個不安全狀態(tài)，例如在T0狀態(tài)下P3中申請1臺磁帶機。如系統(tǒng)實施此次分配使系統(tǒng)狀態(tài)由T0變?yōu)門1狀態(tài)，分析T1狀態(tài)安全情況。進程最大需求已分配還需請求可用可用

分配資源前釋放資源后P1105 5

> 4 P24 22=< 2 4P39 36> 4

因為找不到一個安全序列使所有進程順序地一個個地運行完畢，所以T1狀態(tài)是不安全狀態(tài)，由于實施分配給1臺磁帶機給P3的操作會引起系統(tǒng)狀態(tài)由安全狀態(tài)T0向不安全狀態(tài)下的轉(zhuǎn)換，所以為了避免死鎖，上述的分配只是安全檢測，檢測后判定這樣的申請不能滿足，P3為申請1臺磁帶機而必須阻塞等待。4.7.3利用銀行家算法避免死鎖 最具代表的避免死鎖算法是銀行家算法，這是由于該算法用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。

銀行家的規(guī)定一個用戶對資金的最大需求量不超過其現(xiàn)有資金，可接納分期貸款，總數(shù)不超過最大需求量；不滿足時，可推遲支付，但在有限時間內(nèi)得到；用戶得到所需全部資金時，一定能在有限時間里全部歸還。4.7.3利用銀行家算法避免死鎖銀行家算法的數(shù)據(jù)結(jié)構(gòu)可用資源向量Available[m]m為系統(tǒng)中資源種類數(shù)，Available[j]=k表示系統(tǒng)中第j類資源的可用數(shù)為k個。最大需求矩陣Max[n，m]n為系統(tǒng)中進程數(shù)，Max[i,j]=k表示進程i對j類資源的最大需求數(shù)為k個。分配矩陣Allocation[n，m]

它定義了系統(tǒng)中每一類資源當前已分配給每一進程資源數(shù)，Allocation[i,j]=k表示進程i已分得j類資源的數(shù)目為k個。需求矩陣Need[n,m]

它表示每個進程尚需的各類資源數(shù)，Need[i,j]=k表示進程i還需要j類資源k個。 Need[i,j]=Max[i,j]-Allocation[i,j]4.7.3利用銀行家算法避免死鎖銀行家算法假設(shè)在進程并發(fā)執(zhí)行時進程i提出請求j類資源k個后，表示為Requesti[j]=k。系統(tǒng)按下述步驟進行安全檢查：如果Requesti≤Needi則繼續(xù)以下檢查，否則顯示需求申請超出最大需求值的錯誤。如果Requesti≤Available則繼續(xù)以下檢查，否則顯示系統(tǒng)無足夠資源，Pi阻塞等待。系統(tǒng)試探把要求的資源分配給進程i并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的值：

Available:=Available-Requesti

；

Allocationi:=Allocationi+Requesti；

Needi:=Needi-Requesti

；系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全 狀態(tài)，若安全，才正式將資源分配給進程i，以完成本次分配；否則將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。4.7.3利用銀行家算法避免死鎖安全性算法

安全性算法執(zhí)行步驟如下：初始化設(shè)置工作向量Work[m]表示系統(tǒng)可提供的各類資源數(shù)目，用以保護原數(shù)據(jù)結(jié)構(gòu)有關(guān)值。Work=Available，設(shè)置完成標志向量Finish[n]。Finish[i]=false表示i進程尚末完成，如值為true則表示進程i已完成。從進程集合n中找到一個能滿足下述兩個條件的進程: Finish[i]=false

Necdi≤Work， 如找到，執(zhí)行步驟3，否則執(zhí)行步驟4。當進程i獲得資源后可順利執(zhí)行直到完成，并釋放出分配給它的資源，表示如下：

work=work+Allocationi

；Finish[i]=true；轉(zhuǎn)執(zhí)行步驟2。如果所有進程的Finish[i]＝ture，則表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。4.7.3利用銀行家算法避免死鎖銀行家算法之例 假定系統(tǒng)中有五個進程{P0、P1、P2、P3、P4}和三種類型資源{A、B、C}，每一種資源的數(shù)量分別為10、5、7。各進程的最大需求、T0時刻資源分配情況如下所示。資源進情況程MaxABCAllocationABCNeedABCAvailableABCP052010743332P1322200122P2902302600P3222211011P44330024314.7.3利用銀行家算法避免死鎖T0時刻是否安全

從表中可找出一個安全序列(P1、

P3、P4、

P0、

P2)，因此系統(tǒng)是安全的。資源進情況程WorkABCNeedABCAllocationABCWork+AllocationABCFinishABCP1332122200532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057true4.7.3利用銀行家算法避免死鎖P1請求資源

P1發(fā)出請求向量Request1(1,0,2)，系統(tǒng)按照銀行家算法進行檢查。Request1(1,0,2)≤Need1(1,2,2)，P1請求在最大需求范圍內(nèi)。Request1(1,0,2)≤Available(3,3,2)，可用資源滿足P1請求需要。試探把要求的資源分配給進程P1并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的數(shù)值： Available(3，3，2)－Request1(1,0,2)=Available(2,3,0)； Need1(1,2,2)－Request1(1,0,2)=Need1(0,2,0)； Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；4.7.3利用銀行家算法避免死鎖資源進情況程MaxABCAllocationABCNeedABCAvailableABCP052010743332(230)P1322200(302)122(020)P2902302600P3222211011P44330024314.7.3利用銀行家算法避免死鎖利用安全性算法檢查試探將資源分配后狀態(tài)的安全性如下：存在一個安全序列{P1、P3、P4、P2、P0}

，所以試探將資源分配給進程P1后的狀態(tài)是安全的，可將資源分配給進程P1。資源進情況程WorkABCNeedABCAllocationABCWork+AllocationABCFinishABCP1230020302532trueP3532011211743trueP4743431002745trueP0745743010755trueP27556003021057true4.7.3利用銀行家算法避免死鎖P4請求資源

P4發(fā)出請求向量Request4(3,3,0)，系統(tǒng)按照銀行家算法進行檢查。Request4(3,3,0)≤Need1(4,3,1)，P4請求在最大需求范圍內(nèi)。Request4(3,3,0)≤Available(2,3,0)不成立，可用資源暫不能滿足P4請求資源需要，P4阻塞等待。4.7.3利用銀行家算法避免死鎖P0請求資源

P0發(fā)出請求向量Request0(0,2,0)，系統(tǒng)按照銀行家算法進行檢查。Request0(0,2,0)≤Need1(7,4,3)，P0請求在最大需求范圍內(nèi)。Request0(0,2,0)≤Available(2,3,0)，可用資源能滿足P0請求資源需要。試探把要求的資源分配給進程P0并修改有關(guān)數(shù)據(jù)結(jié)構(gòu)的數(shù)值： Available(2，3，0)－Request0(0,2,0)=Available(2,1,0)； Need0(7,4,3)－Request0(0,2,0)=Need0(7,2,3)； Allocation0(0,1,0)+Request0(0,2,0)=Allocation0(0,3,0)；4.7.3利用銀行家算法避免死鎖安全性算法檢查

可用資源Available(2,1,0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。資源進情況程MaxABCAllocationABCNeedABCAvailableABCP052010(030)43(7

23)230(210)P1322302020P2902302600P3222211011P44330024314.8死鎖的檢測與解除4.8.1死鎖的檢測4.8.2死鎖的解除

4.8.1死鎖的檢測 死鎖的檢測采用資源分配圖的簡化判斷是否發(fā)生了不安全狀態(tài)。資源分配圖（ResourceAllocationGraph）

資源分配圖是一個二元組Ｇ＝＜N，E＞

其中，N又可分為進程節(jié)點P={Pi|i=1，…，n｝和資源節(jié)點R={Rj|j=1，…，m}，而且N=P∪R，P∩R=￠（即P和R是N的一個劃分）；

E={<Pi，Ri>|i=1，…，n；j=1，…，m｝

是連接P和R中節(jié)點的有向邊集合，而且〈Pi，Rj〉表示進程Pi申請資源Rj；<Rj，Pi>表示資源Rj已經(jīng)分配給了進程Pi。P1P2r1r24.8.1死鎖的檢測死鎖定理

S為死鎖狀態(tài)的充分條件是：當且僅當S狀態(tài)的資源分配圖是不可完全簡化的，該充分條件稱為死鎖定理。 資源分配圖簡化的方法如下：在資源分配圖中找一個既不阻塞又非孤立的進程結(jié)點Pi（如某進程既無已分配的資源也不需申請資源，即既無分配邊又無申請邊，則該進程結(jié)點是孤立結(jié)點）讓它獲得所需資源而繼續(xù)運行直至完畢，再釋放它擁有的所有的資源，這相當于取消Pi的分配邊和請求邊，使它成為孤立結(jié)點。經(jīng)過以上簡化，如所有的進程結(jié)點都是孤立結(jié)點則稱資源分配圖是可完全簡化的。若不能通過任何過程使該圖完全簡化，則該圖是不可完全簡化的。4.8.1死鎖的檢測

P1P2P1P2P1P2P1P24.8.1死鎖的檢測

4.8.1死鎖的檢測死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)

類似于銀行家算法的數(shù)據(jù)結(jié)構(gòu)：可利用資源向量Available,表示m類資源中每一類資源的可用數(shù)目。把孤立結(jié)點Allocation=0∩Requesti=0加入表L中，即Li∪L。從進程集合中找到一個Requeati≤Work的進程，做如下處理：將其資源分配圖簡化，釋放出資源，增加工作向量 Work:=Work+Allocationi

；將它加入表L中。若不能把所有進程都加入表L中，表明系統(tǒng)狀態(tài)S的資源分配圖是不可完全簡化的，因此，該系統(tǒng)將發(fā)生死鎖。4.8.1死鎖的檢測

Work:=Available; L:={Li|Allocationi=0∩Requesti=0} ForallLinot∈Ldo begin forallRequesti≤Workdo begin Work:=Work+Allocationi

；

Li∪L; end end deadlock:=┑(L={P1,P1,…,Pn});4.8.2死鎖的解除剝奪資源

從被掛起的進程那里搶占資源剝奪足夠的資源給死鎖進程，以解除死鎖狀態(tài)。撤銷進程最簡單的撤銷進程的方法，是使全部死鎖進程都夭折 掉；按照某種順