《中斷與處理機調度》由會員分享，可在線閱讀，更多相關《中斷與處理機調度（73頁珍藏版）》請在裝配圖網上搜索。

1、3.2 處 理 機 調 度 3.2.1 處 理 機 調 度 算 法n 考 慮 因 素 （ scheduling criteria）n CPU利 用 率 ; (max)n 吞 吐 量 ; (max)n 周 轉 時 間 ; (min)n 響 應 時 間 ; (min)n 系 統(tǒng) 開 銷 ; (min) 調 度 參 數 ni iini i RTnWnW 11 )(1)(1 ni iTnT 1 )(1 RTW sf ttT 周 轉 時 間 ： 完 成 時 間 -進 入 時 間平 均 周 轉 時 間 ： 周 轉 時 間 的 平 均 值帶 權 周 轉 時 間 ： 周 轉 時 間 /運 行 時 間平 均 帶

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

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

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

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

6、3.2.1.2 短 作 業(yè) 優(yōu) 先n SJF（ Shortest Job First)n 按 CPU burst長 度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進 程 到 達 時 間 運 行 時 間 開 始 時 間 完 成 時 間 周 轉 時 間 帶 權 周 轉 時 間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平 均 周 轉 時 間 =(27+8+15+3)/4=13.25 平 均 帶 權 周 轉 時 間 =(2.25+1.6+2.14+1)/4=1.75 3.2.1.2 短 作 業(yè) 優(yōu) 先n 特 點 ：n 假 定 所 有 任 務 同 時 到 達 ， 平 均 等 待時 間 最 短 。n 長 作 業(yè) 可 能 被 餓 死 。 3.2.1.3 最 短 剩 余 時 間 優(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 最 短 剩 余 時 間 優(yōu) 先 算 法 (Cont.)進 程 到 達 時 間 運 行 時 間 開 始 時 間 完 成 時 間 周 轉 時 間 帶 權 周 轉 時 間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平 均 周 轉 時 間 =(30+18+9+3)/4=15平 均 帶 權 周 轉 時 間 =(2.5+2+1.5+1)/4=1.75 平

9、均 等 待 時 間 (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ōu) 先 (HRN)n Highest Response Ratio Nextn RR=(BT+WT)/BT=1+WT/BTn 其 中 :n BT=burst time n WT=wait timen 優(yōu) 點 :n 同 時 到 達 任 務 , 短 者 優(yōu) 先n 長 作 業(yè) 隨 等 待 時 間 增 加 響 應 比 增 加 3.2.1.5 最 高 優(yōu) 先 數 算 法 (HPF)n 靜 態(tài) 優(yōu) 先 數 (static)n 優(yōu) 先

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

11、的 進 程 3.2.1.5 最 高 優(yōu) 先 數 算 法 (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) 先 數 算 法 (Cont.) T W進 程 到 達 時 間 運 行 時 間 優(yōu) 先 級 開 始 時 間 完 成 時 間 周 轉 時 間 帶 權 周 轉 時 間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平 均 周 轉 時 間 =(25+15+9+3+2)/5=38.8 平 均 帶 權 周 轉 時 間 =(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) 先 數 算 法 (Cont.)n 例 子 UNIX： preemptive+dynamic priority（ 可 搶 占 CPU動 態(tài) 優(yōu) 先 數 ） 。n 計 算 公 式 ： p_pri=min1

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

14、ime slice)長 度 固 定 ，不 變 ；n 所 有 進 程 等 速 向 前 推 進 。n 改 進 輪 轉 n 時 間 片 長 度 不 定 ， 可 變 。 3.2.1.6 循 環(huán) 輪 轉 算 法 (Cont.)n 時 間 片 長 度 ： 幾 十 毫 秒 幾 百 毫 秒 (eg. 50ms)n 過 長 ： 響 應 速 度 慢 ；n 過 短 ： 系 統(tǒng) 開 銷 (overhead)大 。n 適 應 系 統(tǒng) ：n 分 時 3.2.1.6 循 環(huán) 輪 轉 算 法 (Cont.)n RR可 搶 占 CPU調 度 ： 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) 輪 轉 算 法 (Cont.)進 程 到 達 時 間 運 行 時 間 開 始 時 間 完 成 時 間 周 轉 時 間 帶 權 周 轉 時 間P1 0 17 0 30 30 1.76P2 0 10 4 25 25 2.5P 3 0 3 8 11 11 3.67平 均 周 轉 時 間 (30+25+11)/3=22 平 均 帶 權 周 轉 時 間 (1.76+2.5+3.67

16、)/3=2.64平 均 等 待 時 間 (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 多 級 隊 列 算 法 (MLQ)n 多 級 隊 列n 多 個 就 緒 隊 列 ， 進 程 所 屬 的 隊 列 固 定 。n 例 如 ： 通 用 系 統(tǒng) 中 ：n 隊 列 1： 實 時 進 程 就 緒 隊 列 （ HPF）n 隊 列 2： 分 時 進 程 就 緒 隊 列 （ RR） n 隊 列 3： 批 處 理 進 程 就 緒 隊 列 （ HPF） 3. 2.1.8 反 饋 排 隊 算 法 (FB

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

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

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

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

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

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

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

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

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

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

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

28、機 性 : 由 隨 機 事 件 觸 發(fā) ， 其 發(fā) 生 時 刻 不 確定 術 語 解 釋n Ready time: 就 緒 時 間n Starting deadline: 開 始 截 止 期n Processing time: 處 理 時 間n Completion deadline: 完 成 截 止 期n Occurring frequency: 發(fā) 生 頻 率 周 期 性 實 時 事 務n 周 期 性 實 時 事 務 :n 令 Ci為 任 務 Pi處 理 時 間 ， Ti為 任 務 Pi的 發(fā) 生周 期 ， 則 任 務 P1,Pm可 調 度 的 必 要 條 件 為 ： 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 調 度 發(fā) 生 時 刻 ： 運 行 進 程 的 counter減 至 0； 運 行 進 程 執(zhí) 行 系 統(tǒng) 調 用 exit ; 運 行 進 程 因 等 待 I/O、 信 號 燈 而 被 封 鎖 ; 原 來 具 有 高 goodness的 進 程 被 解 除 封 鎖 .l 調 度 效 果 : 實 時 優(yōu) 先 于 分 時 交 互 和 I/O進 程

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

31、 集 . 3.6.2 Windows 2000/XP線 程 調 度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) 先 級

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

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

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

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

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

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