【正文】 = 1 +（作業(yè)等待時(shí)間 / 作業(yè)運(yùn)行時(shí)間） （ 4）基于優(yōu)先數(shù)調(diào)度算法 （ HPF： Highest Priority First） 常見(jiàn)的作業(yè)調(diào)度算法 Page 81 2022/5/27 實(shí)時(shí)調(diào)度 ?實(shí)時(shí)系統(tǒng) ?實(shí)時(shí)系統(tǒng)的特點(diǎn) ?對(duì)實(shí)時(shí)系統(tǒng)的要求 ?實(shí)時(shí)調(diào)度算法 Page 82 2022/5/27 ?實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。 W=1/N（ ∑Wi） , Wi= Ti /作業(yè) i 實(shí)際執(zhí)行時(shí)間 i=1 i=1 作業(yè)號(hào) 提交時(shí)刻 運(yùn)行時(shí)間（分鐘） 1 8： 00 120 2 8： 30 30 3 9： 00 6 4 9： 30 12 Page 76 2022/5/27 （ 1） FCFS： 調(diào)度順序?yàn)?1 2 3 4 ? T=1/4（ 120+120+96+78） = ? W=1/4（ 1+4+16+） = 作業(yè)號(hào) 到達(dá)時(shí)刻 要求運(yùn)行時(shí)間 （分鐘） 結(jié)束時(shí)刻 周轉(zhuǎn)時(shí)間 Ti（ 分鐘） 帶權(quán)周轉(zhuǎn)時(shí)間 Wi 1 8： 00 120 10： 00 120 1 2 8： 30 30 10： 30 120 4 3 9： 00 6 10： 36 96 16 4 9： 30 12 10： 48 78 Page 77 2022/5/27 （ 2） SJF(SPF)： 調(diào)度順序?yàn)?1 3 4 2 ?T=1/4（ 120+66+48+138） =93分鐘 ?W=1/4（ 1+11+4+） = 作業(yè)號(hào) 到達(dá)時(shí)刻 要求運(yùn)行時(shí)間 （分鐘） 結(jié)束時(shí)刻 周轉(zhuǎn)時(shí)間 Ti（ 分鐘） 帶權(quán)周轉(zhuǎn)時(shí)間 Wi 1 8： 00 120 10： 00 120 1 3 9： 00 6 10： 06 66 11 4 9： 30 12 10： 18 48 4 2 8： 30 30 10： 48 138 Page 78 2022/5/27 ?（ 3） HRF ?作業(yè) 1最先到達(dá)并運(yùn)行，當(dāng)作業(yè) 1 完成時(shí)（ 10： 00），作業(yè) 4都到達(dá)，則計(jì)算它們的響應(yīng)比 ： 作業(yè) 2響應(yīng)比 =（ 90+30） /30=4 作業(yè) 3響應(yīng)比 =（ 60+6） /6=11 作業(yè) 4響應(yīng)比 =（ 30+12） /12= 由于作業(yè) 3的響應(yīng)比最高，所以作業(yè) 3先運(yùn)行。例如， 第二個(gè) 隊(duì)列的時(shí)間片要 比第一個(gè) 隊(duì)列的時(shí)間片 長(zhǎng)一倍 ， ……，第 i+1個(gè)隊(duì)列的時(shí)間片要比第 i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍 ⑦ Page 69 2022/5/27 就緒隊(duì)列 1 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 就緒隊(duì)列 2 就緒隊(duì)列 3 就緒隊(duì)列 n S 1 S 2 S 3 至 CPU 至 CPU 至 CPU 至 CPU (時(shí)間片： S 1 ＜ S 2 ＜ S 3 ) ?調(diào)度方式 高 低 優(yōu)先級(jí) 時(shí)間片 小 大 S n 按 FIFO原則排隊(duì)等待調(diào)度 尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按FIFO原則等待調(diào)度 采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行 因等待而放棄 CPU后，進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列 Page 70 2022/5/27 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ?注意 ? 僅當(dāng)?shù)?1~(i1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第 i隊(duì)列中的進(jìn)程運(yùn)行 ? 第 i隊(duì)列 中某進(jìn)程正在運(yùn)行時(shí)，又有 新 進(jìn)程進(jìn)入 優(yōu)先權(quán)較高 的隊(duì)列 (第 1~(i1)中的任何一個(gè)隊(duì)列 )，則此時(shí) 新進(jìn)程將搶占 正在運(yùn)行進(jìn)程的處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程 放回到第 i隊(duì)列 的末尾 ? 第 i隊(duì)列 中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，調(diào)度程序把進(jìn)程 放回到第 i隊(duì)列 的末尾 Page 71 2022/5/27 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ?多級(jí)反饋隊(duì)列調(diào)度算法的性能 ?終端型作業(yè)用戶 ? 終端型作業(yè)用戶所提交的作業(yè)多屬于 交互型 作業(yè)，通常 較小 ，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所 規(guī)定的時(shí)間片內(nèi)完成 即可 ?短批處理作業(yè)用戶 ? 若在第 1隊(duì)列中執(zhí)行 一個(gè)時(shí)間片 即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間 ? 如在第一個(gè)隊(duì)列中不能完成，只需在第 3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片 ?長(zhǎng)批處理作業(yè)用戶 ? 長(zhǎng)作業(yè)將依次在第 1， 2， 3… ， n隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行 Page 72 2022/5/27 進(jìn)程調(diào)度 要解決的問(wèn)題 WHAT：按什么原則分配 CPU — 進(jìn)程調(diào)度算法 WHEN：何時(shí)分配 CPU — 進(jìn)程調(diào)度的時(shí)機(jī) HOW： 如何分配 CPU — CPU調(diào)度過(guò)程（進(jìn)程的上下文切換） Page 73 2022/5/27 補(bǔ)充 :進(jìn)程調(diào)度的時(shí)機(jī) ?當(dāng)一個(gè)進(jìn)程 運(yùn)行完畢 或由于某種錯(cuò)誤而終止運(yùn)行 ?當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于 等待 狀態(tài)（等待 I/O） ?分時(shí)系統(tǒng)中 時(shí)間片到 ?當(dāng)有一個(gè) 優(yōu)先級(jí)更高 的進(jìn)程就緒（可搶占式） 例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒 ?在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（ P操作，阻塞原語(yǔ)，喚醒原語(yǔ)） Page 74 2022/5/27 * 保存現(xiàn)場(chǎng) ：順序保存，最后一步保存PSW * 選擇要運(yùn)行的程序 （如果沒(méi)有就緒進(jìn)程 ,系統(tǒng)會(huì)安排一個(gè) 閑逛進(jìn)程 (idle)， 沒(méi)有其他進(jìn)程時(shí)該進(jìn)程一直運(yùn)行 ,在執(zhí)行過(guò)程中可接收中斷） * 恢復(fù)現(xiàn)場(chǎng)： 最后一步恢復(fù)選中進(jìn)程的PSW 補(bǔ)充：調(diào)度的實(shí)施過(guò)程 CPU調(diào)度過(guò)程 Page 75 2022/5/27 課堂練習(xí) : 假如有 4道作業(yè)，它們的提交時(shí)間及運(yùn)行時(shí)間如下表所示： 采用單道運(yùn)行，試問(wèn)下述調(diào)度算法下，它們的調(diào)度順序，并分別計(jì)算各調(diào)度算法下三個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間 T 和平均帶權(quán)周轉(zhuǎn)時(shí)間 W。 (2) 分配占用 CPU的時(shí)間比例 ， 如：前臺(tái) 80%， 后臺(tái) 20%。 后臺(tái) 的就緒隊(duì)列是批處理作業(yè)的進(jìn)程 ， 采用優(yōu)先權(quán)或短作業(yè)優(yōu)先算法 。 ?對(duì)響應(yīng)時(shí)間的要求： ? R(響應(yīng)時(shí)間 )=Nmax(進(jìn)程數(shù)目 )*q(時(shí)間片 ) ?時(shí)間片長(zhǎng)度的影響因素： ? 就緒進(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í)間延長(zhǎng)。 UNIX中采用：時(shí)間片 +優(yōu)先權(quán) ⑤ Page 65 2022/5/27 進(jìn)程名 到達(dá)時(shí)間 服務(wù)時(shí)間 開(kāi)始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周 轉(zhuǎn)時(shí)間 平均 A B C D E A B C D E A B C E A C E C 0 5 10 15 18 t 0 4 A 0 3 B 0 5 C 0 2 D 0 4 E 0 1 2 3 4 9 12 15 17 18 15 15/4 11 11/3 16 16/5 6 6/2 13 13/4 若到達(dá)時(shí)間為 0、 4，又如何？ Page 66 2022/5/27 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ?時(shí)間片長(zhǎng)度變化的影響 ? 過(guò)長(zhǎng) － 退化為 FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。 優(yōu)點(diǎn)：公平。 ④ 響應(yīng)比 Rp定義如下： Rp=作業(yè)響應(yīng)時(shí)間 tR /要求執(zhí)行的時(shí)間 Page 63 2022/5/27 調(diào)度算法 ?先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法 ?高優(yōu)先權(quán)優(yōu)先調(diào)度算法 ?基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 Page 64 2022/5/27 ? 簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法 (RR— Round Robin)將系統(tǒng)中所有的就緒進(jìn)程按照 FCFS原則，排成一個(gè)隊(duì)列； ? 每次調(diào)度時(shí)將 CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如， 0?7或 0?255， 又把該整數(shù)稱(chēng)為 優(yōu)先數(shù) ?確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù) ? 進(jìn)程類(lèi)型 :系統(tǒng)進(jìn)程，用戶進(jìn)程 ? 進(jìn)程對(duì)資源的需求 (對(duì) CPU和內(nèi)存需求較少的進(jìn)程，優(yōu)先級(jí)較高 ) ? 用戶要求 （緊迫程度和付費(fèi)多少） Page 60 2022/5/27 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 ?動(dòng)態(tài)優(yōu)先權(quán) ? 在 創(chuàng)建進(jìn)程 時(shí)賦予的優(yōu)先級(jí)，在進(jìn)程 運(yùn)行過(guò)程中可以自動(dòng)改變 ，以便獲得更好的調(diào)度性能。 ?缺點(diǎn) ： ?對(duì)長(zhǎng)作業(yè)非常不利 ，可能長(zhǎng)時(shí)間得不到執(zhí)行； ?未能依據(jù)作業(yè)的 緊迫程度 來(lái)劃分執(zhí)行的優(yōu)先級(jí)； ?難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間 ，從而影響調(diào)度性能。 A．周轉(zhuǎn)時(shí)間 B、響應(yīng)時(shí)間 C、等待時(shí)間 D、觸發(fā)時(shí)間 ?在批處理系統(tǒng)中，周轉(zhuǎn)時(shí)間是（ ）。 Page 39 2022/5/27 可把平均周轉(zhuǎn)時(shí)間描述為 ： ??????? ??iiiTnT11??????? ??ni SiiTTnW11 作業(yè)的周轉(zhuǎn)時(shí)間 T與系統(tǒng)為它提供服務(wù)的時(shí)間 TS之比 ，即 W=T/TS， 稱(chēng)為 帶權(quán)周轉(zhuǎn)時(shí)間 ， 而 平均帶權(quán)周轉(zhuǎn)時(shí)間 則可表示為 : 系統(tǒng)以多個(gè)用戶都滿意為目標(biāo) 周轉(zhuǎn)時(shí)間＝服務(wù)時(shí)間 周轉(zhuǎn)時(shí)間＝完成時(shí)間－到達(dá)時(shí)間 Page 40 2022/5/27 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 ?面向用戶的準(zhǔn)則 ?響應(yīng)時(shí)間快 ? 響應(yīng)時(shí)間 是指從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)中 首次 產(chǎn)生 響應(yīng) 為止的時(shí)間 ?截止時(shí)間保證 ? 截止時(shí)間 是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間 ? 截止時(shí)間是 實(shí)時(shí)系統(tǒng) 中的重要指標(biāo) Page 41 2022/5/27 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 ?面向用戶的準(zhǔn)則 ?等待時(shí)間短 ? 等待時(shí)間 是在就緒隊(duì)列中等待所花的時(shí)間 ? 調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行 I/O的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間 ?優(yōu)先權(quán)準(zhǔn)則 ? 在 批處理 、 實(shí)時(shí) 和 分時(shí)系統(tǒng) 中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理 ? 有時(shí)還選擇搶占式調(diào)度方式 Page 42 2022/5/27 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 ?面向系統(tǒng)的準(zhǔn)則 ?系統(tǒng)吞吐量高 ? 吞吐量 指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù) ? 作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較大影響 ?處理機(jī)利用率高 ?各類(lèi)資源的平衡利用 ? 使內(nèi)存、外存和 I/O設(shè)備的利用率高 基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？ Page 43 2022/5/27 ? （ ）是指從作業(yè)提交給系統(tǒng)到作業(yè)完成的時(shí)間間隔。 它包括： (1)作業(yè)在外存后備隊(duì)列上等待 (作業(yè) )調(diào)度的時(shí)間； (2)進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間； (3)進(jìn)程在 CPU上執(zhí)行的時(shí)間； (4)等待 I／ O操作完成的時(shí)間 。而 平均帶權(quán)周轉(zhuǎn)時(shí)間 則可表示為 : Page 38 2022/5/27 通常把 周轉(zhuǎn)時(shí)間 作為評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的準(zhǔn)則。 (4) 優(yōu)先權(quán)準(zhǔn)則。 (2) 響應(yīng)時(shí)間快。 A、后備 B、阻塞 C、執(zhí)行 D、完成 Page 19 2022/5/27 ? 高級(jí)、中級(jí)和低級(jí)調(diào)度 ? 進(jìn)程調(diào)度的任務(wù) ? 確定算法的原則 ? 進(jìn)程調(diào)度方式 ? 調(diào)度隊(duì)列模型 ? 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 Page 20 2022/5/27 進(jìn)程調(diào)度的任務(wù) ? 進(jìn)程調(diào)度的任務(wù) 是 控制、協(xié)調(diào)進(jìn)程 對(duì) CPU的競(jìng)爭(zhēng) ,即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把 CPU的使用權(quán)交給被選中的進(jìn)程 Page 21 2022/5/27 處理機(jī)調(diào)度的基本概念 ? 高級(jí)、中級(jí)和低級(jí)調(diào)度 ? 進(jìn)程調(diào)度的任務(wù) ? 確定算法的原則 ? 進(jìn)程調(diào)度方式 ? 調(diào)度隊(duì)列模型 ? 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 Page 22 2022/5/27 確定算法的原則 ? 具有 公平性 ? 資源 利用率高 （特別是 CPU利用率） ? 在交互式系統(tǒng)情況下要追求 響應(yīng)時(shí)間（越短越好）