[計(jì)算機(jī)軟件及應(yīng)用]os-03中斷與處理機(jī)調(diào)度-資料下載頁(yè)
2025-04-14 00:42本頁(yè)面
【正文】 t) – 優(yōu)先選擇截止期最早的實(shí)時(shí)任務(wù) – 可搶先 ? 可以證明：對(duì) EDF來(lái)說(shuō)，可調(diào)度充分條件是： ? 在不可調(diào)度的條件下，可使錯(cuò)過(guò)截止期任務(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年 ? 面向周期性實(shí)時(shí)事務(wù)，非剝奪式 ? 優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實(shí)時(shí)任務(wù) – 可調(diào)度條件： RMS的上限值 RMS vs. EDF 1) RMS可調(diào)度條件強(qiáng)于EDF 2) RMS調(diào)度較 EDF實(shí)現(xiàn)簡(jiǎ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 例題精選 ?假定要在一臺(tái)處理機(jī)上執(zhí)行右表作 業(yè)，且假定這些作業(yè)同時(shí)到達(dá)的次 序是 1, 2, 3, 4, 5， (數(shù)字越小優(yōu)先級(jí) 越高）。 – (1) 給出 Gantt圖說(shuō)明分別使用 FCFS、 RR (時(shí)間片 =1) 、SPN以及非搶占優(yōu)先調(diào)度算法時(shí)這些作業(yè)的執(zhí)行情況。 – (2) 針對(duì)上述每一算法，給出每個(gè)作業(yè)周轉(zhuǎn)時(shí)間； – (3) 就上述每一算法，求出每個(gè)作業(yè)相應(yīng)的等待時(shí)間； – (4) 對(duì)所有作業(yè)而言，具有最小平均等待時(shí)間和最小周轉(zhuǎn)時(shí)間的調(diào)度算法各是哪一個(gè)？ 作業(yè) 執(zhí)行時(shí)間 優(yōu)先級(jí) 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 ? (1) 給出 Gantt圖說(shuō)明分別 使用 FCFS、 RR (時(shí)間片 =1) 、 SPN以及非搶占優(yōu)先調(diào)度算法 時(shí)這些作業(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í)行時(shí)間 優(yōu)先級(jí) 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2 例題精選 ? (2) 針對(duì)上述每一算法， 給出每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間 。 作業(yè) 執(zhí)行時(shí)間 優(yōu)先級(jí) 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) 就每一算法，求出每 個(gè)作業(yè)相應(yīng)的等待時(shí)間 。 ? 解： 作業(yè) 執(zhí)行時(shí)間 優(yōu)先級(jí) 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 (多級(jí)反饋調(diào)度 ) ? 解 : (1) FCFS—— 不怎么有利于短作業(yè)，因?yàn)樵陂L(zhǎng)作業(yè)之后到達(dá)的短作業(yè)將會(huì)等待較長(zhǎng)的時(shí)間。 ? (2) RR—— 同等對(duì)待所有的作業(yè) (給它們分配相等的 CPU時(shí)間 ) ，因此，由于短作業(yè)將首先完成，所以短作業(yè)可以較快地離開(kāi)系統(tǒng)。 ? (3) Feedback——— 比較有利于短作業(yè)，因?yàn)槠涔ぷ鞣绞筋?lèi)似于 RR算法。 例題精選 ?判斷題 (正確的在括號(hào)中記 ?， 錯(cuò)誤的記 ) ? 1. 吞吐量是每單位時(shí)間所完成的作業(yè)個(gè)數(shù) 。 ( ) ? 2. 周轉(zhuǎn)時(shí)間 ＝ CPU忙碌時(shí)間 + 等待時(shí)間 。 ( ) ? 3. 確定時(shí)間片時(shí) ， 使其稍大于進(jìn)程切換所需的時(shí)間 。 ( ) ? 4. 一個(gè)系統(tǒng)中通常有一到兩個(gè)設(shè)備隊(duì)列 。 ( ) ? 5. 搶占是指引起一個(gè)進(jìn)程暫時(shí)停止，以便運(yùn)行另一個(gè)進(jìn)程。（ ） ?? ? 作 業(yè) ? 根據(jù)下表中的各進(jìn)程資料，結(jié)合不同的處理器調(diào)度算法：FCFS先來(lái)先服務(wù)、 RR輪轉(zhuǎn)、 SPN最短進(jìn)程、 SRTN最短剩余時(shí)間 ， HRRN最高響應(yīng)比優(yōu)先，多級(jí)反饋隊(duì)列 FB（共 3個(gè)就緒隊(duì)列， q＝ 2i，采用剝奪策略），畫(huà)出各進(jìn)程執(zhí)行流程圖 ，并計(jì)算 RR調(diào)度算法的平均周轉(zhuǎn)時(shí)間。 end
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1