計算機操作系統(tǒng)(第四章)

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

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

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

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

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

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

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

掛起就緒隊列掛起等待隊列等待隊列就緒隊列等待事件交互式用戶事件出現(xiàn)后備作業(yè)隊列中級調(diào)度第10頁第四章處理機調(diào)度4.1.2作業(yè)與進程作業(yè)是用戶向計算機提交任務(wù)的任務(wù)實體進程是計算機為了完成用戶任務(wù)實體而設(shè)置的執(zhí)行實體，是系統(tǒng)分配資源的基本單位第11頁第四章處理機調(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頁第四章處理機調(diào)度作業(yè)調(diào)度與進程調(diào)度的關(guān)系

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

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

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

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

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

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

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

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

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

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

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

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

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

–

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

–

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

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

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

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

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

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

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

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

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

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

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

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

A．（ABC） B．（BAC）

C．（BCA） D．（CBA）

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

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

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

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

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

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

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

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