第3章 處理機調度與死鎖

1、處理機調度與死鎖處理機調度與死鎖1第三章 處理機調度與死鎖3.1 處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標 3.2 作業(yè)與調度算法作業(yè)與調度算法3.3 進程調度進程調度3.4 實時調度實時調度3.5 死鎖概述死鎖概述3.6 預防死鎖預防死鎖3.7 避免死鎖避免死鎖3.8 死鎖的檢測與解除死鎖的檢測與解除處理機調度與死鎖處理機調度與死鎖23.1 處理機調度的層次處理機調度的層次3.1.1 高高級調度級調度 3.1.2 低低級調度級調度3.1.3 中中級調度級調度P85P85處理機調度與死鎖處理機調度與死鎖3q高級調度高級調度(High-Level Scheduling)

2、又稱又稱作業(yè)調度，決定后備作業(yè)中誰調入內存運行 q低級調度低級調度(Low-Level Scheduling)又稱又稱進程調度，決定就緒隊列中哪個進程獲得CPU； q中級調度中級調度( (Intermediate-Level Scheduling)又稱又稱在虛擬存儲器中引入，在內、外存對換區(qū)進行進程對換。處理機調度與死鎖處理機調度與死鎖4就 緒 隊 列阻 塞 隊 列進程調度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完圖圖 僅具有進程調度的調度隊列模型僅具有進程調度的調度隊列模型 1. 僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型處理機調度與死鎖處理機調度與死鎖5就 緒 隊 列進程調度

3、CPU進程完成等待事件1作業(yè)調度事件1出現(xiàn)時間片完等待事件2事件2出現(xiàn)等待事件n事件n出現(xiàn)后 備 隊 列圖 3-2具有高、低兩級調度的調度隊列模型 2. 具有具有高級、低級調度高級、低級調度的調度隊列模型的調度隊列模型6就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)圖 具有三級調度時的調度隊列模型 3. 具有三級調度的調度隊列模型具有三級調度的調度隊列模型處理機調度與死鎖處理機調度與死鎖71. 處理機調度算法共同目標（處理機調度算法共同目標（從全局角度）從全局角度）1. 資源利用率高（系統(tǒng)吞吐量高

4、）資源利用率高（系統(tǒng)吞吐量高） 單位時間內系統(tǒng)所完成的作業(yè)數(shù)，跟作業(yè)本身和調度算法有關 批處理系統(tǒng)批處理系統(tǒng) 2. 公平性公平性 （將領） 調度方式和算法，不發(fā)生饑餓現(xiàn)象3. 各資源的平衡利用各資源的平衡利用（士兵） 適當?shù)恼{度算法，能保持系統(tǒng)中各類資源都處于忙適當?shù)恼{度算法，能保持系統(tǒng)中各類資源都處于忙碌狀態(tài)。碌狀態(tài)。如CPU繁忙的作業(yè)和I/O繁忙的作業(yè)搭配4. 策略強制執(zhí)行策略強制執(zhí)行 譬如安全策略，必須準確執(zhí)行處理機調度與死鎖處理機調度與死鎖82. 批處理系統(tǒng)的目標批處理系統(tǒng)的目標1、周轉時間短、周轉時間短 作業(yè)從提交給系統(tǒng)到作業(yè)完成所經(jīng)歷的時間（作業(yè)周轉時間作業(yè)周轉時間= = 等待時間

5、+運行時間 =作業(yè)完成時刻 - 作業(yè)提交時刻 批處理系統(tǒng)批處理系統(tǒng) 平均周轉時間平均周轉時間 T=（T1+T2+Tn）/n 帶權周轉時間帶權周轉時間W = 周轉時間周轉時間/CPU執(zhí)行時間執(zhí)行時間2、系統(tǒng)吞吐量高、系統(tǒng)吞吐量高 單位時間內完成的作業(yè)數(shù)3、處理機利用率高、處理機利用率高 因CPU貴處理機調度與死鎖處理機調度與死鎖9 3. 分時系統(tǒng)的目標分時系統(tǒng)的目標2. 均衡性均衡性 系統(tǒng)相應時間的快慢應與用戶所請求服務的復雜性相適應1. 響應時間快響應時間快 從輸入一個請求到給出首次響應的時間分時系統(tǒng)分時系統(tǒng) (此時進程并不一定執(zhí)行完畢)處理機調度與死鎖處理機調度與死鎖10 4. 實時系統(tǒng)的目

6、標實時系統(tǒng)的目標1. 截止時間的保證截止時間的保證l實時系統(tǒng)性能的重要指標實時系統(tǒng)性能的重要指標，因而是選擇實時調度算法的重要準則。l開始截止時間（必須開始執(zhí)行的最遲時間）和完成截止時間（必須完成的最遲時間）2. 可預測性可預測性 希望連續(xù)，譬如游戲、電影處理機調度與死鎖處理機調度與死鎖113.2 作業(yè)與作業(yè)調度作業(yè)與作業(yè)調度資源分配算法/系統(tǒng)資源分配策略不同的系統(tǒng)，不同目標，采用不同的調度算法1 先來先服務（先來先服務（FCFSFCFS）算法2 短作業(yè)短作業(yè)(進程)優(yōu)先調度算法3 高優(yōu)先權優(yōu)先優(yōu)先權優(yōu)先調度算法4 基于時間片的輪轉基于時間片的輪轉調度算法P89P89處理機調度與死鎖處理機調度

7、與死鎖121. 先來先服務先來先服務( (FCFS)FCFS)調度算法調度算法l最簡單，可用于作業(yè)調度和進程調度作業(yè)調度和進程調度l在作業(yè)調度作業(yè)調度中，是從后備作業(yè)隊列后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，調入內存，分配資源、創(chuàng)建進程，放入就緒隊列。l在進程調度進程調度中，是從就緒隊列就緒隊列中選擇一個最先進入隊列的進程，分配處理機使之運行。進程則一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。l特點： 比較有利于長作業(yè)比較有利于長作業(yè)(進程進程)，而不利于短作業(yè)，而不利于短作業(yè)(進程進程) 。 有利于有利于CPU繁忙的作業(yè)，而不利于繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。繁忙的作

8、業(yè)。 處理機調度與死鎖處理機調度與死鎖13l可用于作業(yè)調度和進程調度。l短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF) 是從后備隊列后備隊列中選擇一/多個估計運行時間最短的作業(yè)，將它們調入內存運行。l短進程優(yōu)先短進程優(yōu)先(SPF) 則是從就緒隊列就緒隊列中選出一個估計運行時間最短的進程運行，并一直執(zhí)行到完成，或發(fā)生某事件而阻塞放棄處理機時再重新調度。l缺點：缺點：2. 短作業(yè)短作業(yè)(進程進程)優(yōu)先調度算法優(yōu)先調度算法(SJF/SPF) 對長作業(yè)對長作業(yè)(進程進程)不利不利 沒有考慮緊迫程度沒有考慮緊迫程度 運行時間難以估計運行時間難以估計處理機調度與死鎖處理機調度與死鎖143.2.4 優(yōu)先權優(yōu)先調度算法優(yōu)先權

9、優(yōu)先調度算法為照顧為照顧緊迫型緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理優(yōu)先處理1. 優(yōu)先權的類型優(yōu)先權的類型2. 高響應比優(yōu)先調度算法高響應比優(yōu)先調度算法(priority-scheduling algorithm，PSA)15： 靜態(tài)優(yōu)先權靜態(tài)優(yōu)先權 在創(chuàng)建進程時確定的，在整個運行期間不再改變。依據(jù)有：進程類型、進程對資源的要求、用戶要求的優(yōu)先權。動態(tài)優(yōu)先權動態(tài)優(yōu)先權 動態(tài)優(yōu)先權是基于某種原則，使進程的優(yōu)先權隨時間改變而改變。 譬如輪轉法處理機調度與死鎖處理機調度與死鎖162. 高響應比優(yōu)先調度算法高響應比優(yōu)先調度算法因為：響應時間因為：響應時間= =等待時間等

10、待時間+ +服務時間服務時間所以：優(yōu)先權所以：優(yōu)先權= =響應比響應比RP：作業(yè)的優(yōu)先級，隨著等待時間的增加以速率a提高；則長作業(yè)在等待一定時間后，必有機會分配到處理機有機會分配到處理機。優(yōu)先權的變化規(guī)律： 要求服務時間要求服務時間等待時間優(yōu)先權要求服務時間響應時間要求服務時間要求服務時間等待時間PR處理機調度與死鎖處理機調度與死鎖173.3 進程調度進程調度1.進程調度任務： 保存處理機的現(xiàn)場信息 按某種算法選取進程把處理機分配給進程2. 相應機制1 1 排隊器：排隊器： 按指定算法排2 2 分派器分派器 ：依據(jù)調度程序選進程3 3 上下文切換器：上下文切換器： 執(zhí)行大量的load 和sto

11、reP91P91處理機調度與死鎖處理機調度與死鎖進程調度機制進程調度機制18(1) (1) 排隊器排隊器 (2) (2) 分派器分派器(3) (3) 上下文切換器上下文切換器處理機調度與死鎖處理機調度與死鎖193進程調度方式(1) 非搶占方式非搶占方式 (Non-preemptive Mode) 一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，不搶搶，等。 直至該進程完成完成，自愿釋放處理機，或發(fā)生某事件而被阻塞阻塞時，才再把處理機分配給其他進程。 處理機調度與死鎖處理機調度與死鎖20非搶占方式非搶占方式可能引起進程調度的因素可能引起進程調度的因素： 自己down掉了：正

12、在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行； 自己跑去做別的事：執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行； 自己被阻塞：在進程通信或同步過程中執(zhí)行了某種原語操作，如wait操作、Block原語。優(yōu)點是優(yōu)點是實現(xiàn)簡單，系統(tǒng)開銷小實現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)，適用于大多數(shù)批批處理系統(tǒng)處理系統(tǒng)環(huán)境。但難以滿足緊急任務的要求環(huán)境。但難以滿足緊急任務的要求立即執(zhí)行。立即執(zhí)行。 處理機調度與死鎖處理機調度與死鎖21(2) 搶占方式搶占方式(preemptive Mode) 優(yōu)先權原則優(yōu)先權原則 短作業(yè)短作業(yè)( (進程進程) )優(yōu)先原則優(yōu)先原則 時間片原則時間片原則n（搶）根據(jù)某種原則暫停根據(jù)

13、某種原則暫停正在執(zhí)行的進程，將正在執(zhí)行的進程，將處理機重新處理機重新分配給另一進程分配給另一進程。n優(yōu)點：能滿足對響應時間有嚴格要求的實時任務的需求。n缺點：調度所需付出的開銷較大開銷較大。n（盜亦有道）搶占的幾條原則：搶占的幾條原則：處理機調度與死鎖處理機調度與死鎖223.3.2 輪轉調度算法輪轉調度算法 1. 時間片輪轉法時間片輪轉法l基本原理基本原理 所有就緒進程按先來先服務(FCFS)的原則排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片時間片后停止執(zhí)行，進行進程調度(例子)l時間片大小的確定時間片大小的確定 對對響應時間響應時間的要求的要求 就緒隊列中就緒隊列中

14、進程的數(shù)目進程的數(shù)目 系統(tǒng)的系統(tǒng)的處理能力處理能力處理機調度與死鎖處理機調度與死鎖232. 2. 多級反饋隊列調度算法多級反饋隊列調度算法n時間片輪轉算法和優(yōu)先級算法的綜合和發(fā)展時間片輪轉算法和優(yōu)先級算法的綜合和發(fā)展n算法的原理算法的原理(圖3-4)設置多個就緒隊列設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列最高，第二隊列次之，其余優(yōu)先權逐個降低。各隊列中執(zhí)行時間片的大小各不相同各隊列中執(zhí)行時間片的大小各不相同，優(yōu)先權愈高的隊列，每個進程的執(zhí)行時間片就愈小。新進程進入第一隊列的末尾新進程進入第一隊列的末尾，按FCFS調度，未完成放入下一隊列當?shù)谝魂犃锌臻e時，才調度第二隊列，當?shù)谝?/p>

15、隊列空閑時，才調度第二隊列，處理機調度與死鎖處理機調度與死鎖243. 3. 多級反饋隊列調度算法的性能多級反饋隊列調度算法的性能該算法有較好的性能，能很好地滿足各種類型用戶的該算法有較好的性能，能很好地滿足各種類型用戶的需要。需要。 (1) (1) 終端型作業(yè)用戶終端型作業(yè)用戶。作業(yè)大多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊列所規(guī)定的時間片內完第一隊列所規(guī)定的時間片內完成成，便可使終端型作業(yè)用戶都感到滿意。 (2) (2)短批處理作業(yè)用戶短批處理作業(yè)用戶。對很短的批處理型作業(yè)，像終端型作業(yè)一樣。對稍長的作業(yè)，也只需在第二隊列和第三隊列各執(zhí)行一個時間片即可完成，其周轉時間仍然較短

16、周轉時間仍然較短。 (3) (3)長批處理作業(yè)用戶長批處理作業(yè)用戶。對于長作業(yè)，它將依次在第1，2，n個隊列中運行，然后再按輪轉方式運行，用戶不必擔不必擔心其作業(yè)長期得不到處理心其作業(yè)長期得不到處理。 處理機調度與死鎖處理機調度與死鎖253.4 3.4 實時調度實時調度3.4.1 實現(xiàn)實時調度的實現(xiàn)實時調度的基本條件基本條件3.4.2 實時調度實時調度算法的分類算法的分類3.4.3 常用的幾種常用的幾種實時調度算法實時調度算法處理機調度與死鎖處理機調度與死鎖263.4.1 實現(xiàn)實時調度的基本條件實現(xiàn)實時調度的基本條件1. 提供必要的提供必要的調度信息調度信息2. 系統(tǒng)系統(tǒng)處理能力強處理能力強3

17、. 采用采用搶占式調度搶占式調度機制機制4. 具有具有快速切換快速切換機制機制處理機調度與死鎖處理機調度與死鎖27條件條件1. 提供必要的調度信息提供必要的調度信息n就緒時間就緒時間：成為就緒狀態(tài)的起始時間起始時間，周期任務是事先預知的一串時間序列，而非周期任務也可能是預知的n開始截止時間和完成截止時間開始截止時間和完成截止時間n處理時間處理時間：任務從開始執(zhí)行直至完成所需的時間n資源要求資源要求：任務執(zhí)行時所需的一組資源n優(yōu)先級優(yōu)先級: 賦予“絕對絕對”優(yōu)先級/“相對相對”優(yōu)先級 處理機調度與死鎖處理機調度與死鎖28條件條件2. 系統(tǒng)處理能力強系統(tǒng)處理能力強在實時系統(tǒng)中，通常都有多個實時任務

18、。在實時系統(tǒng)中，通常都有多個實時任務。需要強大的處理能力，否則忙不過來，某些需要強大的處理能力，否則忙不過來，某些任務難及時處理，導致發(fā)生難以預料的后果。任務難及時處理，導致發(fā)生難以預料的后果。11miiiPC 假定系統(tǒng)有假定系統(tǒng)有m m個周期性的硬實時任務，它們的處理個周期性的硬實時任務，它們的處理時間表示為時間表示為CiCi，周期時間表示為周期時間表示為PiPi，則則單處理機情況單處理機情況下，必須滿足下面的限制條件下，必須滿足下面的限制條件, ,系統(tǒng)才是可調度的：系統(tǒng)才是可調度的： 處理機調度與死鎖處理機調度與死鎖29假如系統(tǒng)中有6個硬實時任務，它們的周期時間都是 50 ms，而每次的處

19、理時間為 10 ms，則此時是不能滿足上式的，因而系統(tǒng)是不可調度的。Straightforward ways out： （自己做）（自己做）單處理機系統(tǒng)，單處理機系統(tǒng)，增強處理能力增強處理能力，減少，減少對每一個任務的處理時間；對每一個任務的處理時間； （找人幫忙）（找人幫忙）采用采用多處理機多處理機系統(tǒng)。假定系統(tǒng)中的系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為處理機數(shù)為N N，則應將上述的限制條件改為：則應將上述的限制條件改為： NPCmiii1處理機調度與死鎖處理機調度與死鎖30n硬實時任務硬實時任務( (差一點，都要發(fā)生災難的）的實時系的實時系統(tǒng)中，必須采用統(tǒng)中，必須采用搶占搶占機制，以滿足硬實時任務對

20、機制，以滿足硬實時任務對截止時間的要求。截止時間的要求。條件條件3. 采用搶占式調度機制采用搶占式調度機制處理機調度與死鎖處理機調度與死鎖31 為保證及時運行，實時系統(tǒng)應具有快速切換機為保證及時運行，實時系統(tǒng)應具有快速切換機制，以保證能進行任務的快速切換。有兩方面能力：制，以保證能進行任務的快速切換。有兩方面能力： 條件條件4. 具有快速切換機制具有快速切換機制n對外部中斷的對外部中斷的快速響應能力快速響應能力 為使在緊迫事件的請求能及時響應及時響應，要求系統(tǒng)具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短使禁止中斷的時間間隔盡量短，以免耽誤時機(緊迫任務)。n快速的任務快速的任務分派能力

21、分派能力 為提高分派程序進行任務切換的速度，系統(tǒng)中的每個運行功能單位適當?shù)匦∵\行功能單位適當?shù)匦?，以減少任務切換的時間開銷。 處理機調度與死鎖處理機調度與死鎖323.4.2 實時調度算法的分類實時調度算法的分類l任務性質：硬實時調度算法和軟實時軟實時調度算法l調度方式：非搶占調度算法和搶占調度算法l調度時間：靜態(tài)調度算法和動態(tài)調度算法l多處理機環(huán)境：集中式調度和分布式調度算法 1. 非搶占式調度算法非搶占式調度算法非搶占式非搶占式輪轉調度輪轉調度算法算法 非搶占式非搶占式優(yōu)先調度優(yōu)先調度算法算法。2. 搶占式調度算法搶占式調度算法基于基于時鐘中斷時鐘中斷的搶占式優(yōu)先權調度算法的搶占式優(yōu)先權調度

22、算法立即搶占立即搶占的優(yōu)先權調度算法的優(yōu)先權調度算法(a) 非搶占式輪轉調度當前進程實時進程實時進程請求調度實時進程搶占當前進程并立即執(zhí)行(d) 立即搶占的優(yōu)先權調度調度時間進程 1進程 2實時進程要求調度進程 n實時進程調度實時進程運行(b) 非搶占式優(yōu)先權調度當前進程實時進程實時進程請求調度 當前進程運行完成調度時間當前進程實時進程請求調度 時鐘中斷到來時調度時間(c) 基于時鐘中斷搶占的優(yōu)先權搶占調度調度時間實時進程圖圖3-8 3-8 實時進程調度四種情況的調度時間實時進程調度四種情況的調度時間處理機調度與死鎖處理機調度與死鎖343.4.3 常用的幾種實時調度算法常用的幾種實時調度算法1

23、. 最早截止時間優(yōu)先最早截止時間優(yōu)先(EDF, Earliest Deadline First) )算法算法n非搶占式調度方式用于非搶占式調度方式用于非周期非周期實時任務實時任務n搶占式調度方式用于搶占式調度方式用于周期周期實時任務實時任務2. 最低松弛度優(yōu)先最低松弛度優(yōu)先 (LLF,Least Laxity First)算法算法P99P99P101P101處理機調度與死鎖處理機調度與死鎖351. 最早截止時間優(yōu)先最早截止時間優(yōu)先(EDF, Earliest Deadline First) )算法算法n根據(jù)任務的根據(jù)任務的開始截止時間開始截止時間來確定任務的優(yōu)先級來確定任務的優(yōu)先級n系統(tǒng)保持一

24、個實時任務就緒隊列，隊列按任務系統(tǒng)保持一個實時任務就緒隊列，隊列按任務截止時間的早晚排序截止時間的早晚排序n既可用于既可用于搶占搶占式調度，也可用于式調度，也可用于非搶占非搶占式調度式調度P99P99處理機調度與死鎖處理機調度與死鎖36(1)(1) 非搶占式調度方式用于非周期實時任務非搶占式調度方式用于非周期實時任務1342開始截止時間任務執(zhí)行任務到達12 341342tn4個非周期任務先后到達。先調度任務1，在任務1執(zhí)行期間，任務2、3先后到達。n任務3的開始截止時間早于任務2，故在任務1后將調度任務3。n又到達的作業(yè)4，其開始截止時間仍早于任務2，故在任務3執(zhí)行完后，系統(tǒng)又調度任務4執(zhí)行，

25、最后才調度任務2執(zhí)行。處理機調度與死鎖處理機調度與死鎖37(2)(2) 搶占式調度方式用于周期實時任務搶占式調度方式用于周期實時任務n兩個周期性任務兩個周期性任務，任務，任務A的周期時間為的周期時間為20 ms，每每個周期的處理時間為個周期的處理時間為10 ms；任務任務B的周期時間為的周期時間為50 ms，每個周期的處理時間為每個周期的處理時間為25 ms。n任務任務A的到達時間為的到達時間為0、20、40、；最后期限為；最后期限為20、40、60、；n任務任務B的到達時間為的到達時間為0、50、100、；最后期限為；最后期限為50、100、150、。n圖圖3-10的第一行示出了兩個任務的到

26、達時間、最的第一行示出了兩個任務的到達時間、最后期限和執(zhí)行時間圖。后期限和執(zhí)行時間圖。處理機調度與死鎖處理機調度與死鎖38A1 B1 A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1 A2 B1 A3 B2 A4 B2 A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達時間、執(zhí)行時間和最后期限A1固定優(yōu)先級調度固定優(yōu)先級調度A2 B1A3A4A5，B2A5，B2A4A1(錯過)A2 B1 A3(錯過)A1A2 B1(錯過)A3A4A5，B201020304050 60708090100 時間 t/ms使用完

27、成最后期限最早和最后期限調度(A有較高優(yōu)先級)(B有較高優(yōu)先級)圖3-10 最早截止時間優(yōu)先算法用于搶占調度方式之例 處理機調度與死鎖處理機調度與死鎖39 2. 最低松弛度優(yōu)先最低松弛度優(yōu)先 (LLF,Least Laxity First)算法算法n根據(jù)任務根據(jù)任務緊急緊急/ /松弛的程度松弛的程度, ,來確定任務的優(yōu)先級來確定任務的優(yōu)先級n任務的緊急程度愈高，賦予的優(yōu)先級就愈高任務的緊急程度愈高，賦予的優(yōu)先級就愈高，以，以便優(yōu)先執(zhí)行。便優(yōu)先執(zhí)行。n算法主要用于可搶占調度方式中。算法主要用于可搶占調度方式中。P101P101處理機調度與死鎖處理機調度與死鎖40A1A2A3A4A5A6A7A82

28、0406080100120140160B1B2B3t0例子：例子：周期性實時任務周期性實時任務A A和和B B：任務A：每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務B：每50ms執(zhí)行一次，執(zhí)行時間為25ms。任務A和B每次必須完成的時間必須完成的時間分別為：A1、A2、A3、和B1、B2、B3、。 為保證不遺漏任何一次截止時間，應采用最低松弛度為保證不遺漏任何一次截止時間，應采用最低松弛度優(yōu)先的搶占調度策略。優(yōu)先的搶占調度策略。處理機調度與死鎖處理機調度與死鎖41LLF算法算法A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0t1A1(10)1020304

29、0506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t5t6t7t8B1(5)B2(15)B2(10)處理機調度與死鎖處理機調度與死鎖423.5 死鎖的原因和必要條件死鎖的原因和必要條件1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件3. 處理死鎖的基本方法處理死鎖的基本方法l死鎖概念的提出死鎖概念的提出1965年，Dijkstra研究銀行家算法時提出l死鎖死鎖（Deadlock） 多個進程在運行過程中，因爭奪資源而造成的 一種僵局一種僵局，若無外力作用，它們都將無法推進下去。處理機調度與死鎖處理機調度與死鎖431 產(chǎn)生死鎖的原因

30、產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結為如下兩點產(chǎn)生死鎖的原因可歸結為如下兩點：1 1、競爭資源、競爭資源 當供多個進程共享的資源（如打印機、公用隊列等）數(shù)目不足時，會引起諸進程對資源的競爭而產(chǎn)生死鎖。2 2、進程間推進順序非法、進程間推進順序非法 進程在運行過程中，請求和釋放資源的順序不當。處理機調度與死鎖處理機調度與死鎖44 產(chǎn)生死鎖的四個必要條件產(chǎn)生死鎖的四個必要條件1 1、互斥條件、互斥條件 （只能一人使用） 進程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個進程占用由一個進程占用。2 2、請求和保持條件、請求和保持條件 （兜里攢著一個，又要求另一個） 進程已經(jīng)保持了至少一個

31、資源，但又提出了新的資源請求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。 3 3、不剝奪條件、不剝奪條件 （占著，不給） 進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放自己釋放。 4 4、環(huán)路等待條件、環(huán)路等待條件 （自己不釋放，搶對方的） 發(fā)生死鎖時，必然存在一個進程資源的環(huán)形鏈資源的環(huán)形鏈。P107P107處理機調度與死鎖處理機調度與死鎖45 處理死鎖的基本方法處理死鎖的基本方法l預防死鎖預防死鎖 通過設置某些限定條件，破壞導致死鎖的四個必要條件之一或幾個，來預防死鎖發(fā)生。l避免死鎖避免死鎖 通過某方法防止系統(tǒng)進入不安全狀態(tài)l

32、檢測死鎖檢測死鎖 允許發(fā)生死鎖，通過措施清除。l解除死鎖解除死鎖 與檢測死鎖配套的措施。P108P108處理機調度與死鎖處理機調度與死鎖463.6 預防死鎖的方法預防死鎖的方法1. 破壞“請求和保持”條件2. 破壞“不可搶占”條件3. 破壞“循環(huán)等待”條件 在系統(tǒng)設計時確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個必要條破壞產(chǎn)生死鎖的四個必要條件之一件之一。 “互斥條件互斥條件”由由資源的性質決定資源的性質決定。處理機調度與死鎖處理機調度與死鎖471. 摒棄“請求和保持條件請求和保持條件”條件 所有進程在開始運行前，都必須一次性地申請整個運所有進程在開始運行前，都必須一次性地

33、申請整個運行過程所需的行過程所需的全部資源全部資源。簡單易實現(xiàn)，安全性高；資源浪費簡單易實現(xiàn)，安全性高；資源浪費, 進程延遲運行進程延遲運行n若系統(tǒng)有足夠的資源有足夠的資源，則把需要的所有資源分配給該進程，這樣，進程在整個運行期間便不會再提出資源要求，從而摒棄了請求條件請求條件。n分配資源時，只要有一種資源不能滿足某進程的要求，也不進行分配，而讓進程等待。n由于進程等待期間，并未占有任何資源未占有任何資源，也就摒棄了保持條件保持條件，從而避免死鎖發(fā)生。處理機調度與死鎖處理機調度與死鎖482. 摒棄“不剝奪不剝奪”條件n進程有新的資源請求時，如果得不到滿足，要先釋放原先占有的資源，待以后重新申請

34、。n等價于“被剝奪被剝奪”。n實現(xiàn)比較復雜，系統(tǒng)代價很高實現(xiàn)比較復雜，系統(tǒng)代價很高。例如例如: : 進程在運行過程中已用打印機輸出信息打印機輸出信息，但中途又因申請另一資源未果而被迫暫停運行并釋放打印機，后來系統(tǒng)又把打印機分配給其它進程使用。當進程再次恢復運行并再次獲得打印機繼續(xù)打印時，這前后兩次打印輸出的數(shù)據(jù)并兩次打印輸出的數(shù)據(jù)并不連續(xù)不連續(xù)，即打印輸出的信息其中間有一段是另一進程的。處理機調度與死鎖處理機調度與死鎖493. 摒棄“環(huán)路等待環(huán)路等待”條件n系統(tǒng)資源按類型系統(tǒng)資源按類型線性排序線性排序，并賦予不同的序號，并賦予不同的序號。例如：例如：輸入機序號為1，打印機為2，磁帶機為3，磁盤

35、為4n資源請求必須嚴格按照資源序號遞增序號遞增的次序提出。這樣，在資源分配圖中，不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件。n特性特性l各類資源所分配的序號必須相對穩(wěn)定，這限制了限制了新類型設備的增加新類型設備的增加。l進程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同，可造成對資源的浪費資源的浪費。l限制用戶簡單、自主地編程。處理機調度與死鎖處理機調度與死鎖503.7 系統(tǒng)的安全狀態(tài)系統(tǒng)的安全狀態(tài)基本思想：讓系統(tǒng)處于安全狀態(tài)基本思想：讓系統(tǒng)處于安全狀態(tài)1. 安全狀態(tài)安全狀態(tài)（安全序列）2. 安全狀態(tài)的例子安全狀態(tài)的例子3. 由安全狀態(tài)向不安全狀態(tài)的轉換由安全狀態(tài)向不安全狀態(tài)的轉換允許進程動態(tài)地申請

36、資源動態(tài)地申請資源，一次申請一部分資源。系統(tǒng)在進行資源分配之前，先計算資源分配的安全性資源分配之前，先計算資源分配的安全性。若分配不會導致系統(tǒng)進入不安全狀態(tài)，便將資源分配若分配不會導致系統(tǒng)進入不安全狀態(tài)，便將資源分配給進程；否則，進程必須等待。給進程；否則，進程必須等待。3.7 避免死鎖避免死鎖處理機調度與死鎖處理機調度與死鎖51 1. 安全狀態(tài)安全狀態(tài)（安全序列）n安全狀態(tài)安全狀態(tài)：指系統(tǒng)能按某種進程順序 ( (P P1 1，P P2 2，P Pn n) ) (稱P1，P2，Pn序列為安全序列安全序列)，為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成

37、。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)n安全狀態(tài)一定是沒有死鎖發(fā)生，安全狀態(tài)一定是沒有死鎖發(fā)生，不安全狀態(tài)是有可能進入死鎖狀態(tài)。 因此，避免死鎖的實質在于：系統(tǒng)在進行因此，避免死鎖的實質在于：系統(tǒng)在進行資源資源分配時，分配時，如何使系統(tǒng)如何使系統(tǒng)不進入不安全狀態(tài)。不進入不安全狀態(tài)。處理機調度與死鎖處理機調度與死鎖52 2. 安全狀態(tài)的例子安全狀態(tài)的例子(3個進程，12臺磁帶機)n假定系統(tǒng)中有三個進程P1、 P2和P3，共有12臺磁帶機。n進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。n在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，

38、尚有3臺空閑未分配。進程最大需求已分配可用P11053P242P392處理機調度與死鎖處理機調度與死鎖531. 銀行家算法中的數(shù)據(jù)結構銀行家算法中的數(shù)據(jù)結構2. 銀行家算法銀行家算法3. 安全性算法安全性算法4. 銀行家算法實例銀行家算法實例3.7.2 利用銀行家算法避免死鎖利用銀行家算法避免死鎖n創(chuàng)始人Dijkstra，該算法因能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。n銀行家算法的實質就是要設法保證系統(tǒng)動態(tài)分配資源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。n要求進程預先告知自己的最大資源需求，并且假設系統(tǒng)擁有固定的資源總量。P111P111處理機調度與死鎖處理機調度與死鎖541. 銀行家算法中的數(shù)

39、據(jù)結構銀行家算法中的數(shù)據(jù)結構 可用資源向量可用資源向量Available 一個含有m個元素的數(shù)組數(shù)組，每個元素代表一類可利用的資源數(shù)目，初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。 Availablej=K 表示系統(tǒng)中現(xiàn)有表示系統(tǒng)中現(xiàn)有Rj類資源有類資源有K個。個。 最大需求矩陣最大需求矩陣Max 一個nm的矩陣矩陣，定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。 Maxi,j=k 表示進程表示進程i需要需要Rj類資源的最大數(shù)目為類資源的最大數(shù)目為k處理機調度與死鎖處理機調度與死鎖55 分配矩陣分配矩陣Allocation 一個nm的矩陣，

40、定義系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。 Allocationi,j=k Allocationi,j=k 進程進程i i當前已分配當前已分配RjRj類資源的數(shù)目為類資源的數(shù)目為k k 需求矩陣需求矩陣Need 一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。 Needi,j=k Needi,j=k 進程進程i i還需還需RjRj類資源類資源k k個個 上述三個矩陣間存在下述關系：上述三個矩陣間存在下述關系： Needi,j = Maxi,j - Allocation i,jNeedi,j = Maxi,j - Allocation i,j處理機調度與死鎖處理機調度與死鎖562.

41、銀行家算法銀行家算法 設 R e q u e s ti是 進 程 Pi的 請 求 向 量 。 若Requestij=k，表示進程Pi需要k個j類資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：若RequestiNeedi ，則轉；否則，認為出錯。因為它所需要的資源數(shù)已超過它所宣布的最大值。若RequestiAvailable，則轉；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。處理機調度與死鎖處理機調度與死鎖57系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結構中的數(shù)值。 Available=Available Available=Available Request Requesti i

42、AllocationAllocationi i = = AllocationAllocationi i + Request+ Requesti i NeedNeedi i = = NeedNeedi i Request Requesti i系統(tǒng)執(zhí)行安全性算法，檢測此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。l安全正式將資源分給進程Pi；l不安全試探分配作廢，恢復資源狀態(tài)，Pi等待處理機調度與死鎖處理機調度與死鎖583安全性算法安全性算法安全性算法可描述如下：(1) (1) 設置兩個向量：設置兩個向量： 工作向量Work。系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時

43、，Work:=Available。后期，work:=work + allocation Finish。系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi:=false；當有足夠資源分配給進程時，再令Finishi:=true。 處理機調度與死鎖處理機調度與死鎖59(2) (2) 從進程集合中找到一個能滿足下述條件的進程：從進程集合中找到一個能滿足下述條件的進程： Finishi=false； Needi,jWorkj；若找到，執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。(3) 當進程當進程PiPi獲得資源后，可順利執(zhí)行，直至完成，獲得資源后，可順利執(zhí)行，直至完成， 并釋放出分配

44、給它的資源，故應執(zhí)行：并釋放出分配給它的資源，故應執(zhí)行：Workj:= Workj+Allocationi,j；Finishi:=true；go to step （2）； (4) (4) 如果如果所有進程的所有進程的Finishi=trueFinishi=true都滿足，則表都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 處理機調度與死鎖處理機調度與死鎖604. 銀行家算法實例銀行家算法實例 假定系統(tǒng)中有五個進程P0，P1，P2，P3，P4和三類資源A，B，C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖所示M ax A

45、llocation Need Available 資源 情況 進 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 圖3-15 T0時刻的資源分配表 P113P113處理機調度與死鎖處理機調度與死鎖61(1) T0時刻的安全性時刻的安全性：利用安全性算法對利用安全性算法對T T0 0時刻的資源分配時刻的資源分配情況進行分析情況

46、進行分析( (見圖見圖 3-16 3-16所示所示) )可知，在可知，在T T0 0時刻存在著一個安時刻存在著一個安全序列全序列 P P1 1，P P3 3，P P4 4，P P2 2，P P0 0 ，故系統(tǒng)是安全的。故系統(tǒng)是安全的。 W o rk N eed A llo cat io n W o rk + A llo cat io n 資 源 情 況 進 程 A B C A B C A B C A B C F in is h P1 3 3 2 1 2 2 2 0 0 5 3 2 t ru e P3 5 3 2 0 1 1 2 1 1 7 4 3 t ru e P4 7 4 3 4 3 1 0

47、 0 2 7 4 5 t ru e P2 7 4 5 6 0 0 3 0 2 1 0 4 7 t ru e P0 1 0 4 7 7 4 3 0 1 0 1 0 5 7 t ru e 圖3-16T0時刻的安全序列 M ax A llocation N eed Available 資 源 情 況 進 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0

48、 0 2 4 3 1 處理機調度與死鎖處理機調度與死鎖62(2) P1請求資源請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如下圖中的圓括號所示。M ax Allocation Need Available 資源 情況 進 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3

49、3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 處理機調度與死鎖處理機調度與死鎖63 再利用安全性算法檢查此時系統(tǒng)是否安全(圖3-17)Work Need Allocation Work+Allocation 資源 情況 進 程 A B C A B C A B C A B C Finish P1 2 3 0 0 2 0 3 0 2 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4

50、 7 4 3 4 3 1 0 0 2 7 4 5 true P0 7 4 5 7 4 3 0 1 0 7 5 5 true P2 7 5 5 6 0 0 3 0 2 10 5 7 true 圖3-18P1申請資源時的安全性檢查 M ax A llocation N eed Available 資 源 情 況 進 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4

51、4 3 3 0 0 2 4 3 1 處理機調度與死鎖處理機調度與死鎖64(3) P4請求資源請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，讓P4等待。(4) P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進行檢查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系統(tǒng)暫時先假定可為P0分配資源，并修改有關數(shù)據(jù)，如下圖所示。 處理機

52、調度與死鎖處理機調度與死鎖65圖3-18為P0分配資源后的有關資源數(shù)據(jù) P0發(fā)出請求向量Requst0(0，2，0)，處理機調度與死鎖處理機調度與死鎖66圖3-18為P0分配資源后的有關資源數(shù)據(jù) (5) (5) 進行安全性檢查進行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進程的需要，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不分配資源。若把若把P0發(fā)出的請求向量改為發(fā)出的請求向量改為Request0(0，1，0)，系統(tǒng)是否能將資源分配給它系統(tǒng)是否能將資源分配給它? ?處理機調度與死鎖處理機調度與死鎖673.8 死鎖的檢測和解除死鎖的檢測和解除3.8.1 死鎖的檢測死鎖的檢測3.8.

53、2 死鎖的解除死鎖的解除 系統(tǒng)為進程系統(tǒng)為進程分配資源時，如果沒有分配資源時，如果沒有采取任何采取任何限制性措施，則必須提供限制性措施，則必須提供檢測和解除死鎖檢測和解除死鎖的的手段，手段，為此要做為此要做： 保存有關資源的請求和分配信息信息； 提供算法算法，利用這些信息來檢測系統(tǒng)是n否已進入死鎖狀態(tài)。P115P115處理機調度與死鎖處理機調度與死鎖683.8.1 死鎖的檢測死鎖的檢測1. 資源分配圖資源分配圖 G=(N,E) 2. 死鎖定理死鎖定理(資源分配圖是不可完全簡化) 3. 死鎖檢測中的數(shù)據(jù)結構死鎖檢測中的數(shù)據(jù)結構處理機調度與死鎖處理機調度與死鎖691. 資源分配圖資源分配圖 (Re

54、source Allocation Graph)系統(tǒng)死鎖可利用資源分配圖來描述系統(tǒng)死鎖可利用資源分配圖來描述 資源分配圖資源分配圖是由一組結點N和一組邊E所組成的一個對偶G=(N,E)，有下述定義： (1) N是一組結點，分兩個互斥的子集：一組進程結點P=p1，p2，pn和一組資源結點R=r1，r2，rn，N=PR。 (2) E是邊集合。e=pi，rj是資源是資源請求邊請求邊，由進程pi指向資源rj，表示進程pi請求一個單位的rj資源。e=rj，pi是資源是資源分配邊分配邊，由資源rj指向進程pi，表示把一個單位的資源rj分配給進程pi。處理機調度與死鎖處理機調度與死鎖70圓圈圓圈代表一個進程，代表一個進程，方框方框代