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