【文章內(nèi)容簡(jiǎn)介】 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í)間片。時(shí)間片的長(zhǎng)度從幾個(gè) ms到幾百 ms； ? 在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷； ? 調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程； ? 進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓 CPU（如阻塞） 。 優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間 缺點(diǎn)：緊迫任務(wù)響應(yī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)。 ? 過(guò)短 － 用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)。 ?對(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)。 Page 67 2022/5/27 2. 多級(jí)隊(duì)列調(diào)度 前臺(tái) 的就緒隊(duì)列是交互性作業(yè)的進(jìn)程 ， 采用時(shí)間片輪轉(zhuǎn) 。 后臺(tái) 的就緒隊(duì)列是批處理作業(yè)的進(jìn)程 ， 采用優(yōu)先權(quán)或短作業(yè)優(yōu)先算法 。 調(diào)度方式有兩種： (1) 優(yōu)先調(diào)度前臺(tái) ， 若前臺(tái)無(wú)可運(yùn)行進(jìn)程 ， 才調(diào)度后臺(tái) 。 (2) 分配占用 CPU的時(shí)間比例 ， 如：前臺(tái) 80%， 后臺(tái) 20%。 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ⑥ Page 68 2022/5/27 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ?多級(jí)反饋隊(duì)列調(diào)度算法 ?設(shè)置 多個(gè)就緒隊(duì)列 ，并為各個(gè)隊(duì)列賦予 不同的優(yōu)先級(jí) ?第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低 ?該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行 時(shí)間片的大小也各不相同 ，在 優(yōu)先權(quán)愈高 的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行 時(shí)間片就愈小 。例如， 第二個(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。 （ 1） FCFS（ 先來(lái)先服務(wù)） （ 2） SJF（ 短作業(yè)優(yōu)先） （ 3） HRF（ 響應(yīng)比高者優(yōu)先） n n T=1/N（ ∑Ti） ,Ti=結(jié)束時(shí)刻 提交時(shí)刻 。 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)行。 ?當(dāng)作業(yè) 3完成時(shí)（ 10： 06），計(jì)算作業(yè) 4的響應(yīng)比： 作業(yè) 2響應(yīng)比 =（ 96+30） /30= 作業(yè) 4響應(yīng)比 =（ 36+12） /12=4 由于作業(yè) 2的響應(yīng)比大于作業(yè) 4，所以接著作業(yè) 2運(yùn)行；最后由作業(yè) 4運(yùn)行。 Page 79 2022/5/27 （ 3） HRF： 調(diào)度順序?yàn)?1 3 2 4 ? T=1/4（ 120+66+126+78） = ? W=1/4（ 1+11++） = 作業(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 2 8： 30 30 10： 36 126 4 9： 30 12 10： 48 78 Page 80 2022/5/27 （ 1）先來(lái)先服務(wù)算法 （ FCFS： First Come First Serve） （ 2）最短作業(yè)優(yōu)先算法 （ SJF： Shortest Job First） （ 3）最高響應(yīng)比優(yōu)先算法 （ HRN： Highest Response Ratio Next） 響應(yīng)比 R =（作業(yè)運(yùn)行時(shí)間 + 作業(yè)等待時(shí)間） / 作業(yè)運(yùn)行時(shí)間 = 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)。 ?實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動(dòng)駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒(méi)有響應(yīng)一樣糟糕。 Page 83 2022/5/27 實(shí)時(shí)任務(wù)的類型 ? 根據(jù)對(duì)截止時(shí)間的要求來(lái)劃分 ? 硬實(shí)時(shí)任務(wù) ：系統(tǒng)必須滿足任務(wù)對(duì)截止時(shí)間的要求，否則可能出現(xiàn)難以預(yù)測(cè)的結(jié)果； ? 軟實(shí)時(shí)任務(wù) ：它也聯(lián)系著一個(gè)截止時(shí)間，但并不嚴(yán)格，若偶爾超過(guò)時(shí)間限制也是可以容忍的。 ? 實(shí)時(shí)系統(tǒng)響應(yīng)的事件分為 ? 周期性實(shí)時(shí)任務(wù) ：要求按指定的周期循環(huán)執(zhí)行，以便周期性地控制某個(gè)外部事件； ? 非周期性實(shí)時(shí)任務(wù) ：任務(wù)的執(zhí)行無(wú)明顯的周期性，但都必須聯(lián)系著一個(gè)截止時(shí)間。 Page 84 2022/5/27 實(shí)時(shí)系統(tǒng)的特點(diǎn) ?有限等待時(shí)間 ?有限響應(yīng)時(shí)間 ?用戶控制 ?可靠性高 ?系統(tǒng)出錯(cuò)處理能力強(qiáng) Page 85 2022/5/27 對(duì)實(shí)時(shí)系統(tǒng)的要求 ?要求更詳細(xì)的調(diào)度信息：如，就緒時(shí)間、開(kāi)始或完成截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)（絕對(duì)優(yōu)先級(jí)或相對(duì)優(yōu)先級(jí)）； ?采用基于優(yōu)先級(jí)的隨時(shí)搶先式調(diào)度； ?快速中斷響應(yīng)，具有快速硬件中斷機(jī)構(gòu)，應(yīng)使禁止中斷的時(shí)間盡量短； ?快速上下文切換：相應(yīng)地采用較小的調(diào)度單位（如線程）。 Page 86 2022/5/27 ? 為了保證滿足實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求，實(shí)時(shí)系統(tǒng)必須具備足夠強(qiáng)的處理能力和快速的切換機(jī)制。 假定系統(tǒng)中有 m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為 Ci，周期時(shí)間表示為 Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件：才可能處理所有的負(fù)載。