【正文】 /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)度條件： )12(11 ????ninii nTCRMS的上限值 )12( /1 ?nnn 1 2 3 4 5 6 ┇ ? ┇ ln2? RMS vs. EDF 1) RMS可調(diào)度條件強于EDF 2) RMS調(diào)度較 EDF實現(xiàn)簡單 RMS例子： 進程 Ｔ i Ci A 100 20 B 150 40 C 350 100 7 7 )12(37 5 8 6 31 ????????? TCTCTC可調(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 多處理機調(diào)度 ? 問題： ? M processes (threads) ? N processors ? SMP： symmetric multiprocessors ? all processors are identical (homogeneous) ? 目標： loadsharing ? separate ready queue for each processor, ? not really balanced。 目態(tài)（ Pi運行） 目態(tài)（ Pj運行） 管態(tài) 管態(tài) …... 中斷 中斷 中斷 返回 返回 返回 Pi=Pj: 未發(fā)生進程切換； PiPj: 發(fā)生了進程切換。 ? 適應(yīng)系統(tǒng)： ? 分時 多級隊列算法 (MLQ) ? 多級隊列 ? 多個就緒隊列，進程所屬的隊列固定。 ? 調(diào)度時取 p_pri最小的。 ? 適合批處理進程 ? 動態(tài)優(yōu)先數(shù) (dynamic) ? 進程創(chuàng)建時繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。 短作業(yè)優(yōu)先 ? SJF（ Shortest Job First) ? 按 CPU burst長度 ? Process Arrival time Burst time ? P1 0 12 ? P2 0 5 ? P3 0 7 ? P4 0 3 ? Gantt Chart 0 3 8 15 27 P1 P2 P3 P4 短作業(yè)優(yōu)先 0 3 8 15 27 P1 P2 P3 P4 TW進程 到達時間 運行時間 開始時間 完成時間 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 P1 0 12 15 27 27 P2 0 5 3 8 8 P3 0 7 8 15 15 P4 0 3 0 3 3 1 平均周轉(zhuǎn)時間 =(27+8+15+3)/4= 平均帶權(quán)周轉(zhuǎn)時間 =(+++1)/4= 短作業(yè)優(yōu)先 ? 特點： ? 假定所有任務(wù)同時到達，平均等待時間最短。 剝奪式調(diào)度與非剝奪式調(diào)度 ? 剝奪式 (preemptive) ? 就緒進程 可以 從運行進程手中 搶占 CPU。 (min) 調(diào)度參數(shù) ?? ?? ?? ni iini i RTnWnW 11 )(1)(1??? ni iTnT 1 )(1RTW ?sf ttT ??周轉(zhuǎn)時間：完成時間 進入時間 平均周轉(zhuǎn)時間：周轉(zhuǎn)時間的平均值 帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間 /運行時間 平均帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間的平均值 CPU burst vs. I/O burst ? 陣發(fā)期 : ? CPU burst cycle: 進程 (線程 )使用 CPU計算； ? I/O burst cycle: 進程 (線程 )使用設(shè)備 I/O。 (max) ? 吞吐量 。 除 0中斷時轉(zhuǎn) LA處理 除 0中斷時轉(zhuǎn) LB處理 on divide_zero goto LB 除 0中 斷續(xù)元 除 0中 斷續(xù)元 LA: LB: 相同中斷發(fā)生在不同位置 可采用不同處理方法 應(yīng)用程序自行處理中斷 (Cont.) 編譯時：生成中斷續(xù)元表： 中斷續(xù)元入口 0 中斷續(xù)元入口 1 …… 中斷續(xù)元入口 n 中斷事件 0: 中斷事件 1: 中斷事件 n: …... 運行時：執(zhí)行調(diào)試語句，填寫中斷續(xù)元表。 中斷處理程序 強迫性中斷 自愿性中斷 保存現(xiàn)場信息 取中斷字 分析中斷原因 保存現(xiàn)場信息 取調(diào)用號 分析何種系統(tǒng)調(diào)用 中斷處理 （如等待轉(zhuǎn) dispatcher) 繼續(xù)處理 嵌套中斷 系統(tǒng)?；謴?fù)現(xiàn)場 返回上層中斷 需要切換進程 系統(tǒng)?；謴?fù)現(xiàn)場 返回目態(tài)程序 轉(zhuǎn) dispatcher T F F T IO中斷處理 ? 正常結(jié)束 ? 繼續(xù)傳輸； ? 喚醒相關(guān)進