数据库课件第八章并发控制

第 八 章 并 发 控 制8.1 并 发 控 制 概 述8.2 封 锁8.3 封 锁 协 议8.4 活 锁 和 死 锁8.5 并 发 调 度 的 可 串 行 性8.6 两 段 锁 协 议8.7 封 锁 的 粒 度8.8 Oracle的 并 发 控 制8.9 小 结 并 发 控 制 概 述多 事 务 执 行 方 式 (1)事 务 串 行 执 行 每 个 时 刻 只 有 一 个 事 务 运 行 ， 其 他 事务 必 须 等 到 这 个 事 务 结 束 以 后 方 能 运行 不 能 充 分 利 用 系 统 资 源 ， 发 挥 数 据 库共 享 资 源 的 特 点 并 发 控 制 （ 续 ）(2)交 叉 并 发 方 式 （ interleaved concurrency） 事 务 的 并 行 执 行 是 这 些 并 行 事 务 的 并 行 操 作轮 流 交 叉 运 行 是 单 处 理 机 系 统 中 的 并 发 方 式 ， 能 够 减 少 处理 机 的 空 闲 时 间 ， 提 高 系 统 的 效 率 并 发 控 制 （ 续 ）(3)同 时 并 发 方 式 （ simultaneous concurrency） 多 处 理 机 系 统 中 ， 每 个 处 理 机 可 以 运 行 一 个事 务 ， 多 个 处 理 机 可 以 同 时 运 行 多 个 事 务 ，实 现 多 个 事 务 真 正 的 并 行 运 行 最 理 想 的 并 发 方 式 ， 但 受 制 于 硬 件 环 境 更 复 杂 的 并 发 方 式 机 制 事 务 并 发 执 行 带 来 的 问 题l可 能 会 存 取 和 存 储 不 正 确 的 数 据 ， 破 坏事 务 的 隔 离 性 和 数 据 库 的 一 致 性lDBMS必 须 提 供 并 发 控 制 机 制l并 发 控 制 机 制 是 衡 量 一 个 DBMS性 能 的重 要 标 志 之 一 8.1 并 发 控 制 概 述l并 发 控 制 机 制 的 任 务 对 并 发 操 作 进 行 正 确 调 度 保 证 事 务 的 隔 离 性 保 证 数 据 库 的 一 致 性 T1的 修 改 被 T2覆 盖 了 ！ 读 A=16 AA-3写 回 A=13 读 A=16 AA-1 写 回 A=15 事 务 T2事 务 T1数 据 不 一 致 实 例 ： 飞 机 订 票 系 统 并 发 操 作 带 来 的 数 据 不 一 致 性l丢 失 修 改 （ lost update）l不 可 重 复 读 （ non-repeatable read）l读 “ 脏 ” 数 据 （ dirty read） 1. 丢失修改丢 失 修 改 是 指 事 务 1与 事 务 2从 数 据 库 中 读入 同 一 数 据 并 修 改事 务 2的 提 交 结 果 破 坏 了 事 务 1提 交 的 结 果 ，导 致 事 务 1的 修 改 被 丢 失 。 2. 不可重复读不 可 重 复 读 是 指 事 务 1读 取 数 据 后 ， 事 务 2执 行 更 新 操 作 ， 使 事 务 1无 法 再 现 前 一 次 读取 结 果 。 三 类不可重复读事 务 1读 取 某 一 数 据 后 ：1。 事 务 2对 其 做 了 修 改 ， 当 事 务 1再 次 读 该数 据 时 ， 得 到 与 前 一 次 不 同 的 值 。2. 事 务 2删 除 了 其 中 部 分 记 录 ， 当 事 务 1再次 读 取 数 据 时 ， 发 现 某 些 记 录 神 密 地 消失 了 。3. 事 务 2插 入 了 一 些 记 录 ， 当 事 务 1再 次 按相 同 条 件 读 取 数 据 时 ， 发 现 多 了 一 些 记录 。后 两 种 不 可 重 复 读 有 时 也 称 为 幻 影 现 象（ phantom row） 3. 读“脏”数据事 务 1修 改 某 一 数 据 ， 并 将 其 写 回 磁 盘事 务 2读 取 同 一 数 据 后事 务 1由 于 某 种 原 因 被 撤 消 ， 这 时 事 务 1已 修 改 过的 数 据 恢 复 原 值事 务 2读 到 的 数 据 就 与 数 据 库 中 的 数 据 不 一 致 ，是 不 正 确 的 数 据 ， 又 称 为 “ 脏 ” 数 据 。 图 8.1 三 种 数 据 不 一 致 性 T1 T2 读 A=16 AA-1 写 回 A=15 读 A=16 AA-1写 回 A=15(a) 丢 失 修 改 图 8.1 三 种 数 据 不 一 致 性 (续 ) 读 B=100 BB*2写 回 B=200 读 A=50 读 B=100 求 和 =150 读 A=50 读 B=200 求 和 =250 (验 算 不 对 ) T2T1 (b) 不 可 重 复 读 图 8.1 三 种 数 据 不 一 致 性 (续 ) 读 C=200 读 C=100 CC*2 写 回 C ROLLBACK C恢 复 为 100 T2T1(c) 读 “ 脏 ” 数 据 第八章 并发控制8.1 并 发 控 制 概 述8.2 封 锁8.3 封 锁 协 议8.4 活 锁 和 死 锁8.5 并 发 调 度 的 可 串 行 性8.6 两 段 锁 协 议8.7 封 锁 的 粒 度8.8 Oracle的 并 发 控 制8.9 小 结 8.2 封 锁一 、 什 么 是 封 锁二 、 基 本 封 锁 类 型三 、 基 本 锁 的 相 容 矩 阵 一 、 什 么 是 封 锁l 封 锁 就 是 事 务 T在 对 某 个 数 据 对 象 （ 例 如 表 、记 录 等 ） 操 作 之 前 ， 先 向 系 统 发 出 请 求 ， 对 其加 锁l 加 锁 后 事 务 T就 对 该 数 据 对 象 有 了 一 定 的 控 制 ，在 事 务 T释 放 它 的 锁 之 前 ， 其 它 的 事 务 不 能 更新 此 数 据 对 象 。l 封 锁 是 实 现 并 发 控 制 的 一 个 非 常 重 要 的 技 术 8.2 封 锁一 、 什 么 是 封 锁二 、 基 本 封 锁 类 型三 、 基 本 锁 的 相 容 矩 阵 二 、 基 本 封 锁 类 型l DBMS通 常 提 供 了 多 种 类 型 的 封 锁 。 一 个 事 务对 某 个 数 据 对 象 加 锁 后 究 竟 拥 有 什 么 样 的 控 制是 由 封 锁 的 类 型 决 定 的 。l 基 本 封 锁 类 型 排 它 锁 （ eXclusive lock， 简 记 为 X锁 ） 共 享 锁 （ Share lock， 简 记 为 S锁 ） 排 它 锁l排 它 锁 又 称 为 写 锁l若 事 务 T对 数 据 对 象 A加 上 X锁 ， 则 只 允许 T读 取 和 修 改 A， 其 它 任 何 事 务 都 不 能再 对 A加 任 何 类 型 的 锁 ， 直 到 T释 放 A上的 锁 共 享 锁l共 享 锁 又 称 为 读 锁l若 事 务 T对 数 据 对 象 A加 上 S锁 ， 则 其 它事 务 只 能 再 对 A加 S锁 ， 而 不 能 加 X锁 ，直 到 T释 放 A上 的 S锁 8.2 封 锁一 、 什 么 是 封 锁二 、 基 本 封 锁 类 型三 、 基 本 锁 的 相 容 矩 阵 三 、 锁 的 相 容 矩 阵 Y=Yes， 相 容 的 请 求N=No， 不 相 容 的 请 求 T1 T2 X S -X N N YS N Y Y- Y Y Y 第八章 并发控制8.1 并 发 控 制 概 述8.2 封 锁8.3 封 锁 协 议8.4 活 锁 和 死 锁8.5 并 发 调 度 的 可 串 行 性8.6 两 段 锁 协 议8.7 封 锁 的 粒 度8.8 Oracle的 并 发 控 制8.9 小 结 8.3 封 锁 协 议l 在 运 用 X锁 和 S锁 对 数 据 对 象 加 锁 时 ， 需 要 约 定一 些 规 则 ： 封 锁 协 议 （ Locking Protocol） 何 时 申 请 X锁 或 S锁 持 锁 时 间 、 何 时 释 放l 不 同 的 封 锁 协 议 ， 在 不 同 的 程 度 上 为 并 发 操 作 的 正 确 调 度 提 供 一 定 的 保 证l 常 用 的 封 锁 协 议 ： 三 级 封 锁 协 议 1级 封 锁 协 议l事 务 T在 修 改 数 据 R之 前 必 须 先 对 其 加 X锁 ， 直 到 事 务 结 束 才 释 放 正 常 结 束 （ MIT） 非 正 常 结 束 （ ROLLBACK）l 1级 封 锁 协 议 可 防 止 丢 失 修 改l 在 1级 封 锁 协 议 中 ， 如 果 是 读 数 据 ， 不 需 要 加锁 的 ， 所 以 它 不 能 保 证 可 重 复 读 和 不 读 “ 脏 ”数 据 。 1级 封 锁 协 议T1 T2 Xlock A 获 得 读 A=16 AA-1 写 回 A=15 Commit Unlock A Xlock A等 待等 待等 待等 待获 得 Xlock A读 A=15AA-1写 回 A=14CommitUnlock A 没 有 丢 失 修 改 1级 封 锁 协 议 读 A=15 Xlock A 获 得 读 A=16 AA-1 写 回 A=15 RollbackUnlock A T2T1 读 “ 脏 ” 数 据 1级 封 锁 协 议 Xlock B 获 得 读 B=100 BB*2 写 回 B=200 Commit Unlock B 读 A=50 读 B=100 求 和 =150 读 A=50 读 B=200 求 和 =250 (验 算 不 对 ) T2T1 不 可 重 复 读 2级 封 锁 协 议l1级 封 锁 协 议 +事 务 T在 读 取 数 据 R前 必 须 先加 S锁 ， 读 完 后 即 可 释 放 S锁l2级 封 锁 协 议 可 以 防 止 丢 失 修 改 和 读 “ 脏 ”数 据 。l在 2级 封 锁 协 议 中 ， 由 于 读 完 数 据 后 即 可 释放 S锁 ， 所 以 它 不 能 保 证 可 重 复 读 。 2级 封 锁 协 议 不 可 重 复 读 Sclock A 获 得 读 A=50 Unlock A Sclock B 获 得 读 B=100 Unlock B 求 和 =150 Xlock B等 待等 待获 得 Xlock B读 B=100BB*2 写 回 B=200CommitUnlock BT2T1 Sclock A 获 得 读 A=50 Unlock A Sclock B 获 得 读 B=200 Unlock B 求 和 =250 (验 算 不 对 ) T2T1 (续 ) 3级 封 锁 协 议l1级 封 锁 协 议 + 事 务 T在 读 取 数 据 R之 前必 须 先 对 其 加 S锁 ， 直 到 事 务 结 束 才 释 放l 3级 封 锁 协 议 可 防 止 丢 失 修 改 、 读 脏 数 据 和 不可 重 复 读 。 3级 封 锁 协 议T1 T2 Slock A 读 A=50 Slock B 读 B=100 求 和 =150 读 A=50 读 B=100 求 和 =150 Commit Unlock A Unlock B Xlock B等 待等 待等 待 等 待等 待等 待等 待等 待获 得 Xlock B读 B=100BB*2写 回 B=200CommitUnlock B 可 重 复 读 3级 封 锁 协 议T1 T2 Xlock C 读 C= 100 CC*2 写 回 C=200 ROLLBACK (C恢 复 为 100) Unlock C Slock C等 待等 待等 待等 待获 得 Slock C读 C=100Commit CUnlock C 不 读 “ 脏 ” 数 据 4 封 锁 协 议 小 结l三 级 协 议 的 主 要 区 别 什 么 操 作 需 要 申 请 封 锁 何 时 释 放 锁 （ 即 持 锁 时 间 ） 封 锁 协 议 小 结 (续 ) 第八章 并发控制8.1 并 发 控 制 概 述8.2 封 锁8.3 封 锁 协 议8.4 活 锁 和 死 锁8.5 并 发 调 度 的 可 串 行 性8.6 两 段 锁 协 议8.7 封 锁 的 粒 度8.8 Oracle的 并 发 控 制8.9 小 结 8.4 活 锁 和 死 锁l封 锁 技 术 可 以 有 效 地 解 决 并 行 操 作 的 一致 性 问 题 ， 但 也 带 来 一 些 新 的 问 题 死 锁 活 锁 8.4.1 活 锁 如 何 避 免 活 锁采 用 先 来 先 服 务 的 策 略 ：当 多 个 事 务 请 求 封 锁 同 一 数 据 对 象 时l按 请 求 封 锁 的 先 后 次 序 对 这 些 事 务 排 队l该 数 据 对 象 上 的 锁 一 旦 释 放 ， 首 先 批 准申 请 队 列 中 第 一 个 事 务 获 得 锁 。 8.4.2 死 锁T1 T2 Xlock R1.Xlock R 2等 待等 待等 待. .Xlock R2.Xlock R1等 待等 待. 解 决 死 锁 的 方 法两 类 方 法1. 预 防 死 锁2. 死 锁 的 诊 断 与 解 除 1. 死 锁 的 预 防l产 生 死 锁 的 原 因 是 两 个 或 多 个 事 务 都 已封 锁 了 一 些 数 据 对 象 ， 然 后 又 都 请 求 对已 为 其 他 事 务 封 锁 的 数 据 对 象 加 锁 ， 从而 出 现 死 等 待 。l预 防 死 锁 的 发 生 就 是 要 破 坏 产 生 死 锁 的条 件 死 锁 的 预 防（续）预 防 死 锁 的 方 法l 一 次 封 锁 法l 顺 序 封 锁 法 （ 1） 一 次 封 锁 法l 要 求 每 个 事 务 必 须 一 次 将 所 有 要 使 用 的 数 据 全部 加 锁 ， 否 则 就 不 能 继 续 执 行l 一 次 封 锁 法 存 在 的 问 题 ： 降 低 并 发 度 扩 大 封 锁 范 围 将 以 后 要 用 到 的 全 部 数 据 加 锁 ， 势 必 扩 大了 封 锁 的 范 围 ， 从 而 降 低 了 系 统 的 并 发 度 一 次 封 锁 法 （ 续 ）l难 于 事 先 精 确 确 定 封 锁 对 象 数 据 库 中 数 据 是 不 断 变 化 的 ， 原 来 不要 求 封 锁 的 数 据 ， 在 执 行 过 程 中 可 能会 变 成 封 锁 对 象 ， 所 以 很 难 事 先 精 确地 确 定 每 个 事 务 所 要 封 锁 的 数 据 对 象 解 决 方 法 ： 将 事 务 在 执 行 过 程 中 可 能要 封 锁 的 数 据 对 象 全 部 加 锁 ， 这 就 进一 步 降 低 了 并 发 度 。 （ 2） 顺 序 封 锁 法l 顺 序 封 锁 法 是 预 先 对 数 据 对 象 规 定 一 个 封 锁 顺序 ， 所 有 事 务 都 按 这 个 顺 序 实 行 封 锁 。l 顺 序 封 锁 法 存 在 的 问 题 维 护 成 本 高 数 据 库 系 统 中 可 封 锁 的 数 据 对 象 极 其 众 多 ，并 且 随 数 据 的 插 入 、 删 除 等 操 作 而 不 断 地 变化 ， 要 维 护 这 样 极 多 而 且 变 化 的 资 源 的 封 锁顺 序 非 常 困 难 ， 成 本 很 高 顺 序 封 锁 法 （ 续 ） 难 于 实 现 事 务 的 封 锁 请 求 可 以 随 着 事 务 的 执 行而 动 态 地 决 定 ， 很 难 事 先 确 定 每 一 个事 务 要 封 锁 哪 些 对 象 ， 因 此 也 就 很 难按 规 定 的 顺 序 去 施 加 封 锁 。 例 ： 规 定 数 据 对 象 的 封 锁 顺 序 为 A,B,C,D,E。事 务 T3起 初 要 求 封 锁 数 据 对 象 B,C,E， 但 当它 封 锁 了 B,C后 ， 才 发 现 还 需 要 封 锁 A， 这样 就 破 坏 了 封 锁 顺 序 . 死 锁 的 预 防 （ 续 ）l结 论 在 操 作 系 统 中 广 为 采 用 的 预 防 死 锁 的 策 略 并不 很 适 合 数 据 库 的 特 点 DBMS在 解 决 死 锁 的 问 题 上 更 普 遍 采 用 的 是诊 断 并 解 除 死 锁 的 方 法 2. 死 锁 的 诊 断 与 解 除l允 许 死 锁 发 生l解 除 死 锁 由 DBMS的 并 发 控 制 子 系 统 定 期 检 测 系 统 中是 否 存 在 死 锁 一 旦 检 测 到 死 锁 ， 就 要 设 法 解 除 检 测 死 锁 ： 超 时 法l如 果 一 个 事 务 的 等 待 时 间 超 过 了 规定 的 时 限 ， 就 认 为 发 生 了 死 锁l优 点 ： 实 现 简 单l缺 点有 可 能 误 判 死 锁时 限 若 设 置 得 太 长 ， 死 锁 发 生 后不 能 及 时 发 现 等 待 图 法l 用 事 务 等 待 图 动 态 反 映 所 有 事 务 的 等 待 情 况 事 务 等 待 图 是 一 个 有 向 图 G=(T， U) T为 结 点 的 集 合 ， 每 个 结 点 表 示 正 运 行 的 事 务 U为 边 的 集 合 ， 每 条 边 表 示 事 务 等 待 的 情 况 若 T1等 待 T2， 则 T1， T2之 间 划 一 条 有 向 边 ， 从 T1指向 T2l 并 发 控 制 子 系 统 周 期 性 地 （ 比 如 每 隔 1 min） 检测 事 务 等 待 图 ， 如 果 发 现 图 中 存 在 回 路 ， 则 表示 系 统 中 出 现 了 死 锁 。 死 锁 的 诊 断 与 解 除 （ 续 ）l解 除 死 锁 选 择 一 个 处 理 死 锁 代 价 最 小 的 事 务 ，将 其 撤 消 ， 释 放 此 事 务 持 有 的 所 有 的锁 ， 使 其 它 事 务 能 继 续 运 行 下 去 。 第八章 并发控制8.1 并 发 控 制 概 述8.2 封 锁8.3 封 锁 协 议8.4 活 锁 和 死 锁8.5 并 发 调 度 的 可 串 行 性8.6 两 段 锁 协 议8.7 封 锁 的 粒 度8.8 Oracle的 并 发 控 制8.9 小 结 8.5 并 发 调 度 的 可 串 行 性一 、 什 么 样 的 并 发 操 作 调 度 是 正 确 的二 、 如 何 保 证 并 发 操 作 的 调 度 是 正 确 的 8.5 并 发 调 度 的 可 串 行 性一 、 什 么 样 的 并 发 操 作 调 度 是 正 确 的二 、 如 何 保 证 并 发 操 作 的 调 度 是 正 确 的 一 、 什 么 样 的 并 发 操 作 调 度 是 正 确 的l 计 算 机 系 统 对 并 行 事 务 中 并 行 操 作 的 调 度 是 的随 机 的 ， 而 不 同 的 调 度 可 能 会 产 生 不 同 的 结 果 。l 将 所 有 事 务 串 行 起 来 的 调 度 策 略 一 定 是 正 确 的调 度 策 略 。 如 果 一 个 事 务 运 行 过 程 中 没 有 其 他 事 务 在 同时 运 行 ， 也 就 是 说 它 没 有 受 到 其 他 事 务 的 干扰 ， 那 么 就 可 以 认 为 该 事 务 的 运 行 结 果 是 正常 的 或 者 预 想 的 什 么 样 的 并 发 操 作 调 度 是 正 确 的 （ 续 ）l 以 不 同 的 顺 序 串 行 执 行 事 务 也 有 可 能 会 产 生 不同 的 结 果 ， 但 由 于 不 会 将 数 据 库 置 于 不 一 致 状态 ， 所 以 都 可 以 认 为 是 正 确 的 。l 几 个 事 务 的 并 行 执 行 是 正 确 的 ， 当 且 仅 当 其 结果 与 按 某 一 次 序 串 行 地 执 行 它 们 时 的 结 果 相 同 。这 种 并 行 调 度 策 略 称 为 可 串 行 化 （ Serializable）的 调 度 。 什 么 样 的 并 发 操 作 调 度 是 正 确 的 （ 续 ）l可 串 行 性 是 并 行 事 务 正 确 性 的 唯 一 准 则例 ： 现 在 有 两 个 事 务 ， 分 别 包 含 下 列 操 作 ： 事 务 1： 读 B； A=B+1； 写 回 A； 事 务 2： 读 A； B=A+1； 写 回 B； 假 设 A的 初 值 为 2， B的 初 值 为 2。 什 么 样 的 并 发 操 作 调 度 是 正 确 的 （ 续 ） 对 这 两 个 事 务 的 不 同 调 度 策 略 串 行 执 行串 行 调 度 策 略 1串 行 调 度 策 略 2 交 错 执 行 不 可 串 行 化 的 调 度 可 串 行 化 的 调 度 (a) 串 行 调 度 策 略 ， 正 确 的 调 度Slock BY=B=2Unlock BXlock AA=Y+1写回A(=3)Unlock A Slock AX=A=3Unlock AXlock BB=X+1写回B(=4)Unlock B T1 T2 (b) 串 行 调 度 策 略 ， 正 确 的 调 度 Slock BY=B=3Unlock BXlock AA=Y+1 写回A(=4)Unlock A SlockA X=A=2Unlock AXlock BB=X+1写回B(=3)Unlock B T1 T2 (c) 不 可 串 行 化 的 调 度Slock BY=B=2 Unlock B Xlock AA=Y+1写回A(=3) Unlock A Slock AX=A=2 Unlock A Xlock BB=X+1写回B(=3) Unlock B T1 T2 (c) 不 可 串 行 化 的 调 度 (续 ) 由 于 其 执 行 结 果 与 (a)、 (b)的 结 果 都 不 同 ，所 以 是 错 误 的 调 度 。 (d) 可 串 行 化 的 调 度Slock BY=B=2Unlock BXlock A A=Y+1写回A(=3)Unlock A Slock A 等 待 等 待 等 待X=A=3Unlock AXlock BB=X+1写回B(=4)Unlock B T1 T2 (d) 可 串 行 化 的 调 度 （ 续 ） 由 于 其 执 行 结 果 与 串 行 调 度 （ a） 的 执 行结 果 相 同 ， 所 以 是 正 确 的 调 度 。 8.5 并 发 调 度 的 可 串 行 性一 、 什 么 样 的 并 发 操 作 调 度 是 正 确 的二 、 如 何 保 证 并 发 操 作 的 调 度 是 正 确 的 二 、 如 何 保 证 并 发 操 作 的 调 度 是 正 确 的l 为 了 保 证 并 行 操 作 的 正 确 性 ， DBMS的 并 行 控制 机 制 必 须 提 供 一 定 的 手 段 来 保 证 调 度 是 可 串行 化 的 。l 从 理 论 上 讲 ， 在 某 一 事 务 执 行 时 禁 止 其 他 事 务执 行 的 调 度 策 略 一 定 是 可 串 行 化 的 调 度 ， 这 也是 最 简 单 的 调 度 策 略 ， 但 这 种 方 法 实 际 上 是 不可 行 的 ， 因 为 它 使 用 户 不 能 充 分 共 享 数 据 库 资源 。 如 何 保 证 并 发 操 作 的 调 度 是 正 确 的 （ 续 ）l保 证 并 发 操 作 调 度 正 确 性 的 方 法 封 锁 方 法 ： 两 段 锁 （ Two-Phase Locking，简 称 2PL） 协 议 时 标 方 法 乐 观 方 法