【正文】 隨機性 – 周期性 : 每隔固定時間發(fā)生一次 – 隨機性 : 由隨機事件觸發(fā)，其發(fā)生時刻不確定 術(shù)語解釋 ? Ready time: 就緒時間 ? Starting deadline: 開始截止期 ? Processing time: 處理時間 ? Completion deadline: 完成截止期 ? Occurring frequency: 發(fā)生頻率 周期性實時事務(wù) ? 周期性實時事務(wù) : – 令 Ci為任務(wù) Pi處理時間， Ti為任務(wù) Pi的發(fā)生周期，則任務(wù) P1,… ,Pm可調(diào)度的必要條件為： 周期性實時事務(wù) ? 例： – T1=100, T2=200, T3=500 (ms) – C1=50, C2=30, C3=100 (ms) – C1/T1+C2/T2+C3/T3=++=1 – 滿足可調(diào)度的必要條件 周期性實時事務(wù) 進(jìn)程 就緒時間 處理時間 完成截止期 發(fā)生周期 A 0 10 20 20 B 0 25 50 50 10/20 + 25/50 = 1, 可調(diào)度 (不考慮開銷 ) 例子 Process Arrival time Execution time pletion deadline A(1) A(2) A(3) A(4) A(5) …... B(1) B(2) 0 20 40 60 80 …... 0 50 10 10 10 10 10 …… 25 25 20 40 60 80 100 …... 50 100 最早截止期調(diào)度 ? EDF（ Earliest Deadline First) – 優(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)先級 越高）。 ( ) ? 5. 搶占是指引起一個進(jìn)程暫時停止，以便運行另一個進(jìn)程。因此，在每個優(yōu)先級上都有一個 FIFO隊列，一個進(jìn)程可能在可變優(yōu)先級類中從一個隊列遷移到另一個隊列。 調(diào)度算法 簡單輪轉(zhuǎn)法 RR 處理器 就緒隊列 阻塞隊列 分派 釋放 超時 等待事件 事件發(fā)生 ?輪轉(zhuǎn)調(diào)度 ? 簡單輪轉(zhuǎn)法是以就緒隊列中的所有進(jìn)程均以相同的速度往前推進(jìn)為其特征。典型的調(diào)度類型有： ? 長程調(diào)度 (作業(yè)調(diào)度 ,高級調(diào)度）決定加入到待執(zhí)行的進(jìn)程池中 ? 中程調(diào)度 （交換調(diào)度 ,中級調(diào)度）將進(jìn)程調(diào)入內(nèi)存 ,或者將進(jìn)程交換到硬盤 ? 短程調(diào)度 （進(jìn)程調(diào)度，低級調(diào)度）決定哪一個就緒進(jìn)程將被處理器執(zhí)行 ? 線程調(diào)度 ：決定哪一個線程被處理器執(zhí)行 就緒 /掛起 新建 就緒 運行 退出 阻塞 短程調(diào)度 阻塞 /掛起 中程調(diào)度 長程調(diào)度 長程調(diào)度 中程調(diào)度 ?下一次允許哪一個進(jìn)程進(jìn)入的 決策 可以基于簡單的先來先服務(wù)原則，或者也可以基于管理系統(tǒng)性能的工具 ?使用的原則包括優(yōu)先級、期待執(zhí)行時間和 I/O需求 ?同樣，可以根據(jù)請求哪個 I/O資源和試圖平衡 I/O使用的目的進(jìn)行決策 長程調(diào)度 ?中程調(diào)度的目標(biāo)有 2個： ?解決內(nèi)存資源緊張的矛盾 ?減小并發(fā)度以降低系統(tǒng)開銷 ? 中程調(diào)度算法將結(jié)合存儲管理來設(shè)計。 – 帶權(quán)的周轉(zhuǎn)時間 W： 周轉(zhuǎn)時間與執(zhí)行時間的比值 – 響應(yīng)時間 從提交一個請求到開始處理的時間間隔。 ? 響應(yīng)比 R，代表了進(jìn)程的年齡，算法在保證短進(jìn)程優(yōu)先的同時又兼顧了長進(jìn)程 —— 折中 調(diào)度算法 ?最高響應(yīng)比優(yōu)先調(diào)度算法（ HRRN）