第8章 并发控制.ppt

《第8章 并发控制.ppt》由会员分享，可在线阅读，更多相关《第8章 并发控制.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章 并发控制并发控制Silberschatz,Korth and Sudarshan16.2Database System Concepts 3rd Edition主要内容主要内容nIntroduction to IsolationnDependency Model of IsolationnTransaction Dependency Relationsn基于锁的协议基于锁的协议n基于时间戳的协议基于时间戳的协议n基于验证的协议基于验证的协议n多粒度多粒度n多版本多版本n死锁处理死锁处理n插入与删除操作插入与删除操作n索引结构中的并发索引结构中的并发Silberschatz,Kort

2、h and Sudarshan16.3Database System Concepts 3rd EditionIntroduction to Isolationn系统状态系统状态vs.不变式不变式(invariant)“如果向如果向EMP 插入一个记录，相应地必须向插入一个记录，相应地必须向ZIP 插入一条记录。插入一条记录。”“如果如果EMP的一个副本被更新的一个副本被更新,其余副本也必须以同样的方式被更新。其余副本也必须以同样的方式被更新。”“如果一个程序改变了帐户余额，有关的修改必须记录在案。如果一个程序改变了帐户余额，有关的修改必须记录在案。”n如果满足所有这些不变式，如果满足所有这些

3、不变式，则则系统状态被认为是一致的系统状态被认为是一致的n通常一个状态在向另外一个新的且一致性状态转换时，通常一个状态在向另外一个新的且一致性状态转换时，可能会出现短暂的不一致可能会出现短暂的不一致n例如，例如，向向EMP 表插入一条记录，不可能使表插入一条记录，不可能使EMP 以及以及ZIP 索引的插入完全同步索引的插入完全同步n几乎任何一个涉及多个对象更新的变换，都会使它们之几乎任何一个涉及多个对象更新的变换，都会使它们之间有短暂的不一致性间有短暂的不一致性Silberschatz,Korth and Sudarshan16.4Database System Concepts 3rd Ed

4、itionIntroduction to Isolationn为了应付这些短暂的不一致性，为了应付这些短暂的不一致性，将多个相关将多个相关操作以组的方式形成事务，以操作以组的方式形成事务，以保持一致性的约束保持一致性的约束.一个从一致性的系统状态开始的事务，其间会导致临时一个从一致性的系统状态开始的事务，其间会导致临时的不一致状态，但是在事务结束时系统会进入一个新的一致状态的不一致状态，但是在事务结束时系统会进入一个新的一致状态n事务是一致性的单位事务是一致性的单位，这这就就是事务是事务ACID特性中特性中的的C(一致性一致性)的含义的含义n如果事务是隔离地一一在运行，那么每一个事务可以知道其

5、上一个事务所如果事务是隔离地一一在运行，那么每一个事务可以知道其上一个事务所导致的一致性状态导致的一致性状态n但是，但是，如果多个事务并发执行，那么某些事务的输入和后续行为或许会不如果多个事务并发执行，那么某些事务的输入和后续行为或许会不一致，即使每一个隔离执行的事务都是正确的一致，即使每一个隔离执行的事务都是正确的,并发事务的执行必须加以控并发事务的执行必须加以控制以便正确的程序不会失效制以便正确的程序不会失效n这就是事务这就是事务ACID特性中特性中的的I(隔离性隔离性)的含义的含义Silberschatz,Korth and Sudarshan16.5Database System Co

6、ncepts 3rd EditionIntroduction to Isolationn实现隔离最简单的方式就是一次只运行一个程序实现隔离最简单的方式就是一次只运行一个程序(事务事务,前提是前提是:n如果所有的程序都很短小，如果所有数据可以集中存放如果所有的程序都很短小，如果所有数据可以集中存放在主存中，且如果所有的数据都由一个处理器来存取，在主存中，且如果所有的数据都由一个处理器来存取，这时没必要考虑并发来存取这时没必要考虑并发来存取这些程序可以简单地以这些程序可以简单地以顺序方式执行顺序方式执行n问题是，这些情况中包含了太多的问题是，这些情况中包含了太多的”如果如果”n因此，系统必须以某种

7、方式提供并发控制，保证隔离性，因此，系统必须以某种方式提供并发控制，保证隔离性，使之满足并发的第一法则使之满足并发的第一法则n人们已经尝试过许多种提供自动隔离的方法人们已经尝试过许多种提供自动隔离的方法n其中，一个公认可行的解决方案就是封锁其中，一个公认可行的解决方案就是封锁Silberschatz,Korth and Sudarshan16.6Database System Concepts 3rd EditionIntroduction to Isolationn对封锁方法，仍有一系列费解的问对封锁方法，仍有一系列费解的问题题n如果并发控制机制代价过高，会使得代价高于收益。通如果并发控制机

8、制代价过高，会使得代价高于收益。通常，复杂的算法实现起来和执行起来也比较复杂常，复杂的算法实现起来和执行起来也比较复杂n第二法则主张使用简单的算法第二法则主张使用简单的算法Silberschatz,Korth and Sudarshan16.7Database System Concepts 3rd EditionIntroduction to Isolationn最简单的封锁协议是给每个对象加一个锁。如果这个需要锁同时授最简单的封锁协议是给每个对象加一个锁。如果这个需要锁同时授于另外一个事务，该事务将等待这个锁被释放于另外一个事务，该事务将等待这个锁被释放n封锁是一种实现串行化的机制，这样就

9、确保任一时刻仅仅只有一个封锁是一种实现串行化的机制，这样就确保任一时刻仅仅只有一个事务在存取一个对象事务在存取一个对象n通过细化锁的粒度（锁覆盖的数据多少），可以提高并发度通过细化锁的粒度（锁覆盖的数据多少），可以提高并发度n锁的概念可以追溯到几千年以前，它是紧接着门之后的发明锁的概念可以追溯到几千年以前，它是紧接着门之后的发明n现在这个概念（思想）在操作系统领域里已经很普遍了现在这个概念（思想）在操作系统领域里已经很普遍了,在该领域在该领域中，锁又被称为中，锁又被称为:信号量（信号量（semaphores），），管程（管程（monitors）临界区（临界区（critical sections

10、），），串行重用资源（串行重用资源（serially reuseable reuseable resources）Silberschatz,Korth and Sudarshan16.8Database System Concepts 3rd EditionIntroduction to Isolationn事务系统对并发控制的主要贡献是，进一步提炼了原有事务系统对并发控制的主要贡献是，进一步提炼了原有的这些思想，纳入了自动封锁以及把事务的这些思想，纳入了自动封锁以及把事务undo/redo 算算法同封锁算法结合起来法同封锁算法结合起来n这种方法给应用程序开发者一个极简单的并发控制和异这种方法

11、给应用程序开发者一个极简单的并发控制和异常处理的模型常处理的模型n事务处理系统自动地申请加锁并且登录日志以维护事务处理系统自动地申请加锁并且登录日志以维护ACID 特性特性n应用程序设计人员可能疏忽并发控制问题，除非存在着应用程序设计人员可能疏忽并发控制问题，除非存在着许多事务存取同一个对象而引起的性能问题许多事务存取同一个对象而引起的性能问题,所谓的热点所谓的热点（hotspots hotspots）n隔离性理论是允许自动封锁而带来的重要结果隔离性理论是允许自动封锁而带来的重要结果Silberschatz,Korth and Sudarshan16.9Database System Conc

12、epts 3rd EditionDependency Model of Isolationn理解隔离性结果最简单的方式，是根据事务的输入和输理解隔离性结果最简单的方式，是根据事务的输入和输出来理解出来理解n事务要么读一个对象查看其状态，要么写一个对象改变事务要么读一个对象查看其状态，要么写一个对象改变对象的状态对象的状态n设想创建和消除对象只不过是改写其状态而已。以这种设想创建和消除对象只不过是改写其状态而已。以这种粗略的方式来看，事务可以看作是一连串对象的读写操粗略的方式来看，事务可以看作是一连串对象的读写操作作n两个不同事务对同一个对象的读操作不会破坏一致性，两个不同事务对同一个对象的读操

13、作不会破坏一致性，因为读操作不会改变对象的状态（假定其状态初始是一因为读操作不会改变对象的状态（假定其状态初始是一致的）致的）n因此，只有写操作有可能带来问题因此，只有写操作有可能带来问题Silberschatz,Korth and Sudarshan16.10Database System Concepts 3rd EditionDependency Model of Isolationn同一事务对同一个对象的两个写操作也不会违反同一事务对同一个对象的两个写操作也不会违反一致性，一致性，ACID特性假定事务知道它正在干什么特性假定事务知道它正在干什么nACID特性假定：如果事务隔离地运行，最

14、终会特性假定：如果事务隔离地运行，最终会正确地转换系统状态正确地转换系统状态n因此，只有两个并发事务之间同写操作有关联的因此，只有两个并发事务之间同写操作有关联的的交叉操才可能造成不一致性或是违背隔离性的交叉操才可能造成不一致性或是违背隔离性Silberschatz,Korth and Sudarshan16.11Database System Concepts 3rd EditionDependency Model of IsolationSilberschatz,Korth and Sudarshan16.12Database System Concepts 3rd EditionStat

15、ic vs.Dynamic AllocationSilberschatz,Korth and Sudarshan16.13Database System Concepts 3rd EditionStatic vs.Dynamic Allocationn动态分配系统中，每一个事务都被看作是一系列动态分配系统中，每一个事务都被看作是一系列的行为动作而不是输入输出集的行为动作而不是输入输出集n每个动作的请求都在其出现时按需调度。当一个每个动作的请求都在其出现时按需调度。当一个动作存取一个特定的对象时，对象被动态地分配动作存取一个特定的对象时，对象被动态地分配给事务给事务n例如，只有银行帐户记录和其它

16、的一些特别的事例如，只有银行帐户记录和其它的一些特别的事务将要存取的记录分配给该事务务将要存取的记录分配给该事务,出纳员才能运出纳员才能运行一个银行事务行一个银行事务n这样针对不同帐户的事务可以并发地且隔离地执这样针对不同帐户的事务可以并发地且隔离地执行行Silberschatz,Korth and Sudarshan16.14Database System Concepts 3rd EditionTransaction Dependency Relationsn图中显示了两个在对象图中显示了两个在对象e 上的事务上的事务T1 和和T2，所可能有，所可能有的三种读写执行序列操作的三种读写执行序

17、列操作READ-WRITE,WRITE-READ,WRITE-WRITEn没有没有READ-READ 依赖，因为读同一个版本的多个事依赖，因为读同一个版本的多个事务不会产生对另外一个版本的依赖务不会产生对另外一个版本的依赖Silberschatz,Korth and Sudarshan16.15Database System Concepts 3rd EditionTransaction Dependency Relationsn一个依赖图可以看作一个时间序列一个依赖图可以看作一个时间序列:如果事务如果事务T1 到事务到事务T2 有一条边，那么有一条边，那么T1 访问的对象随后会被访问的对象随

18、后会被T2 访访问，并且这些访问中至少有一个产生一个新的版本问，并且这些访问中至少有一个产生一个新的版本在这种意义上，在这种意义上，在这种意义上，在这种意义上，T1 在在 T2之前运行之前运行在事务的纯顺序执行之中，在事务的纯顺序执行之中，T1运行结束，再运行运行结束，再运行T2 T结束，所有的结束，所有的依赖箭头都是从依赖箭头都是从T1 指向指向T2 n隔离定理的主要结论是：任何一个没有环的依赖图都暗示了隔离定理的主要结论是：任何一个没有环的依赖图都暗示了事务的一种隔离执行方式事务的一种隔离执行方式Silberschatz,Korth and Sudarshan16.16Database S

19、ystem Concepts 3rd EditionThe Three BadThe Three BadTransaction DependenciesTransaction Dependenciesn一个令人惊奇的结论是：这三种不一致的基本形式覆盖了所一个令人惊奇的结论是：这三种不一致的基本形式覆盖了所有的情况，如果他们可以被防止发生，那将不会有并发异常，有的情况，如果他们可以被防止发生，那将不会有并发异常，事务将表现为隔离运行的状态事务将表现为隔离运行的状态Silberschatz,Korth and Sudarshan16.17Database System Concepts 3rd E

20、ditionFormal Model of Isolationn为了更精确地描述并发和恢复的问题，需要一个为了更精确地描述并发和恢复的问题，需要一个形式化的模型。因为，这些问题是复杂而又微妙形式化的模型。因为，这些问题是复杂而又微妙的，的，而而形式化有助于摆脱描述形式化有助于摆脱描述问题问题n“隔离性隔离性”的几种等价定义的几种等价定义直观定义直观定义:依据用户事务特性，直观定义是为依据用户事务特性，直观定义是为了方便了方便应用程序设应用程序设计人员和用户用来描述系统的行为计人员和用户用来描述系统的行为形式形式化定义化定义:依据系统执行的过程和依赖图，依据系统执行的过程和依赖图，形式形式化定义

21、是为化定义是为了了陈述和证明隔离性的性质。陈述和证明隔离性的性质。操作上的定义操作上的定义:依据封锁协议，操作上的定义是为依据封锁协议，操作上的定义是为了了用来指导系用来指导系统的实现。统的实现。n下面下面将要对冲突可串行性作形式化描述，将要对冲突可串行性作形式化描述，给出给出严严格定义格定义Silberschatz,Korth and Sudarshan16.18Database System Concepts 3rd Edition插曲插曲:画的圆没有说的圆圆画的圆没有说的圆圆n把想明白的事情把想明白的事情表达表达清楚是作科研的基本功清楚是作科研的基本功,下面是下面是从从Let开始开始的一

22、种下定义的方法。的一种下定义的方法。n例如例如:圆的定义圆的定义定义定义1:右边的图形称为圆右边的图形称为圆(通俗，通俗，但但不及格不及格)定义定义2:到一点的距离相等的轨迹称为圆到一点的距离相等的轨迹称为圆(及格及格)定义定义3:在一个平面上到一点的距离相等的轨迹称为圆在一个平面上到一点的距离相等的轨迹称为圆(良良)定义定义4:Let O be a point over planet P,R=0,and d(x,y)be the distance between points x and y.Then the set C=x|x in P,d(x,O)=R is said to be the

23、 circle with center O and radius R.(信息完整信息完整,严格规范严格规范,所以所以:优优)n严格定义好处严格定义好处:有了符号体系（模型），为后续研究奠定基础有了符号体系（模型），为后续研究奠定基础Silberschatz,Korth and Sudarshan16.19Database System Concepts 3rd EditionFormal Model of Isolationn隔离性隔离性(用户定义用户定义1):n事务处理系统可以并发地执行事务，但它的结果事务处理系统可以并发地执行事务，但它的结果如同顺序执行一样。就应用程序而言，事务好象如同顺

24、序执行一样。就应用程序而言，事务好象是在没有并发的情况下运行；事务的确切执行顺是在没有并发的情况下运行；事务的确切执行顺序是由系统控制的，系统行为等价于事务的某种序是由系统控制的，系统行为等价于事务的某种顺序执行，其造成的表面现象是一个事务执行完顺序执行，其造成的表面现象是一个事务执行完毕后，下一个事务才开始执行毕后，下一个事务才开始执行Silberschatz,Korth and Sudarshan16.20Database System Concepts 3rd EditionFormal Model of Isolationn隔离性隔离性(用户定义用户定义2)：这是更为程序化的定义，称：

25、这是更为程序化的定义，称事务事务T与其它事务是隔离的，如果：与其它事务是隔离的，如果：（0）T不会重写其它事务的脏数据不会重写其它事务的脏数据（1）T所写的数据，在所写的数据，在T提交（提交（COMMIT WORK）之前，不会被其它事）之前，不会被其它事务读或者写务读或者写（2）T不读脏数据不读脏数据（3）在）在T提交之前，其它事务不会写提交之前，其它事务不会写T所要读的数据所要读的数据条件条件(0)和和(1)排除了丢失修改排除了丢失修改,(2)防止了读脏数据防止了读脏数据(3)防止了不可重复防止了不可重复读读n用用Bernstein,Hadzilacos,Goodman1987,p.36 的

26、记法，定义的记法，定义1是是SR，定义，定义2是两阶段封锁（是两阶段封锁（2PL）n SR 2PL：一些隔离性方法比这里描述的封锁机制更具一般性一些隔离性方法比这里描述的封锁机制更具一般性Silberschatz,Korth and Sudarshan16.21Database System Concepts 3rd EditionFormal Model:Actions and TransactionsSilberschatz,Korth and Sudarshan16.22Database System Concepts 3rd EditionFormal Model:Simple Tra

27、nsactionn系统支持系统支持对象上的动作对象上的动作READ，WRITE，XLOCK，SLOCK，UNLOCK三个一般性的动作三个一般性的动作 BEGIN，COMMIT，ROLLBACKn一个简化事务是由一个简化事务是由READ，WRITE，XLOCK，SLOCK，UNLOCK 等动作组成的等动作组成的Silberschatz,Korth and Sudarshan16.23Database System Concepts 3rd EditionLocks Cover Actions(10/21)Silberschatz,Korth and Sudarshan16.24Database

28、System Concepts 3rd EditionWell Formed and Two-PhasedWell Formed and Two-PhasedTransactionsTransactionsSilberschatz,Korth and Sudarshan16.25Database System Concepts 3rd EditionWell Formed and Two-PhasedWell Formed and Two-PhasedTransactionsTransactionsSilberschatz,Korth and Sudarshan16.26Database Sy

29、stem Concepts 3rd EditionTransaction Historyn一组事务的所有动作序列，在保持各自顺序的情况下，一组事务的所有动作序列，在保持各自顺序的情况下，归并成的一个单一序列，我们称之为这组事务的一个归并成的一个单一序列，我们称之为这组事务的一个调调度度n最简单的调度是首先运行一个事务的所有动作，然后再最简单的调度是首先运行一个事务的所有动作，然后再运行另外一个事务的所有动作，如此一直下去，这样的运行另外一个事务的所有动作，如此一直下去，这样的“一次一个事务一次一个事务”的调度称为的调度称为串行调度串行调度(serial history)n调度的定义暗指了每个动

30、作作为对象状态的一个调度的定义暗指了每个动作作为对象状态的一个ACID 转转换：即每个动作是当作一个换：即每个动作是当作一个ACID 步骤来执行的步骤来执行的n下面的问题是，对给定的一组下面的问题是，对给定的一组ACID 动作，如何既能并发动作，如何既能并发执行这些动作，而又保持事务的隔离性执行这些动作，而又保持事务的隔离性Silberschatz,Korth and Sudarshan16.27Database System Concepts 3rd EditionSummary of Definitionsn事务是在对象上的事务是在对象上的 READ，WRITE，SLOCK和和XLOCK

31、动作的序列，它以动作的序列，它以COMMIT 或或 ROLLBACK动作结尾动作结尾n含含COMMIT或或ROLLBACK的一般事务可以转化成为简化的一般事务可以转化成为简化事务，它只含事务，它只含READ,WRITE,SLOCK,XLOCK和和 UNLOCK动作动作n如果事务的每个如果事务的每个READ，WRITE，UNLOCK 都被相应的都被相应的锁覆盖，且所有的锁都是在事务结束时释放，那么我们锁覆盖，且所有的锁都是在事务结束时释放，那么我们称这样的事务是称这样的事务是规范的规范的n如果一个事务可以分成两个阶段，只请求封锁的扩展阶如果一个事务可以分成两个阶段，只请求封锁的扩展阶段，和只释放

32、封锁的收缩阶段，那么我们称之为段，和只释放封锁的收缩阶段，那么我们称之为两阶段两阶段的事务的事务Silberschatz,Korth and Sudarshan16.28Database System Concepts 3rd Edition基于锁的协议基于锁的协议Silberschatz,Korth and Sudarshan16.29Database System Concepts 3rd Edition基于锁的协议基于锁的协议Silberschatz,Korth and Sudarshan16.30Database System Concepts 3rd Edition基于锁的协议基于锁

33、的协议n锁兼容性矩阵锁兼容性矩阵n如果事务对某数据项的锁请求与其他事务在该数据项上如果事务对某数据项的锁请求与其他事务在该数据项上已有的锁兼容已有的锁兼容,则请求被批准则请求被批准n任意数目的事务可对同一数据持有共享锁任意数目的事务可对同一数据持有共享锁;但若一事务但若一事务对某数据持有排他锁对某数据持有排他锁,则其他事务不得持有该数据上的则其他事务不得持有该数据上的任何锁任何锁n若不能授予锁若不能授予锁,则使请求事务等待持有不兼容锁的所有则使请求事务等待持有不兼容锁的所有其他事务释放锁其他事务释放锁.然后才可授予锁然后才可授予锁Silberschatz,Korth and Sudarshan

34、16.31Database System Concepts 3rd Edition基于锁的协议基于锁的协议n执行封锁的事务例执行封锁的事务例:T2:lock-S(A);read(A);unlock(A);lock-S(B);read(B);unlock(B);display(A+B)n上例中的封锁不足以保证可串行化上例中的封锁不足以保证可串行化 若若A和和B 在读操作之间被修改在读操作之间被修改,则显示的总和是错误的则显示的总和是错误的n锁协议锁协议是所有事务在请求与释放锁时遵守的规则集合是所有事务在请求与释放锁时遵守的规则集合n锁协议对可能出现的调度集合加以限制锁协议对可能出现的调度集合加以

35、限制Silberschatz,Korth and Sudarshan16.32Database System Concepts 3rd Edition基于锁的协议的陷阱基于锁的协议的陷阱(死锁死锁)n考虑下面的部分调度考虑下面的部分调度nT3 和和T4 都不能继续都不能继续 执行执行lock-S(B)使使T4 等待等待T3 释放它持有的释放它持有的B上的锁上的锁,而执行而执行 lock-X(A)使使T3 等待等待T4 释放它持有的释放它持有的A上的锁上的锁n这种情形称为死锁这种情形称为死锁n为处理死锁为处理死锁,T3 或或T4 必须回滚并释放它持有的锁必须回滚并释放它持有的锁Silbersch

36、atz,Korth and Sudarshan16.33Database System Concepts 3rd Edition基于锁的协议的陷阱基于锁的协议的陷阱(死锁死锁)n多数锁协议中都存在潜在的死锁可能性多数锁协议中都存在潜在的死锁可能性.但为了锁机制但为了锁机制的好处的好处,这个缺陷的引入是可以容忍的这个缺陷的引入是可以容忍的n如果并发控制管理器设计的不好还可能出现如果并发控制管理器设计的不好还可能出现饿死饿死n例如例如:一个事务可能在等待给数据项加一个事务可能在等待给数据项加X-锁锁,同时一系列其他事务在同时一系列其他事务在请求并被授予同一数据项上的请求并被授予同一数据项上的S-锁

37、锁同一事务因死锁而被重复回滚同一事务因死锁而被重复回滚n并发控制管理器可设计成能够防止饿死并发控制管理器可设计成能够防止饿死Silberschatz,Korth and Sudarshan16.34Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz,Korth and Sudarshan16.35Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预

38、备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz,Korth and Sudarshan16.36Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz,Korth and Sudarshan16.37Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Si

39、lberschatz,Korth and Sudarshan16.38Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段锁不能避免死锁两阶段锁不能避免死锁n两阶段锁不能避免级联回滚两阶段锁不能避免级联回滚n但用但用严格严格(strict)两阶段锁两阶段锁的改进协议可避免的改进协议可避免:事务必须保持它的所有排他锁直至提交事务必须保持它的所有排他锁直至提交/夭折夭折n严密严密(rigorous)两阶段锁两阶段锁更加严格更加严格:所有锁都必所有锁都必须保持到事务提交须保持到事务提交/夭折夭折,在这种协议中事务可按在这种协议中事务可按它们提交的

40、次序串行化它们提交的次序串行化Silberschatz,Korth and Sudarshan16.39Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议n存在用两阶段锁不能得到的冲突可串行化调度存在用两阶段锁不能得到的冲突可串行化调度n即即:给定不遵守两阶段锁的事务给定不遵守两阶段锁的事务Ti,可以找到使可以找到使用两阶段锁的事务用两阶段锁的事务Tj 及及Ti 与与Tj 的一个不是冲突的一个不是冲突可串行化的调度可串行化的调度n然而然而,在缺少额外信息在缺少额外信息(如数据存取次序如数据存取次序)的情况的情况下下,两阶段锁对冲突可串行化要求来说是

41、必要的两阶段锁对冲突可串行化要求来说是必要的Silberschatz,Korth and Sudarshan16.40Database System Concepts 3rd Edition锁转换锁转换n带有锁转换的两阶段锁带有锁转换的两阶段锁:第一阶段第一阶段:（趋势：扩大封锁，减少共享）（趋势：扩大封锁，减少共享）可获得可获得 lock-S可获得可获得 lock-X可转换可转换 lock-S 到到 lock-X(升级升级)第二阶段第二阶段:（趋势：扩大共享，减少封锁）（趋势：扩大共享，减少封锁）可释放可释放 lock-S可释放可释放 lock-X可转换可转换 lock-X 到到 lock-

42、S (降级降级)n本协议确保可串行化本协议确保可串行化,但仍依靠程序员插入各种封锁指令但仍依靠程序员插入各种封锁指令Silberschatz,Korth and Sudarshan16.41Database System Concepts 3rd Edition锁的自动获得锁的自动获得n事务事务Ti 发出标准的读发出标准的读/写指令写指令,无需使用显式的封锁调用无需使用显式的封锁调用n操作操作read(D)的处理如下的处理如下:(把方便留给用户，把困难留给系统）if Ti 在D上有锁 then read(D)else begin 如有必要则等待直至没有事务在如有必要则等待直至没有事务在D上有上

43、有lock-X 授予授予Ti 在在D上的上的lock-S;read(D)endSilberschatz,Korth and Sudarshan16.42Database System Concepts 3rd Edition锁的自动获得锁的自动获得nwrite(D)如下处理如下处理:if Ti 在在D上有上有 lock-X then write(D)else begin 如有必要则等待直至没有事务在如有必要则等待直至没有事务在D上有任何锁上有任何锁,if Ti 在在D上有上有lock-S then 将将D上的锁升级到上的锁升级到 lock-X else 授予授予Ti 在在D上的上的 lock-

44、X write(D)end;n所有锁在提交所有锁在提交/夭折之后释放夭折之后释放Silberschatz,Korth and Sudarshan16.43Database System Concepts 3rd Edition锁管理器锁管理器n锁管理器锁管理器可实现为单独的进程可实现为单独的进程,事务向它发送加锁与释事务向它发送加锁与释放锁请求放锁请求n锁管理器通过发送锁授予消息来回答锁请求锁管理器通过发送锁授予消息来回答锁请求(或死锁时或死锁时发送请事务回滚的消息发送请事务回滚的消息)n请求事务等待请求事务等待,直至它的请求被回答直至它的请求被回答n锁管理器维护一个称为锁管理器维护一个称为锁

45、表锁表的数据结构来记录授予的锁的数据结构来记录授予的锁和挂起的请求和挂起的请求n锁表通常实现为以被锁数据项的名字为索引的内存散列锁表通常实现为以被锁数据项的名字为索引的内存散列表表Silberschatz,Korth and Sudarshan16.44Database System Concepts 3rd Edition锁管理器锁管理器Silberschatz,Korth and Sudarshan16.45Database System Concepts 3rd Edition锁表锁表(Hash(Hash表实现表实现表实现表实现,高效高效高效高效)n黑色矩形表示已授予的锁黑色矩形表示已授

46、予的锁,白色白色矩形表示等待的请求矩形表示等待的请求n锁表记录授予或请求的锁的类型锁表记录授予或请求的锁的类型n新请求加入到对某数据项的请求新请求加入到对某数据项的请求队列的末尾队列的末尾,并且如果与所有以并且如果与所有以前的锁兼容则被授予前的锁兼容则被授予n释放锁请求导致请求被删除释放锁请求导致请求被删除,并并且其后的请求被检查看看现在是且其后的请求被检查看看现在是否可以授予否可以授予n如果事务夭折如果事务夭折,则该事务的所有则该事务的所有等待或已批准的请求都被删除等待或已批准的请求都被删除n锁管理器可能保存每个事务持有锁管理器可能保存每个事务持有的锁的列表的锁的列表,以便对此高效地实以便对

47、此高效地实现现Silberschatz,Korth and Sudarshan16.46Database System Concepts 3rd Edition锁表锁表(HashHash表实现表实现表实现表实现,高效高效高效高效)Silberschatz,Korth and Sudarshan16.47Database System Concepts 3rd Edition基于图的协议基于图的协议n基于图的协议是相对于两阶段锁协议的另一选基于图的协议是相对于两阶段锁协议的另一选择择n在所有数据项集合在所有数据项集合D=d1,d2,.,dh 上定义一上定义一个偏序个偏序(读作goes to 或先

48、于先于)如果如果di dj 则存取则存取di 和和dj 的任何事务都必须先存取的任何事务都必须先存取di 后存取后存取dj集合集合D可视为可视为有向无圈图有向无圈图(特例为树特例为树(有根的图有根的图),表示表示数据的加工流程数据的加工流程)称为数据库图称为数据库图n树协议树协议是图协议的一种简单形式是图协议的一种简单形式Silberschatz,Korth and Sudarshan16.48Database System Concepts 3rd Edition树协议树协议Silberschatz,Korth and Sudarshan16.49Database System Concep

49、ts 3rd Edition树协议树协议n树协议确保冲突可串行化且可避免死锁树协议确保冲突可串行化且可避免死锁n树协议中释放锁可比两阶段锁协议更早发生树协议中释放锁可比两阶段锁协议更早发生较短等待时间较短等待时间,增加并发度增加并发度协议无死锁协议无死锁,不需回滚不需回滚事务的夭折仍然可能导致级联回滚事务的夭折仍然可能导致级联回滚(教材中对此有改进方法教材中对此有改进方法)n然而然而,在树封锁协议中在树封锁协议中,事务可能对它不需要存取的数据项事务可能对它不需要存取的数据项加锁加锁(可能诛连可能诛连(冤枉封锁了冤枉封锁了)太多子孙，诛九族太多子孙，诛九族)增加锁开销以及额外的等待时间增加锁开销

50、以及额外的等待时间潜在的并发度降低潜在的并发度降低n树协议可产生两阶段锁协议不能产生的调度树协议可产生两阶段锁协议不能产生的调度,反之亦然反之亦然.树协议与树协议与2PL没绝对的强弱，各有用武之地没绝对的强弱，各有用武之地Silberschatz,Korth and Sudarshan16.50Database System Concepts 3rd Edition基于时间戳的协议基于时间戳的协议n两种时间戳，分别对事务，对数据两种时间戳，分别对事务，对数据n每个事务进入系统时被赋予一个时间戳，若一个老事务每个事务进入系统时被赋予一个时间戳，若一个老事务Ti 具有时间戳具有时间戳TS(Ti)，