處理機調度與死鎖

《處理機調度與死鎖》由會員分享，可在線閱讀，更多相關《處理機調度與死鎖（137頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、計 算 機 操 作 系 統(tǒng)東 華 大 學 計 算 機 科 學 與 技 術 學 院主 講 ： 李 繼 云 2 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理 機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 l 3.1.1 高 級 、 中 級 和 低 級 調 度 l 3.1.2 調 度 隊 列 模 型 l 3.1.3 選 擇 調 度 方 式 和 調 度 算 法

2、的 若 干 準 則 3.1 處 理 機 調 度 的 基 本 概 念 4 3.1.1 高 級 、 中 級 和 低 級 調 度 5 1. 高 級 調 度 (High Scheduling) 6 1. 高 級 調 度 (High Scheduling) 7 2. 低 級 調 度 (Low Level Scheduling) 8 2. 低 級 調 度 (Low Level Scheduling) 9 進 程 調 度 方 式 10 3. 中 級 調 度 (Intermediate-Level Scheduling) l 3.1.1 高 級 、 中 級 和 低 級 調 度 l 3.1.2 調 度 隊 列

3、模 型 l 3.1.3 選 擇 調 度 方 式 和 調 度 算 法 的 若 干 準 則 3.1 處 理 機 調 度 的 基 本 概 念 13就 緒 隊 列阻 塞 隊 列 進 程 調 度 CPU 進 程 完 成等 待 事 件交 互 用 戶事件出現(xiàn) 時 間 片 完 3.1.2 調 度 隊 列 模 型 14 就 緒 隊 列 進 程 調 度 CPU 進 程 完 成 等 待 事 件 1 作 業(yè) 調 度 事 件 1出 現(xiàn) 時 間 片 完 等 待 事 件 2 事 件 2出 現(xiàn) 等 待 事 件 n 事 件 n出 現(xiàn) 后 備 隊 列 15 16 就 緒 隊 列 進 程 調 度 CPU 就 緒 ， 掛 起 隊 列

4、中 級 調 度 阻 塞 ， 掛 起 隊 列 阻 塞 隊 列 等 待 事 件 進 程 完 成 時 間 片 完作 業(yè) 調 度 交 互 型 作 業(yè) 后 備 隊 列 批 量 作 業(yè) 掛 起 事 件 出 現(xiàn) 事 件 出 現(xiàn) l 3.1.1 高 級 、 中 級 和 低 級 調 度 l 3.1.2 調 度 隊 列 模 型 l 3.1.3 選 擇 調 度 方 式 和 調 度 算 法 的 若 干 準 則 3.1 處 理 機 調 度 的 基 本 概 念 3.1.3 選 擇 調 度 方 式 和 調 度 算 法 的 若 干 準 則 19 20 ii iTnT 11 ni SiiTTnW 11 21 22 23 24

5、25 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理 機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 26 3.2 調 度 算 法 l 3.2.1 先 來 先 服 務 和 短 作 業(yè) (進 程 )優(yōu) 先 調 度 算 法 l 3.2.2 高 優(yōu) 先 權 優(yōu) 先 調 度 算 法 l 3.2.3 基 于 時 間 片 的 輪 轉 調 度 算 法 3.2 調 度 算

6、法 28 3.2.1先 來 先 服 務 和 短 作 業(yè) (進 程 )優(yōu) 先 調 度 算 法 1001991001001411 1 ii iTnT 30 ii iTnT 11 ni SiiTTnW 11 32 l 3.2.1 先 來 先 服 務 和 短 作 業(yè) (進 程 )優(yōu) 先 調 度 算 法 l 3.2.2 高 優(yōu) 先 權 優(yōu) 先 調 度 算 法 l 3.2.3 基 于 時 間 片 的 輪 轉 調 度 算 法 3.2 調 度 算 法 34 3.2.2 高 優(yōu) 先 權 優(yōu) 先 調 度 算 法 35 36 37 38 39要 求 服 務 時 間 要 求 服 務 時 間等 待 時 間優(yōu) 先 權 要

7、 求 服 務 時 間響 應 時 間要 求 服 務 時 間要 求 服 務 時 間等 待 時 間優(yōu) 先 權 40 l 3.2.1 先 來 先 服 務 和 短 作 業(yè) (進 程 )優(yōu) 先 調 度 算 法 l 3.2.2 高 優(yōu) 先 權 優(yōu) 先 調 度 算 法 l 3.2.3 基 于 時 間 片 的 輪 轉 調 度 算 法 3.2 調 度 算 法 43 3.2.3 基 于 時 間 片 的 輪 轉 調 度 算 法1. 時 間 片 輪 轉 法 44 2. 多 級 反 饋 隊 列 調 度 算 法 45 46 47 48 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理 機 調 度 的 基 本 概

8、念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 49 3.3 實 時 調 度 l 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 l 3.3.2 實 時 調 度 算 法 的 分 類 l 3.3.3 常 用 的 幾 種 實 時 調 度 算 法 3.3 實 時 調 度 51 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 52 mi iiPC1 1 3.3.1 實 現(xiàn) 實 時 調 度

9、的 基 本 條 件 53 mi ii NPC1 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 54 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 55 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 l 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 l 3.3.2 實 時 調 度 算 法 的 分 類 l 3.3.3 常 用 的 幾 種 實 時 調 度 算 法 3.3 實 時 調 度 57 3.3.2 實 時 調 度 算 法 的 分 類 58 3.3.2 實 時 調 度 算 法 的 分 類 59 3.3.2 實 時 調 度 算 法 的 分 類 60 3.3.

10、2 實 時 調 度 算 法 的 分 類 l 3.3.1 實 現(xiàn) 實 時 調 度 的 基 本 條 件 l 3.3.2 實 時 調 度 算 法 的 分 類 l 3.3.3 常 用 的 幾 種 實 時 調 度 算 法 3.3 實 時 調 度 62 3.3.3 常 用 的 幾 種 實 時 調 度 算 法 631 3 4 2 開 始 截 止 時 間 任 務 執(zhí) 行 任 務 到 達 1 2 3 4 1 3 4 2 t 64 65 A1 A2 A3 A4 A5 A6 A7 A8 20 40 60 80 100 120 140 160 B1 B2 B3 t 0 67 第 3章 處 理 機 調 度 與 死 鎖l

11、 3.1 處 理 機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 l 3.4.1 多 處 理 器 系 統(tǒng) 的 類 型 l 3.4.2 進 程 分 配 方 式 l 3.4.3 進 程 (線 程 )調 度 方 式 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度 69 3.4.1 多 處 理 器 系 統(tǒng) 的 類 型 70 3.4.1 多 處 理 器 系 統(tǒng) 的 類 型 l 3

12、.4.1 多 處 理 器 系 統(tǒng) 的 類 型 l 3.4.2 進 程 分 配 方 式 l 3.4.3 進 程 (線 程 )調 度 方 式 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度 72 3.4.2 進 程 分 配 方 式 73 3.4.2 進 程 分 配 方 式 l 3.4.1 多 處 理 器 系 統(tǒng) 的 類 型 l 3.4.2 進 程 分 配 方 式 l 3.4.3 進 程 (線 程 )調 度 方 式 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度 75 3.4.3 進 程 (線 程 )調 度 方 式 76 1. 自 調 度 (Self-Scheduling)方 式 77 1. 自 調

13、 度 (Self-Scheduling)方 式 78 79 80 81 82 小 結 分 級 調 度 調 度 算 法 實 時 調 度 多 處 理 機 調 度 83 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理 機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.5.1 產(chǎn) 生 死 鎖 的 原 因

14、l 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 l 3.5.3 處 理 死 鎖 的 基 本 方 法3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 3.5.1 產(chǎn) 生 死 鎖 的 原 因 R1 R2 P1 P 2 S 2 P1 S3 P3 S1 P2 l 3.5.1 產(chǎn) 生 死 鎖 的 原 因 l 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 l 3.5.3 處 理 死 鎖 的 基 本 方 法3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 3.5.2 產(chǎn) 生 死 鎖 的 必 要 條 件 l 3.5.1 產(chǎn) 生 死 鎖 的 原 因 l 3.5.2 產(chǎn) 生 死 鎖 的 必 要

15、條 件 l 3.5.3 處 理 死 鎖 的 基 本 方 法3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 3.5.3 處 理 死 鎖 的 基 本 方 法 95 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理 機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 l 3.6.1 預 防 死 鎖 l 3.6.2 死 鎖 避 免 l 3.6.3 利 用 銀 行

16、家 算 法 避 免 死 鎖 3.6 預 防 死 鎖 的 方 法 3.6.1 預 防 死 鎖 3.6.1 預 防 死 鎖 3.6.1 預 防 死 鎖 l 3.6.1 預 防 死 鎖 l 3.6.2 死 鎖 避 免 l 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 3.6 預 防 死 鎖 的 方 法 3.6.2 死 鎖 避 免 進 程 最 大 需 求 已 分 配 可 用 P1P2P3 1049 522 3 l 3.6.1 預 防 死 鎖 l 3.6.2 死 鎖 避 免 l 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 3.6 預 防 死 鎖 的 方 法 主 要 思 想 ： 銀

17、行 家 算 法 是 從 當 前 的 狀 態(tài) S出 發(fā) ， 逐 個 檢 查 各 申 請 者中 誰 獲 得 資 源 能 完 成 其 工 作 ， 然 后 假 定 其 完 成 工 作 且 歸 還 全部 資 源 ， 再 進 一 步 檢 查 誰 又 獲 得 資 源 能 完 成 其 工 作 。 若所 有 申 請 者 均 能 完 成 工 作 ， 則 系 統(tǒng) 狀 態(tài) 是 安 全 的 。3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 1. 銀 行 家 算 法 中 的 數(shù) 據(jù) 結 構 3.6.3 利 用 銀 行 家 算 法 避 免 死 鎖 119 第 3章 處 理 機 調 度 與 死 鎖l 3.1 處 理

18、機 調 度 的 基 本 概 念l 3.2 調 度 算 法l 3.3 實 時 調 度l 3.4 多 處 理 機 系 統(tǒng) 中 的 調 度l 3.5 產(chǎn) 生 死 鎖 的 原 因 和 必 要 條 件 l 3.6 預 防 死 鎖 的 方 法 l 3.7 死 鎖 的 檢 測 與 解 除 l 3.7.1 死 鎖 的 檢 測 l 3.7.2 死 鎖 的 解 除 3.7 死 鎖 的 檢 測 與 解 除 3.7.1 死 鎖 的 檢 測 P1 P2 r1 r2 現(xiàn) 假 定 有 3類 資 源 R1， R2， R3， 其 中 R1和 R3都 只 有 1個資 源 ， R2有 2個 資 源 。 有 3個 進 程 P1， P

19、2， P3， 每 個 進 程 占用 資 源 和 等 待 資 源 的 情 況 如 下 表 所 示 。例 如 果 P3進 程 再 提 出 申 請 一 個 R2資 源 則 存 在 兩 條 環(huán) 路 ：P1 R1 P2 R3 P3 R2 PlP2 R3 P3 R2 P2死 鎖 產(chǎn) 生 下 圖 所 示 的 例 子 中 存 在 一 個 環(huán) 路 ， 但 不 形 成 死 鎖 P1R1P3R2P1 （ 1） 如 果 資 源 分 配 圖 中 無 環(huán) 路 ， 則 系 統(tǒng) 中 沒 有 死 鎖 發(fā)生 。 （ 2） 如 果 資 源 分 配 圖 中 有 環(huán) 路 ， 且 環(huán) 中 每 個 進 程 處 于 永久 等 待 ， 則 死

20、 鎖 形 成 ， 環(huán) 路 中 的 進 程 就 處 于 死 鎖 狀 態(tài) 。 （ 3） 如 果 資 源 分 配 圖 中 有 環(huán) 路 ， 但 涉 及 到 的 資 源 類 中 有多 個 資 源 ， 則 環(huán) 路 的 存 在 未 必 就 有 死 鎖 形 成 。從 上 面 的 討 論 中 可 以 得 到 如 下 結 論 ： （ 1） 在 資 源 分 配 圖 中 ， 找 出 一 個 既 不 阻 塞 又 非 獨 立 的 進程 結 點 pi。 在 順 利 情 況 下 ， pi可 獲 得 所 需 資 源 而 繼 續(xù) 執(zhí)行 ， 直 至 運 行 完 畢 ， 再 釋 放 其 所 占 有 的 全 部 資 源 。 這 相當

21、于 消 去 pi所 有 的 請 求 邊 和 分 配 邊 ， 使 之 成 為 孤 立 的 結點 l 3.7.1 死 鎖 的 檢 測 l 3.7.2 死 鎖 的 解 除 3.7 死 鎖 的 檢 測 與 解 除 3.7.2 死 鎖 的 解 除 1. 假 定 系 統(tǒng) 中 有 五 個 進 程 P0、 P1、 P2、 P3、 P4和 三 種 類 型 的 資 源A， B， C， 每 一 種 資 源 的 數(shù) 量 ， 分 別 為 10、 5、 7， 在 T0時 刻 的 資 源分 配 情 況 如 下 表 。 請 找 出 該 表 中 T0時 刻 以 后 存 在 的 安 全 序 列 （ 至 少 2種 ） 思 考 和

22、練 習資 源 情 況進 程 AllocationA B CMaxA B C NeedA B C AvailableA B CP0P1P2P3 P4 0 1 03 2 29 0 22 2 24 3 3 2 0 03 0 22 1 10 0 2 7 4 31 2 26 0 00 1 14 3 1 3 3 27 5 3 2 一 個 OS有 20個 進 程 ， 競 爭 使 用 65個 同 類 資 源 ，申 請 方 式 是 逐 個 進 行 的 ， 一 旦 某 個 進 程 獲 得 它所 需 要 的 全 部 資 源 ， 則 立 即 歸 還 所 有 資 源 。 每個 進 程 最 多 使 用 三 個 資 源 。

23、 若 僅 考 慮 這 類 資 源 ，該 系 統(tǒng) 有 無 可 能 產(chǎn) 生 死 鎖 ， 為 什 么 ？3 死 鎖 和 饑 餓 的 主 要 差 別 是 什 么 ？思 考 和 練 習 2 答 ： 不 可 能 。 因 為 死 鎖 產(chǎn) 生 的 原 因 有 兩 點 ： 系 統(tǒng) 資 源不 足 或 推 進 順 序 不 當 ， 在 本 題 中 ， 進 程 所 需 的 最 大 資源 數(shù) 為 60， 而 系 統(tǒng) 共 有 該 類 資 源 65個 ， 其 資 源 數(shù) 已 足夠 系 統(tǒng) 內 各 進 程 使 用 。3 答 ： 簡 言 之 ， 死 鎖 是 某 進 程 等 待 一 個 不 會 發(fā) 生 的 事 件的 一 種 現(xiàn) 象

24、 ； 而 饑 餓 現(xiàn) 象 是 某 進 程 正 等 待 這 樣 一 個 事件 ， 它 發(fā) 生 了 但 總 是 受 到 其 它 進 程 的 影 響 ， 以 至 輪 不到 （ 或 很 難 輪 到 ） 該 進 程 。 解 答 判 斷（ 1） 參 與 死 鎖 的 所 有 進 程 都 占 有 資 源（ 2） 參 與 死 鎖 的 所 有 進 程 均 正 在 等 待 資 源（ 3） 參 與 死 鎖 的 所 有 進 程 中 至 少 有 兩 個 進 程 占 有 資 源（ 4） 參 與 死 鎖 的 進 程 至 少 有 兩 個 參 與 死 鎖 的 進 程 最 少 是 兩 個 （ 兩 個 以 上 進 程 才 會 出 現(xiàn) 死 鎖 ） 參 與 死 鎖 的 進 程 至 少 有 兩 個 已 經(jīng) 占 有 資 源 參 與 死 鎖 的 所 有 進 程 都 在 等 待 資 源 參 與 死 鎖 的 進 程 是 當 前 系 統(tǒng) 中 所 有 進 程 的 子 集關 于 死 鎖 的 一 些 結 論 練 習 某 系 統(tǒng) 有 同 類 資 源 m個 供 n個 進 程 共 享 ， 如果 每 個 進 程 最 多 申 請 x個 資 源 （ 1=x=m） 且各 進 程 的 最 大 需 求 量 之 和 小 于 （ m+n） ， 試 證明 該 系 統(tǒng) 不 會 發(fā) 生 死 鎖 。 提 示 ： 考 慮 極 端 情 況