数据库总复习第十一章 并发控制_遵循两段锁协议的调度例题

第十一章 并发控制

11.1 并发控制概述

事务是并发控制的基本单位

并发操作带来的数据不一致性
R(x)：读数据x
W(x)：写数据x

丢失修改
T2的提交结果破坏了T1的提交结果，导致T1的修改被丢失

不可重复读

1. T1读取某一数据，T2对其做了修改，当事务T1再次读该数据，得到与前一次不同的值
2. T1读取某些数据，T2删除其中部分数据，当T1再次读取数据，发现某些记录消失了
3. T1读取某些数据，T2插入了一些数据，当T1再次读取数据，发现多了一些记录

读脏数据

• T1修改某一数据，并将其写回磁盘
• T2读取同一数据后，T1由于某种原因被撤销
• 这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致
• T2读到的数据就为“脏”数据，即不正确的数据

11.1.1 调度概念

调度：“事务集”中的一串有序操作集，一个事务中操作在调度中的顺序应该于他们在事务中的顺序一致

每个事务最后的行动：COMMIT和ROLLBACK

并发控制的主要技术

• 封锁
• 时间戳
  • 事先选定事务的次序，按照这个时间戳来解决事务的冲突操作
• 乐观控制法
  • 事务提交前再进行正确性检查

11.2 封锁

• 排他锁（X锁）
  • 若T对数据对象A加上X锁，则只允许T读取和修改A，其他事务在T释放A上的锁之前都不能读取和修改A
• 共享锁（S锁）
  • T能读取A不能修改A，其他事务只能对A上S锁而不能上X锁，直到T释放A上的S锁为止

11.3 封锁协议

• 一级封锁协议
  • 事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放
• 二级封锁协议
  • 在一级封锁协议的基础上增加事务T在读取数据R之前必须对其加S锁，读完后即可释放S锁
• 三级封锁协议
  • 在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放

11.4 活锁和死锁

避免活锁：采取先来先服务原则

产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待现象

解决死锁：

• 预防死锁
  • 一次封锁法
    • 要求每个事务必须一次将所有要使用的数据全部加锁，否则就能继续执行
  • 顺序封锁法
    • 预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实施封锁
• 死锁的诊断与解除

死锁的诊断

• 超时法
  • 实现简单，但有可能误判死锁，时限设置太长死锁发生后不能及时发现
• 事务等待图
  • 图中存在回路则表示出现死锁
    

死锁的解除
选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事务得以继续进行下去

11.5 并发调度的可串行性

可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。

可串行性是并发事务正确调度的准则

冲突操作：不同的事务对同一个数据的读写操作和写写操作，其他不冲突

冲突可串行化调度：一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度

冲突可串行化一定是可串行化调度，可串行化不一定冲突可串行化

盲目写：在执行W(Q)之前没有执行R(Q)的操作，存在于任何不是冲突可串行化的视图可串行化调度中
视图可串行化：两个调度每个事务都读取相同数据从而进行相同的计算

11.5.1 调度冲突可串行化的判定（例题）

11.6 两段锁协议

第一阶段：获得封锁，也称为扩展阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁

第二阶段：释放封锁，也称为收缩阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁

若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的

一次封锁发遵守两段锁协议

两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

11.7 封锁的粒度

封锁对象的大小称为封锁粒度

封锁的对象：逻辑单元（属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库），物理单元（页、物理记录）

• 封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小
• 封锁的粒度越小，并发度较高，但系统的开销也就越大

11.7.1 多粒度树

• 根结点是整个数据库，表示最大的数据粒度
• 叶结点表示最小的数据粒度
  

多粒度封锁中一个数据对象可能以两种方式封锁：

• 显式封锁
  • 直接加到数据对象上的封锁
• 隐式封锁
  • 该数据对象没有独立加锁，是由于其上级节点加锁而使该数据对象加上了锁

对某个数据对象加锁，系统要检查

• 该数据对象
  • 有无显式封锁与之冲突
• 所有上级结点
  • 检查本事务的显式封锁是否与该数据对象上的隐式封锁冲突：（由上级结点已加的封锁造成的）
• 所有下级结点
  • 看上面的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突

11.7.2 意向锁

目的：提高对某个数据对象加锁时系统的检查效率

对任一结点加基本锁，需要对上层结点加意向锁

意向锁类型：

• IS锁：意向共享锁
• IX锁：意向排他锁
• SIX锁：共享意向排他锁
  • 例如对某个表加SIX锁，则表示该事务要读整个表（S锁），同时会更新个别元组（IX锁）

具有意向锁的多粒度封锁方法

• 申请封锁时应该按自上而下的次序进行
• 释放封锁时应该按自下而上的次序进行

例如：事务T1要对关系R1加S锁

• 要首先对数据库加IS锁
• 要检查数据库和R1是否已加了与S不相容的锁（X或IX或SIX）
• 不再需要搜索和检查R1中的元组是否加了不相容的锁（X锁）