资源描述
福 州 大 学 数 计 学 院主 讲 教 师 : 单 红计 算 机 操 作 系 统 第 三 章 处 理 机 调 度 调 度 策 略 考 虑 ： 周 转 时 间 吞 吐 率 相 应 时 间 设 备 利 用 率研 究 的 内 容 有 ： 作 业 与 进 程 的 关 系 作 业 调 度 策 略 与 算 法 进 程 调 度 策 略 与 算 法 几 种 调 度 策 略 的 评 价 本 章 主 要 讨 论 处 理 机 分 配 问 题 1.作 业 的 状 态 及 其 转 换 提 交 状 态 ： 一 个 作 业 北 提 交 给 机 房 后 或 用 户 通 过 终 端 键盘 想 计 算 机 键 入 其 作 业 时 所 处 的 状 态 后 备 状 态 ： 作 业 的 全 部 信 息 都 已 通 过 输 入 机 输 入 ， 并 由操 作 系 统 将 其 存 在 磁 盘 的 某 些 分 区 （ 存 放 作 业 的 输 入 井 ）中 等 待 运 行 。 运 行 状 态 ： 作 业 一 旦 被 作 用 调 度 程 序 选 中 而 被 送 入 主 存中 投 入 运 行 。 完 成 状 态 ： 作 业 完 成 其 全 部 运 行 ， 释 放 出 其 所 占 用 的 全部 资 源 。 准 备 退 出 系 统 时 的 作 业 。 3.1 分 级 调 度 作 业 状 态 及 其 转 换 图 spooling系 统提 交 收 容 外 存就 绪 等 待 运 行就 绪 等 待交 换 调 度 完成 作 业 调 度 进 程 调 度 高 级 调 度 （ 作 业 调 度 、 宏 观 调 度 ） 按 一 定 原 则 对 外存 输 入 井 上 的 作 业 进 行 调 度 ， 并 建 立 进 程 PCB。 它 决 定 允许 哪 些 作 业 竞 争 系 统 资 源 。 由 于 这 种 调 度 决 定 哪 些 作 业可 以 进 入 系 统 ， 所 以 也 称 收 容 调 度 。 作 业 一 旦 被 系 统 收容 ， 就 便 成 进 程 或 进 程 组 。 中 级 调 度 （ 交 换 调 度 ） 它 决 定 允 许 哪 些 进 程 竞 争 处理 机 。 中 级 调 度 通 过 使 进 程 临 时 挂 起 和 激 活 的 方 法 对 系统 负 载 波 动 作 出 反 映 ， 以 便 获 得 平 稳 的 系 统 操 作 和 实 现较 好 的 系 统 综 合 性 能 目 标 ， 中 级 调 度 的 作 用 使 作 为 作 业进 入 系 统 和 将 中 央 处 理 机 分 配 给 这 些 作 业 二 者 之 间 的 一个 缓 冲 。 2 调 度 的 层 次 低 级 调 度 （ 进 程 调 度 ） 它 决 定 了 存 在 就 绪进 程 时 ， 哪 一 个 就 绪 进 程 将 分 配 到 中 央 处 理 机， 并 且 把 中 央 处 理 机 实 际 分 配 给 这 个 进 程 （ 即低 级 调 度 是 将 处 理 机 分 配 给 进 程 ） 。 低 级 调 度是 由 每 秒 可 操 作 许 多 次 的 处 理 机 调 度 程 序 执 行， 处 理 机 调 度 程 序 应 常 驻 内 存 。 2 调 度 的 层 次 作 业 是 用 户 向 计 算 机 提 交 任 务 的 任 务 实 体。 进 程 是 计 算 机 为 了 完 成 用 户 任 务 实 体 而 设置 的 执 行 实 体 。 显 然 ， 计 算 机 要 完 成 一 个 任 务 实 体 ， 必 须要 有 一 个 以 上 的 执 行 实 体 ， 一 个 作 业 总 是 由 一个 以 上 的 多 个 进 程 组 成 。 3 作 业 与 进 程 的 关 系 作 业 调 度 的 功 能 ： 按 某 种 算 法 从 后 备 队 列 中 挑 选一 个 或 一 批 作 业 调 入 内 存 ， 并 创 建 PCB.1 后 备 作 业 队 列 与 作 业 控 制 块 系 统 中 有 若 干 作 业 在 输 入 井 中 ， 为 了 管 理 和调 度 作 业 ， 就 必 须 记 录 已 进 入 系 统 的 各 作 业 的 情况 ， 系 统 为 每 个 作 业 设 置 了 一 个 作 业 控 制 块 （JCB） 。内 容 ： 作 业 名 、 作 业 状 态 、 作 业 调 度 ， 以 及 资 源申 请 和 一 些 控 制 信 息 。 3.2 作 业 的 调 度 作 业 控 制 块 JCB 作 业 名 作 业 类 型 资 源 要 求 资 源 使 用 情 况 优 先 级 当 前 状 态 其 它 作 业 调 度 按 照 某 种 调 度 算 法 从 后 备 作 业 队列 中 选 取 作 业 ， 使 其 进 入 内 存 运 行 。 作 业 调 度 程 序 的 主 要 功 能 是 审 查 系 统 是 否能 满 足 用 户 作 业 的 资 源 要 求 以 及 按 照 一 定 的 算法 选 取 作 业 。 1 作 业 调 度 及 其 功 能 按 照 某 种 调 度 算 法 从 后 备 作 业 队 列 中选 取 作 业 。 为 被 选 取 的 作 业 分 配 内 存 和 外 设 资 源（ 当 系 统 为 动 态 分 配 外 设 时 ， 作 业 所 申请 的 外 设 只 作 为 调 度 的 参 考 因 素 ） 。 因此 要 用 到 内 存 分 配 程 序 和 外 设 分 配 程 序。 为 选 中 的 作 业 建 立 相 应 的 进 程 。 为 作 业 开 始 运 行 做 好 一 切 准 备 工 作 。如 构 造 和 读 写 作 业 运 行 时 所 需 要 的 有 关表 格 及 建 立 负 责 其 运 行 控 制 的 作 业 运 行控 制 程 序 。 在 作 用 运 行 完 毕 或 运 行 过 程 中 因 某 种原 因 需 要 撤 离 时 ， 作 业 调 度 程 序 还 有 完 成 作 业 的 善 后 处 理 工 作 ， 如 收 回 分 配 给他 的 全 部 资 源 ， 它 们 将 从 系 统 中 抹 去 2.作 业 调 度 应 完 成 如 下 几 方 面 的 工 作 1) 调 度 目 标 对 所 有 作 业 应 该 是 公 平 合 理 应 使 设 备 有 高 的 利 用 率 每 天 执 行 尽 可 能 多 的 作 业 有 快 的 响 应 时 间3.作 业 调 度 目 标 与 性 能 衡 量 2） 作 业 调 度 的 转 换 过 程 （ 1） 作 业 从 后 备 状 态 到 执 行 状 态 P85(a)框 图 （ 2） 作 业 从 执 行 状 态 到 完 成 状 态 P85(b)框 图3.作 业 调 度 目 标 与 性 能 衡 量 后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口作 业 从 后 备 状 态 到 执 行 状 态 撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业作 业 从 执 行 状 态 到 完 成 状 态 3） .衡 量 一 个 作 业 调 度 算 法 是 否 满 足 系 统 设 计 的 要 求 给 出 两 个 常 用 的 评 价 在 批 处 理 系 统 中 对 作 业 调 度 算 法优 劣 的 性 能 量 度1 周 转 时 间 ：作 业 i从 提 交 时 刻 tsi到 完 成 时 刻 tei称 为 作 业 的 周 转 时 间 。Ti = Tei - Tsi 完 成 提 交3.作 业 调 度 目 标 与 性 能 衡 量 作 业 平 均 周 转 时 间 为 （ 有 n个 作 业 ， n=1) nT=1/n Ti i=1一 个 作 业 的 周 转 时 间 说 明 了 该 作 业 在 系 统 内 停 留 的 时 间包 含 两 部 分 ： 一 是 等 待 时 间 ； 二 为 执 行 时 间Ti = Twi - Tri (停 留 时 间 )3.作 业 调 度 目 标 与 性 能 衡 量 2 带 权 周 转 时 间 Wi： Wi=Ti/Tri 平 均 带 权 周 转 时 间 为 ： nW=1/n Wi i=1 3.作 业 调 度 目 标 与 性 能 衡 量 （ 1） 先 来 先 服 务 （ FCFS） 调 度 算 法 将 用 户 作 业 和 就 绪 进 程 按 提 交 顺 序 或 变 为 就 绪状 态 的 先 后 排 成 队 列 ， 并 按 照 先 来 先 服 务 的 方 式 进行 调 度 处 理 ， 是 一 种 最 普 遍 和 最 简 单 的 方 法 。 它 优先 考 虑 在 系 统 中 等 待 时 间 最 长 的 作 业 ， 而 不 管 要 求运 行 时 间 的 长 短 。进 程 调 度 算 法 和 作 业 调 度 算 法 。 作 业 进 入 时 刻 开 始 时 刻 完 成 时 刻 周 转 时 间 带 权 周 转 时 间1 8： 00 8： 00 10：2 8： 50 10： 00 10：3 9： 00 10： 50 11：4 9： 50 11： 00 11： 周 转 时 间 T1 2.00 带 权 周 转 时 间 W1 2/2 1 周 转 时 间 T2 2.00 带 权 周 转 时 间 W2 先 来 先 服 务 算 法 分 析 结 果 周 转 时 间 T3 2.00 带 权 周 转 时 间 W3 周 转 时 间 T4 1.30 带 权 周 转 时 间 W4 6.50 周 转 时 间 Ti Tei Tsi 带 权 周 转 时 间 Wi Ti/Tri 平 均 周 转 时 间 T 1/n Tii=1n 该 算 法 总 是 优 先 调 度 要 求 运 行 时 间 最 短 的 作 业 。作 业 进 入 时 刻 开 始 时 刻 完 成 时 刻 周 转 时 间 带 权 周 转 时 间 1 8： 00 8： 00 10： 2 8： 50 10： 30 11： 3 9： 00 10： 00 10： 4 9： 50 10： 10 10：（ 2） .最 短 作 业 优 先 法 （ SJF） 平 均 周 转 时 间T 1.55 平 均 带 权 周 转 时 间T =4.65 最 高 响 应 比 作 业 优 先 算 法 是 对 FCFS方 式 和 SJF方 式的 一 种 综 合 平 衡 相 应 比 R定 义 为 系 统 对 作 业 的 响 应时 间 与 作 业 要 求 运 行 时 间 的 比 值R 响 应 时 间 / 要 求 运 行 时 间 (作 业 等 待 时 间 需 运 行 时 间 )/ 需 运 行 时 间 1 已 等 待 时 间 / 需 运 行 时 间 1 W/T (3)最 高 相 应 比 作 业 优 先 算 法 （ HRN） 响 应 比 R不 仅 是 要 求 运 行 时 间 的 函 数 ， 而 且 还是 等 待 时 间 的 函 数 。由 于 R与 要 求 运 行 时 间 成 反 比 ， 故 对 短 作 业 是 有 利的 ， 另 一 方 面 ， 因 R与 等 待 时 间 成 正 比 ， 故 长 作 业随 着 其 等 待 时 间 的 增 长 ， 也 可 获 的 较 高 的 相 应 比 。这 就 克 服 了 短 作 业 优 先 数 法 的 缺 点 ， 既 照 顾 了 先 来者 ， 又 优 待 了 短 作 业 ， 是 上 述 两 种 算 法 的 一 种 较 好的 折 中 。 作 业 进 入 时 刻 开 始 时 刻 完 成 时 刻 周 转 时 刻 带 权 周 转 时 刻 1 8： 00 8： 00 10： 00 2 8： 50 10： 50 11： 00 3 9： 00 10： 00 10： 10 4 9： 50 11： 00 11： 20 平 均 周 转 时 间 T平 均 带 权 周 转 时 间 W R1 （ 等 待 时 间 执 行 时 间 ） / 执 行时 间 2 / 2 1R2 ） （ （ ） / 0.50 1R3 ） （ （ 1 ） / 0.10 R4 ） +（ 11.00) （ ） 1 时 间 片 轮 转 法 主 要 用 于 进 程 调 度 。 采 用 此 算法 的 系 统 ， 其 程 序 就 绪 队 列 往 往 按 进 程 到 达 的 时间 来 排 序 。 进 程 调 度 程 序 总 是 选 择 就 绪 队 列 中 的第 一 个 进 程 ， 也 就 是 说 按 照 先 来 先 服 务 原 则 调 度， 但 一 旦 进 程 占 又 处 理 机 仅 使 用 一 个 时 间 片 。 在使 用 先 一 个 时 间 片 后 ， 进 程 还 没 又 完 成 其 运 行 ，它 必 须 释 放 出 处 理 机 给 下 一 个 就 绪 的 进 程 ， 而 被抢 占 的 进 程 返 回 到 就 绪 队 列 的 末 尾 重 新 排 队 等 待在 次 运 行 。 (4) 轮 转 法 （ RR） 时 间 片 轮 转 策 略 特 别 适 合 于 分 时 系 统 中 使 用 ， 当 多个 进 程 驻 留 在 主 存 中 时 ， 在 进 程 间 转 接 处 理 机 的 开 销 一般 是 不 大 的 。 在 轮 转 法 中 ， 时 间 片 长 度 的 选 取 非 常 重 要 ， 时 间 片长 度 的 选 择 会 直 接 影 响 系 统 开 销 和 响 应 时 间 ， 如 果 时 间片 长 度 过 短 ， 则 调 度 程 序 剥 夺 处 理 机 的 次 数 增 多 ， 这 将使 进 程 上 下 文 交 换 次 数 也 大 大 增 加 ， 加 重 了 系 统 开 销 。如 果 时 间 片 长 度 选 择 过 长 （ 大 ） 。 大 到 一 个 进 程 足 以 完成 其 全 部 运 行 工 作 所 需 的 时 间 ， 那 么 时 间 片 轮 转 法 就 退化 为 先 来 先 服 务 策 略 了 。 最 佳 的 时 间 片 量 值 应 能 使 分 时用 户 得 到 好 的 响 应 时 间 响 应 时 间 S RT/Nmax R响 应 时 间 Nmax最 大 进 程 数 每 当 一 轮 调 度 开 始 时 ， 系 统 便 根 据 就 绪 队 列中 已 有 进 程 数 目 计 算 一 次 值 。 作 为 新 一 轮 调 度 的时 间 片 。 这 种 方 法 得 到 的 时 间 片 是 随 就 绪 队 列 中的 进 程 数 变 化 的 。 进 程 调 度 的 功 能 ： 从 就 绪 队 列 中 挑 选 一 个 进程 到 处 理 机 上 运 行 。 作 业 调 度 程 序 在 挑 选 作 业 进 入 主 存 运 行 时 ，要 为 该 作 业 建 立 相 应 的 进 程 。 在 作 业 完 成 后 要 撤销 该 作 业 的 全 部 进 程 。 一 个 进 程 被 建 立 后 ， 系 统 为 了 便 于 对 进 程 的管 理 ， 将 系 统 中 的 所 有 进 程 按 其 状 态 将 其 组 织 成不 同 的 进 程 队 列 。 3.3 进 程 调 度 进 程 调 度 程 序 ： 负 责 进 程 调 度 功 能 的 内 核 程 序。作 业 调 度 与 进 程 调 度 程 序 的 区 别 ： 前 者 是 挑 选作 业 进 主 存 运 行 、 后 者 是 挑 选 就 绪 进 程 到 处 理机 上 运 行 。进 程 调 度 的 核 心 问 题 就 是 ， 采 用 什 么 算 法 把 处理 机 分 配 给 进 程 。 进 程 调 度 的 算 法 较 多 ， 在 设 计 进 程 调 度 算法 时 应 考 虑 的 因 素 多 ， 比 如 ： 尽 量 提 高 资 源 利用 率 ， 减 少 处 理 机 的 空 闲 时 间 ， 对 于 用 户 作 业要 较 合 理 的 平 均 响 应 时 间 ， 以 及 尽 可 能 地 增 强CPU的 处 理 能 力 。 3.4 选 择 调 度 算 法 时 应 考 虑 的 问 题 1. FIFO(先 来 先 服 务 调 度 算 法 ) 最 简 单 的 调 度 原 则 是 先 进 先 出 (FIFO)就 绪 队 列A B C D CPU 完 成 3.5 调 度 算 法 根 据 进 程 到 达 就 绪 队 列 的 时 间 来 分 配 中 央 处 理 机 ，一 旦 一 个 进 程 获 得 了 中 央 处 理 机 ， 就 一 直 运 行 到 结 束 ，先 来 先 服 务 是 非 剥 夺 调 度 。 这 种 调 度 从 形 式 上 讲 是 公 平 的 ， 但 它 使 短 作 业 要 等待 长 作 业 的 完 成 ， 重 要 的 作 业 要 等 待 不 重 要 作 业 的 完 成。 从 这 个 意 义 上 讲 又 是 不 公 平 的 。 先 进 先 出 调 度 使 响 应 时 间 的 变 化 较 小 ， 因 此 它 比 其它 大 多 数 调 度 都 可 预 测 。 由 于 这 种 调 度 方 法 不 能 保 证 良好 的 响 应 时 间 ， 在 处 理 交 互 式 用 户 时 很 少 用 这 种 方 法 。 在 当 今 系 统 中 ， 先 进 现 出 很 少 作 为 调 度模 式 ， 而 是 常 常 嵌 套 在 其 它 的 调 度 模 式 中 。例 如 ， 许 多 调 度 模 式 根 据 优 先 级 将 处 理 机 分配 给 进 程 ， 但 具 有 相 同 优 先 级 的 进 程 却 按 先进 先 出 进 行 分 配 。 根 据 作 业 要 求 系 统 提 供 的 处 理 机 时 间 ， 内 存 的 大小 和 I/O设 备 的 数 量 ， 来 确 定 作 业 的 优 先 数 ， 如 果系 统 赋 予 作 业 的 反 比 于 系 统 的 估 计 执 行 时 间 ， 就形 成 短 作 业 优 先 的 算 法 。 由 于 作 业 需 要 的 执 行 时间 事 先 难 于 确 定 ， 只 是 把 用 户 自 保 的 估 计 时 间 作为 依 据 ， 为 防 止 用 户 少 报 自 己 的 作 业 时 间 以 获 得优 先 服 务 ， 在 采 用 短 作 业 优 先 算 法 时 ， 应 采 取 适当 的 防 备 措 施 。 2. 作 业 要 求 的 资 源 在 有 的 系 统 中 ， 分 配 给 作 业 的 优先 数 还 取 决 于 它 所 占 用 的 内 存 的 多 少， 作 业 越 大 ， 占 用 内 存 越 多 ， 分 配 给它 的 优 先 数 越 低 。 显 然 ， 不 论 是 根 据作 业 的 执 行 时 间 ， 还 是 根 据 作 业 的 大小 所 确 定 的 优 先 数 ， 都 有 利 于 短 作 业。 3.动 态 优 先 数 虽 然 基 于 静 态 优 先 数 的 调 度 算 法比 较 简 单 ， 也 颇 为 流 利 ， 但 毕 竟 不 够精 确 。 因 为 进 程 的 优 先 数 在 它 执 行 前就 已 算 好 ， 且 在 整 个 执 行 期 间 都 保 持不 变 ， 但 随 着 进 程 的 推 进 ， 计 算 优 先数 所 依 赖 的 特 征 很 多 都 将 随 之 改 变 ，因 此 静 态 优 先 数 并 非 自 始 至 终 都 能 准 确 地 反 映 出 这 些 特 性 ， 如 果 能 在 进 程运 行 中 ， 不 断 的 随 着 特 性 的 改 变 而 修改 其 优 先 数 ， 显 然 可 以 实 现 更 多 精 确的 调 度 ， 从 而 获 得 更 好 的 调 度 性 能 ，这 对 分 时 系 统 显 得 格 外 重 要 . 4.时 间 片 轮 转 算 法 F C B A . CPU 完 成 A B C 当 时 间 片 很 大 时 ， 每 个 进 程 得 到 比完 成 该 进 程 多 的 处 理 机 时 间 ， 此 时 轮转 调 度 模 式 退 化 为 先 进 先 出 模 式 。 当 时 间 片 非 常 小 时 ， 上 下 文 转 换 开销 就 成 了 决 定 因 素 ， 系 统 性 能 降 低 ，大 多 数 时 间 都 消 耗 在 处 理 机 的 转 换 上， 只 有 少 许 用 在 用 户 的 计 算 上 。 这 个 最 佳 的 时 间 片 值 是 多 少 呢 ？ 显 然 ， 它 将随 系 统 而 异 。 随 负 载 而 异 ， 同 时 也 随 进 程 异 。 时 间 片 的 选 取 是 实 现 各 种 调 度 算 法 的 关 键 之处 ， 而 时 间 片 的 独 额 定 通 常 应 考 虑 终 端 数 目 ， 处理 机 能 力 、 各 终 端 任 务 的 急 迫 程 度 、 外 存 传 输 速度 等 方 面 的 因 素 。 时 间 片 轮 转 法 亦 可 应 用 于 批 处理 系 统 的 处 理 机 调 度 。 一 种 常 用 的 进 程 调 度 算 法 是 把 处 理 机 分 配 给 具 有 最 高 优先 数 的 进 程 （ 用 于 实 时 系 统 ） 在 这 种 算 法 中 ， 首 先 考 虑 的 问 题 是 如 何 确 定 进 程 的优 先 数 。 一 种 是 静 态 优 先 数 ， 另 一 种 是 动 态 优 先 数 。1)静 态 优 先 数 静 态 优 先 数 是 在 系 统 创 建 时 确 定 的 ， 一 经 确 定 之 后在 整 个 进 程 运 行 期 间 不 再 改 变 ， 确 定 静 态 优 先 数 的 有 关静 特 性 是 ： 5.优 先 级 调 度 算 法 系 统 中 由 两 类 进 程 ， 系 统 进 程 和 用 户 进 程 。 系 统 进 程的 优 先 数 比 用 户 进 程 的 优 先 数 高 ， 特 别 是 某 些 系 统 进 程 ，必 须 赋 予 它 一 种 特 权 ， 当 它 需 要 处 理 机 时 ， 应 尽 快 的 到 满足 。 例 如 ， 设 备 管 理 器 中 的 I/O进 程 便 是 如 此 。 这 不 仅 是为 了 保 证 I/O设 备 尽 可 能 忙 碌 ， 一 提 高 设 备 利 用 率 ， ， 更主 要 的 是 为 了 避 免 由 于 响 应 不 及 时 ， 将 造 成 信 息 的 丢 失 。在 用 户 进 程 中 ， I/O繁 忙 的 进 程 应 优 先 与 CPU繁 忙 的 进 程 ，以 保 证 CPU和 I/O设 备 之 间 的 并 行 操 作 。 在 分 时 系 统 中 ， 前台 进 程 应 优 先 于 后 台 进 程 。 进 程 类 型 什 么 是 多 处 理 机 系 统 多 处 理 机 操 作 系 统 的 分 类 多 处 理 机 系 统 调 度 策 略 3.6 多 处 理 机 调 度 多 处 理 机 系 统 ： 是 一 个 具 有 两 个 或 多 个 处 理 机 并能 相 互 进 行 通 信 以 协 同 一 个 大 的 给 定 问 题 求 解 的 计 算机 系 统 。特 点 ： 1） 有 两 个 或 多 个 处 理 机2） 共 享 主 存 或 高 速 通 信 网 络3） 共 享 输 入 输 出 子 系 统4） 有 单 一 完 整 的 操 作 系 统5） 各 级 硬 件 和 软 件 相 互 作 用3.6.1.什 么 是 多 处 理 机 系 统 主 要 功 能 ： 进 程 分 配 更 好 的 利 用 多 机 硬 件 资 源 在 处 理 机 之 间 的 分 配 改 善 程 序 的 响 应 时 间 处 理 机 的 负 载 平 衡 处 理 机 间 的 协 调 和 同 步 因 处 理 机 故 障 引 起 的 系 统 重 组 广 意 上 说 ， 使 用 多 处 理 机 协 调 工 作 ， 来 完 成 用 户 所要 求 任 务 的 计 算 机 系 统 。 这 包 扩 了 并 行 处 理 系 统 （parallel processing system） ， 例 如 数 据 流 机(dataflow machine)和 细 胞 阵 列 处 理 机 (Celluar array processors)等 ,也 包 扩 了 在 物 理 上 分 散 且 通 过 不 同 的 物理 传 输 媒 体 传 输 数 据 的 机 算 机 网 络 系 统 和 计 算 机 网 络 为基 础 的 ,对 用 户 透 明 的 分 布 式 系 统 ,以 及 在 同 一 的 计 算 机系 统 里 共 享 内 存 的 多 处 理 机 系 统 . 广 义 的 计 算 机 系 统 的一 个 共 同 的 特 点 是 有 n个 处 理 器 (n1),能 做 到 真 正 的 并 行处 理 ,也 就 是 能 同 时 执 行 n条 指 令 . 本 节 所 介 绍 的 多 处 理 机 操 作 系 统 是 指 哪 些 用 来 并 行 执 行 用户 的 几 个 程 序 ， 以 提 高 系 统 的 吞 吐 率 ； 或 行 余 操 作 以 提 高 系统 可 靠 性 的 多 处 理 操 作 系 统 。 这 种 系 统 由 共 享 公 共 内 存 和 外 设的 n(n1)个 CPU组 成 。 从 概 念 上 说 ， 在 多 处 理 机 系 统 中 的 各 进 程 的 行 为 与 在 单 机系 统 下 的 行 为 相 同 。 因 此 ， 对 多 处 理 机 操 作 系 统 的 要 求 与 对 多道 程 序 的 批 处 理 系 统 没 有 太 多 的 区 别 。 但 是 ， 多 处 理 环 竟 下 ，进 程 可 在 各 处 理 机 间 进 行 透 明 迁 移 ， 从 而 ， 由 进 程 上 下 文 切 换等 带 来 的 系 统 开 销 将 使 得 多 处 理 机 操 作 系 统 的 复 杂 度 大 大 增 加。 另 外 ， 由 于 多 处 理 机 系 统 并 行 地 执 行 用 户 的 几 个 程 序 （ 进 程） ， 这 又 带 来 了 多 处 理 机 条 件 下 的 并 发 执 行 问 题 。多 处 理 机 操 作 系 统 的 分 类 使 用 多 处 理 机 系 统 的 主 要 原 因 是 提 高 系 统 的 可 靠性 和 在 发 生 故 障 时 能 将 低 使 用 ； 另 一 个 原 因 是 提 高 系 统 吞吐 。 因 此 ， 一 个 多 处 理 机 操 作 系 统 除 了 提 高 资 原 分 配 和管 理 ， 进 程 和 处 理 机 管 理 ， 内 存 和 数 据 集 保 护 以 及 文 件 系统 等 功 能 之 外 ， 还 能 提 供 系 统 结 构 重 组 的 能 力 ， 以 支 持 系统 的 降 级 使 用 。 因 此 ， 多 处 理 机 的 调 度 策 略 也 必 须 考 虑 到降 级 使 用 和 结 构 重 组 问 题 。 目 前 为 止 的 多 处 理 机 操 作 系 统 可 以 分 为 三 类 ： (1) 主 从 式 （ master-slave configuration）(2) 独 立 监 控 系 统 (Separate supervisor) (3) 移 动 式 监 控 系 统 (floating supervisor) 主 从 式 中 ， 指 定 一 台 特 定 的 处 理 机 为 主 处 理 机 ， 由 它负 责 对 全 系 统 的 执 行 进 行 控 制 . 在 主 从 式 操 作 系 统 中 ， 主 处 理 器 上 执 行 操 作 系 统 程 序， 以 控 制 其 它 从 处 理 机 的 状 态 ， 并 为 从 处 理 机 分 配 任 务 。DEC system 10 ,Cyber 170 以 及 多 处 理 机 UNIX系 统 MPX都是 主 从 式 结 构 .在 主 从 式 操 作 系 统 中 ,如 果 从 处 理 机 需 要 主处 理 机 提 供 服 务 时 ,它 们 采 用 硬 件 中 断 方 式 中 断 处 理 机 上 执行 的 进 程 以 要 求 主 处 理 机 提 供 服 务 .这 种 结 构 的 操 作 系 统 一般 重 组 功 能 较 差 ,因 为 只 有 主 处 理 机 上 执 行 操 作 系 统 程 序 .如 果 主 处 理 机 失 败 或 发 生 不 可 恢 复 的 错 误 时 ,整 个 系 统 将 会瘫 痪 . (1)主 从 式 （ master-slave configuration） 独 立 监 控 系 统 的 监 控 程 序 在 每 个 处 理 机 上 执 行, 每 个 处 理 机 为 自 己 的 需 要 提 供 服 务 又 互 相 通 报 执行 情 况 .一 般 来 说 ,每 个 监 控 程 序 能 重 新 装 入 或 在 不同 的 处 理 机 上 复 制 独 立 的 副 本 . 独 立 监 控 系 统 不 像 主 从 结 构 那 样 易 于 崩 溃 ,但其 监 控 程 序 在 各 处 理 机 中 的 副 本 会 占 去 大 量 的 内 存. (2)独 立 监 控 系 统 (Separate supervisor) 移 动 式 监 控 系 统 ： 移 动 式 监 控 系 统 把 监 控 程序 根 据 需 要 从 一 个 处 理 机 移 到 另 一 个 处 理 机 上 .使所 有 资 原 有 比 较 均 衡 的 负 载 . 移 动 式 监 控 系 统 的 处 理 机 调 度 以 及 服 务 请 求冲 突 等 大 都 采 用 优 先 级 的 方 式 来 解 决 .所 以 移 动式 监 控 系 统 是 一 种 效 率 最 高 ,实 现 也 最 难 的 多 处 理操 作 系 统 . (3)移 动 式 监 控 系 统 (floating supervisor) （ 1） 多 处 理 机 系 统 与 单 机 调 度 的 区 别 多 处 理 机 调 度 与 单 机 调 度 的 主 要 区 别 涉 及 两 个 资 源 分配 问 题 ：一 是 存 放 程 序 或 数 据 的 存 储 器 分 配 及 如 何 访 问 他 们 的 问 题。 在 多 机 系 统 中 ， 由 于 各 进 程 在 物 理 上 也 同 时 执 行 而 不是 单 机 系 统 那 样 的 交 叉 执 行 ， 这 些 在 物 理 上 同 时 执 行 的 进程 可 能 同 时 访 问 物 理 存 储 器 的 同 一 地 址 。 处 理 机 对 同 一 存储 块 的 访 问 必 须 是 顺 序 的 。 各 进 程 同 时 访 问 物 理 存 储 器 上的 同 一 地 址 是 不 允 许 的 。3.6.3 多 处 理 机 系 统 调 度 策 略 二 是 将 等 待 执 行 的 就 绪 进 程 分 配 到 哪 一 个 处 理 机 上 执行 的 问 题 。 在 单 机 系 统 中 ， 由 于 只 有 一 个 处 理 机 ， 在 调 度 程序 中 选 取 了 某 个 就 绪 状 态 的 进 程 之 后 ， 不 须 再 选 择 处 理机 。 而 在 多 机 系 统 中 ， 为 了 尽 量 做 到 让 各 处 理 机 负 荷 平恒 ， 可 能 会 会 将 处 理 机 在 进 程 之 间 进 行 多 次 切 换 。 如 果被 切 换 进 程 正 在 执 行 其 临 界 区 部 分 或 系 统 中 进 程 数 目 相当 多 ， 这 种 频 繁 的 上 下 文 转 换 将 会 使 系 统 效 率 大 大 下 降。 为 了 解 决 进 程 对 处 理 机 的 分 配 问 题 ， 在 有 的 多 出 理 机 系统 中 采 用 了 局 部 就 绪 对 列 的 方 法 限 制 进 程 的 转 移 。 局 部 就 绪 对 列 ： 就 是 把 处 于 就 绪 状 态 的 进 程 分 成 不 同的 组 ， 并 使 每 一 组 进 程 和 一 个 处 理 机 对 应 起 来 。 这 样 ， 每 个处 理 机 只 执 行 以 其 对 应 就 绪 对 列 中 的 进 程 。 各 个 就 绪 对 列 中的 进 程 读 断 发 生 横 向 转 移 。 这 种 方 法 减 少 了 调 度 程 序 的 开 销。 但 是 ， 处 理 机 的 使 用 率 却 因 此 下 降 。 例 如 ： 系 统 中 某 个 局部 就 绪 对 列 中 因 等 待 进 程 较 多 而 使 得 对 应 的 处 理 机 十 分 繁 忙， 而 另 外 的 处 理 机 则 因 就 绪 对 列 为 空 而 处 于 空 闲 状 态 。 多 处 理 机 系 统 的 调 度 目 标 是 ： 以 最 高 的 可 靠 性 ， 使 用 最 少 的 处 理 机 在 最 短 的 时 间内 完 成 最 多 的 可 以 并 行 完 成 的 进 程 。 多 处 理 机 的 调 度 有 两 种 评 价 模 型 ： 一 种 是 确 定 性 模 型 ， 另 一 种 是 随 机 性 模 性 。 确 定 性 模 型 ： 进 程 调 度 执 性 之 前 ， 估 计 出 这 些 被 调 度进 程 所 须 要 的 执 行 时 间 ， 以 及 这 些 进 程 之 间 的 相 互 关系 。 调 度 程 序 的 目 的 ： 是 根 据 给 定 的 执 行 时 间 和 相 互 关 系， 确 定 出 一 个 最 佳 的 执 行 顺 序 。 因 此 ， 确 定 性 模 型 只 用 来 确 定 给 定 进 程 的 执 行 顺 序 ，而 随 机 性 模 性 则 常 被 用 来 研 究 动 态 调 度 技 术 。 （ 2） 多 处 理 机 的 调 度 评 价 动 态 调 度 ： 在 一 个 特 定 的 时 刻 ， 将 进 程 分 配 到 一 个 特定 的 处 理 机 上 执 行 。 随 机 模 型 中 的 进 程 执 行 时 间 是 一 个 具有 平 均 值 和 标 准 偏 移 值 的 随 机 变 量 。 无 论 是 确 定 模 型 还 是 随 机 模 型 ， 我 们 都 可 以 把 一 个包 含 进 程 集 合 的 工 作 集 用 优 先 图 的 方 式 表 现 出 来 ， 图 中 节点 的 集 合 T=T1， T2， Tn代 表 进 程 的 集 合 ， 结 点 的 加 权集 合 W=W1,W2， Wn代 表 各 进 程 在 处 理 机 上 执 行 时 间 的集 合 。 对 于 确 定 模 型 来 说 ， W中 各 元 素 为 随 机 变 量 。
展开阅读全文