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

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

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

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

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

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

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

7、3) 進 行 進 程 上 下 文 的 切 換 當 進 程 調 度 選 中 一 個 進 程 占 有 CPU時 , 進 程 調 度 程序 要 做 的 主 要 工 作 則 是 進 行 進 程 上 下 文 切 換 : 將 正 在執(zhí) 行 進 程 的 運 行 現 場 保 留 在 該 進 程 的 PCB中 , 以 便 以 后該 進 程 恢 復 執(zhí) 行 。 將 剛 選 中 進 程 的 運 行 現 場 恢 復 起 來 , 并 將 CPU的 控 制 權 交 給 被 選 中 進 程 , 使 其 執(zhí) 行 。 2. 進 程 調 度 方 式 (1)非 搶 占 方 式 (Non preemptive mode) 在 非 搶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、,0),讓 P4等 待4) 若 P0請 求 資 源 ,發(fā) 出 請 求 向 量 Request(0,2,0)假 定 分 配 ,資 源 為 : 檢 查 此 刻 的 安 全 性 ： Available(2,1,0)已 不 滿 足 任 何進 程 的 需 要 , 不 安 全 ; 不 予 分 配 Available 仍 為 (2,3,0) 。 Max Allocation Need Available 進 程 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 進 程 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請 求 改 為 Request(0,1,0)假 定 分 配 , 資 源 變 為 : 進 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 死 鎖 的 檢 測 與 解 除 允 許 死 鎖 發(fā) 生 ， 系 統(tǒng) 必 須 提 供 檢 測 和 解 除 死 鎖的 手 段 , 操 作 系 統(tǒng) 應 不 斷 監(jiān) 視 系 統(tǒng)

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

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

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

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

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

45、法 (FIFO) (先 來 先 服 務 FCFS)(2)短 作 業(yè) (進 程 )優(yōu) 先 調 度 算 法 (SJF,SPF)(3)優(yōu) 先 權 調 度 算 法 (HPFHighest Priority First)(4)高 響 應 比 優(yōu) 先 調 度 算 法(5)時 間 片 輪 轉 調 度 算 法(6)多 隊 列 反 饋 調 度 算 法5. 常 見 的 實 時 調 度 算 法(1) 最 早 截 止 時 間 優(yōu) 先 算 法 (Earliest Deadline First)(2) 最 低 松 弛 度 優(yōu) 先 算 法 (Least Laxity First)6. 調 度 的 實 現 過 程 保 存 現

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

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

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

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

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

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

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