封锁协议.ppt

1第11章 并发控制 讲课内容：讲课内容： 事务最基本的特性之一就是隔离性当DBMS中有 多个事务并发执行时，事务的隔离性就不一定能 保持DBMS必须对并发事务之间的相互作用加以 控制，这种控制是通过并发控制机制并发控制机制来实现的 所谓的并发控制机制本质上就是并发控制协议， 这些协议是一组规则，用来决定冲突的事务是回 滚重启还是等待执行本章要讨论的所有协议都 能保证调度是可串行化的！ ■封锁协议 ■有效性检查协议 ■死锁处理 ■树形协议 ■多粒度机制 ■插入与删除 ■时间戳排序协议 ■多版本机制 ■本章总结*2§11.1封锁协议Ø 加锁的理由 ü保证调度可串行化的方法之一是对数据 项的访问以互斥的方式进行： • 当一个事务访问某个数据项时，其他任何 事务都不能修改该数据项 ü实现这个要求的最常用的方法就是： • 只有当一个事务目前在一个数据项上持有 某种锁时，DBMS才允许该事务访问这个数 据项； • 否则，就……*3§11.1封锁协议Ø 给数据项加锁的类型 ü 共享锁： • 如果事务T获得了数据项Q上的共享锁(记为S)， 则T可读Q但不能写Q ü 排他锁： • 如果事务T获得了数据项Q上的排他锁(记为X)， 则T既可读Q又可写Q。

Ø 根据操作要求事务给数据项申请适当的锁 ü 该请求是发送给DBMS的并发控制管理器的； ü 只有在并发控制管理器授予事务所需要的锁 之后，事务才能继续其操作4§11.1封锁协议Ø 一个数据项上到底能加有多少个锁？Ø 锁和锁之间的关系是什么？ ü 令A与B代表任意类型的锁，已知如下条件： • 事务Ti正请求对数据项Q加A类型锁； • 而另一个事务Tj当前在数据项Q上持有B类型锁 ü 结论： • 尽管数据项Q上已加有B类型锁，但如果事务Ti可 以立即获得数据项Q上的A类型锁，则称A类型锁 与B类型锁相容 Ø 锁相容矩阵 ü 只有其值为TRUE的两类锁才相容5§11.1封锁协议 Ø 基本的封锁协议 ü 加锁： • 要访问一个数据项，事务T必须首先申请给该数 据项加锁： 如果该数据项已经被另一事务加上了不相容类型的 锁，则在所有不相容类型的锁被释放之前，并发控 制管理器不会授予事务T申请的锁； 因此T必须等待，直到所有不相容类型的锁被释放 ü 解锁： • 只要事务T还在访问某数据项，它就必须拥有该 数据项上的锁； • 除此之外，事务T可以随时释放先前它加在某个 数据项上的锁6§11.1封锁协议 Ø 加锁与解锁的表达 假设Q代表数据项 ü加锁指令： • lock-S(Q)：申请Q 上的共享锁； • lock-X(Q)：申请Q 上的排他锁。

ü解锁指令： • unlock(Q)：释放Q 上相应的锁7§11.1封锁协议Ø 带锁的调度 ü 事务T1申请锁 ü 并发控制管理 器检查是否可 以授予锁？ ü 如果可以， grant-X(A,T1) 指令将授予锁 ü 如果不可以， 则事务T1就必须 等待！*8§11.1封锁协议 Ø 基本封锁协议的问题 ü 从前面的例子可以看出，即使在调度中采用 了基本的封锁协议，也还有可能导致数据库 不一致因此基本的封锁协议也有缺陷： • 解锁问题： 在事务中过早地释放数据项上的锁，有可能导致数 据库的不一致 • 死锁问题： 所有的事务因为持有锁和申请锁而导致大家都处于 等待状态，无法继续执行； • 饿死问题： 一个事务总是不能在某个数据项上加上锁，因此该 事务也就永远不能取得进展9§11.1封锁协议 Ø 解锁与死锁问题 ü 如果对数据项进行读写之后 立即解锁，容易造成数据库 的不一致，那么是否把解锁 的时机往后推到事务的末尾 就万事大吉了呢？ ü 解锁的时机不仅影响事务的 并发度，同时还有可能造成 调度的死锁！ • 死锁比造成数据库不一致要 好，因为死锁可以通过DBMS 回滚某事务加以解决；而…*10§11.1封锁协议 Ø 饿死问题 ü 锁的授予： •事务申请对某 数据项加某种 类型的锁； •没有其他事务 在该数据项上 持有与该事务 所申请的锁不 相容的锁； •此时，并发控 制管理器才可 以授予锁。

当事务Ti申请对数据项Q加M型锁 时，授权加锁的条件是：①不存在其他事务在数据项Q上持有 与M型锁冲突的锁；②不存在其他事务等待对数据项Q加 锁且先于Ti申请加锁11Ø 两阶段封锁协议 ü 为了解决事务的解锁 问题，该协议要求每 个事务分两个阶段提 出加锁和解锁申请： • 增长阶段： 事务可以获得锁， 但不能释放锁 • 缩减阶段： 事务可以释放锁， 但不能获得锁 ü 对于一个事务而言：§11.1封锁协议 ：解锁时机*12§11.1封锁协议 Ø 两阶段封锁协议 ü 饿死问题： • DBMS中并发控制管理器授权加锁 的两个条件 ü 解锁问题： • 两阶段封锁协议指出了事务释放 锁的时机，使得解锁指令也不必 非得出现在事务的末尾，增加了 事务之间的并发度 û 死锁问题： • 在调度中可能还会有死锁发生， 真正的原因是什么呢？*13Ø 封锁点 ü 对任何一个事务而言，在调度中获得其最后 一个锁的时刻，称为该事务的封锁点Ø 思考 ü 调度中多个事务可根据它们的封锁点进行排 序，该顺序就是事务的一个可串行化次序§11.1封锁协议*14Ø加强的两阶段封 锁协议 ü 问题的提出： • 在两阶段封锁 协议下，还有 一个问题就是 在发生故障的 情况下调度中 事务的级联回 滚可能发生。

ü 举例： • 如右图所示§11.1封锁协议*15Ø 加强的两阶段封锁协议 ü 严格两阶段封锁协议： • 除了要求封锁是两阶段之外，还要求事务持有的 所有排他锁必须在事务提交之后方可释放； • 这个要求保证未提交事务所写的任何数据在该事 务提交之前均以排他方式加锁，防止其他事务读 取这些数据 ü 强两阶段封锁协议： • 该协议要求事务提交之前不得释放任何锁，它旨 在让冲突的事务尽可能地串行执行；可重复读！ • 这样调度中的事务可以按其提交的顺序串行化； • 事务提交的顺序与前面讲的封锁点顺序一致吗？§11.1封锁协议问题：降低 了事务之间 的并发度！*16Ø 锁的转换 ü 问题的提出： • 如果事务一开始就申请排他 锁并获得该锁，那么其他事 务只能在该事务提交之后才 有可能获得锁而继续执行； • 也就是说，加强的两阶段封 锁协议虽然保证了调度不会 发生级联回滚，但却降低了 事务之间的并发度 ü 举例： • 事务T12必须对数据项a1加排 他锁，结果导致……§11.1封锁协议*17Ø 锁的转换 ü 问题的解决： • 事实上，只是在T12写a1的时候 才需要对a1加排他锁； • 因此，一开始T12只要对a1加共 享锁就可以，只是在需要时再 将其变为排他锁，这样T12和T13 就可以真正地实现并发执行。

ü 锁的升降级： • upgrade表示将共享锁升级为排 他锁，只能发生在…… • downgrade表示将排他锁降级为 共享锁，只能发生在……§11.1封锁协议*18Ø 商用DBMS中封锁协议的实现 ü 在实际的商用DBMS中，根据加强的封锁协议 实现的并发控制机制很简单且被广泛采用； ü 这样的机制能保证并发控制管理器自动为事 务产生加锁、解锁指令： • 当事务T进行read(Q)操作时，系统产生lock- S(Q)指令，后接read(Q)指令； • 当事务T进行write(Q)操作时，系统检查T是否已 在Q上持有共享锁： 若有，则系统发出upgrade(Q)指令，后接write(Q) 指令； 否则系统发出lock-X(Q)指令，后接write(Q)指令； • 事务提交或回滚后，该事务持有的锁都被释放§11.1封锁协议*19Ø 树状协议 Ø T1:DBGE Ø T2:DH§11.2并发调度中的事务冲突ABCDGHJEFI*20Ø 事务冲突 ü 封锁协议要求事务在操作数据前，必须向并 发控制管理器申请锁： • 如果事务没有立刻获得相关的锁，就说明系统中 有冲突的事务，它必须等待 ü 系统中并发的事务之间存在哪些冲突？这些 冲突会造成哪些问题(数据库不一致)？ • 写读冲突：读未提交的数据，即脏读； • 读写冲突：不可重复读； • 写写冲突：重写未提交的数据，即丢失修改； • 幻影：相同的条件，前后两次查询的结果不同。

§11.2并发调度中的事务冲突*21Ø 写读冲突 ü 读未提交的数据，即脏读： • 事务Tj读取了已经被另一个事务Ti修改，但最终 却没有提交的数据项Q§11.2并发调度中的事务冲突*22Ø 读写冲突 ü 不可重复的读： • 当事务Tj读数据对象Q并仍在运行时，事务Ti修改 了Q的值如果Tj再次读Q的值……§11.2并发调度中的事务冲突*23Ø 写写冲突 ü 重写未提交的数据，即丢失修改： • 事务Ti和Tj读入同一数据并进行修改，Tj重复写 入Q值，并且Ti先于Tj提交这样Tj提交的结果就 破坏了Ti提交的结果，导致Ti的修改丢失§11.2并发调度中的事务冲突*24Ø 幻影 ü事务Tj按一定条件读取了某些数据后，事务Ti 又插入(删除)了一些满足条件的数据当Tj再 次按相同的条件读取数据时，发现多(少)了一 些记录§11.2并发调度中的事务冲突仅保证它所访问的 数据不被其他事务 修改是不够的没有阻止其他事务 插入新的满足条件 的数据*25Ø 调度中冲突事务的解决方案： ü 封锁协议： • 等待执行； • 冲突可串行化顺序： 事务封锁点的顺序； 按事务提交的顺序； 每一对冲突事务的可串行化次序是由执行时第一个 两者都申请但互相冲突的锁决定的。

ü 时间戳排序协议： • 回滚重启； • 冲突可串行化顺序： 事先选定好了事务的串行顺序，即事务进入DBMS的 先后顺序§11.3时间戳排序协议三个顺序的 一致性？*26Ø 时间戳 ü 基本概念： • 对于系统中的每个事务T，把一个唯一固定的时 间标志和事务T联系起来，这个时间标志就是事 务的时间戳 • 时间戳是在事务T开始执行前由DBMS的并发控制 管理器赋予事务的，记为TS(T) ü 时间戳的大小(先后)之分： • 如果事务Ti先于事务Tj进入系统，那么： TS(Ti) *29Ø 协议内容 ü 时间戳排序协议保证并发调度中任何有冲突 的read和write操作按时间戳顺序执行 • 假设事务Ti发出write(Q)操作： 若TS(Ti)*30Ø 协议内容 • 假设事务Ti发出write(Q)操作： 若TS(Ti)*31Ø 调度举例 ü 在时间戳排序 协议下： • 假设事务在第 一条指令执行 前的那一刻被 赋予时间戳； • 对事务要访问 的任何数据项 来说，假设它 们的W-TS和R- TS的初始值都 为0(最小)§11.3时间戳排序协议*32Ø Thomas(托马斯)写规则 ü 对时间戳排序协议中事务间“写/写”冲突规 则的重大修改； ü 首先从一个例子开始： • 如图所示，TS(T3)*35Ø 小结 ü 时间戳排序协议保证： • 满足该协议的任何调度冲突可串行化，为什么？ • 满足该协议的任何调度无死锁，为什么？ ü 但该协议不保证： • 所产生的调度都是可恢复的：§11.3时间戳排序协议*36Ø 并发事务的隔离等级 ü 事务的隔离等级控制事务可暴露给其他并发 执行事务的程度； ü 通过选择隔离等级，事务以把未提交的数据 更新暴露给其他事务为代价，获得更高程度 的并发度； ü 一般商用DBMS的隔离等级分为以下四种： • 读未提交(Read Uncommitted) • 读已提交(Read Committed) • 可重复读(Repeatable Read) • 可串行化(Serializable)§11.4事务的隔离等级*37Ø 读未提交： ü 允许事务可以读取未提交的数据； ü 设置事务的隔离等级为“读未提交”，使得 事务不必等待任何锁，也不必对所读的数据 加共享锁； ü 读未提交虽然提高了事务之间的并发度，但 是以牺牲数据库的一致性为代价： • 。