第03章 處理機(jī)調(diào)度及死鎖

1、2022-5-7第三章 處理機(jī)調(diào)度與死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實(shí)時(shí)調(diào)度3.5 產(chǎn)生死鎖的原因和必要條件3.6 預(yù)防死鎖的方法3.7 死鎖的檢測和解除第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。第三章 處理機(jī)調(diào)度與死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 進(jìn)程調(diào)

2、度要解決的問題WHAT：按什么原則分配CPU 進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)HOW： 如何分配CPU CPU調(diào)度過程（進(jìn)程的上下文切換）第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)調(diào)度算法對整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響可把處理機(jī)調(diào)度分成三個(gè)層次： 高級調(diào)度 中級調(diào)度 低級調(diào)度第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖運(yùn)行運(yùn)行就緒就緒阻塞阻塞掛起阻塞掛起阻塞掛起就緒掛起就緒創(chuàng)建創(chuàng)建退出退出進(jìn)程調(diào)度進(jìn)程調(diào)度中級調(diào)度中級調(diào)度作業(yè)調(diào)度作業(yè)調(diào)度調(diào)度的層次調(diào)度的層次第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.

3、1.1高級調(diào)度高級調(diào)度高級調(diào)度（作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度） 決定哪些作業(yè)可參與競爭CPU和其他資源，它的調(diào)度對象是作業(yè); 將外存作業(yè)調(diào)入內(nèi)存，創(chuàng)建PCB等，插入就緒隊(duì)列; 一般用于批處理系統(tǒng)，分/實(shí)時(shí)系統(tǒng)一般直接入內(nèi)存，無此環(huán)節(jié)。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1作業(yè)和作業(yè)步(1)作業(yè)(Job) 作業(yè)由一組統(tǒng)一管理和操作的進(jìn)程集合構(gòu)成，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書。 作業(yè)可以是完成了編譯、鏈接之后的一個(gè)用戶程序，也可以是用各種命令構(gòu)成的一個(gè)腳本。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖(2) 作業(yè)步(Job Step)。在作業(yè)運(yùn)行期間，經(jīng)過若干個(gè)

4、相對獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，我們把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步。(3) 作業(yè)流。若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，這便形成了輸入的作業(yè)流；在操作系統(tǒng)的控制下，逐個(gè)作業(yè)進(jìn)行處理，于是便形成了處理作業(yè)流。1作業(yè)和作業(yè)步第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2作業(yè)控制塊JCB(Job Control Block)每個(gè)作業(yè)進(jìn)入系統(tǒng)時(shí)由系統(tǒng)為其建立一個(gè)作業(yè)控制塊JCB（Job Control Block)，其中保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息.第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3作業(yè)調(diào)度作業(yè)調(diào)度功能：1.記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況（JCB，

5、Job Control Block）；2.按一定的調(diào)度算法，從后備作業(yè)中選擇一個(gè)或幾個(gè)作業(yè)進(jìn)入系統(tǒng)內(nèi)存；3.為被選中的作業(yè)創(chuàng)建進(jìn)程，并且為其申請系統(tǒng)資源；4.作業(yè)結(jié)束后作善后處理工作。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3作業(yè)調(diào)度第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3作業(yè)調(diào)度每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定1) 決定接納多少個(gè)作業(yè) 作業(yè)調(diào)度每次要接納多少個(gè)作業(yè)進(jìn)入內(nèi)存，取決于多道程序度(Degree of Multiprogramming)，2) 決定接納哪些作業(yè) 應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，這將取決于所采用的調(diào)度算法。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.1

6、.2 低級調(diào)度通常也稱為進(jìn)程調(diào)度、微觀調(diào)度或短程調(diào)度調(diào)度的對象是進(jìn)程(或內(nèi)核級線程)。進(jìn)程調(diào)度是最基本的一種調(diào)度，在三種OS中都有。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1低級調(diào)度的功能低級調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對CPU的競爭。(1) 保存處理機(jī)的現(xiàn)場信息。(2) 按某種算法選取進(jìn)程。(3) 把處理器分配給進(jìn)程。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2進(jìn)程調(diào)度中的三個(gè)基本機(jī)制為了實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制：(1) 排隊(duì)器。將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列。(2) 分派器。將處理機(jī)分配給從就緒隊(duì)列中選定的進(jìn)程(3) 上下文切換機(jī)制。當(dāng)對處理機(jī)進(jìn)行切換

7、時(shí)，會(huì)發(fā)生兩對上下文切換操作。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3進(jìn)程調(diào)度方式進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。非搶占方式(Nonpreemptive Mode) 調(diào)度因素：v 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；v 執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；1) 在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。優(yōu)點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理：實(shí)現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理OS缺點(diǎn)缺點(diǎn)：不適合不適合實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3進(jìn)程調(diào)度方式2)

8、搶占方式(Preemptive Mode)搶占的原則有：v 優(yōu)先權(quán)原則：優(yōu)先權(quán)高的可以搶占優(yōu)先級低的進(jìn)程的處理機(jī)。v 短作業(yè)（進(jìn)程）優(yōu)先原則：短作業(yè)（進(jìn)程）可以搶占長作業(yè)（進(jìn)程）的處理機(jī)。1. 時(shí)間片原則：各進(jìn)程按時(shí)間片運(yùn)行，一個(gè)時(shí)間片用完時(shí)，停止該進(jìn)程執(zhí)行重新進(jìn)行調(diào)度。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.1.3 中級調(diào)度 中級調(diào)度又稱為交換調(diào)度或中程調(diào)度（Medium-Term Scheduling）。 運(yùn)行頻率：低中高。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.1 高級、中級和低級調(diào)度第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則3.2.1調(diào)度

9、隊(duì)列模型1僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就 緒 隊(duì) 列阻 塞 隊(duì) 列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型每個(gè)進(jìn)程在執(zhí)行時(shí)都可能出現(xiàn)以下三種情況：(1) 任務(wù)在給定的時(shí)間片內(nèi)已經(jīng)完成，該進(jìn)程便在釋放處理機(jī)后進(jìn)入完成狀態(tài)；(2) 任務(wù)在本次分得的時(shí)間片內(nèi)尚未完成，OS便將該任務(wù)再放入就緒隊(duì)列的末尾；(3) 在執(zhí)行期間，進(jìn)程因?yàn)槟呈录蛔枞?，被OS放入阻塞隊(duì)列。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2具有高級和低級調(diào)度的調(diào)度隊(duì)列模型CPU就就 緒緒 隊(duì)隊(duì) 列列時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度等待事件等待事

10、件1進(jìn)程完成進(jìn)程完成后備隊(duì)列后備隊(duì)列等待事件等待事件2等待事件等待事件n事件事件1出現(xiàn)出現(xiàn)事件事件2出現(xiàn)出現(xiàn)事件事件n出現(xiàn)出現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖CPU就就 緒緒 隊(duì)隊(duì) 列列時(shí)間片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成后備隊(duì)列后備隊(duì)列作業(yè)調(diào)度作業(yè)調(diào)度中級調(diào)度中級調(diào)度就緒、掛起隊(duì)列就緒、掛起隊(duì)列阻阻 塞、掛塞、掛 起起 隊(duì)隊(duì) 列列掛起掛起事件出現(xiàn)事件出現(xiàn)等待事件等待事件掛起掛起阻阻 塞塞 隊(duì)隊(duì) 列列批量作業(yè)批量作業(yè)交互型作業(yè)交互型作業(yè)3同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型事事件件出出現(xiàn)現(xiàn)第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖基本原則： 具有公平性 資源

11、利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間(越短越好) 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量3.2.2選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1面向用戶的準(zhǔn)則2面向系統(tǒng)的準(zhǔn)則第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短 所謂周轉(zhuǎn)時(shí)間是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括：1、作業(yè)在外存后備隊(duì)列上等待調(diào)度的時(shí)間2、進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間3 、進(jìn)程在CPU上執(zhí)行的時(shí)間4 、進(jìn)程等待I/O操作完成的時(shí)間第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1面向用戶的準(zhǔn)則作業(yè)的周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間： ti i = tcici-

12、tsisi ti i:作業(yè)周轉(zhuǎn)時(shí)間作業(yè)周轉(zhuǎn)時(shí)間 tcici：作業(yè)完成時(shí)間：作業(yè)完成時(shí)間 tsisi: 作業(yè)提交時(shí)間作業(yè)提交時(shí)間 其中，其中，n為被測定作業(yè)流中的作業(yè)數(shù)為被測定作業(yè)流中的作業(yè)數(shù)第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1面向用戶的準(zhǔn)則 T：衡量不同調(diào)度算法對同一個(gè)作業(yè)流的性能：衡量不同調(diào)度算法對同一個(gè)作業(yè)流的性能 W：同一調(diào)度算法對不同作業(yè)流的性能衡量：同一調(diào)度算法對不同作業(yè)流的性能衡量 第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1面向用戶的準(zhǔn)則(2)響應(yīng)時(shí)間快 所謂響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。包括：1、從鍵盤輸入的請求信息傳送

13、到處理機(jī)的時(shí)間2、處理機(jī)對請求信息進(jìn)行處理的時(shí)間，3、以及將所形成的響應(yīng)信息送回到終端顯示器的時(shí)間。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1面向用戶的準(zhǔn)則(3)截至?xí)r間的保證 所謂截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或者必須完成的最遲時(shí)間。(4)優(yōu)先權(quán)準(zhǔn)則 為了便于讓某些緊急的作業(yè)能得到及時(shí)的處理，在選擇調(diào)度算法時(shí)還應(yīng)該遵循優(yōu)先權(quán)準(zhǔn)則。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2面向系統(tǒng)的準(zhǔn)則(1)系統(tǒng)吞吐量高 所謂吞吐量是指在單位時(shí)間內(nèi)系統(tǒng)所完成的工作量。 (2)處理機(jī)利用率好(3)各類資源的平衡使用第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.3調(diào) 度 算 法先進(jìn)先出(FI

14、FO)算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 時(shí)間片輪轉(zhuǎn)法 多級反饋隊(duì)列第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1先來先服務(wù)調(diào)度算法將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理，是一種最普遍和最簡單的方法。它優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長的作業(yè)，而不管要求運(yùn)行時(shí)間的長短。DCBACPU完完成成第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1先來先服務(wù)調(diào)度算法下表列出了JOB1、JOB2、JOB3、JOB4四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間，并計(jì)算

15、出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖作作業(yè)業(yè)進(jìn)進(jìn)入入時(shí)時(shí)間間估估計(jì)計(jì)運(yùn)運(yùn)行行時(shí)時(shí)間間（分分鐘鐘）開開始始時(shí)時(shí)間間結(jié)結(jié)束束時(shí)時(shí)間間周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間JOB18：001208：0010：001201JOB28：505010：0010：501202.4JOB39：001010：5011：0012012JOB49：502011：0011：20904.5作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 T = 112.5作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 W = 4.97545019.9第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖第第3章章

16、 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 A A B B C C D D E E ABCDE平均平均到達(dá)時(shí)間到達(dá)時(shí)間02468服務(wù)時(shí)間服務(wù)時(shí)間36452完成時(shí)間完成時(shí)間39131820周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間37912128.6帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間11.17 2.252.462.5605101520FCFS第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1先來先服務(wù)調(diào)度算法該調(diào)度方式屬于非搶占方式FCFS算法比較有利于長作業(yè)(進(jìn)程)，而不利于短作業(yè)(進(jìn)程)。實(shí)現(xiàn)簡單，但效率較低。不能保證良好的響應(yīng)時(shí)間第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法(SJF)是指對短

17、作業(yè)優(yōu)先調(diào)度，即從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存。 短進(jìn)程優(yōu)先調(diào)度算法(SPF)，是指對短進(jìn)程優(yōu)先調(diào)度，即從就緒隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，為它們分配處理機(jī)，使之投入運(yùn)行。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法作作業(yè)業(yè)進(jìn)進(jìn)入入時(shí)時(shí)間間估估計(jì)計(jì)運(yùn)運(yùn)行行時(shí)時(shí)間間（分分鐘鐘）開開始始時(shí)時(shí)間間結(jié)結(jié)束束時(shí)時(shí)間間周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間JOB18：001208：0010：001201JOB28：505010：3011：201503JOB39：001010：0010：10707JOB49：502

18、010：1010：30402作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 T = 95作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 W = 3.2538013第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖圖 FCFS和SJF調(diào)度算法的性能 FCFS和SJF的性能比較 進(jìn)程名 JOB1 JOB3 JOB4 平 均 到達(dá)時(shí)間 8:00 8:50 9:00 9:50作業(yè) 情況 調(diào)度 算法 服務(wù)時(shí)間 12050 10 20 完成時(shí)間 10:00 10:50 11:00 11:20 周轉(zhuǎn)時(shí)間 120 120 12090 112.5 FCFS (a) 帶權(quán)周轉(zhuǎn)時(shí)間 1 2.4124.5 4.975完成時(shí)間 10:00 11

19、:20 10:10 10:30 周轉(zhuǎn)時(shí)間 120150 70 40 95 SJF (b) 帶權(quán)周轉(zhuǎn)時(shí)間 13723.25 JOB2第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 A A B B E E C C D D ABCDE平均到達(dá)時(shí)間02468服務(wù)時(shí)間36452完成時(shí)間39152011周轉(zhuǎn)時(shí)間37111437.6帶權(quán)周轉(zhuǎn)時(shí)間11.17 2.752.81.51.8405101520 SPN第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法該算法對長作業(yè)不利。該算法完全未考慮作業(yè)的緊迫程度，因而不能保

20、證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理。由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。有效降低作業(yè)的平均等待時(shí)間第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法為照顧緊迫性作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)為照顧緊迫性作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了先處理，引入了最高優(yōu)先權(quán)優(yōu)先（最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算調(diào)度算法。此算法常被用于法。此算法常被用于批處理系統(tǒng)批處理系統(tǒng)中，作為作業(yè)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度進(jìn)程調(diào)度算法，還可用于算法，還可用于實(shí)時(shí)系統(tǒng)實(shí)時(shí)

21、系統(tǒng)中。它分為兩種：中。它分為兩種：非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2優(yōu)先權(quán)的類型對于高優(yōu)先權(quán)優(yōu)先調(diào)度算法，總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。首先考慮的問題是如何確定進(jìn)程的優(yōu)先數(shù)。動(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)可以：在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)：在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的：在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般利用某一范圍的整個(gè)運(yùn)行期間保持不變。一般利用某

22、一范圍的一個(gè)整數(shù)來表示，又稱為優(yōu)先數(shù)。一個(gè)整數(shù)來表示，又稱為優(yōu)先數(shù)。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2優(yōu)先權(quán)的類型確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：(1) 進(jìn)程類型。(2) 進(jìn)程對資源的需求。(3) 用戶要求。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3高響應(yīng)比優(yōu)先調(diào)度算法響應(yīng)比： R=（W+T）/T = 1+W/TT：估計(jì)執(zhí)行時(shí)間W：等待時(shí)間W+T：響應(yīng)時(shí)間 高響應(yīng)比優(yōu)先是對高響應(yīng)比優(yōu)先是對FCFS和和SJF方式的一種綜合平衡方式的一種綜合平衡 每當(dāng)要進(jìn)行調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3 高響應(yīng)比優(yōu)先調(diào)

23、度算法由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖算法特點(diǎn)(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可升到很高，從而也可獲得處理機(jī)?？缮胶芨?，從而也可獲得處理機(jī)。 (1) 作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 服務(wù)的時(shí)間相同時(shí)，作

24、業(yè)的優(yōu)先權(quán)決定于其等服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先服務(wù)?，F(xiàn)的是先來先服務(wù)。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖作業(yè)作業(yè)進(jìn)入時(shí)間進(jìn)入時(shí)間估計(jì)運(yùn)行估計(jì)運(yùn)行時(shí)間時(shí)間（分鐘）（分鐘）開始時(shí)間開始時(shí)間結(jié)束時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間（分鐘）（分鐘）帶權(quán)周轉(zhuǎn)帶權(quán)周轉(zhuǎn)時(shí)間時(shí)間JOB18：001208：0010：001201JOB28：505010：1011：001302.6JOB39：001010：0010：10707JOB49：502011：0011：20904.5作業(yè)平均周轉(zhuǎn)時(shí)間作業(yè)平均

25、周轉(zhuǎn)時(shí)間 T = 102.5作業(yè)帶權(quán)平均周轉(zhuǎn)時(shí)間作業(yè)帶權(quán)平均周轉(zhuǎn)時(shí)間 W = 3.77541015.1第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 A A B B C C E E D D ABCDE平均到達(dá)時(shí)間02468服務(wù)時(shí)間36452完成時(shí)間39132015周轉(zhuǎn)時(shí)間3791478帶權(quán)周轉(zhuǎn)時(shí)間11.17 2.252.83.52.1405101520HRRN第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.3.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1時(shí)間片輪轉(zhuǎn)法1）基本原理將CPU 的處理時(shí)間分成固定大小的時(shí)間片，系統(tǒng)將所有就緒進(jìn)程按先來先服務(wù)的原則排成隊(duì)列。每次

26、調(diào)度時(shí)，把CPU 分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完后，若進(jìn)程未結(jié)束，則重新排入就緒隊(duì)列尾部。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖簡單輪轉(zhuǎn)法的調(diào)度模型第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1時(shí)間片輪轉(zhuǎn)法2) 時(shí)間片大小的確定時(shí)間片長度變化的影響過長退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長。過短用戶的一次請求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長。對響應(yīng)時(shí)間的要求： T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1時(shí)間片輪轉(zhuǎn)法下圖示出了時(shí)間片分別為q=1和q=4時(shí)，A、B、C、D、E五個(gè)進(jìn)程的

27、運(yùn)行情況。進(jìn)程名進(jìn)程名 A A B B C C D D E E 到達(dá)時(shí)間到達(dá)時(shí)間 0 0 1 1 2 2 3 3 4 4 作業(yè)情況作業(yè)情況 服務(wù)時(shí)間服務(wù)時(shí)間 4 4 3 3 4 4 2 2 4 4 第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖時(shí)間片時(shí)間片q q分別為分別為1 1和和4 4時(shí)，五個(gè)進(jìn)程的運(yùn)行情況時(shí)，五個(gè)進(jìn)程的運(yùn)行情況1時(shí)間片輪轉(zhuǎn)法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖進(jìn)程名進(jìn)程名 A A B B C C D D E E 平均平均 到達(dá)時(shí)間到達(dá)時(shí)間 0 0 1 1 2 2 3 3 4 4 作業(yè)情況作業(yè)情況 時(shí)間片時(shí)間片 服務(wù)時(shí)間服務(wù)時(shí)間 4 4 3 3 4 4 2 2 4 4

28、 完成時(shí)間完成時(shí)間 1515 1212 1616 9 9 1717 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 1515 1111 1414 6 6 1313 11.811.8 RRRR q q=1=1 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 3.753.75 3.673.67 3.53.5 3 3 3.333.33 3.463.46 完成時(shí)間完成時(shí)間 4 4 7 7 1111 1313 1717 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 4 4 6 6 9 9 1010 1313 8.48.4 RRRR q q=4=4 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 1 1 2 2 2.252.25 5 5 3.333.33 2.52.5 1時(shí)間片輪轉(zhuǎn)法第第3章章 處理機(jī)調(diào)度

29、與死鎖處理機(jī)調(diào)度與死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 A A B B C C D D E E ABCDE平均到達(dá)時(shí)間02468服務(wù)時(shí)間36452完成時(shí)間317112019周轉(zhuǎn)時(shí)間3157141110帶權(quán)周轉(zhuǎn)時(shí)間12.51.752.85.52.7105101520B B D D Round Robin第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2多級反饋隊(duì)列調(diào)度算法將就緒隊(duì)列分為N級，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級別越高，時(shí)間越長，級別越小，時(shí)間片越小，最后一級采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出；系統(tǒng)從第一級調(diào)度，當(dāng)?shù)谝患墳榭諘r(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，.當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)

30、間片，放棄CPU時(shí)，進(jìn)入下一級隊(duì)列；等待進(jìn)程被喚醒時(shí)，進(jìn)入原來的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級隊(duì)列。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2多級反饋隊(duì)列調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖A A ABCDE平均到達(dá)時(shí)間02468服務(wù)時(shí)間36452完成時(shí)間417182014周轉(zhuǎn)時(shí)間4151414610.6帶權(quán)周轉(zhuǎn)時(shí)間 1.332.53.52.832.6305101520B B A A C C B B D D E E C C D D E E B B C C D D FeedBack第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死

31、鎖3多級反饋隊(duì)列調(diào)度算法的性能 多級反饋隊(duì)列調(diào)度算法具有較好的性能，能較好的滿足各種類型用戶的需要。終端型作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖Windows XP進(jìn)程調(diào)度模型基于優(yōu)先權(quán)的、可搶占的多級反饋隊(duì)列算法調(diào)度線程（而不考慮被調(diào)度線程屬于哪個(gè)進(jìn)程）線程優(yōu)先級：03116個(gè)實(shí)時(shí)優(yōu)先級隊(duì)列(1631)15個(gè)可變優(yōu)先級隊(duì)列(115)1個(gè)系統(tǒng)級隊(duì)列(0)：零頁線程高低等待線程被喚醒后，優(yōu)先級升高。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖Linux進(jìn)程調(diào)度模型對于分時(shí)進(jìn)程：分時(shí)輪轉(zhuǎn)，但時(shí)間片大小不固定。優(yōu)先選擇 進(jìn)程剩余時(shí)間片最大的就緒進(jìn)程。若所

32、有就緒進(jìn)程的時(shí)間片都已用完(counter=0)，則根據(jù)進(jìn)程優(yōu)先值priority，對所有進(jìn)程(包括等待態(tài)進(jìn)程)重新計(jì)算counter值,實(shí)在沒有就緒進(jìn)程可運(yùn)行，就選擇任務(wù)0。對于實(shí)時(shí)進(jìn)程：選優(yōu)先級最高的進(jìn)程先運(yùn)行。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行。行。當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)( (等待等待I/O)I/O)。分時(shí)系統(tǒng)中時(shí)間片到。分時(shí)系統(tǒng)中時(shí)間片到。當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒( (可搶占式可搶占式) )。在進(jìn)程通信中，

33、執(zhí)行中的進(jìn)程執(zhí)行了某種原語操在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作作(P(P操作，阻塞原語，喚醒原語操作，阻塞原語，喚醒原語) )。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.4實(shí) 時(shí) 調(diào) 度3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1提供必要的信息2系統(tǒng)處理能力強(qiáng)3采用搶占式調(diào)度機(jī)制4具有快速切換機(jī)制第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1提供必要的信息就緒時(shí)間就緒時(shí)間：該任務(wù)成為就緒狀態(tài)的時(shí)間。：該任務(wù)成為就緒狀態(tài)的時(shí)間。開始截止時(shí)間和完成截止時(shí)間開始截止時(shí)間和完成截止時(shí)間：只需知道一個(gè)。：只需知道一個(gè)。處理時(shí)間處理時(shí)間：從開始執(zhí)行到完成所需時(shí)間。：從開始執(zhí)行到完成所需時(shí)間。資源要求

34、資源要求：任務(wù)執(zhí)行時(shí)所需的一組資源。：任務(wù)執(zhí)行時(shí)所需的一組資源。優(yōu)先級優(yōu)先級：根據(jù)任務(wù)性質(zhì)賦予不同優(yōu)先級。：根據(jù)任務(wù)性質(zhì)賦予不同優(yōu)先級。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2系統(tǒng)處理能力強(qiáng)假如系統(tǒng)中有M個(gè)周期性的硬實(shí)時(shí)任務(wù)，處理時(shí)間為Ci，周期時(shí)間表示為Pi 則單機(jī)系統(tǒng)中必須滿足條件 多處理機(jī)系統(tǒng)中必須滿足條件11miiiPCNPCmiii1第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3采用搶占式調(diào)度機(jī)制硬實(shí)時(shí)任務(wù)： 廣泛采用搶占機(jī)制。 小的實(shí)時(shí)系統(tǒng)： 可采用非搶占調(diào)度機(jī)制（簡化調(diào)度程序和對任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷）。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖4具有快速切換機(jī)制為保

35、證要求較高的硬實(shí)時(shí)任務(wù)能及時(shí)運(yùn)行，在實(shí)時(shí)系統(tǒng)中還應(yīng)具有快速切換機(jī)制。該機(jī)制應(yīng)具有如下兩方面的能力：(1) 對外部中斷的快速響應(yīng)能力。(2) 快速的任務(wù)分派能力。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.4.2實(shí)時(shí)調(diào)度算法的分類可以按照不同方式對實(shí)時(shí)調(diào)度算法加以分類：可以按照不同方式對實(shí)時(shí)調(diào)度算法加以分類：根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同可分為根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同可分為硬實(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)度算法；第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1) 非搶占式輪轉(zhuǎn)調(diào)度算

36、法1非搶占式調(diào)度算法如果在實(shí)時(shí)系統(tǒng)中存在著要求較為嚴(yán)格的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法為這些任務(wù)賦予較高的優(yōu)先級。該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的(或類似的)對象，為每一個(gè)被控對象建立一個(gè)實(shí)時(shí)任務(wù)。 2) 非搶占式優(yōu)先調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1非搶占式調(diào)度算法進(jìn)程1進(jìn)程2進(jìn)程n實(shí)時(shí)進(jìn)程調(diào)度時(shí)間調(diào)度時(shí)間實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行a a 非搶占輪轉(zhuǎn)調(diào)度非搶占輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成當(dāng)前進(jìn)程運(yùn)行完成b b 非搶占優(yōu)先權(quán)調(diào)度非搶占優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間調(diào)度時(shí)間

37、第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2搶占式調(diào)度算法更高優(yōu)先級的實(shí)時(shí)任務(wù)到達(dá)后，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請求中斷的緊迫任務(wù)。1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法更高優(yōu)先級的實(shí)時(shí)任務(wù)到達(dá)后，并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)。2) 立即搶占的優(yōu)先權(quán)調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖c c 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程搶占當(dāng)前實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程，并立即執(zhí)行進(jìn)程，并立即執(zhí)行b b 立即搶占優(yōu)先權(quán)調(diào)度立即搶占優(yōu)先權(quán)調(diào)度當(dāng)

38、前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程要求調(diào)度實(shí)時(shí)進(jìn)程要求調(diào)度時(shí)鐘中斷到達(dá)時(shí)時(shí)鐘中斷到達(dá)時(shí)調(diào)度時(shí)間調(diào)度時(shí)間調(diào)度時(shí)間調(diào)度時(shí)間2搶占式調(diào)度算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.4.3常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先EDF（Earliest Deadline First）算法最低松弛度優(yōu)先LLF（Least Laxity First）算法第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1最早截止時(shí)間優(yōu)先即EDF算法 根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級 截止時(shí)間越早，優(yōu)先級越高 可以是搶占式或非搶占式第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1) 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù) 四個(gè)非周期任務(wù)

39、，它們先后到達(dá)。四個(gè)非周期任務(wù)，它們先后到達(dá)。 系統(tǒng)先調(diào)度任務(wù)系統(tǒng)先調(diào)度任務(wù)1 1執(zhí)行，在其執(zhí)行期間，任務(wù)執(zhí)行，在其執(zhí)行期間，任務(wù)2 2、3 3又先后到達(dá)。又先后到達(dá)。 由于任務(wù)由于任務(wù)3 3的開始截止時(shí)間早于任務(wù)的開始截止時(shí)間早于任務(wù)2 2，故系統(tǒng)在任務(wù)，故系統(tǒng)在任務(wù)1 1后將調(diào)度任后將調(diào)度任務(wù)務(wù)3 3執(zhí)行。執(zhí)行。 在此期間又到達(dá)作業(yè)在此期間又到達(dá)作業(yè)4 4，其開始截止時(shí)間仍是早于任務(wù)，其開始截止時(shí)間仍是早于任務(wù)2 2的，故在的，故在任務(wù)任務(wù)3 3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4 4執(zhí)行，最后才調(diào)度任務(wù)執(zhí)行，最后才調(diào)度任務(wù)2 2執(zhí)行。執(zhí)行。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)

40、調(diào)度與死鎖2) 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù) 有兩個(gè)周期性任務(wù)。有兩個(gè)周期性任務(wù)。 任務(wù)任務(wù)A A的周期時(shí)間為的周期時(shí)間為20 ms20 ms，每個(gè)周期的處理時(shí)間為，每個(gè)周期的處理時(shí)間為10 ms10 ms。 任務(wù)任務(wù)B B的周期時(shí)間為的周期時(shí)間為50 ms50 ms，每個(gè)周期的處理時(shí)間為，每個(gè)周期的處理時(shí)間為25 ms25 ms。圖中。圖中的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最后期限和執(zhí)行時(shí)間圖。的第一行示出了兩個(gè)任務(wù)的到達(dá)時(shí)間、最后期限和執(zhí)行時(shí)間圖。在在t = 0 t = 0 時(shí)，時(shí)， A1 A1和和B1B1同時(shí)到達(dá)，由于同時(shí)到達(dá)，由于A1A1的截止時(shí)間比的截止時(shí)間比B1B1早，故調(diào)度早，

41、故調(diào)度A1A1執(zhí)行；執(zhí)行；在在t = 10 t = 10 時(shí)，時(shí)， A1 A1完成，又調(diào)度完成，又調(diào)度B1B1執(zhí)行；執(zhí)行；在在t = 20 t = 20 時(shí)，時(shí)， A2 A2到達(dá)，由于到達(dá)，由于A2A2的截止時(shí)間比的截止時(shí)間比B2B2早，早，B1B1被中斷而調(diào)度被中斷而調(diào)度A2A2執(zhí)行；執(zhí)行；在在t = 30 t = 30 時(shí)，時(shí)， A2 A2完成，又重新調(diào)度完成，又重新調(diào)度B1B1執(zhí)行；執(zhí)行；在在t = 40 t = 40 時(shí)，時(shí)， A3 A3又到達(dá)，但又到達(dá)，但B1B1的截止時(shí)間要比的截止時(shí)間要比A A3 3早，仍應(yīng)讓早，仍應(yīng)讓B1B1繼續(xù)執(zhí)行直到完成繼續(xù)執(zhí)行直到完成(t = (t = 4

42、5)45)，然后再調(diào)度，然后再調(diào)度A3A3執(zhí)行；執(zhí)行；在在t = 55 t = 55 時(shí)，時(shí)， A3 A3完成，又調(diào)度完成，又調(diào)度B2B2執(zhí)行。執(zhí)行。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2最低松弛度優(yōu)先即LLF算法例如，一個(gè)任務(wù)在200 ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100 ms，因此，調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100 ms。在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列 。v松弛度：指任務(wù)緊急程度松弛度：指任務(wù)緊急程度第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2最低松弛度優(yōu)先即LLF算法在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周

43、期性實(shí)時(shí)任務(wù)在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A A和和B B。任務(wù)。任務(wù)A A要要求每求每 20 ms20 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 10 ms10 ms；任務(wù)；任務(wù)B B只要求每只要求每5 50 ms0 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 25 ms25 ms。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖v 在剛開始時(shí)(t1=0)，A1必須在20ms時(shí)完成，而它本身運(yùn)行又需 10 ms，可算出A1的松弛度為10ms；vB1必須在50ms時(shí)完成， 而它本身運(yùn)行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。v在t2=10 ms時(shí)，

44、A2的松弛度可按下式算出：vA2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間 =40 ms-10 ms-10 ms=20 ms 2.最低松弛度優(yōu)先(LLF)算法 第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2.最低松弛度優(yōu)先(LLF)算法v類似地，可算出B1的松弛度為15ms，調(diào)度程序應(yīng)選擇B2運(yùn)行。t3=30 ms時(shí)，A2的松弛度已減為0，B1的松弛度為15 ms，于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行.第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.5產(chǎn)生死鎖的原因和必要條件死鎖問題在1965年由Dijkstra（迪科斯徹 ） 發(fā)現(xiàn)，并隨著計(jì)算機(jī)技術(shù)的發(fā)展，逐漸成為人們關(guān)心的問

45、題。什么是死鎖？死鎖是怎么產(chǎn)生的？用什么方法來解決死鎖？這些正是今天我們要討論的問題。 第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.5產(chǎn)生死鎖的原因和必要條件早期的操作系統(tǒng)對申請某種資源的進(jìn)程，若該資源尚未分配時(shí)，立即將該資源分配給這個(gè)進(jìn)程。后來發(fā)現(xiàn)，對資源不加限制地分配可能導(dǎo)致進(jìn)程間由于競爭資源而相互制約以至于無法繼續(xù)運(yùn)行的局面，人們把這種局面稱為死鎖 (deadlock)。死鎖：指多個(gè)進(jìn)程因競爭共享資源而造成的一種死鎖：指多個(gè)進(jìn)程因競爭共享資源而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。向前推進(jìn)。第第3章章 處理機(jī)調(diào)度與死鎖

46、處理機(jī)調(diào)度與死鎖可能會(huì)發(fā)生死鎖已經(jīng)發(fā)生死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖關(guān)于死鎖的一些結(jié)論參與死鎖的進(jìn)程最少是兩個(gè) 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.5.1 產(chǎn)生死鎖的原因1.競爭系統(tǒng)資源2.進(jìn)程的推進(jìn)順序不當(dāng) 可剝奪和非剝奪性資源可剝奪和非剝奪性資源永久性資源和臨時(shí)性資源永久性資源和臨時(shí)性資源第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1競爭資源引起進(jìn)程死鎖1) 可剝奪和非剝奪性資源可把系統(tǒng)中的資源分成兩類一

47、類是可剝奪性資源，是指某進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪。另一類是不可剝奪性資源，當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1競爭資源引起進(jìn)程死鎖2) 競爭非剝奪性資源系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要，會(huì)使進(jìn)程在運(yùn)行過程中，因爭奪這些資源而陷入僵局。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1競爭資源引起進(jìn)程死鎖 若系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)掃描儀R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會(huì)產(chǎn)生死鎖。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖永久性資源和臨時(shí)性資源永久性資源：可

48、以被多個(gè)進(jìn)程多次使用（可再用資源）可搶占資源不可搶占資源臨時(shí)性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）“申請-分配-使用-釋放”模式第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3) 競爭臨時(shí)性資源S1、S2和S3是臨時(shí)性資源。進(jìn)程P1產(chǎn)生消息S1，又要求從P3接收消息S3；進(jìn)程P3產(chǎn)生消息S3，又要求從進(jìn)程P2接收其所產(chǎn)生的消息S2；進(jìn)程P2產(chǎn)生消息S2，又需要接收進(jìn)程P1所產(chǎn)生的消息S1。1競爭資源引起進(jìn)程死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 進(jìn)程之間通信時(shí)的死鎖 S2P1S3P3S1P2第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1競爭資源引起進(jìn)

49、程死鎖P1： Request(S3)； Release(S1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； P1： Release(S1)； Request(S3)； P2： Release(S2)； Request(S1)； P3： Release(S3)； Request(S2)； 如果消息通信按下述順序進(jìn)行：則不可能發(fā)生死鎖，但若改成下述的運(yùn)行順序：則可能發(fā)生死鎖。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖申請掃描儀申請打印機(jī)(阻塞)T1掃描儀打印機(jī)T2申請打印機(jī)申請掃描儀(阻塞)2進(jìn)程推進(jìn)順序不當(dāng)引起死鎖第

50、第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1) 進(jìn)程推進(jìn)順序合法在進(jìn)程P1和P2并發(fā)執(zhí)行時(shí)，如果按下述順序推進(jìn)：P1：Request(R1)；Request(R2)；P1：Release(R1)； Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)；No problem！第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2進(jìn)程推進(jìn)順序不當(dāng)引起死鎖213DP2Req(R2)P2Req(R1)P1Req(R1) P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1) P1Rel(R

51、2)4第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2進(jìn)程推進(jìn)順序不當(dāng)引起死鎖在進(jìn)程P1和P2并發(fā)執(zhí)行時(shí)，按照上圖曲線所示順序推進(jìn)時(shí)，兩進(jìn)程會(huì)順利完成，我們稱這種推進(jìn)順序是合法的。若按曲線的順序推進(jìn)時(shí)，進(jìn)入不安全區(qū) D內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.5.2產(chǎn)生死鎖的必要條件雖然進(jìn)程在運(yùn)行過程中可能發(fā)生死鎖，但死鎖的發(fā)生也必須具備一定的條件。死鎖的發(fā)生必須具備下列四個(gè)必要條件。互斥條件（資源獨(dú)占）請求和保持條件（部分分配，占有申請）不剝奪條件（不可強(qiáng)占）環(huán)路等待條件。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.5.3處理死鎖的基本方法預(yù)防死鎖避免死鎖

52、檢測死鎖解除死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.6預(yù)防死鎖的方法在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。一、互斥條件是資源固有屬性，不能避免。一、互斥條件是資源固有屬性，不能避免。二、摒棄請求和保持條件二、摒棄請求和保持條件三、摒棄三、摒棄“不剝奪不剝奪”條件條件四、摒棄四、摒棄“環(huán)路環(huán)路”條件條件第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.6.1預(yù)防死鎖摒棄請求和保持條件 資源一次性分配-破壞請求和保持條件。摒棄“不剝奪”條件 可剝奪資源-即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源，破壞不可剝奪條件。摒棄“環(huán)路”條件 資

53、源有序分配法-系統(tǒng)給每類資源賦予一個(gè)編號，每一個(gè)進(jìn)程按編號遞增的順序請求資源，釋放則相反，破壞環(huán)路等待條件。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖在預(yù)防死鎖的幾種方法中，都施加了較強(qiáng)的限制條件；在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)啊，便可避免發(fā)生死鎖。3.6.2系統(tǒng)安全狀態(tài)第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖1安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序來為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。安全序列 一個(gè)進(jìn)程序列P1，Pn是安全的，如果對于每一個(gè)

54、進(jìn)程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j i )當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。 安全狀態(tài)一定是沒有死鎖發(fā)生的不安全狀態(tài)：若系統(tǒng)不存在這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2. 安全狀態(tài)之例進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223假定有三個(gè)進(jìn)程假定有三個(gè)進(jìn)程P1P1、 P2P2和和P3P3，共有，共有1212臺(tái)臺(tái)磁帶機(jī)。磁帶機(jī)。進(jìn)程進(jìn)程P1P1總共要求總共要求1010臺(tái)臺(tái)磁帶機(jī)，磁帶機(jī)，P2P2和和P3P3分別要求分別要求4 4臺(tái)臺(tái)和和9 9臺(tái)臺(tái)。假設(shè)在假設(shè)在T0T

55、0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P1P1、P2P2和和P3P3已分別獲得已分別獲得5 5臺(tái)臺(tái)、2 2臺(tái)臺(tái)和和2 2臺(tái)臺(tái)磁帶機(jī)，尚有磁帶機(jī)，尚有3 3臺(tái)臺(tái)空閑未分配?？臻e未分配。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2. 安全狀態(tài)之例經(jīng)分析發(fā)現(xiàn)，在T0時(shí)刻系統(tǒng)是安全的，因?yàn)榇藭r(shí)存在一個(gè)安全序列，即只要系統(tǒng)按此進(jìn)程序列分配資源，就能使每個(gè)進(jìn)程都順利完成?？沈?yàn)證。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖如果不按照安全序分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，此時(shí)無法再找到一個(gè)安

56、全序列。 3.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495232第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)不一定導(dǎo)致死鎖第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.6.3利用銀行家算法避免死鎖由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算法。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.6.3 利用銀行家算

57、法避免死鎖數(shù)據(jù)結(jié)構(gòu) Available：可利用資源向量 Max：最大需求矩陣 Allocation：分配矩陣 Need：需求矩陣銀行家算法安全性算法Available：含有m個(gè)元素的數(shù)組，每一個(gè)元素代表一類可利用的資源數(shù)目。其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Max：nm的矩陣，定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。Allocation：nm的矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得R

58、j類資源的數(shù)目為K。Need：nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)；Request：nm的矩陣，用以表示每一個(gè)進(jìn)程當(dāng)前提出的對某類資源的請求。Available：可利用資源向量Max：最大需求矩陣Allocation：分配矩陣Need：需求矩陣Request：請求矩陣Needi,j=Maxi,j-Allocationi,j第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖3.6.3 利用銀行家算法避免死鎖數(shù)據(jù)結(jié)構(gòu)銀行家算法 當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：安全性算法步驟一：如果Requestij Nee

59、di,j，便轉(zhuǎn)向步驟二；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。步驟二：如果Requestij Availablej，便轉(zhuǎn)向步驟三；否則，表示尚無足夠資源，Pi須等待。 步驟三：系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej := Availablej - Requestij Allocationi,j := Allocationi,j + RequestijNeedi,j := Needi,j - Requestij 步驟四：系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，完成本次分配；否則

60、將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。Requesti：是進(jìn)程Pi的請求向量如果Requestij=K，表示進(jìn)程i需要K個(gè)Rj類型的資源。第第3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖Pi請求資源請求資源Requestij Needj請求超量，錯(cuò)返請求超量，錯(cuò)返Requestij Available不滿足，等待不滿足，等待Available:=Available-RequestijAllocationj:=Allocationj+RequestijNeedj:=Needj-Requestj安全安全確認(rèn)，確認(rèn)，pi繼續(xù)繼續(xù)Available:=Available+Requestij