計(jì)算機(jī)操作系統(tǒng)

第四章處理機(jī)調(diào)度第1頁第四章處理機(jī)調(diào)度第4章處理機(jī)調(diào)度4.1分級調(diào)度4.2作業(yè)調(diào)度4.3進(jìn)程調(diào)度4.4調(diào)度算法4.5算法評價(jià)4.6實(shí)時(shí)系統(tǒng)調(diào)度方法本章小結(jié)第2頁第四章處理機(jī)調(diào)度處理機(jī)調(diào)度要解決的問題WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)HOW：如何分配CPU—CPU調(diào)度過程（進(jìn)程的上下文切換）幾個(gè)常用的指標(biāo)衡量調(diào)度策略的最常用的幾個(gè)指標(biāo)是：周轉(zhuǎn)時(shí)間、吞吐率、響應(yīng)時(shí)間以及設(shè)備利用率等。周轉(zhuǎn)時(shí)間：指將一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。吞吐量：指在給定的時(shí)間內(nèi)，一個(gè)計(jì)算機(jī)系統(tǒng)所完成的總工作量。吞吐率：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，響應(yīng)時(shí)間：指從用戶向計(jì)算機(jī)發(fā)出一個(gè)命令到計(jì)算機(jī)把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時(shí)間。設(shè)備利用率：主要指輸入輸出設(shè)備的使用情況。第4頁第四章處理機(jī)調(diào)度主要內(nèi)容：

本章將以CPU管理為核心，討論管理、控制用戶進(jìn)程執(zhí)行的方法。作業(yè)與進(jìn)程的關(guān)系；作業(yè)調(diào)度策略與算法；進(jìn)程調(diào)度策略與算法；幾種調(diào)度策略的評價(jià)；實(shí)時(shí)調(diào)度系統(tǒng)。第5頁第四章處理機(jī)調(diào)度4.1分級調(diào)度

4.1.1作業(yè)的狀態(tài)及其轉(zhuǎn)換一個(gè)作業(yè)從提交給計(jì)算機(jī)系統(tǒng)到執(zhí)行結(jié)束退出系統(tǒng)，一般都要經(jīng)歷提交、收容、執(zhí)行和完成等4個(gè)狀態(tài)第6頁第四章處理機(jī)調(diào)度4.1.2調(diào)度的層次處理機(jī)調(diào)度問題實(shí)際上也是處理機(jī)的分配問題(1)作業(yè)調(diào)度：即高級調(diào)度（宏觀調(diào)度），又稱為"宏觀調(diào)度"、"高級調(diào)度"。從用戶工作流程的角度，一次提交的若干個(gè)流程，其中每個(gè)程序按照進(jìn)程調(diào)度。時(shí)間上通常是分鐘、小時(shí)或天(2)交換調(diào)度：中級調(diào)度，從存儲器資源的角度。將進(jìn)程的部分或全部換出到外存上，將當(dāng)前所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被CPU直接訪問。(3)進(jìn)程或線程調(diào)度：低級調(diào)度（微觀調(diào)度），又稱為"微觀調(diào)度"、"低級調(diào)度"。從CPU資源的角度，執(zhí)行的單位。時(shí)間上通常是毫秒。因?yàn)閳?zhí)行頻繁，要求在實(shí)現(xiàn)時(shí)達(dá)到高效率

注：在多道批處理系統(tǒng)中，存在著作業(yè)調(diào)度和進(jìn)程調(diào)度。但是，在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，一般不存在作業(yè)調(diào)度，而只有進(jìn)程調(diào)度、交換調(diào)度和線程調(diào)度第7頁第四章處理機(jī)調(diào)度處理機(jī)調(diào)度的層次處理器調(diào)度的層次

中級調(diào)度新建態(tài)掛起就緒態(tài)掛起等待態(tài)高級調(diào)度低級調(diào)度運(yùn)行態(tài)就緒態(tài)等待態(tài)終止態(tài)第9頁第四章處理機(jī)調(diào)度處理器的調(diào)度模型

中級調(diào)度處理器低級調(diào)度高級調(diào)度完成超時(shí)

掛起就緒隊(duì)列掛起等待隊(duì)列等待隊(duì)列就緒隊(duì)列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊(duì)列中級調(diào)度第10頁第四章處理機(jī)調(diào)度4.1.2作業(yè)與進(jìn)程作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體進(jìn)程是計(jì)算機(jī)為了完成用戶任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體，是系統(tǒng)分配資源的基本單位第11頁第四章處理機(jī)調(diào)度4.2作業(yè)調(diào)度作業(yè)調(diào)度主要是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)的轉(zhuǎn)變，以及從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變第12頁第四章處理機(jī)調(diào)度作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系

執(zhí)行狀態(tài)運(yùn)行就緒等待輸入狀態(tài)后備狀態(tài)完成狀態(tài)進(jìn)程調(diào)度中級調(diào)度緩輸出作業(yè)調(diào)度預(yù)輸入完成第13頁第四章處理機(jī)調(diào)度4.2.1作業(yè)調(diào)度的具體功能(1)記錄系統(tǒng)中各作業(yè)的狀況(JCB)(2)從后備隊(duì)列中挑選出一部分作業(yè)投入執(zhí)行(3)為被選中作業(yè)做好執(zhí)行前的準(zhǔn)備工作(4)在作業(yè)執(zhí)行結(jié)束時(shí)做善后處理工作第14頁第四章處理機(jī)調(diào)度圖4.3作業(yè)調(diào)度中狀態(tài)的轉(zhuǎn)換過程第15頁第四章處理機(jī)調(diào)度4.2.2作業(yè)調(diào)度目標(biāo)與性能衡量作業(yè)調(diào)度的功能最主要的是從后備作業(yè)隊(duì)列中選取一批作業(yè)進(jìn)入執(zhí)行狀態(tài)。調(diào)度目標(biāo)主要是以下4點(diǎn):(1)對所有作業(yè)應(yīng)該是公平合理的；(2)應(yīng)使設(shè)備有高的利用率；(3)每天執(zhí)行盡可能多的作業(yè)；(4)有較快的響應(yīng)時(shí)間。第16頁第四章處理機(jī)調(diào)度怎樣來衡量一個(gè)作業(yè)調(diào)度算法是否滿足系統(tǒng)設(shè)計(jì)的要求呢？批處理系統(tǒng)：由于主要用于計(jì)算，對于作業(yè)的周轉(zhuǎn)時(shí)間要求較高。因此，作業(yè)的平均周轉(zhuǎn)時(shí)間或平均帶權(quán)周轉(zhuǎn)時(shí)間，被作為衡量調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn)。主要考察系統(tǒng)的周轉(zhuǎn)時(shí)間。分時(shí)系統(tǒng)：主要考察系統(tǒng)的平均響應(yīng)時(shí)間。實(shí)時(shí)系統(tǒng)：主要考察系統(tǒng)對特定事件的響應(yīng)時(shí)間。因此，分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)來說，外加平均響應(yīng)時(shí)間被作為衡量調(diào)度策略優(yōu)劣的標(biāo)準(zhǔn)第17頁第四章處理機(jī)調(diào)度1.周轉(zhuǎn)時(shí)間：作業(yè)i的周轉(zhuǎn)時(shí)間Ti為

Ti=Tei-Tsi其中Tei為作業(yè)i的完成時(shí)間，Tsi為作業(yè)的提交時(shí)間。對于被測定作業(yè)流所含有的n（n>=1）個(gè)作業(yè)來說，其平均周轉(zhuǎn)時(shí)間為：一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間，包含兩部分：等待時(shí)間；執(zhí)行時(shí)間，即：

Ti=Twi＋Tri這里，Twi主要指作業(yè)i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時(shí)間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時(shí)間。第四章處理機(jī)調(diào)度第18頁2.帶權(quán)周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間包含了兩個(gè)部分，即等待時(shí)間和執(zhí)行時(shí)間。為了更進(jìn)一步反映調(diào)度性能，使用帶權(quán)周轉(zhuǎn)時(shí)間的概念。帶權(quán)周轉(zhuǎn)時(shí)間是作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)執(zhí)行時(shí)間的比：

Wi=Ti/Tri對于被測定作業(yè)流所含有的幾個(gè)作業(yè)來說，其平均帶權(quán)周轉(zhuǎn)時(shí)間為：對于分時(shí)系統(tǒng)，除了要保證系統(tǒng)吞吐量大、資源利用率高之外，還應(yīng)保證有用戶能夠容忍的響應(yīng)時(shí)間。因此，在分時(shí)系統(tǒng)中，僅僅用周轉(zhuǎn)時(shí)間或帶權(quán)周轉(zhuǎn)時(shí)間來衡量調(diào)度性能是不夠的。第四章處理機(jī)調(diào)度第19頁進(jìn)程調(diào)度的功能：調(diào)度程序(dispatcher)記錄所有進(jìn)程的運(yùn)行狀況（靜態(tài)和動態(tài)）當(dāng)進(jìn)程出讓CPU或調(diào)度程序剝奪執(zhí)行狀態(tài)進(jìn)程占用的CPU時(shí)，選擇適當(dāng)?shù)倪M(jìn)程分派CPU完成上下文切換4.3進(jìn)程調(diào)度4.3.1進(jìn)程調(diào)度的功能(1)記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況.（PCB）(2)選擇占有處理機(jī)的進(jìn)程調(diào)度的主要功能是按照一定的策略選擇一個(gè)處于就緒狀態(tài)的進(jìn)程，使其獲得處理機(jī)執(zhí)行。根據(jù)不同的系統(tǒng)設(shè)計(jì)目的，有各種各樣的選擇策略，例如系統(tǒng)開銷較少的靜態(tài)優(yōu)先數(shù)調(diào)度法，適合于分時(shí)系統(tǒng)的輪轉(zhuǎn)法和多級反饋輪轉(zhuǎn)法等。這些選擇策略決定了調(diào)度算法的性能(3)進(jìn)行進(jìn)程上下文切換一個(gè)進(jìn)程的上下文（context）包括進(jìn)程的狀態(tài)、有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值、硬件寄存器的值和PCB以及有關(guān)程序等第21頁第四章處理機(jī)調(diào)度4.3.2進(jìn)程調(diào)度的時(shí)機(jī)(1)正在執(zhí)行的進(jìn)程執(zhí)行完畢。(2)執(zhí)行中進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠等待狀態(tài)。(3)執(zhí)行中進(jìn)程調(diào)用了P原語操作，從而因資源不足而被阻塞；或調(diào)用了V原語操作激活了等待資源的進(jìn)程隊(duì)列。(4)執(zhí)行中進(jìn)程提出I／O請求后被阻塞。(5)在分時(shí)系統(tǒng)中時(shí)間片已經(jīng)用完。(6)在執(zhí)行完系統(tǒng)調(diào)用

以上都是在CPU執(zhí)行不可剝奪方式下所引起進(jìn)程調(diào)度的原因。在CPU執(zhí)行方式是可剝奪時(shí)。(7)就緒隊(duì)列中的某進(jìn)程的優(yōu)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級，從而也將引發(fā)進(jìn)程調(diào)度。第22頁第四章處理機(jī)調(diào)度4.3.3進(jìn)程的上下文切換過程：步驟：（1）決定是否做上下文切換（2）保存當(dāng)前進(jìn)程的上下文。（3）選擇進(jìn)程（4）恢復(fù)或裝配所選進(jìn)程的上下文，交CPU的控制權(quán)。如：用戶態(tài)執(zhí)行進(jìn)程A代碼－－進(jìn)入OS核心（通過時(shí)鐘中斷或系統(tǒng)調(diào)用）保存進(jìn)程A的上下文，恢復(fù)進(jìn)程B的上下文（CPU寄存器和一些表格的當(dāng)前指針）用戶態(tài)執(zhí)行進(jìn)程B代碼注：上下文切換之后，指令和數(shù)據(jù)快速緩存cache通常需要更新，執(zhí)行速度降低第四章處理機(jī)調(diào)度第23頁4.3.3進(jìn)程調(diào)度性能評價(jià)進(jìn)程調(diào)度是系統(tǒng)內(nèi)部的低級調(diào)度，進(jìn)程調(diào)度的優(yōu)劣直接影響作業(yè)調(diào)度的性能。反映作業(yè)調(diào)度優(yōu)劣的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間只在某種程度上反映了進(jìn)程調(diào)度的性能。進(jìn)程調(diào)度性能的衡量方法可分為定性和定量兩種。定性：可靠性（保證調(diào)度的順利進(jìn)行）和簡潔性（切換時(shí)間盡可能的短）定量：CPU的利用率評價(jià)、進(jìn)程在就緒隊(duì)列中的等待時(shí)間與執(zhí)行時(shí)間之比等。第24頁第四章處理機(jī)調(diào)度我們可從不同的角度來判斷處理機(jī)調(diào)度算法的性能，如用戶的角度、處理機(jī)的角度和算法實(shí)現(xiàn)的角度。實(shí)際的處理機(jī)調(diào)度算法選擇是一個(gè)綜合的判斷結(jié)果。周轉(zhuǎn)時(shí)間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。包括：在收容隊(duì)列中等待，CPU上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待－－批處理系統(tǒng)平均周轉(zhuǎn)時(shí)間T平均帶權(quán)周轉(zhuǎn)時(shí)間（帶權(quán)周轉(zhuǎn)時(shí)間W是T(周轉(zhuǎn))/T(CPU執(zhí)行)〕響應(yīng)時(shí)間：用戶輸入一個(gè)請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間－－分時(shí)系統(tǒng)截止時(shí)間：開始截止時(shí)間和完成截止時(shí)間－－實(shí)時(shí)系統(tǒng)，與周轉(zhuǎn)時(shí)間有些相似。公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過分惡化。如長作業(yè)等待很長時(shí)間。優(yōu)先級：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。1.面向用戶的調(diào)度性能準(zhǔn)則第25頁第四章處理機(jī)調(diào)度2.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐率：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng)平均周轉(zhuǎn)時(shí)間不是吞吐量的倒數(shù)，因?yàn)椴l(fā)執(zhí)行的作業(yè)在時(shí)間上可以重疊。如：在2小時(shí)內(nèi)完成4個(gè)作業(yè)，而每個(gè)周轉(zhuǎn)時(shí)間是1小時(shí)，則吞吐量是2個(gè)作業(yè)/小時(shí)處理機(jī)利用率：－－大中型主機(jī)各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時(shí)間短）的作業(yè)搭配－－大中型主機(jī)3.調(diào)度算法本身的調(diào)度性能準(zhǔn)則易于實(shí)現(xiàn)執(zhí)行開銷比第26頁第四章處理機(jī)調(diào)度4.4調(diào)度算法1.先來先服務(wù)（FCFS）調(diào)度算法2.輪轉(zhuǎn)法（roundrobin）3.多級反饋輪轉(zhuǎn)法4.優(yōu)先級法5.最短作業(yè)優(yōu)先法（shortestjobfirst）6.最短剩余時(shí)間優(yōu)先法7.最高響應(yīng)比優(yōu)先法（highestresponserationext）第27頁第四章處理機(jī)調(diào)度1.先來先服務(wù)（FCFS）調(diào)度算法

基本思想：將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理…ribpcbipcbjpcbk等待隊(duì)列頭指針可利用資源隊(duì)列頭指針資源分配程序入口地址后先按請求的先后次序第28頁第四章處理機(jī)調(diào)度按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當(dāng)前作業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進(jìn)程喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前作業(yè)或進(jìn)程出讓CPU。最簡單的算法。排序原則：按請求的先后次序排序。優(yōu)點(diǎn)：算法容易實(shí)現(xiàn)，是一種最普通和最簡單的方法。存在一定的公平性。缺點(diǎn)：效率不高，只顧及作業(yè)和進(jìn)程等候時(shí)間，沒考慮作業(yè)和進(jìn)程要求服務(wù)時(shí)間的長短。算法的特點(diǎn)：有利于長作業(yè)，不利于短作業(yè);有利于CPU繁忙的作業(yè),而不利于I/O繁忙的作業(yè)。算法適用對象：主要適用于作業(yè)和進(jìn)程的調(diào)度所帶來的問題：有一個(gè)作業(yè)長時(shí)間占有資源，其它作業(yè)沒有辦法執(zhí)行第29頁第四章處理機(jī)調(diào)度先來先服務(wù)算法舉例三個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并立即進(jìn)入調(diào)度：作業(yè)名/所需CPU時(shí)間:作業(yè)1/28，作業(yè)2/9，作業(yè)3/3。采用FCFS算法，平均作業(yè)周轉(zhuǎn)時(shí)間為：

35?若三個(gè)作業(yè)提交順序改為作業(yè)2、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間約為：

29若三個(gè)作業(yè)提交順序改為作業(yè)3、2、1，平均作業(yè)周轉(zhuǎn)時(shí)間約為：

18FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。第30頁第四章處理機(jī)調(diào)度例有5個(gè)任務(wù)A，B，C，D，E，它們幾乎同時(shí)到達(dá)，預(yù)計(jì)它們的運(yùn)行時(shí)間為10，6，2，4，8min。對于下列每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間（進(jìn)程切換開銷可不考慮）。先來先服務(wù)（按A，B，C，D，E）算法。采用先來先服務(wù)（FCFS）調(diào)度算法時(shí)，5個(gè)任務(wù)在系統(tǒng)中的執(zhí)行順序、完成時(shí)間及周轉(zhuǎn)時(shí)間如下表所示：執(zhí)行次序運(yùn)行時(shí)間等待時(shí)間周轉(zhuǎn)時(shí)間A10010B61016C21618D41822E82230執(zhí)行次序運(yùn)行時(shí)間優(yōu)先數(shù)等待時(shí)間周轉(zhuǎn)時(shí)間根據(jù)表中的計(jì)算結(jié)果，5個(gè)進(jìn)程的平均周轉(zhuǎn)時(shí)間T為：T=（10+16+18+22+30）/5=19.2min2.輪轉(zhuǎn)法（roundrobin）基本思想：系統(tǒng)把所有就緒進(jìn)程按先后次序排隊(duì)，處理機(jī)總是優(yōu)先分配給就緒隊(duì)列中的第一個(gè)就緒進(jìn)程，并分配它一個(gè)固定的時(shí)間片（如100毫秒）。當(dāng)該運(yùn)行進(jìn)程用完規(guī)定的時(shí)間片時(shí)，被迫釋放處理機(jī)給下一個(gè)處于就緒隊(duì)列中的第一個(gè)進(jìn)程，分給這個(gè)進(jìn)程相同的時(shí)間片，每個(gè)運(yùn)行完時(shí)間片的進(jìn)程，當(dāng)未遇到任何阻塞時(shí)，就回到就緒隊(duì)列的尾部，并等待下次轉(zhuǎn)到它時(shí)再投入運(yùn)行。優(yōu)點(diǎn)：防止那些很少使用外圍設(shè)備的進(jìn)程過長的占用處理器而使得要使用外圍設(shè)備的那些進(jìn)程沒有機(jī)會去啟動外圍設(shè)備。只要是處于就緒隊(duì)列中的進(jìn)程，按此種算法遲早總可以分得處理機(jī)投入運(yùn)行缺點(diǎn)：只能用來調(diào)度分配那些可以搶占的資源。算法適用對象：適用于進(jìn)程調(diào)度（分時(shí)系統(tǒng)），不能作業(yè)調(diào)度。第32頁第四章處理機(jī)調(diào)度時(shí)間片長度的選擇會直接影響系統(tǒng)開銷和響應(yīng)時(shí)間第33頁第四章處理機(jī)調(diào)度對響應(yīng)時(shí)間的要求：設(shè)時(shí)間片為t(恒定），進(jìn)程上下文切換時(shí)間為q,當(dāng)前進(jìn)程數(shù)為n,響應(yīng)時(shí)間為R，則有：R=（n-1)*(q+t)=n*(q+t);系統(tǒng)效率=q/(q+t)(1)如果時(shí)間片長度過短，則調(diào)度程序剝奪處理機(jī)的次數(shù)增多。使進(jìn)程上下文切換次數(shù)也大大增加，從而加重系統(tǒng)開銷。

(2)如果時(shí)間片長度選擇過長，比方說一個(gè)時(shí)間片能保證就緒隊(duì)列中所需執(zhí)行時(shí)間最長的進(jìn)程能執(zhí)行完畢，則輪轉(zhuǎn)法變成了先來先服務(wù)法。時(shí)間片長度的影響因素：就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越?。ó?dāng)響應(yīng)時(shí)間一定時(shí)）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長。第四章處理機(jī)調(diào)度第34頁如何確定時(shí)間片呢？

時(shí)間片長度的選擇是根據(jù)系統(tǒng)對響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)Nmax確定的。它可表示為：

q=R/Nmax例有5個(gè)任務(wù)A，B，C，D，E，它們幾乎同時(shí)到達(dá)，預(yù)計(jì)它們的運(yùn)行時(shí)間為10，6，2，4，8min。對于下列每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間（進(jìn)程切換開銷可不考慮）。時(shí)間片輪轉(zhuǎn)算法。如果系統(tǒng)采用時(shí)間片輪轉(zhuǎn)（RR）算法，令時(shí)間片為2分鐘，5個(gè)任務(wù)輪流執(zhí)行的情況為：第1輪：（A，B，C，D，E）第2輪：（A，B，D，E）第3輪：（A，B，E）第4輪：（A，E）第5輪：（A）顯然，5個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間為：T1=30min、T2=22min、T3=6min、T4=16min、T5=28min。它們的平均周轉(zhuǎn)時(shí)間T為：T=（30+22+6+16+28）/5=20.4min3.多級反饋輪轉(zhuǎn)法主要思想:

將就緒進(jìn)程分為兩級或多級，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)程隊(duì)列，較高優(yōu)先級的隊(duì)列一般分配給較短的時(shí)間片。分級輪轉(zhuǎn)法：將先前的一個(gè)就緒隊(duì)列，根據(jù)進(jìn)程的優(yōu)先級不同劃分兩個(gè)或兩個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先級，在同一隊(duì)列內(nèi)優(yōu)先級相同。當(dāng)一個(gè)進(jìn)程在執(zhí)行完它的時(shí)間片之后，或從睡眠中被喚醒以及被創(chuàng)建之后，將進(jìn)入不同的就緒隊(duì)列。特點(diǎn)：一個(gè)進(jìn)程在執(zhí)行結(jié)束之前需要通過反饋循環(huán)執(zhí)行第37頁第四章處理機(jī)調(diào)度多級反饋隊(duì)列的例子三個(gè)隊(duì)列:Q0

–

用RR調(diào)度算法，時(shí)間片為8毫秒Q1

–

用RR調(diào)度算法，時(shí)間片為16毫秒Q2

–FCFS調(diào)度方法新創(chuàng)建的進(jìn)程進(jìn)入隊(duì)列Q0，當(dāng)用輪轉(zhuǎn)法調(diào)度到它時(shí)，它最多可以執(zhí)行8milliseconds,如果沒有執(zhí)行完，該進(jìn)程將被放到隊(duì)列Q1.在隊(duì)列Q1

該進(jìn)程最多可以執(zhí)行16毫秒，如果還沒有執(zhí)行結(jié)束，則它就將進(jìn)入隊(duì)列

Q2.MultilevelFeedbackQueues4.優(yōu)先級

優(yōu)先級的方法可分為靜態(tài)法和動態(tài)法靜態(tài)法：根據(jù)作業(yè)或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級，一旦開始執(zhí)行之后就不能改變。動態(tài)法：把作業(yè)或進(jìn)程的靜態(tài)特性和動態(tài)特性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先級，隨著作業(yè)或進(jìn)程的執(zhí)行過程，其優(yōu)先級不斷變化第40頁第四章處理機(jī)調(diào)度靜態(tài)優(yōu)先級的確定原則作業(yè)調(diào)度：(1)由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(2)由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級。(3)系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級進(jìn)程調(diào)度：(1)按進(jìn)程的類型給予不同的優(yōu)先級(2)將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進(jìn)程的優(yōu)先級第41頁第四章處理機(jī)調(diào)度靜態(tài)優(yōu)先級使用外圍設(shè)備頻繁者優(yōu)先數(shù)大，這樣有利于提高效率；重要算題程序的進(jìn)程優(yōu)先數(shù)大，這樣有利于用戶；進(jìn)入計(jì)算機(jī)時(shí)間長的進(jìn)程優(yōu)先數(shù)大，這樣有利于縮短作業(yè)完成的時(shí)間；交互式用戶的進(jìn)程優(yōu)先數(shù)大，這樣有利于終端用戶的響應(yīng)時(shí)間等等優(yōu)點(diǎn)：調(diào)度算法實(shí)現(xiàn)簡單，系統(tǒng)開銷小缺點(diǎn)：系統(tǒng)效率較低，調(diào)度性能不高（靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變）第42頁第四章處理機(jī)調(diào)度動態(tài)優(yōu)先級的確定原則根據(jù)進(jìn)程占有CPU時(shí)間的長短來決定根據(jù)進(jìn)程占有CPU時(shí)間多少來決定,當(dāng)進(jìn)程占有CPU時(shí)間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之,進(jìn)程獲得調(diào)度的可能性越大根據(jù)就緒進(jìn)程等待CPU的時(shí)間長短來決定一個(gè)就緒進(jìn)程在就緒隊(duì)列中等待的時(shí)間越長，則它獲得調(diào)度選中的優(yōu)先級就越高

第43頁第四章處理機(jī)調(diào)度線性優(yōu)先級調(diào)度算法

（SRR,SelfishRoundRobin）就緒進(jìn)程隊(duì)列分成兩個(gè)：新創(chuàng)建進(jìn)程隊(duì)列：按FCFS方式排成；進(jìn)程優(yōu)先級按速率a增加；享受服務(wù)隊(duì)列：已得到過時(shí)間片服務(wù)的進(jìn)程按FCFS方式排成；進(jìn)程優(yōu)先級按速率b增加；新創(chuàng)建進(jìn)程等待時(shí)間的確定：當(dāng)新創(chuàng)建進(jìn)程優(yōu)先級與享受服務(wù)隊(duì)列中最后一個(gè)進(jìn)程優(yōu)先級相同時(shí)，轉(zhuǎn)入享受服務(wù)隊(duì)列；本算法是優(yōu)先級算法的一個(gè)實(shí)例，它通過進(jìn)程優(yōu)先級的遞增來改進(jìn)長執(zhí)行時(shí)間進(jìn)程的周轉(zhuǎn)時(shí)間特征。1.SRR算法第44頁第四章處理機(jī)調(diào)度SRR算法的優(yōu)先級變化第45頁第四章處理機(jī)調(diào)度SRR算法與FCFS算法和時(shí)間片輪轉(zhuǎn)算法的關(guān)系當(dāng)b>a>0時(shí)，享受服務(wù)隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程；SRR算法退化成FCFS算法；當(dāng)a>b=0時(shí)，SRR算法就是時(shí)間片輪轉(zhuǎn)算法；第46頁第四章處理機(jī)調(diào)度例有5個(gè)任務(wù)A，B，C，D，E，它們幾乎同時(shí)到達(dá)，預(yù)計(jì)它們的運(yùn)行時(shí)間為10，6，2，4，8min。其優(yōu)先級分別為3，5，2，1和4，這里5為最高優(yōu)先級。對于下列每一種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間（進(jìn)程切換開銷可不考慮）。--優(yōu)先級調(diào)度算法。執(zhí)行次序運(yùn)行時(shí)間優(yōu)先數(shù)等待時(shí)間周轉(zhuǎn)時(shí)間A103010B651016C221618D411822E842230采用最高優(yōu)先級調(diào)度（HPF）算法時(shí)，5個(gè)任務(wù)在系統(tǒng)中的執(zhí)行順序、完成時(shí)間及周轉(zhuǎn)時(shí)間如下表所示：執(zhí)行次序運(yùn)行時(shí)間優(yōu)先數(shù)等待時(shí)間周轉(zhuǎn)時(shí)間B6506E84614A1031424C222426D112627它們的平均周轉(zhuǎn)時(shí)間為：T=（6+14+24+26+27）/5=19.4min兩種算法綜合舉例：例:設(shè)有四個(gè)進(jìn)程P1，P2，P3，P4，它們達(dá)到就緒隊(duì)列的時(shí)刻、運(yùn)行時(shí)間及優(yōu)先級如下表所示：進(jìn)程到達(dá)就緒隊(duì)列時(shí)刻（基本時(shí)間單位）運(yùn)行時(shí)間（基本時(shí)間單位）優(yōu)先級P1091P2143P3282P43104

問:（1）若采用可剝奪的優(yōu)先級調(diào)度算法，給出各進(jìn)程的調(diào)度次序以及每個(gè)進(jìn)程的等待時(shí)間。（1）若采用可剝奪的優(yōu)先級調(diào)度算法，則進(jìn)程執(zhí)行模型為：調(diào)度次序：P1、P2、P4、P2、P3、P1；其中P1等待時(shí)間為：22，P2等待時(shí)間為：10，P3等待時(shí)間為：13，P4等待時(shí)間為：0。P4P3P2P101234567890123456789012345678905.最短作業(yè)優(yōu)先法（shortestjobfirst）主要思想：選擇那些估計(jì)需要執(zhí)行時(shí)間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。優(yōu)點(diǎn)：同一時(shí)間內(nèi)處理的作業(yè)個(gè)數(shù)最多，吞吐量大于其他調(diào)度方式缺點(diǎn)：對長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。第51頁第四章處理機(jī)調(diào)度最短作業(yè)優(yōu)先算法舉例四個(gè)作業(yè)同時(shí)到達(dá)系統(tǒng)并進(jìn)入調(diào)度：作業(yè)名/所需CPU時(shí)間:作業(yè)1/9，作業(yè)2，作業(yè)3/10，作業(yè)4/8。SJF作業(yè)調(diào)度順序?yàn)樽鳂I(yè)2、4、1、3，平均作業(yè)周轉(zhuǎn)時(shí)間T=17，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=1.98。如果實(shí)行FCFS調(diào)度算法，平均作業(yè)周轉(zhuǎn)時(shí)間T=19，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間

W=2.51。第52頁第四章處理機(jī)調(diào)度6.最短剩余時(shí)間優(yōu)先算法SRTF把SJF算法改為搶占式的。一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時(shí)間優(yōu)先算法此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。第53頁第四章處理機(jī)調(diào)度最短剩余時(shí)間優(yōu)先算法舉例四個(gè)作業(yè)其到達(dá)系統(tǒng)/所需CPU時(shí)間如下：Job1-0/8，Job2-1/4，Job3-2/9，Job4-3/5。SRTF調(diào)度平均等待時(shí)間=6.5毫秒。SJF調(diào)度平均等待時(shí)間=7.75毫秒。

J1J2J4J1J3015101726第54頁第四章處理機(jī)調(diào)度7.最高響應(yīng)比優(yōu)先法（highestresponseratiofirst）(HRRF)主要思想：同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長短和估計(jì)需要的執(zhí)行時(shí)間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行，是對FCFS方式和SJF方式的一種綜合平衡。優(yōu)點(diǎn)：同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長短和估計(jì)需要的執(zhí)行時(shí)間長短缺點(diǎn)：1、吞吐量小于最短作業(yè)優(yōu)先，

2、每次調(diào)度要計(jì)算響應(yīng)比，增加了系統(tǒng)的開銷響應(yīng)比的計(jì)算：響應(yīng)比R： R=(W+T)/T=1+W/T

其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。第55頁第四章處理機(jī)調(diào)度例有三個(gè)作業(yè)A（到達(dá)時(shí)間8:50，執(zhí)行時(shí)間1.5小時(shí)）、B（到達(dá)時(shí)間9:00，執(zhí)行時(shí)間0.4小時(shí)）、C（到達(dá)時(shí)間9:30，執(zhí)行時(shí)間1小時(shí)）。當(dāng)作業(yè)全部到達(dá)后，單道批處理系統(tǒng)按照響應(yīng)比高者優(yōu)先算法進(jìn)行調(diào)度，則作業(yè)被選中的次序是（）。

A．（ABC） B．（BAC）

C．（BCA） D．（CBA）

E．（CAB） F．（ACB）進(jìn)程到達(dá)時(shí)間運(yùn)行長度開始時(shí)間結(jié)束時(shí)間A8:501.59:3011:00B9:000.411:0011:24C9:30111:2412:24當(dāng)作業(yè)全部到達(dá)后，也就是9:30，系統(tǒng)開始調(diào)度。此刻各作業(yè)的等待時(shí)間是，A為40分鐘（0.67小時(shí)）、B為0.5小時(shí)、C為0小時(shí)。其響應(yīng)比分別為：A=1+0.67/1.5=1.4B=1+0.5/0.4=1.25C=1+0/1=1系統(tǒng)首先選A運(yùn)行，至11:00運(yùn)行結(jié)束。各作業(yè)的等待時(shí)間是，B為2小時(shí)，C為1.5小時(shí)。其響應(yīng)比分別修改為：B=1+2/0.4=6C=1+1.5/1=2.5系統(tǒng)再選B運(yùn)行，至11:24運(yùn)行結(jié)束。最后選擇C運(yùn)行至12:24結(jié)束。因此，本題的正確答案應(yīng)當(dāng)是AHRRF算法舉例

四個(gè)作業(yè)到達(dá)系統(tǒng)時(shí)間/所需CPU時(shí)間:作業(yè)1-0/20，作業(yè)2-5/15，作業(yè)3-10/5，作業(yè)4-15/10。SJF調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時(shí)間T=25，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=2.25

。FCFS調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時(shí)間T=28.75，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=3.125

。HRRF調(diào)度順序?yàn)樽鳂I(yè)1、3、4、2，平均作業(yè)周轉(zhuǎn)時(shí)間T=26.25，平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間W=2.46

。第58頁第四章處理機(jī)調(diào)度幾點(diǎn)說明I/O型進(jìn)程：讓其進(jìn)入最高優(yōu)先級隊(duì)列，以及時(shí)響應(yīng)I/O交互。通常執(zhí)行一個(gè)小時(shí)間片，要求可處理完一次I/O請求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊(duì)列。計(jì)算型進(jìn)程：每次都執(zhí)行完時(shí)間片，進(jìn)入更低級隊(duì)列。最終采用最大時(shí)間片來執(zhí)行，減少調(diào)度次數(shù)。I/O次數(shù)不多，而主要是CPU處理的進(jìn)程：在I/O完成后，放回優(yōu)先I/O請求時(shí)離開的隊(duì)列，以免每次都回到最高優(yōu)先級隊(duì)列后再逐次下降。為適應(yīng)一個(gè)進(jìn)程在不同時(shí)間段的運(yùn)行特點(diǎn)，I/O完成時(shí)，提高優(yōu)先級；時(shí)間片用完時(shí)，降低優(yōu)先級；第59頁第四章處理機(jī)調(diào)度調(diào)度算法性能分析FCFS,RoundRobin,線性優(yōu)先級算法SRR(SelfishRoundRobin)周轉(zhuǎn)時(shí)間長作業(yè)時(shí)：T(FCFS)<T(SRR)<T(RR)（運(yùn)行時(shí)間是主要因素）短作業(yè)時(shí)：T(RR)<T(SRR)<T(FCFS)（等待時(shí)間是主要因素）調(diào)度算法的性能通常是通過實(shí)驗(yàn)或計(jì)算得到的。第60頁第四章處理機(jī)調(diào)度4.6實(shí)時(shí)調(diào)度第61頁第四章處理機(jī)調(diào)度4.6.1實(shí)時(shí)調(diào)度的特點(diǎn)4.6.2實(shí)時(shí)調(diào)度算法

實(shí)時(shí)操作系統(tǒng)的特性實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。4.6.1實(shí)時(shí)調(diào)度的特點(diǎn)要求更詳細(xì)的調(diào)度信息：如，就緒時(shí)間、開始或完成截止時(shí)間、處理時(shí)間、資源要求、絕對或相對優(yōu)先級（硬實(shí)時(shí)或軟實(shí)時(shí)）。采用搶先式調(diào)度。快速中斷響應(yīng)，在中斷處理時(shí)（硬件）關(guān)中斷的時(shí)間盡量短?？焖偕舷挛那袚Q：相應(yīng)地采用較小的調(diào)度單位（如線程）。第四章處理機(jī)調(diào)度第63頁

硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)通常分為硬實(shí)時(shí)（hardrealtime）系統(tǒng)和軟實(shí)時(shí)（softrealtime）系統(tǒng)。硬實(shí)時(shí)系統(tǒng)意味著存在必須滿足的時(shí)間限制；軟實(shí)時(shí)系統(tǒng)允許系統(tǒng)對任務(wù)的時(shí)限要求有一定的延遲。意味著偶爾超過時(shí)間限制時(shí)可以容忍的。第64頁第四章處理機(jī)調(diào)度實(shí)時(shí)操作系統(tǒng)具有以下特點(diǎn)（1）有限等待時(shí)間（決定性）（2）有限響應(yīng)時(shí)間（3）用戶控制（4）可靠性高（5）系統(tǒng)出錯處理能力強(qiáng)第65頁第四章處理機(jī)調(diào)度實(shí)時(shí)操作系統(tǒng)應(yīng)具有以下能力(1)很快的進(jìn)程或線程切換速度進(jìn)程或線程切換速度是實(shí)時(shí)系統(tǒng)設(shè)計(jì)的核心。調(diào)度算法的設(shè)計(jì)原則是滿足所有硬實(shí)時(shí)任務(wù)的處理時(shí)限和盡可能多地滿足軟實(shí)時(shí)任務(wù)的處理時(shí)限。(2)快速的外部中斷響應(yīng)能力(3)基于優(yōu)先級的隨時(shí)搶先式調(diào)度策略第66頁第四章處理機(jī)調(diào)度基于優(yōu)先級的調(diào)度策略①優(yōu)先級+時(shí)間片輪轉(zhuǎn)調(diào)度策略；②基于優(yōu)先級的非搶先式調(diào)度策略；③基于優(yōu)先級的固定點(diǎn)搶先式調(diào)度策略；④基于優(yōu)先級的隨時(shí)搶先式調(diào)度策略。第67頁第四章處理機(jī)調(diào)度實(shí)時(shí)與分時(shí)的比較(1)分時(shí)系統(tǒng)中并發(fā)執(zhí)行的進(jìn)程具有不確定性，其執(zhí)行順序與執(zhí)行環(huán)境有關(guān);實(shí)時(shí)系統(tǒng)要求所有的進(jìn)程在處理事件時(shí)，都必須在有限時(shí)間內(nèi)開始處理。（實(shí)時(shí)系統(tǒng)的有限響應(yīng)時(shí)間特性是指從系統(tǒng)響應(yīng)外部事件開始，必須在有限時(shí)間內(nèi)處理完畢)(實(shí)時(shí)系統(tǒng)決定性特性）(2)在分時(shí)系統(tǒng)的非實(shí)時(shí)系統(tǒng)中，用戶不能參與對進(jìn)程調(diào)度的控制。在實(shí)時(shí)系統(tǒng)中，用戶可以控制進(jìn)程的優(yōu)先級并選擇相應(yīng)的調(diào)度算法，從而達(dá)到對進(jìn)程執(zhí)行先后順序的控制。(3)實(shí)時(shí)系統(tǒng)要求很高的可靠性。分時(shí)系統(tǒng)的非實(shí)時(shí)系統(tǒng)中，用戶可以用重新啟動計(jì)算機(jī)等來處理系統(tǒng)的差錯；實(shí)時(shí)系統(tǒng)主要是對外部事件進(jìn)行處理和控制。(4)實(shí)時(shí)系統(tǒng)要求系統(tǒng)在出錯時(shí)，既能夠處理所發(fā)生的錯誤，又不影響當(dāng)前正在執(zhí)行的用戶應(yīng)用第68頁第四章處理機(jī)調(diào)度實(shí)時(shí)調(diào)度算法的分類(1)靜態(tài)表格驅(qū)動類

調(diào)度方法多用于調(diào)度處理周期性任務(wù)，其主要分析參數(shù)為周期，執(zhí)行時(shí)間、周期行結(jié)束時(shí)限和任務(wù)優(yōu)先級等。適用于周期性的實(shí)時(shí)應(yīng)用，事先確定一個(gè)固定的調(diào)度方案。這種方法的特點(diǎn)是有效但不靈活。(2)靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類把通用的優(yōu)先級調(diào)度算法用于實(shí)時(shí)系統(tǒng)，但優(yōu)先級的確定是通過靜態(tài)分析（運(yùn)行時(shí)間、到達(dá)頻率）完成的。(3)動態(tài)計(jì)劃調(diào)度算法類(4)盡力而為調(diào)度算法類第69頁第四章處理機(jī)調(diào)度實(shí)時(shí)調(diào)度負(fù)責(zé)