北方工業(yè)大學(xué)操作系統(tǒng)操作系統(tǒng)期末復(fù)習(xí)

操 作 系 統(tǒng) 期 末 復(fù) 習(xí)Made by Tzh 第 一 部 分 ： 大 題 本 部 分 為 課 上 老 師 所 講 的 幾 道 大 題 ， 作 為大 題 而 言 命 中 率 應(yīng) 該 蠻 高 的 吧 ， 它 們 包 括 ： 資 源 分 配 圖 硬 盤 調(diào) 度 頁 面 置 換 算 法 PB操 作 物 理 地 址 替 換 1 .資 源 分 配 圖 會(huì) 看 、 會(huì) 畫 會(huì) 判 斷 死 鎖 P1P2r1 r2 會(huì) 看 、 會(huì) 畫 P1P23 個(gè) 資 源2 個(gè) 資 源P1 進(jìn) 程P1 進(jìn) 程 請 求 資 源進(jìn) 程 擁 有 資 源 P1 擁 有 2 個(gè) r1 資 源 并 請 求 1 個(gè) r2P2 擁 有 1 個(gè) r1 資 源 和 1 個(gè) r2 資 源 并 請 求 1 個(gè) r1r1 r2 判 斷 死 鎖P1P2P1 需 要 1 個(gè) r2 P2 需 要 1 個(gè) r1R1 剩 余 0 個(gè) 資 源 R2 剩 余 1 個(gè) 資 源 P2 的 需 求 無 法 滿 足 ， 但 P1 可 以 得 到 滿 足P1P2 P2 需 要 1 個(gè) r1R1 剩 余 2 個(gè) 資 源 R2 剩 余 1 個(gè) 資 源P1 順 利 執(zhí) 行 ， 釋 放 占 用 所 有 資 源 P2 需 求 得 到 滿 足 ， 順 利 執(zhí) 行P1P2R1 剩 余 3 個(gè) 資 源 R2 剩 余 2 個(gè) 資 源在 這 種 情 況 下 不 會(huì) 死 鎖 那 么 ， 什 么 情 況 下 會(huì) 產(chǎn) 生 死 鎖 呢P1P2P1 需 要 2 個(gè) r2 P2 需 要 1 個(gè) r1R1 剩 余 0 個(gè) 資 源 R2 剩 余 1 個(gè) 資 源此 時(shí) ， P1 、 P2 的 需 求 都 無 法 得 到 滿 足 ， 死 鎖 2 .磁 盤 調(diào) 度想 象 ， 從 磁 盤 圓 心 處 向 外 畫 一 條 直 線 作 為 我 們 下 圖 的 X軸 ， 把 磁 盤 的 磁 道 序 號 標(biāo) 在 上 面 。 題 目 是 這 樣 出 的 條 件 ： 欲 訪 問 的 磁 道 號 ： 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 頭 當(dāng) 前 位 置 ： 1 0 0 問 題 ： 磁 頭 移 動(dòng) 磁 道 數(shù) 和 平 均 尋 道 長 度 1 .先 來 先 服 務(wù) 算 法 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 我 們 從 起 始 位 置 開 始 ， 按 順 序 掃 描 ， 設(shè) 磁 頭 移 動(dòng) 磁 道 數(shù) 為 m， 初 始 為 0 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 頭 移 動(dòng) 到 5 5 ， m+=(1 0 0 -5 5 ),m=4 5 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 頭 移 動(dòng) 到 5 8 ， m+=(5 8 -5 5 ),m=4 8 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 頭 移 動(dòng) 到 3 9 ， m+=(5 8 -3 9 ),m=6 7 注 意 ： 磁 頭 移 動(dòng) 的 是 距 離 而 不 是 位 移 ， 所 以 不 可 能 為 負(fù) 數(shù) ， 因 此 一 定 是 大 減 小 以 此 類 推 ， 直 到 全 部 掃 描 完 當(dāng) 然 ， 如 果 是 答 題 ， 我 們 直 接 列 式 子 即 可 m=(1 0 0 -5 5 )+(5 8 -5 5 )+(5 8 -3 9 )+.=結(jié) 果 平 均 尋 道 長 度 =m/n n為 磁 道 號 個(gè) 數(shù) 2 .最 短 尋 道 時(shí) 間 優(yōu) 先 算 法 為 了 節(jié) 約 時(shí) 間 ， 這 次 我 們 不 再 按 照 順 序 來 掃 描 磁 盤 了 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 還 是 那 些 磁 道 ， 不 過 這 次 我 們 提 前 排 好 序 ， 起 始 位 置 依 然 1 0 0 接 著 我 們 看 ， 在 需 要 跑 的 磁 道 中 ， 離 1 0 0 最 近 的 磁 道 是 哪 個(gè) 這 也 是 我 們 之 所 以 要 排 序 的 原 因 ， 在 這 種 情 況 下 只 有 1 0 0 相 鄰 的 兩 個(gè)磁 道 可 能 是 我 們 的 選 擇 我 們 發(fā) 現(xiàn) ， 相 比 1 5 0 ,磁 道 9 0 離 1 0 0 更 近 ， 所 以 我 們 先 去 9 0 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 m+=(1 0 0 -9 0 ) m=1 0 同 樣 ， 相 比 于 1 0 0 ,5 8 距 離 9 0 更 近 ， 我 們 選 擇 5 8 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 m+=(9 0 -5 8 ) m=4 2 以 此 類 推 ， 知 道 將 所 有 磁 道 跑 完 當(dāng) 然 ， 跑 過 的 磁 道 我 們 不 會(huì) 跑 第 二 遍 我 猜 你 可 能 會(huì) 問 :這 真 的 是 最 短 的 尋 道 時(shí) 間 嗎 ？當(dāng) 然 ， 答 案 肯 定 是 不 一 定 ， 計(jì) 算 機(jī) 只 能 看 到 下 一 步 的 情 況 ，但 它 不 可 能 像 圍 棋 高 手 一 樣 總 覽 全 局 ， 至 于 真 正 的 最 短 ，那 就 是 我 們 程 序 員 寫 的 算 法 才 能 夠 實(shí) 現(xiàn) 了 ， 在 操 作 系 統(tǒng) 中 不 會(huì) 這 么 復(fù) 雜 3 .掃 描 算 法 （ 電 梯 算 法 ） 沒 錯(cuò) ， 就 像 是 電 梯 一 樣 ， 直 上 直 下 ， 一 條 道 走 到 黑 ， 撞 了 南 墻 再 回 頭 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 同 樣 的 ， 我 們 把 磁 道 號 排 好 序 ， 初 始 位 置 1 0 0 然 后 ， 我 們 按 照 序 號 增 加 的 方 向 依 次 尋 道 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 咚 ！ 撞 墻 了 ， 這 時(shí) 可 以 回 頭 了 ， 但 注 意 尋 過 道 的 磁 道 不 需 要 再 走 一 遍 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 所 以 我 們 直 接 跳 到 9 0 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 1 8 、 3 9 、 5 5 、 5 8 、 9 0 、 1 0 0 、 1 5 0 、 1 6 0 分 頁 存 儲(chǔ) 求 物 理 地 址 指 令 ： Load 1 ,2 5 0 0 指 令 的 邏 輯 地 址 是 1 0 0 ， 頁 長 1 k， 求 指 令 的 物 理 地 址 1 .求 頁 號 邏 輯 地 址 /頁 長 ， 商 為 頁 號 ， 余 數(shù) 為 偏 移 量 2 .查 表 3 .物 理 地 址 =物 理 塊 號 *頁 長 +偏 移 量頁 號 物 理塊 號0 41 82 7取 了 兩 次 地 址 ， 第 一 次 根 據(jù) 邏 輯 地 址 找 到 物 理 地 址 ， 第 二 次 取 物 理 地 址 頁 面 置 換 算 法 如 果 給 的 是 邏 輯 地 址 需 要 求 出 頁 號 頁 號 =邏 輯 地 址 /頁 長 （ 要 的 是 商 ） 先 進(jìn) 先 出 （ FIFO）將 頁 號 依 次 排 好 方 法一 開 始 是 依 次 裝 入 物 理 塊 ， 全 都 有 缺 頁 中 斷 方 法如 果 物 理 塊 滿 了 ， 判 斷 哪 個(gè) 頁 面 存 在 時(shí) 間 最 長 就 替 換 方 法 是 向 左 劃 線 判 斷 哪 條 最 長 ， 同 時(shí) 缺 頁 中 斷 方 法如 果 下 一 個(gè) 頁 面 物 理 塊 已 經(jīng) 有 了 ， 就 不 用 寫 了 ， 也 沒 有 缺 頁 中 斷 最 近 最 久 未 使 用 （ LRU） 方 法 往 前 數(shù) 第 三 個(gè) 來 替 換 （ 有 幾 個(gè) 物 理 塊 找 幾 個(gè) ） ， 但 不 算 重 復(fù) 的 ， 有 重 復(fù) 的 還 要 往 前 找 要 計(jì) 算 的 東 西 缺 頁 次 數(shù) ： 每 一 次 頁 面 替 換 和 頁 面 裝 入 （ 畫 的 對 勾 數(shù) ） 被 置 換 的 頁 號 順 序 ： 被 替 換 走 的 頁 號 按 順 序 排 列 缺 頁 率 =缺 頁 次 數(shù) /頁 面 總 數(shù) 生 產(chǎn) 者 消 費(fèi) 者 問 題 他 們 又 是 互 斥 關(guān) 系 ， 又 是 相 互 協(xié) 作 關(guān) 系 ， 也 是 同 步 關(guān) 系 解 法 P操 作 ， 也 可 以 是 wait操 作 是 -， 只 有 參 數(shù) 大 于 0 才 可 以 順 利 執(zhí) 行V操 作 ， 也 可 以 是 signal操 作 是 +， 相 當(dāng) 于 是 恢 復(fù) 例 題2 . 假 定 一 個(gè) 閱 覽 室 可 供 5 0 個(gè) 人 同 時(shí) 閱 讀 。 讀 者 進(jìn) 入 和 離 開 閱 覽 室 時(shí) 都 必 須 在 閱 覽 室 入 口處 的 一 個(gè) 登 記 表 上 登 記 ， 閱 覽 室 有 5 0 個(gè) 座 位 ， 規(guī) 定 每 次 只 允 許 一 個(gè) 人 登 記 或 注 銷 登 記 。要 求 ：（ 1 ） 用 PV操 作 描 述 讀 者 進(jìn) 程 的 實(shí) 現(xiàn) 算 法 （ 可 用 流 程 圖 表 示 ， 登 記 、 注 銷 可 用 自 然 語 言 描述 ） ； （ 2 ） 指 出 算 法 中 所 用 信 號 量 的 名 稱 、 作 用 及 初 值 。 解 S1 :閱 覽 室 可 供 使 用 的 空 座 位 ， 其 初 值 為 5 0 S: 是 否 可 通 過 閱 覽 室 ， 其 初 值 為 1 Process READ_in（ i=1 5 0 ） 到 達(dá) 閱 覽 室 入 口 處 ;P(S1 );P(S); 在 入 口 處 登 記 座 位 號 ; V(s); 進(jìn) 入 座 位 并 閱 讀 ; Process READ_out（ j=1 5 0 ） 結(jié) 束 閱 讀 到 達(dá) 閱 覽 室 入 口 處 ; P(S); 在 入 口 處 注 銷 座 位 號 ; V(S1 );V(S) 離 開 入 口 處 ; 例 題請 用 信 號 量 實(shí) 現(xiàn) 下 圖 所 示 的 前 趨 關(guān) 系 調(diào) 度 算 法 運(yùn) 算 方 法 完 成 時(shí) 間 ： 就 是 目 前 的 完 成 時(shí) 間 加 上 下 一 個(gè) 要 運(yùn) 行 的 進(jìn) 程 的 服 務(wù) 時(shí) 間 周 轉(zhuǎn) 時(shí) 間 ： 各 進(jìn) 程 的 完 成 時(shí) 間 減 去 其 到 達(dá) 的 時(shí) 間 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間 ： 周 轉(zhuǎn) 時(shí) 間 /服 務(wù) 時(shí) 間 高 響 應(yīng) 比 優(yōu) 先 調(diào) 度 算 法 先 算 出 優(yōu) 先 權(quán) 再 進(jìn) 行 比 較 ， 先 運(yùn) 行 大 的 再 運(yùn) 行 小 的 優(yōu) 先 權(quán) =（ 等 待 時(shí) 間 +要 求 服 務(wù) 時(shí) 間 ） /要 求 服 務(wù) 時(shí) 間 等 待 時(shí) 間 ： 該 進(jìn) 程 要 開 始 進(jìn) 行 的 時(shí) 候 總 共 經(jīng) 過 的 時(shí) 間 概 念 題 本 部 分 為 課 上 老 師 在 書 中 所 劃 的 概 念 操 作 系 統(tǒng) 的 目 標(biāo) 有 效 性 提 高 系 統(tǒng) 資 源 利 用 率 提 高 系 統(tǒng) 的 吞 吐 量 吞 吐 量 是 每 秒 的 數(shù) 據(jù) 處 理 量 吞 吐 量 是 在 給 定 時(shí) 間 段 內(nèi) 系 統(tǒng) 完 成 的 交 換 數(shù) 量 .即 系 統(tǒng) 的 吞 吐 量 越 大 ,說明 系 統(tǒng) 在 單 位 時(shí) 間 內(nèi) 完 成 的 用 戶 或 系 統(tǒng) 請 求 越 多 ,系 統(tǒng) 的 資 源 得 到 充 分 利 用 。 方 便 性 可 擴(kuò) 充 性 開 放 性 操 作 系 統(tǒng) 的 作 用 用 戶 接 口 ： OS處 于 用 戶 與 計(jì) 算 機(jī) 硬 件 系 統(tǒng) 之 間 ， 用 戶 通 過 OS來 使 用 計(jì)算 機(jī) 系 統(tǒng) 操 作 系 統(tǒng) 接 口 包 括 ： 1 .命 令 方 式 2 .系 統(tǒng) 調(diào) 用 方 式 3 .圖 形 、 窗 口 方 式 計(jì) 算 機(jī) 系 統(tǒng) 資 源 的 管 理 者 ： OS 推 動(dòng) 操 作 系 統(tǒng) 發(fā) 展 主 要 動(dòng) 力 ： 1 .提 高 計(jì) 算 機(jī) 資 源 的 利 用 率 2 .方 便 用 戶 3 .器 件 升 級 操 作 系 統(tǒng) 的 發(fā) 展 過 程 人 工 操 作 方 式 缺 點(diǎn) ： 1 .用 戶 獨(dú) 占 全 機(jī) 2 .CPU等 待 人 工 操 作 脫 機(jī) 輸 入 /輸 出 方 式 優(yōu) 點(diǎn) ： 1 .減 少 了 CPU的 空 閑 時(shí) 間 2 .提 高 了 I/O速 度 批 處 理 系 統(tǒng) （ 無 交 互 能 力 ） 單 道 批 處 理 系 統(tǒng) 多 道 批 處 理 系 統(tǒng) (宏 觀 并 行 ， 微 觀 串 行 ) 優(yōu) 點(diǎn) ： 1 .資 源 利 用 率 高 2 .系 統(tǒng) 吞 吐 量 大 缺 點(diǎn) ： 1 .平 均 周 轉(zhuǎn) 時(shí) 間 長 2 .無 交 互 能 力 面 臨 問 題 ： 1 .處 理 機(jī) 管 理 問 題 2 .內(nèi) 存 管 理 問 題 3 .I/O設(shè) 備 管 理 問 題 4 .文 件 管 理 問 題 5 .作 業(yè) 管 理 問 題 分 時(shí) 系 統(tǒng) 定 義 ： 它 能 很 好 地 將 一 臺(tái) 計(jì) 算 機(jī) 提 供 給 多 個(gè) 用 戶 同 時(shí) 使 用 ， 提 高 計(jì) 算機(jī) 的 利 用 率 。 用 戶 的 需 求 具 體 表 現(xiàn) 在 ： 1 .人 -機(jī) 交 互 2 .共 享 主 機(jī) 3 .便 于 用 戶 上 機(jī) 關(guān) 鍵 問 題 ： 1 .用 戶 是 否 能 及 時(shí) 接 收 命 令 2 .用 戶 是 否 能 及 時(shí) 處 理 命 令 特 點(diǎn) ： 多 路 性 獨(dú) 立 性 及 時(shí) 性 交 互 性 實(shí) 時(shí) 系 統(tǒng) 硬 實(shí) 時(shí) 與 軟 實(shí) 時(shí) 的 區(qū) 別 硬 實(shí) 時(shí) 系 統(tǒng) 有 一 個(gè) 剛 性 的 、 不 可 改 變 的 時(shí) 間 限 制 ， 它 不 允 許 任 何 超 出時(shí) 限 的 錯(cuò) 誤 。 超 時(shí) 錯(cuò) 誤 會(huì) 帶 來 損 害 甚 至 導(dǎo) 致 系 統(tǒng) 失 敗 、 或 者 導(dǎo) 致 系 統(tǒng) 不 能 實(shí) 現(xiàn) 它 的 預(yù) 期 目 標(biāo) 。 軟 實(shí) 時(shí) 系 統(tǒng) 的 時(shí) 限 是 一 個(gè) 柔 性 靈 活 的 ， 它 可以 容 忍 偶 然 的 超 時(shí) 錯(cuò) 誤 。 失 敗 造 成 的 后 果 并 不 嚴(yán) 重 ， 例 如 在 網(wǎng) 絡(luò) 中 僅僅 是 輕 微 地 降 低 了 系 統(tǒng) 的 吞 吐 量 。 分 時(shí) 系 統(tǒng) 與 實(shí) 時(shí) 系 統(tǒng) 的 比 較 1 .多 路 性 ： 分 時(shí) 系 統(tǒng) 的 多 路 性 與 用 戶 情 況 有 關(guān) ， 時(shí) 多 時(shí) 少 。 實(shí) 時(shí) 控 制系 統(tǒng) 的 多 路 性 則 主 要 表 現(xiàn) 在 系 統(tǒng) 周 期 性 地 對 多 路 現(xiàn) 場 信 息 進(jìn) 行 采 集 ，以 及 對 多 個(gè) 對 象 或 多 個(gè) 執(zhí) 行 機(jī) 構(gòu) 進(jìn) 行 控 制 2 .獨(dú) 立 性 ： 都 是 服 務(wù) 請 求 彼 此 互 不 干 擾 3 .及 時(shí) 性 :實(shí) 時(shí) 系 統(tǒng) 及 時(shí) 性 要 求 更 強(qiáng) 4 .交 互 性 ： 實(shí) 時(shí) 系 統(tǒng) 的 人 與 系 統(tǒng) 的 交 互 僅 限 于 訪 問 系 統(tǒng) 中 某 些 特 定 的專 用 服 務(wù) 程 序 ， 交 互 性 分 時(shí) 系 統(tǒng) 更 強(qiáng) 5 .可 靠 性 ： 實(shí) 時(shí) 系 統(tǒng) 要 求 更 可 靠 操 作 系 統(tǒng) 基 本 特 性 并 發(fā) 性 ： 并 行 性 和 并 發(fā) 性 是 既 相 似 又 有 區(qū) 別 的 兩 個(gè) 概 念 ， 并 行 性 是 指兩 個(gè) 或 多 個(gè) 事 件 在 同 一 時(shí) 刻 發(fā) 生 ； 而 并 發(fā) 性 是 指 兩 個(gè) 或 多 個(gè) 事 件 在 同一 時(shí) 間 間 隔 內(nèi) 發(fā) 生 。 共 享 性 ： 是 指 系 統(tǒng) 中 的 資 源 可 供 內(nèi) 存 中 多 個(gè) 并 發(fā) 執(zhí) 行 的 進(jìn) 程 (線 程 )共同 使 用 虛 擬 性 ： 是 指 通 過 某 種 技 術(shù) 把 一 個(gè) 物 理 實(shí) 體 變 為 若 干 個(gè) 邏 輯 上 的 對 應(yīng)物 。 物 理 實(shí) 體 (前 者 )是 實(shí) 的 ， 即 實(shí) 際 存 在 的 ， 而 后 者 是 虛 的 ， 是 用 戶感 覺 上 的 東 西 。 異 步 性 ： 每 次 只 允 許 一 個(gè) 進(jìn) 程 執(zhí) 行 ， 其 余 進(jìn) 程 只 能 等 待 。 操 作 系 統(tǒng) 的 主 要 功 能 處 理 機(jī) 管 理 功 能 1 .進(jìn) 程 控 制 ： 為 作 業(yè) 創(chuàng) 建 進(jìn) 程 ， 撤 銷 已 結(jié) 束 的 進(jìn) 程 ， 控 制 進(jìn) 程 在 運(yùn) 行過 程 中 的 狀 態(tài) 轉(zhuǎn) 化 2 .進(jìn) 程 同 步 ： 互 斥 與 同 步 方 式 來 協(xié) 調(diào) 多 個(gè) 進(jìn) 程 （ 含 線 程 ） 3 .進(jìn) 程 通 信 方 式 ： 采 用 直 接 通 信 方 式 ， 由 源 進(jìn) 程 利 用 發(fā) 送 命 令 將 信 息掛 到 目 標(biāo) 進(jìn) 程 的 消 息 隊(duì) 列 ， 之 后 由 目 標(biāo) 進(jìn) 程 接 收 。 4 .調(diào) 度 ： 作 業(yè) 調(diào) 度 （ 高 級 調(diào) 度 ） ： 從 后 備 隊(duì) 列 中 通 過 一 定 算 法 找 出 若 干 個(gè) 作 業(yè)并 為 它 們 分 配 內(nèi) 存 ， 建 立 進(jìn) 程 ， 插 入 就 緒 隊(duì) 列 。 進(jìn) 程 調(diào) 度 （ 低 級 調(diào) 度 ） ： 從 就 緒 隊(duì) 列 中 選 出 一 個(gè) 進(jìn) 程 ， 使 該 進(jìn) 程 投 入執(zhí) 行 操 作 系 統(tǒng) 的 主 要 功 能 存 儲(chǔ) 器 管 理 功 能 1 .內(nèi) 存 分 配 ： 為 每 道 程 序 分 配 內(nèi) 存 空 間 （ 靜 態(tài) 、 動(dòng) 態(tài) ） 2 .內(nèi) 存 保 護(hù) ： 使 各 程 序 執(zhí) 行 時(shí) 彼 此 互 不 干 擾 3 .地 址 映 射 ： 邏 輯 地 址 到 物 理 地 址 之 間 的 轉(zhuǎn) 換 4 .內(nèi) 存 擴(kuò) 充 ： 借 助 虛 擬 存 儲(chǔ) （ 1 ） ： 請 求 調(diào) 入 功 能 ： 在 裝 入 部 分 用 戶 程 序 和 數(shù) 據(jù) 的 情 況 下 就 執(zhí) 行 ，中 途 向 OS請 求 從 磁 盤 將 所 需 調(diào) 入 內(nèi) 存 （ 2 ） ： 將 內(nèi) 存 中 一 些 暫 時(shí) 不 用 的 數(shù) 據(jù) 調(diào) 入 硬 盤 騰 出 空 間 操 作 系 統(tǒng) 的 主 要 功 能 設(shè) 備 管 理 功 能 1 .緩 沖 管 理 ： CPU與 I/O之 間 甚 至 緩 沖 區(qū) ， 解 決 速 度 不 匹 配 的 問 題 單 緩 沖 機(jī) 制 、 可 雙 向 傳 送 的 雙 緩 沖 機(jī) 制 、 提 供 多 個(gè) 設(shè) 備 同 時(shí) 使 用 的 公用 緩 沖 池 機(jī) 制 2 .設(shè) 備 分 配 ： 根 據(jù) 用 戶 的 I/O請 求 ， 為 其 分 配 所 需 設(shè) 備 3 .設(shè) 備 處 理 ： CPU與 I/O之 間 的 通 信 操 作 系 統(tǒng) 的 主 要 功 能 文 件 管 理 功 能 1 .文 件 存 儲(chǔ) 空 間 的 管 理 2 .目 錄 管 理 ： 系 統(tǒng) 為 每 個(gè) 文 件 建 立 一 個(gè) 目 錄 項(xiàng) ， 包 括 ： 文 件 名 、 文 件 屬 性 、 文 件 在 磁 盤 上 的 物 理 位 置 3 .文 件 的 讀 /寫 管 理 ： 根 據(jù) 用 戶 給 出 的 文 件 名 檢 索 文 件 目 錄 ， 從 中 獲 得文 件 在 外 存 中 的 位 置 。 4 .文 件 保 護(hù) ： 操 作 系 統(tǒng) 給 應(yīng) 用 的 接 口 程 序 接 口 也 稱 為 系 統(tǒng) 調(diào) 用庫 函 數(shù) 屬 于 用 戶 程 序 而 非 系 統(tǒng) 調(diào) 用 ， 是 系 統(tǒng) 調(diào) 用 的 上 層 ， 有 些 庫 函 數(shù) 與 系 統(tǒng) 調(diào) 用 是 無 關(guān) 的（ math.h）所 謂 原 語 ， 是 操 作 系 統(tǒng) 內(nèi) 核 中 ， 由 若 干 條 指 令 構(gòu) 成 、 用 于 完 成 一 個(gè) 特 定 的 功 能 的 一 個(gè) 過 程 ，該 過 程 在 執(zhí) 行 時(shí) 是 不 可 中 斷 的 。 微 內(nèi) 核 系 統(tǒng) （ 不 含 LINUX） 優(yōu) 點(diǎn) 1 .提 高 系 統(tǒng) 可 擴(kuò) 展 性 2 .提 高 系 統(tǒng) 可 靠 性 3 .可 移 植 性 4 .提 供 了 對 分 布 式 系 統(tǒng) 的 支 持 5 .融 入 了 面 向 對 象 技 術(shù) 缺 點(diǎn) ： 運(yùn) 行 效 率 低 硬 中 斷 ： 由 與 系 統(tǒng) 相 連 的 外 設(shè) (比 如 網(wǎng) 卡 、 硬 盤 )自 動(dòng) 產(chǎn) 生 的 。 主 要 是用 來 通 知 操 作 系 統(tǒng) 系 統(tǒng) 外 設(shè) 狀 態(tài) 的 變 化 微 內(nèi) 核 中 斷 和 陷 入 處 理 （ 軟 中 斷 ） 將 與 硬 件 緊 密 相 關(guān) 的 一 小 部 分 放 在 微 內(nèi) 核 中 處 理 ， 微 內(nèi) 核 所 做 的 就 只是 前 期 處 理 ， 將 消 息 發(fā) 給 服 務(wù) 器 由 服 務(wù) 器 再 進(jìn) 行 后 期 處 理 ， 因 此 微 內(nèi) 核 可 以 做 的 很 小 。 進(jìn) 程 的 順 序 執(zhí) 行 順 序 執(zhí) 行 （ 適 合 直 接 訪 問 ） ： 例 如 輸 入 與 打 印 ， 必 須 按 順 序 前 趨 圖 ： 有 向 無 環(huán) 圖 進(jìn) 程 由 創(chuàng) 建 而 產(chǎn) 生 ， 由 調(diào) 度 而 執(zhí) 行 ， 由 撤 銷 而 消 亡 進(jìn) 程 的 并 發(fā) 執(zhí) 行 程 序 的 并 發(fā) 執(zhí) 行 ： 多 道 程 序 可 同 時(shí) 進(jìn) 行 ， 但 對 于 每 一 道 程 序 而 言 是 順序 執(zhí) 行 。 程 序 并 發(fā) 執(zhí) 行 的 特 征 ： 1 .間 斷 性 ： 一 個(gè) 任 務(wù) 可 能 需 要 等 待 它 的 前 驅(qū) 任 務(wù) 完 成 才 能 繼 續(xù) 執(zhí) 行 ，產(chǎn) 生 等 待 。 2 .失 去 封 閉 性 ： 多 個(gè) 程 序 共 享 系 統(tǒng) 中 資 源 ， 這 些 資 源 將 由 多 個(gè) 程 序 來改 變 。 3 .不 可 再 現(xiàn) 性 ： 由 于 失 去 封 閉 性 ， 輸 入 的 結(jié) 果 與 并 發(fā) 程 序 的 速 度 有 關(guān) ，每 一 次 的 輸 出 結(jié) 果 不 同 。 進(jìn) 程 特 征 和 狀 態(tài) 1 .結(jié) 構(gòu) 特 征 ： 進(jìn) 程 實(shí) 體 （ 在 UNIX中 稱 為 “進(jìn) 程 映 像 ”） 程 序 段 相 關(guān) 數(shù) 據(jù) 段 PCB： 作 用 寄 存 器 有 什 么 ， 進(jìn) 程 的 唯 一 標(biāo) 識(shí) 動(dòng) 態(tài) 性 ： 進(jìn) 程 是 程 序 的 一 次 執(zhí) 行 過 程 ， 它 有 一 定 的 生 命 期 并 發(fā) 性 ： 多 個(gè) 進(jìn) 程 同 時(shí) 進(jìn) 行 獨(dú) 立 性 ： 進(jìn) 程 實(shí) 體 獨(dú) 立 異 步 性 ： 進(jìn) 程 各 自 獨(dú) 立 ， 速 度 不 一 2 .進(jìn) 程 的 狀 態(tài) 許 可 釋 放 進(jìn) 程 控 制 塊 （ PCB） 進(jìn) 程 控 制 塊 組 織 方 式 ： 1 .鏈 接 方 式 按 進(jìn) 程 優(yōu) 先 級 高 低 排 列 隱 式 鏈 接 最 不 適 合 直 接 訪 問 執(zhí) 行 指 針 就 一 個(gè) 鏈 接 字 2 .索 引 表 方 式 進(jìn) 程 控 制 進(jìn) 程 的 創(chuàng) 建 ： 1 .申 請 空 白 PCB 2 .為 新 進(jìn) 程 分 配 資 源 3 .初 始 化 進(jìn) 程 控 制 塊 （ PCB） 4 .將 新 進(jìn) 程 插 入 就 緒 隊(duì) 列 終 止 過 程 ： 1 .通 過 該 進(jìn) 程 PCB讀 出 該 進(jìn) 程 的 狀 態(tài) 2 .結(jié) 束 該 進(jìn) 程 的 執(zhí) 行 3 .結(jié) 束 該 進(jìn) 程 的 子 孫 進(jìn) 程 4 .釋 放 該 進(jìn) 程 占 有 的 資 源 5 .將 被 終 止 進(jìn) 程 從 所 在 隊(duì) 列 移 出 進(jìn) 程 阻 塞 與 喚 醒 進(jìn) 程 的 阻 塞 ： 進(jìn) 程 由 于 某 些 原 因 無 法 繼 續(xù) 進(jìn) 行 ， 進(jìn) 程 調(diào) 用 阻 塞 源 語 自己 把 自 己 阻 塞 ， 從 執(zhí) 行 狀 態(tài) 變 為 阻 塞 狀 態(tài) 。 阻 塞 原 因 ： 1 .請 求 系 統(tǒng) 服 務(wù) 未 得 到 響 應(yīng) 。 2 .啟 動(dòng) 某 種 操 作 （ 操 作 完 成才 可 繼 續(xù) 執(zhí) 行 ） 。 3 .新 數(shù) 據(jù) 尚 未 到 達(dá) 。 4 .無 新 工 作 可 做 進(jìn) 程 的 喚 醒 （ 與 阻 塞 互 逆 ） ： 當(dāng) 進(jìn) 程 所 期 望 的 事 件 出 現(xiàn) ， 便 自 己 調(diào) 用喚 醒 源 語 ， 將 自 己 從 阻 塞 隊(duì) 列 移 出 ， 到 就 緒 隊(duì) 列 。 掛 起 ： 由 用 戶 或 父 進(jìn) 程 引 起 激 活 （ 與 掛 起 互 逆 ） ： 由 用 戶 或 父 進(jìn) 程 引 起 進(jìn) 程 同 步 互 斥 臨 界 區(qū) ： 每 個(gè) 進(jìn) 程 訪 問 臨 界 資 源 的 那 段 代 碼 稱 為 臨 界 區(qū) 臨 界 資 源 （ 硬 件 資 源 如 打 印 機(jī) 等 ） ： 在 一 段 時(shí) 間 內(nèi) 只 允 許 一 個(gè) 進(jìn) 程 訪問 的 資 源 ， 臨 界 資 源 的 訪 問 要 求 互 斥 的 訪 問 進(jìn) 程 互 斥 ： 一 個(gè) 進(jìn) 程 正 在 訪 問 臨 界 資 源 ， 另 一 個(gè) 要 訪 問 該 資 源 的 進(jìn) 程必 須 等 待 。 但 互 斥 無 法 限 制 訪 問 者 對 資 源 的 訪 問 順 序 ， 即 訪 問 是 無 序的 。 進(jìn) 程 同 步 ： 是 指 在 互 斥 的 基 礎(chǔ) 上 （ 大 多 數(shù) 情 況 ） ， 通 過 其 它 機(jī) 制 實(shí) 現(xiàn)訪 問 者 對 資 源 的 有 序 訪 問 。 在 大 多 數(shù) 情 況 下 ， 同 步 已 經(jīng) 實(shí) 現(xiàn) 了 互 斥 ，特 別 是 所 有 寫 入 資 源 的 情 況 必 定 是 互 斥 的 。 少 數(shù) 情 況 是 指 可 以 允 許 多個(gè) 訪 問 者 同 時(shí) 訪 問 資 源 同 步 機(jī) 制 規(guī) 則 1 .空 閑 讓 進(jìn) 2 .忙 則 等 待 3 .有 限 等 待 ： 不 能 讓 進(jìn) 程 一 直 等 ， 得 一 段 時(shí) 間 內(nèi) 能 得 到 臨 界 資 源 4 .讓 權(quán) 等 待 ： 進(jìn) 程 如 果 不 能 進(jìn) 入 臨 界 區(qū) ， 就 別 等 了 信 號 量 1 .整 型 信 號 量 ： wait（ S） ， signal（ S） S為 整 型 信 號 量 ， 初 值 為 1 ， 當(dāng) 前 為 2 代 表 有 兩 個(gè) 資 源 ， 當(dāng) 前 為 0 代 表 被占 用 ， 當(dāng) 前 為 -1 代 表 已 經(jīng) 有 一 個(gè) 等 待 2 .記 錄 型 信 號 量 除 了 對 信 號 量 加 減 之 外 ， 還 有 判 斷 ， 不 行 就 阻 塞 去 3 .AND型 信 號 量 ： 一 個(gè) 進(jìn) 程 可 能 需 要 多 個(gè) 資 源 才 能 進(jìn) 行 ， 中 途 可 能 有其 它 資 源 爭 奪 ， 所 以 為 了 解 決 死 鎖 的 問 題 ， 我 們 在 wait語 句 中 增 加 and條 件 ， 只 有 判 斷 它 每 一 個(gè) 要 求 的 資 源 都 存 在 ， 才 占 用 ， 否 則 阻 塞 信 號 量 集 ： 設(shè) 置 需 求 值 和 下 限 值 ， 判 斷 條 件 不 再 是 1 ， 而 是 下 限 值 信 號 量 的 應(yīng) 用 1 .利 用 信 號 量 實(shí) 現(xiàn) 進(jìn) 程 互 斥 ： 設(shè) 置 一 互 斥 信 號 量 ， 初 值 為 1 ， 標(biāo) 記 該 資源 是 否 可 以 被 使 用 ， 從 而 使 進(jìn) 程 對 該 資 源 互 斥 訪 問 2 .利 用 信 號 量 （ 初 值 為 0 ） 實(shí) 現(xiàn) 前 趨 關(guān) 系 ： 對 于 有 前 置 的 等 待 進(jìn) 程 ， 只有 它 的 前 趨 進(jìn) 程 執(zhí) 行 完 才 執(zhí) 行 該 進(jìn) 程 ， 前 趨 進(jìn) 程 是 否 執(zhí) 行 結(jié) 束 我 們 通過 信 號 量 來 控 制 。 經(jīng) 典 進(jìn) 程 同 步 問 題 生 產(chǎn) 者 消 費(fèi) 者 讀 者 寫 者 哲 學(xué) 家 進(jìn) 餐 問 題 進(jìn) 程 通 信 進(jìn) 程 間 的 信 息 交 換 直 接 通 信 方 式 ： 直 接 把 消 息 發(fā) 送 給 目 標(biāo) 進(jìn) 程 ， 發(fā) 送 進(jìn) 程 和 接 收 進(jìn) 程 都是 顯 示 方 式 提 供 對 方 標(biāo) 識(shí) 符 間 接 通 信 方 式 ： 有 一 個(gè) 實(shí) 體 （ 信 箱 ） 暫 存 發(fā) 送 的 消 息 ， 接 受 消 息 的 一方 也 從 信 箱 中 獲 取 消 息 消 息 緩 沖 隊(duì) 列 通 信 機(jī) 制 ： 在 緩 沖 區(qū) 暫 存 信 息 ， 以 隊(duì) 列 的 形 式 逐 條 存 儲(chǔ) 線 程 （ 只 是 調(diào) 度 單 位 ） 進(jìn) 程 使 資 源 分 配 單 位 +調(diào) 度 單 位 屬 性 ： 1 .輕 型 實(shí) 體 ： 基 本 不 擁 有 系 統(tǒng) 資 源 ， 只 有 TCB 2 .獨(dú) 立 調(diào) 度 和 分 派 的 基 本 單 位 ： 不 可 再 分 ， 切 換 迅 速 開 銷 小 3 .可 并 發(fā) 執(zhí) 行 4 .共 享 進(jìn) 程 資 源 內(nèi) 核 支 持 線 程 ： 進(jìn) 程 的 創(chuàng) 建 撤 銷 都 是 利 用 系 統(tǒng) 調(diào) 用 進(jìn) 入 內(nèi) 核 ， 線 程 也是 如 此 用 戶 級 線 程 ： 只 存 在 于 用 戶 空 間 中 ， 無 需 系 統(tǒng) 調(diào) 用 調(diào) 度 作 業(yè) 調(diào) 度 （ 高 級 調(diào) 度 、 長 程 調(diào) 度 ） ： 從 后 備 隊(duì) 列 中 通 過 一 定 算 法 找 出若 干 個(gè) 作 業(yè) 并 為 它 們 分 配 內(nèi) 存 ， 建 立 進(jìn) 程 ， 插 入 就 緒 隊(duì) 列 。 進(jìn) 程 調(diào) 度 （ 低 級 調(diào) 度 、 短 程 調(diào) 度 ） ： 從 就 緒 隊(duì) 列 中 選 出 一 個(gè) 進(jìn) 程 ， 使該 進(jìn) 程 投 入 執(zhí) 行 1 .保 存 現(xiàn) 場 信 息 ， 存 入 PCB 2 .按 某 種 算 法 選 取 進(jìn) 程 3 .把 處 理 器 分 配 給 進(jìn) 程 基 本 機(jī) 制 ： 1 .排 隊(duì) 器 ： 將 就 緒 進(jìn) 程 排 隊(duì) ， 提 高 效 率 2 .分 派 器 ： 從 就 緒 隊(duì) 列 提 出 選 中 的 要 執(zhí) 行 進(jìn) 程 3 .上 下 文 切 換 ： 第 一 隊(duì) 上 下 文 ： 將 當(dāng) 前 運(yùn) 行 進(jìn) 程 的 信 息 保 存 給 分 派 程 序 第 二 隊(duì) 上 下 文 ： 將 新 進(jìn) 程 的 現(xiàn) 場 信 息 裝 進(jìn) 來 調(diào) 度 方 式 非 搶 占 方 式 ： 一 個(gè) 進(jìn) 程 一 直 運(yùn) 行 到 完 才 運(yùn) 行 下 一 個(gè) 搶 占 方 式 ： 通 過 以 下 原 則 暫 停 某 個(gè) 正 在 運(yùn) 行 的 進(jìn) 程 原 則 ： 1 .優(yōu) 先 權(quán) 原 則 ： 緊 急 任 務(wù) 具 有 較 高 優(yōu) 先 權(quán) 2 短 作 業(yè) 優(yōu) 先 原 則 ： 先 執(zhí) 行 耗 時(shí) 短 的 進(jìn) 程 3 .時(shí) 間 片 原 則 ： 按 時(shí) 間 片 流 轉(zhuǎn) ， 公 平 。 時(shí) 間 片 大 了 小 了 都 不 好 ， 應(yīng) 該 在 0 .0 1 s0 .1 s之 間 （ 大 部 分 如 此 ） 調(diào) 度 隊(duì) 列 模 型 僅 有 進(jìn) 程 調(diào) 度 ： 完 全 按 照 用 戶 鍵 入 的 命 令 順 序 執(zhí) 行 程 序 作 業(yè) 調(diào) 度 ： 根 據(jù) 不 同 原 則 的 不 同 算 法 選 擇 插 入 就 緒 隊(duì) 列 的 進(jìn) 程 ， 不 一定 按 順 序 。 中 級 調(diào) 度 ： 把 進(jìn) 程 就 緒 分 為 內(nèi) 存 就 緒 （ 進(jìn) 程 在 內(nèi) 存 中 就 緒 ） 和 外 存 就緒 （ 進(jìn) 程 在 外 存 中 就 緒 ） ， 阻 塞 狀 態(tài) 也 分 成 外 存 內(nèi) 存 調(diào) 度 準(zhǔn) 則 面 向 用 戶 ： 周 轉(zhuǎn) 時(shí) 間 短 、 響 應(yīng) 時(shí) 間 快 、 截 止 時(shí) 間 保 證 、 優(yōu) 先 權(quán) 準(zhǔn) 則 面 向 系 統(tǒng) ： 系 統(tǒng) 吞 吐 量 高 、 處 理 機(jī) 利 用 率 好 、 各 類 資 源 平 衡 利 用 實(shí) 時(shí) 調(diào) 度 最 早 截 止 時(shí) 間 優(yōu) 先 （ EDF） 算 法 ： 任 務(wù) 的 開 始 截 止 時(shí) 間 越 早 ， 優(yōu) 先 級越 高 最 低 松 弛 度 優(yōu) 先 （ LLF） 算 法 ： 根 據(jù) 任 務(wù) 緊 急 或 松 弛 的 程 度 來 確 定 優(yōu) 先級 死 鎖 定 義 ： 多 個(gè) 進(jìn) 程 搶 奪 資 源 而 形 成 的 僵 局 原 因 ： 1 .競 爭 資 源 ： 因 為 諸 進(jìn) 程 對 資 源 的 競 爭 引 起 2 .進(jìn) 程 間 推 進(jìn) 順 序 非 法 ： 請 求 和 釋 放 資 源 的 順 序 不 當(dāng) ， 也 同 樣 會(huì) 導(dǎo) 致產(chǎn) 生 進(jìn) 程 的 死 鎖 。 產(chǎn) 生 死 鎖 的 必 要 條 件 1 .互 斥 條 件 ： 該 資 源 要 求 訪 問 的 進(jìn) 程 互 斥 訪 問 2 .請 求 和 保 持 條 件 ： 該 進(jìn) 程 已 占 有 資 源 但 還 請 求 其 他 資 源 ， 但 資 源 又被 其 他 進(jìn) 程 占 用 ， 則 該 進(jìn) 程 請 求 進(jìn) 程 阻 塞 ， 又 對 已 獲 得 資 源 不 放 3 .不 剝 奪 條 件 ： 進(jìn) 程 已 獲 得 的 資 源 在 該 進(jìn) 程 執(zhí) 行 完 畢 之 前 不 釋 放 4 .環(huán) 路 等 待 條 件 ： 發(fā) 生 死 鎖 時(shí) ， 必 然 存 在 一 個(gè) 進(jìn) 程 資 源 的 環(huán) 形 鏈 P0 ， P1 ， P2 ,.Pn， P0 等 待 P1 資 源 ， P1 等 待 P2 資 源 。 。 Pn等 待 P0 資 源 處 理 死 鎖 方 法 1 .預(yù) 防 死 鎖 ： 通 過 破 壞 產(chǎn) 生 死 鎖 的 四 個(gè) 必 要 條 件 中 的 某 些 來 避 免 死 鎖 2 .安 全 狀 態(tài) ： 在 資 源 分 配 之 前 先 檢 測 資 源 分 配 安 全 性 ， 若 不 安 全 ， 則另 進(jìn) 程 等 待 銀 行 家 算 法 銀 行 家 算 法 的 步 驟 死 鎖 檢 測 與 解 除 檢 測 方 法 ： 利 用 資 源 分 配 圖 （ 大 題 第 一 個(gè) ） 死 鎖 解 除 ： 1 .剝 奪 資 源 ： 從 其 它 進(jìn) 程 剝 奪 足 夠 量 的 資 源 給 死 鎖 進(jìn) 程 解 除 死 鎖 狀 態(tài) 2 .撤 銷 進(jìn) 程 ： 撤 銷 死 鎖 進(jìn) 程 溫 柔 一 點(diǎn) 的 方 法 是 按 某 種 順 序 逐 個(gè) 撤 銷 死 鎖 進(jìn) 程 ， 在 此 過 程 中 可 以 釋放 資 源 ， 使 得 某 些 死 鎖 進(jìn) 程 得 以 解 除 死 鎖 狀 態(tài)