北方工业大学操作系统操作系统期末复习

操 作 系 统 期 末 复 习Made by Tzh 第 一 部 分 ： 大 题 本 部 分 为 课 上 老 师 所 讲 的 几 道 大 题 ， 作 为大 题 而 言 命 中 率 应 该 蛮 高 的 吧 ， 它 们 包 括 ： 资 源 分 配 图 硬 盘 调 度 页 面 置 换 算 法 PB操 作 物 理 地 址 替 换 1 .资 源 分 配 图 会 看 、 会 画 会 判 断 死 锁 P1P2r1 r2 会 看 、 会 画 P1P23 个 资 源2 个 资 源P1 进 程P1 进 程 请 求 资 源进 程 拥 有 资 源 P1 拥 有 2 个 r1 资 源 并 请 求 1 个 r2P2 拥 有 1 个 r1 资 源 和 1 个 r2 资 源 并 请 求 1 个 r1r1 r2 判 断 死 锁P1P2P1 需 要 1 个 r2 P2 需 要 1 个 r1R1 剩 余 0 个 资 源 R2 剩 余 1 个 资 源 P2 的 需 求 无 法 满 足 ， 但 P1 可 以 得 到 满 足P1P2 P2 需 要 1 个 r1R1 剩 余 2 个 资 源 R2 剩 余 1 个 资 源P1 顺 利 执 行 ， 释 放 占 用 所 有 资 源 P2 需 求 得 到 满 足 ， 顺 利 执 行P1P2R1 剩 余 3 个 资 源 R2 剩 余 2 个 资 源在 这 种 情 况 下 不 会 死 锁 那 么 ， 什 么 情 况 下 会 产 生 死 锁 呢P1P2P1 需 要 2 个 r2 P2 需 要 1 个 r1R1 剩 余 0 个 资 源 R2 剩 余 1 个 资 源此 时 ， P1 、 P2 的 需 求 都 无 法 得 到 满 足 ， 死 锁 2 .磁 盘 调 度想 象 ， 从 磁 盘 圆 心 处 向 外 画 一 条 直 线 作 为 我 们 下 图 的 X轴 ， 把 磁 盘 的 磁 道 序 号 标 在 上 面 。 题 目 是 这 样 出 的 条 件 ： 欲 访 问 的 磁 道 号 ： 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 头 当 前 位 置 ： 1 0 0 问 题 ： 磁 头 移 动 磁 道 数 和 平 均 寻 道 长 度 1 .先 来 先 服 务 算 法 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 我 们 从 起 始 位 置 开 始 ， 按 顺 序 扫 描 ， 设 磁 头 移 动 磁 道 数 为 m， 初 始 为 0 1 0 0 、 5 5 、 5 8 、 3 9 、 1 8 、 9 0 、 1 6 0 、 1 5 0 磁 头 移 动 到 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 磁 头 移 动 到 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 磁 头 移 动 到 3 9 ， m+=(5 8 -3 9 ),m=6 7 注 意 ： 磁 头 移 动 的 是 距 离 而 不 是 位 移 ， 所 以 不 可 能 为 负 数 ， 因 此 一 定 是 大 减 小 以 此 类 推 ， 直 到 全 部 扫 描 完 当 然 ， 如 果 是 答 题 ， 我 们 直 接 列 式 子 即 可 m=(1 0 0 -5 5 )+(5 8 -5 5 )+(5 8 -3 9 )+.=结 果 平 均 寻 道 长 度 =m/n n为 磁 道 号 个 数 2 .最 短 寻 道 时 间 优 先 算 法 为 了 节 约 时 间 ， 这 次 我 们 不 再 按 照 顺 序 来 扫 描 磁 盘 了 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 最 近 的 磁 道 是 哪 个 这 也 是 我 们 之 所 以 要 排 序 的 原 因 ， 在 这 种 情 况 下 只 有 1 0 0 相 邻 的 两 个磁 道 可 能 是 我 们 的 选 择 我 们 发 现 ， 相 比 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 以 此 类 推 ， 知 道 将 所 有 磁 道 跑 完 当 然 ， 跑 过 的 磁 道 我 们 不 会 跑 第 二 遍 我 猜 你 可 能 会 问 :这 真 的 是 最 短 的 寻 道 时 间 吗 ？当 然 ， 答 案 肯 定 是 不 一 定 ， 计 算 机 只 能 看 到 下 一 步 的 情 况 ，但 它 不 可 能 像 围 棋 高 手 一 样 总 览 全 局 ， 至 于 真 正 的 最 短 ，那 就 是 我 们 程 序 员 写 的 算 法 才 能 够 实 现 了 ， 在 操 作 系 统 中 不 会 这 么 复 杂 3 .扫 描 算 法 （ 电 梯 算 法 ） 没 错 ， 就 像 是 电 梯 一 样 ， 直 上 直 下 ， 一 条 道 走 到 黑 ， 撞 了 南 墙 再 回 头 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 咚 ！ 撞 墙 了 ， 这 时 可 以 回 头 了 ， 但 注 意 寻 过 道 的 磁 道 不 需 要 再 走 一 遍 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 分 页 存 储 求 物 理 地 址 指 令 ： Load 1 ,2 5 0 0 指 令 的 逻 辑 地 址 是 1 0 0 ， 页 长 1 k， 求 指 令 的 物 理 地 址 1 .求 页 号 逻 辑 地 址 /页 长 ， 商 为 页 号 ， 余 数 为 偏 移 量 2 .查 表 3 .物 理 地 址 =物 理 块 号 *页 长 +偏 移 量页 号 物 理块 号0 41 82 7取 了 两 次 地 址 ， 第 一 次 根 据 逻 辑 地 址 找 到 物 理 地 址 ， 第 二 次 取 物 理 地 址 页 面 置 换 算 法 如 果 给 的 是 逻 辑 地 址 需 要 求 出 页 号 页 号 =逻 辑 地 址 /页 长 （ 要 的 是 商 ） 先 进 先 出 （ FIFO）将 页 号 依 次 排 好 方 法一 开 始 是 依 次 装 入 物 理 块 ， 全 都 有 缺 页 中 断 方 法如 果 物 理 块 满 了 ， 判 断 哪 个 页 面 存 在 时 间 最 长 就 替 换 方 法 是 向 左 划 线 判 断 哪 条 最 长 ， 同 时 缺 页 中 断 方 法如 果 下 一 个 页 面 物 理 块 已 经 有 了 ， 就 不 用 写 了 ， 也 没 有 缺 页 中 断 最 近 最 久 未 使 用 （ LRU） 方 法 往 前 数 第 三 个 来 替 换 （ 有 几 个 物 理 块 找 几 个 ） ， 但 不 算 重 复 的 ， 有 重 复 的 还 要 往 前 找 要 计 算 的 东 西 缺 页 次 数 ： 每 一 次 页 面 替 换 和 页 面 装 入 （ 画 的 对 勾 数 ） 被 置 换 的 页 号 顺 序 ： 被 替 换 走 的 页 号 按 顺 序 排 列 缺 页 率 =缺 页 次 数 /页 面 总 数 生 产 者 消 费 者 问 题 他 们 又 是 互 斥 关 系 ， 又 是 相 互 协 作 关 系 ， 也 是 同 步 关 系 解 法 P操 作 ， 也 可 以 是 wait操 作 是 -， 只 有 参 数 大 于 0 才 可 以 顺 利 执 行V操 作 ， 也 可 以 是 signal操 作 是 +， 相 当 于 是 恢 复 例 题2 . 假 定 一 个 阅 览 室 可 供 5 0 个 人 同 时 阅 读 。 读 者 进 入 和 离 开 阅 览 室 时 都 必 须 在 阅 览 室 入 口处 的 一 个 登 记 表 上 登 记 ， 阅 览 室 有 5 0 个 座 位 ， 规 定 每 次 只 允 许 一 个 人 登 记 或 注 销 登 记 。要 求 ：（ 1 ） 用 PV操 作 描 述 读 者 进 程 的 实 现 算 法 （ 可 用 流 程 图 表 示 ， 登 记 、 注 销 可 用 自 然 语 言 描述 ） ； （ 2 ） 指 出 算 法 中 所 用 信 号 量 的 名 称 、 作 用 及 初 值 。 解 S1 :阅 览 室 可 供 使 用 的 空 座 位 ， 其 初 值 为 5 0 S: 是 否 可 通 过 阅 览 室 ， 其 初 值 为 1 Process READ_in（ i=1 5 0 ） 到 达 阅 览 室 入 口 处 ;P(S1 );P(S); 在 入 口 处 登 记 座 位 号 ; V(s); 进 入 座 位 并 阅 读 ; Process READ_out（ j=1 5 0 ） 结 束 阅 读 到 达 阅 览 室 入 口 处 ; P(S); 在 入 口 处 注 销 座 位 号 ; V(S1 );V(S) 离 开 入 口 处 ; 例 题请 用 信 号 量 实 现 下 图 所 示 的 前 趋 关 系 调 度 算 法 运 算 方 法 完 成 时 间 ： 就 是 目 前 的 完 成 时 间 加 上 下 一 个 要 运 行 的 进 程 的 服 务 时 间 周 转 时 间 ： 各 进 程 的 完 成 时 间 减 去 其 到 达 的 时 间 带 权 周 转 时 间 ： 周 转 时 间 /服 务 时 间 高 响 应 比 优 先 调 度 算 法 先 算 出 优 先 权 再 进 行 比 较 ， 先 运 行 大 的 再 运 行 小 的 优 先 权 =（ 等 待 时 间 +要 求 服 务 时 间 ） /要 求 服 务 时 间 等 待 时 间 ： 该 进 程 要 开 始 进 行 的 时 候 总 共 经 过 的 时 间 概 念 题 本 部 分 为 课 上 老 师 在 书 中 所 划 的 概 念 操 作 系 统 的 目 标 有 效 性 提 高 系 统 资 源 利 用 率 提 高 系 统 的 吞 吐 量 吞 吐 量 是 每 秒 的 数 据 处 理 量 吞 吐 量 是 在 给 定 时 间 段 内 系 统 完 成 的 交 换 数 量 .即 系 统 的 吞 吐 量 越 大 ,说明 系 统 在 单 位 时 间 内 完 成 的 用 户 或 系 统 请 求 越 多 ,系 统 的 资 源 得 到 充 分 利 用 。 方 便 性 可 扩 充 性 开 放 性 操 作 系 统 的 作 用 用 户 接 口 ： OS处 于 用 户 与 计 算 机 硬 件 系 统 之 间 ， 用 户 通 过 OS来 使 用 计算 机 系 统 操 作 系 统 接 口 包 括 ： 1 .命 令 方 式 2 .系 统 调 用 方 式 3 .图 形 、 窗 口 方 式 计 算 机 系 统 资 源 的 管 理 者 ： OS 推 动 操 作 系 统 发 展 主 要 动 力 ： 1 .提 高 计 算 机 资 源 的 利 用 率 2 .方 便 用 户 3 .器 件 升 级 操 作 系 统 的 发 展 过 程 人 工 操 作 方 式 缺 点 ： 1 .用 户 独 占 全 机 2 .CPU等 待 人 工 操 作 脱 机 输 入 /输 出 方 式 优 点 ： 1 .减 少 了 CPU的 空 闲 时 间 2 .提 高 了 I/O速 度 批 处 理 系 统 （ 无 交 互 能 力 ） 单 道 批 处 理 系 统 多 道 批 处 理 系 统 (宏 观 并 行 ， 微 观 串 行 ) 优 点 ： 1 .资 源 利 用 率 高 2 .系 统 吞 吐 量 大 缺 点 ： 1 .平 均 周 转 时 间 长 2 .无 交 互 能 力 面 临 问 题 ： 1 .处 理 机 管 理 问 题 2 .内 存 管 理 问 题 3 .I/O设 备 管 理 问 题 4 .文 件 管 理 问 题 5 .作 业 管 理 问 题 分 时 系 统 定 义 ： 它 能 很 好 地 将 一 台 计 算 机 提 供 给 多 个 用 户 同 时 使 用 ， 提 高 计 算机 的 利 用 率 。 用 户 的 需 求 具 体 表 现 在 ： 1 .人 -机 交 互 2 .共 享 主 机 3 .便 于 用 户 上 机 关 键 问 题 ： 1 .用 户 是 否 能 及 时 接 收 命 令 2 .用 户 是 否 能 及 时 处 理 命 令 特 点 ： 多 路 性 独 立 性 及 时 性 交 互 性 实 时 系 统 硬 实 时 与 软 实 时 的 区 别 硬 实 时 系 统 有 一 个 刚 性 的 、 不 可 改 变 的 时 间 限 制 ， 它 不 允 许 任 何 超 出时 限 的 错 误 。 超 时 错 误 会 带 来 损 害 甚 至 导 致 系 统 失 败 、 或 者 导 致 系 统 不 能 实 现 它 的 预 期 目 标 。 软 实 时 系 统 的 时 限 是 一 个 柔 性 灵 活 的 ， 它 可以 容 忍 偶 然 的 超 时 错 误 。 失 败 造 成 的 后 果 并 不 严 重 ， 例 如 在 网 络 中 仅仅 是 轻 微 地 降 低 了 系 统 的 吞 吐 量 。 分 时 系 统 与 实 时 系 统 的 比 较 1 .多 路 性 ： 分 时 系 统 的 多 路 性 与 用 户 情 况 有 关 ， 时 多 时 少 。 实 时 控 制系 统 的 多 路 性 则 主 要 表 现 在 系 统 周 期 性 地 对 多 路 现 场 信 息 进 行 采 集 ，以 及 对 多 个 对 象 或 多 个 执 行 机 构 进 行 控 制 2 .独 立 性 ： 都 是 服 务 请 求 彼 此 互 不 干 扰 3 .及 时 性 :实 时 系 统 及 时 性 要 求 更 强 4 .交 互 性 ： 实 时 系 统 的 人 与 系 统 的 交 互 仅 限 于 访 问 系 统 中 某 些 特 定 的专 用 服 务 程 序 ， 交 互 性 分 时 系 统 更 强 5 .可 靠 性 ： 实 时 系 统 要 求 更 可 靠 操 作 系 统 基 本 特 性 并 发 性 ： 并 行 性 和 并 发 性 是 既 相 似 又 有 区 别 的 两 个 概 念 ， 并 行 性 是 指两 个 或 多 个 事 件 在 同 一 时 刻 发 生 ； 而 并 发 性 是 指 两 个 或 多 个 事 件 在 同一 时 间 间 隔 内 发 生 。 共 享 性 ： 是 指 系 统 中 的 资 源 可 供 内 存 中 多 个 并 发 执 行 的 进 程 (线 程 )共同 使 用 虚 拟 性 ： 是 指 通 过 某 种 技 术 把 一 个 物 理 实 体 变 为 若 干 个 逻 辑 上 的 对 应物 。 物 理 实 体 (前 者 )是 实 的 ， 即 实 际 存 在 的 ， 而 后 者 是 虚 的 ， 是 用 户感 觉 上 的 东 西 。 异 步 性 ： 每 次 只 允 许 一 个 进 程 执 行 ， 其 余 进 程 只 能 等 待 。 操 作 系 统 的 主 要 功 能 处 理 机 管 理 功 能 1 .进 程 控 制 ： 为 作 业 创 建 进 程 ， 撤 销 已 结 束 的 进 程 ， 控 制 进 程 在 运 行过 程 中 的 状 态 转 化 2 .进 程 同 步 ： 互 斥 与 同 步 方 式 来 协 调 多 个 进 程 （ 含 线 程 ） 3 .进 程 通 信 方 式 ： 采 用 直 接 通 信 方 式 ， 由 源 进 程 利 用 发 送 命 令 将 信 息挂 到 目 标 进 程 的 消 息 队 列 ， 之 后 由 目 标 进 程 接 收 。 4 .调 度 ： 作 业 调 度 （ 高 级 调 度 ） ： 从 后 备 队 列 中 通 过 一 定 算 法 找 出 若 干 个 作 业并 为 它 们 分 配 内 存 ， 建 立 进 程 ， 插 入 就 绪 队 列 。 进 程 调 度 （ 低 级 调 度 ） ： 从 就 绪 队 列 中 选 出 一 个 进 程 ， 使 该 进 程 投 入执 行 操 作 系 统 的 主 要 功 能 存 储 器 管 理 功 能 1 .内 存 分 配 ： 为 每 道 程 序 分 配 内 存 空 间 （ 静 态 、 动 态 ） 2 .内 存 保 护 ： 使 各 程 序 执 行 时 彼 此 互 不 干 扰 3 .地 址 映 射 ： 逻 辑 地 址 到 物 理 地 址 之 间 的 转 换 4 .内 存 扩 充 ： 借 助 虚 拟 存 储 （ 1 ） ： 请 求 调 入 功 能 ： 在 装 入 部 分 用 户 程 序 和 数 据 的 情 况 下 就 执 行 ，中 途 向 OS请 求 从 磁 盘 将 所 需 调 入 内 存 （ 2 ） ： 将 内 存 中 一 些 暂 时 不 用 的 数 据 调 入 硬 盘 腾 出 空 间 操 作 系 统 的 主 要 功 能 设 备 管 理 功 能 1 .缓 冲 管 理 ： CPU与 I/O之 间 甚 至 缓 冲 区 ， 解 决 速 度 不 匹 配 的 问 题 单 缓 冲 机 制 、 可 双 向 传 送 的 双 缓 冲 机 制 、 提 供 多 个 设 备 同 时 使 用 的 公用 缓 冲 池 机 制 2 .设 备 分 配 ： 根 据 用 户 的 I/O请 求 ， 为 其 分 配 所 需 设 备 3 .设 备 处 理 ： CPU与 I/O之 间 的 通 信 操 作 系 统 的 主 要 功 能 文 件 管 理 功 能 1 .文 件 存 储 空 间 的 管 理 2 .目 录 管 理 ： 系 统 为 每 个 文 件 建 立 一 个 目 录 项 ， 包 括 ： 文 件 名 、 文 件 属 性 、 文 件 在 磁 盘 上 的 物 理 位 置 3 .文 件 的 读 /写 管 理 ： 根 据 用 户 给 出 的 文 件 名 检 索 文 件 目 录 ， 从 中 获 得文 件 在 外 存 中 的 位 置 。 4 .文 件 保 护 ： 操 作 系 统 给 应 用 的 接 口 程 序 接 口 也 称 为 系 统 调 用库 函 数 属 于 用 户 程 序 而 非 系 统 调 用 ， 是 系 统 调 用 的 上 层 ， 有 些 库 函 数 与 系 统 调 用 是 无 关 的（ math.h）所 谓 原 语 ， 是 操 作 系 统 内 核 中 ， 由 若 干 条 指 令 构 成 、 用 于 完 成 一 个 特 定 的 功 能 的 一 个 过 程 ，该 过 程 在 执 行 时 是 不 可 中 断 的 。 微 内 核 系 统 （ 不 含 LINUX） 优 点 1 .提 高 系 统 可 扩 展 性 2 .提 高 系 统 可 靠 性 3 .可 移 植 性 4 .提 供 了 对 分 布 式 系 统 的 支 持 5 .融 入 了 面 向 对 象 技 术 缺 点 ： 运 行 效 率 低 硬 中 断 ： 由 与 系 统 相 连 的 外 设 (比 如 网 卡 、 硬 盘 )自 动 产 生 的 。 主 要 是用 来 通 知 操 作 系 统 系 统 外 设 状 态 的 变 化 微 内 核 中 断 和 陷 入 处 理 （ 软 中 断 ） 将 与 硬 件 紧 密 相 关 的 一 小 部 分 放 在 微 内 核 中 处 理 ， 微 内 核 所 做 的 就 只是 前 期 处 理 ， 将 消 息 发 给 服 务 器 由 服 务 器 再 进 行 后 期 处 理 ， 因 此 微 内 核 可 以 做 的 很 小 。 进 程 的 顺 序 执 行 顺 序 执 行 （ 适 合 直 接 访 问 ） ： 例 如 输 入 与 打 印 ， 必 须 按 顺 序 前 趋 图 ： 有 向 无 环 图 进 程 由 创 建 而 产 生 ， 由 调 度 而 执 行 ， 由 撤 销 而 消 亡 进 程 的 并 发 执 行 程 序 的 并 发 执 行 ： 多 道 程 序 可 同 时 进 行 ， 但 对 于 每 一 道 程 序 而 言 是 顺序 执 行 。 程 序 并 发 执 行 的 特 征 ： 1 .间 断 性 ： 一 个 任 务 可 能 需 要 等 待 它 的 前 驱 任 务 完 成 才 能 继 续 执 行 ，产 生 等 待 。 2 .失 去 封 闭 性 ： 多 个 程 序 共 享 系 统 中 资 源 ， 这 些 资 源 将 由 多 个 程 序 来改 变 。 3 .不 可 再 现 性 ： 由 于 失 去 封 闭 性 ， 输 入 的 结 果 与 并 发 程 序 的 速 度 有 关 ，每 一 次 的 输 出 结 果 不 同 。 进 程 特 征 和 状 态 1 .结 构 特 征 ： 进 程 实 体 （ 在 UNIX中 称 为 “进 程 映 像 ”） 程 序 段 相 关 数 据 段 PCB： 作 用 寄 存 器 有 什 么 ， 进 程 的 唯 一 标 识 动 态 性 ： 进 程 是 程 序 的 一 次 执 行 过 程 ， 它 有 一 定 的 生 命 期 并 发 性 ： 多 个 进 程 同 时 进 行 独 立 性 ： 进 程 实 体 独 立 异 步 性 ： 进 程 各 自 独 立 ， 速 度 不 一 2 .进 程 的 状 态 许 可 释 放 进 程 控 制 块 （ PCB） 进 程 控 制 块 组 织 方 式 ： 1 .链 接 方 式 按 进 程 优 先 级 高 低 排 列 隐 式 链 接 最 不 适 合 直 接 访 问 执 行 指 针 就 一 个 链 接 字 2 .索 引 表 方 式 进 程 控 制 进 程 的 创 建 ： 1 .申 请 空 白 PCB 2 .为 新 进 程 分 配 资 源 3 .初 始 化 进 程 控 制 块 （ PCB） 4 .将 新 进 程 插 入 就 绪 队 列 终 止 过 程 ： 1 .通 过 该 进 程 PCB读 出 该 进 程 的 状 态 2 .结 束 该 进 程 的 执 行 3 .结 束 该 进 程 的 子 孙 进 程 4 .释 放 该 进 程 占 有 的 资 源 5 .将 被 终 止 进 程 从 所 在 队 列 移 出 进 程 阻 塞 与 唤 醒 进 程 的 阻 塞 ： 进 程 由 于 某 些 原 因 无 法 继 续 进 行 ， 进 程 调 用 阻 塞 源 语 自己 把 自 己 阻 塞 ， 从 执 行 状 态 变 为 阻 塞 状 态 。 阻 塞 原 因 ： 1 .请 求 系 统 服 务 未 得 到 响 应 。 2 .启 动 某 种 操 作 （ 操 作 完 成才 可 继 续 执 行 ） 。 3 .新 数 据 尚 未 到 达 。 4 .无 新 工 作 可 做 进 程 的 唤 醒 （ 与 阻 塞 互 逆 ） ： 当 进 程 所 期 望 的 事 件 出 现 ， 便 自 己 调 用唤 醒 源 语 ， 将 自 己 从 阻 塞 队 列 移 出 ， 到 就 绪 队 列 。 挂 起 ： 由 用 户 或 父 进 程 引 起 激 活 （ 与 挂 起 互 逆 ） ： 由 用 户 或 父 进 程 引 起 进 程 同 步 互 斥 临 界 区 ： 每 个 进 程 访 问 临 界 资 源 的 那 段 代 码 称 为 临 界 区 临 界 资 源 （ 硬 件 资 源 如 打 印 机 等 ） ： 在 一 段 时 间 内 只 允 许 一 个 进 程 访问 的 资 源 ， 临 界 资 源 的 访 问 要 求 互 斥 的 访 问 进 程 互 斥 ： 一 个 进 程 正 在 访 问 临 界 资 源 ， 另 一 个 要 访 问 该 资 源 的 进 程必 须 等 待 。 但 互 斥 无 法 限 制 访 问 者 对 资 源 的 访 问 顺 序 ， 即 访 问 是 无 序的 。 进 程 同 步 ： 是 指 在 互 斥 的 基 础 上 （ 大 多 数 情 况 ） ， 通 过 其 它 机 制 实 现访 问 者 对 资 源 的 有 序 访 问 。 在 大 多 数 情 况 下 ， 同 步 已 经 实 现 了 互 斥 ，特 别 是 所 有 写 入 资 源 的 情 况 必 定 是 互 斥 的 。 少 数 情 况 是 指 可 以 允 许 多个 访 问 者 同 时 访 问 资 源 同 步 机 制 规 则 1 .空 闲 让 进 2 .忙 则 等 待 3 .有 限 等 待 ： 不 能 让 进 程 一 直 等 ， 得 一 段 时 间 内 能 得 到 临 界 资 源 4 .让 权 等 待 ： 进 程 如 果 不 能 进 入 临 界 区 ， 就 别 等 了 信 号 量 1 .整 型 信 号 量 ： wait（ S） ， signal（ S） S为 整 型 信 号 量 ， 初 值 为 1 ， 当 前 为 2 代 表 有 两 个 资 源 ， 当 前 为 0 代 表 被占 用 ， 当 前 为 -1 代 表 已 经 有 一 个 等 待 2 .记 录 型 信 号 量 除 了 对 信 号 量 加 减 之 外 ， 还 有 判 断 ， 不 行 就 阻 塞 去 3 .AND型 信 号 量 ： 一 个 进 程 可 能 需 要 多 个 资 源 才 能 进 行 ， 中 途 可 能 有其 它 资 源 争 夺 ， 所 以 为 了 解 决 死 锁 的 问 题 ， 我 们 在 wait语 句 中 增 加 and条 件 ， 只 有 判 断 它 每 一 个 要 求 的 资 源 都 存 在 ， 才 占 用 ， 否 则 阻 塞 信 号 量 集 ： 设 置 需 求 值 和 下 限 值 ， 判 断 条 件 不 再 是 1 ， 而 是 下 限 值 信 号 量 的 应 用 1 .利 用 信 号 量 实 现 进 程 互 斥 ： 设 置 一 互 斥 信 号 量 ， 初 值 为 1 ， 标 记 该 资源 是 否 可 以 被 使 用 ， 从 而 使 进 程 对 该 资 源 互 斥 访 问 2 .利 用 信 号 量 （ 初 值 为 0 ） 实 现 前 趋 关 系 ： 对 于 有 前 置 的 等 待 进 程 ， 只有 它 的 前 趋 进 程 执 行 完 才 执 行 该 进 程 ， 前 趋 进 程 是 否 执 行 结 束 我 们 通过 信 号 量 来 控 制 。 经 典 进 程 同 步 问 题 生 产 者 消 费 者 读 者 写 者 哲 学 家 进 餐 问 题 进 程 通 信 进 程 间 的 信 息 交 换 直 接 通 信 方 式 ： 直 接 把 消 息 发 送 给 目 标 进 程 ， 发 送 进 程 和 接 收 进 程 都是 显 示 方 式 提 供 对 方 标 识 符 间 接 通 信 方 式 ： 有 一 个 实 体 （ 信 箱 ） 暂 存 发 送 的 消 息 ， 接 受 消 息 的 一方 也 从 信 箱 中 获 取 消 息 消 息 缓 冲 队 列 通 信 机 制 ： 在 缓 冲 区 暂 存 信 息 ， 以 队 列 的 形 式 逐 条 存 储 线 程 （ 只 是 调 度 单 位 ） 进 程 使 资 源 分 配 单 位 +调 度 单 位 属 性 ： 1 .轻 型 实 体 ： 基 本 不 拥 有 系 统 资 源 ， 只 有 TCB 2 .独 立 调 度 和 分 派 的 基 本 单 位 ： 不 可 再 分 ， 切 换 迅 速 开 销 小 3 .可 并 发 执 行 4 .共 享 进 程 资 源 内 核 支 持 线 程 ： 进 程 的 创 建 撤 销 都 是 利 用 系 统 调 用 进 入 内 核 ， 线 程 也是 如 此 用 户 级 线 程 ： 只 存 在 于 用 户 空 间 中 ， 无 需 系 统 调 用 调 度 作 业 调 度 （ 高 级 调 度 、 长 程 调 度 ） ： 从 后 备 队 列 中 通 过 一 定 算 法 找 出若 干 个 作 业 并 为 它 们 分 配 内 存 ， 建 立 进 程 ， 插 入 就 绪 队 列 。 进 程 调 度 （ 低 级 调 度 、 短 程 调 度 ） ： 从 就 绪 队 列 中 选 出 一 个 进 程 ， 使该 进 程 投 入 执 行 1 .保 存 现 场 信 息 ， 存 入 PCB 2 .按 某 种 算 法 选 取 进 程 3 .把 处 理 器 分 配 给 进 程 基 本 机 制 ： 1 .排 队 器 ： 将 就 绪 进 程 排 队 ， 提 高 效 率 2 .分 派 器 ： 从 就 绪 队 列 提 出 选 中 的 要 执 行 进 程 3 .上 下 文 切 换 ： 第 一 队 上 下 文 ： 将 当 前 运 行 进 程 的 信 息 保 存 给 分 派 程 序 第 二 队 上 下 文 ： 将 新 进 程 的 现 场 信 息 装 进 来 调 度 方 式 非 抢 占 方 式 ： 一 个 进 程 一 直 运 行 到 完 才 运 行 下 一 个 抢 占 方 式 ： 通 过 以 下 原 则 暂 停 某 个 正 在 运 行 的 进 程 原 则 ： 1 .优 先 权 原 则 ： 紧 急 任 务 具 有 较 高 优 先 权 2 短 作 业 优 先 原 则 ： 先 执 行 耗 时 短 的 进 程 3 .时 间 片 原 则 ： 按 时 间 片 流 转 ， 公 平 。 时 间 片 大 了 小 了 都 不 好 ， 应 该 在 0 .0 1 s0 .1 s之 间 （ 大 部 分 如 此 ） 调 度 队 列 模 型 仅 有 进 程 调 度 ： 完 全 按 照 用 户 键 入 的 命 令 顺 序 执 行 程 序 作 业 调 度 ： 根 据 不 同 原 则 的 不 同 算 法 选 择 插 入 就 绪 队 列 的 进 程 ， 不 一定 按 顺 序 。 中 级 调 度 ： 把 进 程 就 绪 分 为 内 存 就 绪 （ 进 程 在 内 存 中 就 绪 ） 和 外 存 就绪 （ 进 程 在 外 存 中 就 绪 ） ， 阻 塞 状 态 也 分 成 外 存 内 存 调 度 准 则 面 向 用 户 ： 周 转 时 间 短 、 响 应 时 间 快 、 截 止 时 间 保 证 、 优 先 权 准 则 面 向 系 统 ： 系 统 吞 吐 量 高 、 处 理 机 利 用 率 好 、 各 类 资 源 平 衡 利 用 实 时 调 度 最 早 截 止 时 间 优 先 （ EDF） 算 法 ： 任 务 的 开 始 截 止 时 间 越 早 ， 优 先 级越 高 最 低 松 弛 度 优 先 （ LLF） 算 法 ： 根 据 任 务 紧 急 或 松 弛 的 程 度 来 确 定 优 先级 死 锁 定 义 ： 多 个 进 程 抢 夺 资 源 而 形 成 的 僵 局 原 因 ： 1 .竞 争 资 源 ： 因 为 诸 进 程 对 资 源 的 竞 争 引 起 2 .进 程 间 推 进 顺 序 非 法 ： 请 求 和 释 放 资 源 的 顺 序 不 当 ， 也 同 样 会 导 致产 生 进 程 的 死 锁 。 产 生 死 锁 的 必 要 条 件 1 .互 斥 条 件 ： 该 资 源 要 求 访 问 的 进 程 互 斥 访 问 2 .请 求 和 保 持 条 件 ： 该 进 程 已 占 有 资 源 但 还 请 求 其 他 资 源 ， 但 资 源 又被 其 他 进 程 占 用 ， 则 该 进 程 请 求 进 程 阻 塞 ， 又 对 已 获 得 资 源 不 放 3 .不 剥 夺 条 件 ： 进 程 已 获 得 的 资 源 在 该 进 程 执 行 完 毕 之 前 不 释 放 4 .环 路 等 待 条 件 ： 发 生 死 锁 时 ， 必 然 存 在 一 个 进 程 资 源 的 环 形 链 P0 ， P1 ， P2 ,.Pn， P0 等 待 P1 资 源 ， P1 等 待 P2 资 源 。 。 Pn等 待 P0 资 源 处 理 死 锁 方 法 1 .预 防 死 锁 ： 通 过 破 坏 产 生 死 锁 的 四 个 必 要 条 件 中 的 某 些 来 避 免 死 锁 2 .安 全 状 态 ： 在 资 源 分 配 之 前 先 检 测 资 源 分 配 安 全 性 ， 若 不 安 全 ， 则另 进 程 等 待 银 行 家 算 法 银 行 家 算 法 的 步 骤 死 锁 检 测 与 解 除 检 测 方 法 ： 利 用 资 源 分 配 图 （ 大 题 第 一 个 ） 死 锁 解 除 ： 1 .剥 夺 资 源 ： 从 其 它 进 程 剥 夺 足 够 量 的 资 源 给 死 锁 进 程 解 除 死 锁 状 态 2 .撤 销 进 程 ： 撤 销 死 锁 进 程 温 柔 一 点 的 方 法 是 按 某 种 顺 序 逐 个 撤 销 死 锁 进 程 ， 在 此 过 程 中 可 以 释放 资 源 ， 使 得 某 些 死 锁 进 程 得 以 解 除 死 锁 状 态