《處理機調(diào)度》PPT課件

第 三 章 處 理 機 調(diào) 度 與 死 鎖 3.1 處 理 機 調(diào) 度 的 層 次 3.2 調(diào) 度 隊 列 模 型 和 調(diào) 度 準 則 3.3 調(diào) 度 算 法 3.4 實 時 調(diào) 度 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 3.6 預 防 死 鎖 的 方 法 3.7 死 鎖 的 檢 測 與 解 除 第 三 章 處 理 機 調(diào) 度 與 死 鎖 3.1 處 理 機 調(diào) 度 的 層 次 3.1.1 高 級 調(diào) 度 （ 作 業(yè) 調(diào) 度 、 長 程 調(diào) 度 ） 按 照 某 種 算 法 ， 決 定 把 外 存 上 處 于 后 備 隊列 中 的 那 些 作 業(yè) 調(diào) 入 內(nèi) 存 。第 三 章 處 理 機 調(diào) 度 與 死 鎖 作 業(yè) 步 (Job Step)：通常，在作業(yè)運行期間，把其中的每一個加工步驟稱為一個作業(yè)步1 作 業(yè) 和 作 業(yè) 步 作 業(yè) (Job)：作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對程序的運行進行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 2 作 業(yè) 控 制 塊 JCB(Job Control Block)在 多 道 批 處 理 系 統(tǒng) 中 為 每 個 作 業(yè) 設 置 了 一 個 作 業(yè)控 制 塊 （ JCB),它 是 作 業(yè) 在 系 統(tǒng) 中 存 在 的 標 志 .當 作 業(yè) 進 入 系 統(tǒng) 時 ， OS為 其 建 立 JCB.3 作 業(yè) 調(diào) 度 作 業(yè) 調(diào) 度 的 主 要 功 能 是 根 據(jù) JCB， 審 查 系 統(tǒng) 能 否 滿 足 用 戶作 業(yè) 的 資 源 需 求 ， 以 及 按 照 一 定 的 算 法 ， 從 外 存 的 后 備 隊 列 中選 取 某 些 作 業(yè) 調(diào) 入 內(nèi) 存 ， 并 為 它 們 創(chuàng) 建 進 程 、 分 配 必 要 的 資 源 。然 后 再 將 新 創(chuàng) 建 的 進 程 插 入 就 緒 隊 列 ， 準 備 執(zhí) 行 。 因 此 ， 有 時也 把 作 業(yè) 調(diào) 度 稱 為 接 納 調(diào) 度 (Admission Scheduling)。 周 轉 時 間 3.1.2. 低 級 調(diào) 度 (Low Level Scheduling)-進 程 調(diào) 度 決 定 就 緒 隊 列 中 的 哪 個 進 程 應 獲 得 處 理 機 ， 由 分 派 程 序 執(zhí)行 把 處 理 機 分 配 給 該 進 程 的 具 體 操 作 1) 非 搶 占 方 式 (Non-preemptive Mode) :自 愿 放 棄 2) 搶 占 方 式 (Preemptive Mode) ： 時 間 片 ； 優(yōu) 先 級第 三 章 處 理 機 調(diào) 度 與 死 鎖 引 入 的 主 要 目 的 ： 為 了 提 高 內(nèi) 存 利 用 率 和 系 統(tǒng) 吞 吐 量 使 暫 時 不 能 運 行 的 進 程 不 再 占 用 寶 貴 的 內(nèi) 存 資 源 ， 將它 們 調(diào) 至 外 存 上 暫 時 等 待 （ 就 緒 駐 外 存 狀 態(tài) 或 掛 起 狀 態(tài) ） ，當 這 些 進 程 重 又 具 備 運 行 條 件 、 且 內(nèi) 存 又 有 空 閑 時 ， 由 中級 調(diào) 度 來 決 定 把 外 存 上 的 哪 些 又 具 備 運 行 條 件 的 就 緒 進 程 ，重 新 調(diào) 入 內(nèi) 存 ， 并 修 改 其 狀 態(tài) 為 就 緒 狀 態(tài) ， 掛 在 就 緒 隊 列上3.1.3. 中 級 調(diào) 度 (Intermediate-Level Scheduling) 中 程 調(diào) 度第 三 章 處 理 機 調(diào) 度 與 死 鎖 3. 2 調(diào) 度 隊 列 模 型 和 調(diào) 度 準 則3.2.1. 調(diào) 度 隊 列 模 型 圖 3 - 1 僅 具 有 進 程 調(diào) 度 的 調(diào) 度 隊 列 模 型 第 三 章 處 理 機 調(diào) 度 與 死 鎖 就 緒 隊 列阻 塞 隊 列 進 程 調(diào) 度 CPU 進 程 完 成等 待 事 件交 互 用 戶事件出現(xiàn) 時 間 片 完1.僅 有 進 程 調(diào) 度 的 調(diào) 度 隊 列 模 型 CPU進 程 i進 程 調(diào) 度進 程 j進 程 k進 程 p就緒隊列 時間片完 進 程 f進 程 b進 程 n進 程 l 阻塞隊列等 待 事 件事 件 出 現(xiàn) 進 程 完 成進 程 X 第 三 章 處 理 機 調(diào) 度 與 死 鎖 2. 具 有 高 級 和 低 級 調(diào) 度 的 調(diào) 度 隊 列 模 型 圖 3-2 具 有 高 、 低 兩 級 調(diào) 度 的 調(diào) 度 隊 列 模 型 第 三 章 處 理 機 調(diào) 度 與 死 鎖 就 緒 隊 列 進 程 調(diào) 度 CPU 進 程 完 成等 待 事 件 1作 業(yè)調(diào) 度事 件 1出 現(xiàn) 時 間 片 完 等 待 事 件 2 事 件 2出 現(xiàn) 等 待 事 件 n事 件 n出 現(xiàn)后 備 隊 列 作業(yè)3 作業(yè)2 作業(yè)1 作 業(yè) 調(diào) 度 進程2 就 緒 隊 列 CPU阻 塞 隊 列 1 阻 塞 隊 列 n阻 塞 隊 列 2 進 程 調(diào) 度等 待 事 件 1進程1 等 待 事 件 2等 待 事 件 n 事 件 1出 現(xiàn)事 件 2出 現(xiàn)事 件 n出 現(xiàn)第 三 章 處 理 機 調(diào) 度 與 死 鎖 3. 同 時 具 有 三 級 調(diào) 度 的 調(diào) 度 隊 列 模 型 圖 3-3 具 有 三 級 調(diào) 度 時 的 調(diào) 度 隊 列 模 型 第 三 章 處 理 機 調(diào) 度 與 死 鎖 就 緒 隊 列 進 程 調(diào) 度 CPU就 緒 ， 掛 起 隊 列中 級 調(diào) 度 阻 塞 ， 掛 起 隊 列阻 塞 隊 列 等 待 事 件 進 程 完 成時 間 片 完作 業(yè) 調(diào) 度交 互 型 作 業(yè)后 備 隊 列批 量 作 業(yè) 掛 起事 件 出 現(xiàn)事件出現(xiàn) 3.2.2 選 擇 調(diào) 度 方 式 和 調(diào) 度 算 法 的 若 干 準 則 1. 面 向 用 戶 的 準 則 (1) 周 轉 時 間 短 。 周 轉 時 間 ： 從 作 業(yè) 被 提 交給 系 統(tǒng) 開 始 ， 到 作 業(yè) 完 成為 止 的 這 段 時 間 間 隔 ni SiiTTnW 11作 業(yè) 的 周 轉 時 間 T與 系 統(tǒng) 為 它 提 供 服 務 的 時 間 TS之 比 ， 即W=T/TS， 稱 為 帶 權 周 轉 時 間 第 三 章 處 理 機 調(diào) 度 與 死 鎖 作 業(yè) 在 外 存 后 備 隊 列 上 的 等 待 時 間進 程 在 就 緒 隊 列 上 等 待 進 程 調(diào) 度 的 時 間 進 程 在 CPU上 執(zhí) 行 的 時 間進 程 等 待 I/O操 作 完 成 的 時 間 (2) 響 應 時 間 快 。 (3) 截 止 時 間 的 保 證 。 (4) 優(yōu) 先 權 準 則 。 第 三 章 處 理 機 調(diào) 度 與 死 鎖 ni iTnT 11 ni iTTnW 1 s1平 均 周 轉 時 間 平 均 帶 權 周 轉 時 間 2. 面 向 系 統(tǒng) 的 準 則 (1) 系 統(tǒng) 吞 吐 量 高 。 ?(2) 處 理 機 利 用 率 好 。 (3) 各 類 資 源 的 平 衡 利 用 。 第 三 章 處 理 機 調(diào) 度 與 死 鎖 第 三 章 處 理 機 調(diào) 度 與 死 鎖 3.3 調(diào) 度 算 法 先 來 先 服 務 調(diào) 度 算 法 FCFS 短 作 業(yè) (進 程 )優(yōu) 先 調(diào) 度 算 法 SJ(P)F 高 優(yōu) 先 權 優(yōu) 先 調(diào) 度 算 法 基 于 時 間 片 的 輪 轉 調(diào) 度 算 法 3.3.1 先 來 先 服 務 和 短 作 業(yè) (進 程 )優(yōu) 先 調(diào) 度 算 法 第 三 章 處 理 機 調(diào) 度 與 死 鎖 1 先 來 先 服 務 （ FCFS） 調(diào) 度 算 法作 業(yè) 調(diào) 度 ： 從 后 備 作 業(yè) 隊 列 中 ， 選 擇 一 個 或 多 個 最 先進 入 該 隊 列 的 作 業(yè) ， 將 它 們 調(diào) 入 內(nèi) 存 運 行 ；進 程 調(diào) 度 ： 就 緒 隊 列 按 進 入 的 先 后 次 序 排 列 ， 調(diào) 度 時 ，選 隊 首 進 程 投 入 運 行 。 進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10 先來先服務FCFS到 達 時 間 0完 成 時 間 10周 轉 時 間 10帶 權 周 轉 時 間 1 5 35 301.2 10 40 30 6 15 50 353.5 105/4=26.2511.7/4=2.925 例 ： FCFS算 法 比 較 有 利 于 長 作 業(yè) (進 程 )， 而 不利 于 短 作 業(yè) (進 程 )。 下 表 列 出 了 A、 B、 C、 D四個 作 業(yè) 分 別 到 達 系 統(tǒng) 的 時 間 、 要 求 服 務 的 時 間 、開 始 執(zhí) 行 的 時 間 及 各 自 的 完 成 時 間 ， 并 計 算 出 各自 的 周 轉 時 間 和 帶 權 周 轉 時 間 。 2、 短 作 業(yè) （ 進 程 ） 優(yōu) 先 調(diào) 度 算 法 （ SJ(P)F） 短 作 業(yè) 優(yōu) 先 SJF調(diào) 度 算 法 是 從 后 備 隊 列 中 選 擇 一 個或 若 干 個 估 計 運 行 時 間 最 短 的 作 業(yè) ， 將 它 們 調(diào) 入 內(nèi)存 運 行 。 短 進 程 SPF優(yōu) 先 調(diào) 度 算 法 是 從 就 緒 隊 列 中 選 出 一 估計 運 行 時 間 最 短 的 進 程 ， 將 處 理 機 分 配 給 它 ， 使 它立 即 執(zhí) 行 并 一 直 執(zhí) 行 到 完 成 ， 或 發(fā) 生 某 事 件 而 被 阻塞 放 棄 處 理 機 時 ， 再 重 新 調(diào) 度 。 進 程 名 A B C D 平 均就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10先 來 先 服 務（ FCFS） 周 轉 時 間 10 30 30 35 26.25帶 權 周 轉 時 間 1 1.2 6 3.5 2.925短 進 程 優(yōu) 先（ SPF） 周 轉 時 間 10 45 5 10 17.5帶 權 周 轉 時 間 1 1.8 1 1 1.2FCFS和 SPF調(diào) 度 算 法 的 性 能 比 較 3.3.2 高 優(yōu) 先 權 優(yōu) 先 調(diào) 度 算 法 1. 優(yōu) 先 權 調(diào) 度 算 法 的 類 型 非 搶 占 式 優(yōu) 先 權 算 法 搶 占 式 優(yōu) 先 權 調(diào) 度 算 法 2. 優(yōu) 先 權 的 類 型 1) 靜 態(tài) 優(yōu) 先 權 第 三 章 處 理 機 調(diào) 度 與 死 鎖 確 定 進 程 優(yōu) 先 權 的 依 據(jù) 有 如 下 三 個 方 面 ： (1) 進 程 類 型 。 (2) 進 程 對 資 源 的 需 求 。 (3) 用 戶 要 求 。 進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10優(yōu) 先 權 0 1 3 2開 始 時 間完 成 時 間周 轉 時 間帶 權 周 轉 時 間 高優(yōu)先權優(yōu)先( 靜態(tài)) 非 搶 占 式 優(yōu) 先 權 調(diào) 度0 25 10 1510 50 15 2510 45 5 101 1.8 1 1 A0 t10 20 5030 40B C5 15 3525 45D進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10優(yōu) 先 權 0 1 3 2 高優(yōu)先權優(yōu)先( 靜態(tài))搶 占 式 優(yōu) 先 權 調(diào) 度 2) 動 態(tài) 優(yōu) 先 權 動 態(tài) 優(yōu) 先 權 是 指 ， 在 創(chuàng) 建 進 程 時 所 賦 予 的 優(yōu) 先 權 ， 是 可以 隨 進 程 的 推 進 或 隨 其 等 待 時 間 的 增 加 而 改 變 的 ， 以 便 獲 得更 好 的 調(diào) 度 性 能 。 例 如 ， 我 們 可 以 規(guī) 定 ， 在 就 緒 隊 列 中 的 進程 ， 隨 其 等 待 時 間 的 增 長 ， 其 優(yōu) 先 權 以 速 率 a提 高 。 當 采 用 搶占 式 優(yōu) 先 權 調(diào) 度 算 法 時 ， 如 果 再 規(guī) 定 當 前 進 程 的 優(yōu) 先 權 以 速率 b下 降 ， 則 可 防 止 一 個 長 作 業(yè) 長 期 地 壟 斷 處 理 機 。 第 三 章 處 理 機 調(diào) 度 與 死 鎖 3) 高 響 應 比 優(yōu) 先 調(diào) 度 算 法 優(yōu) 先 權 的 變 化 規(guī) 律 可 描 述 為 ： 由 于 等 待 時 間 與 服 務 時 間 之 和 ， 就 是 系 統(tǒng) 對 該 作 業(yè) 的 響 應時 間 ， 故 該 優(yōu) 先 權 又 相 當 于 響 應 比 RP。 據(jù) 此 ， 又 可 表 示 為 ： 第 三 章 處 理 機 調(diào) 度 與 死 鎖 要 求 服 務 時 間要 求 服 務 時 間等 待 時 間R + 要 求 服 務 時 間等 待 時 間要 求 服 務 時 間要 求 服 務 時 間等 待 時 間R + 3.3.3 基 于 時 間 片 的 輪 轉 調(diào) 度 算 法 1. 時 間 片 輪 轉 法 RR 在 早 期 的 時 間 片 輪 轉 法 中 ， 系 統(tǒng) 將 所 有 的 就 緒 進 程 按 先來 先 服 務 的 原 則 ， 排 成 一 個 隊 列 ， 每 次 調(diào) 度 時 ， 把 CPU分 配給 隊 首 進 程 ， 并 令 其 執(zhí) 行 一 個 時 間 片 。 時 間 片 的 大 小 從 幾ms到 幾 百 ms。 當 執(zhí) 行 的 時 間 片 用 完 時 ， 由 一 個 計 時 器 發(fā) 出時 鐘 中 斷 請 求 ， 調(diào) 度 程 序 便 據(jù) 此 信 號 來 停 止 該 進 程 的 執(zhí) 行 ，并 將 它 送 往 就 緒 隊 列 的 末 尾 ； 然 后 ， 再 把 處 理 機 分 配 給 就 緒隊 列 中 新 的 隊 首 進 程 ， 同 時 也 讓 它 執(zhí) 行 一 個 時 間 片 。 這 樣 就可 以 保 證 就 緒 隊 列 中 的 所 有 進 程 ， 在 一 給 定 的 時 間 內(nèi) ， 均 能獲 得 一 時 間 片 的 處 理 機 執(zhí) 行 時 間 。第 三 章 處 理 機 調(diào) 度 與 死 鎖 A0 t10 20 5030 40B C5 15 3525 45D進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10 時間片輪轉法RR時 間 片 為 5個 單 位 時 間 2. 多 級 反 饋 隊 列 調(diào) 度 算 法 第 三 章 處 理 機 調(diào) 度 與 死 鎖 就 緒 隊 列 1就 緒 隊 列 2就 緒 隊 列 3就 緒 隊 列 n S1S2S3 至 CPU至 CPU至 CPU至 CPU(時 間 片 ： S 1S 2S3)圖 3-5 多 級 反 饋 隊 列 調(diào) 度 算 法 3. 多 級 反 饋 隊 列 調(diào) 度 算 法 的 性 能 (1) 終 端 型 作 業(yè) 用 戶 。 (2) 短 批 處 理 作 業(yè) 用 戶 。 (3) 長 批 處 理 作 業(yè) 用 戶 。第 三 章 處 理 機 調(diào) 度 與 死 鎖 假 定 在 單 CPU條 件 下 有 下 列 要 執(zhí) 行 的 作 業(yè) :作 業(yè) A B C D E到 達 時 間 0 1 2 3 4運 行 時 間 6 1 2 1 5優(yōu) 先 級 3 1 3 4 2（ 1） 用 一 個 執(zhí) 行 時 間 圖 描 述 在 下 列 算 法 時 各 自 執(zhí) 行 這 些 作 業(yè) 的 情 況 ：FCFS、 RR（ 時 間 片 1） 和 非 搶 占 式 優(yōu) 先 級 。（ 2） 對 于 上 述 每 種 算 法 ， 各 個 作 業(yè) 的 周 轉 時 間 是 多 少 ？ 平 均 周 轉 時 間是 多 少 ？ （ 3） 對 于 上 述 每 種 算 法 ， 各 個 作 業(yè) 的 帶 權 周 轉 時 間 是 多 少 ？ 平 均 帶 權周 轉 時 間 是 多 少 ？ 作 業(yè) A B C D E到 達 時 間 0 1 2 3 4運 行 時 間 6 1 2 1 5優(yōu) 先 級 3 1 3 4 2FCFS 周 轉 時 間 6 6 7 7 11帶 權 周 轉 時 間 1 6 3.5 7 2.2RR 周 轉 時 間 13 1 6 2 11帶 權 周 轉 時 間 2.5 1 2.5 1 2非 搶 占 式優(yōu) 先 周 轉 時 間 6 14 7 4 10帶 權 周 轉 時 間 1 14 3.5 4 2非 搶 占 高響 應 比 周 轉 時 間 6 6 8 5 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t 3.4 實 時 調(diào) 度 3.4.1 實 現(xiàn) 實 時 調(diào) 度 的 基 本 條 件 1. 提 供 必 要 的 信 息 :就 緒 時 間 開 始 截 止 時 間 和 完 成 截 止 時 間2. 系 統(tǒng) 處 理 能 力 強假 定 系 統(tǒng) 中 有 m個 周 期 性 的 硬 實 時 任 務 ， 它 們 的 處 理 時 間 可 表 示 為C i， 周 期 時 間 表 示 為 Pi， 則 在 單 處 理 機 情 況 下 ， 必 須 滿 足 下 面 的 限制 條 件 ： 3. 采 用 搶 占 式 調(diào) 度 機 制4. 具 有 快 速 切 換 機 制 第 三 章 處 理 機 調(diào) 度 與 死 鎖 11 mi iiPC 3.4.2 實 時 調(diào) 度 算 法 的 分 類 1. 非 搶 占 式 調(diào) 度 算 法 (1) 非 搶 占 式 輪 轉 調(diào) 度 算 法 。 (2) 非 搶 占 式 優(yōu) 先 調(diào) 度 算 法 。 第 三 章 處 理 機 調(diào) 度 與 死 鎖 2. 搶 占 式 調(diào) 度 算 法 (1) 基 于 時 鐘 中 斷 的 搶 占 式 優(yōu) 先 權 調(diào) 度 算 法 。(2) 立 即 搶 占 (Immediate Preemption)的 優(yōu) 先 權 調(diào) 度 算 法 。 圖 3-6 實 時 進 程 調(diào) 度 第 三 章 處 理 機 調(diào) 度 與 死 鎖 . (a) 非 搶 占 式 輪 轉 調(diào) 度 當 前 進 程 實 時 進 程實 時 進 程 請 求 調(diào) 度 實 時 進 程 搶 占 當 前進 程 并 立 即 執(zhí) 行(d) 立 即 搶 占 的 優(yōu) 先 權 調(diào) 度調(diào) 度 時 間進 程 1 進 程 2實 時 進 程 要 求 調(diào) 度 進 程 n 實 時 進 程調(diào) 度 實 時 進 程 運 行(b) 非 搶 占 式 優(yōu) 先 權 調(diào) 度當 前 進 程 實 時 進 程實 時 進 程 請 求 調(diào) 度 當 前 進 程 運 行 完 成調(diào) 度 時 間 當 前 進 程實 時 進 程 請 求 調(diào) 度 時 鐘 中 斷 到 來 時調(diào) 度 時 間(c) 基 于 時 鐘 中 斷 搶 占 的 優(yōu) 先 權 搶 占 調(diào) 度調(diào) 度 時 間 實 時 進 程 3.4.3 常 用 的 幾 種 實 時 調(diào) 度 算 法 1. 最 早 截 止 時 間 優(yōu) 先 即 EDF(Earliest Deadline First)算 法 開 始 截 止 時 間2. 最 低 松 弛 度 優(yōu) 先 即 LLF(Least Laxity First)算 法 松 馳 度 =完 成 截 止 時 間 -其 本 身 運 行 時 間 -當 前 時 間 第 三 章 處 理 機 調(diào) 度 與 死 鎖 進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10開 始 截 止 時 間 5 15 25 20 最早截止時間優(yōu)先EDF搶 占 式 調(diào) 度A0 t10 20 5030 40B C5 15 3525 45 D 進 程 名 A B C D就 緒 時 間 0 5 10 15要 求 服 務 時 間 10 25 5 10完 成 截 止 時 間 30 40 35 55松 馳 度 最低松馳度優(yōu)先LLF 搶 占 式 調(diào) 度A0 t10 20 5030 40B C5 15 3525 45D 20 10 20 3015 1550 50 2150 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條件死 鎖 （ Deadlock） ,是 指 多 個 進 程在 運 行 過 程 中 因 爭 奪 資 源 而 造 成 的一 種 僵 局 ， 當 進 程 處 于 這 種 狀 態(tài) 時 ，若 無 外 力 作 用 ， 它 們 都 將 無 法 再 向前 推 進 。 3.5.1 產(chǎn) 生 死 鎖 的 原 因 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 3.5.3 處 理 死 鎖 的 基 本 方 法 3.5.1 產(chǎn) 生 死 鎖 的 原 因 產(chǎn) 生 死 鎖 的 原 因 可 歸 結 為 如 下 兩 點 ：1.競 爭 資 源 。2.進 程 間 推 進 順 序 非 法 ?？?剝 奪 和 非 剝 奪 性 資 源永 久 性 資 源 和 臨 時 性 資 源 . Request(B); Request(A); Release(A); Release(B); P2. Request(A); Request(B); Release(B); Release(A); P1v例 如 ：死 鎖 發(fā) 生 ： 雙 方 都 擁 有 部 分 資 源 ， 同 時 在 請 求 對 方 已占 有 的 資 源 。 競 爭 非 剝 奪 性 資 源P1: P2: v (consumable resource)： 可 以 動 態(tài) 生 成 和 消 耗 ，一 般 不 限 制 數(shù) 量 。 如 硬 件 中 斷 、 信 號 、 消 息 、 緩 沖區(qū) 內(nèi) 的 數(shù) 據(jù) 。 . Receive(P1,N); Send(P1,R); P2. Receive(P2,R); Send(P2,N); P1死 鎖 發(fā) 生 ： 雙 方 都 等 待 對 方 去 生 成 資 源 ，如 次 序 ： P1 P2競 爭 臨 時 性 資 源P1: P2: 正 確 的 進 程 推 進 順 序 P1: Release(S1); Request(S3); P2: Release(S2); Request(S1); P3: Release(S3); Request(S2); 死 鎖 的 進 程 推 進 順 序 P1: Request(S3); Release(S1); P2: Request(S1); Release(S2); P3: Request(S2); Release(S3);進 程 推 進 順 序 不 當 引 起 死 鎖S3 S1S2P1P3 P2 P2Rel(R1)P2Rel(R2)P2Req(R1)P2 Req(R2 ) P 1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2) D進 程 推 進 順 序 對 死 鎖 的 影 響 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件雖 然 進 程 在 運 行 過 程 中 可 能 發(fā) 生 死 鎖 ，但 死 鎖 的 發(fā) 生 也 必 須 具 備 一 定 的 條 件 ?？?以 看 出 ， 必 須 具 備 以 下 四 個 條 件 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 1.互 斥 條 件 ： 指 進 程 對 所 分 配 到 的 資源 進 行 排 他 性 使 用 ， 即 在 一 段 時 間內(nèi) 某 資 源 只 由 一 個 進 程 占 用 。 如 果此 時 還 有 其 他 進 程 請 求 該 資 源 ， 則請 求 者 只 能 等 待 ， 直 至 占 有 該 資 源的 進 程 用 畢 釋 放 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 2.請 求 和 保 持 條 件 ： 指 進 程 已 經(jīng) 保 持了 至 少 一 個 資 源 ， 但 又 提 出 了 新 的資 源 請 求 ， 而 該 資 源 又 被 其 他 進 程占 有 ， 此 時 請 求 進 程 阻 塞 ， 但 又 對自 己 已 獲 得 的 其 他 資 源 保 持 不 放 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 3.不 剝 奪 條 件 ： 指 進 程 已 獲 得 的 資 源 ，在 未 使 用 完 之 前 ， 不 能 被 剝 奪 ， 只能 在 使 用 完 時 由 自 己 釋 放 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件4.環(huán) 路 等 待 條 件 ： 指 在 發(fā) 生 死 鎖 時 ， 必 然存 在 一 個 “ 進 程 資 源 ” 的 環(huán) 形 鏈 ，即 進 程 集 合 P0,P1,P2,Pn中 的 P0正 在 等 待 一 個 P1占 用 的 資 源 ； P1正 在等 待 一 個 P2占 用 的 資 源 ， ， Pn正在 等 待 一 個 已 被 P0占 用 的 資 源 。 3.5.3 處 理 死 鎖 的 基 本 方 法一 、 預 防 死 鎖 消 除 產(chǎn) 生 死 鎖 的 必 要 條 件二 、 避 免 死 鎖 分 配 資 源 時 防 止 進 入 不 安 全 狀 態(tài)三 、 檢 測 死 鎖 不 預 防 死 鎖 ， 出 現(xiàn) 死 鎖 就 解 除四 、 解 除 死 鎖 與 檢 測 死 鎖 配 合 使 用 思 考 題 一 臺 計 算 機 共 8臺 磁 帶 機 ， 由 N個 進 程 共享 ， 每 個 進 程 最 多 要 3臺 ， 問 N為 多 少 時不 會 有 死 鎖 ， 為 什 么 ？ 3.6 預 防 與 避 免 死 鎖 的 方 法 3.6.1 預 防 死 鎖 3.6.2 系 統(tǒng) 安 全 狀 態(tài) 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 3.6.1 預 防 死 鎖 預 防 死 鎖 的 方 法 是 使 四 個 必 要 條 件 中 的 第 2、 3、 4條件 之 一 不 能 成 立 ， 來 避 免 發(fā) 生 死 鎖 。 至 于 必 要 條 件 1，因 為 它 是 由 設 備 的 固 有 條 件 所 決 定 的 ， 不 僅 不 能 改變 ， 還 應 加 以 保 證 。 下 面 分 別 對 三 種 情 況 加 以 說 明 ： 1、 摒 棄 “ 請 求 和 保 持 ” 條 件 不 分 配 或 者 全 部 分 配 靜 態(tài) 資 源 分 配 法 優(yōu) 點 ： 算 法 簡 單 、 易 于 實 現(xiàn) 且 很 安 全 缺 點 ： 資 源 浪 費 嚴 重 ， 進 程 延 遲 運 行 。 2、 摒 棄 “ 不 剝 奪 ” 條 件 系 統(tǒng) 規(guī) 定 ， 進 程 是 逐 個 地 提 出 對 資 源 的 要 求的 。 當 一 個 已 經(jīng) 保 持 了 某 些 資 源 的 進 程 ， 提出 新 的 要 求 不 被 滿 足 時 必 須 釋 放 它 已 經(jīng) 保 持的 所 有 資 源 ， 待 以 后 需 要 時 再 重 新 申 請 。 從而 摒 棄 了 “ 不 剝 奪 ” 條 件 。 該 方 法 實 現(xiàn) 起 來 比 較 復 雜 且 付 出 很 大 代 價 。可 能 會 造 成 前 功 盡 棄 ， 反 復 申 請 和 釋 放 (抖動 )情 況 。 3、 摒 棄 “ 環(huán) 路 等 待 ” 條 件 有 序 資 源 分 配 法 ： 與 前 兩 種 策 略 比 較 ， 資 源 利 用 率 和 系 統(tǒng) 吞 吐 量 都 有較 明 顯 的 改 善 。 但 也 存 在 嚴 重 問 題 ： 為 資 源 編 號 限 制 新 設 備 的 增 加 ；進 程 使 用 設 備 順 序 與 申 請 順 序 相 反 ； 限 制 用 戶 編 程自 由 。 r1 r2 rk rm. .申 請 次 序 3.6.2 系 統(tǒng) 安 全 狀 態(tài) 在 避 免 死 鎖 的 方 法 中 把 系 統(tǒng) 的 狀 態(tài) 分 為安 全 狀 態(tài) 和 不 安 全 狀 態(tài) ， 只 要 能 使 系 統(tǒng)始 終 都 處 于 安 全 狀 態(tài) ， 便 可 避 免 發(fā) 生 死鎖 。 檢 測可 滿 足 請 求 分 配 不 分 配安 全不 安 全系 統(tǒng) 處 于 安 全 狀 態(tài) ： 存 在 安 全 進 程 序 列 進 程 序 列 安 全 ， p1,p2,pn可 依 次 進 行 完 。安 全 不 安 全死 鎖1、 安 全 狀 態(tài) 2、 安 全 狀 態(tài) 之 例 假 定 系 統(tǒng) 中 有 三 個 進 程 A、 B和 C， 共 有 12臺 磁 帶 機 。 進程 A總 共 要 求 10臺 ， B和 C分 別 要 求 4臺 和 9臺 。 假 設 在 T0時 刻 ， 進 程 A、 B和 C已 分 別 獲 得 5臺 、 2臺 和 2臺 ， 尚 有 3臺 未 分 配 ， 如 下 表 所 示 ： t0時 刻 安 全 ？ C請 求 1臺 磁 帶 機 ， 安 全 嗎 ？進 程 最 大 需 求 已 分 配 可 用A 10 5 3B 4 2C 9 2 23 3.6.3 利 用 銀 行 家 算 法 避 免 死鎖1. 銀 行 家 算 法 中 的 數(shù) 據(jù) 結 構（ 1） 可 利 用 資 源 向 量 Available。 這 是 一 個 含 有 m個 元 素 的數(shù) 組 ， 其 中 的 每 一 個 元 素 代 表 一 類 可 利 用 的 資 源 數(shù) 目 ;（ 2） 最 大 需 求 矩 陣 Max。 這 是 一 個 n*m的 矩 陣 ， 它 定 義 了 系統(tǒng) 中 n個 進 程 中 的 每 一 個 進 程 對 m類 資 源 的 最 大 需 求 。（ 3） 分 配 矩 陣 Allocation。 這 也 是 一 個 n*m的 矩 陣 ， 它 定 義了 系 統(tǒng) 中 每 一 類 資 源 當 前 已 分 配 給 每 一 進 程 的 資 源 數(shù) 。（ 4） 需 求 矩 陣 Need。 這 也 是 一 個 n*m的 矩 陣 ， 用 以 表 示 每一 個 進 程 尚 需 的 各 類 資 源 數(shù) ?？?利 用 資 源 向 量Available(A B C) 2 5 3 最 大 需 求 矩 陣 Max(A B C)P1 3 2 2P2 5 2 2P3 7 4 5 分 配 矩 陣Allocation(A B C) 2 0 0 2 1 1 3 0 2 需 求 矩 陣Need(A B C) 1 2 2 3 1 1 4 4 3- = 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖2. 銀 行 家 算 法 設 Requesti是 進 程 Pi的 請 求 向 量 ， 如 果 Requesti j=K， 表 示 進 程 Pi需 要 K個 Rj類 型 的 資 源 。當 Pi發(fā) 出 資 源 請 求 后 ， 系 統(tǒng) 按 下 述 步 驟 進 行檢 查 ： Pi請 求 資 源RequestINeedI 請 求 超 量 ， 錯 返RequestIAvailable不 滿 足 ， 等 待 Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安 全確 認 ， 分 配 完成 Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等 待 FTF TT F銀行家算法 案 例 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖3. 安 全 性 算 法（ 1） 設 置 兩 個 向 量 ： 工 作 向 量 work： 表 示 系 統(tǒng) 可 提 供 給 進 程 繼 續(xù) 運 行 的各 類 資 源 數(shù) 目 ， 在 執(zhí) 行 安 全 算 法 開 始 時 ，work:=Available; Finish:它 表 示 系 統(tǒng) 是 否 有 足 夠 的 資 源 分 配 進 程 ， 使之 運 行 完 成 。 開 始 時 先 做 Finishi:=false;當 有 足 夠資 源 分 配 給 進 程 時 ， 再 令 Finishi:=true。 安全性檢測算法FWork:=Available;Finish:=false; 有 滿 足 條 件 的 j:Finishj=falseNeedjWorkFinishj=true;Work:=Work+AllocationjT j ,finishj=trueT F安 全 不 安 全 4、銀行家算法之例 假 定 系 統(tǒng) 中 有 四 個 進 程 P1,P2,P3,P4和 三 類 資 源A,B,C， 各 種 資 源 的 數(shù) 量 分 別 為 10、 4、 7， 在T0時 刻 的 資 源 分 配 情 況 如 下 所 示 : 資 源 情 況進 程 MaxA B C AllocationA B C NeedA B C AvailableA B CP1P2P3P4 3 2 2 9 0 22 2 24 3 3 2 0 03 0 22 1 10 0 2 1 2 26 0 0 0 1 14 3 1 3 3 2 資 源 情 況進 程 WorkA B C AllocationA B C Allocation+Work Finish(1)T0時 刻 的 安 全 性 ： 4、銀行家算法之例 資 源 情 況進 程 MaxA B C AllocationA B C NeedA B C AvailableA B CP1P2P3P4 3 2 2 9 0 22 2 24 3 3 2 0 03 0 22 1 10 0 2 1 2 26 0 0 0 1 14 3 1 3 3 2Work P1 3 3 2 2 0 0 5 3 2 true P3 5 3 2 2 1 1 7 4 3 true P4 7 4 3 0 0 2 7 4 5 true P2 7 4 5 3 0 2 10 4 7 trueT0時 刻 系 統(tǒng) 是 安 全 的 ， 存 在 安 全 序 列P1,P3,P4,P2 Request1(1,0,2)=Need1(1,2,3)； Request1(1,0,2)=Available(3,3,2)； 試 探 性 把 資 源 分 配 給 P1,并 修 改 相 應 的 數(shù) 據(jù) ,形 成 的資 源 變 化 情 況 上 表 所 示 ； 由 所 執(zhí) 行 安 全 性 檢 查 得 知 :可 以 找 到 一 個 安 全 序 列P1,P3,P4,P2,即 此 時 系 統(tǒng) 是 安 全 的 ,可 以 滿 足 請 求 。 資 源 情 況進 程 WorkA B C AllocationA B C Allocation+Work Finish(2)P1請 求 資 源 ， 發(fā) 出 請 求 向 量 Request1(1,0,2)； 4、銀行家算法之例 資 源 情 況進 程 MaxA B C AllocationA B C NeedA B C AvailableA B CP1P2P3P4 3 2 2 9 0 22 2 24 3 3 2 0 03 0 22 1 10 0 2 1 2 26 0 0 0 1 14 3 1 3 3 2Request1(1,0,2) P1 2 3 0 3 0 2 5 3 2 true P3 5 3 2 2 1 1 7 4 3 true P4 7 4 3 0 0 2 7 4 5 true P2 7 4 5 3 0 2 10 4 7 true2 03 2 0 0 Work Request4(3,3,0)Need4(4,3,1)； Request4(3,3,0)Available(2,3,0)；(3)P4請 求 資 源 ， 發(fā) 出 請 求 向 量 Request4(3,3,0)； 4、銀行家算法之例 資 源 情 況進 程 MaxA B C AllocationA B C NeedA B C AvailableA B CP1P2P3P4 3 2 2 9 0 22 2 24 3 3 3 0 23 0 22 1 10 0 2 0 2 06 0 0 0 1 14 3 1 2 3 0Request4(3,3,0) 當 前 系 統(tǒng) 資 源 不 能 滿 足 P4的 請 求 ， 不 予 分 配 ； Request4(0,2,0)Need4(4,3,1)； Request4(0,2,0)Available(2,3,0)；(4)P4請 求 資 源 ， 發(fā) 出 請 求 向 量 Request4(0,2,0)； 4、銀行家算法之例 資 源 情 況進 程 MaxA B C AllocationA B C NeedA B C AvailableA B CP1P2P3P4 3 2 2 9 0 22 2 24 3 3 3 0 23 0 22 1 10 0 2 0 2 06 0 0 0 1 14 3 1 2 3 0Request4(0,2,0) 系 統(tǒng) 試 探 性 為 P4分 配 資 源 ， 并 修 改 相 應 的 數(shù) 據(jù) ， 開 成 的 資 源分 配 情 況 如 上 所 示 ； 1 2 4 1 Work 進 行 安 全 性 檢 查 ： 可 用 資 源 Available(2,1,0)已 不 能 滿 足 任 何進 程 的 需 要 ， 系 統(tǒng) 進 入 不 安 全 狀 態(tài) ， 故 系 統(tǒng) 不 能 滿 足 P4的 請 求 3.7 死 鎖 的 檢 測 與 解 除 3.7.1 死 鎖 的 檢 測 3.7.2 死 鎖 的 解 除 3.7.1 死 鎖 的 檢 測 當 系 統(tǒng) 為 進 程 分 配 資 源 時 ， 若 未 采 取 任何 限 制 性 措 施 ， 則 系 統(tǒng) 必 須 提 供 檢 測 和解 除 死 鎖 的 手 段 ， 為 此 系 統(tǒng) 必 須 ：1. 保 存 有 關 資 源 的 請 求 和 分 配 信 息 ；2. 提 供 一 種 算 法 ， 以 利 用 這 些 信 息 來 檢 測系 統(tǒng) 是 否 已 進 入 死 鎖 狀 態(tài) 。 1 資 源 分 配 圖定 義 : G=(V,E), V=PR, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj)(rj,pi), piP, rjR. 申 請 邊 (pi,rj): pi申 請 rj； 分 配 邊 (rj,pi): rj分 配 pi;圖 示 ： 進 程 ： 資 源 ： 申 請 邊 ： 由 進 程 到 資 源 類 ； 分 配 邊 ： 由 資 源 實 例 到 進 程 。 r2 P2P1r1 1 資 源 分 配 圖申 請 ： pi申 請 rj中 的 一 個 資 源 實 例 ， 由 pi向 rj畫 一 申請 邊 ， 如 可 滿 足 ， 改 為 分 配 邊 。釋 放 ： 去 掉 分 配 邊 。 例 子 （ 無 環(huán) 路 ， 無 死 鎖 ）p1 p2 p3r1 r3r2 r4 例 子 （ 有 環(huán) 路 ， 有 死 鎖 ）p1 p2 p3r1 r3r2 r4 例 子 （ 有 環(huán) 路 ， 無 死 鎖 ）p1 p2p3p4r1 r2 2、 資 源 分 配 圖 的 簡 化 簡 化 方 法 如 下 ：1.在 資 源 分 配 圖 中 找 出 一 個 既 不 阻 塞 又 非 獨 立 的進 程 結 點 Pi， 在 順 利 的 情 況 下 運 行 完 畢 ， 釋 放 其占 有 的 全 部 資 源 。2.由 于 釋 放 了 資 源 ， 這 樣 能 使 其 它 被 阻 塞 的 進 程獲 得 資 源 繼 續(xù) 運 行 。3.在 經(jīng) 過 一 系 列 簡 化 后 若 能 消 去 圖 中 的 所 有 的 邊 ，使 所 有 進 程 結 點 都 孤 立 ， 則 稱 該 圖 是 可 完 全 簡 化的 ， 反 之 是 不 可 完 全 簡 化 的 。 3、 死 鎖 定 理 可 以 證 明 ： S狀 態(tài) 為 死 鎖 狀 態(tài) 的 充 分 條件 是 當 且 僅 當 S狀 態(tài) 的 資 源 分 配 圖 是 不可 完 全 簡 化 的 。 例 ： 根 據(jù) 死 鎖 定 理 判 斷 如 下 所 示 的 資 源 分配 圖 是 否 存 在 死 鎖 。 P1 P2 P3R1 R2 R3 P1 P3 P2 R1 R2圖 1 圖 2 3.7.2 死 鎖 的 解 除 當 發(fā) 現(xiàn) 進 程 死 鎖 時 ， 便 應 立 即 把 它 們 從死 鎖 狀 態(tài) 中 解 脫 出 來 。 常 采 用 的 方 法 是 ：1. 剝 奪 資 源 。 從 其 他 進 程 剝 奪 足 夠 數(shù) 量 的資 源 給 死 鎖 進 程 以 解 除 死 鎖 狀 態(tài) 。2. 撤 銷 進 程 。 最 簡 單 的 是 讓 全 部 進 程 都 死掉 ； 溫 和 一 點 的 是 按 照 某 種 順 序 逐 個 撤銷 進 程 ， 直 至 有 足 夠 的 資 源 可 用 ， 使 死鎖 狀 態(tài) 消 除 為 止 。 本 章 基 礎 要 點1. 要 使 當 前 運 行 進 程 總 是 優(yōu) 先 級 最 高 的 進 程 ，則 應 選 擇 ：搶 占 優(yōu) 先 級 調(diào) 度 算 法 。2. 在 分 時 系 統(tǒng) 中 ， 進 程 調(diào) 度 經(jīng) 常 采 用 ：時 間 片 輪 轉 調(diào) 度 算 法 。3. 進 程 運 行 結 束 、 進 入 阻 塞 狀 態(tài) 、 時 間 片 用完 、 有 更 高 優(yōu) 先 級 的 進 程 進 入 就 緒 隊 列 等原 因 均 可 引 起 ：進 程 調(diào) 度 。 本 章 基 礎 要 點4. 進 程 調(diào) 度 采 用 時 間 片 輪 轉 法 時 ， 時 間 片 過大 ， 就 會 使 輪 轉 法 轉 化 為 ：先 來 先 服 務 調(diào) 度 算 法 。5. 進 程 的 調(diào) 度 方 式 有 兩 種 ：搶 占 式 調(diào) 度 和 非 搶 占 式 調(diào) 度 。6. 死 鎖 產(chǎn) 生 的 四 個 必 要 條 件 是 ：互 斥 、 請 求 和 保 持 、 不 剝 奪 和 環(huán) 路 等 待 。7. 在 有 m個 進 程 的 系 統(tǒng) 中 出 現(xiàn) 死 鎖 時 ， 死 鎖 進程 的 個 數(shù) k應 滿 足 的 條 件 是 ： 2 k m。 本 章 基 礎 要 點8. 不 讓 死 鎖 發(fā) 生 的 策 略 可 分 為 靜 態(tài) 和 動 態(tài) 兩種 ， 死 鎖 避 免 屬 于 ： 動 態(tài) 策 略 。9. 某 系 統(tǒng) 中 有 3個 并 發(fā) 進 程 ， 都 需 要 同 類 資 源 4個 ， 該 系 統(tǒng) 絕 對 不 會 發(fā) 生 死 鎖 的 最 少 資 源 個數(shù) 是 ： 10。10. 資 源 的 按 序 分 配 策 略 可 以 破 壞 ： 環(huán) 路 等 待 條 件 。11. 預 先 靜 態(tài) 分 配 法 可 以 破 壞 ： 請 求 和 保 持 條 件 。 課 堂 練 習一 個 系 統(tǒng) 具 有 150個 存 儲 單 元 ， 在 T0時 刻 按 下 表 所 示分 配 給 3個 進 程 。 資 源進 程 Max allocationp1 70 25P2 60 40P3 60 45對 下 列 請 求 應 用 銀 行 家 算 法 分 別 分 析 判 斷 是 否 安 全 ？1) 第 4個 進 程 P4到 達 ， 最 大 需 求 60個 存 儲 單 元 ， 當 前 分 配 25個 單 元 。 2) 第 4個 進 程 P4到 達 ， 最 大 需 求 50個 存 儲 單 元 ， 當 前 分 配 35個 單 元 。如 果 是 安 全 的 ， 請 給 出 一 個 可 能 的 安 全 序 列 ； 如 果 不 是 安 全 的 ， 請 說 明 原 因 。