[計算機軟件及應(yīng)用]os-03中斷與處理機調(diào)度-資料下載頁
2025-04-14 00:42本頁面
【正文】 t) – 優(yōu)先選擇截止期最早的實時任務(wù) – 可搶先 ? 可以證明：對 EDF來說，可調(diào)度充分條件是： ? 在不可調(diào)度的條件下，可使錯過截止期任務(wù)最小化 11???mi iiTC例子 : Earliest Deadline First 0 10 20 30 40 50 60 70 80 90 100 Time A2 A2 dl A3 A3 dl A4 A4 dl B1 A1 A1dl B1 dl B2 B2 dl A5 A5 dl A1 B1 A2 B1 A3 B2 A5 B2 A4 A1 A2 B1 A3 A4 A5B2 速率單調(diào)調(diào)度 ? RMS（ Rate Monotonic Scheduling） – 提出于 1973年 ? 面向周期性實時事務(wù)，非剝奪式 ? 優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實時任務(wù) – 可調(diào)度條件： RMS的上限值 RMS vs. EDF 1) RMS可調(diào)度條件強于EDF 2) RMS調(diào)度較 EDF實現(xiàn)簡單 RMS例子： 進(jìn)程 Ｔ i Ci A 100 20 B 150 40 C 350 100 可調(diào)度，具體調(diào)度結(jié)果： A1 B1 C1 A2 B2 A3 A4 B3 C2 0 20 60 160 180 220 240 300 320 360 460 例題精選 ?假定要在一臺處理機上執(zhí)行右表作 業(yè)，且假定這些作業(yè)同時到達(dá)的次 序是 1, 2, 3, 4, 5， (數(shù)字越小優(yōu)先級 越高）。 – (1) 給出 Gantt圖說明分別使用 FCFS、 RR (時間片 =1) 、SPN以及非搶占優(yōu)先調(diào)度算法時這些作業(yè)的執(zhí)行情況。 – (2) 針對上述每一算法，給出每個作業(yè)周轉(zhuǎn)時間； – (3) 就上述每一算法，求出每個作業(yè)相應(yīng)的等待時間； – (4) 對所有作業(yè)而言，具有最小平均等待時間和最小周轉(zhuǎn)時間的調(diào)度算法各是哪一個？ 作業(yè) 執(zhí)行時間 優(yōu)先級 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 ? (1) 給出 Gantt圖說明分別 使用 FCFS、 RR (時間片 =1) 、 SPN以及非搶占優(yōu)先調(diào)度算法 時這些作業(yè)的執(zhí)行情況。 1(10) 2(1) 3(2) 4(1) 5(5) FCFS / RR 1 2 3 4 5 1 3 5 1 5 1 5 1 5 1（ 5） 2(1) 4(1) 3(2) 5(5) 1(10) SPN / Priority 2(1) 5(5) 1(10) 3(2) 4(1) 例題精選 作業(yè) 執(zhí)行時間 優(yōu)先級 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 例題精選 ? (2) 針對上述每一算法， 給出每個作業(yè)的周轉(zhuǎn)時間 。 作業(yè) 執(zhí)行時間 優(yōu)先級 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 作業(yè) FCFS RR SPN Priority 1 10 19 19 16 2 11 2 1 1 3 13 7 4 18 4 14 4 2 19 5 19 14 9 6 平均 7 12 例題精選 ? (3) 就每一算法，求出每 個作業(yè)相應(yīng)的等待時間 。 ? 解： 作業(yè) 執(zhí)行時間 優(yōu)先級 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 作業(yè) FCFS RR SPN Priority 1 0 9 9 6 2 10 1 0 0 3 11 5 2 16 4 13 3 1 18 5 14 9 4 1 平均 例題精選 ?敘述下列調(diào)度算法在支持短作業(yè)方面的差別： (1) FCFS； (2) RR； (3) Feedback (多級反饋調(diào)度 ) ? 解 : (1) FCFS—— 不怎么有利于短作業(yè)，因為在長作業(yè)之后到達(dá)的短作業(yè)將會等待較長的時間。 ? (2) RR—— 同等對待所有的作業(yè) (給它們分配相等的 CPU時間 ) ，因此，由于短作業(yè)將首先完成，所以短作業(yè)可以較快地離開系統(tǒng)。 ? (3) Feedback——— 比較有利于短作業(yè)，因為其工作方式類似于 RR算法。 例題精選 ?判斷題 (正確的在括號中記 ?， 錯誤的記 ) ? 1. 吞吐量是每單位時間所完成的作業(yè)個數(shù) 。 ( ) ? 2. 周轉(zhuǎn)時間 ＝ CPU忙碌時間 + 等待時間 。 ( ) ? 3. 確定時間片時 ， 使其稍大于進(jìn)程切換所需的時間 。 ( ) ? 4. 一個系統(tǒng)中通常有一到兩個設(shè)備隊列 。 ( ) ? 5. 搶占是指引起一個進(jìn)程暫時停止，以便運行另一個進(jìn)程。（ ） ?? ? 作 業(yè) ? 根據(jù)下表中的各進(jìn)程資料，結(jié)合不同的處理器調(diào)度算法：FCFS先來先服務(wù)、 RR輪轉(zhuǎn)、 SPN最短進(jìn)程、 SRTN最短剩余時間 ， HRRN最高響應(yīng)比優(yōu)先，多級反饋隊列 FB（共 3個就緒隊列， q＝ 2i，采用剝奪策略），畫出各進(jìn)程執(zhí)行流程圖 ，并計算 RR調(diào)度算法的平均周轉(zhuǎn)時間。 end
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1