111封锁协议

2020/1/161第11章并发控制讲课内容：事务最基本的特性之一就是隔离性。当DBMS中有多个事务并发执行时，事务的隔离性就不一定能保持。DBMS必须对并发事务之间的相互作用加以控制，这种控制是通过并发控制机制来实现的。所谓的并发控制机制本质上就是并发控制协议，这些协议是一组规则，用来决定冲突的事务是回滚重启还是等待执行。本章要讨论的所有协议都能保证调度是可串行化的！■封锁协议■有效性检查协议■死锁处理■树形协议■多粒度机制■插入与删除■时间戳排序协议■多版本机制■本章总结2020/1/162§11.1封锁协议加锁的理由保证调度可串行化的方法之一是对数据项的访问以互斥的方式进行：•当一个事务访问某个数据项时，其他任何事务都不能修改该数据项。实现这个要求的最常用的方法就是：•只有当一个事务目前在一个数据项上持有某种锁时，DBMS才允许该事务访问这个数据项；•否则，就……2020/1/163§11.1封锁协议给数据项加锁的类型共享锁：•如果事务T获得了数据项Q上的共享锁(记为S)，则T可读Q但不能写Q。排他锁：•如果事务T获得了数据项Q上的排他锁(记为X)，则T既可读Q又可写Q。根据操作要求事务给数据项申请适当的锁该请求是发送给DBMS的并发控制管理器的；只有在并发控制管理器授予事务所需要的锁之后，事务才能继续其操作。2020/1/164§11.1封锁协议一个数据项上到底能加有多少个锁？锁和锁之间的关系是什么？令A与B代表任意类型的锁，已知如下条件：•事务Ti正请求对数据项Q加A类型锁；•而另一个事务Tj当前在数据项Q上持有B类型锁。结论：•尽管数据项Q上已加有B类型锁，但如果事务Ti可以立即获得数据项Q上的A类型锁，则称A类型锁与B类型锁相容。锁相容矩阵只有其值为TRUE的两类锁才相容。2020/1/165§11.1封锁协议基本的封锁协议加锁：•要访问一个数据项，事务T必须首先申请给该数据项加锁：如果该数据项已经被另一事务加上了不相容类型的锁，则在所有不相容类型的锁被释放之前，并发控制管理器不会授予事务T申请的锁；因此T必须等待，直到所有不相容类型的锁被释放。解锁：•只要事务T还在访问某数据项，它就必须拥有该数据项上的锁；•除此之外，事务T可以随时释放先前它加在某个数据项上的锁。2020/1/166§11.1封锁协议加锁与解锁的表达假设Q代表数据项加锁指令：•lock-S(Q)：申请Q上的共享锁；•lock-X(Q)：申请Q上的排他锁。解锁指令：•unlock(Q)：释放Q上相应的锁。2020/1/167§11.1封锁协议带锁的调度事务T1申请锁并发控制管理器检查是否可以授予锁？如果可以，grant-X(A,T1)指令将授予锁如果不可以，则事务T1就必须等待！2020/1/168§11.1封锁协议基本封锁协议的问题从前面的例子可以看出，即使在调度中采用了基本的封锁协议，也还有可能导致数据库不一致。因此基本的封锁协议也有缺陷：•解锁问题：在事务中过早地释放数据项上的锁，有可能导致数据库的不一致。•死锁问题：所有的事务因为持有锁和申请锁而导致大家都处于等待状态，无法继续执行；•饿死问题：一个事务总是不能在某个数据项上加上锁，因此该事务也就永远不能取得进展。2020/1/169§11.1封锁协议解锁与死锁问题如果对数据项进行读写之后立即解锁，容易造成数据库的不一致，那么是否把解锁的时机往后推到事务的末尾就万事大吉了呢？解锁的时机不仅影响事务的并发度，同时还有可能造成调度的死锁！•死锁比造成数据库不一致要好，因为死锁可以通过DBMS回滚某事务加以解决；而…2020/1/1610§11.1封锁协议饿死问题锁的授予：•事务申请对某数据项加某种类型的锁；•没有其他事务在该数据项上持有与该事务所申请的锁不相容的锁；•此时，并发控制管理器才可以授予锁。当事务Ti申请对数据项Q加M型锁时，授权加锁的条件是：①不存在其他事务在数据项Q上持有与M型锁冲突的锁；②不存在其他事务等待对数据项Q加锁且先于Ti申请加锁。2020/1/1611两阶段封锁协议为了解决事务的解锁问题，该协议要求每个事务分两个阶段提出加锁和解锁申请：•增长阶段：事务可以获得锁，但不能释放锁。•缩减阶段：事务可以释放锁，但不能获得锁。对于一个事务而言：§11.1封锁协议：解锁时机2020/1/1612§11.1封锁协议两阶段封锁协议饿死问题：•DBMS中并发控制管理器授权加锁的两个条件。解锁问题：•两阶段封锁协议指出了事务释放锁的时机，使得解锁指令也不必非得出现在事务的末尾，增加了事务之间的并发度。死锁问题：•在调度中可能还会有死锁发生，真正的原因是什么呢？2020/1/1613封锁点对任何一个事务而言，在调度中获得其最后一个锁的时刻，称为该事务的封锁点。思考调度中多个事务可根据它们的封锁点进行排序，该顺序就是事务的一个可串行化次序。§11.1封锁协议2020/1/1614加强的两阶段封锁协议问题的提出：•在两阶段封锁协议下，还有一个问题就是在发生故障的情况下调度中事务的级联回滚可能发生。举例：•如右图所示§11.1封锁协议2020/1/1615加强的两阶段封锁协议严格两阶段封锁协议：•除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务提交之后方可释放；•这个要求保证未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据。强两阶段封锁协议：•该协议要求事务提交之前不得释放任何锁，它旨在让冲突的事务尽可能地串行执行；可重复读！•这样调度中的事务可以按其提交的顺序串行化；•事务提交的顺序与前面讲的封锁点顺序一致吗？§11.1封锁协议问题：降低了事务之间的并发度！2020/1/1616锁的转换问题的提出：•如果事务一开始就申请排他锁并获得该锁，那么其他事务只能在该事务提交之后才有可能获得锁而继续执行；•也就是说，加强的两阶段封锁协议虽然保证了调度不会发生级联回滚，但却降低了事务之间的并发度。举例：•事务T12必须对数据项a1加排他锁，结果导致……§11.1封锁协议2020/1/1617锁的转换问题的解决：•事实上，只是在T12写a1的时候才需要对a1加排他锁；•因此，一开始T12只要对a1加共享锁就可以，只是在需要时再将其变为排他锁，这样T12和T13就可以真正地实现并发执行。锁的升降级：•upgrade表示将共享锁升级为排他锁，只能发生在……•downgrade表示将排他锁降级为共享锁，只能发生在……§11.1封锁协议2020/1/1618商用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封锁协议2020/1/1619树状协议。T1:DBGET2:DH§11.2并发调度中的事务冲突ABCDGHJEFI2020/1/1620事务冲突封锁协议要求事务在操作数据前，必须向并发控制管理器申请锁：•如果事务没有立刻获得相关的锁，就说明系统中有冲突的事务，它必须等待。系统中并发的事务之间存在哪些冲突？这些冲突会造成哪些问题(数据库不一致)？•写读冲突：读未提交的数据，即脏读；•读写冲突：不可重复读；•写写冲突：重写未提交的数据，即丢失修改；•幻影：相同的条件，前后两次查询的结果不同。§11.2并发调度中的事务冲突2020/1/1621写读冲突读未提交的数据，即脏读：•事务Tj读取了已经被另一个事务Ti修改，但最终却没有提交的数据项Q。§11.2并发调度中的事务冲突2020/1/1622读写冲突不可重复的读：•当事务Tj读数据对象Q并仍在运行时，事务Ti修改了Q的值。如果Tj再次读Q的值……§11.2并发调度中的事务冲突2020/1/1623写写冲突重写未提交的数据，即丢失修改：•事务Ti和Tj读入同一数据并进行修改，Tj重复写入Q值，并且Ti先于Tj提交。这样Tj提交的结果就破坏了Ti提交的结果，导致Ti的修改丢失。§11.2并发调度中的事务冲突2020/1/1624幻影事务Tj按一定条件读取了某些数据后，事务Ti又插入(删除)了一些满足条件的数据。当Tj再次按相同的条件读取数据时，发现多(少)了一些记录。§11.2并发调度中的事务冲突仅保证它所访问的数据不被其他事务修改是不够的没有阻止其他事务插入新的满足条件的数据2020/1/1625调度中冲突事务的解决方案：封锁协议：•等待执行；•冲突可串行化顺序：事务封锁点的顺序；按事务提交的顺序；每一对冲突事务的可串行化次序是由执行时第一个两者都申请但互相冲突的锁决定的。时间戳排序协议：•回滚重启；•冲突可串行化顺序：事先选定好了事务的串行顺序，即事务进入DBMS的先后顺序。§11.3时间戳排序协议三个顺序的一致性？2020/1/1626时间戳基本概念：•对于系统中的每个事务T，把一个唯一固定的时间标志和事务T联系起来，这个时间标志就是事务的时间戳•时间戳是在事务T开始执行前由DBMS的并发控制管理器赋予事务的，记为TS(T)。时间戳的大小(先后)之分：•如果事务Ti先于事务Tj进入系统，那么：TS(Ti)TS(Tj)实现方式：•使用系统时钟或逻辑计数器§11.3时间戳排序协议2020/1/1627时间戳的特征事务的时间戳决定了调度中事务的可串行化顺序：•若TS(Ti)TS(Tj)，则DBMS保证所产生的调度等价于Ti出现在Tj之前的某个串行调度。每个数据项Q需要和以下两个重要的时间戳相关联：•W-TS(Q)：当前已成功执行write(Q)的所有事务的最大时间戳•R-TS(Q)：当前已成功执行read(Q)的所有事务的最大时间戳•随着读写指令的成功执行，它们随时被更新。§11.3时间戳排序协议2020/1/1628协议内容时间戳排序协议保证并发调度中任何有冲突的read和write操作按时间戳顺序执行。•假设事务Ti发出read(Q)操作：若TS(Ti)W-TS(Q)，则Ti需要读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚；(写读冲突)若TS(Ti)≥W-TS(Q)，则执行read操作，而R-TS(Q)的值被设为R-TS(Q)与TS(Ti)中的较大者。§11.3时间戳排序协议Ti,Tj2020/1/1629协议内容时间戳排序协议保证并发调度中任何有冲突的read和write操作按时间戳顺序执行。•假设事务Ti发出write(Q)操作：若TS(Ti)R-TS(Q)，则Ti产生的Q值是先前所需要的值，但系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚；(读写冲突)§11.3时间戳排序协议Ti,Tj2020/1/1630协议内容•假设事务Ti发出write(Q)操作：若TS(Ti)W-TS(Q)，则Ti想写入的Q值已经丢失。因此，write操作被拒绝，Ti回滚；(写写冲突)其他情况下执行write(Q)操作，并将W-TS(Q)的值设为TS(Ti)。•事务Ti被并发控制机制回滚之后，被赋予新的时间戳并重新启动，进入系统。§11.3时间戳排序协议Ti,Tj2020/1/1631调度举例在时间戳排序协议下：•假设事务在第一条指令执行前的那一刻被赋予时间戳；•对事务要访问的任何数据项来说，假设它们的W-TS和R-TS的初始值都为0(最小)。§11.3时间戳排序协议2020/1/1632Thomas(托马斯)写规则对时间戳排序协议中