数据库系统概念16并发控制.ppt

* 数据库系统概念----并发控制 * 死锁的预防 结论 在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点 DBMS在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法 * 数据库系统概念----并发控制 * 死锁检测 允许死锁发生 解除死锁 由DBMS的并发控制子系统定期检测系统中是否存在死锁 一旦检测到死锁，就要设法解除 * 数据库系统概念----并发控制 * 检测死锁：超时法 如果一个事务的等待时间超过了规定的时限，就认为发生了死锁 优点：实现简单 缺点 有可能误判死锁 时限若设置得太长，死锁发生后不能及时发现 * 数据库系统概念----并发控制 * 等待图法 用事务等待图动态反映所有事务的等待情况 事务等待图是一个有向图G=(V，E) V为结点的集合，每个结点表示正运行的事务 E为边的集合，每条边表示事务等待的情况 若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2 并发控制子系统周期性地（比如每隔1 min）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。 * 数据库系统概念----并发控制 * 从死锁中恢复 解除死锁 选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务能继续运行下去。 * 数据库系统概念----并发控制 * 小结 数据共享与数据一致性是一对矛盾 数据库的价值在很大程度上取决于它所能提供的数据共享度。 数据共享在很大程度上取决于系统允许对数据并发操作的程度。 数据并发程度又取决于数据库中的并发控制机制 另一方面，数据的一致性也取决于并发控制的程度。施加的并发控制愈多，数据的一致性往往愈好。 * 数据库系统概念----并发控制 * 小结 数据库的并发控制以事务为单位 数据库的并发控制通常使用封锁机制 两类最常用的封锁 * 数据库系统概念----并发控制 * 小结 并发控制机制调度并发事务操作是否正确的判别准则是可串行性 并发操作的正确性则通常由两段锁协议来保证。 两段锁协议是可串行化调度的充分条件，但不是必要条件 * 数据库系统概念----并发控制 * 小结 对数据对象施加封锁，带来问题 活锁： 先来先服务 死锁： 预防方法 一次封锁法顺序封锁法 抢占与回滚 死锁的诊断与解除 超时法 等待图法 * 前言 * * 数据库系统概念----并发控制 * 两阶段封锁协议 两阶段封锁协议不保证不会发生死锁 * 数据库系统概念----并发控制 * 两阶段封锁协议 两阶段封锁协议下，级联回滚可能发生 * 数据库系统概念----并发控制 * 严格两阶段封锁协议 严格两阶段封锁协议除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务结束后，方可释放。 * 数据库系统概念----并发控制 * 强两阶段封锁协议 事务提交之前，不得释放任何锁 在强两阶段封锁协议下，事务可以按其结束的顺序串行化 * 数据库系统概念----并发控制 * 锁转换 Upgrade：从共享锁提升为排他锁 Downgrade：从排他锁降级为共享锁 锁升级只能发生在增长阶段，锁降级只能发生在缩减阶段 * 数据库系统概念----并发控制 * 基于图的协议 树形协议中，可用的加锁指令只有lock-X。每个事务Ti对一个数据项最多只能加一次锁，并且遵循以下规则： - Ti首次加锁可以对任何数据项进行 -此后， Ti对数据项Q加锁的前提是Ti持有Q的父项上的锁 -对数据项的解锁可以随时进行 -数据项被Ti加锁并解锁后， Ti不能再对该数据项加锁 * 数据库系统概念----并发控制 * 提纲 并发控制概述 封锁 时间戳 封锁的粒度 多版本机制 死锁处理 * 数据库系统概念----并发控制 * 基于时间戳的协议 另一种解决事务可串行化的次序的方法是事先选定事务的次序 * 数据库系统概念----并发控制 * 时间戳 对于系统中的每一个事务Ti，将唯一的时间戳与它相联系，记为TS(Ti)。 时间戳的两种简单方法： -系统时钟 -逻辑计数器 事务的时间戳决定了串行化顺序 * 数据库系统概念----并发控制 * 数据项时间戳 W-timestamp(Q)：表示成功执行write(Q)的所有事务的最大的时间戳 R- timestamp(Q)：表示成功执行read(Q)的所有事务的最大的时间戳 * 数据库系统概念----并发控制 * 时间戳排序协议 保证任何有冲突的read或write操作按照时间戳顺序执行 1、假设事务Ti发出read(Q) -如果TS(Ti) W-timestamp(Q)，则Ti需读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚 -如果TS(Ti)= W-timestamp(Q)，则执行read操作，R-