例 如, 一 个 含 有 2000 个 记 录 的 文 件, 每 个 磁 盘 块 可 容 纳 250 个 记 录, 则 该 文 件 包 含 8 个 磁 盘 块 然 后 对 该 文 件 作 二 路 归 并 的 外 排 序, 每 次 往 内 存 读 入 两 个 磁 盘 块, 排 序 后 再 写 回 磁

Transcription

1 说 明 改 动 的 内 容 很 少, 且 都 是 不 怎 么 重 要 的, 因 此 无 需 过 多 纠 结, 大 家 看 完 后 一 目 了 然 第 6 章 排 序 1 增 加 了 :( 十 ) 外 部 排 序 第 一 部 分 : 数 据 结 构 2 后 面 的 修 改 :( 十 一 ) 各 种 内 部 排 序 算 法 的 比 较 ;( 十 二 ) 内 部 排 序 算 法 的 应 用 外 部 排 序 历 来 不 是 DS 的 重 点, 有 些 学 校 的 本 科 课 程 甚 至 都 直 接 跳 过, 而 且 外 部 排 序 和 内 部 排 序 算 法 不 具 有 较 大 的 可 比 性, 因 此 增 加 和 改 动 的 这 个 知 识 点 不 必 纠 结 外 部 排 序 本 节 内 容 属 于 了 解 型 知 识 点, 考 查 的 概 率 不 大 主 要 可 能 会 考 查 外 部 排 序 的 概 念 方 法 和 排 序 过 程, 外 部 排 序 的 算 法 比 较 复 杂, 不 会 在 算 法 设 计 上 进 行 考 查 本 节 的 主 要 内 容 如 下 : 1) 外 部 排 序 指 待 排 序 文 件 较 大, 内 存 一 次 存 放 不 下, 尚 需 存 放 在 外 部 介 质 的 文 件 的 排 序 2) 为 减 少 平 衡 归 并 中 外 存 读 写 次 数 所 采 取 的 方 法 : 增 大 归 并 路 数 和 减 少 归 并 段 个 数 3) 利 用 败 者 树 增 大 归 并 路 数 4) 利 用 置 换 - 选 择 排 序 增 大 归 并 段 长 度 来 减 少 归 并 段 个 数 5) 由 长 度 不 等 的 归 并 段, 进 行 多 路 平 衡 归 并, 需 要 构 造 最 佳 归 并 树 1. 外 部 排 序 的 基 本 概 念 前 面 介 绍 过 的 排 序 方 法 都 是 在 内 存 中 进 行 的 ( 称 为 内 部 排 序 ) 而 在 许 多 实 际 应 用 中, 经 常 需 要 对 大 文 件 进 行 排 序, 因 为 文 件 中 的 记 录 很 多 信 息 量 庞 大, 无 法 将 整 个 文 件 拷 贝 进 内 存 中 进 行 排 序 因 此, 需 要 将 待 排 序 的 记 录 存 储 在 外 存 上, 排 序 时 再 把 数 据 一 部 分 一 部 分 的 调 入 内 存 进 行 排 序 在 排 序 过 程 中 需 要 多 次 进 行 内 存 和 外 存 之 间 的 交 换, 对 外 存 文 件 中 的 记 录 进 行 排 序 后 的 结 果 仍 然 被 放 到 原 有 文 件 中 这 种 排 序 方 法 就 称 为 外 部 排 序 2. 外 部 排 序 的 方 法 在 实 际 应 用 中, 由 于 使 用 的 外 存 设 备 不 同, 通 常 又 可 分 为 磁 盘 文 件 排 序 和 磁 带 文 件 排 序 两 大 类 磁 带 排 序 和 磁 盘 排 序 的 基 本 步 骤 相 类 似, 它 们 的 主 要 不 同 之 处 在 于 初 始 归 并 段 在 外 存 介 质 中 的 分 布 方 式, 磁 盘 是 直 接 存 取 设 备, 磁 带 是 顺 序 存 取 设 备 下 面 以 磁 盘 为 例 进 行 说 明 文 件 通 常 是 按 块 存 储 在 磁 盘 / 磁 带 上 的,OS 也 是 按 块 对 磁 盘 / 磁 带 上 的 信 息 进 行 读 写 的 因 为 磁 盘 / 磁 带 的 读 / 写 的 机 械 动 作 所 需 时 间 远 远 超 过 内 存 运 算 的 时 间 ( 相 比 而 言, 可 以 忽 略 不 计 ) 因 此, 在 外 部 排 序 的 过 程 中 考 虑 时 间 代 价 主 要 考 虑 访 问 磁 盘 / 磁 带 的 次 数, 即 I/O 次 数 外 部 排 序 通 常 采 用 归 并 排 序 方 法 它 包 括 两 个 相 对 独 立 的 阶 段 : 首 先, 根 据 内 存 缓 冲 区 的 大 小, 将 外 存 上 含 n 个 记 录 的 文 件 分 成 若 干 长 度 为 h 的 子 文 件, 依 次 读 入 内 存 并 利 用 有 效 的 内 部 排 序 方 法 对 它 们 进 行 排 序, 并 将 排 序 后 得 到 的 有 序 子 文 件 重 新 写 回 外 存, 通 常 称 这 些 有 序 子 文 件 为 初 始 归 并 段 或 顺 串 ; 然 后, 对 这 些 初 始 归 并 段 进 行 逐 趟 归 并, 使 归 并 段 ( 有 序 的 子 文 件 ) 逐 渐 由 小 到 大, 直 至 得 到 整 个 有 序 文 件 为 止 最 简 单 的 归 并 方 法 类 似 于 内 部 排 序 中 的 二 路 归 并 算 法 二 路 平 衡 归 并 的 基 本 思 想 是 : 先 把 具 有 n 个 记 录 的 文 件 看 作 是 由 n 个 长 度 为 1 的 顺 串 构 成 在 此 基 础 上 进 行 一 趟 又 一 趟 的 归 并 一 趟 归 并, 是 把 文 件 中 每 一 对 长 度 为 h 的 顺 串 合 并 成 一 个 长 度 为 2h 的 顺 串 ; 其 结 果 将 使 文 件 中 顺 串 的 长 度 增 加 一 倍 而 使 顺 串 的 数 量 减 少 一 半 经 过 若 干 趟 归 并 之 后, 当 文 件 中 只 含 有 一 个 长 度 为 n 的 顺 串 时, 整 个 文 件 的 排 序 就 完 成 了

2 例 如, 一 个 含 有 2000 个 记 录 的 文 件, 每 个 磁 盘 块 可 容 纳 250 个 记 录, 则 该 文 件 包 含 8 个 磁 盘 块 然 后 对 该 文 件 作 二 路 归 并 的 外 排 序, 每 次 往 内 存 读 入 两 个 磁 盘 块, 排 序 后 再 写 回 磁 盘 图 6-1 二 路 平 衡 归 并 的 排 序 过 程 若 把 内 存 工 作 区 等 分 为 3 个 缓 冲 区, 如 图 6-2 所 示 其 中 的 两 个 为 输 入 缓 冲 区, 一 个 为 输 出 缓 冲 区, 可 以 在 内 存 中 利 用 7.5 节 中 的 简 单 二 路 归 并 merge 函 数 实 现 二 路 归 并 首 先, 从 参 加 归 并 排 序 的 两 个 输 入 归 并 段 R1 和 R2 中 分 别 读 入 一 个 块, 放 在 输 入 缓 冲 区 1 和 输 入 缓 冲 区 2 中 然 后, 在 内 存 中 进 行 二 路 归 并, 归 并 出 来 的 对 象 顺 序 存 放 在 输 出 缓 冲 区 中 若 输 出 缓 冲 区 中 对 象 存 满, 则 将 其 内 的 对 象 顺 序 写 到 输 出 归 并 段 (R1 ) 中, 再 将 该 输 出 缓 冲 区 清 空, 继 续 存 放 归 并 后 的 对 象 若 某 一 个 输 入 缓 冲 区 中 的 对 象 取 空, 则 从 对 应 的 输 入 归 并 段 中 再 读 取 下 一 块 ( 这 种 情 况 第 一 趟 归 并 时 不 会 出 现 ), 继 续 参 加 归 并 如 此 继 续, 直 到 两 个 输 入 归 并 段 中 对 象 全 部 读 入 内 存 并 都 归 并 完 成 为 止 当 R1 和 R2 归 并 完 后, 再 归 并 R3 和 R4 R5 和 R6 最 后 归 并 R7 和 R8, 这 算 作 一 趟 归 并 再 把 上 趟 的 结 果 R1 R2 R3 和 R4 两 两 归 并, 这 又 是 一 趟 归 并 最 后 把 R1 和 R2 两 个 归 并 段 归 并, 结 果 得 到 最 终 的 有 序 文 件, 一 共 进 行 了 3 趟 归 并, 如 图 6-1 所 示 图 6-2 二 路 归 并 在 外 部 排 序 中 实 现 两 两 归 并 时, 不 仅 要 调 用 7.5 节 中 的 merge 过 程, 而 且 要 进 行 外 存 的 读 / 写, 由 于 不 可 能 将 两 个 有 序 段 及 归 并 结 果 段 同 时 存 放 在 内 存 中, 需 要 不 停 地 将 数 据 读 出 写 入 磁 盘, 这 将 耗 费 大 量 的 时 间 一 般 情 况 下 : 外 排 序 的 总 时 间 = 内 部 排 序 所 需 的 时 间 + 外 存 信 息 读 写 的 时 间 + 内 部 归 并 所 需 的 时 间 即, 其 中,r 是 初 始 归 并 段 个 数,t IS 是 对 每 一 个 初 始 归 并 段 进 行 内 部 排 序 的 时 间,d 是 访 问 外 存 块 的 次 数,t IO 是 每 一 个 块 的 存 取 时 间,S 是 归 并 趟 数,n 是 每 趟 参 加 二 路 归 并 的 记 录 个 数,t mg 是 每 作 一 次 内 部 归 并, 取 得 一 个 关 键 字 最 小 记 录 的 时 间 显 然 磁 盘 存 取 的 时 间 远 远 大 于 内 部 排 序 和 内 部 归 并 的 时 间, 因 此 要 提 高 外 排 序 的 速 度, 应 着 力 减 少 d, 即 I/O 次 数 由 于 外 存 上 信 息 的 读 / 写 是 以 物 理 块 为 单 位 的, 且 每 个 物 理 块 可 容 纳 250 个 记 录, 可 知 每 一 趟 归 并 需 进 行 8 次 读 和 8 次 写,3 趟 归 并 加 上 内 部 排 序 时 所 需 进 行 的 读 / 写 使 得 在 外 排 中 总 共 需 进 行 16 4=64 次 的 读 写 故, 上 述 二 路 平 衡 归 并 排 序 的 总 时 间 为 : 8 t IS +64 t IO t mg 对 于 上 例, 若 采 用 4 路 归 并 排 序 则 只 需 要 2 趟 归 并, 外 排 时 总 的 读 / 写 次 数 便 减 至 =48 因 此, 增 大 归 并 路 数, 可 减 少 归 并 趟 数, 从 而 减 少 总 的 磁 盘 I/O 次 数 图 6-3 四 路 平 衡 归 并 的 排 序 过 程 一 般 地, 对 r 个 初 始 归 并 段, 作 m 路 平 衡 归 并, 归 并 树 可 用 严 格 m 叉 树 ( 即 只 有 度 为 m 与

3 度 为 0 的 结 点 的 m 叉 树 ) 来 表 示 第 一 趟 可 将 r 个 初 始 归 并 段 归 并 为 趟 归 并 将 l 个 归 并 段 归 并 成 个 归 并 段, 以 后 每 一 个 归 并 段, 直 到 最 后 形 成 一 个 大 的 归 并 段 为 止 树 的 高 度 = = 归 并 趟 数 S 可 见, 只 要 增 大 归 并 路 数 m, 或 减 少 初 始 归 并 段 个 数 r, 都 能 减 少 归 并 趟 数 S, 以 减 少 读 写 磁 盘 次 数 d, 达 到 提 高 外 部 排 序 速 度 的 目 的 3. 多 路 平 衡 归 并 与 败 者 树 在 上 节 讨 论 过, 归 并 趟 数 S= 从 而 增 加 归 并 路 数 m 可 以 减 少 归 并 趟 数 S, 进 而 减 少 访 问 外 存 的 次 数 (I/O 次 数 ) 然 而, 当 增 加 归 并 路 数 m 时, 内 部 归 并 的 时 间 将 增 加 作 内 部 归 并 时, 在 m 个 元 素 中 选 择 关 键 字 最 小 的 记 录 需 要 比 较 m-1 次 每 趟 归 并 n 个 元 素 需 要 作 次 比 较,S 趟 归 并 总 共 需 要 的 比 较 次 数 为 : 其 中 的 在 初 始 归 并 段 个 数 r 与 记 录 个 数 n 一 定 时 是 常 数 而 随 m 增 长 而 增 长, 则 内 部 归 并 时 间 亦 随 m 的 增 长 而 增 长 这 将 抵 消 由 于 增 大 m 而 减 少 外 存 访 问 次 数 所 得 到 的 效 益 因 此, 不 能 使 用 普 通 的 内 部 归 并 排 序 算 法 为 了 使 内 部 归 并 不 受 m 的 增 大 的 影 响, 引 入 了 败 者 树 败 者 树 是 对 树 形 选 择 排 序 的 一 种 变 形, 可 以 看 作 一 棵 完 全 二 叉 树 每 个 叶 结 点 ( 外 结 点 ) 存 放 各 归 并 段 在 归 并 过 程 中 当 前 参 加 比 较 的 记 录, 内 部 结 点 用 来 记 忆 左 右 子 树 中 的 失 败 者, 而 让 胜 者 往 上 继 续 进 行 比 较, 一 直 到 根 结 点 如 果 比 较 两 个 数, 大 的 为 失 败 者 小 的 为 胜 利 者, 则 根 结 点 指 向 的 数 为 最 小 数 图 6-4 实 现 5- 路 归 并 的 败 者 树 如 图 6-4(a),b3 与 b4 比 较,b4 是 败 者, 因 此 将 段 号 4 写 入 父 结 点 ls4 b1 与 b2 比 较,b2 是 败 者, 将 段 号 2 写 入 ls3 b3 与 b4 的 胜 者 b3 与 b0 比 较,b0 是 败 者, 将 段 号 0 写 入 ls2 最 后 两 个 胜 者 b3 与 b1 比 较,b1 是 败 者, 段 号 写 入 ls1 而 将 胜 者 b3 的 段 号 写 入 ls0 此 时, 根 结 点 ls0 所 指 的 段 的 关 键 字 最 小 b3 中 的 6 输 出 后, 将 下 一 个 关 键 字 填 入 叶 结 点 b3, 继 续 比 较 因 为 m 路 归 并 的 败 者 树 深 度 为, 因 此 m 个 记 录 中 选 择 最 小 关 键 字, 最 多 需 要 次 比 较 所 以 总 的 比 较 次 数 为 : = = 可 见, 使 用 败 者 树 后, 内 部 归 并 的 比 较 次 数 与 归 并 路 数 无 关 了 因 此, 只 要 内 存 空 间 允 许, 增 大 归 并 路 数 m 将 有 效 地 减 少 归 并 树 的 高 度, 从 而 减 少 I/O 次 数 d, 提 高 外 部 排 序 的 速 度 值 得 说 明 的 是, 归 并 路 数 m 的 选 择 并 不 是 越 大 越 好 归 并 路 数 m 增 大 时, 相 应 地 需 要 增 加 输 入 缓 冲 区 个 数 如 果 可 供 使 用 的 内 存 空 间 不 变, 势 必 要 减 少 每 个 输 入 缓 冲 区 的 容 量, 使 得 内 外 存 交 换 数 据 的 次 数 增 大 当 m 值 过 大 时, 虽 然 归 并 趟 数 会 减 少, 但 读 写 外 存 的 次 数 仍 会 增 加 3. 置 换 - 选 择 排 序 ( 生 成 初 始 归 并 段 ) 上 节 讨 论 如 何 使 用 m 路 归 并 来 减 少 磁 盘 访 问 次 数, 从 而 加 快 外 排 序 的 速 度 从 第 一 节 的 讨

4 论 可 知, 减 少 初 始 归 并 段 个 数 r 也 可 以 减 少 归 并 趟 数 S 若 总 的 记 录 个 数 为 n, 每 个 归 并 段 的 长 度 为 l, 则 归 并 段 的 个 数 m= 如 果 采 用 前 面 介 绍 过 的 内 部 排 序 方 法, 将 得 到 长 度 都 相 同 的 初 始 归 并 段 因 此, 必 须 探 索 新 的 算 法 来 生 成 初 始 归 并 段, 这 就 是 本 节 要 介 绍 的 置 换 - 选 择 算 法 设 初 始 待 排 文 件 FI, 初 始 归 并 段 文 件 为 FO, 内 存 工 作 区 为 WA, 内 存 工 作 区 可 容 纳 w 个 记 录 置 换 - 选 择 算 法 的 步 骤 如 下 : 1) 从 待 排 文 件 FI 输 入 w 个 记 录 到 工 作 区 WA 2) 从 内 存 工 作 区 WA 中 选 出 其 中 关 键 字 取 最 小 值 的 记 录, 记 为 MINIMAX ( 以 后 再 选 出 关 键 字 比 它 大 的 记 录 归 入 本 归 并 段, 比 它 小 的 归 入 下 一 归 并 段 ) 3) 将 MINIMAX 记 录 输 出 到 FO 中 去 4) 若 FI 未 读 完, 则 从 FI 输 入 下 一 个 记 录 到 WA 中 5) 从 WA 中 所 有 关 键 字 比 MINIMAX 记 录 的 关 键 字 大 的 记 录 中 选 出 最 小 的 关 键 字 记 录, 作 为 新 的 MINIMAX 6) 重 复 3)~ 5), 直 到 在 WA 中 选 不 出 新 的 MINIMAX 记 录 为 止, 由 此 得 到 一 个 初 始 归 并 段, 输 出 一 个 归 并 段 的 结 束 标 志 到 FO 中 去 7) 重 复 2)~ 6), 直 到 WA 为 空 由 此 得 到 全 部 初 始 归 并 段 例 如, 设 待 排 文 件 FI={17,21,05,44,10,12,56,32,29}, 内 存 工 作 区 容 量 w 为 3 排 序 过 程 如 下 ( 红 色 标 记 的 为 每 次 的 MINIMAX): 表 6-1 置 换 - 选 择 排 序 过 程 示 例 输 出 文 件 FO 工 作 区 WA 输 入 文 件 FI ,21,05,44,10,12,56,32, ,10,12,56,32, ,12,56,32, ,56,32, ,32, , # # - - 上 述 算 法 中, 选 择 MINIMAX 记 录 的 过 程 的 需 利 用 败 者 树 来 实 现 4. 最 佳 归 并 树 文 件 经 过 置 换 - 选 择 排 序 之 后, 得 到 的 是 长 度 不 等 的 初 始 归 并 段 下 面 讨 论 如 何 组 织 初 始 归 并 段 的 归 并 顺 序, 使 I/O 访 问 次 数 最 少 m- 路 归 并 排 序 可 用 一 棵 m 叉 树 描 述 因 为 每 一 次 作 m 路 归 并 都 需 要 有 m 个 归 并 段 参 加, 因 此, 归 并 树 是 一 棵 只 有 度 为 0 和 度 为 m 的 结 点 的 严 格 m 叉 树 图 路 平 衡 归 并 的 归 并 树

5 设 由 置 换 - 选 择 得 到 9 个 初 始 归 并 段, 其 长 度 ( 记 录 数 ) 依 次 为 :9,30,12,18,3,17,2,6,24 现 作 3- 路 平 衡 归 并, 其 归 并 树 如 图 6-5 所 示 在 图 6-5 中, 各 叶 结 点 表 示 参 加 归 并 的 一 个 初 始 归 并 段, 叶 结 点 上 的 权 值 表 示 该 初 始 归 并 段 中 的 记 录 数, 根 结 点 表 示 最 终 生 成 的 归 并 段, 叶 结 点 到 根 结 点 的 路 径 长 度 表 示 在 归 并 过 程 中 的 归 并 趟 数, 各 非 叶 结 点 代 表 归 并 成 的 新 归 并 段, 则 归 并 树 的 带 权 路 径 长 度 WPL 即 为 归 并 过 程 中 的 总 读 记 录 数 因 而 在 归 并 过 程 中, 总 的 I/O 次 数 为 2 WPL=484 归 并 方 案 不 同, 所 得 归 并 树 亦 不 同, 树 的 带 权 路 径 长 度 ( 外 存 I/O 次 数 ) 亦 不 同 为 了 优 化 归 并 树 的 WPL, 可 将 第 4 章 Huffman 树 的 思 想 推 广 到 m 叉 树 的 情 形 在 归 并 树 中, 让 记 录 数 少 的 初 始 归 并 段 最 先 归 并, 记 录 数 多 的 初 始 归 并 段 最 晚 归 并, 就 可 以 建 立 总 的 I/O 次 数 达 到 最 少 的 最 佳 归 并 树 对 上 述 9 个 初 始 归 并 段 可 构 造 成 一 棵 如 图 6-6 所 示 的 归 并 树, 按 此 树 进 行 归 并, 仅 需 对 外 存 进 行 446 次 读 / 写, 这 棵 归 并 树 便 称 作 最 佳 归 并 树 图 路 平 衡 归 并 的 最 佳 归 并 树 图 6-6 的 Huffman 树 是 一 棵 严 格 3 叉 树 若 只 有 8 个 初 始 归 并 段, 设 上 例 中 少 了 一 个 长 度 为 30 的 归 并 段 如 果 在 设 计 归 并 方 案 时, 缺 额 的 归 并 段 留 着 最 后, 即 除 了 最 后 一 次 作 2- 路 归 并 外, 其 他 各 次 归 并 仍 都 是 3- 路 归 并, 此 归 并 方 案 的 外 存 读 / 写 次 数 为 386 显 然 不 是 最 佳 方 案 图 个 归 并 段 的 最 佳 归 并 树 正 确 的 做 法 是, 若 初 始 归 并 段 不 足 构 成 一 棵 严 格 m 叉 树 时, 需 添 加 长 度 为 0 的 虚 段, 按 照 Huffman 树 的 原 则, 权 为 0 的 叶 子 应 离 树 根 最 远 因 此, 最 佳 归 并 树 应 如 图 6-7 所 示 如 何 判 定 添 加 虚 段 的 数 目? 设 度 为 0 的 结 点 有 n 0 (=n) 个, 度 为 m 的 结 点 有 n m 个, 则 对 严 格 m 叉 树 有 n 0 =(m-1)n m +1, 由 此 可 以 得 出 n m =(n 0-1)/(m-1) 如 果 (n 0-1) % (m-1) = 0(% 为 取 余 运 算 ), 则 说 明 这 n 0 个 叶 结 点 ( 初 始 归 并 段 ) 正 好 可 以 构 造 m 叉 归 并 树 此 时, 内 结 点 有 n m 个 如 果 (n 0-1) % (m-1) = u 0, 则 说 明 对 于 这 n 0 个 叶 结 点, 其 中 有 u 个 多 余, 不 能 包 含 在 m 叉 归 并 树 中 为 构 造 包 含 所 有 n 0 个 初 始 归 并 段 的 m 叉 归 并 树, 应 在 原 有 n m 个 内 结 点 的 基 础 上 再 增 加 一 个 内 结 点 它 在 归 并 树 中 代 替 了 一 个 叶 结 点 位 置, 被 代 替 的 叶 结 点 加 上 刚 才 多 出 的 u 个 叶 结 点, 再 加 上 m-u-1 个 空 归 并 段, 就 可 以 建 立 归 并 树 以 图 6-7 为 例, 用 8 个 归 并 段 构 成 3 叉 树,(n 0-1) % (m-1)=(8-1) % (3-1)=1, 说 明 7 个 归 并 段 刚 好 可 以 构 成 一 个 严 格 3 叉 树 ( 假 设 把 以 5 为 根 的 树 看 做 一 个 叶 子 ) 为 此, 将 叶 子 5 变 成 一 个 内 结 点, 再 添 加 3-1-1=1 个 空 归 并 段, 就 可 以 构 成 一 个 严 格 m 叉 树

6 6.7.2 例 题 精 析 例 题 1 设 在 磁 盘 上 存 放 有 个 记 录, 作 5 路 平 衡 归 并 排 序, 内 存 工 作 区 能 容 纳 600 个 记 录, 为 把 所 有 记 录 排 好 序, 需 要 作 ( ) 趟 归 并 排 序 A. 3 B. 4 C. 5 D. 6 解 析 初 始 归 并 段 个 数 r= /600=625, 因 此, 归 并 趟 数 S= = =4 第 一 趟 把 625 个 归 并 段 归 并 成 625/5=125; 第 二 趟 把 125 个 归 并 段 归 并 成 125/5=25; 第 三 趟 归 并 成 25/5=5 个 归 并 段 ; 第 四 趟 归 并 成 5/5=1 个 归 并 段 本 题 答 案 为 B 例 题 2 设 有 5 个 初 始 归 并 段, 每 个 归 并 段 有 20 个 记 录, 采 用 5 路 平 衡 归 并 排 序, 若 不 采 用 败 者 树, 使 用 传 统 的 顺 序 选 出 最 小 记 录 ( 简 单 选 择 排 序 ) 的 方 法, 总 的 比 较 次 数 是 ( 1 ); 若 采 用 败 者 树 最 小 的 方 法, 总 的 比 较 次 数 是 ( 2 ) A. 20 B. 300 C. 396 D. 500 解 析 1 不 采 用 败 者 树 时, 在 5 个 记 录 中 选 出 最 小 的 需 要 作 4 次 比 较, 总 共 有 100 个 记 录, 需 要 作 99 次 选 择 最 小 记 录 的 操 作, 所 以 需 要 的 比 较 次 数 为 4 99=396 本 题 答 案 为 C 解 析 2 采 用 败 者 树 时,5- 路 归 并 意 味 着 败 者 树 的 外 结 点 有 5 个, 败 者 树 的 高 度 h= =3 每 次 在 参 加 比 较 的 记 录 中 选 择 一 个 关 键 字 最 小 的 记 录, 比 较 次 数 不 超 过 h, 总 共 100 个 记 录, 需 要 的 比 较 次 数 不 超 过 100x3=300 次 本 题 答 案 为 B 例 题 3 置 换 - 选 择 排 序 的 作 用 是 ( ) A. 置 换 - 选 择 排 序 用 于 生 成 外 排 序 的 初 始 归 并 段 B. 置 换 - 选 择 排 序 是 完 成 将 一 个 磁 盘 文 件 排 序 成 有 序 文 件 的 有 效 的 外 排 序 算 法 C. 置 换 - 选 择 排 序 生 成 的 初 始 归 并 段 的 长 度 平 均 是 内 存 工 作 区 的 2 倍 D. 置 换 - 选 择 排 序 是 对 外 排 序 中 输 入 / 归 并 / 输 出 的 并 行 处 理 解 析 置 换 - 选 择 排 序 是 外 排 序 中 生 成 初 始 归 并 段 的 方 法, 用 此 方 法 得 到 的 初 始 归 并 段 的 长 度 是 不 等 长 的, 其 长 度 平 均 是 传 统 等 长 初 始 归 并 段 的 2 倍, 从 而 使 得 初 始 归 并 段 数 减 少 到 原 来 的 近 二 分 之 一 但 是, 置 换 - 选 择 排 序 不 是 一 个 完 整 的 生 成 有 序 文 件 的 外 排 序 算 法 本 题 答 案 为 B 例 题 4 最 佳 归 并 树 在 外 排 序 中 的 作 用 是 ( ) A. 完 成 m 路 归 并 排 序 B. 设 计 m 路 归 并 排 序 的 优 化 方 案 C. 产 生 初 始 归 并 段 D. 与 竞 标 赛 树 的 作 用 类 似 解 析 最 佳 归 并 树 在 外 排 序 中 的 作 用 是 设 计 m 路 归 并 排 序 的 优 化 方 案, 仿 照 构 造 Huffman 树 的 方 法, 以 初 始 归 并 段 的 长 度 为 权 值, 构 造 具 有 最 小 带 权 路 径 长 度 的 m 叉 Huffman 树, 可 以 有 效 地 减 少 归 并 过 程 中 的 读 写 记 录 数, 加 快 外 排 序 的 速 度 本 题 答 案 为 B 例 题 5 在 下 列 关 于 外 排 序 过 程 输 入 / 输 出 缓 冲 区 作 用 的 叙 述 中 不 正 确 的 是 ( ) A. 暂 存 输 入 / 输 出 记 录 B. 内 部 归 并 的 工 作 区 C. 产 生 初 始 归 并 段 的 工 作 区 D. 传 送 用 户 界 面 的 消 息 解 析 在 外 排 序 过 程 中 输 入 / 输 出 缓 冲 区 就 是 排 序 的 内 存 工 作 区, 例 如 作 m 路 平 衡 归 并 就 需 要 m 个 输 入 缓 冲 区 和 1 个 输 出 缓 冲 区, 用 以 存 放 参 加 归 并 的 和 归 并 完 成 的 记 录 在 产 生 初 始 归 并 段 时 也 可 用 作 内 排 序 的 工 作 区 它 没 有 传 送 用 户 界 面 的 消 息 的 任 务 本 题 答 案 为 D 例 题 6 在 作 m 路 平 衡 归 并 排 序 的 过 程 中, 为 实 现 输 入 / 内 部 归 并 / 输 出 的 并 行 处 理, 需 要 设 置 ( 1 ) 个 输 入 缓 冲 区 和 ( 2 ) 个 输 出 缓 冲 区 1)A. 2 B. m C. 2m-1 D. 2m 2)A. 2 B. m C. 2m-1 D. 2m 解 析 在 作 k 路 平 衡 归 并 排 序 的 过 程 中, 为 实 现 输 入 / 内 部 归 并 / 输 出 的 并 行 处 理, 需 要 设 置 2m 个 输 入 缓 冲 区 和 2 个 输 出 缓 冲 区, 以 便 在 执 行 内 部 归 并 时, 能 同 时 进 行 输 入 / 输 出 操 作 本 题 答 案 依 次 为 D A 例 题 7 多 路 平 衡 归 并 排 序 是 外 排 序 的 主 要 方 法, 试 问 多 路 平 衡 归 并 排 序 包 括 哪 两 个 相 对 独 立

7 的 阶 段? 每 个 阶 段 完 成 何 种 工 作? 解 析 多 路 平 衡 归 并 排 序 由 两 个 相 对 独 立 的 阶 段 组 成 : 生 成 初 始 归 并 段 和 多 趟 归 并 排 序 生 成 初 始 归 并 段 阶 段 根 据 内 存 工 作 区 的 大 小, 将 有 n 个 记 录 的 磁 盘 文 件 分 批 输 入 内 存, 采 用 有 效 的 内 排 序 方 法 分 别 进 行 排 序, 生 成 若 干 个 有 序 的 子 文 件, 即 初 始 归 并 段 多 趟 归 并 排 序 阶 段 采 用 多 路 归 并 方 法 将 这 些 归 并 段 逐 趟 归 并, 最 后 归 并 成 一 个 有 序 文 件 例 题 8 如 果 某 个 文 件 经 内 排 序 得 到 80 个 初 始 归 并 段, 试 问 : 1) 若 使 用 多 路 平 衡 归 并 执 行 3 趟 完 成 排 序, 那 么 应 取 得 归 并 路 数 至 少 应 为 多 少? 2) 如 果 操 作 系 统 要 求 一 个 程 序 同 时 可 用 的 输 入 / 输 出 文 件 的 总 数 不 超 过 15 个, 则 按 多 路 归 并 至 少 需 要 几 趟 可 以 完 成 排 序? 如 果 限 定 趟 数, 可 取 的 最 低 路 数 是 多 少? 解 析 1) 设 归 并 路 数 为 m, 初 始 归 并 段 个 数 r=80, 根 据 归 并 趟 数 计 算 公 式 S= = =3, 得 :log m 80 3,m 3 80 由 此 解 得 m 5, 即 应 取 的 归 并 路 数 至 少 为 5 2) 设 多 路 归 并 的 归 并 路 数 为 m, 需 要 m 个 输 入 缓 冲 区 和 1 个 输 出 缓 冲 区 1 个 缓 冲 区 对 应 一 个 文 件, 有 m+1=15, 因 此 m=14, 可 作 14 路 归 并 由 S= = =2 即 至 少 需 要 2 趟 归 并 可 完 成 排 序 若 限 定 趟 数 为 2, 由 S= 在 2 趟 内 完 成 排 序, 进 行 9 路 归 并 排 序 即 可 =2, 有 80 m 2, 可 取 的 最 低 路 数 为 9 即 要 例 题 9 假 设 文 件 由 个 记 录, 在 磁 盘 上 每 个 块 可 放 75 个 记 录 计 算 机 中 用 于 排 序 的 内 存 区 可 容 纳 450 个 记 录 试 问 : 1) 可 以 建 立 多 少 个 初 始 归 并 段? 每 个 初 始 归 并 段 有 多 少 记 录? 存 放 于 多 少 个 块 中? 2) 应 采 用 几 路 归 并? 请 写 出 归 并 过 程 及 每 趟 需 要 读 写 磁 盘 的 块 数 解 析 1) 文 件 由 个 记 录, 用 于 排 序 的 内 存 区 可 容 纳 450 个 记 录, 可 建 立 的 初 始 归 并 段 有 4 500/450=10 个 每 个 初 始 归 并 段 中 有 450 个 记 录, 存 于 450/75=6 个 块 中 2) 内 存 区 可 容 纳 6 个 块, 可 建 立 6 个 缓 冲 区, 其 中 5 个 缓 冲 区 用 于 输 入,1 个 缓 冲 区 用 于 输 出, 因 此, 可 采 用 5 路 归 并 归 并 过 程 如 图 6-8 所 示 图 路 归 并 的 归 并 过 程 共 作 了 2 趟 归 并, 每 趟 需 要 读 60 块 写 60 个 块 图 6-9 败 者 树 的 构 造 过 程

8 例 题 10 设 初 始 归 并 段 为 (10,15,31),(9,20),(22,34,37),(6,15,42),(12,37),(84,95) 试 利 用 败 者 树 进 行 m 路 归 并, 手 工 执 行 选 择 最 小 的 5 个 关 键 字 的 过 程 解 析 作 6 路 归 并 排 序, 选 择 最 小 的 5 个 关 键 字 的 败 者 树 如 图 6-9 所 示 ( 上 一 页 ) 例 题 11 给 出 12 个 初 始 归 并 段, 其 长 度 分 别 为 30,44,8,6,3,20,60,18,9,62,68,85 现 要 作 4 路 外 归 并 排 序, 试 画 出 表 示 归 并 过 程 的 最 佳 归 并 树, 并 计 算 该 归 并 树 的 带 权 路 径 长 度 WPL 解 析 设 初 始 归 并 段 个 数 n=12, 外 归 并 路 数 k=4, 计 算 (n-1) % (k-1) = 11 % 3 = 2 0, 说 明 不 能 做 完 全 的 4 路 归 并, 因 为 多 出 了 2 个 初 始 归 并 段, 必 须 添 加 k-2-1=1 个 长 度 为 0 的 空 归 并 段, 才 能 构 成 严 格 的 4 路 归 并 树, 即 每 次 归 并 都 有 k 个 归 并 段 参 加 归 并 此 时, 归 并 树 的 内 结 点 应 有 (n-1+1)/(k-1) = 12/3 = 4 个, 如 图 6-10 所 示 图 6-10 归 并 树 的 构 造 过 程 WPL=(3+6+8) 3+( ) 2+(68+85) 1= =690 例 题 12 已 知 有 31 个 长 度 不 等 的 初 始 归 并 段, 其 中 8 段 长 度 为 2,8 段 长 度 为 3,7 段 长 度 为 5,5 段 长 度 为 12,3 段 长 度 为 20( 单 位 均 为 物 理 块 ) 请 为 此 设 计 一 个 最 佳 5 路 归 并 方 案, 并 计 算 总 的 ( 归 并 所 需 的 ) 读 / 写 外 存 的 次 数 解 析 首 先 计 算 是 否 需 要 补 充 空 归 并 段 因 为 (31-1) % (5-1) = 2 0, 需 补 充 5-2-1=2 个 空 归 并 段 然 后 仿 照 Huffman 树 构 成 5 路 归 并 树, 如 图 6-11 所 示 图 6-11 构 造 出 来 的 最 佳 归 并 树 如 图 6-12 所 示 构 造 归 并 段 图 6-12 最 终 的 归 并 树 总 的 读 外 存 的 次 数 等 于 最 佳 归 并 树 的 带 权 路 径 长 度 WPL WPL=( ) 3+( ) =400 读 / 写 外 存 的 次 数 为 400 2=800

9 第 二 部 分 : 计 算 机 组 成 原 理 第 2 章 数 据 的 表 示 和 运 算 1 删 除 了 :( 三 )1. 浮 点 数 的 表 示 范 围 第 3 章 存 储 器 层 次 结 构 2 ( 三 )1. SRAM 存 储 器 的 工 作 原 理 2. DRAM 存 储 器 的 工 作 原 理 改 成 了 :1. SRAM 存 储 器 2. DRAM 存 储 器 ( 属 于 换 汤 不 换 药 ) 3 增 加 了 :Flash 存 储 器 ( 仅 考 查 基 本 概 念 ) 单 科 指 导 书 上 已 有, 见 P83 (4) 闪 速 存 储 器 (Flash Memory) Flash Memory 是 在 EPROM 与 E 2 PROM 基 础 上 发 展 起 来 的, 其 主 要 特 点 是 既 可 在 不 加 电 的 情 况 下 长 期 保 存 信 息, 又 能 在 线 进 行 快 速 擦 除 与 重 写 闪 速 存 储 器 既 有 EPROM 的 价 格 便 宜 集 成 度 高 的 优 点, 又 有 E 2 PROM 电 可 擦 除 重 写 的 特 点, 且 擦 除 重 写 的 速 度 快 大 纲 解 析 上 的 内 容 : 原 理 : 主 要 是 浮 栅 做 得 更 薄 除 了 也 用 电 擦 除 外, 在 系 统 编 程 上 能 力 更 强, 并 具 有 软 件 和 硬 件 保 护 能 力, 可 按 字 节 (byte), 区 块 (sector) 或 页 面 (page) 进 行 擦 除 和 编 程 操 作, 内 部 可 以 自 行 产 生 编 程 电 压 (Vpp), 所 以 只 用 单 电 源 Vcc 供 电 例 题 U 盘 属 于 ( ) 类 型 的 存 储 器 A. 高 速 缓 存 B. 主 存 C. 只 读 存 储 器 D. 随 机 存 取 存 储 器 解 析 U 盘 采 用 Flash Memory 技 术, 属 于 ROM 由 于 擦 写 速 度 和 性 价 比 均 很 可 观, 故 而 其 常 常 可 用 做 辅 存 注 意 随 机 存 取 是 相 对 磁 带 等 存 储 器 无 法 读 取 任 意 位 置 而 言 的 随 机 存 取 存 储 器 可 随 机 存 储, 但 能 随 机 存 储 的 不 一 定 是 随 机 存 取 存 储 器 本 题 答 案 为 C 4 删 除 了 :( 六 )1. 程 序 访 问 的 局 部 性 原 理 程 序 访 问 的 局 部 性 原 理, 也 属 于 Cache 的 基 本 原 理, 因 此 这 里 删 除 也 等 于 没 删 除! 第 5 章 中 央 处 理 器 5 增 加 了 : 指 令 流 水 线 的 基 本 实 现 这 部 分 内 容 王 道 书 已 基 本 囊 括 单 科 指 导 书,P175-P179, 这 里 再 补 充 一 点 点 (2) 指 令 流 水 线 的 基 本 实 现 一 条 指 令 的 执 行 过 程 可 以 分 成 多 个 阶 段 ( 或 过 程 ), 根 据 计 算 机 的 不 同 具 体 的 分 法 也 不 同 图 中 把 一 条 指 令 的 执 行 过 程 分 为 如 下 3 个 阶 段 : 图 一 条 指 令 执 行 过 程 的 划 分 取 指 : 根 据 PC 内 容 访 问 主 存 储 器, 取 出 一 条 指 令 送 到 IR 中 分 析 : 对 指 令 操 作 码 进 行 译 码, 按 照 给 定 的 寻 址 方 式 和 地 址 字 段 中 的 内 容 形 成 操 作 数 的 有 效 地 址 EA, 并 从 有 效 地 址 EA 中 取 出 操 作 数 执 行 : 根 据 操 作 码 字 段, 完 成 指 令 规 定 的 功 能, 即 把 运 算 结 果 写 到 通 用 寄 存 器 或 主 存 中 当 多 条 指 令 在 处 理 器 中 执 行 时, 可 以 采 用 以 下 3 种 方 式 : 1. 顺 序 执 行 方 式

10 指 令 按 顺 序 执 行, 前 一 条 指 令 执 行 完 后, 才 启 动 下 一 条 指 令, 如 图 5.5.2(a) 设 取 指 分 析 执 行 3 个 阶 段 的 时 间 都 相 等, 用 t 表 示, 则 顺 序 执 行 n 条 指 令 所 用 时 间 T 为 : T=3nt 传 统 冯 诺 依 曼 机 采 用 顺 序 执 行 方 式, 又 称 串 行 执 行 方 式 其 优 点 是 控 制 简 单, 硬 件 代 价 小 其 缺 点 是 执 行 指 令 的 速 度 较 慢, 在 任 何 时 刻, 处 理 机 中 只 有 一 条 指 令 在 执 行, 各 功 能 部 件 的 利 用 率 很 低 如 取 指 时, 内 存 是 忙 碌 的, 而 指 令 执 行 部 件 是 空 闲 的 图 指 令 的 三 种 执 行 方 式 2. 一 次 重 叠 执 行 方 式 这 种 方 式 把 第 k 条 指 令 的 执 行 阶 段 和 第 k+1 条 指 令 的 取 指 阶 段 同 时 进 行, 如 图 5.5.2(b) 所 示 采 用 此 种 方 式 时, 执 行 n 条 指 令 所 用 的 时 间 为 : T=(1+2n)t 采 用 一 次 重 叠 执 行 方 式 的 优 点 是 程 序 的 执 行 时 间 缩 短 了 1/3, 各 功 能 部 件 的 利 用 率 明 显 提 高 但 为 此 需 要 付 出 硬 件 上 较 大 开 销 的 代 价, 控 制 过 程 也 比 顺 序 执 行 复 杂 了 3. 二 次 重 叠 执 行 方 式 为 了 进 一 步 提 高 指 令 的 执 行 速 度, 可 以 把 取 k+1 条 指 令 提 前 到 分 析 第 k 条 指 令 的 期 间 完 成, 而 将 分 析 第 k+1 条 指 令 与 执 行 第 k 条 指 令 同 时 进 行, 如 图 5.5.2(c) 所 示 采 用 此 种 方 式 时, 执 行 n 条 指 令 所 用 的 时 间 为 : T=(2+n)t 与 顺 序 执 行 方 式 相 比, 采 用 二 次 重 叠 执 行 方 式 能 够 使 指 令 的 执 行 时 间 缩 短 近 2/3 这 是 一 种 理 想 的 指 令 执 行 方 式, 在 正 常 情 况 下, 处 理 机 中 同 时 有 3 条 指 令 在 执 行 若 每 条 指 令 需 要 通 过 4 个 或 5 个 执 行 步 骤 完 成, 则 可 以 采 取 3 次 或 4 次 重 叠 执 行 方 式 例 题 在 告 诉 计 算 机 中, 广 泛 采 用 指 令 流 水 线 技 术 在 指 令 流 水 线 技 术 中, 可 以 将 指 令 的 执 行 分 为 取 指 令 分 析 指 令 和 执 行 指 令 三 个 阶 段 不 同 指 令 的 不 同 阶 段 可 以 ( 1 ) 执 行, 各 个 阶 段 的 执 行 时 间 最 好 ( 2 ), 否 则 在 流 水 闲 运 行 时, 每 个 阶 段 的 执 行 时 间 应 取 ( 3 ) 1) A. 顺 序 B. 重 叠 C. 循 环 D. 并 行 2) A. 是 1 个 时 钟 中 期 B. 是 2 个 时 钟 周 期 C. 相 等 D. 不 等 3) A. 3 个 中 兴 阶 段 的 时 间 之 和 B. 3 个 执 行 阶 段 时 间 的 平 均 值 C. 3 个 执 行 阶 段 时 间 的 最 小 值 D. 3 个 执 行 阶 段 时 间 的 最 大 值 解 析 ( 1)D (2)C (3)D 6 增 加 了 : 多 核 处 理 器 的 基 本 概 念 5.6 多 核 处 理 器 的 基 本 概 念 (1) 多 核 处 理 器 的 发 展 简 述

11 在 一 块 芯 片 上 集 成 的 晶 体 管 数 目 越 多, 意 味 着 运 算 速 度 即 主 频 就 更 快 显 然, 当 晶 体 管 数 目 增 加 导 致 功 耗 增 长 超 过 性 能 增 长 速 度 后, 处 理 器 的 可 靠 性 就 会 受 到 致 命 的 影 响, 而 且 速 度 也 会 遇 到 自 己 的 极 限 这 也 就 是 单 纯 的 主 频 提 升, 已 经 无 法 明 显 提 升 系 统 整 体 性 能 就 连 戈 登 摩 尔 本 人 似 乎 也 依 稀 看 到 了 主 频 为 王 这 条 路 的 尽 头 2005 年 4 月, 他 曾 公 开 表 示, 引 领 半 导 体 市 场 接 近 40 年 的 摩 尔 定 律, 在 未 来 10 年 至 20 年 内 可 能 失 效 2006 年 7 月, 英 特 尔 基 于 酷 睿 (Core) 架 构 的 处 理 器 正 式 发 布, 与 上 一 代 台 式 机 处 理 器 相 比,Core 双 核 处 理 器 在 性 能 方 面 提 高 40%, 功 耗 反 而 降 低 40% (2) 多 核 处 理 器 的 基 本 概 念 多 核 处 理 器 一 般 指 单 芯 片 多 处 理 器 (chip multi-processor, CMP), 即 在 一 个 芯 片 内 集 成 两 个 或 多 个 完 整 且 并 行 工 作 的 处 理 器 核 心 而 构 成 的 处 理 器 核 心 通 常 包 含 指 令 部 件 算 术 / 逻 辑 部 件 寄 存 器 堆 和 一 级 或 二 级 缓 存 的 处 理 单 元, 这 些 核 心 通 过 某 种 方 式 互 联 后, 能 够 相 互 交 换 数 据, 对 外 呈 现 为 一 个 统 一 的 多 核 处 理 器 图 简 单 的 多 核 处 理 器 模 型 图 如 图 所 示 为 简 单 的 多 核 处 理 器 模 型 所 有 CPU 共 享 一 个 统 一 的 地 址 空 间 : 有 单 独 的 L1 Cache; 采 用 多 级 Cache 结 构 ( 共 享 L2 和 L3 级 ); 通 常 采 用 总 线 作 为 互 连 结 构 ; 使 用 Cache 一 致 性 协 议 维 护 数 据 一 致 性 ; 采 用 多 线 程 或 多 进 程 作 为 并 行 软 件 设 计 方 法 (3) 多 核 处 理 器 的 主 要 技 术 和 挑 战 1. 维 持 Cache 一 致 性 技 术 由 于 多 个 内 核 通 过 共 享 Cache 实 现 信 息 交 换 和 同 步 的 同 时, 带 来 了 Cache 在 不 同 核 间 数 据 前 后 不 一 致 的 问 题, 解 决 此 问 题 的 技 术 称 为 维 持 Cache 一 致 性 技 术 目 前 的 CMP 系 统 大 多 采 用 基 于 总 线 的 侦 听 协 议 2. 核 间 通 信 技 术 多 核 处 理 器 内 各 处 理 器 并 行 执 行 程 序 时, 核 间 需 要 进 行 数 据 共 享 与 同 步, 其 硬 件 结 构 必 须 支 持 高 效 的 核 间 通 信, 此 即 核 间 通 信 技 术 目 前 比 较 主 流 的 片 上 高 效 通 信 机 制 有 两 种, 一 种 是 基 于 总 线 共 享 的 Cache 结 构, 一 种 是 基 于 片 上 的 互 连 结 构 3. 对 软 件 设 计 的 挑 战 在 单 个 芯 片 上 集 成 了 多 个 处 理 器 核 心, 为 更 好 地 发 挥 它 们 的 性 能 优 势, 对 软 件 设 计 来 说 需 要 程 序 的 并 行 化, 包 括 编 译 技 术 和 任 务 调 度 等 对 多 核 的 支 持, 因 此, 这 是 多 核 时 代 对 软 件 设 计 的 挑 战 例 题 关 于 多 核 处 理 器, 下 面 叙 述 正 确 的 是 ( ) A. 一 般 指 多 芯 片 单 处 理 器 B. 对 外 呈 现 为 一 个 统 一 工 作 的 多 核 处 理 器 C. 维 持 核 间 通 信 技 术 为 主 要 技 术 之 一 D. 核 间 Cache 通 信 技 术 为 主 要 技 术 之 一 解 析 A 选 项 显 然 错 误,CD 两 项 的 表 述 有 误 本 题 答 案 为 B 第 7 章 输 入 输 出 系 统 7 增 加 了 :I/O 地 址 空 间 及 其 编 码

12 这 部 分 内 容 即 I/O 的 编 址 方 式 (I/O 端 口 及 其 编 制 ), 见 单 科 指 导 书 P225, 大 纲 解 析 上 亦 没 有 新 增 任 何 内 容, 考 研 大 纲 的 编 者 估 计 有 点 NC 第 三 部 分 : 操 作 系 统 考 查 目 标 增 加 说 明 : 能 利 用 C 语 言 描 述 相 关 算 法 单 科 指 导 书 上 的 代 码 均 采 用 C 语 言 描 述 ( 有 些 教 材 可 能 采 用 Pascal), 因 此 不 必 纠 结! 第 1 章 操 作 系 统 概 述 1 运 行 环 境 扩 充 为 : 核 心 态 与 用 户 态 ; 中 断 异 常 ; 系 统 调 用 这 些 内 容, 单 科 指 导 书 上 均 有, 而 且 讲 解 的 比 较 详 细 核 心 态 与 用 户 态 见 :P11 系 统 调 用 见 :P4 程 序 接 口 部 分 中 断 异 常 见 :P12 2 增 加 了 : 操 作 系 统 体 系 结 构 单 科 指 导 全 书 上 有,P4 4. 操 作 系 统 的 结 构 大 纲 解 析 上 的 内 容 : 操 作 系 统 的 体 系 结 构 是 一 个 开 放 的 问 题 正 如 上 文 所 述, 操 作 系 统 在 核 心 态 为 应 用 程 序 提 供 公 共 的 服 务, 那 么 操 作 系 统 在 核 心 态 应 该 提 供 什 么 服 务 怎 样 提 供 服 务? 有 关 这 个 问 题 的 回 答 形 成 了 两 个 主 要 的 体 系 结 构 : 大 内 核 和 微 内 核 大 内 核 系 统 将 操 作 系 统 的 主 要 功 能 模 块 都 作 为 一 个 紧 密 联 系 的 整 体 运 行 在 核 心 态, 从 而 为 应 用 提 供 高 性 能 的 系 统 服 务 因 为 各 管 理 模 块 之 间 共 享 信 息, 能 有 效 利 用 相 互 之 间 的 有 效 特 性, 所 以 具 有 无 可 比 拟 的 性 能 优 势 但 随 着 计 算 机 体 系 结 构 和 应 用 需 求 的 不 断 发 展, 需 要 操 作 系 统 提 供 的 服 务 越 来 越 多, 而 且 接 口 形 式 越 来 越 复 杂, 操 作 系 统 的 设 计 规 模 也 急 剧 增 长, 操 作 系 统 也 面 临 着 软 件 危 机 困 境 为 此, 操 作 系 统 设 计 人 员 试 图 按 照 复 杂 性 时 间 常 数 抽 象 级 别 等 因 素, 将 操 作 系 统 内 核 分 成 基 本 进 程 管 理 虚 存 I/O 与 设 备 管 理 IPC 文 件 系 统 等 几 个 层 次, 继 而 定 义 层 次 之 间 的 服 务 结 构, 提 高 操 作 系 统 内 核 设 计 上 的 模 块 化 但 是 由 于 层 次 之 间 的 交 互 关 系 错 综 复 杂, 定 义 清 晰 的 层 次 间 接 口 非 常 困 难, 复 杂 的 交 互 关 系 也 使 得 层 次 之 间 的 界 限 极 其 模 糊 为 了 解 决 操 作 系 统 内 核 代 码 难 以 维 护 的 问 题, 有 人 就 提 出 了 微 内 核 的 体 系 结 构 它 讲 内 核 中 最 基 本 的 功 能 ( 如 进 程 管 理 虚 存 管 理 等 ) 保 留 在 内 核, 而 将 那 些 不 需 要 在 核 心 态 执 行 的 部 分 移 到 用 户 态 执 行, 从 而 降 低 了 内 核 的 设 计 复 杂 性 而 那 些 移 出 内 核 的 操 作 系 统 代 码 根 据 分 层 的 原 则 被 划 分 成 若 干 服 务 程 序, 它 们 的 执 行 相 互 独 立, 交 互 则 都 借 助 于 微 内 核 进 行 通 信 微 内 核 结 构 有 效 地 分 离 了 内 核 与 服 务 服 务 于 服 务, 使 得 它 们 之 间 的 接 口 相 对 更 加 明 晰, 维 护 的 代 价 大 大 降 低, 各 部 分 可 以 独 立 地 优 化 和 演 进, 从 而 保 证 了 操 作 系 统 的 可 靠 性 微 内 核 系 统 的 最 大 问 题 是 性 能 问 题, 因 为 需 要 频 繁 地 在 管 态 和 目 态 之 间 进 行 切 换, 操 作 系 统 的 执 行 开 销 相 对 偏 大 因 此 有 的 操 作 系 统 将 那 些 频 繁 使 用 的 系 统 服 务 又 移 回 内 核, 从 而 保 证 系 统 性 能 但 是 有 相 当 多 的 实 验 证 据 表 明, 体 系 结 构 不 甚 引 起 性 能 下 降 的 主 要 因 素, 体 系 结 构 带 来 的 性 能 提 高 足 以 弥 补 切 换 开 销 带 来 的 缺 陷 为 了 减 少 切 换 开 销, 也 有 人 提 出 了 将 系 统 服 务 作 为 运 行 库 链 接 到 用 户 程 序 的 一 种 解 决 方 案, 这 样 的 体 系 结 构 称 为 库 操 作 系 统 ( 或 者 垂 直 结 构 微 内 核 操 作 系 统 ) 第 3 章 内 存 管 理

13 3 删 除 了 :( 二 )6. 请 求 分 段 管 理 方 式 4 删 除 了 :( 二 )7. 请 求 段 页 式 管 理 方 式 第 5 章 输 入 输 出 (I/O) 管 理 5 删 除 了 :( 一 )1. I/O 设 备 6 删 除 了 :( 一 )2. I/O 管 理 目 标 7 删 除 了 :( 一 )3. I/O 管 理 功 能 8 删 除 了 :( 一 )4. I/O 应 用 接 口 9 删 除 了 :( 二 )5. 出 错 处 理 10 增 加 了 :I/O 软 件 的 层 次 结 构 单 科 指 导 全 书 已 有 本 部 分 内 容, 见 P242,1. I/O 层 次 结 构