1、Page Chapter3 處理機(jī)調(diào)度與死鎖Chapter3 處理機(jī)調(diào)度與死鎖? 3.1 處理機(jī)調(diào)度的基本概念? 3.2 調(diào)度算法? 3.3 實(shí)時(shí)調(diào)度? 3.4 產(chǎn)生死鎖的原因和必要條件? 3.5 預(yù)防死鎖的方法? 3.6 死鎖的監(jiān)測(cè)與解除Page Chapter3 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的基本概念 在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后，必須經(jīng)過處理機(jī)調(diào)度后，方能因獲得處理機(jī)而執(zhí)行。 對(duì)于批量型作業(yè)批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度作業(yè)調(diào)度（高級(jí)調(diào)度）和進(jìn)程調(diào)度進(jìn)程調(diào)度（低級(jí)調(diào)度）兩個(gè)過程后，方能獲得處理機(jī)。 對(duì)于終端型作業(yè)終端型作業(yè)，則通常只須經(jīng)過進(jìn)程調(diào)度。在較完善的操作系統(tǒng)中，

2、往往還設(shè)置了中級(jí)調(diào)度中級(jí)調(diào)度。對(duì)于上述的每一級(jí)調(diào)度，又都可采用不同的調(diào)度方式和調(diào)度算法。本節(jié)主要是對(duì)處理機(jī)調(diào)度的基本概念做較詳細(xì)的闡述。Page Chapter3 處理機(jī)調(diào)度與死鎖3.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)調(diào)度高級(jí)調(diào)度又稱為作業(yè)調(diào)度或長程調(diào)度(Long-Term scheduling),用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，是先駐留在外存上的，因此需要有作業(yè)調(diào)度的過程，以便將它們分批地裝入內(nèi)存。 在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，通常不需要作業(yè)調(diào)度。Page Chapt

3、er3 處理機(jī)調(diào)度與死鎖高級(jí)調(diào)度(續(xù)) 高級(jí)調(diào)度高級(jí)調(diào)度( (續(xù)續(xù)) )在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定。 接納多少個(gè)作業(yè)作業(yè)調(diào)度每次要接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度。即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。 數(shù)目太多時(shí)，可能會(huì)影響到系統(tǒng)的服務(wù)質(zhì)量，比如，使周轉(zhuǎn)時(shí)間太長。 數(shù)量太少時(shí)，又會(huì)導(dǎo)致系統(tǒng)的資源利用率和系統(tǒng)吞吐量太低， 接納哪些作業(yè)應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，將取決于所采用的調(diào)度算法。Page Chapter3 處理機(jī)調(diào)度與死鎖低級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度 用來決定就緒隊(duì)列中就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。 進(jìn)程調(diào)度方式是

4、指當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要進(jìn)行處理，即有優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列，此時(shí)應(yīng)如何分配處理機(jī)。 進(jìn)程調(diào)度是最基本最基本的一種調(diào)度，在三種類型的OS中，都必須配置這級(jí)調(diào)度。 Page Chapter3 處理機(jī)調(diào)度與死鎖低級(jí)調(diào)度(續(xù)) 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)） - - 兩種調(diào)度方式 非搶占方式 指當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，仍然讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程。非剝奪方式又稱非搶占方式、不可剝奪方式。Page Chapter3 處理

5、機(jī)調(diào)度與死鎖低級(jí)調(diào)度(續(xù)2)引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個(gè)： 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行； 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如wait操作（P操作）、Block原語、Wakeup原語等。 特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。 但它難以滿足緊急任務(wù)的要求。Page Chapter3 處理機(jī)調(diào)度與死鎖低級(jí)調(diào)度（續(xù)3） 低級(jí)調(diào)度低級(jí)調(diào)度 - - 兩種調(diào)度方式 搶占方式搶占方式 指當(dāng)一個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要使用處理機(jī)，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)

6、更重要或緊迫的進(jìn)程。剝奪方式又稱搶占方式、可剝奪方式。Page Chapter3 處理機(jī)調(diào)度與死鎖低級(jí)調(diào)度（續(xù)4） 搶占的原則搶占的原則： 優(yōu)先權(quán)原則 當(dāng)高優(yōu)先權(quán)作業(yè)到達(dá)時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行進(jìn)程的優(yōu)先權(quán)高，便停止正在執(zhí)行（當(dāng)前）的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程，使之執(zhí)行。 短作業(yè)（進(jìn)程）優(yōu)先原則 當(dāng)新到達(dá)的作業(yè)（進(jìn)程）比正在執(zhí)行的作業(yè)（進(jìn)程）明顯短時(shí)，將暫停當(dāng)前長作業(yè)（進(jìn)程）的執(zhí)行，將處理機(jī)分配給新到的短作業(yè)（進(jìn)程），使之優(yōu)先執(zhí)行。 時(shí)間片原則 各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這種原則適用于分時(shí)系統(tǒng)、大多數(shù)的實(shí)時(shí)系統(tǒng)，以及要求較高的批處理系統(tǒng)

7、。Page Chapter3 處理機(jī)調(diào)度與死鎖中級(jí)調(diào)度 中級(jí)調(diào)度中級(jí)調(diào)度引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存利提高內(nèi)存利用率用率和系統(tǒng)吞吐量系統(tǒng)吞吐量。應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來決定把外存上的哪些進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上是存儲(chǔ)器管理中的對(duì)換功能。Page Chapter3 處理機(jī)調(diào)度與死鎖三種調(diào)度總結(jié) 三種調(diào)度總結(jié)總結(jié) 進(jìn)程調(diào)度的運(yùn)行頻率最高，分時(shí)系統(tǒng)中通常是10-100ms

8、進(jìn)行一次進(jìn)程調(diào)度，因而進(jìn)程調(diào)度算法不能太復(fù)雜，以免占用太多的CPU時(shí)間。 作業(yè)調(diào)度往往是發(fā)生在一個(gè)（批）作業(yè)運(yùn)行完畢，退出系統(tǒng)，而需要重新調(diào)入一個(gè)（批）作業(yè)進(jìn)入內(nèi)存時(shí)，故作業(yè)調(diào)度的周期較長，大約幾分鐘一次。因而也允許作業(yè)調(diào)度算法花費(fèi)較多的時(shí)間。 中級(jí)調(diào)度的運(yùn)行頻率，基本上介于上述兩種調(diào)度之間。Page Chapter3 處理機(jī)調(diào)度與死鎖3.1.2 調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 在分時(shí)系統(tǒng)中，通常僅設(shè)置了進(jìn)程調(diào)度，用戶鍵入的命令和數(shù)據(jù)，都直接送入內(nèi)存對(duì)于命令，是由OS為之建立一個(gè)進(jìn)程。系統(tǒng)可以把處于就緒狀態(tài)的進(jìn)程組織成棧、樹或一個(gè)無序鏈表，至于到底采用其中哪種形式，則與OS類型和所采用

9、的調(diào)度算法有關(guān)。 Page Chapter3 處理機(jī)調(diào)度與死鎖具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還需有作業(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)程。 就緒隊(duì)列的形式。最常用的就緒隊(duì)列形式是優(yōu)先權(quán)隊(duì)列。 設(shè)置多個(gè)阻塞隊(duì)列。在大、中型系統(tǒng)中，通常都設(shè)置了若干個(gè)阻塞隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)于某一種進(jìn)程阻塞事件。Page Chapter3 處理機(jī)調(diào)度與死鎖同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 當(dāng)在OS中引入中級(jí)調(diào)度后，人們可把進(jìn)程的就緒狀態(tài)

10、分為內(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)變?yōu)橥獯婢途w，由內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞谥屑?jí)調(diào)度的作用下，又可使外存就緒轉(zhuǎn)變?yōu)閮?nèi)存就緒。Page Chapter3 處理機(jī)調(diào)度與死鎖3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 - - 為了滿足用戶需求。 周轉(zhuǎn)周期短；（常用來評(píng)價(jià)批處理系統(tǒng)） 響應(yīng)時(shí)間快；（常用來評(píng)價(jià)分時(shí)系統(tǒng)） 截止時(shí)間的保證；（常用來評(píng)價(jià)實(shí)時(shí)系統(tǒng)） 先后權(quán)準(zhǔn)則；（批處理、實(shí)時(shí)、分時(shí)系統(tǒng)中都可采用） x.25 Host.Page

11、 Chapter3 處理機(jī)調(diào)度與死鎖選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則（續(xù)） 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 - - 為了滿足系統(tǒng)需求。 系統(tǒng)吞吐量高；（常用來評(píng)價(jià)批處理系統(tǒng)） 處理機(jī)利用率高；（在大中型設(shè)備中?？紤]） 各類資源平衡利用；（在大中型設(shè)備中?？紤]）Page Chapter3 處理機(jī)調(diào)度與死鎖3.2 調(diào)度算法 實(shí)質(zhì)是一種資源分配資源分配，因而調(diào)度算法調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。 對(duì)于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法，例如，在批處理系統(tǒng)批處理系統(tǒng)中，為了照顧為數(shù)眾多的短作業(yè)，應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法又如在分時(shí)系統(tǒng)分時(shí)系統(tǒng)中，為了保證系統(tǒng)具有合理

12、的響應(yīng)時(shí)間，應(yīng)采用輪轉(zhuǎn)法進(jìn)行調(diào)度。 目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度；但也有些調(diào)度算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。 Page Chapter3 處理機(jī)調(diào)度與死鎖3.2.1 FCFS和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 先來先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)

13、，則每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后，才放棄處理機(jī)。 Page Chapter3 處理機(jī)調(diào)度與死鎖先來先服務(wù)調(diào)度算法之例一Process運(yùn)行時(shí)間 P1 24 P2 3 P3 3 假設(shè)進(jìn)程到達(dá)的順序?yàn)? P1 , P2 , P3 用Gantt圖表示的調(diào)度順序?yàn)?P1P2P32427300u等待時(shí)間： P1 = 0; P2 = 24; P3 = 27u平均等待時(shí)間: (0 + 24 + 27)/3 = 17Page Chapter3 處理機(jī)調(diào)度與死鎖先來先服務(wù)調(diào)度算法之例一（續(xù)）假設(shè)進(jìn)程到達(dá)的順序?yàn)? P2

14、 , P3 , P1 用Gantt圖表示的調(diào)度順序?yàn)?P1P3P263300 等待時(shí)間： P1 = 6；P2 = 0；P3 = 3 平均等待時(shí)間: (6 + 0 + 3)/3 = 3 好于前一個(gè)例子 系統(tǒng)性能與作業(yè)長度和運(yùn)行順序密切相關(guān)Page Chapter3 處理機(jī)調(diào)度與死鎖先來先服務(wù)調(diào)度算法之例二先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法下表列出了A、B、C 、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間，并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。z 從表上可以看出，其中短作業(yè)C的帶權(quán)周轉(zhuǎn)時(shí)間競(jìng)高達(dá)100,這是不能容忍的，而長作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間僅為1.99。 完

15、成 時(shí) 間 到 達(dá) 時(shí) 間帶 權(quán) 周 轉(zhuǎn) 時(shí) 間服 務(wù) 時(shí) 間Page Chapter3 處理機(jī)調(diào)度與死鎖先來先服務(wù)調(diào)度算法總結(jié) 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法 FCFS調(diào)度算法有利于CPU繁忙型的作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）。 CPU繁忙型作業(yè)繁忙型作業(yè)，是指該類作業(yè)需要大量的CPU時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求I/O。通常的科學(xué)計(jì)算便屬于CPU繁忙型作業(yè)。 I/O繁忙型繁忙型作業(yè)，是指CPU進(jìn)行處理時(shí)，需頻繁地請(qǐng)求I/O。目前的大多數(shù)事務(wù)處理都屬于I/O繁忙型作業(yè)。 Page Chapter3 處理機(jī)調(diào)度與死鎖短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法 指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法,可以分

16、別用于作業(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)度。Page Chapter3 處理機(jī)調(diào)度與死鎖SJF(SPF)優(yōu)先調(diào)度算法之例(非搶占式)ProcessArrival Time 運(yùn)行時(shí)間 P1 0.07 P22.04 P34.01 P4 5.04 SJF (非搶占式)P1P3P273160P4812u平均等待時(shí)間 (0 + 6 + 3 + 7

17、)/4 = 4Page Chapter3 處理機(jī)調(diào)度與死鎖SJF(SPF)優(yōu)先調(diào)度算法之例(搶占式)ProcessArrival Time運(yùn)行時(shí)間 P1 0.0 7 P2 2.0 4 P34.0 1 P45.0 4 SJF (搶占式)P1P3P242110P457P2P116u平均等待時(shí)間 (9 + 1 + 0 +2)/4 = 3Page Chapter3 處理機(jī)調(diào)度與死鎖SJ(P)F調(diào)度算法缺點(diǎn)z SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)： 該算法對(duì)長作業(yè)不利。 該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。 由于作業(yè)（進(jìn)程）的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)

18、間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。Page Chapter3 處理機(jī)調(diào)度與死鎖3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 目 的為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法，還可用于實(shí)時(shí)系統(tǒng)中。Mapping of Win32 priorities to Windows 2000 prioritiesPage Chapter3 處理機(jī)調(diào)度與死鎖Windows 2000支持32級(jí)線程優(yōu)先級(jí)P

19、age Chapter3 處理機(jī)調(diào)度與死鎖算法分類用于作業(yè)調(diào)度時(shí)，系統(tǒng)將從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)，裝入內(nèi)存。用于進(jìn)程調(diào)度時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。分為非搶占非搶占式優(yōu)先權(quán)算法和搶占式優(yōu)先權(quán)調(diào)度算法式優(yōu)先權(quán)算法和搶占式優(yōu)先權(quán)調(diào)度算法。Page Chapter3 處理機(jī)調(diào)度與死鎖優(yōu)先權(quán)的確定 優(yōu)先權(quán)的確定 進(jìn)程類型通常，系統(tǒng)進(jìn)程(如接收進(jìn)程、對(duì)換進(jìn)程、磁盤I/O進(jìn)程)的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。 進(jìn)程對(duì)資源的需求如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量的多少，對(duì)這些要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先 用戶要求 由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來確定優(yōu)先權(quán)P

20、age Chapter3 處理機(jī)調(diào)度與死鎖優(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)行期間保持不變。一般優(yōu)先權(quán)利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，07或0255中的某一整數(shù)。有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時(shí)，其優(yōu)先權(quán)愈低，而有的系統(tǒng)恰恰相反。z簡(jiǎn)單易行，系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進(jìn)程）長期沒有被調(diào)度的情況。因此，僅在要求不高的系統(tǒng)中，才使用靜態(tài)僅在要求不高的系統(tǒng)中，才使用靜態(tài)優(yōu)先權(quán)優(yōu)先權(quán). .Page Chapter3 處理機(jī)調(diào)度與死鎖優(yōu)先權(quán)分類(續(xù))動(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)或隨其等待

21、時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長，其優(yōu)先權(quán)以速率提高。若再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率下降，則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。Page Chapter3 處理機(jī)調(diào)度與死鎖高響應(yīng)比優(yōu)先調(diào)度算法 在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法主要的不足之處，是長作業(yè)的運(yùn)行得不到保證。 如果能為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率提高則長作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比Rp。據(jù)此，又可表示為：P

22、age Chapter3 處理機(jī)調(diào)度與死鎖高響應(yīng)比優(yōu)先調(diào)度算法（續(xù)） 高響應(yīng)比優(yōu)先調(diào)度算法 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)。 對(duì)于長作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級(jí)便可升到很高，從而獲得處理機(jī)。Page Chapter3 處理機(jī)調(diào)度與死鎖高響應(yīng)比優(yōu)先調(diào)度算法（續(xù)2）z 該算法既照顧了短作業(yè)，又考慮了作業(yè)到既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序達(dá)的先后次序，不會(huì)使長作業(yè)長期得不到服務(wù)。因此

23、，該算法實(shí)現(xiàn)了一種較好的折衷。 在利用該算法時(shí)，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計(jì)算，會(huì)增加系統(tǒng)開銷。Page Chapter3 處理機(jī)調(diào)度與死鎖3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 早期的時(shí)間片輪轉(zhuǎn)法早期的時(shí)間片輪轉(zhuǎn)法 在早期的時(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í)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒

24、隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)，響應(yīng)所有用戶的請(qǐng)求。Page Chapter3 處理機(jī)調(diào)度與死鎖多級(jí)反饋隊(duì)列調(diào)度算法z前面介紹的各種用作進(jìn)程調(diào)度的算法，都有一定的局限性。 如短進(jìn)程優(yōu)先的調(diào)度算法，僅照顧了短進(jìn)程而忽略了長進(jìn)程，而且如果并未指明進(jìn)程的長度，則短進(jìn)程優(yōu)先和基于進(jìn)程長度的搶占式調(diào)度算法，都將無法使用。 多級(jí)反饋隊(duì)列調(diào)度算法，則不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，而且還可以滿足各種類型進(jìn)程的需要。 Page Chapter3 處理機(jī)調(diào)度與死鎖多級(jí)反饋隊(duì)列調(diào)度算法(續(xù))z設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第

25、一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍。Page Chapter3 處理機(jī)調(diào)度與死鎖多級(jí)反饋隊(duì)列調(diào)度算法(續(xù)2)z 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第1隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。z當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)，如果它在1個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第2隊(duì)列的末尾，再同樣按FCFS原則等待調(diào)度執(zhí)行；z如果它在第2隊(duì)列中運(yùn)行1個(gè)時(shí)間片后仍未完成，再依

26、次將它放入第3隊(duì)列如此下去，當(dāng)1個(gè)長作業(yè)（進(jìn)程）從第1隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。Page Chapter3 處理機(jī)調(diào)度與死鎖多級(jí)反饋隊(duì)列調(diào)度算法(續(xù)3)僅當(dāng)?shù)?隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第2隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1(i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第，隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。Page Chapter3 處理機(jī)調(diào)度與死鎖多級(jí)反饋隊(duì)列調(diào)度算

27、法性能 多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能較好地滿足各種類型用戶需要。終端型作業(yè)用戶 由于終端型作業(yè)用戶所提交的作業(yè)，大多屬于文互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)（進(jìn)程）在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。短批處理作業(yè)用戶 對(duì)于很短的批處理型作業(yè)，開始時(shí)像終端型作業(yè)一樣，如果僅在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間。對(duì)于稍長的作業(yè)，通常也只需在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。長批處理作業(yè)用戶 對(duì)于長作業(yè)，它將依次在第1, 2, ,n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期

28、得不到處理。Page Chapter3 處理機(jī)調(diào)度與死鎖習(xí)題假定執(zhí)行表中所列作業(yè)，作業(yè)號(hào)即為到達(dá)順序，依次在時(shí)刻0按照次序1,2,3,4,5進(jìn)入單處理機(jī)系統(tǒng)。1.分別采用先來先服務(wù)、時(shí)間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非搶占式優(yōu)先權(quán)算法算出各作業(yè)的執(zhí)行先后次序。2.計(jì)算每種情況下的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。Page Chapter3 處理機(jī)調(diào)度與死鎖作業(yè)號(hào)執(zhí)行時(shí)間優(yōu)先數(shù)1103211323414552Page Chapter3 處理機(jī)調(diào)度與死鎖FCFS：執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Page Chapter3 處理機(jī)調(diào)度與死鎖RR執(zhí)行次序執(zhí)行時(shí)間提交時(shí)間完成時(shí)間

29、周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Page Chapter3 處理機(jī)調(diào)度與死鎖SJF執(zhí)行次序執(zhí)行時(shí)間等待時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Page Chapter3 處理機(jī)調(diào)度與死鎖非剝奪優(yōu)先權(quán)算法執(zhí)行次序優(yōu)先數(shù)執(zhí)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Page Chapter3 處理機(jī)調(diào)度與死鎖3.3 實(shí)時(shí)調(diào)度 實(shí)時(shí)系統(tǒng)中都存在著若干個(gè)實(shí)時(shí)進(jìn)程或任務(wù)，它們用來反應(yīng)或控制某個(gè)（些）外部事件，往往帶有某種程度的緊迫性緊迫性，因而對(duì)實(shí)時(shí)系統(tǒng)中的調(diào)度提出了某些特殊要求，前面所介紹的多種調(diào)度算法，并不能很好地滿足實(shí)時(shí)系統(tǒng)對(duì)調(diào)度的要求。為此，引入一種新的調(diào)度，即實(shí)時(shí)調(diào)度。應(yīng)用于： Engine control Pro

30、cess control in industrial plants Robotics Air traffic control Telecommunications Military command and control systems Multimedia applicationsPage Chapter3 處理機(jī)調(diào)度與死鎖3.3.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息 系統(tǒng)應(yīng)向調(diào)度程序提供有關(guān)任務(wù)的下述一些信息： 就緒時(shí)間就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始起始時(shí)間，在周期任務(wù)的情況下，它就是事先預(yù)知的一串時(shí)間序列；而在非周期任務(wù)的情況下，它也可能是預(yù)知的。 開始截止時(shí)間和完成截止時(shí)

31、間開始截止時(shí)間和完成截止時(shí)間。對(duì)于典型的實(shí)時(shí)應(yīng)用，只須知道開始截止時(shí)間，或者知道完成截止時(shí)間。 處理時(shí)間處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。在某些情況下，該時(shí)間也是系統(tǒng)提供的。 資源要求資源要求。這是指任務(wù)執(zhí)行時(shí)所需的一組資源。 優(yōu)先級(jí)優(yōu)先級(jí)。Page Chapter3 處理機(jī)調(diào)度與死鎖實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件（續(xù)）系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 途徑: 采用單處理機(jī)系統(tǒng)采用單處理機(jī)系統(tǒng)，增強(qiáng)其處理能力，減少對(duì)每一個(gè)任務(wù)處理時(shí)間 或是采用多處理機(jī)系統(tǒng)采用多處理機(jī)系統(tǒng)。采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制具有快速切換機(jī)制對(duì)外部中斷的快速響應(yīng)能力快速的任務(wù)分派能力。P

32、age Chapter3 處理機(jī)調(diào)度與死鎖3.3.2 實(shí)時(shí)調(diào)度算法的分類 可以按不同方式對(duì)實(shí)時(shí)調(diào)度算法加以分類，如： 根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同，可將實(shí)時(shí)調(diào)度的算法分為硬實(shí)時(shí)調(diào)度算法硬實(shí)時(shí)調(diào)度算法和軟實(shí)時(shí)調(diào)度軟實(shí)時(shí)調(diào)度算法； 按調(diào)度方式的不同，又可分為非搶占調(diào)度非搶占調(diào)度算法和搶占搶占調(diào)度調(diào)度算法； 因調(diào)度程序調(diào)度時(shí)間的不同而分成靜態(tài)調(diào)度算法靜態(tài)調(diào)度算法和動(dòng)動(dòng)態(tài)調(diào)度算法態(tài)調(diào)度算法，前者是指在進(jìn)程執(zhí)行前，調(diào)度程序便已經(jīng)決定了各進(jìn)程間的執(zhí)行順序，而后者則是在進(jìn)程的執(zhí)行過程中，由調(diào)度程序?qū)脮r(shí)根據(jù)情況臨時(shí)決定將哪一進(jìn)程投入運(yùn)行； 在多處理機(jī)環(huán)境下，還可將調(diào)度算法分為集中式調(diào)度集中式調(diào)度和分布式調(diào)度分布式調(diào)

33、度兩種算法。Page Chapter3 處理機(jī)調(diào)度與死鎖搶占式調(diào)度算法 在要求較嚴(yán)格的（響應(yīng)時(shí)間為數(shù)十毫秒以下）的實(shí)時(shí)系統(tǒng)中，應(yīng)采用搶占式優(yōu)先權(quán)調(diào)度算法，可根據(jù)搶占發(fā)生時(shí)間的不同而進(jìn)一步分成以下兩種調(diào)度算法。 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法?；跁r(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。調(diào)度延遲可降為幾十毫秒至幾毫秒，可用于大多數(shù)的實(shí)時(shí)系統(tǒng)中 立即搶占的優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法。調(diào)度延遲降低到幾毫秒至100 微秒，甚至更低。Page Chapter3 處理機(jī)調(diào)度與死鎖常用的幾種實(shí)時(shí)調(diào)度算法 最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDF (Earliest Deadline First）算法

34、該算法是根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序當(dāng)然，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時(shí)，總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)LLF(Least Laxity First)算法算法 該算法是根據(jù)任務(wù)緊急（或松弛）的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。Page Chapter3 處理機(jī)調(diào)度與死鎖例題：搶占式調(diào)度

35、用于周期實(shí)施任務(wù)Page Chapter3 處理機(jī)調(diào)度與死鎖Page Chapter3 處理機(jī)調(diào)度與死鎖3.5產(chǎn)生死鎖的原因和必要條件z 3.5.1 產(chǎn)生死鎖的原因z 3.5.2 產(chǎn)生死鎖的必要條件z 3.5.3 處理死鎖的基本方法 Page Chapter3 處理機(jī)調(diào)度與死鎖死鎖的定義死鎖簡(jiǎn)單的定義：死鎖就是兩個(gè)或兩個(gè)以上的進(jìn)程等候著一個(gè)永遠(yuǎn)不會(huì)發(fā)生的事件時(shí)所處的一種系統(tǒng)狀態(tài)。較正式的定義：兩個(gè)或兩個(gè)以上并發(fā)進(jìn)程，如果每個(gè)進(jìn)程持有某種資源，而又等待著別的進(jìn)程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進(jìn)。此時(shí)，每個(gè)進(jìn)程都占用了一定的資源，但又都不能向前推進(jìn)。這種現(xiàn)象稱為死鎖。Page Ch

36、apter3 處理機(jī)調(diào)度與死鎖死鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖） 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源 參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集Page Chapter3 處理機(jī)調(diào)度與死鎖3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn): 競(jìng)爭(zhēng)資源當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的資源如打印機(jī)、公用隊(duì)列等，其數(shù)目不足以滿足諸進(jìn)程的需要時(shí)，會(huì)引起諸進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。 進(jìn)程間推進(jìn)順序非法進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，同樣會(huì)導(dǎo)致產(chǎn)生進(jìn)程死鎖 Page Chapter3 處理機(jī)調(diào)度與死鎖競(jìng)爭(zhēng)資源引起進(jìn)程死鎖可剝奪和

37、非剝奪性資源可把系統(tǒng)中的資源分成兩類: 可剝奪性資源，是指某進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪。 例如，優(yōu)先權(quán)高的進(jìn)程可以剝奪優(yōu)先權(quán)低的進(jìn)程的處理機(jī)。又如，內(nèi)存區(qū)可由存儲(chǔ)器管理程序，把一個(gè)進(jìn)程從一個(gè)存儲(chǔ)區(qū)移到另一個(gè)存儲(chǔ)區(qū)，此即剝奪了該進(jìn)程原來占有的存儲(chǔ)區(qū)。甚至可將一進(jìn)程從內(nèi)存調(diào)出到外存上?？梢姡珻PU和主存均屬于可剝奪資源。 不可剝奪性資源，當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放. 如磁帶機(jī)、打印機(jī)等。 Page Chapter3 處理機(jī)調(diào)度與死鎖競(jìng)爭(zhēng)資源引起進(jìn)程死鎖(續(xù))競(jìng)爭(zhēng)非剝奪性資源在系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足

38、諸進(jìn)程運(yùn)行的需要，會(huì)使進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪這些資源而陷入僵局。 競(jìng)爭(zhēng)臨時(shí)性資源系統(tǒng)中有一類資源被稱為所謂的臨時(shí)性資源臨時(shí)性資源，這是指由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一段短暫時(shí)間后便無用的資源，故也稱之為消耗性資源消耗性資源，它也可能引起死鎖。資源分配圖Page Chapter3 處理機(jī)調(diào)度與死鎖3.5.2 產(chǎn)生死鎖的必要條件 死鎖的發(fā)生也必須具備一定的條件，必須具備下列四個(gè)必要條件: 互斥條件互斥條件 進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求該資源，則請(qǐng)求者只能等待，直至占有該資源的進(jìn)程用畢釋放。 請(qǐng)求和保持條件請(qǐng)求和保持條件 進(jìn)程

39、已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。Page Chapter3 處理機(jī)調(diào)度與死鎖產(chǎn)生死鎖的必要條件(續(xù))不剝奪條件不剝奪條件 進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。環(huán)路等待條件環(huán)路等待條件 指在發(fā)生死鎖時(shí)，必然存在一個(gè)”進(jìn)程-資源” 的環(huán)形鏈，即進(jìn)程集合P0, P1, P2 , , Pn中的P0正在等待一個(gè)P1占用的資源；P1，正在等待P2，占用的資源，,Pn正在等待已被P0占用的資源。Page Chapter3 處理機(jī)調(diào)度與死鎖3.5.3 處理死鎖的基本方法 為保證

40、系統(tǒng)中諸進(jìn)程的正常運(yùn)行，應(yīng)事先采取必要的措施，來預(yù)防發(fā)生死鎖。在系統(tǒng)中已經(jīng)出現(xiàn)死鎖后，則應(yīng)及時(shí)檢測(cè)到死鎖的發(fā)生，并采取適當(dāng)措施來解除死鎖。目前，處理死鎖的方法可歸結(jié)為以下四種：預(yù)防死鎖預(yù)防死鎖 通過設(shè)置某些限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來預(yù)防發(fā)生死鎖。較易實(shí)現(xiàn)，但由于所施加的限制條件往往太嚴(yán)格，可能會(huì)導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。 Page Chapter3 處理機(jī)調(diào)度與死鎖處理死鎖的方法(續(xù)) 避免死鎖避免死鎖 屬于事先預(yù)防的策略，但它并不須事先采取各種限制措施去破壞產(chǎn)生死鎖的四個(gè)必要條件，而是在資源的動(dòng)態(tài)分配過程中在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)

41、死鎖。 檢測(cè)死鎖檢測(cè)死鎖 允許系統(tǒng)在運(yùn)行中發(fā)生死鎖，大可以通過檢測(cè)機(jī)構(gòu)檢測(cè)出死鎖的發(fā)生。 解除死鎖解除死鎖與檢測(cè)死鎖配套，用以解除死鎖。Page Chapter3 處理機(jī)調(diào)度與死鎖3.6.1 預(yù)防死鎖 定義：在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。Page Chapter3 處理機(jī)調(diào)度與死鎖預(yù)防死鎖（2） 破壞破壞“不可剝奪不可剝奪”條件條件在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請(qǐng)。 缺點(diǎn)：實(shí)現(xiàn)起來比較復(fù)雜,要付出很大代價(jià)。因?yàn)橐粋€(gè)資源在使用一段時(shí)間后

42、，它的被迫釋放可能會(huì)造成前段工作的失效?？赡芤?yàn)榉磸?fù)地申請(qǐng)和釋放資源，致使進(jìn)程的執(zhí)行被無限地推遲，這不僅延長了進(jìn)程的周轉(zhuǎn)時(shí)間，而且也增加了系統(tǒng)開銷，降低了系統(tǒng)吞吐量。Page Chapter3 處理機(jī)調(diào)度與死鎖預(yù)防死鎖（3） 破壞破壞“請(qǐng)求和保持請(qǐng)求和保持”條件條件要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才一次性分配。缺點(diǎn)資源被嚴(yán)重浪費(fèi)，因?yàn)橐粋€(gè)進(jìn)程是一次性地獲得其整個(gè)運(yùn)行過程所需的全部資源的，且獨(dú)占資源，其中可能有些資源很少使用，甚至在整個(gè)運(yùn)行期間都未使用. 使進(jìn)程延遲運(yùn)行，僅當(dāng)進(jìn)程在獲得了其所需的全部資源后才能開始運(yùn)行，但可能因有些資源已長期被其

43、它進(jìn)程占用而致使等待該資源的進(jìn)程遲遲不能運(yùn)行。Page Chapter3 處理機(jī)調(diào)度與死鎖預(yù)防死鎖（4） 破壞破壞“循環(huán)等待循環(huán)等待”條件條件采用資源有序分配法：把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。例如：例如：1 1，2 2，3 3，1010P1：申請(qǐng)1申請(qǐng)3申請(qǐng)9P2：申請(qǐng)1申請(qǐng)2申請(qǐng)5P3 P10Page Chapter3 處理機(jī)調(diào)度與死鎖3.6.2 死鎖的避免 預(yù)防死鎖幾種方法中，施加了較強(qiáng)的限制條件； 在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)安全狀態(tài)和不安全狀態(tài)不

44、安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可避免發(fā)生死鎖。z 安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序（P1, P2,，Pn）（稱序列為安全序列），來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。z 如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。Page Chapter3 處理機(jī)調(diào)度與死鎖安全狀態(tài)之例 系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3。已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：l經(jīng)分析發(fā)現(xiàn)，在T0

45、時(shí)刻系統(tǒng)是安全的，因?yàn)檫@時(shí)存在一個(gè)安全序列，即只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成。Page Chapter3 處理機(jī)調(diào)度與死鎖銀行家算法最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。系統(tǒng)要求: 系統(tǒng)中須有多種/多個(gè)可用資源. 每個(gè)進(jìn)程必須預(yù)先聲明自己對(duì)資源的最大需求. 進(jìn)程在提出資源請(qǐng)求時(shí)可以等待. 當(dāng)進(jìn)程對(duì)資源的所有請(qǐng)求得到滿足時(shí)，應(yīng)歸還系統(tǒng)自己所得的全部資源.Page Chapter3 處理機(jī)調(diào)度與死鎖銀行家算法所用的數(shù)據(jù)結(jié)構(gòu) n：系統(tǒng)中進(jìn)程的總數(shù) m：資源類總數(shù) Available: 系統(tǒng)中各類資源可用數(shù)

46、目ARRAY1.m of integer; Max: 進(jìn)程對(duì)各類資源的最大需求, n x m matrix. ARRAY1.n,1.m of integer; Allocation: 已分配給某進(jìn)程的各類資源數(shù), n x m matrix. ARRAY1.n,1.m of integer; Need: 若進(jìn)程運(yùn)行完畢，還需資源數(shù), n x m matrix. ARRAY1.n,1.m of integer;wNeed i,j = Maxi,j Allocation i,j Request: 進(jìn)程某一次對(duì)系統(tǒng)提出的資源請(qǐng)求, n x m matrix. ARRAY1.n,1.m of integ

47、er;Page Chapter3 處理機(jī)調(diào)度與死鎖安全算法 檢查系統(tǒng)是否出處于安全狀態(tài)，存在一個(gè)序列，使所有進(jìn)程都可以順利執(zhí)行完畢。 1. Let Work and Finish be vectors of length m and n, respectively. Initialize:Work = AvailableFinish i = false for i - 1,3, , n. 2. Find and i such that both: (a) Finish i = false (b) Needi WorkIf no such i exists, go to step 4. 3. W

48、ork = Work + Allocation；Finishi = truego to step 2. 4. If Finish i = true for all i, then the system is in a safe state.Page Chapter3 處理機(jī)調(diào)度與死鎖進(jìn)程Pi請(qǐng)求資源算法Request = request vector for process Pi . If Requesti j = k then process Pi wants k instances of resource type Rj .1. If Requesti Needi go to step 2

49、. Otherwise, raise error condition, since process has exceeded its maximum claim.2. If Requesti Available, go to step 3. Otherwise Pi must wait, since resources are not available.3. Pretend to allocate requested resources to Pi by modifying the state as follows:Available = Available - Requesti ;Allocationi = Allocationi + Requesti ;Needi = Needi Requesti ;lIf safe the resources are allocated to Pi. lIf unsafe Pi must wait, and the old resource-allocation state is restoredPage Chapter3 處理機(jī)調(diào)度與死鎖銀行家算法的例子 5 processes P0 through P4; 3 resource types： A (10 instances), B ( 5 instance