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

1、第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 3.1 處 理 機(jī) 調(diào) 度 的 層 次 3.2 調(diào) 度 隊(duì) 列 模 型 和 調(diào) 度 準(zhǔn) 則 3.3 調(diào) 度 算 法 3.4 實(shí) 時(shí) 調(diào) 度 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 3.6 預(yù) 防 死 鎖 的 方 法 3.7 死 鎖 的 檢 測(cè) 與 解 除 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 3.1 處 理 機(jī) 調(diào) 度 的 層 次 3.1.1 高 級(jí) 調(diào) 度 （ 作 業(yè) 調(diào) 度 、 長 程 調(diào) 度 ） 按 照 某 種 算 法 ， 決 定 把 外 存 上 處 于 后 備 隊(duì)列 中 的 那 些 作 業(yè) 調(diào) 入 內(nèi) 存 。第 三 章

2、處 理 機(jī) 調(diào) 度 與 死 鎖 作 業(yè) 步 (Job Step)：通常，在作業(yè)運(yùn)行期間，把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步1 作 業(yè) 和 作 業(yè) 步 作 業(yè) (Job)：作業(yè)是一個(gè)比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)該說明書來對(duì)程序的運(yùn)行進(jìn)行控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。 2 作 業(yè) 控 制 塊 JCB(Job Control Block)在 多 道 批 處 理 系 統(tǒng) 中 為 每 個(gè) 作 業(yè) 設(shè) 置 了 一 個(gè) 作 業(yè)控 制 塊 （ JCB),它 是 作 業(yè) 在 系 統(tǒng) 中 存 在 的 標(biāo) 志 .當(dāng) 作 業(yè) 進(jìn)

3、 入 系 統(tǒng) 時(shí) ， OS為 其 建 立 JCB.3 作 業(yè) 調(diào) 度 作 業(yè) 調(diào) 度 的 主 要 功 能 是 根 據(jù) JCB， 審 查 系 統(tǒng) 能 否 滿 足 用 戶作 業(yè) 的 資 源 需 求 ， 以 及 按 照 一 定 的 算 法 ， 從 外 存 的 后 備 隊(duì) 列 中選 取 某 些 作 業(yè) 調(diào) 入 內(nèi) 存 ， 并 為 它 們 創(chuàng) 建 進(jìn) 程 、 分 配 必 要 的 資 源 。然 后 再 將 新 創(chuàng) 建 的 進(jìn) 程 插 入 就 緒 隊(duì) 列 ， 準(zhǔn) 備 執(zhí) 行 。 因 此 ， 有 時(shí)也 把 作 業(yè) 調(diào) 度 稱 為 接 納 調(diào) 度 (Admission Scheduling)。 周 轉(zhuǎn) 時(shí) 間

4、3.1.2. 低 級(jí) 調(diào) 度 (Low Level Scheduling)-進(jìn) 程 調(diào) 度 決 定 就 緒 隊(duì) 列 中 的 哪 個(gè) 進(jìn) 程 應(yīng) 獲 得 處 理 機(jī) ， 由 分 派 程 序 執(zhí)行 把 處 理 機(jī) 分 配 給 該 進(jìn) 程 的 具 體 操 作 1) 非 搶 占 方 式 (Non-preemptive Mode) :自 愿 放 棄 2) 搶 占 方 式 (Preemptive Mode) ： 時(shí) 間 片 ； 優(yōu) 先 級(jí)第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 引 入 的 主 要 目 的 ： 為 了 提 高 內(nèi) 存 利 用 率 和 系 統(tǒng) 吞 吐 量 使 暫 時(shí) 不 能 運(yùn) 行 的 進(jìn)

5、 程 不 再 占 用 寶 貴 的 內(nèi) 存 資 源 ， 將它 們 調(diào) 至 外 存 上 暫 時(shí) 等 待 （ 就 緒 駐 外 存 狀 態(tài) 或 掛 起 狀 態(tài) ） ，當(dāng) 這 些 進(jìn) 程 重 又 具 備 運(yùn) 行 條 件 、 且 內(nèi) 存 又 有 空 閑 時(shí) ， 由 中級(jí) 調(diào) 度 來 決 定 把 外 存 上 的 哪 些 又 具 備 運(yùn) 行 條 件 的 就 緒 進(jìn) 程 ，重 新 調(diào) 入 內(nèi) 存 ， 并 修 改 其 狀 態(tài) 為 就 緒 狀 態(tài) ， 掛 在 就 緒 隊(duì) 列上3.1.3. 中 級(jí) 調(diào) 度 (Intermediate-Level Scheduling) 中 程 調(diào) 度第 三 章 處 理 機(jī) 調(diào) 度 與

6、 死 鎖 3. 2 調(diào) 度 隊(duì) 列 模 型 和 調(diào) 度 準(zhǔn) 則3.2.1. 調(diào) 度 隊(duì) 列 模 型 圖 3 - 1 僅 具 有 進(jìn) 程 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 就 緒 隊(duì) 列阻 塞 隊(duì) 列 進(jìn) 程 調(diào) 度 CPU 進(jìn) 程 完 成等 待 事 件交 互 用 戶事件出現(xiàn) 時(shí) 間 片 完1.僅 有 進(jìn) 程 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 CPU進(jìn) 程 i進(jìn) 程 調(diào) 度進(jìn) 程 j進(jìn) 程 k進(jìn) 程 p就緒隊(duì)列 時(shí)間片完 進(jìn) 程 f進(jìn) 程 b進(jìn) 程 n進(jìn) 程 l 阻塞隊(duì)列等 待 事 件事 件 出 現(xiàn) 進(jìn) 程 完 成進(jìn) 程 X 第 三 章 處 理 機(jī)

7、 調(diào) 度 與 死 鎖 2. 具 有 高 級(jí) 和 低 級(jí) 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 圖 3-2 具 有 高 、 低 兩 級(jí) 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 就 緒 隊(duì) 列 進(jìn) 程 調(diào) 度 CPU 進(jìn) 程 完 成等 待 事 件 1作 業(yè)調(diào) 度事 件 1出 現(xiàn) 時(shí) 間 片 完 等 待 事 件 2 事 件 2出 現(xiàn) 等 待 事 件 n事 件 n出 現(xiàn)后 備 隊(duì) 列 作業(yè)3 作業(yè)2 作業(yè)1 作 業(yè) 調(diào) 度 進(jìn)程2 就 緒 隊(duì) 列 CPU阻 塞 隊(duì) 列 1 阻 塞 隊(duì) 列 n阻 塞 隊(duì) 列 2 進(jìn) 程 調(diào) 度等 待 事 件 1進(jìn)程1 等 待 事 件

8、 2等 待 事 件 n 事 件 1出 現(xiàn)事 件 2出 現(xiàn)事 件 n出 現(xiàn)第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 3. 同 時(shí) 具 有 三 級(jí) 調(diào) 度 的 調(diào) 度 隊(duì) 列 模 型 圖 3-3 具 有 三 級(jí) 調(diào) 度 時(shí) 的 調(diào) 度 隊(duì) 列 模 型 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 就 緒 隊(duì) 列 進(jìn) 程 調(diào) 度 CPU就 緒 ， 掛 起 隊(duì) 列中 級(jí) 調(diào) 度 阻 塞 ， 掛 起 隊(duì) 列阻 塞 隊(duì) 列 等 待 事 件 進(jìn) 程 完 成時(shí) 間 片 完作 業(yè) 調(diào) 度交 互 型 作 業(yè)后 備 隊(duì) 列批 量 作 業(yè) 掛 起事 件 出 現(xiàn)事件出現(xiàn) 3.2.2 選 擇 調(diào) 度 方 式 和 調(diào) 度

9、算 法 的 若 干 準(zhǔn) 則 1. 面 向 用 戶 的 準(zhǔn) 則 (1) 周 轉(zhuǎn) 時(shí) 間 短 。 周 轉(zhuǎn) 時(shí) 間 ： 從 作 業(yè) 被 提 交給 系 統(tǒng) 開 始 ， 到 作 業(yè) 完 成為 止 的 這 段 時(shí) 間 間 隔 ni SiiTTnW 11作 業(yè) 的 周 轉(zhuǎn) 時(shí) 間 T與 系 統(tǒng) 為 它 提 供 服 務(wù) 的 時(shí) 間 TS之 比 ， 即W=T/TS， 稱 為 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 作 業(yè) 在 外 存 后 備 隊(duì) 列 上 的 等 待 時(shí) 間進(jìn) 程 在 就 緒 隊(duì) 列 上 等 待 進(jìn) 程 調(diào) 度 的 時(shí) 間 進(jìn) 程 在 CPU上 執(zhí) 行 的 時(shí) 間進(jìn) 程

10、 等 待 I/O操 作 完 成 的 時(shí) 間 (2) 響 應(yīng) 時(shí) 間 快 。 (3) 截 止 時(shí) 間 的 保 證 。 (4) 優(yōu) 先 權(quán) 準(zhǔn) 則 。 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 ni iTnT 11 ni iTTnW 1 s1平 均 周 轉(zhuǎn) 時(shí) 間 平 均 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 2. 面 向 系 統(tǒng) 的 準(zhǔn) 則 (1) 系 統(tǒng) 吞 吐 量 高 。 ?(2) 處 理 機(jī) 利 用 率 好 。 (3) 各 類 資 源 的 平 衡 利 用 。 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 3.3 調(diào) 度 算 法 先 來 先 服 務(wù) 調(diào) 度 算

11、法 FCFS 短 作 業(yè) (進(jìn) 程 )優(yōu) 先 調(diào) 度 算 法 SJ(P)F 高 優(yōu) 先 權(quán) 優(yōu) 先 調(diào) 度 算 法 基 于 時(shí) 間 片 的 輪 轉(zhuǎn) 調(diào) 度 算 法 3.3.1 先 來 先 服 務(wù) 和 短 作 業(yè) (進(jìn) 程 )優(yōu) 先 調(diào) 度 算 法 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 1 先 來 先 服 務(wù) （ FCFS） 調(diào) 度 算 法作 業(yè) 調(diào) 度 ： 從 后 備 作 業(yè) 隊(duì) 列 中 ， 選 擇 一 個(gè) 或 多 個(gè) 最 先進(jìn) 入 該 隊(duì) 列 的 作 業(yè) ， 將 它 們 調(diào) 入 內(nèi) 存 運(yùn) 行 ；進(jìn) 程 調(diào) 度 ： 就 緒 隊(duì) 列 按 進(jìn) 入 的 先 后 次 序 排 列 ， 調(diào) 度 時(shí)

12、 ，選 隊(duì) 首 進(jìn) 程 投 入 運(yùn) 行 。 進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10 先來先服務(wù)FCFS到 達(dá) 時(shí) 間 0完 成 時(shí) 間 10周 轉(zhuǎn) 時(shí) 間 10帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 1 5 35 301.2 10 40 30 6 15 50 353.5 105/4=26.2511.7/4=2.925 例 ： FCFS算 法 比 較 有 利 于 長 作 業(yè) (進(jìn) 程 )， 而 不利 于 短 作 業(yè) (進(jìn) 程 )。 下 表 列 出 了 A、 B、 C、 D四個(gè) 作 業(yè) 分 別 到 達(dá) 系 統(tǒng) 的 時(shí) 間 、 要 求 服 務(wù) 的 時(shí)

13、 間 、開 始 執(zhí) 行 的 時(shí) 間 及 各 自 的 完 成 時(shí) 間 ， 并 計(jì) 算 出 各自 的 周 轉(zhuǎn) 時(shí) 間 和 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 。 2、 短 作 業(yè) （ 進(jìn) 程 ） 優(yōu) 先 調(diào) 度 算 法 （ SJ(P)F） 短 作 業(yè) 優(yōu) 先 SJF調(diào) 度 算 法 是 從 后 備 隊(duì) 列 中 選 擇 一 個(gè)或 若 干 個(gè) 估 計(jì) 運(yùn) 行 時(shí) 間 最 短 的 作 業(yè) ， 將 它 們 調(diào) 入 內(nèi)存 運(yùn) 行 。 短 進(jìn) 程 SPF優(yōu) 先 調(diào) 度 算 法 是 從 就 緒 隊(duì) 列 中 選 出 一 估計(jì) 運(yùn) 行 時(shí) 間 最 短 的 進(jìn) 程 ， 將 處 理 機(jī) 分 配 給 它 ， 使 它立 即 執(zhí) 行 并

14、一 直 執(zhí) 行 到 完 成 ， 或 發(fā) 生 某 事 件 而 被 阻塞 放 棄 處 理 機(jī) 時(shí) ， 再 重 新 調(diào) 度 。 進(jìn) 程 名 A B C D 平 均就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10先 來 先 服 務(wù)（ FCFS） 周 轉(zhuǎn) 時(shí) 間 10 30 30 35 26.25帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 1 1.2 6 3.5 2.925短 進(jìn) 程 優(yōu) 先（ SPF） 周 轉(zhuǎn) 時(shí) 間 10 45 5 10 17.5帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 1 1.8 1 1 1.2FCFS和 SPF調(diào) 度 算 法 的 性 能 比 較 3.3.2 高 優(yōu) 先 權(quán) 優(yōu) 先 調(diào) 度

15、 算 法 1. 優(yōu) 先 權(quán) 調(diào) 度 算 法 的 類 型 非 搶 占 式 優(yōu) 先 權(quán) 算 法 搶 占 式 優(yōu) 先 權(quán) 調(diào) 度 算 法 2. 優(yōu) 先 權(quán) 的 類 型 1) 靜 態(tài) 優(yōu) 先 權(quán) 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 確 定 進(jìn) 程 優(yōu) 先 權(quán) 的 依 據(jù) 有 如 下 三 個(gè) 方 面 ： (1) 進(jìn) 程 類 型 。 (2) 進(jìn) 程 對(duì) 資 源 的 需 求 。 (3) 用 戶 要 求 。 進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10優(yōu) 先 權(quán) 0 1 3 2開 始 時(shí) 間完 成 時(shí) 間周 轉(zhuǎn) 時(shí) 間帶 權(quán) 周 轉(zhuǎn) 時(shí) 間

16、高優(yōu)先權(quán)優(yōu)先( 靜態(tài)) 非 搶 占 式 優(yōu) 先 權(quán) 調(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進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10優(yōu) 先 權(quán) 0 1 3 2 高優(yōu)先權(quán)優(yōu)先( 靜態(tài))搶 占 式 優(yōu) 先 權(quán) 調(diào) 度 2) 動(dòng) 態(tài) 優(yōu) 先 權(quán) 動(dòng) 態(tài) 優(yōu) 先 權(quán) 是 指 ， 在 創(chuàng) 建 進(jìn) 程 時(shí) 所 賦 予 的 優(yōu) 先 權(quán) ， 是 可以 隨 進(jìn) 程 的 推 進(jìn) 或 隨 其 等 待 時(shí) 間 的 增 加 而 改 變 的 ，

17、以 便 獲 得更 好 的 調(diào) 度 性 能 。 例 如 ， 我 們 可 以 規(guī) 定 ， 在 就 緒 隊(duì) 列 中 的 進(jìn)程 ， 隨 其 等 待 時(shí) 間 的 增 長 ， 其 優(yōu) 先 權(quán) 以 速 率 a提 高 。 當(dāng) 采 用 搶占 式 優(yōu) 先 權(quán) 調(diào) 度 算 法 時(shí) ， 如 果 再 規(guī) 定 當(dāng) 前 進(jìn) 程 的 優(yōu) 先 權(quán) 以 速率 b下 降 ， 則 可 防 止 一 個(gè) 長 作 業(yè) 長 期 地 壟 斷 處 理 機(jī) 。 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 3) 高 響 應(yīng) 比 優(yōu) 先 調(diào) 度 算 法 優(yōu) 先 權(quán) 的 變 化 規(guī) 律 可 描 述 為 ： 由 于 等 待 時(shí) 間 與 服 務(wù) 時(shí) 間 之

18、 和 ， 就 是 系 統(tǒng) 對(duì) 該 作 業(yè) 的 響 應(yīng)時(shí) 間 ， 故 該 優(yōu) 先 權(quán) 又 相 當(dāng) 于 響 應(yīng) 比 RP。 據(jù) 此 ， 又 可 表 示 為 ： 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 要 求 服 務(wù) 時(shí) 間要 求 服 務(wù) 時(shí) 間等 待 時(shí) 間R + 要 求 服 務(wù) 時(shí) 間等 待 時(shí) 間要 求 服 務(wù) 時(shí) 間要 求 服 務(wù) 時(shí) 間等 待 時(shí) 間R + 3.3.3 基 于 時(shí) 間 片 的 輪 轉(zhuǎn) 調(diào) 度 算 法 1. 時(shí) 間 片 輪 轉(zhuǎn) 法 RR 在 早 期 的 時(shí) 間 片 輪 轉(zhuǎn) 法 中 ， 系 統(tǒng) 將 所 有 的 就 緒 進(jìn) 程 按 先來 先 服 務(wù) 的 原 則 ， 排 成 一

19、 個(gè) 隊(duì) 列 ， 每 次 調(diào) 度 時(shí) ， 把 CPU分 配給 隊(duì) 首 進(jìn) 程 ， 并 令 其 執(zhí) 行 一 個(gè) 時(shí) 間 片 。 時(shí) 間 片 的 大 小 從 幾ms到 幾 百 ms。 當(dāng) 執(zhí) 行 的 時(shí) 間 片 用 完 時(shí) ， 由 一 個(gè) 計(jì) 時(shí) 器 發(fā) 出時(shí) 鐘 中 斷 請(qǐng) 求 ， 調(diào) 度 程 序 便 據(jù) 此 信 號(hào) 來 停 止 該 進(jìn) 程 的 執(zhí) 行 ，并 將 它 送 往 就 緒 隊(duì) 列 的 末 尾 ； 然 后 ， 再 把 處 理 機(jī) 分 配 給 就 緒隊(duì) 列 中 新 的 隊(duì) 首 進(jìn) 程 ， 同 時(shí) 也 讓 它 執(zhí) 行 一 個(gè) 時(shí) 間 片 。 這 樣 就可 以 保 證 就 緒 隊(duì) 列 中 的

20、所 有 進(jìn) 程 ， 在 一 給 定 的 時(shí) 間 內(nèi) ， 均 能獲 得 一 時(shí) 間 片 的 處 理 機(jī) 執(zhí) 行 時(shí) 間 。第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 A0 t10 20 5030 40B C5 15 3525 45D進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10 時(shí)間片輪轉(zhuǎn)法RR時(shí) 間 片 為 5個(gè) 單 位 時(shí) 間 2. 多 級(jí) 反 饋 隊(duì) 列 調(diào) 度 算 法 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 就 緒 隊(duì) 列 1就 緒 隊(duì) 列 2就 緒 隊(duì) 列 3就 緒 隊(duì) 列 n S1S2S3 至 CPU至 CPU至 CPU至

21、 CPU(時(shí) 間 片 ： S 1S 2S3)圖 3-5 多 級(jí) 反 饋 隊(duì) 列 調(diào) 度 算 法 3. 多 級(jí) 反 饋 隊(duì) 列 調(diào) 度 算 法 的 性 能 (1) 終 端 型 作 業(yè) 用 戶 。 (2) 短 批 處 理 作 業(yè) 用 戶 。 (3) 長 批 處 理 作 業(yè) 用 戶 。第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 假 定 在 單 CPU條 件 下 有 下 列 要 執(zhí) 行 的 作 業(yè) :作 業(yè) A B C D E到 達(dá) 時(shí) 間 0 1 2 3 4運(yùn) 行 時(shí) 間 6 1 2 1 5優(yōu) 先 級(jí) 3 1 3 4 2（ 1） 用 一 個(gè) 執(zhí) 行 時(shí) 間 圖 描 述 在 下 列 算 法 時(shí) 各 自

22、 執(zhí) 行 這 些 作 業(yè) 的 情 況 ：FCFS、 RR（ 時(shí) 間 片 1） 和 非 搶 占 式 優(yōu) 先 級(jí) 。（ 2） 對(duì) 于 上 述 每 種 算 法 ， 各 個(gè) 作 業(yè) 的 周 轉(zhuǎn) 時(shí) 間 是 多 少 ？ 平 均 周 轉(zhuǎn) 時(shí) 間是 多 少 ？ （ 3） 對(duì) 于 上 述 每 種 算 法 ， 各 個(gè) 作 業(yè) 的 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 是 多 少 ？ 平 均 帶 權(quán)周 轉(zhuǎn) 時(shí) 間 是 多 少 ？ 作 業(yè) A B C D E到 達(dá) 時(shí) 間 0 1 2 3 4運(yùn) 行 時(shí) 間 6 1 2 1 5優(yōu) 先 級(jí) 3 1 3 4 2FCFS 周 轉(zhuǎn) 時(shí) 間 6 6 7 7 11帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 1 6

23、 3.5 7 2.2RR 周 轉(zhuǎn) 時(shí) 間 13 1 6 2 11帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 2.5 1 2.5 1 2非 搶 占 式優(yōu) 先 周 轉(zhuǎn) 時(shí) 間 6 14 7 4 10帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 1 14 3.5 4 2非 搶 占 高響 應(yīng) 比 周 轉(zhuǎn) 時(shí) 間 6 6 8 5 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t 3.4 實(shí) 時(shí) 調(diào) 度 3.4.1 實(shí) 現(xiàn) 實(shí) 時(shí) 調(diào) 度 的 基 本 條 件 1. 提 供 必 要 的 信 息 :就 緒 時(shí) 間 開 始 截 止 時(shí) 間 和 完 成 截 止 時(shí) 間2. 系 統(tǒng) 處 理 能 力 強(qiáng)假 定 系 統(tǒng) 中 有

24、m個(gè) 周 期 性 的 硬 實(shí) 時(shí) 任 務(wù) ， 它 們 的 處 理 時(shí) 間 可 表 示 為C i， 周 期 時(shí) 間 表 示 為 Pi， 則 在 單 處 理 機(jī) 情 況 下 ， 必 須 滿 足 下 面 的 限制 條 件 ： 3. 采 用 搶 占 式 調(diào) 度 機(jī) 制4. 具 有 快 速 切 換 機(jī) 制 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 11 mi iiPC 3.4.2 實(shí) 時(shí) 調(diào) 度 算 法 的 分 類 1. 非 搶 占 式 調(diào) 度 算 法 (1) 非 搶 占 式 輪 轉(zhuǎn) 調(diào) 度 算 法 。 (2) 非 搶 占 式 優(yōu) 先 調(diào) 度 算 法 。 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 2

25、. 搶 占 式 調(diào) 度 算 法 (1) 基 于 時(shí) 鐘 中 斷 的 搶 占 式 優(yōu) 先 權(quán) 調(diào) 度 算 法 。(2) 立 即 搶 占 (Immediate Preemption)的 優(yōu) 先 權(quán) 調(diào) 度 算 法 。 圖 3-6 實(shí) 時(shí) 進(jìn) 程 調(diào) 度 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 . (a) 非 搶 占 式 輪 轉(zhuǎn) 調(diào) 度 當(dāng) 前 進(jìn) 程 實(shí) 時(shí) 進(jìn) 程實(shí) 時(shí) 進(jìn) 程 請(qǐng) 求 調(diào) 度 實(shí) 時(shí) 進(jìn) 程 搶 占 當(dāng) 前進(jìn) 程 并 立 即 執(zhí) 行(d) 立 即 搶 占 的 優(yōu) 先 權(quán) 調(diào) 度調(diào) 度 時(shí) 間進(jìn) 程 1 進(jìn) 程 2實(shí) 時(shí) 進(jìn) 程 要 求 調(diào) 度 進(jìn) 程 n 實(shí) 時(shí) 進(jìn) 程調(diào)

26、度 實(shí) 時(shí) 進(jìn) 程 運(yùn) 行(b) 非 搶 占 式 優(yōu) 先 權(quán) 調(diào) 度當(dāng) 前 進(jìn) 程 實(shí) 時(shí) 進(jìn) 程實(shí) 時(shí) 進(jìn) 程 請(qǐng) 求 調(diào) 度 當(dāng) 前 進(jìn) 程 運(yùn) 行 完 成調(diào) 度 時(shí) 間 當(dāng) 前 進(jìn) 程實(shí) 時(shí) 進(jìn) 程 請(qǐng) 求 調(diào) 度 時(shí) 鐘 中 斷 到 來 時(shí)調(diào) 度 時(shí) 間(c) 基 于 時(shí) 鐘 中 斷 搶 占 的 優(yōu) 先 權(quán) 搶 占 調(diào) 度調(diào) 度 時(shí) 間 實(shí) 時(shí) 進(jìn) 程 3.4.3 常 用 的 幾 種 實(shí) 時(shí) 調(diào) 度 算 法 1. 最 早 截 止 時(shí) 間 優(yōu) 先 即 EDF(Earliest Deadline First)算 法 開 始 截 止 時(shí) 間2. 最 低 松 弛 度 優(yōu) 先 即 LLF(Lea

27、st Laxity First)算 法 松 馳 度 =完 成 截 止 時(shí) 間 -其 本 身 運(yùn) 行 時(shí) 間 -當(dāng) 前 時(shí) 間 第 三 章 處 理 機(jī) 調(diào) 度 與 死 鎖 進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10開 始 截 止 時(shí) 間 5 15 25 20 最早截止時(shí)間優(yōu)先EDF搶 占 式 調(diào) 度A0 t10 20 5030 40B C5 15 3525 45 D 進(jìn) 程 名 A B C D就 緒 時(shí) 間 0 5 10 15要 求 服 務(wù) 時(shí) 間 10 25 5 10完 成 截 止 時(shí) 間 30 40 35 55松 馳 度 最低松馳

28、度優(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） ,是 指 多 個(gè) 進(jìn) 程在 運(yùn) 行 過 程 中 因 爭(zhēng) 奪 資 源 而 造 成 的一 種 僵 局 ， 當(dāng) 進(jìn) 程 處 于 這 種 狀 態(tài) 時(shí) ，若 無 外 力 作 用 ， 它 們 都 將 無 法 再 向前 推 進(jìn) 。 3.5.1 產(chǎn) 生 死 鎖 的 原 因 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 3.5.3 處 理 死 鎖 的 基 本 方 法 3.5.

29、1 產(chǎn) 生 死 鎖 的 原 因 產(chǎn) 生 死 鎖 的 原 因 可 歸 結(jié) 為 如 下 兩 點(diǎn) ：1.競(jìng) 爭(zhēng) 資 源 。2.進(jìn) 程 間 推 進(jìn) 順 序 非 法 。可 剝 奪 和 非 剝 奪 性 資 源永 久 性 資 源 和 臨 時(shí) 性 資 源 . Request(B); Request(A); Release(A); Release(B); P2. Request(A); Request(B); Release(B); Release(A); P1v例 如 ：死 鎖 發(fā) 生 ： 雙 方 都 擁 有 部 分 資 源 ， 同 時(shí) 在 請(qǐng) 求 對(duì) 方 已占 有 的 資 源 。 競(jìng) 爭(zhēng) 非 剝 奪 性 資

30、 源P1: P2: v (consumable resource)： 可 以 動(dòng) 態(tài) 生 成 和 消 耗 ，一 般 不 限 制 數(shù) 量 。 如 硬 件 中 斷 、 信 號(hào) 、 消 息 、 緩 沖區(qū) 內(nèi) 的 數(shù) 據(jù) 。 . Receive(P1,N); Send(P1,R); P2. Receive(P2,R); Send(P2,N); P1死 鎖 發(fā) 生 ： 雙 方 都 等 待 對(duì) 方 去 生 成 資 源 ，如 次 序 ： P1 P2競(jìng) 爭(zhēng) 臨 時(shí) 性 資 源P1: P2: 正 確 的 進(jìn) 程 推 進(jìn) 順 序 P1: Release(S1); Request(S3); P2: Release(

31、S2); Request(S1); P3: Release(S3); Request(S2); 死 鎖 的 進(jìn) 程 推 進(jìn) 順 序 P1: Request(S3); Release(S1); P2: Request(S1); Release(S2); P3: Request(S2); Release(S3);進(jìn) 程 推 進(jìn) 順 序 不 當(dāng) 引 起 死 鎖S3 S1S2P1P3 P2 P2Rel(R1)P2Rel(R2)P2Req(R1)P2 Req(R2 ) P 1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2) D進(jìn) 程 推 進(jìn) 順 序 對(duì) 死 鎖 的 影 響 3.

32、5.2 產(chǎn) 生 死 鎖 的 必 要 條 件雖 然 進(jìn) 程 在 運(yùn) 行 過 程 中 可 能 發(fā) 生 死 鎖 ，但 死 鎖 的 發(fā) 生 也 必 須 具 備 一 定 的 條 件 ?？?以 看 出 ， 必 須 具 備 以 下 四 個(gè) 條 件 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 1.互 斥 條 件 ： 指 進(jìn) 程 對(duì) 所 分 配 到 的 資源 進(jìn) 行 排 他 性 使 用 ， 即 在 一 段 時(shí) 間內(nèi) 某 資 源 只 由 一 個(gè) 進(jìn) 程 占 用 。 如 果此 時(shí) 還 有 其 他 進(jìn) 程 請(qǐng) 求 該 資 源 ， 則請(qǐng) 求 者 只 能 等 待 ， 直 至 占 有 該 資 源的 進(jìn) 程 用 畢

33、釋 放 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 2.請(qǐng) 求 和 保 持 條 件 ： 指 進(jìn) 程 已 經(jīng) 保 持了 至 少 一 個(gè) 資 源 ， 但 又 提 出 了 新 的資 源 請(qǐng) 求 ， 而 該 資 源 又 被 其 他 進(jìn) 程占 有 ， 此 時(shí) 請(qǐng) 求 進(jìn) 程 阻 塞 ， 但 又 對(duì)自 己 已 獲 得 的 其 他 資 源 保 持 不 放 。 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 3.不 剝 奪 條 件 ： 指 進(jìn) 程 已 獲 得 的 資 源 ，在 未 使 用 完 之 前 ， 不 能 被 剝 奪 ， 只能 在 使 用 完 時(shí) 由 自 己 釋 放 。 3.5.2 產(chǎn) 生 死

34、鎖 的 必 要 條 件4.環(huán) 路 等 待 條 件 ： 指 在 發(fā) 生 死 鎖 時(shí) ， 必 然存 在 一 個(gè) “ 進(jìn) 程 資 源 ” 的 環(huán) 形 鏈 ，即 進(jìn) 程 集 合 P0,P1,P2,Pn中 的 P0正 在 等 待 一 個(gè) P1占 用 的 資 源 ； P1正 在等 待 一 個(gè) P2占 用 的 資 源 ， ， Pn正在 等 待 一 個(gè) 已 被 P0占 用 的 資 源 。 3.5.3 處 理 死 鎖 的 基 本 方 法一 、 預(yù) 防 死 鎖 消 除 產(chǎn) 生 死 鎖 的 必 要 條 件二 、 避 免 死 鎖 分 配 資 源 時(shí) 防 止 進(jìn) 入 不 安 全 狀 態(tài)三 、 檢 測(cè) 死 鎖 不 預(yù) 防

35、 死 鎖 ， 出 現(xiàn) 死 鎖 就 解 除四 、 解 除 死 鎖 與 檢 測(cè) 死 鎖 配 合 使 用 思 考 題 一 臺(tái) 計(jì) 算 機(jī) 共 8臺(tái) 磁 帶 機(jī) ， 由 N個(gè) 進(jìn) 程 共享 ， 每 個(gè) 進(jìn) 程 最 多 要 3臺(tái) ， 問 N為 多 少 時(shí)不 會(huì) 有 死 鎖 ， 為 什 么 ？ 3.6 預(yù) 防 與 避 免 死 鎖 的 方 法 3.6.1 預(yù) 防 死 鎖 3.6.2 系 統(tǒng) 安 全 狀 態(tài) 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 3.6.1 預(yù) 防 死 鎖 預(yù) 防 死 鎖 的 方 法 是 使 四 個(gè) 必 要 條 件 中 的 第 2、 3、 4條件 之 一 不 能 成 立 ，

36、來 避 免 發(fā) 生 死 鎖 。 至 于 必 要 條 件 1，因 為 它 是 由 設(shè) 備 的 固 有 條 件 所 決 定 的 ， 不 僅 不 能 改變 ， 還 應(yīng) 加 以 保 證 。 下 面 分 別 對(duì) 三 種 情 況 加 以 說 明 ： 1、 摒 棄 “ 請(qǐng) 求 和 保 持 ” 條 件 不 分 配 或 者 全 部 分 配 靜 態(tài) 資 源 分 配 法 優(yōu) 點(diǎn) ： 算 法 簡 單 、 易 于 實(shí) 現(xiàn) 且 很 安 全 缺 點(diǎn) ： 資 源 浪 費(fèi) 嚴(yán) 重 ， 進(jìn) 程 延 遲 運(yùn) 行 。 2、 摒 棄 “ 不 剝 奪 ” 條 件 系 統(tǒng) 規(guī) 定 ， 進(jìn) 程 是 逐 個(gè) 地 提 出 對(duì) 資 源 的 要 求

37、的 。 當(dāng) 一 個(gè) 已 經(jīng) 保 持 了 某 些 資 源 的 進(jìn) 程 ， 提出 新 的 要 求 不 被 滿 足 時(shí) 必 須 釋 放 它 已 經(jīng) 保 持的 所 有 資 源 ， 待 以 后 需 要 時(shí) 再 重 新 申 請(qǐng) 。 從而 摒 棄 了 “ 不 剝 奪 ” 條 件 。 該 方 法 實(shí) 現(xiàn) 起 來 比 較 復(fù) 雜 且 付 出 很 大 代 價(jià) ?？?能 會(huì) 造 成 前 功 盡 棄 ， 反 復(fù) 申 請(qǐng) 和 釋 放 (抖動(dòng) )情 況 。 3、 摒 棄 “ 環(huán) 路 等 待 ” 條 件 有 序 資 源 分 配 法 ： 與 前 兩 種 策 略 比 較 ， 資 源 利 用 率 和 系 統(tǒng) 吞 吐 量 都 有較

38、 明 顯 的 改 善 。 但 也 存 在 嚴(yán) 重 問 題 ： 為 資 源 編 號(hào) 限 制 新 設(shè) 備 的 增 加 ；進(jìn) 程 使 用 設(shè) 備 順 序 與 申 請(qǐng) 順 序 相 反 ； 限 制 用 戶 編 程自 由 。 r1 r2 rk rm. .申 請(qǐng) 次 序 3.6.2 系 統(tǒng) 安 全 狀 態(tài) 在 避 免 死 鎖 的 方 法 中 把 系 統(tǒng) 的 狀 態(tài) 分 為安 全 狀 態(tài) 和 不 安 全 狀 態(tài) ， 只 要 能 使 系 統(tǒng)始 終 都 處 于 安 全 狀 態(tài) ， 便 可 避 免 發(fā) 生 死鎖 。 檢 測(cè)可 滿 足 請(qǐng) 求 分 配 不 分 配安 全不 安 全系 統(tǒng) 處 于 安 全 狀 態(tài) ： 存

39、在 安 全 進(jìn) 程 序 列 進(jìn) 程 序 列 安 全 ， p1,p2,pn可 依 次 進(jìn) 行 完 。安 全 不 安 全死 鎖1、 安 全 狀 態(tài) 2、 安 全 狀 態(tài) 之 例 假 定 系 統(tǒng) 中 有 三 個(gè) 進(jìn) 程 A、 B和 C， 共 有 12臺(tái) 磁 帶 機(jī) 。 進(jìn)程 A總 共 要 求 10臺(tái) ， B和 C分 別 要 求 4臺(tái) 和 9臺(tái) 。 假 設(shè) 在 T0時(shí) 刻 ， 進(jìn) 程 A、 B和 C已 分 別 獲 得 5臺(tái) 、 2臺(tái) 和 2臺(tái) ， 尚 有 3臺(tái) 未 分 配 ， 如 下 表 所 示 ： t0時(shí) 刻 安 全 ？ C請(qǐng) 求 1臺(tái) 磁 帶 機(jī) ， 安 全 嗎 ？進(jìn) 程 最 大 需 求 已 分

40、配 可 用A 10 5 3B 4 2C 9 2 23 3.6.3 利 用 銀 行 家 算 法 避 免 死鎖1. 銀 行 家 算 法 中 的 數(shù) 據(jù) 結(jié) 構(gòu)（ 1） 可 利 用 資 源 向 量 Available。 這 是 一 個(gè) 含 有 m個(gè) 元 素 的數(shù) 組 ， 其 中 的 每 一 個(gè) 元 素 代 表 一 類 可 利 用 的 資 源 數(shù) 目 ;（ 2） 最 大 需 求 矩 陣 Max。 這 是 一 個(gè) n*m的 矩 陣 ， 它 定 義 了 系統(tǒng) 中 n個(gè) 進(jìn) 程 中 的 每 一 個(gè) 進(jìn) 程 對(duì) m類 資 源 的 最 大 需 求 。（ 3） 分 配 矩 陣 Allocation。 這 也 是

41、一 個(gè) n*m的 矩 陣 ， 它 定 義了 系 統(tǒng) 中 每 一 類 資 源 當(dāng) 前 已 分 配 給 每 一 進(jìn) 程 的 資 源 數(shù) 。（ 4） 需 求 矩 陣 Need。 這 也 是 一 個(gè) n*m的 矩 陣 ， 用 以 表 示 每一 個(gè) 進(jìn) 程 尚 需 的 各 類 資 源 數(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

42、4 3- = 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖2. 銀 行 家 算 法 設(shè) Requesti是 進(jìn) 程 Pi的 請(qǐng) 求 向 量 ， 如 果 Requesti j=K， 表 示 進(jìn) 程 Pi需 要 K個(gè) Rj類 型 的 資 源 。當(dāng) Pi發(fā) 出 資 源 請(qǐng) 求 后 ， 系 統(tǒng) 按 下 述 步 驟 進(jìn) 行檢 查 ： Pi請(qǐng) 求 資 源RequestINeedI 請(qǐng) 求 超 量 ， 錯(cuò) 返RequestIAvailable不 滿 足 ， 等 待 Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI

43、:=NeedI-RequestI安 全確 認(rèn) ， 分 配 完成 Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等 待 FTF TT F銀行家算法 案 例 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖3. 安 全 性 算 法（ 1） 設(shè) 置 兩 個(gè) 向 量 ： 工 作 向 量 work： 表 示 系 統(tǒng) 可 提 供 給 進(jìn) 程 繼 續(xù) 運(yùn) 行 的各 類 資 源 數(shù) 目 ， 在 執(zhí) 行 安 全 算 法 開 始 時(shí) ，work:=Available; Finish:它

44、 表 示 系 統(tǒng) 是 否 有 足 夠 的 資 源 分 配 進(jìn) 程 ， 使之 運(yùn) 行 完 成 。 開 始 時(shí) 先 做 Finishi:=false;當(dāng) 有 足 夠資 源 分 配 給 進(jìn) 程 時(shí) ， 再 令 Finishi:=true。 安全性檢測(cè)算法FWork:=Available;Finish:=false; 有 滿 足 條 件 的 j:Finishj=falseNeedjWorkFinishj=true;Work:=Work+AllocationjT j ,finishj=trueT F安 全 不 安 全 4、銀行家算法之例 假 定 系 統(tǒng) 中 有 四 個(gè) 進(jìn) 程 P1,P2,P3,P4和

45、三 類 資 源A,B,C， 各 種 資 源 的 數(shù) 量 分 別 為 10、 4、 7， 在T0時(shí) 刻 的 資 源 分 配 情 況 如 下 所 示 : 資 源 情 況進(jìn) 程 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 資 源 情 況進(jìn) 程 WorkA B C AllocationA B C Allocation+Work Finish(1)T0時(shí) 刻 的 安 全 性 ： 4、銀行家算法

46、之例 資 源 情 況進(jìn) 程 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時(shí) 刻 系 統(tǒng) 是 安 全 的 ， 存 在 安 全 序 列P1,P3,P4,P2 Reques

47、t1(1,0,2)=Need1(1,2,3)； Request1(1,0,2)=Available(3,3,2)； 試 探 性 把 資 源 分 配 給 P1,并 修 改 相 應(yīng) 的 數(shù) 據(jù) ,形 成 的資 源 變 化 情 況 上 表 所 示 ； 由 所 執(zhí) 行 安 全 性 檢 查 得 知 :可 以 找 到 一 個(gè) 安 全 序 列P1,P3,P4,P2,即 此 時(shí) 系 統(tǒng) 是 安 全 的 ,可 以 滿 足 請(qǐng) 求 。 資 源 情 況進(jìn) 程 WorkA B C AllocationA B C Allocation+Work Finish(2)P1請(qǐng) 求 資 源 ， 發(fā) 出 請(qǐng) 求 向 量 Requ

48、est1(1,0,2)； 4、銀行家算法之例 資 源 情 況進(jìn) 程 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 Re

49、quest4(3,3,0)Need4(4,3,1)； Request4(3,3,0)Available(2,3,0)；(3)P4請(qǐng) 求 資 源 ， 發(fā) 出 請(qǐng) 求 向 量 Request4(3,3,0)； 4、銀行家算法之例 資 源 情 況進(jìn) 程 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) 當(dāng) 前 系 統(tǒng) 資 源 不 能 滿 足 P4的 請(qǐng) 求 ， 不

50、予 分 配 ； Request4(0,2,0)Need4(4,3,1)； Request4(0,2,0)Available(2,3,0)；(4)P4請(qǐng) 求 資 源 ， 發(fā) 出 請(qǐng) 求 向 量 Request4(0,2,0)； 4、銀行家算法之例 資 源 情 況進(jìn) 程 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分 配 資 源

51、， 并 修 改 相 應(yīng) 的 數(shù) 據(jù) ， 開 成 的 資 源分 配 情 況 如 上 所 示 ； 1 2 4 1 Work 進(jìn) 行 安 全 性 檢 查 ： 可 用 資 源 Available(2,1,0)已 不 能 滿 足 任 何進(jìn) 程 的 需 要 ， 系 統(tǒng) 進(jìn) 入 不 安 全 狀 態(tài) ， 故 系 統(tǒng) 不 能 滿 足 P4的 請(qǐng) 求 3.7 死 鎖 的 檢 測(cè) 與 解 除 3.7.1 死 鎖 的 檢 測(cè) 3.7.2 死 鎖 的 解 除 3.7.1 死 鎖 的 檢 測(cè) 當(dāng) 系 統(tǒng) 為 進(jìn) 程 分 配 資 源 時(shí) ， 若 未 采 取 任何 限 制 性 措 施 ， 則 系 統(tǒng) 必 須 提 供 檢 測(cè)

52、和解 除 死 鎖 的 手 段 ， 為 此 系 統(tǒng) 必 須 ：1. 保 存 有 關(guān) 資 源 的 請(qǐng) 求 和 分 配 信 息 ；2. 提 供 一 種 算 法 ， 以 利 用 這 些 信 息 來 檢 測(cè)系 統(tǒng) 是 否 已 進(jìn) 入 死 鎖 狀 態(tài) 。 1 資 源 分 配 圖定 義 : G=(V,E), V=PR, P=p1,p2,pn, R=r1,r2,rm, E=(pi,rj)(rj,pi), piP, rjR. 申 請(qǐng) 邊 (pi,rj): pi申 請(qǐng) rj； 分 配 邊 (rj,pi): rj分 配 pi;圖 示 ： 進(jìn) 程 ： 資 源 ： 申 請(qǐng) 邊 ： 由 進(jìn) 程 到 資 源 類 ； 分 配

53、 邊 ： 由 資 源 實(shí) 例 到 進(jìn) 程 。 r2 P2P1r1 1 資 源 分 配 圖申 請(qǐng) ： pi申 請(qǐng) rj中 的 一 個(gè) 資 源 實(shí) 例 ， 由 pi向 rj畫 一 申請(qǐng) 邊 ， 如 可 滿 足 ， 改 為 分 配 邊 。釋 放 ： 去 掉 分 配 邊 。 例 子 （ 無 環(huán) 路 ， 無 死 鎖 ）p1 p2 p3r1 r3r2 r4 例 子 （ 有 環(huán) 路 ， 有 死 鎖 ）p1 p2 p3r1 r3r2 r4 例 子 （ 有 環(huán) 路 ， 無 死 鎖 ）p1 p2p3p4r1 r2 2、 資 源 分 配 圖 的 簡 化 簡 化 方 法 如 下 ：1.在 資 源 分 配 圖 中 找

54、出 一 個(gè) 既 不 阻 塞 又 非 獨(dú) 立 的進(jìn) 程 結(jié) 點(diǎn) Pi， 在 順 利 的 情 況 下 運(yùn) 行 完 畢 ， 釋 放 其占 有 的 全 部 資 源 。2.由 于 釋 放 了 資 源 ， 這 樣 能 使 其 它 被 阻 塞 的 進(jìn) 程獲 得 資 源 繼 續(xù) 運(yùn) 行 。3.在 經(jīng) 過 一 系 列 簡 化 后 若 能 消 去 圖 中 的 所 有 的 邊 ，使 所 有 進(jìn) 程 結(jié) 點(diǎn) 都 孤 立 ， 則 稱 該 圖 是 可 完 全 簡 化的 ， 反 之 是 不 可 完 全 簡 化 的 。 3、 死 鎖 定 理 可 以 證 明 ： S狀 態(tài) 為 死 鎖 狀 態(tài) 的 充 分 條件 是 當(dāng) 且 僅

55、當(dāng) S狀 態(tài) 的 資 源 分 配 圖 是 不可 完 全 簡 化 的 。 例 ： 根 據(jù) 死 鎖 定 理 判 斷 如 下 所 示 的 資 源 分配 圖 是 否 存 在 死 鎖 。 P1 P2 P3R1 R2 R3 P1 P3 P2 R1 R2圖 1 圖 2 3.7.2 死 鎖 的 解 除 當(dāng) 發(fā) 現(xiàn) 進(jìn) 程 死 鎖 時(shí) ， 便 應(yīng) 立 即 把 它 們 從死 鎖 狀 態(tài) 中 解 脫 出 來 。 常 采 用 的 方 法 是 ：1. 剝 奪 資 源 。 從 其 他 進(jìn) 程 剝 奪 足 夠 數(shù) 量 的資 源 給 死 鎖 進(jìn) 程 以 解 除 死 鎖 狀 態(tài) 。2. 撤 銷 進(jìn) 程 。 最 簡 單 的 是

56、讓 全 部 進(jìn) 程 都 死掉 ； 溫 和 一 點(diǎn) 的 是 按 照 某 種 順 序 逐 個(gè) 撤銷 進(jìn) 程 ， 直 至 有 足 夠 的 資 源 可 用 ， 使 死鎖 狀 態(tài) 消 除 為 止 。 本 章 基 礎(chǔ) 要 點(diǎn)1. 要 使 當(dāng) 前 運(yùn) 行 進(jìn) 程 總 是 優(yōu) 先 級(jí) 最 高 的 進(jìn) 程 ，則 應(yīng) 選 擇 ：搶 占 優(yōu) 先 級(jí) 調(diào) 度 算 法 。2. 在 分 時(shí) 系 統(tǒng) 中 ， 進(jìn) 程 調(diào) 度 經(jīng) 常 采 用 ：時(shí) 間 片 輪 轉(zhuǎn) 調(diào) 度 算 法 。3. 進(jìn) 程 運(yùn) 行 結(jié) 束 、 進(jìn) 入 阻 塞 狀 態(tài) 、 時(shí) 間 片 用完 、 有 更 高 優(yōu) 先 級(jí) 的 進(jìn) 程 進(jìn) 入 就 緒 隊(duì) 列 等

57、原 因 均 可 引 起 ：進(jìn) 程 調(diào) 度 。 本 章 基 礎(chǔ) 要 點(diǎn)4. 進(jìn) 程 調(diào) 度 采 用 時(shí) 間 片 輪 轉(zhuǎn) 法 時(shí) ， 時(shí) 間 片 過大 ， 就 會(huì) 使 輪 轉(zhuǎn) 法 轉(zhuǎn) 化 為 ：先 來 先 服 務(wù) 調(diào) 度 算 法 。5. 進(jìn) 程 的 調(diào) 度 方 式 有 兩 種 ：搶 占 式 調(diào) 度 和 非 搶 占 式 調(diào) 度 。6. 死 鎖 產(chǎn) 生 的 四 個(gè) 必 要 條 件 是 ：互 斥 、 請(qǐng) 求 和 保 持 、 不 剝 奪 和 環(huán) 路 等 待 。7. 在 有 m個(gè) 進(jìn) 程 的 系 統(tǒng) 中 出 現(xiàn) 死 鎖 時(shí) ， 死 鎖 進(jìn)程 的 個(gè) 數(shù) k應(yīng) 滿 足 的 條 件 是 ： 2 k m。 本 章

58、 基 礎(chǔ) 要 點(diǎn)8. 不 讓 死 鎖 發(fā) 生 的 策 略 可 分 為 靜 態(tài) 和 動(dòng) 態(tài) 兩種 ， 死 鎖 避 免 屬 于 ： 動(dòng) 態(tài) 策 略 。9. 某 系 統(tǒng) 中 有 3個(gè) 并 發(fā) 進(jìn) 程 ， 都 需 要 同 類 資 源 4個(gè) ， 該 系 統(tǒng) 絕 對(duì) 不 會(huì) 發(fā) 生 死 鎖 的 最 少 資 源 個(gè)數(shù) 是 ： 10。10. 資 源 的 按 序 分 配 策 略 可 以 破 壞 ： 環(huán) 路 等 待 條 件 。11. 預(yù) 先 靜 態(tài) 分 配 法 可 以 破 壞 ： 請(qǐng) 求 和 保 持 條 件 。 課 堂 練 習(xí)一 個(gè) 系 統(tǒng) 具 有 150個(gè) 存 儲(chǔ) 單 元 ， 在 T0時(shí) 刻 按 下 表 所 示分 配 給 3個(gè) 進(jìn) 程 。 資 源進(jìn) 程 Max allocationp1 70 25P2 60 40P3 60 45對(duì) 下 列 請(qǐng) 求 應(yīng) 用 銀 行 家 算 法 分 別 分 析 判 斷 是 否 安 全 ？1) 第 4個(gè) 進(jìn) 程 P4到 達(dá) ， 最 大 需 求 60個(gè) 存 儲(chǔ) 單 元 ， 當(dāng) 前 分 配 25個(gè) 單 元 。 2) 第 4個(gè) 進(jìn) 程 P4到 達(dá) ， 最 大 需 求 50個(gè) 存 儲(chǔ) 單 元 ， 當(dāng) 前 分 配 35個(gè) 單 元 。如 果 是 安 全 的 ， 請(qǐng) 給 出 一 個(gè) 可 能 的 安 全 序 列 ； 如 果 不 是 安 全 的 ， 請(qǐng) 說 明 原 因 。