生产围棋工人不小心把相等数量黑子和白子混在一块

生 产 围 棋 的 工 人 不 小 心 把 相 等 数 量 的 黑 子 和 白 子 混在 一 块 ， 该 系 统 由 两 个 并 发 执 行 的 进 程 组 成 ， 系 统功 能 如 下 ：（ 1） 进 程 A专 门 拣 黑 子 ， 进 程 B专 门 拣 白 子 ；（ 2） 每 个 进 程 每 次 只 拣 一 个 子 ， 当 一 个 进 程 在 拣子 时 不 允 许 另 一 个 进 程 去 拣 子（ 3） 当 一 个 进 程 拣 一 个 子 后 ， 必 让 另 一 个 进 程 拣一 个 子试 用 同 步 原 语 管 理 进 程 ， 使 其 能 正 确 实 现 上 述 功 能 。（ 假 定 系 统 启 动 时 先 让 进 程 A拣 子 ） P111 5.19若 将 读 者 离 开 与 读 者 进 入 分 别 看 成 一 个 进 程 ，试 用 同 步 原 语 描 述 进 程 间 关 系 。读 者 进 入 进 程 读 者 离 开 进 程进 入 注 销登 记 离 开 一 条 小 河 上 有 一 座 独 木 桥 ， 现 河 东 河 西 都有 人 要 过 桥 ， 同 一 方 向 的 可 连 续 过 桥 ； 某方 向 有 人 过 桥 时 另 一 方 向 的 人 须 等 待 。 如果 把 每 个 过 桥 者 看 作 一 个 进 程 ， 为 保 证 安全 ， 用 信 号 量 协 调 他 们 之 间 的 关 系 。 第 七 章 死 锁 (Deadlock)1、 死 锁 问 题 的 提 出2、 死 锁 的 必 要 条 件3、 死 锁 的 预 防4、 死 锁 的 避 免 和 银 行 家 算 法5、 死 锁 的 检 测6、 死 锁 的 恢 复 7.1 死 锁 问 题 的 提 出死 锁 是 指 计 算 机 系 统 和 进 程 所 处 的 一 种 状 态 。常 定 义 为 ： 在 系 统 中 的 一 组 进 程 ， 由 于 竞 争系 统 资 源 或 由 于 彼 此 通 信 而 永 远 阻 塞 ， 我 们称 这 些 进 程 处 于 死 锁 状 态 。 死 锁 的 现 象 A进 程 B进 程wait(s1) wait(s2)wait(s2) wait(s1)signal(s2) signal(s1)signal(s1) signal(s2) 死 锁 的 原 因资 源 不 足 ， 竞 争 资 源进 程 推 进 路 径 不 当 申 请 不 同 类 型 资 源 产 生 死 锁P1： 申 请 打 印 机申 请 扫 描 仪使 用释 放 打 印 机释 放 扫 描 仪 P2： 申 请 扫 描 仪申 请 打 印 机使 用释 放 打 印 机释 放 扫 描 仪 申 请 同 类 资 源 产 生 死 锁 （ 如 内 存 ） 设 有 资 源 R， R有 m个 分 配 单 位 ， 由 n个进 程 P1,P2,Pn（ n m） 共 享 。 假设 每 个 进 程 对 R的 申 请 和 释 放 符 合 下列 原 则 ： * 一 次 只 能 申 请 一 个 单 位 * 满 足 总 申 请 后 才 能 使 用 * 使 用 完 后 一 次 性 释 放 m=2， n=3资 源 分 配 不 当 导 致 死 锁 产 生 7.2 死 锁 的 必 要 条 件 资 源 的 分 类 死 锁 的 必 要 条 件 一 、 资 源 的 分 类 可 抢 占 资 源 、 不 可 抢 占 资 源 共 享 资 源 、 独 享 资 源 可 再 次 使 用 的 永 久 资 源 、 消 耗 性 的 临 时 资 源 二 、 死 锁 的 必 要 条 件 互 斥 条 件 :一 个 资 源 每 次 只 能 给 一 个 进 程 使 用 不 可 抢 占 条 件 :资 源 申 请 者 不 能 强 行 从 资 源 占 有 者 手 中 夺 取 资 源 ， 资 源 只 能 由 占 有 者 自 愿 释 放 部 分 分 配 条 件 :一 个 进 程 在 申 请 新 资 源 的 同 时 保 持 对 原 有 资 源 的 占 有 循 环 等 待 条 件 :存 在 一 个 进 程 等 待 队 列 P1 , P2 , , Pn, 其 中 P 1等 待 P2占 有 的 资 源 ， P2等 待 P3占 有 的 资 源 ， ， Pn等 待 P1占 有 的 资 源 ， 形 成 一 个 进 程 等 待 环 路 7.3 死 锁 的 预 防 在 系 统 设 计 时 确 定 资 源 分 配 算 法 ， 保 证不 发 生 死 锁 。 具 体 的 做 法 是 破 坏 产 生 死锁 的 四 个 必 要 条 件 之 一 预 防 死 锁 是 一 种 较 可 取 的 方 法 ， 但 资 源的 利 用 率 较 低 。 1、 破 坏 互 斥 条 件 互 斥 是 正 确 使 用 非 共 享 资 源 的 唯 一 手 段 。 故 不 能 通 过 取 消 互 斥 来 预 防 死 锁 。 2、 破 坏 不 可 抢 占 条 件适 用 于 状 态 容 易 保 护 ， 稍 后 又 容 易 恢 复 的资 源 。 如 CPU， 内 存 。 3、 破 坏 部 分 分 配 条 件 采 用 预 先 静 态 分 配 法 ： 每 个 进 程 执 行 前 ，一 次 分 配 其 所 有 资 源 允 许 进 程 仅 当 自 己 未 占 有 资 源 时 才 申 请资 源 。 4、 破 坏 循 环 等 待 条 件 有 序 资 源 分 配为 使 “ 循 环 等 待 ” 条 件 不 满 足 ， 我 们 把 所 有资 源 按 类 型 进 行 排 队 ， 并 赋 予 不 同 的 编 号 。 申 请 按 序 号 递 增 次 序 进 行 每 个 进 程 释 放 按 序 号 递 减 次 序 进 行优 点 ： 较 前 几 种 ， 改 善 资 源 的 利 用 率 。缺 点 ： 进 程 实 际 需 求 和 资 源 顺 序 不 一 致 会 造 成 资 源 浪 费 。 例 如 ： 1， 2， 3， ， 10P1：申 请 1申 请 3申 请 9 P2：申 请 1申 请 2申 请 5 P3 P10 7.4 死 锁 的 避 免 和 银 行 家 算 法 死 锁 避 免 安 全 状 态 和 不 安 全 状 态 银 行 家 算 法 数 据 结 构 银 行 家 算 法 一 、 死 锁 避 免 定 义在 系 统 运 行 过 程 中 ， 对 进 程 发 出 的 每 一 个系 统 能 够 满 足 的 资 源 申 请 进 行 动 态 检 查 ，并 根 据 检 查 结 果 决 定 是 否 分 配 资 源 ， 若 分配 后 系 统 可 能 发 生 死 锁 ， 则 不 予 分 配 ， 否则 予 以 分 配 例 单 资 源 的 银 行 家 算 法假 定 某 银 行 家 有 一 笔 资 金 可 供 一 批 顾 客 借 用 ，并 假 定 ： 每 个 顾 客 预 知 他 的 最 大 借 款 总 额 ， 且 不 超 过 银 行家 拥 有 的 可 用 资 金 总 和 。 每 次 借 款 以 一 万 元 为 单 位 。 每 当 顾 客 提 出 借 口 请 求 ， 银 行 家 可 立 即 给 予 ， 或让 顾 客 等 一 段 时 间 。 只 有 当 顾 客 达 到 他 的 预 定 最 大 借 款 额 时 ， 他 才 在有 限 时 间 依 次 归 还 。 安 全 状 态 ： 如 果 在 某 时 刻 ， 银 行 有可 能 使 它 当 时 的 所 有 的 顾 客 在 以 后有 限 时 间 内 完 成 全 部 成 交 ， 则 此 刻的 状 态 是 安 全 。不 安 全 状 态 ： 永 远 不 具 有 成 交 的 可能 ， 则 为 不 安 全 。 C 2 P 4（ 4） Q 2（ 1） R 2（ 7）C： 现 金 总 额 ， P， Q， R： 顾 客C 4 P 4（ 4） R 2（ 7） C 8 R 2（ 7） C 10安 全 状 态C 1 P 4（ 4） Q 2（ 1） R 3（ 6） C 3 P 4（ 4） R 3（ 6） 不 安 全 状 态 二 、 安 全 状 态 和 不 安 全 状 态 安 全 状 态 ： 指 系 统 能 按 某 种 进 程 顺 序 如 为 每 个 进 程 分 配 资 源 直 至最 大 需 求 。 不 安 全 状 态 ： 在 系 统 中 不 存 在 这 样 的 序列 。 三 、 银 行 家 算 法 数 据 结 构 Available： 一 个 长 度 为 m的 向 量 ， 表 示 每 类 资 源 的可 用 数 目 。 如 果 Availablej=k， 表 明 Rj类 资 源 有 k个 。 Max： 一 个 m n矩 阵 ， 定 义 每 个 进 程 的 最 大 资 源 需求 数 ， 如 果 Maxi,j=k,表 示 进 程 i需 要 Rj类 资 源 有 k个 。 Allocation： 一 个 m n矩 阵 ， 定 义 当 前 分 配 给 每 个进 程 每 类 资 源 的 数 目 。 如 果 Allocation i,j=k， 则 表示 进 程 I获 得 ： Rj类 资 源 有 k个 Need： 一 个 m n矩 阵 ， 表 示 每 个 进 程 还 需 多 少 资源 。 如 果 Needi,j=k， 表 示 进 程 I还 需 要 Rj类 资 源有 k个 。 表 示 进 程 I需 要 Rj类 资 源 有 k个 四 、 银 行 家 算 法设 ： Requesti是 进 程 Pi的 请 求 向 量当 Pi发 出 资 源 请 求 后 ， 系 统 按 如 下 步 骤 进 行 检 查 ：1、 如 果 Requesti Needi 则 go to 2,否 则 认 为 出 错 。2、 如 果 Requesti Available 则 go to 3， 否 则 表 示 无足 够 资 源 ， Pi等 待 。3、 系 统 进 行 试 探 分 配 ， 并 求 该 相 应 数 据 结 构 数 据 Available： = Available- Requesti Allocationi： = Allocationi+ Requesti Needi： = Needi-Requesti4、 系 统 执 行 安 全 性 算 法 ： 安 全 ， 把 资 源 分 配 给 Pi，否 则 ， Pi等 待 。 安 全 性 算 法1、 设 Work 和 Finish是 长 度 分 别 为 m,n的 向 量 初 始 值 Work： =Available ， Finishi： = False（ 所 有 ）2、 从 进 程 集 合 中 找 到 一 个 能 满 足 下 列 条 件 的 进 程 a. Finishi= False b. Needi Work 如 找 到 go to 3 ， 否 则 go to 4 3、 当 进 程 Pi 获 得 资 源 后 ， 顺 利 执 行 ， 直 至 完 成 ， 并 释放 分 配 给 它 的 资 源 。 Work： = Work+ Allocationi Finishi： = True go to 24、 如 果 所 有 进 程 的 Finishi= True 则 表 示 系 统 安 全 ， 否 则 为 不 安 全 。 例 1假 定 系 统 中 五 个 进 程 P0P4和 三 种 资 源A， B， C， 资 源 数 量 分 别 为 10， 5， 7， 在T0时 刻 的 资 源 分 配 情 况 如 下 表 。 Max Allocation Need AvailableP0 7， 5， 3 0， 1， 0 7， 4， 3 3， 3， 2P1 3， 2， 2 2， 0， 0 1， 2， 2P2 9， 0， 2 3， 0， 2 6， 0， 0P3 2， 2， 2 2， 1， 1 0， 1， 1P4 4， 3， 3 0， 0， 2 4， 3， 1 1、 T0时 刻 安 全 性 Work Need Allocation Work+ Allocation FinishP1 3 3 2 1 2 2 2 0 0 5 3 2 T P3 5 3 2 0 1 1 2 1 1 7 4 3 T P4 7 4 3 4 3 1 0 0 2 7 4 5 T P2 7 4 5 6 0 0 3 0 2 10 4 7 T P0 10 4 7 7 4 3 0 1 0 10 5 7 TT0状 态 是 安 全 2、 P1请 求 资 源P1 请 求 向 量 Request1（ 1， 0， 2）系 统 按 银 行 家 算 法 进 行 检 查 ： Request1（ 1， 0， 2） Need1（ 1， 2， 2） Request1（ 1， 0， 2） Available（ 3， 3， 2） 系 统 先 假 定 为 P1分 配 资 源 ， 并 求 该 数 据 结 构 的 值 Available = Available- Request1=（ 2， 3， 0） Allocation1 = Allocation1+Request1=（ 3， 0， 2） Need1 = Need1-Request1： =（ 0， 2， 0） 系 统 调 用 安 全 性 算 法 ， 检 查 其 安 全 性 Work Need Allocation Work+ Allocation FinishP1 2 3 0 0 2 0 3 0 2 5 3 2 TP3 5 3 2 0 1 1 2 1 1 7 4 3 TP4 7 4 3 4 3 1 0 0 2 7 4 5 TP0 7 4 5 7 4 3 0 1 0 7 5 5 TP2 7 5 5 6 0 0 3 0 2 10 5 7 T状 态 是 安 全 ， P1的 请 求 能 满 足 3、 P4 请 求 资 源P4 请 求 向 量 Request4（ 3， 3， 0）系 统 按 银 行 家 算 法 进 行 检 查 ： Request4（ 3， 3， 0） Need4（ 4， 3， 1） Request4（ 3， 3， 0） Available（ 2， 3， 0）让 P4等 待 。 4、 P0请 求 资 源P0请 求 向 量 Request0（ 0， 2， 0）系 统 按 银 行 家 算 法 进 行 检 查 ： Request0（ 0， 2， 0） Need0（ 7， 4， 3） Request0（ 0， 2， 0） Available（ 2， 3， 0） 系 统 先 假 定 为 P0分 配 资 源 ， 并 求 该 数 据 结 构 的 值 Available： = Available- Request0=（ 2， 1， 0） Allocation0： = Allocation0+Request0=（ 0， 3， 0） Need0： = Need0-Request0： =（ 7， 2， 3） 系 统 调 用 安 全 性 算 法 ， 检 查 结 果 为 不 安 全 银 行 家 算 法 的 优 缺 点 本 算 法 要 求 被 分 配 每 类 资 源 数 量 是 固 定不 变 。 本 算 法 要 求 用 户 数 固 定 不 变 。 本 算 法 保 证 所 有 用 户 的 要 求 在 有 限 时 间内 得 到 ， 实 时 较 差 。 本 算 法 要 求 用 户 事 先 说 明 他 的 最 大 资 源要 求 ， 这 对 用 户 较 难 。 7.5 死 锁 的 检 测 与 恢 复 死 锁 检 测 的 概 念 资 源 分 配 图 资 源 分 配 图 的 化 简 死 锁 检 测 中 数 据 结 构 检 测 死 锁 的 算 法 死 锁 的 恢 复 一 、 死 锁 检 测 允 许 死 锁 发 生 。 操 作 系 统 不 断 监 视系 统 进 展 情 况 ， 判 断 死 锁 是 否 发 生 。 一 旦 死 锁 发 生 则 采 取 专 门 的 措 施 ，解 除 死 锁 并 以 最 小 的 代 价 恢 复 操 作系 统 运 行 二 、 资 源 分 配 图 用 有 向 图 描 述 进 程 的 死 锁 资 源 分 配 图 表 示 法资 源 类 （ 资 源 的 不 同 类 型 ） 用 方 框 表 示资 源 实 例 （ 存 在 于 每 个 资 源 中 的 若 干 同 种 资 源 ） 用 方 框 中 的 黑 圆 点 表 示进 程 用 圆 圈 中 加 进 程 名 表 示分 配 边 ： 资 源 实 例 进 程 的 一 条 有 向 边申 请 边 ： 进 程 资 源 类 的 一 条 有 向 边 有 环 有 死 锁 有 环 无 死 锁 死 锁 定 理 如 果 资 源 分 配 图 中 没 有 环 路 ， 则 系统 中 没 有 死 锁 ； 如 果 图 中 存 在 环 路则 系 统 中 可 能 存 在 死 锁 如 果 每 个 资 源 类 中 只 包 含 一 个 资 源实 例 ， 则 环 路 是 死 锁 存 在 的 充 分 必要 条 件 三 、 资 源 分 配 图 化 简如 果 一 个 进 程 所 需 的 资 源 都 满 足 ， 则 对 该进 程 结 点 化 简 。化 简 的 方 法 ： 移 走 所 有 分 配 边 和 申 请 边 。如 果 图 中 所 有 的 进 程 结 点 均 可 化 简 成 为 孤立 的 结 点 ， 则 该 状 态 是 安 全 的 ， 否 则 是 不安 全 的 。 四 、 死 锁 检 测 中 数 据 结 构 可 利 用 资 源 Available， 它 表 示 m类 资 源 中 每 类 资 源可 用 数 目 。 请 求 矩 阵 Request ， 一 个 m n矩 阵 ， 用 以 表 示 进程 当 前 对 各 类 资 源 的 请 求 数 目 。 分 配 矩 阵 Allocation， 一 个 m n矩 阵 ， 用 以 表 示 某一 时 刻 的 资 源 的 分 配 情 况 。 工 作 向 量 Work， 表 示 系 统 可 提 供 的 各 类 资 源 的 数目 。 进 程 向 量 L， 记 录 当 前 已 不 占 用 资 源 的 各 进 程 。 五 、 检 测 死 锁 的 算 法 把 某 时 刻 t的 可 用 资 源 向 量 Available赋 予 Work 把 不 占 用 资 源 的 进 程 向 量 记 入 表 L。 从 进 程 集 合 中 找 到 一 个 Requesti Work的 进 程 ， 做 如 下处 理 ： 1.将 其 资 源 分 配 图 化 简 Work： = Work+ Allocationi 2.将 它 记 入 L表 中 若 不 能 把 所 有 进 程 都 记 入 L表 ， 则 状 态 S资 源 分 配 图 不可 完 全 化 简 ， 该 系 统 发 生 死 锁 。 六 、 死 锁 的 恢 复 强 制 性 撤 消 死 锁 的 进 程 并 剥 夺 资 源 撤 消 的 次 序 ： 使 用 最 少 处 理 器 时 间 的 进 程 使 用 最 少 输 出 工 作 量 的 进 程 具 有 最 多 剩 余 时 间 的 进 程 分 得 最 少 资 源 的 进 程 最 小 优 先 级 的 进 程 挂 起 和 解 除 挂 起 作 业 1： 假 定 一 个 处 理 机 上 执 行 的 作 业 如 下 ：作 业 提 交 时 间 短 暂 时 间 段 长 度 优 先 数 1 0 7 3 2 1 4 1 3 2 2 6 4 3 1 4 5 3 5 2 且 规 定 优 先 数 大 优 先 级 别 高 。 试 分 别 用 先 来 先 服 务 ， 时 间 片 （ 时 间 片 为 2） ， 短 作 业 优 先 ， 优 先 级 调 度 算 法 （ 非 抢 占 ， 可 抢 占 ） 调 度 这 些 作 业 ， 并 计 算 它们 的 平 均 周 转 时 间 。 作 业 2：设 有 三 个 作 业 ， 它 们 到 达 系 统 的 时 间 和 计算 时 间 如 下 ：J1： 8： 00到 达 计 算 时 间 2个 小 时J2： 8： 30到 达 计 算 时 间 1个 小 时J3： 9： 30到 达 计 算 时 间 0.5小 时系 统 采 用 响 应 比 高 者 优 先 调 度 ， 在 9： 30开始 调 度 时 ， 试 写 出 作 业 调 度 次 序 。