《《處理器管理》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《處理器管理》PPT課件（92頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第 2章 處 理 器 管 理 主 講 ： 周 文 強(qiáng) 課 程 ： 操 作 系 統(tǒng) 本 章 內(nèi) 容 ：2.4 進(jìn) 程 同 步 機(jī) 制2.5 進(jìn) 程 通 信2.6 處 理 機(jī) 調(diào) 度 2.4 進(jìn) 程 同 步 機(jī) 制 操 作 系 統(tǒng) 中 引 入 進(jìn) 程 后 ， 雖 然 改 善 了 資 源的 利 用 率 ， 提 高 了 系 統(tǒng) 的 吞 吐 量 。 但 是 ， 由 于 進(jìn) 程 的 異 步 性 ， 也 會 給 系 統(tǒng) 造成 混 亂 。 因 此 ， 必 須 有 效 地 協(xié) 調(diào) 各 個 并 發(fā)進(jìn) 程 間 的 關(guān) 系 ， 從 而 使 它 們 能 正 確 的 執(zhí) 行 。 本 節(jié) 主 要 介 紹 進(jìn) 程 的 同 步

2、 與 互 斥 的 實 現(xiàn) 機(jī)制 。 2.4.1 進(jìn) 程 的 并 發(fā) 性 在 并 發(fā) 運 行 的 系 統(tǒng) 中 ， 若 干 個 作 業(yè) 可 以 同時 運 行 ， 而 每 個 作 業(yè) 又 需 要 有 多 個 進(jìn) 程 協(xié)作 完 成 。 在 這 些 同 時 存 在 的 進(jìn) 程 間 具 有 并發(fā) 性 ， 稱 之 為 “ 并 發(fā) 進(jìn) 程 ”。 進(jìn) 程 間 的 關(guān) 系 可 以 分 為 ：1、 資 源 共 享 關(guān) 系2、 相 互 合 作 關(guān) 系 1、 資 源 共 享 關(guān) 系 系 統(tǒng) 中 的 某 些 進(jìn) 程 需 要 訪 問 共 同 的 資 源 ，即 當(dāng) 一 個 進(jìn) 程 訪 問 共 享 資 源 時 ， 訪 問 該

3、共享 資 源 的 其 他 進(jìn) 程 必 須 等 待 ， 當(dāng) 這 個 進(jìn) 程使 用 完 后 ， 其 他 進(jìn) 程 才 能 使 用 。 這 時 要 求進(jìn) 程 應(yīng) 互 斥 地 訪 問 共 享 資 源 。 2、 相 互 合 作 關(guān) 系 系 統(tǒng) 中 的 某 些 進(jìn) 程 之 間 存 在 相 互 合 作 的 關(guān)系 ， 即 一 個 進(jìn) 程 執(zhí) 行 完 后 ， 另 一 個 進(jìn) 程 才能 開 始 。 否 則 ， 另 一 個 進(jìn) 程 不 能 開 始 ， 這時 就 要 保 證 相 互 合 作 的 進(jìn) 程 在 執(zhí) 行 次 序 上要 同 步 。 1、 臨 界 資 源 通 常 一 次 僅 允 許 一 個 進(jìn) 程 使 用 的 資

4、 源稱 為 臨 界 資 源 ， 同 時 ， 也 將 一 個 進(jìn) 程訪 問 的 這 種 臨 界 資 源 的 那 段 程 序 代 碼稱 為 臨 界 區(qū) 。 操 作 系 統(tǒng) 中 的 進(jìn) 程 就 緒 隊 列 就 是 一 種在 一 個 時 刻 只 能 允 許 一 個 進(jìn) 程 訪 問 的臨 界 資 源 。 所 以 ， 進(jìn) 程 的 互 斥 就 是 兩個 進(jìn) 程 不 能 同 時 進(jìn) 入 訪 問 同 一 臨 界 資源 的 臨 界 區(qū) 。 2、 臨 界 區(qū) (critical section) 臨 界 區(qū) 是 進(jìn) 程 執(zhí) 行 程 序 中 的 對 臨 界 資 源 訪問 的 那 一 段 程 序 ， 這 段 程 序 的

5、 進(jìn) 入 執(zhí) 行 ，需 要 有 一 定 的 原 則 來 協(xié) 調(diào) 。 例 如 ： 1、 有 若 干 進(jìn) 程 都 欲 進(jìn) 入 臨 界 區(qū) ， 它 們 不 能互 相 阻 塞 ， 使 得 誰 也 進(jìn) 不 了 臨 界 區(qū) ， 應(yīng) 當(dāng)在 有 限 時 間 內(nèi) 讓 一 個 進(jìn) 程 進(jìn) 入 臨 界 區(qū) 。 2、 每 次 至 多 有 一 個 進(jìn) 程 進(jìn) 入 臨 界 區(qū) ， 并 且在 臨 界 區(qū) 中 只 能 停 留 有 限 的 時 間 。 3、 進(jìn) 程 同 步 多 個 相 關(guān) 進(jìn) 程 在 執(zhí) 行 次 序 上 的 協(xié) 調(diào) ， 這 些 進(jìn)程 相 互 合 作 ， 在 一 些 關(guān) 鍵 點 上 需 要 相 互 等 待或 相

6、互 通 信 。 通 過 臨 界 區(qū) 可 以 協(xié) 調(diào) 進(jìn) 程 間 相 互 合 作 的 關(guān) 系 ，這 就 是 進(jìn) 程 同 步 4、 進(jìn) 程 互 斥 當(dāng) 一 個 進(jìn) 程 進(jìn) 入 臨 界 區(qū) 使 用 臨 界 資 源 時 ，另 一 個 進(jìn) 程 必 須 等 待 。 當(dāng) 占 用 臨 界 資 源 的進(jìn) 程 退 出 臨 界 區(qū) 后 ， 另 一 個 進(jìn) 程 才 被 允 許使 用 臨 界 資 源 。 通 過 臨 界 區(qū) 協(xié) 調(diào) 進(jìn) 程 間 資 源 共 享 的 關(guān) 系 ，就 是 進(jìn) 程 互 斥 。 2.4.3 進(jìn) 程 同 步 機(jī) 制 應(yīng) 遵 循 的 原 則 (1)空 閑 讓 進(jìn) 。 當(dāng) 無 進(jìn) 程 處 于 臨 界 區(qū)

7、 時 ，允 許 一 個 進(jìn) 程 進(jìn) 入 。 (2)忙 則 等 待 。 當(dāng) 有 進(jìn) 程 在 臨 界 區(qū) 中 ，其 他 欲 進(jìn) 入 臨 界 區(qū) 的 進(jìn) 程 必 須 等 待 。 (3)有 限 等 待 。 對 要 求 進(jìn) 入 臨 界 區(qū) 的 進(jìn)程 ， 應(yīng) 在 有 限 時 間 內(nèi) 讓 其 進(jìn) 入 ， 避 免“ 死 等 ” 。 (4)讓 權(quán) 等 待 。 臨 界 區(qū) 讓 出 ， 必 須 立 即釋 放 處 理 器 ， 讓 等 待 進(jìn) 程 進(jìn) 入 ， 避 免“ 忙 等 ” 。 12 n鎖 操 作 ：1.測 試 鎖 位 的 值 ； lock/unlock2.若 原 來 的 值 是 為 “ 0”， 將 鎖 位 置

8、為 “ 1”（ 占 用 該資 源 ） ；3.若 原 來 值 是 為 “ 1”， （ 該 資 源 已 被 別 人 占 用 ） ，則 轉(zhuǎn) 到 1。n開 鎖 操 作 ：進(jìn) 程 使 用 完 資 源 后 ， 將 鎖 位 置 為 “ 0”， 稱 為 開 鎖 操作 。 2.4.4 進(jìn) 程 同 步 機(jī) 制 鎖 13 鎖 操 作 的 缺 點 14 18 20 放 水 果 問 題有 一 個 水 果 盤 ， 只 能 放 入 1個 水 果 。 父 親 每 次 放1個 蘋 果 供 兒 子 吃 ， 或 者 放 1個 橘 子 供 女 兒 吃 。 給出 父 親 、 兒 子 、 女 兒 的 算 法 描 述 。 放 水 果 問

9、題需 要 三 個 信 號 量 s1,s2,s3分 別 代 表 需 要 盤子 是 否 為 空 ， 是 否 可 以 有 蘋 果 ， 是 否 橘 子 。父 親 進(jìn) 程 ：A:P（ s1 ）if 放 蘋 果 then V(s2)else V(s3) goto As1 = 1， s2 = 0， s2 = 0 放 水 果 問 題兒 子 進(jìn) 程 ：B:P(s2) 取 走 蘋 果V（ s1）goto B 女 兒 進(jìn) 程C:P(s3) 取 走 蘋 果V（ s1）goto C PA Ppbufferdeposit(data) remove(data)例 進(jìn) 程 PA和 PB共 享 緩 沖 隊 列 發(fā) 送 和 接

10、收數(shù) 據(jù) 。 26 在 PA至 少 送 一 塊 數(shù) 據(jù) 入 一 個 緩 沖 區(qū) 之 前 ，PB不 可 能 從 緩 沖 區(qū) 中 取 出 數(shù) 據(jù) (假 定 數(shù) 據(jù) 塊長 等 于 緩 沖 區(qū) 長 度 )； PA往 緩 沖 隊 列 發(fā) 送 數(shù) 據(jù) 時 ， 至 少 有 一 個 緩沖 區(qū) 是 空 的 ； 由 PA發(fā) 送 的 數(shù) 據(jù) 塊 在 緩 沖 隊 列 中 按 先 進(jìn) 先出 方 式 排 列 。 2.4.8 利 用 信 號 量 實 現(xiàn) 進(jìn) 程 同 步 與 互 斥 每 個 進(jìn) 程 中 各 個 P操 作 的 次 序 是 重 要 的 ： 先 檢 查 資 源 數(shù) 目 ， 再檢 查 是 否 互 斥 否 則 可 能

11、死 鎖 ！ Consumer：Producer：P(avail);P(mutex); one unit-buf;V(mutex);V(full); P(full);P(mutex); /進(jìn) 入 區(qū) one unit-buf;V(mutex);V(avail); /退 出 區(qū)分 析 ： 當(dāng) full=0, mutex = 1時 ， 執(zhí) 行 順 序 ： / C阻 塞 ， 等 待 Producer 發(fā) 出 的 full信 號 / P 阻 塞 ， 等 待 Consumer發(fā) 出 的 avail信 號 2.4.9 利 用 信 號 量 實 現(xiàn) 進(jìn) 程 同 步 的 方 法1、 使 用 PV操 作 的 規(guī) 則

12、（ 1） 分 清 哪 些 是 互 斥 問 題 ， 哪 些 是 同 步 問 題（ 2） 對 于 互 斥 問 題 要 設(shè) 置 互 斥 信 號 量 ， 不 管 有 互斥 關(guān) 系 的 進(jìn) 程 有 幾 個 或 幾 類 ， 互 斥 信 號 量 的 個 數(shù)只 與 臨 界 資 源 的 種 類 有 關(guān)（ 3） 對 于 同 步 問 題 要 設(shè) 置 同 步 信 號 量 ， 通 常 同 步信 號 量 的 個 數(shù) 與 參 與 同 步 的 進(jìn) 程 種 類 有 關(guān)（ 4） 在 每 個 進(jìn) 程 中 由 于 實 現(xiàn) 互 斥 的 PV操 作 必 須 成對 出 現(xiàn) ； 用 于 實 現(xiàn) 同 步 的 PV操 作 也 必 須 成 對 出

13、 現(xiàn)。 必 須 先 執(zhí) 行 對 同 步 信 號 量 的 P操 作 ， 再 執(zhí) 行 對互 斥 信 號 量 的 P操 作 。 2、 同 步 互 斥 問 題 的 解 題 步 驟（ 1） 確 定 進(jìn) 程 。 包 括 進(jìn) 程 的 數(shù) 量 、 進(jìn) 程 的工 作 內(nèi) 容 ， 可 以 用 流 程 圖 描 述（ 2） 確 定 同 步 互 斥 關(guān) 系 。 根 據(jù) 使 用 的 是 臨界 資 源 ， 還 是 處 理 的 前 后 關(guān) 系 ， 來 確 定 互斥 與 同 步 ， 然 后 確 定 信 號 的 個 數(shù) 、 含 義 ，以 及 對 信 號 量 的 PV操 作（ 3） 用 C語 言 描 述 同 步 或 互 斥 算 法

14、 2.5 進(jìn) 程 通 信 進(jìn) 程 通 信 是 指 進(jìn) 程 間 的 信 息 交 換 。 進(jìn) 程 通信 所 交 換 的 信 息 量 少 則 一 個 數(shù) 值 或 狀 態(tài) ，多 則 成 千 上 萬 個 字 節(jié) 。 根 據(jù) 通 信 的 機(jī) 制 不 同 將 進(jìn) 程 通 信 分 為 低 級通 信 和 高 級 通 信 。 低 級 通 信 -進(jìn) 程 的 同 步 和 互 斥進(jìn) 程 的 同 步 和 互 斥 稱 為 低 級 通 信 。缺 點 ：1、 效 率 低 ， 一 次 發(fā) 送 的 信 息 量 比 較 少 。2、 信 號 量 機(jī) 制 主 要 依 靠 進(jìn) 程 來 控 制 ， 用 戶使 用 不 方 便 。 高 級 通

15、信 高 級 通 信 是 指 用 戶 直 接 利 用 操 作 系 統(tǒng) 提 供的 一 組 通 信 命 令 ， 高 效 地 傳 送 大 量 數(shù) 據(jù) 的一 種 通 信 方 式 。高 級 通 信 機(jī) 制 分 為 3大 類 ：1、 共 享 存 儲 器 系 統(tǒng)2、 消 息 傳 遞 系 統(tǒng)3、 管 道 通 信 系 統(tǒng) 2.5.1 共 享 存 儲 器 系 統(tǒng) 在 共 享 存 儲 器 系 統(tǒng) 中 ， 相 互 通 信 的 進(jìn) 程 共享 某 些 數(shù) 據(jù) 結(jié) 構(gòu) 或 存 儲 區(qū) ， 進(jìn) 程 之 間 能 夠通 過 它 們 進(jìn) 程 通 信 。共 享 存 儲 器 系 統(tǒng) 分 為 2種 方 式 ：1、 共 享 數(shù) 據(jù) 結(jié) 構(gòu)

16、方 式2、 共 享 存 儲 區(qū) 方 式 1、 共 享 數(shù) 據(jù) 結(jié) 構(gòu) 方 式 在 這 種 通 信 方 式 下 ， 相 互 通 信 的 進(jìn) 程 共 用 某些 數(shù) 據(jù) 結(jié) 構(gòu) ， 并 通 過 這 些 數(shù) 據(jù) 結(jié) 構(gòu) 交 換 信 息 。這 種 方 式 與 信 號 量 機(jī) 制 相 比 ， 并 沒 有 發(fā) 生 太大 的 變 化 ， 比 較 低 效 、 復(fù) 雜 ， 只 適 合 于 傳 送少 量 的 數(shù) 據(jù) 。 2、 共 享 存 儲 區(qū) 方 式 這 種 通 信 方 式 是 在 存 儲 器 中 劃 出 一 塊 共 享 存儲 區(qū) ， 相 互 通 信 的 進(jìn) 程 可 以 通 過 對 共 享 存 儲區(qū) 中 的 數(shù)

17、據(jù) 進(jìn) 行 讀 或 寫 來 實 現(xiàn) 通 信 。 這 種 方式 效 率 高 ， 可 以 傳 送 較 多 的 數(shù) 據(jù) 。 2.5.2 消 息 傳 遞 系 統(tǒng) 在 消 息 傳 遞 信 息 中 ， 進(jìn) 程 間 的 數(shù) 據(jù) 交 換 是 以消 息 為 單 位 進(jìn) 行 的 。 用 戶 直 接 利 用 系 統(tǒng) 中 提供 的 一 組 通 信 命 令 （ 原 語 ） 進(jìn) 程 通 信 。 消 息傳 遞 系 統(tǒng) 成 為 最 常 用 的 高 級 通 信 方 式 。優(yōu) 點 ：1、 工 作 效 率 提 高2、 簡 化 了 程 序 編 制 的 復(fù) 雜 性 ， 方 便 用 戶 的 使用 。 1、 直 接 通 信 方 式 發(fā) 送

18、 進(jìn) 程 使 用 發(fā) 送 原 語 直 接 將 消 息 發(fā) 送 給 接 收 進(jìn)程 ， 并 將 它 掛 在 接 收 進(jìn) 程 的 消 息 緩 沖 隊 列 上 。 接收 接 收 進(jìn) 程 使 用 接 收 原 語 從 消 息 緩 沖 隊 列 中 讀 取消 息 。 通 常 系 統(tǒng) 提 供 兩 條 通 信 原 語 。發(fā) 送 原 語 ： Send（ Receiver， message） ；接 收 原 語 ： Receive（ Sender， message） ；例 如 原 語 Send（ P2， M） 表 示 將 消 息 M發(fā) 送 給 接 收進(jìn) 程 P2； 而 原 語 Receive（ P1， M） 則 是 表

19、 示 接收 由 進(jìn) 程 P1發(fā) 送 來 的 消 息 M。 2、 間 接 通 信 方 式 發(fā) 送 進(jìn) 程 與 接 收 進(jìn) 程 通 過 中 間 實 體 信 箱來 完 成 通 信 ， 既 可 以 實 現(xiàn) 實 時 通 信 ， 有 可以 實 現(xiàn) 非 實 時 通 信 。 接 收 進(jìn) 程 使 用 接 收 原 語 從 信 箱 中 取 出 消 息 。 （ 1） 信 箱 通 信 的 操 作 系 統(tǒng) 為 信 箱 通 信 提 供 了 若 干 條 操 作 原 語 ，包 括 創(chuàng) 建 信 箱 原 語 、 撤 銷 信 箱 原 語 、 發(fā) 送原 語 、 接 收 原 語 等 。 1、 信 箱 的 創(chuàng) 建 與 撤 銷 。 進(jìn) 程

20、可 以 利 用 信 箱 創(chuàng) 建 原 語 來 建 立 一 個 新信 箱 。 創(chuàng) 建 進(jìn) 程 應(yīng) 給 出 信 箱 的 名 字 、 信 箱屬 性 等 。 當(dāng) 信 箱 所 屬 進(jìn) 程 不 再 需 要 該 信 箱時 ， 可 用 信 箱 撤 銷 原 語 來 撤 銷 信 箱 。 2、 消 息 的 發(fā) 送 與 接 收 。 相 互 通 信 的 進(jìn) 程 利用 系 統(tǒng) 提 供 的 下 述 通 信 原 語 來 實 現(xiàn) 消 息 的發(fā) 送 與 接 收 。Send（ mailbox， message） ： 將 一 個 消 息發(fā) 送 到 指 定 信 箱Receive（ mailbox， message） ： 從 指 定信 箱

21、 中 接 收 一 個 消 息 （ 2） 消 息 的 分 類 消 息 可 以 由 操 作 系 統(tǒng) 創(chuàng) 建 ， 也 可 以 由 用 戶創(chuàng) 建 。 創(chuàng) 建 者 是 信 箱 的 擁 有 者 ， 信 箱 可 以分 為 3類 ： 1、 私 用 信 箱 。 用 戶 進(jìn) 程 可 以 為 自 己 建 立 一個 新 信 箱 ， 并 作 為 進(jìn) 程 的 一 部 分 信 箱 的 擁有 者 有 權(quán) 從 信 箱 中 讀 取 信 息 ， 其 他 用 戶 只能 將 自 己 的 消 息 發(fā) 送 到 該 信 箱 中 。 當(dāng) 擁 有該 信 箱 的 進(jìn) 程 終 止 時 ， 信 箱 也 隨 之 消 失 。 2、 公 用 信 箱 。 它

22、 由 操 作 系 統(tǒng) 創(chuàng) 建 ， 并 提 供給 系 統(tǒng) 中 所 有 核 準(zhǔn) 的 用 戶 進(jìn) 程 使 用 。 核 準(zhǔn)的 進(jìn) 程 既 可 以 把 消 息 發(fā) 送 到 該 信 箱 ， 有 可以 從 信 箱 中 取 出 發(fā) 送 給 本 人 的 消 息 。 通 常 ，公 用 信 箱 在 系 統(tǒng) 運 行 期 間 始 終 存 在 。 3、 共 享 信 箱 。 它 實 際 上 是 某 種 進(jìn) 程 創(chuàng) 建 的私 有 信 箱 。 在 創(chuàng) 建 時 或 創(chuàng) 建 后 ， 又 指 明 它是 可 以 共 享 的 ， 同 時 指 出 共 享 進(jìn) 程 （ 用 戶 ）的 名 字 ， 此 時 就 成 為 共 享 信 箱 。 信 箱

23、 的 擁有 者 和 共 享 者 ， 都 有 權(quán) 從 信 箱 中 取 走 發(fā) 送給 本 人 的 消 息 。 （ 3） 通 信 進(jìn) 程 間 的 關(guān) 系 當(dāng) 利 用 信 箱 通 信 時 ， 發(fā) 送 進(jìn) 程 與 接 收 進(jìn) 程 存 在 下 列 關(guān) 系 ： 1、 一 對 一 關(guān) 系 。 在 一 個 發(fā) 送 進(jìn) 程 和 一 個 接 收 進(jìn) 程 之 間 建立 一 條 專 用 的 通 信 通 道 ， 使 它 們 之 間 的 通 信 不 受 其 他 進(jìn)程 的 影 響 。 2、 多 對 一 關(guān) 系 。 允 許 提 供 服 務(wù) 的 一 個 接 收 進(jìn) 程 與 多 個 用戶 發(fā) 送 進(jìn) 程 之 間 進(jìn) 行 通 信 ，

24、 也 稱 為 客 戶 /服 務(wù) 器 方 式 。 3、 一 對 多 關(guān) 系 ， 允 許 一 個 發(fā) 送 進(jìn) 程 與 多 個 接 收 進(jìn) 程 進(jìn) 行通 信 ， 使 發(fā) 送 進(jìn) 程 可 以 用 廣 播 形 式 ， 向 一 組 或 全 部 接 收者 發(fā) 送 消 息 。 4、 多 對 多 關(guān) 系 。 允 許 建 立 一 個 公 用 信 箱 ， 讓 多 個 進(jìn) 程 既可 以 把 消 息 發(fā) 送 到 該 信 箱 ， 又 可 以 從 信 箱 中 取 出 發(fā) 送 給本 人 的 消 息 。 2.5.3 管 道 通 信 系 統(tǒng) 管 道 是 指 連 接 讀 進(jìn) 程 和 寫 進(jìn) 程 的 ， 用 于 實現(xiàn) 它 們 之 間

25、 通 信 的 共 享 文 件 。 向 管 道 提 供輸 入 的 發(fā) 送 進(jìn) 程 （ 寫 進(jìn) 程 ） ， 以 字 符 流 的形 式 間 大 量 數(shù) 據(jù) 送 入 管 道 ， 而 接 收 管 道 輸出 的 接 收 進(jìn) 程 （ 讀 進(jìn) 程 ） ， 可 以 從 管 道 中接 收 數(shù) 據(jù) 。 由 于 發(fā) 送 進(jìn) 程 和 接 收 進(jìn) 程 是 利用 管 道 進(jìn) 行 通 信 的 ， 故 稱 為 管 道 通 信 方 式 。 2.6 處 理 機(jī) 調(diào) 度 一 個 作 業(yè) 從 提 交 開 始 直 到 完 成 ， 往 往 要 經(jīng) 歷三 級 調(diào) 度 ， 即 作 業(yè) 調(diào) 度 （ 高 級 調(diào) 度 ） 、 進(jìn) 程調(diào) 度 （ 低

26、級 調(diào) 度 ） 和 中 級 調(diào) 度 。1、 作 業(yè) 調(diào) 度 是 從 后 備 作 業(yè) 隊 列 中 選 擇 出 若 干個 作 業(yè) ， 為 它 們 分 配 必 要 的 資 源 ， 將 它 們 調(diào)入 主 存 ， 為 它 們 建 立 進(jìn) 程 ， 使 之 成 為 就 緒 進(jìn)程 。2、 進(jìn) 程 調(diào) 度 是 從 主 存 就 緒 隊 列 上 選 擇 哪 個 進(jìn)程 獲 得 處 理 器 資 源 ， 讓 進(jìn) 程 運 行 。 56 功 能 ： 按 照 一 定調(diào) 度 算 法 從 就 緒隊 列 中 選 擇 一 個新 的 進(jìn) 程 投 入 運行 。入 口 信 息 ： 可 省 入 口 （ 就 緒 隊 列 指 針 ） 調(diào) 度 算

27、法 選 擇 將 選 中 進(jìn) 程 從 就 緒 隊 列 取 出 運 行 修 改 選 中 進(jìn) 程 的 PCB： 狀 態(tài) =運 行 態(tài) 就 緒 隊 列 就 緒 隊 列 運 行 態(tài) 進(jìn) 程 調(diào) 度 2.6.1 進(jìn) 程 調(diào) 度 算 法 的 選 取 原 則 選 擇 調(diào) 度 算 法 的 原 則 有 面 向 用 戶 的 ， 也 有面 向 系 統(tǒng) 的 。1、 面 向 用 戶 的 原 則（ 1） 周 轉(zhuǎn) 時 間 短（ 2） 相 應(yīng) 時 間 快（ 3） 截 止 時 間 有 保 證（ 4） 優(yōu) 先 權(quán) 原 則 計 算 公 式周 轉(zhuǎn) 時 間 =完 成 時 間 -到 達(dá) 時 間平 均 周 轉(zhuǎn) 時 間 =每 個 進(jìn) 程 的

28、周 轉(zhuǎn) 時 間 之 和 /進(jìn)程 個 數(shù)帶 權(quán) 周 轉(zhuǎn) 時 間 =進(jìn) 程 的 周 轉(zhuǎn) 時 間 /系 統(tǒng) 為 進(jìn) 程提 供 的 實 際 服 務(wù) 時 間平 均 帶 權(quán) 周 轉(zhuǎn) 時 間 =所 有 進(jìn) 程 的 帶 權(quán) 周 轉(zhuǎn) 世間 之 和 /進(jìn) 程 個 數(shù) 2、 面 向 系 統(tǒng) 的 原 則（ 1） 系 統(tǒng) 吞 吐 量 高（ 2） 處 理 器 利 用 率 高（ 3） 各 類 資 源 的 平 衡 利 用 2.6.2 常 用 的 進(jìn) 程 調(diào) 度 算 法 算 法 選 擇 的 合 理 性 ， 將 決 定 進(jìn) 程 調(diào) 度 的 優(yōu) 劣， 它 要 解 決 兩 個 問 題 ： 第 一 選 擇 哪 個 進(jìn) 程 執(zhí) 行 進(jìn)

29、程 調(diào) 度 ； 第 二 個 選 中 某 個 進(jìn) 程 ， 如 何 給 它 分 配 處 理 器， 該 進(jìn) 程 能 占 用 處 理 器 多 久 。 第 一 個 問 題 是 選 擇 進(jìn) 程 調(diào) 度 算 法 ， 第 二 個 問題 是 選 擇 進(jìn) 程 的 調(diào) 度 方 式 。 1 先 來 先 服 務(wù) 調(diào) 度 算 法 FCFS按 照 進(jìn) 程 進(jìn) 入 就 緒 隊 列 的 先 后 順 序選 擇 可 以 占 用 處 理 器 的 進(jìn) 程 。 這 是 一 種 不可 搶 占 方 式 的 調(diào) 度 算 法 。 優(yōu) 點 ： 實 現(xiàn) 簡 單 ， 缺 點 ： 后 來 的 進(jìn) 程 等 待 CPU的 時 間 較 長 。 2 短 執(zhí) 行

30、 進(jìn) 程 優(yōu) 先 算 法 SPF就 是 從 就 緒 隊 列 中 選 擇 一 個 CPU執(zhí) 行時 間 預(yù) 期 最 短 的 進(jìn) 程 ， 將 處 理 器 分 配 給 它。 優(yōu) 點 ： 較 公 平 缺 點 ： 實 現(xiàn) 難 度 較 大 ， 因 為 要 準(zhǔn) 確 預(yù) 定 下一 個 進(jìn) 程 的 CPU執(zhí) 行 周 期 是 很 困 難 的 。 3.最 短 剩 余 時 間 優(yōu) 先 調(diào) 度 算 法 SRT是 將 CPU分 配 給 需 要 最 少 時 間 來完 成 的 進(jìn) 程 。 SRT充 分 照 顧 了 剩 余 運 行 時間 短 的 進(jìn) 程 。 4 時 間 片 輪 轉(zhuǎn) 法 RR讓 每 個 進(jìn) 程 在 就 緒 隊 列

31、中 的 等 待 時 間 與 享受 服 務(wù) 的 時 間 成 比 例 。 在 RR中 ， 需 要 將 CPU的 處 理 時 間 分 成 固 定 大小 的 時 間 片 。 如 果 一 個 進(jìn) 程 在 被 調(diào) 度 選 中 之 后用 完 了 系 統(tǒng) 規(guī) 定 的 時 間 片 ， 但 又 未 完 成 要 求 的任 務(wù) ， 則 它 自 行 釋 放 自 己 所 占 有 的 CPU而 排 到就 緒 隊 列 的 末 尾 ， 等 待 下 一 次 調(diào) 度 。 同 時 ， 進(jìn) 程 調(diào) 度 程 序 又 去 調(diào) 度 當(dāng) 前 就 緒 隊 列 中的 第 一 個 進(jìn) 程 。 5 優(yōu) 先 權(quán) 調(diào) 度 算 法 HPF的 核 心 是 確

32、 定 進(jìn) 程 的 優(yōu) 先 級 。 確 定 優(yōu) 先 級 的 方 法 可 分 為 靜 態(tài) 法 和 動 態(tài) 法 。靜 態(tài) 法 根 據(jù) 進(jìn) 程 的 靜 態(tài) 特 性 ， 在 進(jìn) 程 開 始 執(zhí)行 之 前 就 確 定 它 們 的 優(yōu) 先 級 ， 一 旦 開 始 執(zhí) 行之 后 就 不 能 改 變 。 動 態(tài) 法 把 進(jìn) 程 的 靜 態(tài) 特 性 和 動 態(tài) 特 性 結(jié) 合 起來 確 定 進(jìn) 程 的 優(yōu) 先 級 ， 隨 著 進(jìn) 程 的 執(zhí) 行 過 程， 其 優(yōu) 先 級 不 斷 變 化 。 基 于 靜 態(tài) 優(yōu) 先 級 的 調(diào) 度 算 法 優(yōu) 點 ： 實 現(xiàn) 簡 單 ， 系 統(tǒng) 開 銷 小 缺 點 ： 靜 態(tài) 優(yōu)

33、先 級 一 旦 確 定 之 后 ， 直到 執(zhí) 行 結(jié) 束 為 止 始 終 保 持 不 變 ， 從 而 系統(tǒng) 效 率 較 低 ， 調(diào) 度 性 能 不 高 。 現(xiàn) 在 的 操 作 系 統(tǒng) 中 ， 大 多 采 用 動 態(tài) 優(yōu)先 級 的 調(diào) 度 策 略 。 基 于 動 態(tài) 優(yōu) 先 級 的 調(diào) 度 算 法 (1)根 據(jù) 進(jìn) 程 占 有 CPU時 間 的 長 短 來 決定 。 一 個 進(jìn) 程 占 有 處 理 機(jī) 的 時 間 愈 長， 則 在 被 阻 塞 之 后 再 次 獲 得 調(diào) 度 的 優(yōu)先 級 就 越 低 。 反 之 ， 其 獲 得 調(diào) 度 的 可能 性 就 會 越 大 。 (2)根 據(jù) 就 緒 進(jìn)

34、程 等 待 CPU的 時 間 長 短來 決 定 。 一 個 就 緒 進(jìn) 程 在 就 緒 隊 列 中等 待 的 時 間 越 長 ， 則 它 獲 得 調(diào) 度 選 中的 優(yōu) 先 級 就 越 高 。 2.6.3 作 業(yè) 調(diào) 度 作 業(yè) 是 指 用 戶 在 一 次 計 算 過 程 或 者 事 務(wù) 處 理過 程 中 ， 要 求 計 算 機(jī) 系 統(tǒng) 所 作 工 作 的 集 合 。 作 業(yè) 調(diào) 度 是 從 后 備 作 業(yè) 隊 列 中 選 擇 若 干 個 作業(yè) ， 為 它 們 分 配 必 要 的 資 源 ， 將 它 們 調(diào) 入 主存 ， 為 它 們 建 立 進(jìn) 程 ， 使 它 們 成 為 就 緒 進(jìn) 程的 過

35、程 。 這 涉 及 到 作 業(yè) 所 處 的 狀 態(tài) 、 作 業(yè) 調(diào)度 以 及 調(diào) 度 算 法 。 1、 作 業(yè) 調(diào) 度 采 用 的 數(shù) 據(jù) 結(jié) 構(gòu) 為 了 管 理 和 調(diào) 度 作 業(yè) ， 系 統(tǒng) 為 每 個 作 業(yè) 設(shè)置 一 個 作 業(yè) 控 制 塊 （ JCB） 。 JCB 是 在 作 業(yè) 進(jìn) 入 系 統(tǒng) 時 由 SPOOLING系統(tǒng) 為 其 建 立 的 。 其 內(nèi) 容 由 作 業(yè) 控 制 卡 （ 說明 書 ） 中 得 到 的 。 JCB是 作 業(yè) 存 在 系 統(tǒng) 的標(biāo) 志 ， 作 業(yè) 進(jìn) 入 系 統(tǒng) 時 ， 則 為 之 建 立 JCB， 當(dāng) 作 業(yè) 退 出 時 ， 則 其 JCB也 被 撤

36、銷 。 作 業(yè) 名資 源 要 求資 源 使 用 情 況類 型 級 別優(yōu) 先 級 狀 態(tài) 要 求 的 運 行 時 間 、 使 用 語 言最 遲 完 成 時 間 、 要 求 的 主 存 量要 求 外 設(shè) 類 型 、 臺 數(shù)要 求 的 文 件 量 和 輸 出 量進(jìn) 入 系 統(tǒng) 時 間開 始 運 行 時 間已 運 行 時 間主 存 地 址外 設(shè) 臺 號控 制 方 式 作 業(yè) 類 型優(yōu) 先 數(shù) 作 業(yè) 控 制 表 JCB SPOOLING系 統(tǒng) SPOOLING又 稱 為 外 圍 設(shè) 備 同 時 聯(lián) 機(jī) 操 作 。在 SPOOLING系 統(tǒng) 中 ， 多 臺 外 圍 設(shè) 備 通 過 通道 或 DMA器 件

37、 和 主 機(jī) 與 外 存 連 接 起 來 。 在 硬盤 中 開 辟 一 塊 輸 入 /輸 出 井 ， 并 將 多 個 用 戶 作業(yè) 隨 機(jī) 的 存 儲 提 取 ， 各 用 戶 間 互 不 干 擾 。 系 統(tǒng) 中 的 輸 入 程 序 包 含 兩 個 獨 立 的 過 程 ， 一個 過 程 負(fù) 責(zé) 從 外 部 設(shè) 備 把 信 息 讀 入 緩 沖 區(qū) ；另 一 個 是 寫 過 程 ， 負(fù) 責(zé) 把 緩 沖 區(qū) 的 信 息 送 到外 存 輸 入 井 中 。 2、 作 業(yè) 調(diào) 度 與 進(jìn) 程 調(diào) 度 的 關(guān) 系作 業(yè) 調(diào) 度 與 進(jìn) 程 調(diào) 度 的 關(guān) 系 用 戶 作 業(yè) 錄 入 提 交 收 容 完 成運

38、行 就 緒 阻 塞等 待I/OI/O完 成進(jìn) 程 調(diào) 度 作 業(yè) 調(diào) 度 執(zhí) 行 作 業(yè) 調(diào) 度 3、 常 用 的 作 業(yè) 調(diào) 度 算 法 作 業(yè) 調(diào) 度 程 序 要 完 成 以 下 工 作 ：(1) 按 照 某 種 調(diào) 度 算 法 從 后 備 作 業(yè) 隊 列 中 挑 選 作 業(yè)(2) 為 選 中 的 作 業(yè) 分 配 主 存 和 外 設(shè) 資 源 。(3) 為 選 中 的 作 業(yè) 建 立 相 應(yīng) 的 進(jìn) 程 。(4) 構(gòu) 造 和 填 寫 作 業(yè) 運 行 時 所 需 的 有 關(guān) 表 格 。(5) 作 業(yè) 結(jié) 束 時 完 成 該 作 業(yè) 的 善 后 處 理 工 作 ， 如 收回 資 源 ， 輸 出

39、必 要 的 信 息 ， 撤 消 該 作 業(yè) 的 全 部 進(jìn)程 (PCB) 和 作 業(yè) 控 制 塊 JCB。 調(diào) 度 原 則 ： 公 平 ， 合 理 ， 使 用 戶 滿 意 提 高 系 統(tǒng) 資 源 利 用 率 ， 如 提 高 系 統(tǒng) 吞 吐 量 作 業(yè) 調(diào) 度 算 法 的 評 價 因 素 作 業(yè) 吞 吐 量 ： 運 行 盡 可 能 多 的 作 業(yè) ； 充 分 利 用 資 源 ： CPU忙 、 I/O設(shè) 備 忙 ； 對 各 作 業(yè) 公 平 、 合 理 ， 使 用 戶 滿 意 ： 執(zhí) 行 時 間 長 短 、等 待 時 間 等 ；（ 1） 選 擇 作 業(yè) 調(diào) 度 算 法 應(yīng) 考 慮 的 因 素 （ 2

40、） 常 用 的 作 業(yè) 調(diào) 度 算 法 FCFS按 作 業(yè) 到 達(dá) 系 統(tǒng) 的 先 后 次 序 進(jìn)行 調(diào) 度 。 該 算 法 優(yōu) 先 考 慮 在 系 統(tǒng) 中 等待 時 間 最 長 的 作 業(yè) ， 而 不 考 慮 作 業(yè) 運行 時 間 的 長 短 。 1.先 來 先 服 務(wù) 調(diào) 度 算 法 先 來 先 服 務(wù) 調(diào) 度 算 法由 此 ： 此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 T (2.0+1.5+1.2+1.5)/4=1.55h，此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 W (1.0+3.0+6.0+3.75)/4=3.4375h 注 ： 通 過 以 上 分 析 ， 顯 然 ， 這

41、 種 算 法 容 易 實 現(xiàn) ， 但 效 率 很低 。 2.短 作 業(yè) 優(yōu) 先 調(diào) 度 算 法 SJF 總 是 從 作 業(yè) 的 后 備 隊 列 中 挑 選 運行 時 間 最 短 的 作 業(yè) ， 作 為 下 個 調(diào) 度運 行 的 對 象 。 短 作 業(yè) 優(yōu) 先 調(diào) 度 算 法由 此 ： 此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 T (2.0+2.1+0.7+1.0)/4=1.45h，此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 W (1.0+4.2+3.5+2.5)/4=2.8h注 ： 通 過 以 上 分 析 ， 雖 然 這 種 算 法 易 于 實 現(xiàn) ， 且 效 率 也比 較 高 ，

42、但 未 考 慮 長 作 業(yè) 的 利 益 。 FCFS和 SPF存 在 的 問 題 先 來 先 服 務(wù) 調(diào) 度 算 法 只 考 慮 了 作 業(yè) 的 等 待時 間 ， 而 忽 略 了 作 業(yè) 的 運 行 時 間 ， 對 短 作業(yè) 不 利 ； 短 作 業(yè) 優(yōu) 先 調(diào) 度 算 法 只 考 慮 了 作 業(yè) 運 行 時間 的 長 短 ， 而 忽 略 了 作 業(yè) 的 等 待 時 間 ， 對運 行 時 間 長 的 作 業(yè) 不 利 ， 因 為 如 果 始 終 有短 作 業(yè) 進(jìn) 入 系 統(tǒng) ， 則 較 長 作 業(yè) 會 長 時 間 得不 到 調(diào) 度 。 3.響 應(yīng) 比 高 者 優(yōu) 先 調(diào) 度 算 法 HRRN是 在

43、 每 次 調(diào) 度 作 業(yè) 運 行 時 ， 先 計算 后 備 作 業(yè) 隊 列 中 每 個 作 業(yè) 的 響 應(yīng) 比 ，然 后 挑 選 響 應(yīng) 比 最 高 者 投 入 運 行 。 HRRN既 考 慮 了 作 業(yè) 的 等 待 時 間 又 考慮 了 作 業(yè) 的 運 行 時 間 的 調(diào) 度 算 法 ， 響 應(yīng) 比 高 者 優(yōu) 先 調(diào) 度 算 法 R 作 業(yè) 的 響 應(yīng) 時 間 作 業(yè) 的 運 行 時 間 作 業(yè) 的 響 應(yīng) 時 間 作 業(yè) 的 等 待 時 間 作 業(yè)的 運 行 時 間 作 業(yè) 的 響 應(yīng) 比 為 ： R 1 作 業(yè) 的 等 待 時 間 作 業(yè) 的 運 行 時 間 。 一 個 作 業(yè) 的 響

44、 應(yīng) 比 隨 著 等 待 時 間 的 增 加 而提 高 。 在 相 同 等 待 時 間 的 情 況 下 ， 短 作 業(yè)優(yōu) 先 ， 而 對 于 相 同 運 行 時 間 的 作 業(yè) ， 等 待時 間 長 的 作 業(yè) 優(yōu) 先 運 行 。 響 應(yīng) 比 高 者 優(yōu) 先 調(diào) 度 算 法 由 于 作 業(yè) 1的 開 始 時 間 是 5： 00， 而 其 余 作業(yè) 均 未 到 達(dá) ， 故 先 運 行 作 業(yè) 1。 當(dāng) 作 業(yè) 1運行 完 畢 ， 計 算 后 備 隊 列 中 作 業(yè) 2， 3， 4的 響應(yīng) 比 。 按 照 以 上 的 定 義 和 計 算 公 式 ， 計 算如 下 ： 作 業(yè) 2:R=(60+30)

45、/30=3 作 業(yè) 3:R=(30+12)/12=3.5 作 業(yè) 4:R=(24+24)/24=2 可 見 ， 作 業(yè) 3的 響 應(yīng) 比 最 高 ， 選 擇 作 業(yè) 3運 行 ， 故表 2-3中 作 業(yè) 3的 開 始 時 間 為 作 業(yè) 1的 完 成 時 間 ，即 7:00， 當(dāng) 作 業(yè) 3運 行 完 畢 ， 計 算 后 備 隊 列 中 作業(yè) 2， 4的 響 應(yīng) 比 ， 計 算 如 下 ： 作 業(yè) 2:R=(72+30)/30=3.4 作 業(yè) 4:R=(36+24)/24=2.5 顯 然 ， 這 次 應(yīng) 該 選 擇 作 業(yè) 2， 故 表 2-3中 作 業(yè) 2的開 始 時 間 為 作 業(yè) 3的

46、完 成 時 間 ， 即 7:12， 最 后 運行 作 業(yè) 4。 故 作 業(yè) 運 行 的 次 序 為 ： 1， 3， 2， 4。 由 此 ： 此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 T (2.0+1.7+0.7+1.5)/4=1.475h，此 作 業(yè) 流 的 平 均 周 轉(zhuǎn) 時 間 為 W (1.0+3.4+3.5+3.75)/4=2.9125注 ： 通 過 以 上 分 析 ， 這 種 算 法 既 考 慮 了 作 業(yè) 的 等 待時 間 ， 也 考 慮 了 作 業(yè) 的 運 行 時 間 ， 是 一 種 比 較 理想 的 調(diào) 度 算 法 。 但 這 種 算 法 復(fù) 雜 ， 而 且 需 要 動

47、態(tài)計 算 某 一 作 業(yè) 完 成 時 刻 后 備 隊 列 中 每 個 作 業(yè) 的 響應(yīng) 比 ， 增 加 了 系 統(tǒng) 的 開 銷 。 4.優(yōu) 先 權(quán) 調(diào) 度 算 法 根 據(jù) 作 業(yè) 的 優(yōu) 先 數(shù) 調(diào) 度 作 業(yè) 進(jìn) 入 系 統(tǒng)運 行 。 為 每 個 作 業(yè) 確 定 一 個 優(yōu) 先 數(shù) ，資 源 能 滿 足 且 優(yōu) 先 數(shù) 高 的 作 業(yè) 優(yōu) 先 被選 中 ， 當(dāng) 幾 個 作 業(yè) 有 相 同 的 優(yōu) 先 數(shù) 時， 對 這 些 具 有 相 同 優(yōu) 先 數(shù) 的 作 業(yè) 再 按照 先 來 先 服 務(wù) 原 則 進(jìn) 行 調(diào) 度 。 實 例 解 析 【 例 】 系 統(tǒng) 中 有 四 個 作 業(yè) 同 時 到 達(dá)

48、 ， 它 們的 運 行 時 間 和 優(yōu) 先 數(shù) 如 表 2-9所 示 ， 若 使 用優(yōu) 先 權(quán) 調(diào) 度 算 法 時 ， 作 業(yè) 的 平 均 周 轉(zhuǎn) 時 間為 多 少 ？ 分 析 ： 優(yōu) 先 權(quán) 調(diào) 度 算 法 中 規(guī) 定 作 業(yè) 的 優(yōu) 先數(shù) 越 高 ， 則 該 作 業(yè) 在 運 行 的 次 序 中 越 靠 前， 所 以 本 例 四 個 作 業(yè) 的 運 行 次 序 為 1， 3， 4， 2。 實 例 解 析解 ： 由 表 2-9作 業(yè) 的 優(yōu) 先 數(shù) 得 作 業(yè) 運 行 次 序 為 1， 3， 4， 2，故 該 批 作 業(yè) 的 平 均 周 轉(zhuǎn) 時 間 為 ： T (3) +(3+7) +(3+7

49、+2) +(3+7+2+5)/4=42/4=10.5 5.均 衡 調(diào) 度 算 法 這 種 調(diào) 度 算 法 根 據(jù) 作 業(yè) 對 資 源 的 要 求 進(jìn) 行 分 類 ， 作業(yè) 調(diào) 度 從 各 類 作 業(yè) 中 挑 選 ， 盡 可 能 地 使 使 用 不 同 資源 的 作 業(yè) 同 時 執(zhí) 行 。 這 樣 不 僅 可 以 使 系 統(tǒng) 中 的 不 同類 型 的 資 源 都 在 被 使 用 ， 而 且 可 以 減 少 作 業(yè) 等 待 使用 相 同 資 源 的 時 間 ， 從 而 加 快 作 業(yè) 的 執(zhí) 行 。 有 的 系 統(tǒng) 還 對 每 一 類 中 的 各 作 業(yè) 確 定 優(yōu) 先 數(shù) ， 作 業(yè)調(diào) 度 時 在 每 類 作 業(yè) 中 再 按 優(yōu) 先 數(shù) 高 者 優(yōu) 先 的 調(diào) 度 原則 選 擇 作 業(yè) 。 這 樣 ， 既 能 使 各 類 作 業(yè) 都 得 到 照 顧 ，又 能 照 顧 同 類 作 業(yè) 中 的 緊 迫 作 業(yè) 。