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

1、第 三 章 處 理 機(jī) 調(diào) 度 (CPU調(diào) 度 ) 無 論 在 多 道 批 處 理 系 統(tǒng) 還 是 分 時(shí) 系 統(tǒng) 中 , 系 統(tǒng) 中的 用 戶 進(jìn) 程 數(shù) 都 遠(yuǎn) 遠(yuǎn) 超 過 處 理 機(jī) 數(shù) , 除 用 戶 進(jìn) 程 要 占用 處 理 機(jī) 外 , 操 作 系 統(tǒng) 還 要 建 立 若 干 個(gè) 系 統(tǒng) 進(jìn) 程 完 成系 統(tǒng) 功 能 。 這 么 多 的 進(jìn) 程 競(jìng) 爭(zhēng) 處 理 機(jī) , 就 要 求 系 統(tǒng) 提供 進(jìn) 程 調(diào) 度 功 能 , 以 便 采 用 一 些 策 略 , 將 處 理 機(jī) 動(dòng) 態(tài)地 分 配 給 系 統(tǒng) 中 的 各 個(gè) 就 緒 進(jìn) 程 , 使 之 執(zhí) 行 。 分 配 處理 機(jī) 的 任

2、務(wù) 是 由 處 理 機(jī) 調(diào) 度 程 序 完 成 的 ; 處 理 機(jī) 是 計(jì)算 機(jī) 最 重 要 的 資 源 , 如 何 提 高 處 理 機(jī) 的 利 用 率 及 改 善系 統(tǒng) 性 能 , 在 很 大 程 度 上 取 決 于 處 理 機(jī) 調(diào) 度 性 能 的 好壞 , 處 理 機(jī) 調(diào) 度 成 為 操 作 系 統(tǒng) 設(shè) 計(jì) 中 心 工 作 。 要 解 決 的 問 題WHAT： 按 什 么 原 則 分 配 CPU 進(jìn) 程 調(diào) 度 算 法WHEN： 何 時(shí) 分 配 CPU 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī)HOW： 如 何 分 配 CPU CPU調(diào) 度 過 程 （ 進(jìn) 程 的 上 下 文 切 換 ） 一 批 作 業(yè)

3、從 進(jìn) 入 系 統(tǒng) 到 作 業(yè) 運(yùn) 行 完 畢 可 能 經(jīng) 歷 三 級(jí)調(diào) 度 高 級(jí) 、 低 級(jí) 和 中 級(jí) 調(diào) 度 。一 . 高 級(jí) 調(diào) 度 (High Scheduling) 又 稱 為 作 業(yè) 調(diào) 度 接 納 調(diào) 度 或 長(zhǎng) 程 調(diào) 度 , 用 于 批 處 理系 統(tǒng) , 確 定 將 外 存 后 備 隊(duì) 列 中 哪 些 作 業(yè) 調(diào) 入 內(nèi) 存 , 并 為 它們 創(chuàng) 建 進(jìn) 程 。 實(shí) 時(shí) 系 統(tǒng) 和 分 時(shí) 系 統(tǒng) 的 前 臺(tái) 作 業(yè) 不 需 要 作業(yè) 調(diào) 度 。 每 次 作 業(yè) 調(diào) 度 時(shí) , 都 必 須 做 出 兩 個(gè) 決 定 : 1) 接 納 多 少 個(gè) 作 業(yè) : 取 決 于 多

4、道 程 序 度 。 2) 接 納 哪 些 作 業(yè) (用 什 么 調(diào) 度 算 法 ): 先 來 先 服 務(wù) 、 短 作 業(yè) 優(yōu) 先 、 優(yōu) 先 權(quán) 、 響 應(yīng) 比 優(yōu) 先 。3.1 處 理 機(jī) 調(diào) 度 的 基 本 概 念 3.1.1 高 級(jí) 、 低 級(jí) 和 中 級(jí) 調(diào) 度 響 應(yīng) /運(yùn) 行 二 . 低 級(jí) 調(diào) 度 (進(jìn) 程 調(diào) 度 ,短 程 調(diào) 度 ) 進(jìn) 程 調(diào) 度 的 任 務(wù) 是 控 制 協(xié) 調(diào) 進(jìn) 程 對(duì) CPU的 競(jìng) 爭(zhēng) , 即按 照 一 定 的 調(diào) 度 算 法 從 就 緒 隊(duì) 列 中 選 中 一 個(gè) 進(jìn) 程 ， 把CPU的 使 用 權(quán) 交 給 被 選 中 的 進(jìn) 程 。 它 是 最 基

5、 本 的 一 種調(diào) 度 , 批 處 理 系 統(tǒng) , 實(shí) 時(shí) 系 統(tǒng) 和 分 時(shí) 系 統(tǒng) 都 必 須 有 進(jìn) 程調(diào) 度 。 它 通 過 進(jìn) 程 調(diào) 度 程 序 來 完 成 。1. 進(jìn) 程 調(diào) 度 程 序 的 主 要 功 能 可 描 述 如 下 ：(1) 記 錄 系 統(tǒng) 中 各 進(jìn) 程 的 狀 況 為 了 很 好 地 實(shí) 現(xiàn) 進(jìn) 程 調(diào) 度 , 進(jìn) 程 調(diào) 度 程 序 首 先 必 須管 理 系 統(tǒng) 中 各 進(jìn) 程 的 PCB， 將 進(jìn) 程 的 狀 態(tài) 變 化 及 資 源需 求 情 況 及 時(shí) 地 記 錄 到 PCB中 。 通 過 PCB變 化 來 準(zhǔn) 確地 掌 握 系 統(tǒng) 中 所 有 進(jìn) 程 的

6、狀 態(tài) 特 征 和 執(zhí) 行 情 況 。 (2) 選 擇 進(jìn) 程 真 正 占 有 CPU 這 是 進(jìn) 程 調(diào) 度 的 實(shí) 質(zhì) , 即 按 照 系 統(tǒng) 規(guī) 定 的 調(diào) 度 策 略從 就 緒 隊(duì) 列 中 選 擇 一 個(gè) 進(jìn) 程 占 有 CPU執(zhí) 行 。 進(jìn) 程 調(diào) 度依 據(jù) 的 算 法 與 系 統(tǒng) 的 設(shè) 計(jì) 目 標(biāo) 相 一 致 。 對(duì) 于 不 同 的 系統(tǒng) , 通 常 采 用 不 同 的 調(diào) 度 策 略 。 對(duì) 于 批 處 理 系 統(tǒng) 常 采 用短 進(jìn) 程 的 進(jìn) 程 優(yōu) 先 , 以 減 少 各 進(jìn) 程 的 周 轉(zhuǎn) 時(shí) 間 。 對(duì) 于 分時(shí) 系 統(tǒng) , 更 多 地 采 用 時(shí) 間 片 輪 轉(zhuǎn) 。(

7、3) 進(jìn) 行 進(jìn) 程 上 下 文 的 切 換 當(dāng) 進(jìn) 程 調(diào) 度 選 中 一 個(gè) 進(jìn) 程 占 有 CPU時(shí) , 進(jìn) 程 調(diào) 度 程序 要 做 的 主 要 工 作 則 是 進(jìn) 行 進(jìn) 程 上 下 文 切 換 : 將 正 在執(zhí) 行 進(jìn) 程 的 運(yùn) 行 現(xiàn) 場(chǎng) 保 留 在 該 進(jìn) 程 的 PCB中 , 以 便 以 后該 進(jìn) 程 恢 復(fù) 執(zhí) 行 。 將 剛 選 中 進(jìn) 程 的 運(yùn) 行 現(xiàn) 場(chǎng) 恢 復(fù) 起 來 , 并 將 CPU的 控 制 權(quán) 交 給 被 選 中 進(jìn) 程 , 使 其 執(zhí) 行 。 2. 進(jìn) 程 調(diào) 度 方 式 (1)非 搶 占 方 式 (Non preemptive mode) 在 非 搶

8、 占 方 式 下 , 調(diào) 度 程 序 一 旦 把 CPU分 配 給 某一 進(jìn) 程 后 便 讓 它 一 直 運(yùn) 行 下 去 , 直 到 進(jìn) 程 完 成 或 發(fā) 生某 事 件 而 不 能 運(yùn) 行 時(shí) ， 才 將 CPU分 給 其 它 進(jìn) 程 。 這 種 調(diào) 度 方 式 通 常 用 在 批 處 理 系 統(tǒng) 中 。 它 的 主 要優(yōu) 點(diǎn) 是 簡(jiǎn) 單 、 系 統(tǒng) 開 銷 小 。 (2)搶 占 方 式 (Preemptive mode) 當(dāng) 一 個(gè) 進(jìn) 程 正 在 執(zhí) 行 時(shí) ， 系 統(tǒng) 可 以 基 于 某 種 策 略剝 奪 CPU給 其 它 進(jìn) 程 。 剝 奪 的 原 則 有 ： 優(yōu) 先 權(quán) 原 則 、

9、 短 進(jìn) 程 優(yōu) 先 原 則 、 時(shí) 間 片 原 則 。 顯 然 這 種 調(diào) 度 方 式 多 用 在 分 時(shí) 系 統(tǒng) 和 實(shí) 時(shí) 系 統(tǒng) 中 ，以 便 及 時(shí) 響 應(yīng) 各 進(jìn) 程 的 請(qǐng) 求 。 3. 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī) 所 謂 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī) ， 是 指 什 么 情 況 下 引 起 進(jìn)程 調(diào) 度 程 序 工 作 。 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī) 是 與 進(jìn) 程 調(diào) 度 的方 式 有 關(guān) 的 。 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī) 如 下 ：1) 正 在 執(zhí) 行 的 進(jìn) 程 正 確 完 成 , 或 由 于 某 種 錯(cuò) 誤 而 終止 運(yùn) 行 (陷 阱 或 中 斷 ) ；2) 執(zhí) 行 中

10、 的 進(jìn) 程 提 出 I/O請(qǐng) 求 , 等 待 I/O完 成 時(shí) ;3) 在 分 時(shí) 系 統(tǒng) 中 , 按 照 時(shí) 間 片 輪 轉(zhuǎn) , 分 給 進(jìn) 程 的 時(shí)間 片 用 完 時(shí) ；4) 按 照 優(yōu) 先 級(jí) 調(diào) 度 時(shí) , 有 更 高 優(yōu) 先 級(jí) 進(jìn) 程 變 為 就 緒時(shí) (搶 占 方 式 )；5) 在 進(jìn) 程 通 訊 中 , 執(zhí) 行 中 的 進(jìn) 程 執(zhí) 行 了 某 種 原 語 操作 , 如 wait操 作 、 阻 塞 原 語 和 喚 醒 原 語 時(shí) , 都 可能 引 起 進(jìn) 程 調(diào) 度 。 三 . 中 級(jí) 調(diào) 度 (中 程 調(diào) 度 ) 中 級(jí) 調(diào) 度 使 暫 時(shí) 停 止 的 進(jìn) 程 不 再 占

11、用 寶 貴的 內(nèi) 存 資 源 , 將 它 們 調(diào) 到 外 存 上 去 成 為 掛 起 狀態(tài) 。 當(dāng) 處 于 掛 起 就 緒 的 進(jìn) 程 重 新 具 備 運(yùn) 行 條 件且 內(nèi) 存 稍 有 空 閑 時(shí) , 中 級(jí) 調(diào) 度 將 它 重 新 調(diào) 入 內(nèi)存 , 掛 在 活 動(dòng) 就 緒 隊(duì) 列 上 等 待 進(jìn) 程 調(diào) 度 。 中 級(jí)調(diào) 度 實(shí) 質(zhì) 上 就 是 存 儲(chǔ) 管 理 中 的 對(duì) 換 功 能 。 進(jìn) 程 調(diào) 度 頻 率 最 高 (10100ms/次 )調(diào) 度 算 法簡(jiǎn) 單 快 速 ; 作 業(yè) 調(diào) 度 頻 率 最 低 約 幾 分 鐘 一 次 ,調(diào)度 算 法 允 許 花 費(fèi) 較 多 的 時(shí) 間 ; 中

12、級(jí) 調(diào) 度 介 于 兩者 之 間 。 3.1.2. 調(diào) 度 隊(duì) 列 模 型1. 僅 有 進(jìn) 程 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 在 分 時(shí) 系 統(tǒng) 中 , 通 常 僅 有 進(jìn) 程 調(diào) 度 , 采 用 FIFO算 法 。CPU就 緒 隊(duì) 列阻 塞 隊(duì) 列時(shí) 間 片 完 進(jìn) 程 調(diào) 度等 待 事 件事 件出 現(xiàn)交 互 用 戶 完 成 2. 具 有 高 級(jí) 和 低 級(jí) 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 在 批 處 理 系 統(tǒng) 中 ,不 僅 需 要 進(jìn) 程 調(diào) 度 而 且 需要 作 業(yè) 調(diào) 度 。 CPU就 緒 隊(duì) 列阻 塞 隊(duì) 列時(shí) 間 片 完 進(jìn) 程調(diào) 度事 件 1出 現(xiàn) 后 備隊(duì) 列 完

13、成阻 塞 隊(duì) 列事 件 2出 現(xiàn) 阻 塞 隊(duì) 列事 件 n出 現(xiàn) . 等 待 事 件 1等 待 事 件 2等 待 事 件 n作 業(yè)調(diào) 度 3. 具 有 三 級(jí) 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 在 具 有 三 級(jí) 調(diào) 度 系 統(tǒng) 中 , 增 加 了 在 外 存 的 掛 起 狀 態(tài)CPU就 緒 隊(duì) 列就 緒 掛 起 時(shí) 間 片 完 進(jìn) 程調(diào) 度事件出現(xiàn)后 備隊(duì) 列 完 成阻 塞 掛 起阻 塞 隊(duì) 列 掛 起等 待 事 件作 業(yè)調(diào) 度 事 件 出 現(xiàn)中 級(jí)調(diào) 度交 互 作 業(yè) 調(diào) 出 對(duì) 于 不 同 的 系 統(tǒng) , 有 不 同 的 設(shè) 計(jì) 目 標(biāo) , 采 用 不 同的 調(diào) 度 算 法 。 調(diào) 度

14、 算 法 實(shí) 質(zhì) 上 是 個(gè) 策 略 問 題面 向 用 戶 的 準(zhǔn) 則 ：l 周 轉(zhuǎn) 時(shí) 間 短l 交 互 式 系 統(tǒng) 的 響 應(yīng) 時(shí) 間 快l 截 止 時(shí) 間 保 證l 優(yōu) 先 權(quán) 準(zhǔn) 則 (公 平 合 理 )面 向 系 統(tǒng) 的 準(zhǔn) 則 ：l 單 位 時(shí) 間 內(nèi) 運(yùn) 行 盡 可 能 多 的 進(jìn) 程 , 吞 吐 量 高 l 使 處 理 機(jī) 盡 可 能 保 持 “ 忙 碌 ” 利 用 率 高l 使 內(nèi) 外 存 、 I/O設(shè) 備 得 以 均 衡 、 充 分 利 用3.1.3. 調(diào) 度 算 法 的 評(píng) 價(jià) 準(zhǔn) 則 進(jìn) 程 (作 業(yè) )平 均 周 轉(zhuǎn) 時(shí) 間 （ 周 轉(zhuǎn) 時(shí) 間 、 吞 吐 量 ） 設(shè)

15、 某 進(jìn) 程 創(chuàng) 建 時(shí) 間 為 Si, 結(jié) 束 的 時(shí) 間 為 Ei 它 的 周 轉(zhuǎn) 時(shí) 間 (全 過 程 所 用 時(shí) 間 )為 Ti =Ei Si 系 統(tǒng) 為 它 提 供 的 實(shí) 際 服 務(wù) 時(shí) 間 為 Tsi 則 進(jìn) 程 平 均 周 轉(zhuǎn) 時(shí) 間 T,帶 權(quán) 平 均 周 轉(zhuǎn) 時(shí) 間 W為 ： T W= 其 中 ， n為 被 測(cè) 定 進(jìn) 程 流 中 的 進(jìn) 程 數(shù)ni=1Tin1 ni=1 Tin1 Tsi 要 設(shè) 計(jì) 一 個(gè) 理 想 的 調(diào) 度 算 法 是 一 件 十 分 困 難 的事 ,在 實(shí) 際 系 統(tǒng) 中 , 調(diào) 度 算 法 往 往 折 衷 考 慮 。 大 多 數(shù) 操 作 系 統(tǒng) 都

16、 采 用 比 較 簡(jiǎn) 單 的 調(diào) 度 算 法 3.2 調(diào) 度 算 法1.先 進(jìn) 先 出 調(diào) 度 算 法 (FIFO) (先 來 先 服 務(wù) FCFS) 作 業(yè) 調(diào) 度 按 照 進(jìn) 入 后 備 隊(duì) 列 的 先 后 次 序 調(diào) 度 , 進(jìn) 程調(diào) 度 按 照 進(jìn) 入 進(jìn) 程 就 緒 隊(duì) 列 的 先 后 次 序 來 調(diào) 度 優(yōu) 點(diǎn) :實(shí) 現(xiàn) 簡(jiǎn) 單 缺 點(diǎn) :不 利 于 短 作 業(yè) (進(jìn) 程 ),緊 迫 性 作 業(yè) (進(jìn) 程 )得 不 到及 時(shí) 處 理2.短 作 業(yè) (進(jìn) 程 )優(yōu) 先 調(diào) 度 算 法 (SJF,SPF) 選 擇 就 緒 隊(duì) 列 中 估 計(jì) 運(yùn) 行 時(shí) 間 最 短 的 進(jìn) 程 投 入

17、運(yùn) 行 優(yōu) 點(diǎn) : 平 均 周 轉(zhuǎn) 時(shí) 間 ,帶 權(quán) 平 均 周 轉(zhuǎn) 時(shí) 間 都 改 善 缺 點(diǎn) : 對(duì) 長(zhǎng) 作 業(yè) (進(jìn) 程 )非 常 不 利 不 能 保 證 緊 迫 性 作 業(yè) (進(jìn) 程 )得 到 及 時(shí) 處 理 估 計(jì) 運(yùn) 行 時(shí) 間 不 準(zhǔn) 確 3. 優(yōu) 先 權(quán) 調(diào) 度 算 法 (HPFHighest Priority First)優(yōu) 先 選 擇 就 緒 隊(duì) 列 中 優(yōu) 先 權(quán) 最 高 的 進(jìn) 程 投 入 運(yùn) 行非 搶 占 式 優(yōu) 先 權(quán) 算 法 :僅 在 事 件 發(fā) 生 放 棄 處 理 機(jī) 時(shí)搶 占 式 優(yōu) 先 權(quán) 算 法 : 可 將 正 在 運(yùn) 行 的 運(yùn) 行 權(quán) 剝 奪 優(yōu) 先

18、權(quán) 的 類 型靜 態(tài) 優(yōu) 先 權(quán) : 在 進(jìn) 程 創(chuàng) 建 時(shí) 指 定 優(yōu) 先 權(quán) , 在 進(jìn) 程 運(yùn) 行時(shí) 優(yōu) 先 數(shù) 不 變動(dòng) 態(tài) 優(yōu) 先 權(quán) : 在 進(jìn) 程 創(chuàng) 建 時(shí) 創(chuàng) 立 一 個(gè) 優(yōu) 先 權(quán) ， 但 在其 生 命 周 期 內(nèi) 優(yōu) 先 數(shù) 可 以 動(dòng) 態(tài) 變 化 。 如 等 待 時(shí) 間 長(zhǎng)優(yōu) 先 數(shù) 可 改 變 確 定 優(yōu) 先 權(quán) 的 依 據(jù)進(jìn) 程 類 型 、 對(duì) 資 源 的 需 求 、 根 據(jù) 用 戶 要 求 4. 高 響 應(yīng) 比 優(yōu) 先 調(diào) 度 算 法 ： 改 進(jìn) 短 作 業(yè) (進(jìn) 程 )優(yōu) 先 調(diào) 度 算 法 ,優(yōu) 先 權(quán) 用 下 式 動(dòng)態(tài) 計(jì) 算 出 來 優(yōu) 先 權(quán) = =上

19、式 可 看 出 等 待 時(shí) 間 相 同 要 求 服 務(wù) 的 時(shí) 間 越 短 優(yōu) 先 權(quán) 越 高 , 有 利 于 短 作 業(yè) 要 求 服 務(wù) 時(shí) 間 相 同 ,等 待 時(shí) 間 越 長(zhǎng) 優(yōu) 先 權(quán) 越 高 ,近似 于 先 來 先 服 務(wù) 長(zhǎng) 作 業(yè) 的 優(yōu) 先 權(quán) 會(huì) 隨 等 待 時(shí) 間 加 長(zhǎng) 而 升 高 ,長(zhǎng) 作業(yè) 也 會(huì) 得 到 執(zhí) 行等 待 時(shí) 間 +要 求 服 務(wù) 時(shí) 間 響 應(yīng) 時(shí) 間 要 求 服 務(wù) 時(shí) 間 要 求 服 務(wù) 時(shí) 間 把 CPU劃 分 成 若 干 時(shí) 間 片 ,并 且 按 順 序 賦 給 就 緒隊(duì) 列 中 的 每 一 個(gè) 進(jìn) 程 ， 進(jìn) 程 輪 流 占 有 CPU， 當(dāng)

20、 時(shí) 間片 用 完 時(shí) ， 即 使 進(jìn) 程 未 執(zhí) 行 完 畢 ， 系 統(tǒng) 也 剝 奪 該 進(jìn)程 的 CPU， 將 該 進(jìn) 程 排 在 就 緒 隊(duì) 列 末 尾 。 同 時(shí) 系 統(tǒng)選 擇 另 一 個(gè) 進(jìn) 程 運(yùn) 行 分 時(shí) 系 統(tǒng) 中 常 用 時(shí) 間 片 輪 轉(zhuǎn) 法時(shí) 間 片 選 擇 問 題 ： 固 定 時(shí) 間 片 、 可 變 時(shí) 間 片確 定 時(shí) 間 片 大 小 的 因 素 ： 系 統(tǒng) 響 應(yīng) 時(shí) 間 、 就 緒 進(jìn) 程 個(gè) 數(shù) 、 CPU能 力 5.時(shí) 間 片 輪 轉(zhuǎn) 調(diào) 度 算 法 6.多 隊(duì) 列 反 饋 調(diào) 度 算 法 ： 系 統(tǒng) 按 優(yōu) 先 級(jí) 設(shè) 置 多 級(jí) 就 緒 隊(duì) 列 第 一

21、級(jí) 優(yōu) 先 級(jí) 最 高 各 就 緒 隊(duì) 列 分 配 不 同 的 時(shí) 間 片 ,優(yōu) 先 級(jí) 高 的 第 一 級(jí) 隊(duì)列 時(shí) 間 片 最 小 , 隨 著 隊(duì) 列 優(yōu) 先 級(jí) 的 降 低 , 時(shí) 間 片 加 大 各 個(gè) 隊(duì) 列 按 照 先 進(jìn) 先 出 調(diào) 度 算 法 一 個(gè) 新 進(jìn) 程 就 緒 后 進(jìn) 入 第 一 級(jí) 就 緒 隊(duì) 列 進(jìn) 程 由 于 等 待 事 件 而 放 棄 CPU后 , 進(jìn) 入 等 待 隊(duì) 列 , 一旦 等 待 的 事 件 發(fā) 生 , 則 回 到 原 來 的 就 緒 隊(duì) 列 當(dāng) 有 一 個(gè) 優(yōu) 先 級(jí) 更 高 的 進(jìn) 程 就 緒 時(shí) , 可 以 搶 占 CPU,被 搶 占 進(jìn) 程

22、回 到 原 來 一 級(jí) 就 緒 隊(duì) 列 末 尾 當(dāng) 第 一 級(jí) 隊(duì) 列 空 時(shí) , 就 去 調(diào) 度 第 二 級(jí) 隊(duì) 列 , 如 此 類 推 時(shí) 間 片 用 完 后 進(jìn) 程 放 棄 CPU, 進(jìn) 入 下 一 級(jí) 就 緒 隊(duì) 列 實(shí) 時(shí) 系 統(tǒng) 中 , 對(duì) 實(shí) 時(shí) 進(jìn) 程 的 調(diào) 度 有 截 止 時(shí) 間 的 要 求1.實(shí) 現(xiàn) 實(shí) 時(shí) 調(diào) 度 的 基 本 條 件 1) 提 供 必 要 的 信 息 就 緒 時(shí) 間 、 開 始 截 止 時(shí) 間 或 完 成 截 止 時(shí) 間 、 處 理 時(shí)間 、 資 源 要 求 、 優(yōu) 先 級(jí) ( 硬 實(shí) 時(shí) 任 務(wù) 賦 絕 對(duì) 優(yōu) 先 級(jí) )。 2) 系 統(tǒng) 處 理 速

23、度 快 若 系 統(tǒng) 中 有 m 個(gè) 周 期 性 硬 實(shí) 時(shí) 任 務(wù) , 處 理 時(shí) 間 為 Ci周 期 時(shí) 間 為 Pi , 則 處 理 機(jī) 處 理 速 度 應(yīng) 達(dá) 到 可 調(diào) 度 條 件 : 1 (單 處 理 機(jī) ) n (多 處 理 機(jī) ) 3) 采 用 搶 占 式 調(diào) 度 機(jī) 制 以 滿 足 對(duì) 截 止 時(shí) 間 的 要 求 4) 具 有 快 速 切 換 機(jī) 制 : 快 速 中 斷 響 應(yīng) 、 快 速 任 務(wù) 分 派3.3 實(shí) 時(shí) 調(diào) 度CiPii=1n CiPii=1n 2. 實(shí) 時(shí) 調(diào) 度 算 法 的 分 類 1) 非 搶 占 式 調(diào) 度 算 法 非 搶 占 式 輪 轉(zhuǎn) 調(diào) 度 算 法

24、 (響 應(yīng) 時(shí) 間 數(shù) 秒 到 數(shù) 十 秒 ) 輪 轉(zhuǎn) 一 圈 后 調(diào) 度 非 搶 占 式 優(yōu) 先 權(quán) 調(diào) 度 算 法 (響 應(yīng) 時(shí) 間 數(shù) 百 毫 秒 ) 當(dāng) 前 進(jìn) 程 完 成 (或 被 阻 塞 )后 調(diào) 度 2) 搶 占 式 調(diào) 度 算 法 嚴(yán) 格 要 求 的 實(shí) 時(shí) 系 統(tǒng) , 響 應(yīng) 時(shí) 間 在 數(shù) 十 毫 秒 以 內(nèi) 基 于 時(shí) 鐘 中 斷 的 搶 占 式 調(diào) 度 算 法 時(shí) 鐘 中 斷 到 來 時(shí) 調(diào) 度 立 即 搶 占 的 優(yōu) 先 權(quán) 調(diào) 度 算 法 立 即 剝 奪 當(dāng) 前 進(jìn) 程 調(diào) 度 時(shí) 間 見 P 83 圖 3-6 3.幾 種 常 見 的 實(shí) 時(shí) 調(diào) 度 算 法 1)

25、最 早 截 止 時(shí) 間 優(yōu) 先 算 法 (Earliest Deadline First) 根 據(jù) 任 務(wù) 的 開 始 截 止 時(shí) 間 確 定 優(yōu) 先 級(jí) 。 2) 最 低 松 弛 度 優(yōu) 先 算 法 (Least Laxity First) 根 據(jù) 任 務(wù) 的 松 弛 度 (緊 急 程 度 )確 定 優(yōu) 先 級(jí) 根 據(jù) 任 務(wù) 完 成 截 止 時(shí) 間 和 本 身 運(yùn) 行 時(shí) 間 確 定 松 弛 度 松 弛 度 = 必 須 完 成 時(shí) 間 -本 身 運(yùn) 行 時(shí) 間 -當(dāng) 前 時(shí) 間 P 85 圖 3-9 保 存 現(xiàn) 場(chǎng) :順 序 保 存 進(jìn) 程 的 上 下 文 , 包 括 程 序 計(jì)數(shù) 器 和

26、 其 它 寄 存 器 用 新 狀 態(tài) 和 相 關(guān) 信 息 更 新 正 在 運(yùn) 行 進(jìn) 程 的 PCB 把 該 進(jìn) 程 移 至 合 適 的 隊(duì) 列 -就 緒 、 阻 塞 選 擇 另 一 個(gè) 要 執(zhí) 行 的 進(jìn) 程 ,更 新 該 進(jìn) 程 的 PCB 從 被 選 中 進(jìn) 程 中 重 裝 入 CPU 上 下 文 ,恢 復(fù) 現(xiàn) 場(chǎng) 若 無 就 緒 進(jìn) 程 ,系 統(tǒng) 會(huì) 安 排 一 個(gè) 閑 逛 進(jìn) 程 (idle), 一 直 運(yùn) 行 , 在 執(zhí) 行 過 程 中 可 接 收 中 斷 。3.4 CPU調(diào) 度 的 實(shí) 現(xiàn) 操 作 系 統(tǒng) 的 核 心 向 上 提 供 無 中 斷 的 虛 擬 機(jī) 器 , 在 核 心

27、 內(nèi) 不 允 許 中 斷特 點(diǎn) : 核 心 常 駐 內(nèi) 存 , 短 小 精 焊 , 為 進(jìn) 程 運(yùn) 行 提 供 舞 臺(tái) 核 心 的 組 成中 斷 處 理 : 時(shí) 鐘 、 I/O、 虛 擬 存 儲(chǔ) 器進(jìn) 程 管 理 : 調(diào) 度 控 制 通 訊 互 斥 同 步 等原 語 管 理 : 提 供 一 系 列 原 語 , 同 步 , 通 信 , 創(chuàng) 建 , 撤 消 等隊(duì) 列 管 理 :中 斷 之 后 調(diào) 度 之 前 (運(yùn) 行 -就 緒 -等 待 隊(duì) 列 )現(xiàn) 場(chǎng) 管 理 : 保 存 現(xiàn) 場(chǎng) 、 恢 復(fù) 現(xiàn) 場(chǎng)時(shí) 鐘 管 理 : 絕 對(duì) 時(shí) 鐘 、 間 隔 時(shí) 鐘 、 虛 時(shí) 鐘 保 存 現(xiàn) 場(chǎng) 、 分 析

28、 中 斷 源 處 理 中 斷原 語 管 理 、 隊(duì) 列 管 理 、 時(shí) 鐘 管 理 、 進(jìn) 程 調(diào) 度 恢 復(fù) 現(xiàn) 場(chǎng)中 斷 核 心 入 口核 心 處 理 流 程 唯 一 入 口 :中 斷 ,由 硬 件 完 成 作 業(yè) : P101 2, 3, 5 3.5死 鎖死 鎖 的 基 本 概 念死 鎖 的 解 決 方 案 （ 預(yù) 防 ， 避 免 ， 檢 測(cè) 及 解 除 ）資 源 分 配 圖 3.5.1 死 鎖 的 基 本 概 念死 鎖 (Deadlock)的 定 義 ： 一 組 進(jìn) 程 中 ， 每 個(gè) 進(jìn) 程 都 無 限 等 待 被 該 組進(jìn) 程 中 另 一 進(jìn) 程 所 占 有 的 資 源 ， 因 而

29、 永 遠(yuǎn) 無 法得 到 的 資 源 ， 這 種 現(xiàn) 象 稱 為 進(jìn) 程 死 鎖 ， 這 一 組進(jìn) 程 就 稱 為 死 鎖 進(jìn) 程說 明 : 參 與 死 鎖 的 進(jìn) 程 最 少 是 兩 個(gè)參 與 死 鎖 的 進(jìn) 程 至 少 有 兩 個(gè) 已 經(jīng) 占 有 資 源參 與 死 鎖 的 所 有 進(jìn) 程 都 在 等 待 資 源注 意 ： 如 果 死 鎖 發(fā) 生 ， 會(huì) 浪 費(fèi) 大 量 系 統(tǒng) 資 源 ，甚 至 導(dǎo) 致 系 統(tǒng) 崩 潰 。 死 鎖 產(chǎn) 生 的 原 因1.競(jìng) 爭(zhēng) 資 源 引 起永 久 性 資 源 :可 被 多 個(gè) 進(jìn) 程 多 次 使 用 (可 再 用 資 源 ) 剝 奪 性 資 源 (CPU、

30、內(nèi) 存 ） 非 剝 奪 性 資 源 (磁 帶 機(jī) 、 打 印 機(jī) ) 競(jìng) 爭(zhēng) 非 剝 奪 性 資 源 會(huì) 引 起 死 鎖臨 時(shí) 性 資 源 :只 可 使 用 一 次 的 資 源 ； 如 信 號(hào) 量 ,中 斷 信 號(hào) ,同 步 信 號(hào) 等 (可 消 耗 性 資 源 ) 競(jìng) 爭(zhēng) 臨 時(shí) 性 資 源 也 會(huì) 引 起 死 鎖2. 進(jìn) 程 推 進(jìn) 順 序 不 當(dāng) 引 起 對(duì) 資 源 采 用 “ 申 請(qǐng) -分 配 -使 用 -釋 放 ” 模 式 , 由于 推 進(jìn) 順 序 不 當(dāng) 兩 進(jìn) 程 都 要 申 請(qǐng) 對(duì) 方 已 占 有 的 資 源 P1： 申 請(qǐng) 打 印 機(jī)申 請(qǐng) 掃 描 儀使 用釋 放 打 印 機(jī)

31、釋 放 掃 描 儀 P2： 申 請(qǐng) 掃 描 儀申 請(qǐng) 打 印 機(jī)使 用釋 放 打 印 機(jī)釋 放 掃 描 儀死 鎖 的 例 子 :競(jìng) 爭(zhēng) 非 剝 奪 性 資 源 進(jìn) 程 推 進(jìn) 順 序 不 當(dāng) 引 起 死 鎖 Req(R1) Req(R2) Rel(R1) Rel(R2)Rel(R1)Rel(R2)Req(R1)Req(R2) P2 P1不 安 全 區(qū)競(jìng) 爭(zhēng) 非 剝 奪 性 資 源推 進(jìn) 順 序 不 當(dāng)進(jìn) 入 不 安 全 區(qū) 3.5.2產(chǎn) 生 死 鎖 的 四 個(gè) 必 要 條 件1) 互 斥 條 件 （ 資 源 獨(dú) 占 ） ： 一 個(gè) 資 源 每 次 只 能 給 一 個(gè) 進(jìn) 程 使 用2) 請(qǐng) 求

32、 和 保 持 條 件 : (部 分 分 配 ,占 有 申 請(qǐng) ) 在 申 請(qǐng) 新 資 源 的 同 時(shí) 保 持 對(duì) 原 有 資 源 的 占 有3) 不 可 剝 奪 條 件 （ 不 可 強(qiáng) 占 ） ： 資 源 申 請(qǐng) 者 不 能 強(qiáng) 行 的 從 資 源 占 有 者 手 中 奪取 資 源 , 資 源 只 能 由 占 有 者 自 愿 釋 放4) 循 環(huán) 等 待 條 件 ： 存 在 進(jìn) 程 -等 待 資 源 環(huán) 形 鏈 P1 , P2 , , Pn, 其 中 P 1等 待 P2占 有 的 資 源 , P2等 待 P3占 有 的 資 源 , , Pn等 待 P1占 有 的 資 源 。 3.6 死 鎖 的

33、預(yù) 防 3.6.1 強(qiáng) 限 制 預(yù) 防 確 定 資 源 分 配 算 法 ,保 證 不 發(fā) 生 死 鎖 。 做 法是 破 壞 產(chǎn) 生 死 鎖 的 四 個(gè) 必 要 條 件 之 一 。1. 破 壞 “ 請(qǐng) 求 和 保 持 (部 分 分 配 )”條 件 每 個(gè) 進(jìn) 程 運(yùn) 行 前 必 須 一 次 性 申 請(qǐng) 運(yùn) 行 期 所 需全 部 資 源 , 若 所 需 資 源 均 可 滿 足 則 全 部 分 配 。 該進(jìn) 程 運(yùn) 行 中 不 再 請(qǐng) 求 資 源 , 屏 棄 請(qǐng) 求 條 件 。 簡(jiǎn) 單 、 安 全 ; 但 資 源 利 用 率 低 ,要 長(zhǎng) 期 等 待 。2. 破 壞 “ 不 可 剝 奪 ” 條 件

34、在 允 許 進(jìn) 程 動(dòng) 態(tài) 申 請(qǐng) 資 源 前 提 下 , 規(guī) 定 : 某進(jìn) 程 在 申 請(qǐng) 新 的 資 源 不 能 立 即 滿 足 而 被 阻 塞 之前 , 必 須 釋 放 已 占 有 的 資 源 (可 能 造 成 前 一 段 工作 失 效 ), 若 需 要 再 重 新 申 請(qǐng) (增 加 開 銷 )。 3.破 壞 “ 循 環(huán) 等 待 ” 條 件 采 用 資 源 有 序 分 配 法 :允 許 進(jìn) 程 動(dòng) 態(tài) 申 請(qǐng) 資源 , 對(duì) 系 統(tǒng) 中 所 有 資 源 編 號(hào) , 進(jìn) 程 申 請(qǐng) 資 源 時(shí) 應(yīng)嚴(yán) 格 按 資 源 編 號(hào) 遞 增 次 序 進(jìn) 行 ,否 則 不 予 分 配 。P1：申 請(qǐng) 1

35、申 請(qǐng) 3申 請(qǐng) 4 P2：申 請(qǐng) 2申 請(qǐng) 4申 請(qǐng) 8 Pn：申 請(qǐng) 1申 請(qǐng) 2申 請(qǐng) 8缺 點(diǎn) : 資 源 利 用 仍 不 充 分 3.6.2 避 免 死 鎖 的 銀 行 家 算 法 前 面 的 三 種 方 法 由 于 限 制 太 強(qiáng) , 資 源 利 用 率都 不 太 高 。 能 否 放 寬 限 制 條 件 ？ E.W.Dijkstra于 1968年 提 出 銀 行 家 算 法 , 此算 法 要 事 先 知 道 每 個(gè) 進(jìn) 程 對(duì) 資 源 的 最 大 需 求 量 ; 算 法 的 基 本 思 路 :允 許 進(jìn) 程 動(dòng) 態(tài) 申 請(qǐng) 資 源 ,但 在 每次 分 配 資 源 前 先 對(duì) 本 次

36、 分 配 的 安 全 性 進(jìn) 行 檢 查 , 以 判 斷 這 種 分 配 是 否 可 能 導(dǎo) 致 死 鎖 , 若 分 配 可 能導(dǎo) 致 系 統(tǒng) 死 鎖 , 則 不 予 分 配 , 否 則 分 配 該 資 源 。(檢 查 每 次 分 配 后 是 否 仍 存 在 安 全 分 配 序 列 ) 顯 然 , 此 法 避 免 了 死 鎖 且 資 源 利 用 率 高 。 1. 安 全 序 列 ： 如 果 進(jìn) 程 序 列 P1， ， Pn對(duì) 每 個(gè) Pi(1in)進(jìn) 程 , 它 以 后 尚 需 要 的 資 源 量 不 超 過 系 統(tǒng) 當(dāng) 前 剩 余 資 源 量 與所 有 Pj (j Available(2,3

37、,0),讓 P4等 待4) 若 P0請(qǐng) 求 資 源 ,發(fā) 出 請(qǐng) 求 向 量 Request(0,2,0)假 定 分 配 ,資 源 為 : 檢 查 此 刻 的 安 全 性 ： Available(2,1,0)已 不 滿 足 任 何進(jìn) 程 的 需 要 , 不 安 全 ; 不 予 分 配 Available 仍 為 (2,3,0) 。 Max Allocation Need Available 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2

38、 2 2 1 1 0 1 1 P 4 4 3 3 0 0 2 4 3 1 檢 查 此 刻 的 安 全 性 Max Allocation Need Available 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1安 全 , 可 將 (0,1,0)分 配 給 P0若 將 P0請(qǐng) 求 改 為 Request(0,1,0)假 定 分 配 , 資 源 變 為 : 進(jìn) Work

39、 Allocation Need W+ A Finish 程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1 0 1 1 7 3 3 trueP4 7 3 3 0 0 2 4 3 1 7 3 5 trueP0 7 3 5 0 2 0 7 3 3 7 5 5 trueP2 7 5 5 3 0 2 6 0 0 10 5 7 true 3.7 死 鎖 的 檢 測(cè) 與 解 除 允 許 死 鎖 發(fā) 生 ， 系 統(tǒng) 必 須 提 供 檢 測(cè) 和 解 除 死 鎖的 手 段 , 操 作 系 統(tǒng) 應(yīng) 不 斷 監(jiān) 視 系 統(tǒng)

40、 進(jìn) 展 情 況 ， 判 斷 死鎖 是 否 發(fā) 生 。 3.7.1死 鎖 的 檢 測(cè)1. 資 源 分 配 圖用 有 向 圖 描 述 進(jìn) 程 的 死 鎖 : 準(zhǔn) 確 、 形 象 系 統(tǒng) 由 若 干 類 資 源 構(gòu) 成 ， 一 類 資 源 稱 為 一 個(gè) 資 源 類 ；每 個(gè) 資 源 類 中 包 含 若 干 個(gè) 同 種 資 源 ， 稱 為 資 源 實(shí) 例 。二 元 組 G=（ V， E） V： 結(jié) 點(diǎn) 集 ， 分 為 P， R兩 部 分 P=p1,p2,pn R=r1,r2,rm E： 邊 的 集 合 , 其 元 素 為 有 序 二 元 組 分 配 邊 (rj,pi): 資 源 實(shí) 例 進(jìn) 程 的

41、 一 條 有 向 邊申 請(qǐng) 邊 (pi,rj): 進(jìn) 程 資 源 類 的 一 條 有 向 邊 有 環(huán) 有 死 鎖 有 環(huán) 無 死 鎖 2. 死 鎖 定 理 如 果 資 源 分 配 圖 中 沒 有 環(huán) 路 , 則 系 統(tǒng) 中 沒 有 死 鎖 , 如 果 圖 中 存 在 環(huán) 路 則 系 統(tǒng) 中 可 能 存 在 死 鎖 。 如 果 每 個(gè) 資 源 類 中 只 包 含 一 個(gè) 資 源 實(shí) 例 , 則 資 源分 配 圖 環(huán) 路 是 死 鎖 存 在 的 充 分 必 要 條 件 。資 源 分 配 圖 化 簡(jiǎn) 方 法 ：1） 找 一 個(gè) 非 孤 立 點(diǎn) 進(jìn) 程 結(jié) 點(diǎn) 且 只 有 分 配 邊 ， 去 掉 分配

42、 邊 ， 將 其 變 為 孤 立 結(jié) 點(diǎn) 。2） 再 把 相 應(yīng) 的 資 源 分 配 給 一 個(gè) 等 待 該 資 源 的 進(jìn) 程 ，即 將 某 進(jìn) 程 的 申 請(qǐng) 邊 變 為 分 配 邊 。3） 重 復(fù) (1) (2)操 作 直 到 無 法 再 化 簡(jiǎn) , 若 所 有 結(jié) 點(diǎn) 都 為孤 立 結(jié) 點(diǎn) 則 無 死 鎖 , 否 則 死 鎖 發(fā) 生 3.7.2死 鎖 的 解 除 一 旦 死 鎖 發(fā) 生 則 采 取 專 門 的 措 施 ， 解 除死 鎖 并 以 最 小 的 代 價(jià) 恢 復(fù) 操 作 系 統(tǒng) 運(yùn) 行 。死 鎖 的 解 除 (關(guān) 鍵 是 代 價(jià) 最 小 )：1） 重 新 啟 動(dòng)2） 撤 消 進(jìn)

43、 程3） 剝 奪 資 源4） 進(jìn) 程 回 退 1. 處 理 機(jī) 調(diào) 度 (1) 高 級(jí) 調(diào) 度 (作 業(yè) 調(diào) 度 接 納 調(diào) 度 或 長(zhǎng) 程 調(diào) 度 ) 將 后 備 隊(duì) 列 中 作 業(yè) 調(diào) 入 內(nèi) 存 ,并 創(chuàng) 建 進(jìn) 程 。 (2)低 級(jí) 調(diào) 度 (進(jìn) 程 調(diào) 度 ,短 程 調(diào) 度 ) 從 就 緒 隊(duì) 列 中 選 中 一 進(jìn) 程 ,把 CPU使 用 權(quán) 交 給 它 。 (3)中 級(jí) 調(diào) 度 : 內(nèi) 存 緊 張 時(shí) 將 內(nèi) 存 的 進(jìn) 程 掛 起 調(diào) 到 外 存 或 內(nèi) 存 稍 有 空 閑 時(shí) 將 它 激 活 重 新 調(diào) 入 內(nèi) 存 2. 進(jìn) 程 調(diào) 度 方 式 (1)非 搶 占 方 式 (N

44、on preemptive mode) (2)搶 占 方 式 (Preemptive mode)3. 進(jìn) 程 調(diào) 度 的 時(shí) 機(jī) (1) 執(zhí) 行 進(jìn) 程 正 確 完 成 或 錯(cuò) 誤 終 止 (2) 執(zhí) 行 進(jìn) 程 提 出 I/O請(qǐng) 求 , 等 待 I/O完 成 時(shí) ; (3) 分 時(shí) 系 統(tǒng) 時(shí) 間 片 輪 轉(zhuǎn) , 分 給 進(jìn) 程 的 時(shí) 間 片 用 完 時(shí) (4) 優(yōu) 先 級(jí) 調(diào) 度 , 搶 占 方 式 中 有 更 高 優(yōu) 先 級(jí) 進(jìn) 程 就 緒 (5) 執(zhí) 行 進(jìn) 程 執(zhí) 行 wait、 阻 塞 原 語 和 喚 醒 原 語 等 操 作 4. 調(diào) 度 算 法(1)先 進(jìn) 先 出 調(diào) 度 算

45、法 (FIFO) (先 來 先 服 務(wù) FCFS)(2)短 作 業(yè) (進(jìn) 程 )優(yōu) 先 調(diào) 度 算 法 (SJF,SPF)(3)優(yōu) 先 權(quán) 調(diào) 度 算 法 (HPFHighest Priority First)(4)高 響 應(yīng) 比 優(yōu) 先 調(diào) 度 算 法(5)時(shí) 間 片 輪 轉(zhuǎn) 調(diào) 度 算 法(6)多 隊(duì) 列 反 饋 調(diào) 度 算 法5. 常 見 的 實(shí) 時(shí) 調(diào) 度 算 法(1) 最 早 截 止 時(shí) 間 優(yōu) 先 算 法 (Earliest Deadline First)(2) 最 低 松 弛 度 優(yōu) 先 算 法 (Least Laxity First)6. 調(diào) 度 的 實(shí) 現(xiàn) 過 程 保 存 現(xiàn)

46、 進(jìn) 程 現(xiàn) 場(chǎng) 、 更 新 它 的 PCB、 把 它 移 至 合 適 隊(duì) 列 選 擇 要 執(zhí) 行 的 進(jìn) 程 、 更 新 它 的 PCB、 恢 復(fù) 新 進(jìn) 程 現(xiàn) 場(chǎng) 7. 死 鎖 (Deadlock)的 定 義 ：進(jìn) 程 組 中 各 進(jìn) 程 都 無 限 等 待 被 該 組 另 一 進(jìn) 程 所 占 的 資 源注 意 ： 參 與 死 鎖 的 進(jìn) 程 最 少 是 兩 個(gè) 、 至 少 有 兩 個(gè) 已 占 有 資 源 、 該 組 所 有 進(jìn) 程 都 在 等 待 資 源8.產(chǎn) 生 死 鎖 的 四 個(gè) 必 要 條 件 (1) 互 斥 條 件 (資 源 獨(dú) 占 ): 一 個(gè) 資 源 只 能 給 一 個(gè) 進(jìn)

47、 程 使 用 (2) 請(qǐng) 求 和 保 持 條 件 : 部 分 分 配 , 保 持 原 資 源 申 請(qǐng) 新 資 源 (3) 不 可 剝 奪 條 件 : (不 可 強(qiáng) 占 , 只 能 由 占 有 者 自 愿 釋 放 ) (4) 循 環(huán) 等 待 條 件 : 形 成 等 待 環(huán)9. 死 鎖 的 預(yù) 防 (強(qiáng) 限 制 ) 破 壞 產(chǎn) 生 死 鎖 的 四 個(gè) 必 要 條 件 之 一 (后 3條 )10. 避 免 死 鎖 的 銀 行 家 算 法 (寬 限 制 ) 檢 查 每 次 分 配 后 是 否 仍 存 在 安 全 分 配 序 列 避 免 了 死 鎖 且 資 源 利 用 率 高 11. 死 鎖 的 檢 測(cè)

48、 允 許 死 鎖 發(fā) 生 ,OS應(yīng) 不 斷 檢 測(cè) 死 鎖 是 否 發(fā) 生12. 資 源 分 配 圖結(jié) 點(diǎn) 集 : 各 進(jìn) 程 結(jié) 點(diǎn) P, 各 資 源 類 結(jié) 點(diǎn) R邊 集 : 元 素 為 有 序 二 元 組 , 分 配 邊 (rj,pi) 申 請(qǐng) 邊 (pi,rj) 13. 死 鎖 定 理資 源 分 配 圖 無 環(huán) 路 , 則 沒 有 死 鎖 , 有 環(huán) 路 則 可 能 存 在 死 鎖 若 各 資 源 類 只 含 一 個(gè) 資 源 , 環(huán) 路 是 死 鎖 的 充 分 必 要 條 件14. 資 源 分 配 圖 化 簡(jiǎn) 方 法 () (1)找 只 有 分 配 邊 的 進(jìn) 程 結(jié) 點(diǎn) ,去 掉 分

49、 配 邊 變 為 孤 立 結(jié) 點(diǎn) (2)把 相 應(yīng) 的 資 源 分 配 給 等 待 進(jìn) 程 , 申 請(qǐng) 邊 變 為 分 配 邊 重 復(fù) (1) (2) 直 到 無 法 再 化 簡(jiǎn) , 若 仍 有 環(huán) 路 則 死 鎖 發(fā) 生15. 死 鎖 的 解 除 (關(guān) 鍵 是 代 價(jià) 最 小 )：重 新 啟 動(dòng) 、 撤 消 進(jìn) 程 、 剝 奪 資 源 、 進(jìn) 程 回 退 課 后 題 P102 16、 17、 18、 19、 20 補(bǔ) 充 1: 三 個(gè) 進(jìn) 程 共 享 四 個(gè) 資 源 , 這 些 資 源 的 分 配 與釋 放 只 能 一 次 一 個(gè) , 已 知 每 一 進(jìn) 程 最 多 需 要 兩 個(gè) 資源 ,

50、 請(qǐng) 問 該 系 統(tǒng) 會(huì) 發(fā) 生 死 鎖 碼 ？ 試 說 明 原 因 。 補(bǔ) 充 2: 設(shè) 三 個(gè) 進(jìn) 程 P1, P2, P3, 各 按 如 下 順 序 執(zhí) 行 ： 進(jìn) 程 P1 進(jìn) 程 P2 進(jìn) 程 P3 在 執(zhí) 行 時(shí) 能 否 產(chǎn) 生 死 鎖 ？ 如 果 可 能 ， 請(qǐng) 說 明 在什 么 情 況 下 會(huì) 產(chǎn) 生 死 鎖 ？ 并 給 出 一 個(gè) 防 止 死 鎖 產(chǎn) 生的 修 改 辦 法 。P（ S1）P（ S2） :V（ S1）V（ S2） P（ S3）P（ S1） :V（ S3）V（ S1） P（ S2）P（ S3） :V（ S2）V（ S3） 上 機(jī) 安 排 : 院 機(jī) 房 二 樓電

51、科 1-2： 第 七 、 八 周 周 一 、 三 . 3-4節(jié)電 科 3-4： 第 九 、 十 周 周 一 、 三 . 3-4節(jié)計(jì) 科 1-3： 第 七 、 八 周 周 一 . 5-6節(jié) 周 三 . 1-2節(jié)內(nèi) 容 : p 1 進(jìn) 程 管 理 ，要 求 : 事 先 預(yù) 習(xí) 看 懂 程 序P10 func timeint() 函 數(shù) 模 擬 時(shí) 間 片 中 斷 process1, process2, process3 模 擬 3 個(gè) 進(jìn) 程P14 case 配 合 goto 及 “ 進(jìn) 程 ” 中 的 標(biāo) 號(hào) 等 模 擬 并 發(fā)其 中 的 if 語 句 的 條 件 改 為 ：else if (x

52、=0.33)and(x=0.67)and(exe=3) P 3 框 圖 2 改 為 ： 進(jìn) 程 調(diào) 度 過 程 schedulerpd:=find; 選 優(yōu) 先 數(shù) 最 小 的 pdpdnilpd=nil and exe=nil pd優(yōu) exe優(yōu)exe=nilpcbexe.status:=r;pcbpd.status:=e;exe:=pd; 調(diào) 度pcbpd.status:=e;exe:=pd; 調(diào) 度i:=pcbexe.inum; 恢 復(fù) 現(xiàn) 場(chǎng)addr:= pcbexe. addr;scheduler:=exe; 返 回Y Y Y NNN NY send 發(fā) 送 receive 接 收init 初 始 化 random 隨 機(jī) 數(shù) find 選 進(jìn) 程 scheduler 調(diào) 度 block 阻 塞 p wait操 作 wakeup 喚 醒 v signal操 作 timeint 時(shí) 間 片 中 斷 eexit 退 出 process1、 process1、 process1 模 擬 3個(gè) 并 發(fā) 進(jìn) 程main 主 程 序