《处理器管理》PPT课件

第 2章 处 理 器 管 理 主 讲 ： 周 文 强 课 程 ： 操 作 系 统 本 章 内 容 ：2.4 进 程 同 步 机 制2.5 进 程 通 信2.6 处 理 机 调 度 2.4 进 程 同 步 机 制 操 作 系 统 中 引 入 进 程 后 ， 虽 然 改 善 了 资 源的 利 用 率 ， 提 高 了 系 统 的 吞 吐 量 。 但 是 ， 由 于 进 程 的 异 步 性 ， 也 会 给 系 统 造成 混 乱 。 因 此 ， 必 须 有 效 地 协 调 各 个 并 发进 程 间 的 关 系 ， 从 而 使 它 们 能 正 确 的 执 行 。 本 节 主 要 介 绍 进 程 的 同 步 与 互 斥 的 实 现 机制 。 2.4.1 进 程 的 并 发 性 在 并 发 运 行 的 系 统 中 ， 若 干 个 作 业 可 以 同时 运 行 ， 而 每 个 作 业 又 需 要 有 多 个 进 程 协作 完 成 。 在 这 些 同 时 存 在 的 进 程 间 具 有 并发 性 ， 称 之 为 “ 并 发 进 程 ”。 进 程 间 的 关 系 可 以 分 为 ：1、 资 源 共 享 关 系2、 相 互 合 作 关 系 1、 资 源 共 享 关 系 系 统 中 的 某 些 进 程 需 要 访 问 共 同 的 资 源 ，即 当 一 个 进 程 访 问 共 享 资 源 时 ， 访 问 该 共享 资 源 的 其 他 进 程 必 须 等 待 ， 当 这 个 进 程使 用 完 后 ， 其 他 进 程 才 能 使 用 。 这 时 要 求进 程 应 互 斥 地 访 问 共 享 资 源 。 2、 相 互 合 作 关 系 系 统 中 的 某 些 进 程 之 间 存 在 相 互 合 作 的 关系 ， 即 一 个 进 程 执 行 完 后 ， 另 一 个 进 程 才能 开 始 。 否 则 ， 另 一 个 进 程 不 能 开 始 ， 这时 就 要 保 证 相 互 合 作 的 进 程 在 执 行 次 序 上要 同 步 。 1、 临 界 资 源 通 常 一 次 仅 允 许 一 个 进 程 使 用 的 资 源称 为 临 界 资 源 ， 同 时 ， 也 将 一 个 进 程访 问 的 这 种 临 界 资 源 的 那 段 程 序 代 码称 为 临 界 区 。 操 作 系 统 中 的 进 程 就 绪 队 列 就 是 一 种在 一 个 时 刻 只 能 允 许 一 个 进 程 访 问 的临 界 资 源 。 所 以 ， 进 程 的 互 斥 就 是 两个 进 程 不 能 同 时 进 入 访 问 同 一 临 界 资源 的 临 界 区 。 2、 临 界 区 (critical section) 临 界 区 是 进 程 执 行 程 序 中 的 对 临 界 资 源 访问 的 那 一 段 程 序 ， 这 段 程 序 的 进 入 执 行 ，需 要 有 一 定 的 原 则 来 协 调 。 例 如 ： 1、 有 若 干 进 程 都 欲 进 入 临 界 区 ， 它 们 不 能互 相 阻 塞 ， 使 得 谁 也 进 不 了 临 界 区 ， 应 当在 有 限 时 间 内 让 一 个 进 程 进 入 临 界 区 。 2、 每 次 至 多 有 一 个 进 程 进 入 临 界 区 ， 并 且在 临 界 区 中 只 能 停 留 有 限 的 时 间 。 3、 进 程 同 步 多 个 相 关 进 程 在 执 行 次 序 上 的 协 调 ， 这 些 进程 相 互 合 作 ， 在 一 些 关 键 点 上 需 要 相 互 等 待或 相 互 通 信 。 通 过 临 界 区 可 以 协 调 进 程 间 相 互 合 作 的 关 系 ，这 就 是 进 程 同 步 4、 进 程 互 斥 当 一 个 进 程 进 入 临 界 区 使 用 临 界 资 源 时 ，另 一 个 进 程 必 须 等 待 。 当 占 用 临 界 资 源 的进 程 退 出 临 界 区 后 ， 另 一 个 进 程 才 被 允 许使 用 临 界 资 源 。 通 过 临 界 区 协 调 进 程 间 资 源 共 享 的 关 系 ，就 是 进 程 互 斥 。 2.4.3 进 程 同 步 机 制 应 遵 循 的 原 则 (1)空 闲 让 进 。 当 无 进 程 处 于 临 界 区 时 ，允 许 一 个 进 程 进 入 。 (2)忙 则 等 待 。 当 有 进 程 在 临 界 区 中 ，其 他 欲 进 入 临 界 区 的 进 程 必 须 等 待 。 (3)有 限 等 待 。 对 要 求 进 入 临 界 区 的 进程 ， 应 在 有 限 时 间 内 让 其 进 入 ， 避 免“ 死 等 ” 。 (4)让 权 等 待 。 临 界 区 让 出 ， 必 须 立 即释 放 处 理 器 ， 让 等 待 进 程 进 入 ， 避 免“ 忙 等 ” 。 12 n锁 操 作 ：1.测 试 锁 位 的 值 ； lock/unlock2.若 原 来 的 值 是 为 “ 0”， 将 锁 位 置 为 “ 1”（ 占 用 该资 源 ） ；3.若 原 来 值 是 为 “ 1”， （ 该 资 源 已 被 别 人 占 用 ） ，则 转 到 1。n开 锁 操 作 ：进 程 使 用 完 资 源 后 ， 将 锁 位 置 为 “ 0”， 称 为 开 锁 操作 。 2.4.4 进 程 同 步 机 制 锁 13 锁 操 作 的 缺 点 14 18 20 放 水 果 问 题有 一 个 水 果 盘 ， 只 能 放 入 1个 水 果 。 父 亲 每 次 放1个 苹 果 供 儿 子 吃 ， 或 者 放 1个 橘 子 供 女 儿 吃 。 给出 父 亲 、 儿 子 、 女 儿 的 算 法 描 述 。 放 水 果 问 题需 要 三 个 信 号 量 s1,s2,s3分 别 代 表 需 要 盘子 是 否 为 空 ， 是 否 可 以 有 苹 果 ， 是 否 橘 子 。父 亲 进 程 ：A:P（ s1 ）if 放 苹 果 then V(s2)else V(s3) goto As1 = 1， s2 = 0， s2 = 0 放 水 果 问 题儿 子 进 程 ：B:P(s2) 取 走 苹 果V（ s1）goto B 女 儿 进 程C:P(s3) 取 走 苹 果V（ s1）goto C PA Ppbufferdeposit(data) remove(data)例 进 程 PA和 PB共 享 缓 冲 队 列 发 送 和 接 收数 据 。 26 在 PA至 少 送 一 块 数 据 入 一 个 缓 冲 区 之 前 ，PB不 可 能 从 缓 冲 区 中 取 出 数 据 (假 定 数 据 块长 等 于 缓 冲 区 长 度 )； PA往 缓 冲 队 列 发 送 数 据 时 ， 至 少 有 一 个 缓冲 区 是 空 的 ； 由 PA发 送 的 数 据 块 在 缓 冲 队 列 中 按 先 进 先出 方 式 排 列 。 2.4.8 利 用 信 号 量 实 现 进 程 同 步 与 互 斥 每 个 进 程 中 各 个 P操 作 的 次 序 是 重 要 的 ： 先 检 查 资 源 数 目 ， 再检 查 是 否 互 斥 否 则 可 能 死 锁 ！ Consumer：Producer：P(avail);P(mutex); one unit-buf;V(mutex);V(full); P(full);P(mutex); /进 入 区 one unit-buf;V(mutex);V(avail); /退 出 区分 析 ： 当 full=0, mutex = 1时 ， 执 行 顺 序 ： / C阻 塞 ， 等 待 Producer 发 出 的 full信 号 / P 阻 塞 ， 等 待 Consumer发 出 的 avail信 号 2.4.9 利 用 信 号 量 实 现 进 程 同 步 的 方 法1、 使 用 PV操 作 的 规 则（ 1） 分 清 哪 些 是 互 斥 问 题 ， 哪 些 是 同 步 问 题（ 2） 对 于 互 斥 问 题 要 设 置 互 斥 信 号 量 ， 不 管 有 互斥 关 系 的 进 程 有 几 个 或 几 类 ， 互 斥 信 号 量 的 个 数只 与 临 界 资 源 的 种 类 有 关（ 3） 对 于 同 步 问 题 要 设 置 同 步 信 号 量 ， 通 常 同 步信 号 量 的 个 数 与 参 与 同 步 的 进 程 种 类 有 关（ 4） 在 每 个 进 程 中 由 于 实 现 互 斥 的 PV操 作 必 须 成对 出 现 ； 用 于 实 现 同 步 的 PV操 作 也 必 须 成 对 出 现。 必 须 先 执 行 对 同 步 信 号 量 的 P操 作 ， 再 执 行 对互 斥 信 号 量 的 P操 作 。 2、 同 步 互 斥 问 题 的 解 题 步 骤（ 1） 确 定 进 程 。 包 括 进 程 的 数 量 、 进 程 的工 作 内 容 ， 可 以 用 流 程 图 描 述（ 2） 确 定 同 步 互 斥 关 系 。 根 据 使 用 的 是 临界 资 源 ， 还 是 处 理 的 前 后 关 系 ， 来 确 定 互斥 与 同 步 ， 然 后 确 定 信 号 的 个 数 、 含 义 ，以 及 对 信 号 量 的 PV操 作（ 3） 用 C语 言 描 述 同 步 或 互 斥 算 法 2.5 进 程 通 信 进 程 通 信 是 指 进 程 间 的 信 息 交 换 。 进 程 通信 所 交 换 的 信 息 量 少 则 一 个 数 值 或 状 态 ，多 则 成 千 上 万 个 字 节 。 根 据 通 信 的 机 制 不 同 将 进 程 通 信 分 为 低 级通 信 和 高 级 通 信 。 低 级 通 信 -进 程 的 同 步 和 互 斥进 程 的 同 步 和 互 斥 称 为 低 级 通 信 。缺 点 ：1、 效 率 低 ， 一 次 发 送 的 信 息 量 比 较 少 。2、 信 号 量 机 制 主 要 依 靠 进 程 来 控 制 ， 用 户使 用 不 方 便 。 高 级 通 信 高 级 通 信 是 指 用 户 直 接 利 用 操 作 系 统 提 供的 一 组 通 信 命 令 ， 高 效 地 传 送 大 量 数 据 的一 种 通 信 方 式 。高 级 通 信 机 制 分 为 3大 类 ：1、 共 享 存 储 器 系 统2、 消 息 传 递 系 统3、 管 道 通 信 系 统 2.5.1 共 享 存 储 器 系 统 在 共 享 存 储 器 系 统 中 ， 相 互 通 信 的 进 程 共享 某 些 数 据 结 构 或 存 储 区 ， 进 程 之 间 能 够通 过 它 们 进 程 通 信 。共 享 存 储 器 系 统 分 为 2种 方 式 ：1、 共 享 数 据 结 构 方 式2、 共 享 存 储 区 方 式 1、 共 享 数 据 结 构 方 式 在 这 种 通 信 方 式 下 ， 相 互 通 信 的 进 程 共 用 某些 数 据 结 构 ， 并 通 过 这 些 数 据 结 构 交 换 信 息 。这 种 方 式 与 信 号 量 机 制 相 比 ， 并 没 有 发 生 太大 的 变 化 ， 比 较 低 效 、 复 杂 ， 只 适 合 于 传 送少 量 的 数 据 。 2、 共 享 存 储 区 方 式 这 种 通 信 方 式 是 在 存 储 器 中 划 出 一 块 共 享 存储 区 ， 相 互 通 信 的 进 程 可 以 通 过 对 共 享 存 储区 中 的 数 据 进 行 读 或 写 来 实 现 通 信 。 这 种 方式 效 率 高 ， 可 以 传 送 较 多 的 数 据 。 2.5.2 消 息 传 递 系 统 在 消 息 传 递 信 息 中 ， 进 程 间 的 数 据 交 换 是 以消 息 为 单 位 进 行 的 。 用 户 直 接 利 用 系 统 中 提供 的 一 组 通 信 命 令 （ 原 语 ） 进 程 通 信 。 消 息传 递 系 统 成 为 最 常 用 的 高 级 通 信 方 式 。优 点 ：1、 工 作 效 率 提 高2、 简 化 了 程 序 编 制 的 复 杂 性 ， 方 便 用 户 的 使用 。 1、 直 接 通 信 方 式 发 送 进 程 使 用 发 送 原 语 直 接 将 消 息 发 送 给 接 收 进程 ， 并 将 它 挂 在 接 收 进 程 的 消 息 缓 冲 队 列 上 。 接收 接 收 进 程 使 用 接 收 原 语 从 消 息 缓 冲 队 列 中 读 取消 息 。 通 常 系 统 提 供 两 条 通 信 原 语 。发 送 原 语 ： Send（ Receiver， message） ；接 收 原 语 ： Receive（ Sender， message） ；例 如 原 语 Send（ P2， M） 表 示 将 消 息 M发 送 给 接 收进 程 P2； 而 原 语 Receive（ P1， M） 则 是 表 示 接收 由 进 程 P1发 送 来 的 消 息 M。 2、 间 接 通 信 方 式 发 送 进 程 与 接 收 进 程 通 过 中 间 实 体 信 箱来 完 成 通 信 ， 既 可 以 实 现 实 时 通 信 ， 有 可以 实 现 非 实 时 通 信 。 接 收 进 程 使 用 接 收 原 语 从 信 箱 中 取 出 消 息 。 （ 1） 信 箱 通 信 的 操 作 系 统 为 信 箱 通 信 提 供 了 若 干 条 操 作 原 语 ，包 括 创 建 信 箱 原 语 、 撤 销 信 箱 原 语 、 发 送原 语 、 接 收 原 语 等 。 1、 信 箱 的 创 建 与 撤 销 。 进 程 可 以 利 用 信 箱 创 建 原 语 来 建 立 一 个 新信 箱 。 创 建 进 程 应 给 出 信 箱 的 名 字 、 信 箱属 性 等 。 当 信 箱 所 属 进 程 不 再 需 要 该 信 箱时 ， 可 用 信 箱 撤 销 原 语 来 撤 销 信 箱 。 2、 消 息 的 发 送 与 接 收 。 相 互 通 信 的 进 程 利用 系 统 提 供 的 下 述 通 信 原 语 来 实 现 消 息 的发 送 与 接 收 。Send（ mailbox， message） ： 将 一 个 消 息发 送 到 指 定 信 箱Receive（ mailbox， message） ： 从 指 定信 箱 中 接 收 一 个 消 息 （ 2） 消 息 的 分 类 消 息 可 以 由 操 作 系 统 创 建 ， 也 可 以 由 用 户创 建 。 创 建 者 是 信 箱 的 拥 有 者 ， 信 箱 可 以分 为 3类 ： 1、 私 用 信 箱 。 用 户 进 程 可 以 为 自 己 建 立 一个 新 信 箱 ， 并 作 为 进 程 的 一 部 分 信 箱 的 拥有 者 有 权 从 信 箱 中 读 取 信 息 ， 其 他 用 户 只能 将 自 己 的 消 息 发 送 到 该 信 箱 中 。 当 拥 有该 信 箱 的 进 程 终 止 时 ， 信 箱 也 随 之 消 失 。 2、 公 用 信 箱 。 它 由 操 作 系 统 创 建 ， 并 提 供给 系 统 中 所 有 核 准 的 用 户 进 程 使 用 。 核 准的 进 程 既 可 以 把 消 息 发 送 到 该 信 箱 ， 有 可以 从 信 箱 中 取 出 发 送 给 本 人 的 消 息 。 通 常 ，公 用 信 箱 在 系 统 运 行 期 间 始 终 存 在 。 3、 共 享 信 箱 。 它 实 际 上 是 某 种 进 程 创 建 的私 有 信 箱 。 在 创 建 时 或 创 建 后 ， 又 指 明 它是 可 以 共 享 的 ， 同 时 指 出 共 享 进 程 （ 用 户 ）的 名 字 ， 此 时 就 成 为 共 享 信 箱 。 信 箱 的 拥有 者 和 共 享 者 ， 都 有 权 从 信 箱 中 取 走 发 送给 本 人 的 消 息 。 （ 3） 通 信 进 程 间 的 关 系 当 利 用 信 箱 通 信 时 ， 发 送 进 程 与 接 收 进 程 存 在 下 列 关 系 ： 1、 一 对 一 关 系 。 在 一 个 发 送 进 程 和 一 个 接 收 进 程 之 间 建立 一 条 专 用 的 通 信 通 道 ， 使 它 们 之 间 的 通 信 不 受 其 他 进程 的 影 响 。 2、 多 对 一 关 系 。 允 许 提 供 服 务 的 一 个 接 收 进 程 与 多 个 用户 发 送 进 程 之 间 进 行 通 信 ， 也 称 为 客 户 /服 务 器 方 式 。 3、 一 对 多 关 系 ， 允 许 一 个 发 送 进 程 与 多 个 接 收 进 程 进 行通 信 ， 使 发 送 进 程 可 以 用 广 播 形 式 ， 向 一 组 或 全 部 接 收者 发 送 消 息 。 4、 多 对 多 关 系 。 允 许 建 立 一 个 公 用 信 箱 ， 让 多 个 进 程 既可 以 把 消 息 发 送 到 该 信 箱 ， 又 可 以 从 信 箱 中 取 出 发 送 给本 人 的 消 息 。 2.5.3 管 道 通 信 系 统 管 道 是 指 连 接 读 进 程 和 写 进 程 的 ， 用 于 实现 它 们 之 间 通 信 的 共 享 文 件 。 向 管 道 提 供输 入 的 发 送 进 程 （ 写 进 程 ） ， 以 字 符 流 的形 式 间 大 量 数 据 送 入 管 道 ， 而 接 收 管 道 输出 的 接 收 进 程 （ 读 进 程 ） ， 可 以 从 管 道 中接 收 数 据 。 由 于 发 送 进 程 和 接 收 进 程 是 利用 管 道 进 行 通 信 的 ， 故 称 为 管 道 通 信 方 式 。 2.6 处 理 机 调 度 一 个 作 业 从 提 交 开 始 直 到 完 成 ， 往 往 要 经 历三 级 调 度 ， 即 作 业 调 度 （ 高 级 调 度 ） 、 进 程调 度 （ 低 级 调 度 ） 和 中 级 调 度 。1、 作 业 调 度 是 从 后 备 作 业 队 列 中 选 择 出 若 干个 作 业 ， 为 它 们 分 配 必 要 的 资 源 ， 将 它 们 调入 主 存 ， 为 它 们 建 立 进 程 ， 使 之 成 为 就 绪 进程 。2、 进 程 调 度 是 从 主 存 就 绪 队 列 上 选 择 哪 个 进程 获 得 处 理 器 资 源 ， 让 进 程 运 行 。 56 功 能 ： 按 照 一 定调 度 算 法 从 就 绪队 列 中 选 择 一 个新 的 进 程 投 入 运行 。入 口 信 息 ： 可 省 入 口 （ 就 绪 队 列 指 针 ） 调 度 算 法 选 择 将 选 中 进 程 从 就 绪 队 列 取 出 运 行 修 改 选 中 进 程 的 PCB： 状 态 =运 行 态 就 绪 队 列 就 绪 队 列 运 行 态 进 程 调 度 2.6.1 进 程 调 度 算 法 的 选 取 原 则 选 择 调 度 算 法 的 原 则 有 面 向 用 户 的 ， 也 有面 向 系 统 的 。1、 面 向 用 户 的 原 则（ 1） 周 转 时 间 短（ 2） 相 应 时 间 快（ 3） 截 止 时 间 有 保 证（ 4） 优 先 权 原 则 计 算 公 式周 转 时 间 =完 成 时 间 -到 达 时 间平 均 周 转 时 间 =每 个 进 程 的 周 转 时 间 之 和 /进程 个 数带 权 周 转 时 间 =进 程 的 周 转 时 间 /系 统 为 进 程提 供 的 实 际 服 务 时 间平 均 带 权 周 转 时 间 =所 有 进 程 的 带 权 周 转 世间 之 和 /进 程 个 数 2、 面 向 系 统 的 原 则（ 1） 系 统 吞 吐 量 高（ 2） 处 理 器 利 用 率 高（ 3） 各 类 资 源 的 平 衡 利 用 2.6.2 常 用 的 进 程 调 度 算 法 算 法 选 择 的 合 理 性 ， 将 决 定 进 程 调 度 的 优 劣， 它 要 解 决 两 个 问 题 ： 第 一 选 择 哪 个 进 程 执 行 进 程 调 度 ； 第 二 个 选 中 某 个 进 程 ， 如 何 给 它 分 配 处 理 器， 该 进 程 能 占 用 处 理 器 多 久 。 第 一 个 问 题 是 选 择 进 程 调 度 算 法 ， 第 二 个 问题 是 选 择 进 程 的 调 度 方 式 。 1 先 来 先 服 务 调 度 算 法 FCFS按 照 进 程 进 入 就 绪 队 列 的 先 后 顺 序选 择 可 以 占 用 处 理 器 的 进 程 。 这 是 一 种 不可 抢 占 方 式 的 调 度 算 法 。 优 点 ： 实 现 简 单 ， 缺 点 ： 后 来 的 进 程 等 待 CPU的 时 间 较 长 。 2 短 执 行 进 程 优 先 算 法 SPF就 是 从 就 绪 队 列 中 选 择 一 个 CPU执 行时 间 预 期 最 短 的 进 程 ， 将 处 理 器 分 配 给 它。 优 点 ： 较 公 平 缺 点 ： 实 现 难 度 较 大 ， 因 为 要 准 确 预 定 下一 个 进 程 的 CPU执 行 周 期 是 很 困 难 的 。 3.最 短 剩 余 时 间 优 先 调 度 算 法 SRT是 将 CPU分 配 给 需 要 最 少 时 间 来完 成 的 进 程 。 SRT充 分 照 顾 了 剩 余 运 行 时间 短 的 进 程 。 4 时 间 片 轮 转 法 RR让 每 个 进 程 在 就 绪 队 列 中 的 等 待 时 间 与 享受 服 务 的 时 间 成 比 例 。 在 RR中 ， 需 要 将 CPU的 处 理 时 间 分 成 固 定 大小 的 时 间 片 。 如 果 一 个 进 程 在 被 调 度 选 中 之 后用 完 了 系 统 规 定 的 时 间 片 ， 但 又 未 完 成 要 求 的任 务 ， 则 它 自 行 释 放 自 己 所 占 有 的 CPU而 排 到就 绪 队 列 的 末 尾 ， 等 待 下 一 次 调 度 。 同 时 ， 进 程 调 度 程 序 又 去 调 度 当 前 就 绪 队 列 中的 第 一 个 进 程 。 5 优 先 权 调 度 算 法 HPF的 核 心 是 确 定 进 程 的 优 先 级 。 确 定 优 先 级 的 方 法 可 分 为 静 态 法 和 动 态 法 。静 态 法 根 据 进 程 的 静 态 特 性 ， 在 进 程 开 始 执行 之 前 就 确 定 它 们 的 优 先 级 ， 一 旦 开 始 执 行之 后 就 不 能 改 变 。 动 态 法 把 进 程 的 静 态 特 性 和 动 态 特 性 结 合 起来 确 定 进 程 的 优 先 级 ， 随 着 进 程 的 执 行 过 程， 其 优 先 级 不 断 变 化 。 基 于 静 态 优 先 级 的 调 度 算 法 优 点 ： 实 现 简 单 ， 系 统 开 销 小 缺 点 ： 静 态 优 先 级 一 旦 确 定 之 后 ， 直到 执 行 结 束 为 止 始 终 保 持 不 变 ， 从 而 系统 效 率 较 低 ， 调 度 性 能 不 高 。 现 在 的 操 作 系 统 中 ， 大 多 采 用 动 态 优先 级 的 调 度 策 略 。 基 于 动 态 优 先 级 的 调 度 算 法 (1)根 据 进 程 占 有 CPU时 间 的 长 短 来 决定 。 一 个 进 程 占 有 处 理 机 的 时 间 愈 长， 则 在 被 阻 塞 之 后 再 次 获 得 调 度 的 优先 级 就 越 低 。 反 之 ， 其 获 得 调 度 的 可能 性 就 会 越 大 。 (2)根 据 就 绪 进 程 等 待 CPU的 时 间 长 短来 决 定 。 一 个 就 绪 进 程 在 就 绪 队 列 中等 待 的 时 间 越 长 ， 则 它 获 得 调 度 选 中的 优 先 级 就 越 高 。 2.6.3 作 业 调 度 作 业 是 指 用 户 在 一 次 计 算 过 程 或 者 事 务 处 理过 程 中 ， 要 求 计 算 机 系 统 所 作 工 作 的 集 合 。 作 业 调 度 是 从 后 备 作 业 队 列 中 选 择 若 干 个 作业 ， 为 它 们 分 配 必 要 的 资 源 ， 将 它 们 调 入 主存 ， 为 它 们 建 立 进 程 ， 使 它 们 成 为 就 绪 进 程的 过 程 。 这 涉 及 到 作 业 所 处 的 状 态 、 作 业 调度 以 及 调 度 算 法 。 1、 作 业 调 度 采 用 的 数 据 结 构 为 了 管 理 和 调 度 作 业 ， 系 统 为 每 个 作 业 设置 一 个 作 业 控 制 块 （ JCB） 。 JCB 是 在 作 业 进 入 系 统 时 由 SPOOLING系统 为 其 建 立 的 。 其 内 容 由 作 业 控 制 卡 （ 说明 书 ） 中 得 到 的 。 JCB是 作 业 存 在 系 统 的标 志 ， 作 业 进 入 系 统 时 ， 则 为 之 建 立 JCB， 当 作 业 退 出 时 ， 则 其 JCB也 被 撤 销 。 作 业 名资 源 要 求资 源 使 用 情 况类 型 级 别优 先 级 状 态 要 求 的 运 行 时 间 、 使 用 语 言最 迟 完 成 时 间 、 要 求 的 主 存 量要 求 外 设 类 型 、 台 数要 求 的 文 件 量 和 输 出 量进 入 系 统 时 间开 始 运 行 时 间已 运 行 时 间主 存 地 址外 设 台 号控 制 方 式 作 业 类 型优 先 数 作 业 控 制 表 JCB SPOOLING系 统 SPOOLING又 称 为 外 围 设 备 同 时 联 机 操 作 。在 SPOOLING系 统 中 ， 多 台 外 围 设 备 通 过 通道 或 DMA器 件 和 主 机 与 外 存 连 接 起 来 。 在 硬盘 中 开 辟 一 块 输 入 /输 出 井 ， 并 将 多 个 用 户 作业 随 机 的 存 储 提 取 ， 各 用 户 间 互 不 干 扰 。 系 统 中 的 输 入 程 序 包 含 两 个 独 立 的 过 程 ， 一个 过 程 负 责 从 外 部 设 备 把 信 息 读 入 缓 冲 区 ；另 一 个 是 写 过 程 ， 负 责 把 缓 冲 区 的 信 息 送 到外 存 输 入 井 中 。 2、 作 业 调 度 与 进 程 调 度 的 关 系作 业 调 度 与 进 程 调 度 的 关 系 用 户 作 业 录 入 提 交 收 容 完 成运 行 就 绪 阻 塞等 待I/OI/O完 成进 程 调 度 作 业 调 度 执 行 作 业 调 度 3、 常 用 的 作 业 调 度 算 法 作 业 调 度 程 序 要 完 成 以 下 工 作 ：(1) 按 照 某 种 调 度 算 法 从 后 备 作 业 队 列 中 挑 选 作 业(2) 为 选 中 的 作 业 分 配 主 存 和 外 设 资 源 。(3) 为 选 中 的 作 业 建 立 相 应 的 进 程 。(4) 构 造 和 填 写 作 业 运 行 时 所 需 的 有 关 表 格 。(5) 作 业 结 束 时 完 成 该 作 业 的 善 后 处 理 工 作 ， 如 收回 资 源 ， 输 出 必 要 的 信 息 ， 撤 消 该 作 业 的 全 部 进程 (PCB) 和 作 业 控 制 块 JCB。 调 度 原 则 ： 公 平 ， 合 理 ， 使 用 户 满 意 提 高 系 统 资 源 利 用 率 ， 如 提 高 系 统 吞 吐 量 作 业 调 度 算 法 的 评 价 因 素 作 业 吞 吐 量 ： 运 行 尽 可 能 多 的 作 业 ； 充 分 利 用 资 源 ： CPU忙 、 I/O设 备 忙 ； 对 各 作 业 公 平 、 合 理 ， 使 用 户 满 意 ： 执 行 时 间 长 短 、等 待 时 间 等 ；（ 1） 选 择 作 业 调 度 算 法 应 考 虑 的 因 素 （ 2） 常 用 的 作 业 调 度 算 法 FCFS按 作 业 到 达 系 统 的 先 后 次 序 进行 调 度 。 该 算 法 优 先 考 虑 在 系 统 中 等待 时 间 最 长 的 作 业 ， 而 不 考 虑 作 业 运行 时 间 的 长 短 。 1.先 来 先 服 务 调 度 算 法 先 来 先 服 务 调 度 算 法由 此 ： 此 作 业 流 的 平 均 周 转 时 间 为 T (2.0+1.5+1.2+1.5)/4=1.55h，此 作 业 流 的 平 均 周 转 时 间 为 W (1.0+3.0+6.0+3.75)/4=3.4375h 注 ： 通 过 以 上 分 析 ， 显 然 ， 这 种 算 法 容 易 实 现 ， 但 效 率 很低 。 2.短 作 业 优 先 调 度 算 法 SJF 总 是 从 作 业 的 后 备 队 列 中 挑 选 运行 时 间 最 短 的 作 业 ， 作 为 下 个 调 度运 行 的 对 象 。 短 作 业 优 先 调 度 算 法由 此 ： 此 作 业 流 的 平 均 周 转 时 间 为 T (2.0+2.1+0.7+1.0)/4=1.45h，此 作 业 流 的 平 均 周 转 时 间 为 W (1.0+4.2+3.5+2.5)/4=2.8h注 ： 通 过 以 上 分 析 ， 虽 然 这 种 算 法 易 于 实 现 ， 且 效 率 也比 较 高 ， 但 未 考 虑 长 作 业 的 利 益 。 FCFS和 SPF存 在 的 问 题 先 来 先 服 务 调 度 算 法 只 考 虑 了 作 业 的 等 待时 间 ， 而 忽 略 了 作 业 的 运 行 时 间 ， 对 短 作业 不 利 ； 短 作 业 优 先 调 度 算 法 只 考 虑 了 作 业 运 行 时间 的 长 短 ， 而 忽 略 了 作 业 的 等 待 时 间 ， 对运 行 时 间 长 的 作 业 不 利 ， 因 为 如 果 始 终 有短 作 业 进 入 系 统 ， 则 较 长 作 业 会 长 时 间 得不 到 调 度 。 3.响 应 比 高 者 优 先 调 度 算 法 HRRN是 在 每 次 调 度 作 业 运 行 时 ， 先 计算 后 备 作 业 队 列 中 每 个 作 业 的 响 应 比 ，然 后 挑 选 响 应 比 最 高 者 投 入 运 行 。 HRRN既 考 虑 了 作 业 的 等 待 时 间 又 考虑 了 作 业 的 运 行 时 间 的 调 度 算 法 ， 响 应 比 高 者 优 先 调 度 算 法 R 作 业 的 响 应 时 间 作 业 的 运 行 时 间 作 业 的 响 应 时 间 作 业 的 等 待 时 间 作 业的 运 行 时 间 作 业 的 响 应 比 为 ： R 1 作 业 的 等 待 时 间 作 业 的 运 行 时 间 。 一 个 作 业 的 响 应 比 随 着 等 待 时 间 的 增 加 而提 高 。 在 相 同 等 待 时 间 的 情 况 下 ， 短 作 业优 先 ， 而 对 于 相 同 运 行 时 间 的 作 业 ， 等 待时 间 长 的 作 业 优 先 运 行 。 响 应 比 高 者 优 先 调 度 算 法 由 于 作 业 1的 开 始 时 间 是 5： 00， 而 其 余 作业 均 未 到 达 ， 故 先 运 行 作 业 1。 当 作 业 1运行 完 毕 ， 计 算 后 备 队 列 中 作 业 2， 3， 4的 响应 比 。 按 照 以 上 的 定 义 和 计 算 公 式 ， 计 算如 下 ： 作 业 2:R=(60+30)/30=3 作 业 3:R=(30+12)/12=3.5 作 业 4:R=(24+24)/24=2 可 见 ， 作 业 3的 响 应 比 最 高 ， 选 择 作 业 3运 行 ， 故表 2-3中 作 业 3的 开 始 时 间 为 作 业 1的 完 成 时 间 ，即 7:00， 当 作 业 3运 行 完 毕 ， 计 算 后 备 队 列 中 作业 2， 4的 响 应 比 ， 计 算 如 下 ： 作 业 2:R=(72+30)/30=3.4 作 业 4:R=(36+24)/24=2.5 显 然 ， 这 次 应 该 选 择 作 业 2， 故 表 2-3中 作 业 2的开 始 时 间 为 作 业 3的 完 成 时 间 ， 即 7:12， 最 后 运行 作 业 4。 故 作 业 运 行 的 次 序 为 ： 1， 3， 2， 4。 由 此 ： 此 作 业 流 的 平 均 周 转 时 间 为 T (2.0+1.7+0.7+1.5)/4=1.475h，此 作 业 流 的 平 均 周 转 时 间 为 W (1.0+3.4+3.5+3.75)/4=2.9125注 ： 通 过 以 上 分 析 ， 这 种 算 法 既 考 虑 了 作 业 的 等 待时 间 ， 也 考 虑 了 作 业 的 运 行 时 间 ， 是 一 种 比 较 理想 的 调 度 算 法 。 但 这 种 算 法 复 杂 ， 而 且 需 要 动 态计 算 某 一 作 业 完 成 时 刻 后 备 队 列 中 每 个 作 业 的 响应 比 ， 增 加 了 系 统 的 开 销 。 4.优 先 权 调 度 算 法 根 据 作 业 的 优 先 数 调 度 作 业 进 入 系 统运 行 。 为 每 个 作 业 确 定 一 个 优 先 数 ，资 源 能 满 足 且 优 先 数 高 的 作 业 优 先 被选 中 ， 当 几 个 作 业 有 相 同 的 优 先 数 时， 对 这 些 具 有 相 同 优 先 数 的 作 业 再 按照 先 来 先 服 务 原 则 进 行 调 度 。 实 例 解 析 【 例 】 系 统 中 有 四 个 作 业 同 时 到 达 ， 它 们的 运 行 时 间 和 优 先 数 如 表 2-9所 示 ， 若 使 用优 先 权 调 度 算 法 时 ， 作 业 的 平 均 周 转 时 间为 多 少 ？ 分 析 ： 优 先 权 调 度 算 法 中 规 定 作 业 的 优 先数 越 高 ， 则 该 作 业 在 运 行 的 次 序 中 越 靠 前， 所 以 本 例 四 个 作 业 的 运 行 次 序 为 1， 3， 4， 2。 实 例 解 析解 ： 由 表 2-9作 业 的 优 先 数 得 作 业 运 行 次 序 为 1， 3， 4， 2，故 该 批 作 业 的 平 均 周 转 时 间 为 ： T (3) +(3+7) +(3+7+2) +(3+7+2+5)/4=42/4=10.5 5.均 衡 调 度 算 法 这 种 调 度 算 法 根 据 作 业 对 资 源 的 要 求 进 行 分 类 ， 作业 调 度 从 各 类 作 业 中 挑 选 ， 尽 可 能 地 使 使 用 不 同 资源 的 作 业 同 时 执 行 。 这 样 不 仅 可 以 使 系 统 中 的 不 同类 型 的 资 源 都 在 被 使 用 ， 而 且 可 以 减 少 作 业 等 待 使用 相 同 资 源 的 时 间 ， 从 而 加 快 作 业 的 执 行 。 有 的 系 统 还 对 每 一 类 中 的 各 作 业 确 定 优 先 数 ， 作 业调 度 时 在 每 类 作 业 中 再 按 优 先 数 高 者 优 先 的 调 度 原则 选 择 作 业 。 这 样 ， 既 能 使 各 类 作 业 都 得 到 照 顾 ，又 能 照 顾 同 类 作 业 中 的 紧 迫 作 业 。