第4章處理機(jī)調(diào)度

1、第第4 4 章章 處理機(jī)調(diào)度處理機(jī)調(diào)度 廖俊 曉莊學(xué)院第四章 處理機(jī)調(diào)度與死鎖n4.1 處理機(jī)調(diào)度的層次n4.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n4.3 調(diào)度算法 n4.4 實(shí)時(shí)調(diào)度 4.1 4.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次n在多道程序系統(tǒng)中，一個(gè)作業(yè)從提交到執(zhí)行，通常都要經(jīng)歷多級(jí)調(diào)度如高級(jí)調(diào)度、低級(jí)調(diào)度、中級(jí)調(diào)度以及IO調(diào)度等n系統(tǒng)的運(yùn)行性能在很大程度上取決于調(diào)度如吞吐量的大小、周轉(zhuǎn)時(shí)間的長(zhǎng)短、響應(yīng)的及時(shí)性等n調(diào)度是多道系統(tǒng)的關(guān)鍵n CPU資源管理多道程序設(shè)計(jì)面臨的挑戰(zhàn)批處理系統(tǒng)：如何安排內(nèi)存中多個(gè)作業(yè)的運(yùn)行順序？交互式系統(tǒng)：如何更好應(yīng)對(duì)不同的交互式請(qǐng)求？實(shí)時(shí)系統(tǒng)：如何保證實(shí)時(shí)服務(wù)的高質(zhì)量？

2、n 進(jìn)程調(diào)度有效的管理CPU資源When：何時(shí)進(jìn)行進(jìn)程調(diào)度？How：遵循何種規(guī)則完成調(diào)度？What：調(diào)度過(guò)程中需要完成哪些工作？n 進(jìn)程調(diào)度的級(jí)別高級(jí)調(diào)度：也稱(chēng)宏觀調(diào)度，決定哪些程序可以進(jìn)入系統(tǒng)中級(jí)調(diào)度：也稱(chēng)內(nèi)存調(diào)度，決定內(nèi)存中程序的位置和狀態(tài)低級(jí)調(diào)度：也稱(chēng)微觀調(diào)度，決定CPU資源在就緒進(jìn)程間的分配4.1.1 高級(jí)調(diào)度l 又稱(chēng)作業(yè)調(diào)度或長(zhǎng)程調(diào)度，其主要功能是按照某種原則從磁盤(pán)某些盤(pán)區(qū)的作業(yè)隊(duì)列中選取作業(yè)進(jìn)入主存，并為作業(yè)做好運(yùn)行前的準(zhǔn)備工作和作業(yè)完成后的善后工作。l 其調(diào)度對(duì)象是作業(yè)作業(yè)作業(yè)n作業(yè)（JOB）是用戶(hù)在一次算題過(guò)程中或一次事務(wù)處理中，要求計(jì)算機(jī)系統(tǒng)所做的工作的集合n作業(yè)是比進(jìn)程更廣

3、泛的概念，不僅包含了通常的程序和數(shù)據(jù)，而且還配有一份作業(yè)說(shuō)明書(shū)，系統(tǒng)根據(jù)作業(yè)說(shuō)明書(shū)對(duì)程序運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，以作業(yè)為單位從外存調(diào)入內(nèi)存n用戶(hù)為了讓計(jì)算機(jī)完成某個(gè)特定任務(wù)，首先編寫(xiě)成源程序，然后提交給計(jì)算機(jī)通過(guò)編譯或匯編、連接、裝配、運(yùn)行等步驟，最終由計(jì)算機(jī)送出用戶(hù)所需要的運(yùn)行結(jié)果。從計(jì)算機(jī)管理的角度看，上述一系列的一系列的由計(jì)算機(jī)執(zhí)行的任務(wù)的集合就是作業(yè)由計(jì)算機(jī)執(zhí)行的任務(wù)的集合就是作業(yè)。中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院$END$RUNData for program$LOADFortran program$FORTRAN $JOB, 10,429754 Cherry Chen 作業(yè)步

4、作業(yè)步編輯編譯或匯編連接裝入運(yùn)行n計(jì)算機(jī)完成作業(yè)是通過(guò)執(zhí)行一系列有序的工作步驟進(jìn)行的，每個(gè)步驟完成作業(yè)的一部分特定工作n把計(jì)算機(jī)系統(tǒng)完成一個(gè)作業(yè)所需的一系列有序的相對(duì)獨(dú)立的工作步驟稱(chēng)為作業(yè)步n作業(yè)的各個(gè)作業(yè)步雖然功能相對(duì)獨(dú)立，但它們之間相互關(guān)聯(lián)，往往是一個(gè)作業(yè)步的執(zhí)行需要使用上一個(gè)作業(yè)步的執(zhí)行結(jié)果。n若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，形成輸入的作業(yè)流；在操作系統(tǒng)控制下，逐個(gè)作業(yè)進(jìn)行處理，形成處理的作業(yè)流作業(yè)流作業(yè)流作業(yè)控制塊作業(yè)控制塊u 作業(yè)提交給系統(tǒng)進(jìn)入后備狀態(tài)后，系統(tǒng)將為每個(gè)作業(yè)建立一個(gè)作業(yè)控制塊JCB。u JCB在作業(yè)的整個(gè)運(yùn)行過(guò)程中始終存在，并且其內(nèi)容與作業(yè)的狀態(tài)同步地動(dòng)態(tài)變化

5、。只有當(dāng)作業(yè)完成并退出系統(tǒng)時(shí)，JCB才被撤消?？梢哉f(shuō)，JCB是一個(gè)作業(yè)在系統(tǒng)中存在的惟一標(biāo)志，系統(tǒng)根據(jù)JCB才感知到作業(yè)的存在u 作業(yè)控制塊JCB中包含了對(duì)作業(yè)進(jìn)行管理的必要信息，JCB中的信息一部分是從用戶(hù)提供的作業(yè)控制卡或作業(yè)說(shuō)明書(shū)中得到，另一部分是記錄作業(yè)運(yùn)行過(guò)程中的動(dòng)態(tài)信息u JCB的具體內(nèi)容因系統(tǒng)不同而異作業(yè)名作業(yè)名資源要求預(yù)估的運(yùn)行時(shí)間最遲完成時(shí)間要求的內(nèi)存量要求外設(shè)類(lèi)型、臺(tái)數(shù)要求的文件量和輸出量資源使用情況進(jìn)入系統(tǒng)時(shí)間開(kāi)始運(yùn)行時(shí)間已運(yùn)行時(shí)間內(nèi)存地址外設(shè)臺(tái)號(hào)類(lèi)型級(jí)別控制方式作業(yè)類(lèi)型優(yōu)先級(jí)狀態(tài)用戶(hù)賬戶(hù)作業(yè)控制塊 4.1.1 高級(jí)調(diào)度高級(jí)調(diào)度根據(jù)JCB，審查系統(tǒng)能否滿(mǎn)足用戶(hù)作業(yè)的資源需

6、求按一定算法算法，從外存后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存為它們創(chuàng)建進(jìn)程、分配必要資源將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行作業(yè)調(diào)度功能作業(yè)調(diào)度功能4.1.1 高級(jí)調(diào)度高級(jí)調(diào)度u用戶(hù)希望：自己作業(yè)的周轉(zhuǎn)時(shí)間盡可能少u(mài)系統(tǒng)希望：作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能少u(mài)作業(yè)調(diào)度： 1）決定接納多少個(gè)作業(yè) 2）決定接納哪些作業(yè)u先來(lái)先服務(wù)（FCFS）、 短作業(yè)優(yōu)先（SF）、 優(yōu)先級(jí)高優(yōu)先（HPF） 、響應(yīng)比高者優(yōu)先（RPF）作業(yè)調(diào)度算法作業(yè)調(diào)度算法4.1.1 高級(jí)調(diào)度高級(jí)調(diào)度u主要用于批處理系統(tǒng)。其設(shè)計(jì)目標(biāo)是最大限度地發(fā)揮各種資源的利用率和保持系統(tǒng)內(nèi)各種活動(dòng)的充分并行一個(gè)例子：對(duì)資源需求不同的作業(yè)進(jìn)行合理搭配科學(xué)計(jì)算

7、往往需要占用大量的CPU時(shí)間，屬于CPUCPU繁忙型作業(yè)繁忙型作業(yè)，對(duì)于I/O設(shè)備的使用少；而數(shù)據(jù)處理則相反，它們要求占用較少的CPU時(shí)間，但要求大量I/O時(shí)間，屬于I/OI/O繁忙型作業(yè)繁忙型作業(yè)；有些遞歸計(jì)算，產(chǎn)生大量中間結(jié)果，需要很多內(nèi)存單元存放它們，這屬于內(nèi)存繁忙型作業(yè)內(nèi)存繁忙型作業(yè)。如果能把它們搭配在一起，程序A在使用處理機(jī)，程序B在利用通道l，而程序C恰好利用通道2等，這樣一來(lái)，A、B和C從來(lái)不在同一時(shí)間使用同一資源，每個(gè)程序就好像單獨(dú)在一個(gè)機(jī)器上運(yùn)行l(wèi) 又稱(chēng)進(jìn)程調(diào)度或短程調(diào)度，其主要功能是按照某種原則將處理機(jī)分配給就緒進(jìn)程將處理機(jī)分配給就緒進(jìn)程。執(zhí)行低級(jí)調(diào)度功能的程序稱(chēng)為進(jìn)程調(diào)度

8、程序進(jìn)程調(diào)度程序，由它實(shí)現(xiàn)處理機(jī)在進(jìn)程間的轉(zhuǎn)換。它必須常駐主存，是操作系統(tǒng)內(nèi)核內(nèi)核的主要部分l 實(shí)際上，進(jìn)程調(diào)度程序主要是完成一臺(tái)物理的CPU轉(zhuǎn)變成多臺(tái)虛擬(或邏輯)的CPU的工作l 在多道批處理、分時(shí)和實(shí)時(shí)系統(tǒng)中都必須配備4.1.2 低級(jí)調(diào)度低級(jí)調(diào)度進(jìn)程調(diào)度程序的主要功能n保存現(xiàn)場(chǎng)。當(dāng)前運(yùn)行的進(jìn)程調(diào)用進(jìn)程調(diào)度程序時(shí)，即表示該進(jìn)程要求放棄CPU(因時(shí)間片用完或等待I/O等原因)。這時(shí)，進(jìn)程調(diào)度程序把它的現(xiàn)場(chǎng)信息，如程序計(jì)數(shù)器及通用寄存器的內(nèi)容等保留在該進(jìn)程PCB的現(xiàn)場(chǎng)信息區(qū)中n挑選進(jìn)程。根據(jù)一定的調(diào)度算法調(diào)度算法(如優(yōu)先級(jí)算法)，從就緒隊(duì)列中選出一個(gè)進(jìn)程來(lái)，并把它的狀態(tài)改為運(yùn)行態(tài)，準(zhǔn)備把CPU

9、分配給它n恢復(fù)現(xiàn)場(chǎng)把處理器分配給進(jìn)程。為選中的進(jìn)程恢復(fù)現(xiàn)場(chǎng)信息，并把CPU的控制權(quán)交給該進(jìn)程,它接著上次間斷的地方繼續(xù)運(yùn)行進(jìn)程調(diào)度中的三個(gè)基本機(jī)制n排隊(duì)器。將就緒進(jìn)程按一定方式排成隊(duì)列n分派器（分派程序）。把進(jìn)程調(diào)度程序選定的進(jìn)程，從就緒隊(duì)列中取出，進(jìn)行上下文切換，把處理器分配給它n上下文切換機(jī)制。保存當(dāng)前進(jìn)程上下文，裝入分派程序上下文，分派程序運(yùn)行；移出分派程序，裝入新選進(jìn)程上下文進(jìn)程調(diào)度方式1 1非搶占方式非搶占方式(Non-Preemptive Mode)(Non-Preemptive Mode)u 一旦處理機(jī)分配，便讓進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配

10、給其它進(jìn)程u 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷(xiāo)小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境u 缺點(diǎn)：難于滿(mǎn)足需要立即執(zhí)行的緊急任務(wù)，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中不宜采用u 在采用非搶占調(diào)度方式時(shí)，可能引起進(jìn)程調(diào)度的因素：u 正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行 u 執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行u 在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如P操作(wait操作)、Block原語(yǔ)、Wakeup原語(yǔ)等2 2搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)u 允許調(diào)度程序停止正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)，重新分配重新分配給另一進(jìn)程u 搶占的原則有

11、u 時(shí)間片原則u 優(yōu)先權(quán)原則u 短作業(yè)(進(jìn)程)優(yōu)先原則u 優(yōu)點(diǎn)：可防止長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占有處理機(jī)，為多數(shù)進(jìn)程提供公平服務(wù)u 缺點(diǎn)：系統(tǒng)開(kāi)銷(xiāo)較大進(jìn)程調(diào)度方式u 中級(jí)調(diào)度又稱(chēng)中程調(diào)度(Medium-Term Scheduling)u 引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量u 使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，將它們調(diào)至外存上去等待，把此時(shí)的進(jìn)程狀態(tài)稱(chēng)為就緒駐外存狀態(tài)或掛起狀態(tài)u 當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來(lái)決定把外存上的那些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度u 對(duì)換(存儲(chǔ)器管理)u

12、短期調(diào)整系統(tǒng)負(fù)荷，平順系統(tǒng)操作4.1.3 中級(jí)調(diào)度中級(jí)調(diào)度調(diào)度類(lèi)型調(diào)度類(lèi)型運(yùn)行頻率運(yùn)行頻率運(yùn)行時(shí)間運(yùn)行時(shí)間算法復(fù)雜性算法復(fù)雜性進(jìn)程調(diào)度進(jìn)程調(diào)度高高短短低低中程調(diào)度中程調(diào)度中等中等較短較短中等中等作業(yè)調(diào)度作業(yè)調(diào)度低低長(zhǎng)長(zhǎng)高高三級(jí)調(diào)度比較三級(jí)調(diào)度比較三級(jí)調(diào)度的相互比較三級(jí)調(diào)度的相互比較 高級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度外存到內(nèi)存內(nèi)外存互換內(nèi)存中批處理實(shí)時(shí)分時(shí)運(yùn)行頻率高運(yùn)行頻率適中運(yùn)行頻率低第四章 處理機(jī)調(diào)度n4.1 處理機(jī)調(diào)度的層次n4.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n4.3 調(diào)度算法 n4.4 實(shí)時(shí)調(diào)度 n高級(jí)調(diào)度、中級(jí)調(diào)度、低級(jí)調(diào)度，都將涉及到作業(yè)或進(jìn)程隊(duì)列，共有三種類(lèi)型的調(diào)度隊(duì)列模型。4.2 4.2 調(diào)

13、度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則 4.2.1 4.2.1 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就 緒隊(duì) 列阻 塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶(hù)事件出現(xiàn)時(shí)間片完分時(shí)系統(tǒng)通常僅設(shè)置進(jìn)程調(diào)度。每個(gè)進(jìn)程執(zhí)行都可能出現(xiàn)三種情況：(1)任務(wù)在該時(shí)間片內(nèi)已完成，釋放CPU進(jìn)入完成狀態(tài)；(2)任務(wù)在本次時(shí)間片內(nèi)尚未完成，OS便將該任務(wù)放在就緒隊(duì)列的后面；(3)執(zhí)行期間，進(jìn)程因某事件而被阻塞，放人阻塞隊(duì)列。具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完進(jìn)程調(diào)度完成等待事件 1事件 1 出現(xiàn)阻塞隊(duì)列等待事

14、件 2阻塞隊(duì)列等待事件 n事件 2 出現(xiàn)事件 n 出現(xiàn)后備隊(duì)列進(jìn)程調(diào)度作業(yè)調(diào)度實(shí)例：批處理操作系統(tǒng)(1) 引入了作業(yè)調(diào)度：從外存的后備隊(duì)列中選擇選擇一批作業(yè)調(diào)入內(nèi)存，為之創(chuàng)建進(jìn)程后送入就緒隊(duì)列。最常用的是優(yōu)先權(quán)隊(duì)列。(2) 設(shè)置多個(gè)阻塞隊(duì)列，每個(gè)對(duì)應(yīng)一種阻塞原因。同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型n在OS中引人中級(jí)調(diào)度后，就緒狀態(tài)分為：內(nèi)存就緒和外存就緒兩種狀態(tài)；阻塞狀態(tài)分成：內(nèi)存阻塞和外存阻塞兩種狀態(tài)。內(nèi)存緊張換出時(shí)，內(nèi)存就緒轉(zhuǎn)變?yōu)橥獯婢途w、內(nèi)存阻塞轉(zhuǎn)變?yōu)橥獯孀枞?；在中?jí)調(diào)度的作用下，又可使外存就緒轉(zhuǎn)為內(nèi)存就緒。就緒隊(duì)列CPU時(shí)間片完后備隊(duì)列進(jìn)程調(diào)度完成中級(jí)調(diào)度事件

15、出現(xiàn)阻塞隊(duì)列等待事件事件出現(xiàn)掛起就緒隊(duì)列就緒，掛起隊(duì)列阻塞，掛起隊(duì)列掛起作業(yè)調(diào)度交互作業(yè)批量作業(yè)4.2.2 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則n取決于操作系統(tǒng)的類(lèi)型和目標(biāo)n不同的操作系統(tǒng)，有不同的調(diào)度方式和算法n有面向用戶(hù)的準(zhǔn)則，也有面向系統(tǒng)的準(zhǔn)則面向用戶(hù)的準(zhǔn)則面向用戶(hù)的準(zhǔn)則n周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間短（批處理系統(tǒng)）n響應(yīng)時(shí)間快（分時(shí)系統(tǒng)）n截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。n優(yōu)先權(quán)準(zhǔn)則（批處理、分時(shí)、實(shí)時(shí)）讓某些緊急的作業(yè)得到及時(shí)的處理。在要求較嚴(yán)格的場(chǎng)合可采用搶占調(diào)度方式。u周轉(zhuǎn)時(shí)間，是指從作業(yè)提交給系統(tǒng)開(kāi)始，

16、到作業(yè)完成為止的這段時(shí)間間隔(稱(chēng)為作業(yè)周轉(zhuǎn)時(shí)間)，它包括：(1)作業(yè)在外存后備隊(duì)列上等待(作業(yè))調(diào)度的時(shí)間；(2)進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間；(3)進(jìn)程在CPU上執(zhí)行的時(shí)間；(4)等待IO操作完成的時(shí)間。平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間短會(huì)有效地提高資源利用率，且可使大多數(shù)用戶(hù)感到滿(mǎn)意。短會(huì)有效地提高資源利用率，且可使大多數(shù)用戶(hù)感到滿(mǎn)意。平均周轉(zhuǎn)時(shí)間可描述為：平均周轉(zhuǎn)時(shí)間可描述為：niiTnT11若系統(tǒng)為作業(yè)提供的實(shí)際服務(wù)時(shí)間為若系統(tǒng)為作業(yè)提供的實(shí)際服務(wù)時(shí)間為T(mén)sTs，W=TW=TTsTs稱(chēng)為帶權(quán)周轉(zhuǎn)時(shí)間，稱(chēng)為帶權(quán)周轉(zhuǎn)時(shí)間，平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間可表示為：可表示為：nisiiTTnW

17、11u 響應(yīng)時(shí)間是從用戶(hù)通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者說(shuō)直到在屏幕上顯示為止的一段時(shí)間間隔。它包括：(1)從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間；(2)處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；(3)將所形成的響應(yīng)回送到終端顯示器的時(shí)間面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則1系統(tǒng)吞吐量高（批處理）吞吐量是指在單位時(shí)間內(nèi)所完成的作業(yè)數(shù)。2處理機(jī)利用率好大、中型多用戶(hù)系統(tǒng)，CPU昂貴，處理機(jī)的利用率成為衡量系統(tǒng)性能的重要指標(biāo)3各類(lèi)資源的平衡利用第四章 處理機(jī)調(diào)度n4.1 處理機(jī)調(diào)度的層次n4.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則n4.3 調(diào)度算法 n4.4 實(shí)時(shí)調(diào)度 4.3 調(diào)度算法n在OS中，

18、調(diào)度的實(shí)質(zhì)是資源分配。n調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。n不同的系統(tǒng)和系統(tǒng)目標(biāo)，采用不同的調(diào)度算法。先來(lái)先服務(wù)調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法4.3.1 先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法n最簡(jiǎn)單的調(diào)度算法。n既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度。n每次調(diào)度都是選擇一個(gè)或多個(gè)最先進(jìn)入隊(duì)列的作業(yè)或進(jìn)程，為它們分配資源，創(chuàng)建進(jìn)程或分配CPU，使之投入運(yùn)行。 先來(lái)先服務(wù)調(diào)度算法(FCFS)的特點(diǎn)l作業(yè)調(diào)度和進(jìn)程調(diào)度均可，最簡(jiǎn)單簡(jiǎn)單，本質(zhì)上屬非剝奪方式l有利于長(zhǎng)作業(yè)/進(jìn)程，不利于短作業(yè)l有利于CPU繁忙型的作業(yè)(如通常的科

19、學(xué)計(jì)算)，而不利于IO繁忙的作業(yè)/進(jìn)程（如大多數(shù)的事務(wù)處理)例例4.3.2 短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法n短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度作業(yè)調(diào)度和進(jìn)程調(diào)度n短作業(yè)作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行n短進(jìn)程進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度例例圖 4-4 FCFS和SJF調(diào)度算法的性能 nSJ(P)F調(diào)度算法

20、有利于短作業(yè)，與FCFS算法相比，大大降低短作業(yè)的周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間短，系統(tǒng)吞吐量高nSJ(P)F調(diào)度算法對(duì)長(zhǎng)作業(yè)不利。甚至可能導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度，發(fā)生“饑餓”現(xiàn)象n該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理n此外，由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶(hù)所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶(hù)又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度 短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度優(yōu)先調(diào)度的特點(diǎn)的特點(diǎn)4.3.3 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法n既可用于作業(yè)調(diào)度作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度。n為照顧緊迫性

21、作業(yè)，使之進(jìn)入系統(tǒng)后獲得優(yōu)先處理，引入最高優(yōu)先權(quán)優(yōu)先調(diào)度算法。n按照進(jìn)程的優(yōu)先級(jí)大小來(lái)調(diào)度，使高優(yōu)先級(jí)進(jìn)程得到優(yōu)先的處理的高度策略稱(chēng)為優(yōu)先權(quán)調(diào)度算法。n在許多采用優(yōu)先級(jí)調(diào)度的系統(tǒng)中，通常采用動(dòng)態(tài)優(yōu)先數(shù)策略。進(jìn)程的優(yōu)先級(jí)不是固定的，往往隨許多因素的變化而變化。尤其隨作業(yè)（進(jìn)程）的等待時(shí)間、已使用的處理機(jī)時(shí)間或其它資源的使用情況而定。優(yōu)先級(jí)調(diào)度方法又可分為： 非搶占的優(yōu)先級(jí)調(diào)度法：即一旦某個(gè)高優(yōu)先級(jí)的進(jìn)程占有了處理機(jī)，就一直運(yùn)行下去，直到由于其自身的原因而主動(dòng)讓出處理機(jī)時(shí)(任務(wù)完成或等待事件)才讓另一高優(yōu)先級(jí)進(jìn)程運(yùn)行。主要用于批處理系統(tǒng)批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)實(shí)時(shí)性要求

22、不嚴(yán)的實(shí)時(shí)系統(tǒng)中。 可搶占的優(yōu)先級(jí)調(diào)度法：任何時(shí)刻都嚴(yán)格按照高優(yōu)先級(jí)進(jìn)程在處理機(jī)上運(yùn)行的原則進(jìn)行進(jìn)程的調(diào)度。常用于要求比較嚴(yán)格的實(shí)時(shí)要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)系統(tǒng)中， 以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。 1、優(yōu)先權(quán)調(diào)度算法的類(lèi)型、優(yōu)先權(quán)調(diào)度算法的類(lèi)型思考：I/O繁忙型的進(jìn)程，大部分時(shí)間是在等待I/O操作完成對(duì)于這一類(lèi)進(jìn)程，當(dāng)它們要求CPU運(yùn)行時(shí)，應(yīng)立即給予滿(mǎn)足，以便讓它們開(kāi)始下一個(gè)I/O操作和其它計(jì)算型的進(jìn)程并行工作。否則，這些I/O繁忙型的進(jìn)程將長(zhǎng)時(shí)間占據(jù)存儲(chǔ)器，降低系統(tǒng)并行度。解決方案：一個(gè)行之有效的算法是在進(jìn)程每次獲取CPU運(yùn)行后，重新指定該進(jìn)程的優(yōu)先級(jí)

23、為 1/f。這里的f表示進(jìn)程上次在CPU上實(shí)際運(yùn)行時(shí)間實(shí)際運(yùn)行時(shí)間與時(shí)間片之比與時(shí)間片之比。例如，若時(shí)間片為100毫秒，進(jìn)程上次在CPU上的實(shí)際運(yùn)行時(shí)間為2毫秒，則它的優(yōu)先級(jí)為50；若它上次實(shí)際運(yùn)行時(shí)間為50毫秒，則它的優(yōu)級(jí)為2。由于I/O繁忙型的進(jìn)程每次在CPU上運(yùn)行的時(shí)間很短，依此算法，它們的優(yōu)先級(jí)將較高，從而優(yōu)先得到服務(wù)。 實(shí)際中，優(yōu)先權(quán)算法常和輪轉(zhuǎn)法結(jié)合使用，也就是按優(yōu)先級(jí)將進(jìn)程分組，組間組間采用優(yōu)先級(jí)調(diào)度算法，而組內(nèi)組內(nèi)優(yōu)先級(jí)相同的進(jìn)程則按輪轉(zhuǎn)法調(diào)度。顯然，若優(yōu)先級(jí)不動(dòng)態(tài)地進(jìn)行調(diào)整，則優(yōu)先級(jí)低的就緒進(jìn)程就可能餓死。2. 優(yōu)先權(quán)的類(lèi)型優(yōu)先權(quán)的類(lèi)型 1) 靜態(tài)優(yōu)先權(quán)。靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)

24、程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：(1)(1) 進(jìn)程類(lèi)型進(jìn)程類(lèi)型 (2) (2) 進(jìn)程對(duì)資源的需求進(jìn)程對(duì)資源的需求(3) (3) 用戶(hù)要求用戶(hù)要求 2) 動(dòng)態(tài)優(yōu)先權(quán)。在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能 例如，我們可以規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)以速率a提高a) 若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程，將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法b) 若所有的就緒進(jìn)程具有

25、各不相同的優(yōu)先權(quán)初值，那么，對(duì)于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時(shí)間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機(jī)c) 當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個(gè)長(zhǎng)作業(yè)長(zhǎng)期地壟斷處理機(jī)3. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法n短作業(yè)優(yōu)先算法的不足之處是長(zhǎng)作業(yè)的運(yùn)行得不到保證n為每個(gè)作業(yè)引入動(dòng)態(tài)優(yōu)先權(quán)，使長(zhǎng)作業(yè)在等待一段時(shí)間后，有機(jī)會(huì)分配到處理機(jī)要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)(1

26、) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。(3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)。 調(diào)度之前，計(jì)算響應(yīng)比，增加系統(tǒng)開(kāi)銷(xiāo)！ 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)l(xiāng) 分時(shí)系統(tǒng)普遍采用l 早期,簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)l 20世紀(jì)90年代以后,廣泛采用多級(jí)反饋隊(duì)列調(diào)度算法4.3.4 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法l本質(zhì)：屬于

27、剝奪方式,分時(shí)系統(tǒng)中無(wú)例外采用(為確保響應(yīng)時(shí)間)l方法：每個(gè)進(jìn)程依次按時(shí)間片q輪流執(zhí)行，q的大小從幾ms到幾百ms。時(shí)間片用完則計(jì)時(shí)器觸發(fā)一中斷，重新調(diào)度，在一給定的時(shí)間內(nèi)，就緒進(jìn)程均能獲得一時(shí)間片的執(zhí)行時(shí)間時(shí)間片大小是關(guān)鍵問(wèn)題時(shí)間片大小是關(guān)鍵問(wèn)題1.時(shí)間片q正比于響應(yīng)時(shí)間，反比于就緒進(jìn)程數(shù)目。2.計(jì)算機(jī)的處理能力。速度快，q可小些。通常q值是這樣決定的：分時(shí)系統(tǒng)：q=T/Nmax T-響應(yīng)時(shí)間上限 Nmax-最大進(jìn)程數(shù)1 基于基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法時(shí)間片的輪轉(zhuǎn)調(diào)度算法練習(xí)題練習(xí)題 有下述五個(gè)進(jìn)程，按照時(shí)間片輪轉(zhuǎn)法進(jìn)行調(diào)度。每個(gè)進(jìn)程的到達(dá)時(shí)間和服務(wù)時(shí)間如下表所示。時(shí)間片長(zhǎng)度為1個(gè)單位，請(qǐng)描述

28、各個(gè)時(shí)間片的執(zhí)行情況，并計(jì)算每個(gè)進(jìn)程的結(jié)束時(shí)間、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。時(shí)間片長(zhǎng)度為1個(gè)單位時(shí)間片長(zhǎng)度為4個(gè)單位2. 2. 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法n不必不必事先知道各進(jìn)程所需執(zhí)行時(shí)間，可滿(mǎn)足各種進(jìn)程需要，是目前被公認(rèn)較好的調(diào)度算法。n設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。隊(duì)列按FCFS原則排列n各隊(duì)列時(shí)間片不同時(shí)間片不同n當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放在第一隊(duì)列尾，按FCFS原則調(diào)度；如果該時(shí)間片內(nèi)未結(jié)束，轉(zhuǎn)入第二隊(duì)隊(duì)列尾轉(zhuǎn)入第二隊(duì)隊(duì)列尾；直到最后的第N隊(duì)列，在第N隊(duì)列采取按時(shí)間片輪轉(zhuǎn)方式調(diào)度n僅當(dāng)?shù)诋?dāng)?shù)贗 I隊(duì)列空閑時(shí)隊(duì)列空閑時(shí)，才調(diào)度第i+1隊(duì)列n如有新進(jìn)程進(jìn)入優(yōu)先

29、級(jí)較高的隊(duì)列，則剝奪CPU執(zhí)行新進(jìn)程，舊進(jìn)程放入原隊(duì)列尾例如，若一個(gè)進(jìn)程總共需運(yùn)行例如，若一個(gè)進(jìn)程總共需運(yùn)行100100個(gè)時(shí)間片個(gè)時(shí)間片l 初始時(shí)指定它在優(yōu)先級(jí)最高的進(jìn)程組中，很快就會(huì)在CPU上運(yùn)行一個(gè)時(shí)間片，之后優(yōu)先級(jí)也降低一個(gè)級(jí)別l 當(dāng)它第二次有機(jī)會(huì)在CPU上運(yùn)行時(shí)，它將運(yùn)行2tl 以后它將在CPU上運(yùn)行的時(shí)間長(zhǎng)度依次是4，8，16，32和64個(gè)t，最后一次運(yùn)行時(shí)，只須64個(gè)t中的37個(gè) t 就可完成l 總共需總共需調(diào)度調(diào)度7 7次。次。比較單純的輪轉(zhuǎn)法，節(jié)省了93次切換時(shí)間練習(xí)題練習(xí)題 有下述五個(gè)進(jìn)程，按照多級(jí)反饋調(diào)度算法進(jìn)行調(diào)度。每個(gè)進(jìn)程的到達(dá)時(shí)間和服務(wù)時(shí)間如下表所示。分別描述當(dāng)時(shí)間片

30、長(zhǎng)度P=1和P= 時(shí)，各個(gè)時(shí)間片的執(zhí)行情況，并計(jì)算每個(gè)進(jìn)程的結(jié)束時(shí)間、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。3. 3. 多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法的性能 u終端型作業(yè)終端型作業(yè)用戶(hù)用戶(hù)u在第一隊(duì)列中完成，作業(yè)短，交互型； u短短批處理作業(yè)批處理作業(yè)用戶(hù)用戶(hù)u周期時(shí)間較短，通常三個(gè)隊(duì)列即可完成；u長(zhǎng)長(zhǎng)批處理作業(yè)批處理作業(yè)用戶(hù)用戶(hù)u依次在前n個(gè)隊(duì)列中執(zhí)行，然后再按輪轉(zhuǎn)方式運(yùn)行。第四章 處理機(jī)調(diào)度與死鎖4.1 處理機(jī)調(diào)度的層次4.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則4.3 調(diào)度算法 4.4 實(shí)時(shí)調(diào)度 4.4 4.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度n實(shí)時(shí)進(jìn)程或任務(wù)，用來(lái)反應(yīng)或控制某個(gè)外部事件，帶有某種程度的緊迫性，對(duì)調(diào)

31、度提出了特殊要求特殊要求n實(shí)時(shí)調(diào)度必須滿(mǎn)足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求4.4.1 4.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1. 1. 提供必要的信息（向調(diào)度程序提供）提供必要的信息（向調(diào)度程序提供） (1) 就緒時(shí)間(2) 開(kāi)始截止時(shí)間和完成截止時(shí)間 (3) 處理時(shí)間 (4) 資源要求 (5) 優(yōu)先級(jí) 2. 2. 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) l 實(shí)時(shí)系統(tǒng)中通常都有著多個(gè)實(shí)時(shí)任務(wù)l 若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理， 從而導(dǎo)致發(fā)生難以預(yù)料的后果l 假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則

32、在單處理機(jī)情況下，必須滿(mǎn)足下面的限制條件： miiiPC114.4.1 4.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3. 3. 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 l 當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿(mǎn)足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。這種調(diào)度機(jī)制比較復(fù)雜l 對(duì)于一些小的實(shí)時(shí)系統(tǒng)，如果能預(yù)知預(yù)知任務(wù)的開(kāi)始截止時(shí)間，則對(duì)實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制，簡(jiǎn)化簡(jiǎn)化調(diào)度程序和對(duì)任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開(kāi)銷(xiāo)。但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí)，應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時(shí)地將自己阻塞起來(lái)，以便釋放出處理機(jī)

33、，供調(diào)度程序去調(diào)度那種開(kāi)始截止時(shí)間即將到達(dá)的任務(wù) 4.4.1 4.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件4. 4. 具有快速切換機(jī)制具有快速切換機(jī)制 該機(jī)制應(yīng)具有如下兩方面的能力： (1) 對(duì)外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù)) (2) 快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度，應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男。詼p少任務(wù)切換的時(shí)間開(kāi)銷(xiāo)4.4.1 4.4.1 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件

34、4.4.2 4.4.2 實(shí)時(shí)調(diào)度算法的分類(lèi)實(shí)時(shí)調(diào)度算法的分類(lèi) 實(shí)時(shí)任務(wù)性質(zhì)的不同硬實(shí)時(shí)調(diào)度算法軟實(shí)時(shí)調(diào)度算法調(diào)度方式的不同非搶占調(diào)度算法搶占調(diào)度算法調(diào)度時(shí)間的不同靜態(tài)調(diào)度算法動(dòng)態(tài)調(diào)度算法多處理機(jī)環(huán)境集中式調(diào)度算法分布式調(diào)度算法1. 1. 非搶占式調(diào)度算法非搶占式調(diào)度算法 (1) 非搶占式輪轉(zhuǎn)輪轉(zhuǎn)調(diào)度算法常用于工業(yè)生產(chǎn)群控系統(tǒng)，可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間常用于工業(yè)生產(chǎn)群控系統(tǒng)，可獲得數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間(2) 非搶占式優(yōu)先優(yōu)先調(diào)度算法?？色@得數(shù)秒至數(shù)百毫秒的響應(yīng)時(shí)間可獲得數(shù)秒至數(shù)百毫秒的響應(yīng)時(shí)間2. 2. 搶占式調(diào)度算法搶占式調(diào)度算法 (1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)搶占式優(yōu)先權(quán)調(diào)度算法。

35、較好的響應(yīng)效果，調(diào)度延遲降為幾十毫秒至幾毫秒較好的響應(yīng)效果，調(diào)度延遲降為幾十毫秒至幾毫秒(2) 立即搶占立即搶占(Immediate Preemption)的優(yōu)先權(quán)調(diào)度算法。非常快的響應(yīng)，調(diào)度延遲降為幾毫秒至非?？斓捻憫?yīng)，調(diào)度延遲降為幾毫秒至100100微秒微秒4.4.3 4.4.3 常用的幾種實(shí)時(shí)調(diào)度算法常用的幾種實(shí)時(shí)調(diào)度算法1. 1. 最早截止時(shí)間優(yōu)先級(jí)最早截止時(shí)間優(yōu)先級(jí)EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 u 根據(jù)任務(wù)的開(kāi)始截止時(shí)間開(kāi)始截止時(shí)間確定任務(wù)的優(yōu)先級(jí)u 截止時(shí)間越早，優(yōu)先級(jí)越高u 實(shí)時(shí)任務(wù)就緒隊(duì)

36、列按開(kāi)始截止時(shí)間排序u 可用于搶占式調(diào)度，也可用于非搶占式調(diào)度1 1）非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)）非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù) 圖圖 EDF EDF算法用于非搶占調(diào)度方式算法用于非搶占調(diào)度方式 2 2）搶占式調(diào)度方式用于）搶占式調(diào)度方式用于周期實(shí)時(shí)周期實(shí)時(shí)任務(wù)任務(wù) B2B10102030405060708090100時(shí)間t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到達(dá)時(shí)間執(zhí)行時(shí)間最后期限B2 B1B2 B1A1A2A3A4B2A5固定優(yōu)先級(jí)固定優(yōu)先級(jí)調(diào)度（A優(yōu)先級(jí)高）B1錯(cuò)過(guò) B1B2B12 2）搶占式調(diào)度方式用

37、于周期實(shí)時(shí)任務(wù)）搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù) 0102030405060708090100時(shí)間t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到達(dá)時(shí)間執(zhí)行時(shí)間最后期限A1錯(cuò)過(guò)A2A3A5固定優(yōu)先級(jí)固定優(yōu)先級(jí)調(diào)度（B優(yōu)先級(jí)高） B2A4錯(cuò)過(guò)B2 B1 B1 B2B2B12 2）搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)）搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù) 0102030405060708090100時(shí)間t/msA1A2A3A4A5A1最后期限A2最后期限A3最后期限A4最后期限B1最后期限B2最后期限A5最后期限到達(dá)時(shí)間執(zhí)行時(shí)間最后期限A2A3最

38、早截止時(shí)間優(yōu)先A1A4A52. 2. 最低松弛度優(yōu)先級(jí)最低松弛度優(yōu)先級(jí)LLF(Least Laxity First)LLF(Least Laxity First)算法算法 u 根據(jù)任務(wù)緊急(或松弛)的程度，來(lái)確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高 松弛程度=必須完成時(shí)間-運(yùn)行時(shí)間 例如，一個(gè)任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間就有100ms，因此，調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100 msu 要求系統(tǒng)有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行u 主要用于可搶占調(diào)度方式可搶占調(diào)度方式中圖圖 A和和B任務(wù)每次必須完成的時(shí)間任務(wù)每次必須完成的時(shí)間 A1A2A3A4A5A6A7A