中斷與處理機(jī)調(diào)度

《中斷與處理機(jī)調(diào)度》由會(huì)員分享，可在線閱讀，更多相關(guān)《中斷與處理機(jī)調(diào)度（73頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、3.2 處 理 機(jī) 調(diào) 度 3.2.1 處 理 機(jī) 調(diào) 度 算 法n 考 慮 因 素 （ scheduling criteria）n CPU利 用 率 ; (max)n 吞 吐 量 ; (max)n 周 轉(zhuǎn) 時(shí) 間 ; (min)n 響 應(yīng) 時(shí) 間 ; (min)n 系 統(tǒng) 開(kāi) 銷 ; (min) 調(diào) 度 參 數(shù) ni iini i RTnWnW 11 )(1)(1 ni iTnT 1 )(1 RTW 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í) 間平 均 帶

2、 權(quán) 周 轉(zhuǎn) 時(shí) 間 ： 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 的 平 均 值 CPU burst vs. I/O burst n 陣 發(fā) 期 :n CPU burst cycle: 進(jìn) 程 (線 程 )使 用 CPU計(jì) 算 ；n I/O burst cycle: 進(jìn) 程 (線 程 )使 用 設(shè) 備 I/O。n 進(jìn) 程 運(yùn) 行 行 為 ：n CPU burst, I/O burst, CPU burst, I/O burst, n CPU調(diào) 度 ： 考 慮 處 于 CPU burst進(jìn) 程 集 合 n CPU burst時(shí) 間 根 據(jù) 以 前 行 為 推 定 。 CPU burst vs. I/O burs

3、tn 下 一 個(gè) CPU burst的 長(zhǎng) 度 估 算n 令 n是 估 計(jì) 的 第 n個(gè) CPU陣 發(fā) 期 的 長(zhǎng) 度 ， tn的 值 是 進(jìn) 程 最 近 一 次 CPU陣 發(fā) 期 長(zhǎng) 度 ， 則 有如 下 估 算 公 式 ：n n+1=tn + (1-)nn 參 數(shù) (01)控 制 tn和 n在 公 式 中 起 的 作 用 ：當(dāng) =0時(shí) ， n+1=n； 當(dāng) =1時(shí) ， n+1=tn。通 常 取 0.5。 剝 奪 式 調(diào) 度 與 非 剝 奪 式 調(diào) 度n 剝 奪 式 (preemptive)n 就 緒 進(jìn) 程 可 以 從 運(yùn) 行 進(jìn) 程 手 中 搶 占 CPU。n 進(jìn) 程 運(yùn) 行 ,直 到

4、結(jié) 束 、 等 待 或 被 搶 先n 非 剝 奪 式 (non-preemptive)n 就 緒 進(jìn) 程 不 可 從 運(yùn) 行 進(jìn) 程 手 中 搶 占 CPU。 n 進(jìn) 程 運(yùn) 行 ,直 到 結(jié) 束 或 等 待 3.2.1.1 先 到 先 服 務(wù) 算 法n FCFS（ First Come First Serve)n 按 進(jìn) 程 申 請(qǐng) CPU（ 就 緒 ） 的 次 序 。n Process Arrival time Burst timen P1 0 27 n P2 1 3n P3 2 5n CPU調(diào) 度 狀 況 可 用 Gantt 圖 表 示 0 27 30 35P1 P2 P3 3.2.1.

5、1 先 到 先 服 務(wù) 算 法 (Cont.)進(jìn) 程 到 達(dá) 時(shí) 間 運(yùn) 行 時(shí) 間 開(kāi) 始 時(shí) 間 完 成 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間P 1 0 27 0 27 27 1P2 1 3 27 30 29 9.67P3 2 5 30 35 33 6.6平 均 周 轉(zhuǎn) 時(shí) 間 =(27+29+33)/3=29.67 平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 =(1+9.67+6.6)/3=5.76 T W0 27 30 35P1 P2 P3 3.2.1.1 先 到 先 服 務(wù) 算 法 (Cont.)n 優(yōu) 點(diǎn) ：n “ 公 平 ” ；n 缺 點(diǎn) :n 短 作 業(yè) 等 待 時(shí) 間 長(zhǎng) 。

6、3.2.1.2 短 作 業(yè) 優(yōu) 先n SJF（ Shortest Job First)n 按 CPU burst長(zhǎng) 度n Process Arrival time Burst time n P1 0 12n P2 0 5n P3 0 7n P4 0 3n Gantt Chart0 3 8 15 27P1P2 P3P4 3.2.1.2 短 作 業(yè) 優(yōu) 先0 3 8 15 27P1P2 P3P4 T W進(jìn) 程 到 達(dá) 時(shí) 間 運(yùn) 行 時(shí) 間 開(kāi) 始 時(shí) 間 完 成 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間P1 0 12 15 27 27 2.25P2 0 5 3 8 8 1.6P3 0 7

7、8 15 15 2.14P4 0 3 0 3 3 1平 均 周 轉(zhuǎn) 時(shí) 間 =(27+8+15+3)/4=13.25 平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 =(2.25+1.6+2.14+1)/4=1.75 3.2.1.2 短 作 業(yè) 優(yōu) 先n 特 點(diǎn) ：n 假 定 所 有 任 務(wù) 同 時(shí) 到 達(dá) ， 平 均 等 待時(shí) 間 最 短 。n 長(zhǎng) 作 業(yè) 可 能 被 餓 死 。 3.2.1.3 最 短 剩 余 時(shí) 間 優(yōu) 先 算 法 (SRTN)n Shortest Remaining Time Nextn 可 剝 奪 SJFn Process Arrival time Burst timen P1 0

8、12n P2 1 9 n P3 3 6n P4 5 3n Gantt圖P1 P2 P3 P4 P3 P2 P10 1 3 5 8 12 19 30 3.2.1.3 最 短 剩 余 時(shí) 間 優(yōu) 先 算 法 (Cont.)進(jìn) 程 到 達(dá) 時(shí) 間 運(yùn) 行 時(shí) 間 開(kāi) 始 時(shí) 間 完 成 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間P1 0 12 0 30 30 2.5P2 1 9 1 19 18 2P 3 3 6 3 12 9 1.5P4 5 3 5 8 3 1平 均 周 轉(zhuǎn) 時(shí) 間 =(30+18+9+3)/4=15平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 =(2.5+2+1.5+1)/4=1.75 平

9、均 等 待 時(shí) 間 (18+9+3+0)/ 4 7.5(ms)P1 P2 P3 P4 P3 P2 P10 1 3 5 8 12 19 30 3.2.1.4最 高 響 應(yīng) 比 優(yōu) 先 (HRN)n Highest Response Ratio Nextn RR=(BT+WT)/BT=1+WT/BTn 其 中 :n BT=burst time n WT=wait timen 優(yōu) 點(diǎn) :n 同 時(shí) 到 達(dá) 任 務(wù) , 短 者 優(yōu) 先n 長(zhǎng) 作 業(yè) 隨 等 待 時(shí) 間 增 加 響 應(yīng) 比 增 加 3.2.1.5 最 高 優(yōu) 先 數(shù) 算 法 (HPF)n 靜 態(tài) 優(yōu) 先 數(shù) (static)n 優(yōu) 先

10、數(shù) 在 進(jìn) 程 創(chuàng) 建 時(shí) 分 配 ， 生 存 期 內(nèi) 不 變 。n 響 應(yīng) 速 度 慢 ， 開(kāi) 銷 小 。n 適 合 批 處 理 進(jìn) 程n 動(dòng) 態(tài) 優(yōu) 先 數(shù) (dynamic) n 進(jìn) 程 創(chuàng) 建 時(shí) 繼 承 優(yōu) 先 數(shù) ， 生 存 期 內(nèi) 可 以 修 改 。n 響 應(yīng) 速 度 快 ， 開(kāi) 銷 大 。 3.2.1.5 最 高 優(yōu) 先 數(shù) 算 法 (Cont.)n 非 剝 奪 式 優(yōu) 先 數(shù)n 獲 得 處 理 機(jī) 的 進(jìn) 程 運(yùn) 行 ， 直 至n 終 止n 等 待n 剝 奪 式 優(yōu) 先 數(shù)n 獲 得 處 理 機(jī) 的 進(jìn) 程 運(yùn) 行 ， 直 至 n 終 止n 等 待n 出 現(xiàn) 高 優(yōu) 先 級(jí)

11、的 進(jìn) 程 3.2.1.5 最 高 優(yōu) 先 數(shù) 算 法 (Cont.)n 可 搶 占 CPUn Process Arrival time Priority Burst timen P1 0 0 8n P2 2 1 5 n P3 4 3 7n P4 0 2 3n P5 5 7 2n Gantt Chart0 3 4 5 7 13 17 25P1P4 P2P2 P3P3 P5 3.2.1.5 最 高 優(yōu) 先 數(shù) 算 法 (Cont.) T W進(jìn) 程 到 達(dá) 時(shí) 間 運(yùn) 行 時(shí) 間 優(yōu) 先 級(jí) 開(kāi) 始 時(shí) 間 完 成 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間P1 0 8 0 17 25 25

12、3.13P2 2 5 1 3 17 15 3P3 4 7 3 4 13 9 1.29P4 0 3 2 0 3 3 1P5 5 2 7 5 7 2 1平 均 周 轉(zhuǎn) 時(shí) 間 =(25+15+9+3+2)/5=38.8 平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 =(3.13+3+1.29+1+1)/5=1.88 0 3 4 5 7 13 17 25P1P4 P2P2 P3P3 P5 3.2.1.5 最 高 優(yōu) 先 數(shù) 算 法 (Cont.)n 例 子 UNIX： preemptive+dynamic priority（ 可 搶 占 CPU動(dòng) 態(tài) 優(yōu) 先 數(shù) ） 。n 計(jì) 算 公 式 ： p_pri=min1

13、27, USER+p_cpu/16+p_nicen 定 義 USER=100；n p_cpu: 運(yùn) 行 進(jìn) 程 每 20ms加 1（ 優(yōu) 先 級(jí) 降 低 ） ， 其它 進(jìn) 程 每 1200ms減 10（ 優(yōu) 先 級(jí) 提 高 ） ； n p_nice: 可 以 通 過(guò) 系 統(tǒng) 調(diào) 用 nice()修 改 的 量 ： 規(guī)定 用 戶 進(jìn) 程 020之 間 （ 低 ） ， 系 統(tǒng) 進(jìn) 程 -20+20之 間 （ 高 ） 。n 調(diào) 度 時(shí) 取 p_pri最 小 的 。 3.2.1.6 循 環(huán) 輪 轉(zhuǎn) 算 法 (RR)n Round Robin(RR)n 基 本 輪 轉(zhuǎn)n 時(shí) 間 片 (quantum,t

14、ime slice)長(zhǎng) 度 固 定 ，不 變 ；n 所 有 進(jìn) 程 等 速 向 前 推 進(jìn) 。n 改 進(jìn) 輪 轉(zhuǎn) n 時(shí) 間 片 長(zhǎng) 度 不 定 ， 可 變 。 3.2.1.6 循 環(huán) 輪 轉(zhuǎn) 算 法 (Cont.)n 時(shí) 間 片 長(zhǎng) 度 ： 幾 十 毫 秒 幾 百 毫 秒 (eg. 50ms)n 過(guò) 長(zhǎng) ： 響 應(yīng) 速 度 慢 ；n 過(guò) 短 ： 系 統(tǒng) 開(kāi) 銷 (overhead)大 。n 適 應(yīng) 系 統(tǒng) ：n 分 時(shí) 3.2.1.6 循 環(huán) 輪 轉(zhuǎn) 算 法 (Cont.)n RR可 搶 占 CPU調(diào) 度 ： time slice=4msn Process Arriveral time Bu

15、rst timen P1 0 17n P2 0 10 n P3 0 3n Gantt ChartP1 P2 P3 P1 P2 P1 P2 P1 P10 4 8 11 15 19 23 25 29 30 3.2.1.6 循 環(huán) 輪 轉(zhuǎn) 算 法 (Cont.)進(jìn) 程 到 達(dá) 時(shí) 間 運(yùn) 行 時(shí) 間 開(kāi) 始 時(shí) 間 完 成 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間P1 0 17 0 30 30 1.76P2 0 10 4 25 25 2.5P 3 0 3 8 11 11 3.67平 均 周 轉(zhuǎn) 時(shí) 間 (30+25+11)/3=22 平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 (1.76+2.5+3.67

16、)/3=2.64平 均 等 待 時(shí) 間 (13+15+8)/ 3 12(ms)P1 P2 P3 P1 P2 P1 P2 P1 P10 4 8 11 15 19 23 25 29 30 3.2.1.7 多 級(jí) 隊(duì) 列 算 法 (MLQ)n 多 級(jí) 隊(duì) 列n 多 個(gè) 就 緒 隊(duì) 列 ， 進(jìn) 程 所 屬 的 隊(duì) 列 固 定 。n 例 如 ： 通 用 系 統(tǒng) 中 ：n 隊(duì) 列 1： 實(shí) 時(shí) 進(jìn) 程 就 緒 隊(duì) 列 （ HPF）n 隊(duì) 列 2： 分 時(shí) 進(jìn) 程 就 緒 隊(duì) 列 （ RR） n 隊(duì) 列 3： 批 處 理 進(jìn) 程 就 緒 隊(duì) 列 （ HPF） 3. 2.1.8 反 饋 排 隊(duì) 算 法 (FB

17、)n Feed-Back:n 多 個(gè) 就 緒 隊(duì) 列 ， 進(jìn) 程 所 屬 隊(duì) 列 可 變 。運(yùn) 行 s1時(shí) 間 片運(yùn) 行 s2時(shí) 間 片.創(chuàng) 建喚 醒 優(yōu)先級(jí) 時(shí)間片運(yùn) 行 sn時(shí) 間 片Q1 ( RR, HPF1 ) Q2 ( RR, HPF 2 ) Qn ( RR, HPFn ) 3.2.1.8 反 饋 排 隊(duì) 算 法 (Cont.)n 調(diào) 度 效 果 ：n 資 源 利 用 率 高n P1等 待 P2占 有 的 資 源 R, P2釋 放 R, 分 給 P1, P1被 喚 醒 , 進(jìn)入 最 高 級(jí) 隊(duì) 列 , 可 盡 早 投 入 運(yùn) 行 , 使 用 資 源 R；n 響 應(yīng) 速 度 快 n 交

18、 互 式 進(jìn) 程 經(jīng) 常 進(jìn) 入 等 待 狀 態(tài) (等 待 用 戶 輸 入 ),一 旦 被 喚 醒(輸 入 完 成 ),進(jìn) 入 最 高 級(jí) 隊(duì) 列 ,可 盡 快 被 調(diào) 度 選 中 ,投 入 運(yùn) 行 ,反應(yīng) 及 時(shí) ；n 系 統(tǒng) 開(kāi) 銷 小n 計(jì) 算 量 大 的 進(jìn) 程 用 完 前 面 n-1級(jí) 時(shí) 間 片 ,沒(méi) 有 處 理 完 ,落 入 底層 隊(duì) 列 ,調(diào) 度 頻 率 下 降 ,但 每 次 獲 得 較 長(zhǎng) 的 時(shí) 間 片 。 3.2.2 處 理 機(jī) 調(diào) 度 時(shí) 機(jī)l 運(yùn) 行 進(jìn) 程 結(jié) 束 ；l 運(yùn) 行 進(jìn) 程 等 待 ；l 核 心 級(jí) 現(xiàn) 場(chǎng) =PCBl 處 理 機(jī) 被 剝 奪 。l 用

19、戶 級(jí) 現(xiàn) 場(chǎng) =PCB l 中 斷 是 處 理 機(jī) 切 換 的 必 要 條 件 ， 但 不 是充 分 條 件l 必 然 引 起 進(jìn) 程 切 換 的 中 斷 進(jìn) 程 自 愿 結(jié) 束 , exit() 進(jìn) 程 被 強(qiáng) 行 終 止 ；l 非 法 指 令 ， 越 界 ， killl 可 能 引 起 進(jìn) 程 切 換 的 中 斷 時(shí) 鐘 系 統(tǒng) 調(diào) 用 l dispatcherl 保 存 下 降 進(jìn) 程 的 現(xiàn) 場(chǎng) 寄 存 器 (PSW,PC,SP,通 用 寄 存 器 ,地 址 寄 存 器 )PCBl 選 擇 上 升 進(jìn) 程 按 處 理 機(jī) 調(diào) 度 算 法l 恢 復(fù) 上 升 進(jìn) 程 的 現(xiàn) 場(chǎng) PCB

20、寄 存 器 先 恢 復(fù) 通 用 寄 存 器 和 地 址 寄 存 器 ,最 后 恢 復(fù) PSW,PC PSW和 PC必 須 用 一 條 指 令 恢 復(fù) 3.3 調(diào) 度 級(jí) 別 與 多 級(jí) 調(diào) 度n 3.3.1 交 換 與 中 級(jí) 調(diào) 度n Swapping and mid-level schedulingn 3.3.2 作 業(yè) 與 高 級(jí) 調(diào) 度n Job and high-level scheduling處 理 機(jī) 調(diào) 度 為 低 級(jí) 調(diào)度CPU scheduling = low level scheduling 3.3.1 交 換 與 中 級(jí) 調(diào) 度n 術(shù) 語(yǔ)n 交 換 (swapping)

21、n 中 級(jí) 調(diào) 度 (mid-level scheduling)n 并 發(fā) 度 (degree of multi-programming)n 目 標(biāo) ： 控 制 并 發(fā) 度n 并 發(fā) 度 過(guò) 高 n 系 統(tǒng) 開(kāi) 銷 大n 響 應(yīng) 速 度 慢n 內(nèi) 存 等 資 源 緊 張n 進(jìn) 程 (線 程 )頻 繁 進(jìn) 入 等 待 狀 態(tài)n More deadlocks 3.3.1 交 換 與 中 級(jí) 調(diào) 度剝 奪就 緒 等 待運(yùn) 行 選 中 等 待 事 件事 件 發(fā) 生就 緒掛 起 等 待掛 起無(wú) 終 止創(chuàng) 建創(chuàng) 建 結(jié) 束換 出 換 出換 入 換 入 事 件 發(fā) 生 UNIX的 中 級(jí) 調(diào) 度 （ sch

22、ed #0)n 移 入 SRUN狀 態(tài) 進(jìn) 程n 如 內(nèi) 存 不 夠 ，n 移 出 SWAIT和 SSTOP狀 態(tài) 進(jìn) 程 ；n 如 還 不 夠 ， 移 出 SSLEEP和 SRUN狀 態(tài) 進(jìn) 程 ； n 條 件 ：n 待 移 入 進(jìn) 程 在 外 存 時(shí) 間 =3秒 ；n 待 移 出 進(jìn) 程 在 內(nèi) 存 時(shí) 間 =2秒 。 3.3.2 作 業(yè) 與 高 級(jí) 調(diào) 度n 作 業(yè) 狀 態(tài) :n 提 交 : 輸 入 機(jī) 向 輸 入 井 傳 送n 后 備 : 在 輸 入 井 ,尚 未 進(jìn) 入 內(nèi) 存n 執(zhí) 行 : 分 解 為 進(jìn) 程 ,在 內(nèi) 存 處 理n 完 成 : 處 理 完 畢 ,結(jié) 果 在 輸 出

23、 井n 退 出 : 由 輸 出 井 向 打 印 機(jī) 傳 送 l 狀 態(tài) 轉(zhuǎn) 換 : 提 交 后 備 : 由 SPOOLing輸 入 進(jìn) 程 完 成 Simultaneous Peripheral Operation On-Line 后 備 執(zhí) 行 : 由 作 業(yè) 調(diào) 度 (1)(高 級(jí) 調(diào) 度 )完 成 高 級(jí) 調(diào) 度 : 系 統(tǒng) 進(jìn) 程 執(zhí) 行 完 成 : 由 作 業(yè) 調(diào) 度 (2)完 成 完 成 退 出 : 由 SPOOLing輸 出 進(jìn) 程 完 成提 交 后 備 執(zhí) 行 完 成 退 出SPOOLing輸 入 作 業(yè) 調(diào) 度 1 作 業(yè) 調(diào) 度 2 SPOOLing輸 出 作 業(yè) 控 制

24、塊 與 作 業(yè) 表n JCB（ Job Control Block） ：作 業(yè) 存 在 的 數(shù) 據(jù) 結(jié) 構(gòu) ， 其 中保 存 系 統(tǒng) 對(duì) 作 業(yè) 進(jìn) 行 管 理 的全 部 信 息n 作 業(yè) 標(biāo) 識(shí)n 所 屬 用 戶n 作 業(yè) 狀 態(tài) n 調(diào) 度 參 數(shù)n 輸 入 井 地 址n 輸 出 井 地 址n 資 源 需 求n 進(jìn) 入 時(shí) 間n 處 理 時(shí) 間n 完 成 時(shí) 間n SPOOling輸 入 建 立 ， 作 業(yè) 調(diào)度 使 用 ， SPOOling輸 出 撤 銷 。 JCB1JCB2JCB3JCBk作 業(yè) 表 作 業(yè) 調(diào) 度 程 序 (1)內(nèi) 存 已 有 n 道 作 業(yè) 等 待T輸 入 井 中

25、有 后 備 作業(yè)等 待 F 訪 問(wèn) 磁 盤(pán) 中 JCB表根 據(jù) 調(diào) 度 參 數(shù)按 作 業(yè) 調(diào) 度 算 法 選 擇 后 備 作 業(yè)作 業(yè) 狀 態(tài) 標(biāo) 志 為 “ 執(zhí) 行 ”為 該 作 業(yè) 建 立 作 業(yè) 控 制 進(jìn) 程 作 業(yè) 調(diào) 度 程 序 (2)有 終 止 的 作 業(yè) 控 制 進(jìn)程 等 待F作 業(yè) 調(diào) 度 (1)因 內(nèi) 存有 n道 作 業(yè) 而 等 待撤 銷 該 作 業(yè) 控 制 進(jìn) 程 ， 做 善 后 處 理取 一 終 止 的 作 業(yè) 控 制 進(jìn) 程對(duì) 應(yīng) 作 業(yè) 狀 態(tài) 改 為 “ 完 成 ” 喚 醒 作 業(yè) 調(diào) 度 (1)TSpooling輸 出 等 待 作 業(yè) 完成 喚 醒 Spooli

26、ng輸 出T 作 業(yè) 調(diào) 度 算 法n 適 合 批 作 業(yè) 調(diào) 度 的 算 法n 先 到 先 服 務(wù) 算 法 (FCFS)n 優(yōu) 先 數(shù) 調(diào) 度 算 法 (HPF)n 短 作 業(yè) 優(yōu) 先 調(diào) 度 算 法 (SJF)n 最 高 響 應(yīng) 比 優(yōu) 先 調(diào) 度 算 法 (HRN)n 不 適 合 批 作 業(yè) 調(diào) 度 的 算 法 n 時(shí) 間 片 輪 轉(zhuǎn) 算 法 (RR)n 最 短 剩 余 時(shí) 間 優(yōu) 先 (SRTN)n 反 饋 排 隊(duì) 算 法 (FB) 3.4 實(shí) 時(shí) 調(diào) 度 (real-time scheduling)n 實(shí) 時(shí) 任 務(wù) ：n 具 有 明 確 時(shí) 間 約 束 的 計(jì) 算 任 務(wù) 。n E

27、g.n 某 時(shí) 刻 前 必 須 開(kāi) 始 處 理n 某 時(shí) 刻 前 必 須 處 理 完 畢n 實(shí) 時(shí) 調(diào) 度 ： n 合 理 安 排 就 緒 實(shí) 時(shí) 任 務(wù) 的 執(zhí) 行 次 序 ， 滿 足 每個(gè) 實(shí) 時(shí) 任 務(wù) 時(shí) 間 約 束 條 件 的 調(diào) 度 。 實(shí) 時(shí) 任 務(wù) 分 類n 硬 實(shí) 時(shí) vs. 軟 實(shí) 時(shí) n 硬 實(shí) 時(shí) (hard real-time): 必 須 滿 足 任 務(wù) 截止 期 要 求 . n 軟 實(shí) 時(shí) (soft real-time): 期 望 滿 足 截 止 期要 求 . n 周 期 性 vs. 隨 機(jī) 性 n 周 期 性 : 每 隔 固 定 時(shí) 間 發(fā) 生 一 次 n 隨

28、機(jī) 性 : 由 隨 機(jī) 事 件 觸 發(fā) ， 其 發(fā) 生 時(shí) 刻 不 確定 術(shù) 語(yǔ) 解 釋n Ready time: 就 緒 時(shí) 間n Starting deadline: 開(kāi) 始 截 止 期n Processing time: 處 理 時(shí) 間n Completion deadline: 完 成 截 止 期n Occurring frequency: 發(fā) 生 頻 率 周 期 性 實(shí) 時(shí) 事 務(wù)n 周 期 性 實(shí) 時(shí) 事 務(wù) :n 令 Ci為 任 務(wù) Pi處 理 時(shí) 間 ， Ti為 任 務(wù) Pi的 發(fā) 生周 期 ， 則 任 務(wù) P1,Pm可 調(diào) 度 的 必 要 條 件 為 ： 1 1 mi iiT

29、C l 例 ： T1=100, T2=200, T3=500 (ms) C1=50, C2=30, C3=100 (ms) C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.850)goodness=counter+priority l 調(diào) 度 發(fā) 生 時(shí) 刻 ： 運(yùn) 行 進(jìn) 程 的 counter減 至 0； 運(yùn) 行 進(jìn) 程 執(zhí) 行 系 統(tǒng) 調(diào) 用 exit ; 運(yùn) 行 進(jìn) 程 因 等 待 I/O、 信 號(hào) 燈 而 被 封 鎖 ; 原 來(lái) 具 有 高 goodness的 進(jìn) 程 被 解 除 封 鎖 .l 調(diào) 度 效 果 : 實(shí) 時(shí) 優(yōu) 先 于 分 時(shí) 交 互 和 I/O進(jìn) 程

30、 優(yōu) 先 于 CPU進(jìn) 程 l Linux2.0是 支 持 對(duì) 稱 多 處 理 硬 件 的 第 一 個(gè) Linux核 心 ; 進(jìn) 程 或 線 程 可 以 同 時(shí) 運(yùn) 行 在 多 個(gè) 處 理 機(jī) 上 .l 為 保 持 核 心 非 剝 奪 同 步 要 求 ， SMP通 過(guò) 一 個(gè) 唯一 的 核 心 自 旋 鎖 (spin-lock)來(lái) 保 證 任 何 時(shí) 刻 最多 只 有 一 個(gè) 處 理 機(jī) 執(zhí) 行 核 心 代 碼 , 支 持 真 正 意 義 上 的 SMP： 將 一 個(gè) 自 旋 鎖 分 解 為 若 干個(gè) 相 互 獨(dú) 立 的 自 旋 鎖 ， 分 別 用 于 保 護(hù) 核 心 代 碼 不 相交 的 子

31、 集 . 3.6.2 Windows 2000/XP線 程 調(diào) 度n Main Features：n Thread level scheduling;n Real time + foreground + background;n real time: no deadline scheduling; n foreground: GUI windown background: non-interactiven Preemptive + dynamic priority + RR + Feed back;n Symmetric Multi-Processor(SMP) support; 優(yōu) 先 級(jí)

32、別n 16個(gè) 實(shí) 時(shí) 優(yōu) 先 級(jí) （ 16-31）n 一 些 內(nèi) 核 線 程n 應(yīng) 用 程 序 提 升 為 實(shí) 時(shí) 優(yōu) 先 級(jí) 需 要 有 權(quán) 限n 不 是 真 正 意 義 上 的 實(shí) 時(shí) 調(diào) 度n 15個(gè) 可 變 線 程 優(yōu) 先 級(jí) （ 1-15） n 基 本 優(yōu) 先 級(jí)n 線 程 基 本 優(yōu) 先 級(jí) 繼 承 進(jìn) 程 基 本 優(yōu) 先 級(jí) , 可 上 下 浮 動(dòng) 2n 如 : 進(jìn) 程 基 本 優(yōu) 先 級(jí) 4, 其 線 程 基 本 優(yōu) 先 級(jí) 26, n 當(dāng) 前 優(yōu) 先 級(jí)n 在 基 本 優(yōu) 先 級(jí) 與 15之 間 浮 動(dòng)n 可 動(dòng) 態(tài) 提 升n 運(yùn) 行 完 一 個(gè) quantum之 后 自 動(dòng)

33、 下 降 , 不 低 于 基 本 優(yōu) 先 級(jí)n 1個(gè) 系 統(tǒng) 線 程 優(yōu) 先 級(jí) （ 0） Windows優(yōu) 先 級(jí)31282419 16158210實(shí) 時(shí) (系 統(tǒng) )線 程可 變 (用 戶 )線 程頁(yè) 面 清 0守 護(hù) 線 程 當(dāng) 前 優(yōu) 先 級(jí)基 本 優(yōu) 先 級(jí) (繼 承 得 到 ,上 下 浮 動(dòng) 2,最 低 為 1)(下 浮 )(上 浮 ) 優(yōu) 先 級(jí) 提 升n 優(yōu) 先 級(jí) 提 升n IO操 作 完 成n 事 件 等 待 結(jié) 束n 前 臺(tái) 進(jìn) 程 中 的 線 程 完 成 一 個(gè) 等 待 操 作n 由 于 窗 口 活 動(dòng) 而 喚 醒 GUI線 程n 就 緒 超 過(guò) 一 定 時(shí) 限 ， 未

34、 獲 得 處 理 機(jī)n 優(yōu) 先 級(jí) 提 升 不 會(huì) 超 過(guò) 15 搶 占 CPUn 搶 先 情 形n 被 喚 醒 線 程 優(yōu) 先 級(jí) 高 于 運(yùn) 行 線 程 優(yōu) 先 級(jí) ；n 某 就 緒 線 程 的 優(yōu) 先 級(jí) 動(dòng) 態(tài) 變 化n 被 搶 先 線 程n 回 到 相 應(yīng) 就 緒 隊(duì) 列n 時(shí) 間 配 額 n 實(shí) 時(shí) 線 程 ： 重 新 分 配 完 整 時(shí) 間 配 額n 其 它 線 程 ： 保 持 剩 余 配 額 時(shí) 間 配 額 (quantum)n 配 額 長(zhǎng) 度 ： 6-36n 時(shí) 鐘 中 斷 （ 15ms發(fā) 生 一 次 ） 減 3， 2-12次 時(shí) 鐘 中 斷 （ 30ms-180ms） 配

35、額用 完n 配 額 用 完 后 進(jìn) 入 就 緒 隊(duì) 列 ， 優(yōu) 先 級(jí) 下 降 SMP上 的 線 程 調(diào) 度n 線 程 與 CPU的 親 合 關(guān) 系n 每 個(gè) 進(jìn) 程 有 一 個(gè) 處 理 器 親 合 掩 碼 ， 缺 省 為 所有 處 理 器 的 集 合n 線 程 繼 承 其 進(jìn) 程 的 親 合 掩 碼n 親 合 掩 碼 可 以 修 改 n SetProcessAffinityMask, n SetThreadAffinityMask; SMP上 的 線 程 調(diào) 度n 線 程 的 理 想 處 理 器 （ Ideal processor）n 首 選 處 理 器 ：n 第 二 處 理 器 ： （ 在

36、 內(nèi) 核 線 程 控 制 塊 中 ）n 理 想 處 理 器 確 定n 線 程 創(chuàng) 建 時(shí) 隨 機(jī) 確 定 ，n 分 散 各 個(gè) 線 程 與 處 理 機(jī) 對(duì) 應(yīng) 關(guān) 系 。 n 線 程 可 修 改 SetThreadIdealProcessor 就 緒 線 程 對(duì) 處 理 器 的 選 擇n 有 空 閑 處 理 器n 首 選 處 理 器n 第 二 處 理 器n 當(dāng) 前 執(zhí) 行 處 理 器 （ 正 執(zhí) 行 調(diào) 度 代 碼 ）n 由 高 到 低 順 序 找 空 閑 的 處 理 器n 無(wú) 空 閑 處 理 器 ， 考 慮 搶 先 n 首 選 處 理 器n 第 二 處 理 器n 可 運(yùn) 行 編 號(hào) 最 大

37、處 理 器n 不 能 搶 先 進(jìn) 入 相 應(yīng) 的 就 緒 隊(duì) 列 處 理 器 對(duì) 就 緒 線 程 的 選 擇n 空 閑 處 理 器 調(diào) 度n 線 程 上 次 在 此 CPU上 運(yùn) 行 （ 二 級(jí) 緩 沖 利 用 ）n 線 程 的 理 想 處 理 器 是 該 CPUn 處 于 就 緒 狀 態(tài) 時(shí) 間 超 過(guò) 2個(gè) quantumn 優(yōu) 先 級(jí) 別 大 于 等 于 24 作 業(yè) #1 進(jìn) 程 切 換 時(shí) 需 要 保 存 哪 些 現(xiàn) 場(chǎng) 信 息 ？ 請(qǐng) 盡 量 考 慮完 全 。 由 核 心 返 回 目 態(tài) 程 序 時(shí) ， 進(jìn) 程 的 PSW和 PC為 何 必須 用 一 條 機(jī) 器 指 令 同 時(shí) 恢 復(fù) ？ 對(duì) 如 下 三 個(gè) 實(shí) 時(shí) 任 務(wù) : T1=100, C1=50; T2=200, C2=30; T3=500, C3=100. 采 用 EDF算 法 和 RMS算 法 是 否 可 調(diào) 度 ?如 是 畫(huà) 出 對(duì)應(yīng) 的 Gantt圖 ,否 則 說(shuō) 明 原 因 。