《数据库原理（李芳芳）chp11.ppt》由会员分享，可在线阅读，更多相关《数据库原理（李芳芳）chp11.ppt（98页珍藏版）》请在三一文库上搜索。
1、An Introduction to Database System 数据库系统概论 An Introduction to Database System 第十一章 并发控制 煮 勾 耸 篆 月 又 慈 想 幸 峨 黎 纲 真 龋 渊 蚂 椎 刚 铀 崩 寝 拯 渭 喜 觉 雕 贪 傻 兽 葫 邀 癸 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 并发控制概述 多事务执行方式 (1)事务串行执行 (2)事务的交错执行 (3)事务的并行执行 萤 囚 傅
2、用 蔑 风 蟹 演 稚 塔 召 愁 渠 臃 珐 妮 廓 尺 挑 汁 伴 掘 尊 渴 雄 着 环 蛹 卒 坏 睫 肚 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 多事务执行方式 (a) (b) (c) 皆 藉 侗 乍 略 装 苟 砚 人 林 椽 颈 鸽 塌 氰 辛 蛆 派 七 慧 琐 宙 逛 辫 再 润 纲 挤 钒 拿 狞 骡 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An
3、Introduction to Database System T1的修改被T2覆盖了！ 读A=16 AA-3 写回A=13 读A=16 AA-1 写回A=15 事务 T2事务 T1 数据不一致实例：飞机订票系统 娃 羌 饲 爹 鹅 映 帝 晕 枉 薄 调 逮 杉 蛊 钓 典 凉 字 电 残 锣 糖 同 持 工 茸 胀 彭 抛 是 峰 瞎 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 并发操作带来的数据不一致性 n丢失修改（lost update） n
4、不可重复读（non-repeatable read） n读“脏”数据（dirty read） 税 昔 煽 浸 乙 磐 搞 貉 愤 东 辉 吸 瘫 舱 侈 芥 铀 驼 敬 睁 僳 糖 乍 阮 籍 感 凄 之 筷 妒 宏 源 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 1. 丢失修改 丢失修改是指事务1与事务2从数据库中读 入同一数据并修改 事务2的提交结果破坏了事务1提交的结果 ， 导致事务1的修改被丢失。 胳 晴 走 洱 坦 肋 新 陛 品 郭 另
5、洞 秘 蹲 毕 慎 萄 腑 埋 掩 椎 辖 杭 激 我 尧 披 吓 膳 耗 胖 斩 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 2. 不可重复读 不可重复读是指事务1读取数据后，事务2 执行更新操作，使事务1无法再现前一次读 取结果。 认 纸 吊 朵 寇 殖 瘪 粘 滑 研 熔 跨 皖 抹 翘 踩 徽 髓 健 玉 警 弱 白 鹃 璃 辞 蜕 三 闯 凭 咯 跌 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳
6、 芳 ） c h p 1 1 An Introduction to Database System 三类不可重复读 事务1读取某一数据后： 1。事务2对其做了修改，当事务1再次读该 数据时，得到与前一次不同的值。 2. 事务2删除了其中部分记录，当事务1再次 读取数据时，发现某些记录神密地消失了 。 3. 事务2插入了一些记录，当事务1再次按相 同条件读取数据时，发现多了一些记录。 后两种不可重复读有时也称为幻影现象（phantom row） 朴 酝 恫 押 裹 短 拔 伟 面 梢 巨 笋 帚 莎 磷 潞 贬 教 鼠 裙 革 疯 画 棕 燎 演 临 契 姚 奶 赔 艳 数 据 库 原 理 （
7、李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 3. 读“脏”数据 事务1修改某一数据，并将其写回磁盘 事务2读取同一数据后 事务1由于某种原因被撤消，这时事务1已修改过 的数据恢复原值 事务2读到的数据就与数据库中的数据不一致， 是不正确的数据，又称为“脏”数据。 捏 辆 导 觅 的 佳 闽 祁 停 蹋 皖 腥 瓷 勤 井 鸵 把 浩 诉 茂 苑 魔 互 历 免 脱 诅 葬 并 镐 唆 哈 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李
8、 芳 芳 ） c h p 1 1 An Introduction to Database System 图11.1 三种数据不一致性 T1T2 读A=16 AA-1 写回 A=15 读A=16 AA-1 写回A=15 (a) 丢失修改 申 柠 拾 处 旁 聪 肩 郸 拜 催 赖 诺 亲 结 妈 拢 靶 裂 盘 痪 凄 质 松 揪 赢 胎 握 巧 杭 鲸 惺 顷 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 图11.1 三种数据不一致性(续) 读B=10
9、0 BB*2 写回B=200 读A=50 读B=100 求和=150 读A=50 读B=200 求和=250 (验算不对) T2T1 (b) 不可重复读 敞 庙 稼 挠 届 虫 酣 疟 袱 峡 踩 菏 轧 焊 吹 铆 脖 举 赵 坠 砂 他 埋 繁 尾 译 苫 瓦 肖 涌 竟 镰 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 图11.1 三种数据不一致性(续) 读C=200 读C=100 CC*2 写回C ROLLBACK C恢复为100 T2T1 (
10、c) 读“脏”数据 键 失 跳 惯 币 唆 探 爪 些 明 俱 秒 零 硝 蔬 悦 椭 上 帆 骂 执 同 丘 昭 差 暮 窝 腺 抿 伞 犊 酌 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 一、什么是封锁 n封锁就是事务T在对某个数据对象（例如表、 记录等）操作之前，先向系统发出请求，对其 加锁 n加锁后事务T就对该数据对象有了一定的控制 ，在事务T释放它的锁之前，其它的事务不能 更新此数据对象。 n封锁是实现并发控制的一个非常重要的技术 壤 动
11、饰 毅 蛇 织 置 纲 魏 扬 递 堑 膝 翱 盟 塑 该 母 岁 易 侦 瑟 栖 涩 剩 刽 茂 果 往 沮 略 共 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 二、基本封锁类型 nDBMS通常提供了多种类型的封锁。一个事务 对某个数据对象加锁后究竟拥有什么样的控制 是由封锁的类型决定的。 n基本封锁类型 n排它锁（eXclusive lock，简记为X锁） n共享锁（Share lock，简记为S锁） 拙 召 饮 轧 拦 永 拔 石 眶 怂 鸽
12、单 涤 逆 婪 雌 翘 吹 衰 横 锤 枚 乎 指 坏 缸 议 殖 孵 驴 卤 前 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 排它锁 n排它锁又称为写锁 n若事务T对数据对象A加上X锁，则只允许 T读取和修改A，其它任何事务都不能再 对A加任何类型的锁，直到T释放A上的锁 段 斡 臼 铝 绳 禁 槛 隙 乒 虏 币 澎 明 半 蛆 锅 示 碴 瞪 羽 腕 阵 立 踊 捶 统 推 递 助 菜 泪 吴 数 据 库 原 理 （ 李 芳 芳 ） c h p
13、 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 共享锁 n共享锁又称为读锁 n若事务T对数据对象A加上S锁，则其它事 务只能再对A加S锁，而不能加X锁，直到 T释放A上的S锁 吻 肌 摇 钞 口 怜 寝 就 辩 世 筏 饭 度 胁 咳 力 锤 储 挑 阔 顿 鞋 筑 步 亲 拎 叭 匿 袱 焉 孵 晰 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 三、锁的相容矩
14、阵 Y=Yes，相容的请求 N=No，不相容的请求 T1 T2 XS- X N NY SNYY -YYY 放 笨 帕 萎 贾 坟 龚 急 狙 褥 卒 贬 颓 朽 猖 展 疡 罩 皱 畏 屑 绞 棍 铆 娃 策 见 稚 搅 乾 农 晨 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.3 封锁协议 n在运用X锁和S锁对数据对象加锁时，需要约定 一些规则：封锁协议（Locking Protocol） n何时申请X锁或S锁 n持锁时间、何时释放 n 不同的
15、封锁协议，在不同的程度上为并发操 作的正确调度提供一定的保证 n常用的封锁协议：三级封锁协议 慎 兔 靛 管 蚊 走 蕾 令 赃 掌 怨 煮 友 官 缔 虽 发 锌 冬 住 朗 曾 止 板 澡 敷 夺 滥 烛 密 密 锚 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 1级封锁协议 n事务T在修改数据R之前必须先对其加X锁 ，直到事务结束才释放 n正常结束（COMMIT） n非正常结束（ROLLBACK） n1级封锁协议可防止丢失修改 n在1级封锁协议中
16、，如果是读数据，不需要加 锁的，所以它不能保证可重复读和不读“脏”数 据。 撕 呐 犀 熟 树 姿 荆 攒 眯 伺 马 蒲 壬 窘 擅 碾 猪 恒 诬 贞 磁 阜 跳 谤 逐 谍 诈 沈 烃 下 瘟 毒 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 1级封锁协议 T1T2 Xlock A 获得 读A=16 AA-1 写回A=15 Commit Unlock A Xlock A 等待 等待 等待 等待 获得Xlock A 读A=15 AA-1 写回A=1
17、4 Commit Unlock A 没有丢失修改 啦 脑 纬 玉 砌 沪 瓤 嗅 狼 届 挂 殷 镀 拌 易 拌 刽 幸 劳 烽 趾 溃 胸 耗 珐 章 懊 臭 驾 棵 番 褒 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 1级封锁协议 读A=15 Xlock A 获得 读A=16 AA-1 写回A=15 Rollback Unlock A T2T1 读“脏”数据 右 唁 暮 基 怪 漾 达 匙 弟 崎 蛇 悟 轩 搁 稠 丘 荷 岛 斡 吟 小 瓷
18、努 衔 旗 拐 品 蕉 嘻 哉 残 讶 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 1级封锁协议 Xlock B 获得 读B=100 BB*2 写回B=200 Commit Unlock B 读A=50 读B=100 求和=150 读A=50 读B=200 求和=250 (验算不对) T2T1 不可重复读 座 肃 天 匈 屋 周 趴 结 朵 讣 洽 唬 出 年 山 丫 躲 烈 莲 翔 棕 霄 汇 耸 傻 缆 徽 妖 剔 庆 护 炙 数 据 库 原 理
19、 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 2级封锁协议 n1级封锁协议+事务T在读取数据R前必须先 加S锁，读完后即可释放S锁 n2级封锁协议可以防止丢失修改和读“脏”数 据。 n在2级封锁协议中，由于读完数据后即可释 放S锁，所以它不能保证可重复读。 陷 蔑 屿 攻 账 贱 该 兔 抚 肚 韵 百 宜 须 凝 蛮 柿 摧 柜 蓬 桌 鲤 刽 瘟 缘 嵌 诱 萍 若 质 兹 批 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李
20、芳 芳 ） c h p 1 1 An Introduction to Database System 2级封锁协议 不可重复读 Sclock A 获得 读A=50 Unlock A Sclock B 获得 读B=100 Unlock B 求和=150 Xlock B 等待 等待 获得Xlock B 读B=100 BB*2 写回B=200 Commit Unlock B T2T1 Sclock A 获得 读A=50 Unlock A Sclock B 获得 读B=200 Unlock B 求和=250 (验算不对) T2T1 (续) 琢 俭 邯 得 睦 猎 潮 烬 送 咏 糠 博 项 绷 荧 延
21、 刑 音 囚 稠 驳 逃 怠 杆 毗 窝 频 奇 淮 成 察 们 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 3级封锁协议 n1级封锁协议 + 事务T在读取数据R之前 必须先对其加S锁，直到事务结束才释放 n3级封锁协议可防止丢失修改、读脏数据和不 可重复读。 孽 哇 继 侩 卡 贡 乓 蛛 茸 恤 揪 仲 袁 悄 羞 秃 徒 倍 贺 掸 曲 滴 茁 歌 辜 邢 字 辈 宅 滩 遥 揍 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数
22、据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 3级封锁协议 T1T2 Slock A 读A=50 Slock B 读B=100 求和=150 读A=50 读B=100 求和=150 Commit Unlock A Unlock B Xlock B 等待 等待 等待 等待 等待 等待 等待 等待 获得Xlock B 读B=100 BB*2 写回B=200 Commit Unlock B 可重复读 禁 恋 面 模 伶 黄 肺 纫 灶 狄 迅 画 吼 划 寅 钢 智 叮 正 合 坞 补 驾 笆 某 护 犹 萤 司 洲 聊
23、 断 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 3级封锁协议 T1T2 Xlock C 读C= 100 CC*2 写回C=200 ROLLBACK (C恢复为100) Unlock C Slock C 等待 等待 等待 等待 获得Slock C 读C=100 Commit C Unlock C 不读“脏”数据 佩 灵 截 趋 戚 违 罚 掩 疡 舌 拾 诵 纽 聚 佰 逼 烧 套 付 戴 锹 梅 田 愚 侣 胸 臀 忻 兵 购 裹 峪 数 据 库
24、原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 4封锁协议小结 n三级协议的主要区别 n什么操作需要申请封锁 n何时释放锁（即持锁时间） 锹 儡 脊 抠 武 尘 耸 镶 垛 颠 刑 石 吐 呕 钻 僳 略 闪 凉 降 执 癣 佬 粟 嫡 从 逊 诞 烁 御 太 萨 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 封锁协议小结(
25、续) 碧 噎 鲜 乎 绝 速 奢 头 树 渡 坍 系 佬 杀 壳 民 酋 柞 烧 嗅 淮 孵 乓 摩 霓 混 殖 阁 瘦 袒 熄 您 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.4 活锁和死锁 n封锁技术可以有效地解决并行操作的一 致性问题，但也带来一些新的问题 n死锁 n活锁 琉 板 呻 全 刺 敌 拄 缩 渍 隋 滇 耘 双 箕 矣 哟 朔 骡 年 楞 卑 宋 蹭 躁 猪 淮 离 墟 折 庇 内 褐 数 据 库 原 理 （ 李 芳 芳 ）
26、c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.4.1 活锁 趋 绣 俐 看 伏 他 灼 禁 废 饱 贯 恤 冷 熙 腕 肥 袁 援 映 钧 俩 笔 瘩 窝 花 剑 频 紧 带 尖 刮 陆 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 如何避免活锁 采用先来先服务的策略： 当多个事务请求封锁同一数据对象时 n按请求封锁的先后次序对这些事务排队 n
27、该数据对象上的锁一旦释放，首先批准 申请队列中第一个事务获得锁。 戏 豺 牟 病 揣 券 拭 沃 址 绒 暖 意 息 胞 余 旺 儒 鼠 萧 蔼 袄 孕 潜 硅 舵 烃 翼 诬 韭 蚕 东 词 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.4.2 死锁 T1 T2 Xlock R1 . . . Xlock R2 等待 等待 等待 . . . Xlock R2 . . Xlock R1 等待 等待 . 竭 坯 挑 惟 剐 沙 姑 驰 瞎 挟 宙 察
28、 郑 氖 醒 挣 柑 而 删 埠 周 蚊 墩 俊 核 迢 键 觅 擎 轴 靠 轰 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 解决死锁的方法 两类方法 1. 预防死锁 2. 死锁的诊断与解除 歧 祖 赴 资 敢 毒 奏 汕 尚 访 校 歉 种 锦 久 虞 茎 先 秦 烯 赂 岁 媳 若 吃 彬 鄂 栽 跺 熊 穴 答 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Intr
29、oduction to Database System 死锁的预防（续） 预防死锁的方法 n 一次封锁法 n 顺序封锁法 梢 著 缘 啸 台 哉 巾 码 账 许 舰 锰 蹈 厚 习 号 叼 倒 光 煮 妄 锭 桌 噶 海 四 杭 嫩 毕 线 蛀 涸 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System （1）一次封锁法 n要求每个事务必须一次将所有要使用的数据全 部加锁，否则就不能继续执行 n一次封锁法存在的问题：降低并发度 n 扩大封锁范围 n将以后要用到的
30、全部数据加锁，势必扩大了 封锁的范围，从而降低了系统的并发度 幸 牢 食 乒 螟 沉 胰 码 宾 晴 敏 瘩 窖 规 越 澡 腾 和 斟 狮 律 恿 赴 污 剥 去 恳 谗 勒 弹 诸 奖 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 一次封锁法（续） n难于事先精确确定封锁对象 n数据库中数据是不断变化的，原来不 要求封锁的数据，在执行过程中可能 会变成封锁对象，所以很难事先精确 地确定每个事务所要封锁的数据对象 n解决方法：将事务在执行过程中可能
31、要封锁的数据对象全部加锁，这就进 一步降低了并发度。 熬 筛 二 揖 剐 互 族 杀 乌 眺 梭 坎 爬 才 茄 摧 充 锦 判 拢 到 畜 梗 蛰 喳 柯 瓷 铆 帐 填 胀 弯 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System （2）顺序封锁法 n顺序封锁法是预先对数据对象规定一个封锁顺 序，所有事务都按这个顺序实行封锁。 n顺序封锁法存在的问题 n 维护成本高 n数据库系统中可封锁的数据对象极其众多， 并且随数据的插入、删除等操作而不断地变 化，要维
32、护这样极多而且变化的资源的封锁 顺序非常困难，成本很高 枯 趾 伶 矢 滇 吓 承 中 廊 论 佃 呸 勾 吱 宪 脆 屁 秘 厕 副 籍 干 湿 采 玫 姥 矮 擒 淳 钡 现 卵 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 顺序封锁法（续） n难于实现 n事务的封锁请求可以随着事务的执行而 动态地决定，很难事先确定每一个事务 要封锁哪些对象，因此也就很难按规定 的顺序去施加封锁。 例：规定数据对象的封锁顺序为A,B,C,D,E。事 务T3起初要求
33、封锁数据对象B,C,E，但当它封 锁了B,C后，才发现还需要封锁A，这样就破坏 了封锁顺序. 谦 玄 奥 羚 讣 箭 譬 碍 兑 侵 肛 仕 民 络 叁 挎 殊 以 沪 拉 梧 笺 汹 玻 荐 补 遵 箕 撩 冒 逾 荡 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 死锁的预防（续） n结论 n在操作系统中广为采用的预防死锁的策略并 不很适合数据库的特点 nDBMS在解决死锁的问题上更普遍采用的是 诊断并解除死锁的方法 宰 简 顾 雪 此 显 机 婶
34、纤 零 宅 伍 框 戴 聘 酣 弄 卸 淮 像 颤 涤 寸 涛 腾 可 喝 魂 性 履 诀 膨 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 2. 死锁的诊断与解除 n允许死锁发生 n解除死锁 n由DBMS的并发控制子系统定期检测系统中 是否存在死锁 n一旦检测到死锁，就要设法解除 蜂 氨 等 侵 首 生 状 瘦 钝 根 翼 蝎 眩 犁 颓 漠 粱 脚 斡 郊 表 梧 峡 汹 宇 稿 套 茁 贼 粳 帮 懈 数 据 库 原 理 （ 李 芳 芳 ） c
35、h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 检测死锁：超时法 n如果一个事务的等待时间超过了规 定的时限，就认为发生了死锁 n优点：实现简单 n缺点 n有可能误判死锁 n时限若设置得太长，死锁发生后 不能及时发现 承 拟 庸 盂 击 驭 杯 叫 闺 吟 烽 榴 机 抿 返 徊 紫 群 蝎 誊 遮 岭 束 介 硼 拥 遵 步 侈 励 希 璃 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to
36、 Database System 等待图法 n用事务等待图动态反映所有事务的等待情况 n事务等待图是一个有向图G=(T，U),若T1等待T2，则 T1，T2之间划一条有向边，从T1指向T2 n并发控制子系统周期性地（比如每隔1 min）检测事务 等待图，如果发现图中存在回路，则表示系统中出现 了死锁。 慑 惨 纽 双 捕 自 杰 仿 蠕 祭 鸡 俯 录 矾 屉 阴 睹 儿 翼 刮 店 电 韵 炙 楼 鸡 泰 呜 凝 卜 以 篮 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Datab
37、ase System 死锁的诊断与解除（续） n解除死锁 n选择一个处理死锁代价最小的事务， 将其撤消，释放此事务持有的所有的 锁，使其它事务能继续运行下去。 京 利 鹿 庙 骂 酚 运 符 肩 诉 秒 法 戎 荔 汀 少 倔 款 场 撞 葡 囚 缘 帅 蝎 垣 焰 献 涌 觉 掩 惩 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.5 并发调度的可串行性 一、什么样的并发操作调度是正确的 二、如何保证并发操作的调度是正确的 坟 钉 猜 泳 舷 逮
38、 附 菲 恿 槽 逞 诬 畴 澡 失 绝 阔 司 陛 咨 冠 搅 入 控 耳 跋 潘 苦 岩 蘸 连 抒 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 什么样的并发操作调度是正确的（续） n以不同的顺序串行执行事务也有可能会产生不 同的结果，但由于不会将数据库置于不一致状 态，所以都可以认为是正确的。 n 几个事务的并行执行是正确的，当且仅当其结 果与按某一次序串行地执行它们时的结果相同 。这种并行调度策略称为可串行化（ Serializable）的调
39、度。 当 譬 闰 靖 节 客 非 凹 览 茹 柴 葵 廷 醚 虽 爆 周 甘 富 缀 辱 而 馋 蒙 霓 要 您 苫 腺 举 匡 欺 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 什么样的并发操作调度是正确的（续） n可串行性是并行事务正确性的唯一准则 例：现在有两个事务，分别包含下列操作： 事务1：读B；A=B+1；写回A； 事务2：读A；B=A+1；写回B； 假设A的初值为2，B的初值为2。 呛 恼 分 伯 究 唇 趟 禹 摩 挨 银 取 佐 邵
40、阅 蚤 敢 届 盔 郭 卿 筒 蚜 评 淘 晨 蜒 无 恃 乒 允 更 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 什么样的并发操作调度是正确的（续） n对这两个事务的不同调度策略 n串行执行 n串行调度策略1 n串行调度策略2 n交错执行 n不可串行化的调度 n可串行化的调度 览 潮 穿 霖 笑 怜 啡 遁 揪 悦 蛔 这 吴 凋 军 爱 藐 涎 号 冠 聪 拈 操 梅 诀 于 篷 曙 颗 狼 照 葛 数 据 库 原 理 （ 李 芳 芳 ） c h
41、 p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System (a) 串行调度策略，正确的调度 Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A(=3) Unlock A Slock A X=A=3 Unlock A Xlock B B=X+1 写回B(=4) Unlock B T1T2 奔 势 奢 奎 辰 红 舶 杀 个 氖 城 容 殆 打 组 收 贿 烷 乍 倾 坯 欧 闰 畏 味 筏 查 诬 耍 汇 乓 赘 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据
42、库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System (b) 串行调度策略，正确的调度 Slock B Y=B=3 Unlock B Xlock A A=Y+1 写回A(=4) Unlock A SlockA X=A=2 Unlock A Xlock B B=X+1 写回B(=3) Unlock B T1T2 赦 徘 榴 巩 茧 辕 夷 倍 敷 寸 熔 男 营 出 昔 贰 蘸 撒 铰 絮 抓 坦 亿 谓 拽 呸 婪 伞 罚 睦 卫 臼 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳
43、芳 ） c h p 1 1 An Introduction to Database System (c) 不可串行化的调度 Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A(=3) Unlock A Slock A X=A=2 Unlock A Xlock B B=X+1 写回B(=3) Unlock B T1T2 撒 官 檄 宇 驳 沃 愿 苫 疥 浙 疽 轻 韶 炭 淹 崔 嘶 声 堪 篷 封 遣 莽 躇 径 座 肋 畅 加 植 勒 字 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 A
44、n Introduction to Database System (c) 不可串行化的调度(续) n由于其执行结果与(a)、(b)的结果都不同， 所以是错误的调度。 唱 榆 肉 员 骇 霓 涨 刚 藐 遮 颅 海 吩 绅 妨 鳞 厅 衬 诽 洁 碱 屠 等 钓 记 塑 饶 迭 羊 力 拨 昨 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System (d) 可串行化的调度 Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A(=3)
45、Unlock A Slock A 等待 等待 等待 X=A=3 Unlock A Xlock B B=X+1 写回B(=4) Unlock B T1T2 甚 贮 硷 浚 粱 晦 亏 娱 冷 年 薯 翱 熏 趴 焙 裙 杨 谈 掳 俏 边 防 澄 趋 综 柿 懦 喉 盂 闯 讥 装 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System (d) 可串行化的调度（续） n由于其执行结果与串行调度（a）的执行 结果相同，所以是正确的调度。 耍 兄 杠 挤 丹 锡 揉
46、姑 刨 侥 雀 梯 启 攫 逼 洱 省 师 省 塘 厩 感 粱 反 跨 摄 疼 迫 及 袄 核 峰 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 冲突可串行化调度 n可串行化调度的充分条件 n一个调度Sc在保证冲突操作的次序不变的情 况下，通过交换两个事务不冲突操作的次序 得到另一个调度Sc，如果Sc是串行的，称 调度Sc为冲突可串行化的调度。 n一个调度是冲突可串行化，一定是可串行化 的调度。 An Introduction to Database System 议 稼 氨 擞 轧 按 钡 富 睡 录 吞 亥 路 涡
47、琢 初 肝 蛇 肿 反 搏 袖 嚷 咯 宙 涩 遵 着 暮 蛾 啦 朴 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 冲突可串行化调度（续） n冲突操作 n冲突操作是指不同事务对同一个数据的读写 操作和写写操作。 Ri(x)与Wj(x) Wi(x)与Wj(x) n不同事务的冲突操作和同一个事务的两个操 作不能交换。 An Introduction to Database System 垣 滓 且 极 止 馆 试 联 堰 殴 帖 钥 枚 垛 榔 象 坪 邢 撅 纳 烙 靛 柿 晰 笑 砧 杉 喧 忿 猜 聚 俗 数 据 库
48、 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 冲突可串行化调度(续) 【例4】今有调度 Sc1=r1(A)w1(A) r2(A) w2(A) r1(B) w1(B) r2(B) w2(B) An Introduction to Database System 侣 撑 旺 廷 惮 巡 胁 石 麓 勇 拢 构 琉 汇 席 察 阎 航 耗 蛤 进 妊 螺 怠 磅 影 屠 词 搭 挣 盛 哈 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introductio
49、n to Database System 11.5 并发调度的可串行性 一、什么样的并发操作调度是正确的 二、如何保证并发操作的调度是正确的 菠 礁 樟 萤 住 坝 冷 徐 碳 腆 乎 残 马 肥 辆 妇 粟 氯 减 厕 办 舵 甲 扒 爱 访 剂 童 钻 犀 妒 梳 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 如何保证并发操作的调度是正确的（续） n保证并发操作调度正确性的方法 n封锁方法：两段锁（Two-Phase Locking， 简称2PL）协议 n时标方法 n乐观方法 香 鸯 耗 渺 弗 姨 涂 蛤 详 良 答 傲 咏 镣 代 米 滴 召 投 弟 膳 倒 煤 赁 慎 侥 澳 蛆 宋 扎 闸 毯 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 数 据 库 原 理 （ 李 芳 芳 ） c h p 1 1 An Introduction to Database System 11.6 两段锁协议 n两段锁协议的内容 1.