事务调度的可串行性.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,8.5,事务调度的可串行性,引言,DBMS,需对多个并发事务进行运行调度,能将所有事务串行起来的调度策略不会破坏数据库的不一致性，故而总是正确的,概念,可串行化的调度,：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同,可串行性是并发事务操作是否正确的判别准则,事务调度的可串行性,为了保证并发操作的正确性，,DBMS,的并发控制机制必须提供一定的手段来保证调度是可串行化的,保证事务调度可串行性的策略,事务排它式执行,(,资源无法充分共享,),两段锁,(Two-Phase Locking,2PL),协议,其它，如时间戳,(,TimeStamp,),方法等,DBMS,普通采用封锁方法实现并发操作调度的可串行性,并发事务的不同调度策略,T1,T2,T1,T2,T1,T2,Slock,B,Y=B=2,Unlock B,Xlock,A,A=Y+1,写回A(,=3,),Unlock A,X=A=3,Unlock A,写回,B(,=4,),Unlock B,Slock,A,Xlock,B,B=X+1,a,串行调度,c,不可串行化的调度,(,结果与,a,b,不同，错误调度,),Slock,B,Y=B=2,Unlock B,Xlock,A,A=Y+1,写回A(,=3,),Unlock A,X=A=2,Unlock A,写回,B(,=3,),Unlock B,Slock,A,Xlock,B,B=X+1,Slock,B,Y=B=2,Unlock B,Xlock,A,A=Y+1,写回A(,=3,),Unlock A,Slock,A,X=A=3,Unlock A,写回,B(,=4),Unlock B,Xlock,B,B=X+1,等待,等待,等待,T1,T2,Slock,B,Y=B=3,Unlock B,Xlock,A,A=Y+1,写回A(,=4,),Unlock A,X=A=2,Unlock A,写回,B(,=3,),Unlock B,Slock,A,Xlock,B,B=X+1,d,可串行化的调度,(,结果与,a,相同，正确调度,),T1:,读,B;A=B+1;,写回,A;T2:,读,A;B=A+1;,写回,B;A,B,初值均为,2,b,串行调度,8.6,两段锁协议,概念：事务对数据项的加锁和解锁分为两个阶段完成,获得封锁,：在对数据读写之前首先申请并获得封锁；,释放封锁,：在释放一个封锁后不再申请和获得任何其他封锁,如遵守两段锁协议的事务,Slock,A,Slock,B,Xlock,C.,Unlock B Unlock A Unlock C,如不遵守两段锁协议的事务,Slock,A,Unlock A,Slock,B.,Xlock,C,Unlock C,Unlock B,两段锁协议的性质,两段锁协议是可串行化调度的充分条件，但不是必要条件,若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的；,若对并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议,两段锁协议可以保证并发事务的正确性，但可能发生死锁,T1,T2,T1,T2,T1,T2,Slock,B,读B=2,Y=B,A=Y+1,写回,A=3,Unlock B,Unlock A,Slock,A,等待,等待,读A=3,Unlock B,Unlock A,等待,等待,Y=A,写回,B(=4),Slock,B,读B=2,Y=B,Xlock,A,A=Y+1,Slock,A,等待,等待,读A=3,Xlock,B,B=X+1,等待,等待,X=A,Unlock A,Unlock B,写回,A(=3),Unlock A,Slock,B,读B=2,Xlock,A,Slock,A,等待,Xlock,B,等待,可串行调度,遵守两段锁协议,可串行调度,不遵守两段锁协议,遵守两段锁协议的事务发生死锁,关于两段锁协议,Xlock,A,等待,Xlock,B,B=Y+1,写回,B(=4),Unlock B,读A=2,等待,8.7,封锁的粒度,封锁的粒度即封锁对象的大小，如,逻辑单元,：属性、元组、关系、索引、数据库等,物理单元,：页、块等,封锁粒度对并发控制的影响,封锁粒度越大，并发度越小，系统封锁开销越小；,封锁粒度越小，并发度越高，系统封锁开销越大；,封锁粒度,修改属性？,修改关系？,如何选择封锁粒度？,多粒度封锁,定义：一个系统中同时支持多种封锁粒度供不同事务选择的方法,术语：结点、上层结点、后裔结点,多粒度树,显式封锁,(,应事务要求直接加锁,),隐式封锁,(,由于上层结点加锁而加锁,),数据库,关系,R1,关系,Rn,元组,元组,元组,元组,多粒度封锁的问题,操作办法,对某个数据对象加锁，系统要检查该对象上有无显式封锁与之冲突；,还要检查所有上级结点，看本事务的显式封锁是否与该对象上的隐式封锁冲突；,还有检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突,问题：检查效率低,数据库,关系,R1,关系,Rn,元组,元组,元组,元组,意向锁,概念：如果对以一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁,三种意向锁,意向共享锁,(IS),意向排它锁,(IX),共享意向排它锁,(SIX)=S+IX,对某个表加,SIX,，,表示该事务要读整个表，同时会更新个别元组,扩充的封锁相容矩阵,锁的,强度的偏序关系,T1 T2,S,X,IS,IX,SIX,-,S,Y,N,Y,N,N,Y,X,N,N,N,N,N,Y,IS,Y,N,Y,Y,Y,Y,IX,N,N,Y,Y,N,Y,SIX,N,N,Y,N,N,Y,-,Y,Y,Y,Y,Y,Y,X,SIX,S,IX,IS,具有意向锁的多粒度封锁方法的特点,任意事务要对一个数据对象加锁，必须先对其上层结点加意向锁。申请封锁时按自上而下的次序进行，释放封锁时按自下而上的次序进行,该方法提高了系统的并发度，减少了加锁和解锁的开销,习题,P280 13,题,