资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,6,数据库保护,数据库恢复,并发控制,数据库安全性,数据库完整性,2,1,、事务的表示方法：,R,i,(X),表示事务,T,i,的读,X,操作；,W,i,(X),表示事务,T,i,的写,X,操作。,例：事务,T1(Read(B),；,A=B+1,；,write(A),，,事务,T2(Read(A),；,B=A+1,；,write(B),可以表示成：,T,1,：,R,1,(B)W,1,(A)T,2,：,R,2,(A)W,2,(B),三、调度的可串行性,3,例,:,事务,T,1,：,R,1,(X)R,1,(Y)W,1,(Y),的执行顺序可表示为,R,1,(X),R,1,(Y),W,1,(Y),符号,表示先于（,),，即,R,1,(X),先于,W,1,(Y),执行，,R,1,(Y),先于,W,1,(Y),执行，而,R,1,(X),和,R,1,(Y),的先后次序无关紧要。,4,2,、冲突操作,定义,：如果两个操作来自不同的事务，它们对同一数据单位进行操作，并且其中至少有一个是写操作，则称这两个操作是相互冲突的或冲突操作。,例：事务,T,0,：,W,0,(X)W,0,(Y)W,0,(Z),事务,T,1,：,R,1,(X)R,1,(Z)W,1,(X),则在这两个事务中有冲突操作：,R,1,(X),与,W,0,(X),W,1,(X),与,W,0,(X),R,1,(Z),与,W,0,(Z),对于冲突操作不能同时执行，哪个先执行，哪个后执行由调度决定。,5,3,、调度,设,=T,1,，,T,2,，,T,n,是一事务集，,的一个调度,S,是一拟序集（,s),其中,:1),说明,S,执行的操作正是,T1,，,T2,，,T n,的操作。,2)s,说明调度,S,遵守每个事务的操作的 内部执行次序,3),每对冲突操作的执行次序由,S,决定。,6,例如：考虑下列两个事务,T,0,，,T,1,T,0,=,W,0,(X),W,0,(Y),W,0,(Z),T,1,=,R,1,(X),R,1,(Z),W,1,(X),T,0,，,T,1,的拟序集表示为：,T,0,=(W,0,(X),W,0,(Y),W,0,(Z),),T,1,=,(R,1,(X),R,1,(Z),W,1,(X),R,1,(X)W,1,(X),R,1,(Z)W,1,(X),7,R,1,(X),R,1,(Z),W,1,(X),S,1,=,W,0,(X),W,0,(Y),W,0,(Z),S,1,=(,W,0,(X),W,0,(Y),W,0,(Z),R,1,(X),R,1,(Z),W,1,(X),，,W,0,(X)R,1,(X),，,W,0,(Z)R,1,(Z),，,R,1,(X)R,1,(Z),，,R,1,(X)W,1,(X),，,R,1,(Z)W,1,(X),),两个事务,T,0,，,T,1,的调度可以表示为：,8,S,2,=,（,W,0,(X),W,0,(Y),W,0,(Z),R,1,(X),R,1,(Z),W,1,(X),，,W,0,(X)R,1,(X),W,0,(Z)R,1,(Z),R,1,(Z)R,1,(X),R,1,(X)W,1,(X),R,1,(Z)W,1,(X),）,R,1,(X),R,1,(Z),W,1,(X),S,2,=,W,0,(X),W,0,(Y),W,0,(Z),两个事务,T,0,，,T,1,的调度可以表示为：,9,R,1,(X),R,1,(Z),W,1,(X),S,3,=,W,0,(X),W,0,(Y),W,0,(Z),S,3,=,（,W,0,(X),W,0,(Y),W,0,(Z),R,1,(X),R,1,(Z),W,1,(X),，,W,0,(X)R,1,(X),W,0,(Z)R,1,(Z),R,1,(X)W,1,(X),R,1,(Z)W,1,(X),）,两个事务,T,0,，,T,1,的调度可以表示为：,10,例：给出事务,T,0,T,1,T,2,T,3,T,4,的一个调度,T,0,=,W,0,(X),W,0,(Y),W,0,(Z),T,1,=,R,1,(X),R,1,(Z),W,1,(X),T,4,=,R,4,(X),R,4,(Y),R,4,(Z),T,2,=,R,2,(X),W,2,(Y),T,3,=,R,3,(Z),W,3,(Y),W,3,(Z),11,一个调度,S,1,W,0,(X),W,0,(Y),W,0,(Z),R,1,(X),R,1,(Z),W,1,(X),R,3,(Z),W,3,(Y),W,3,(Z),R,4,(X),R,4,(Y),R,4,(Z),R,2,(X),W,2,(Y),请写出,S1,的拟序集,12,4,、串行调度,如果在一个调度中，各个事务不交叉执行，而顺序地串行执行，这个调度被称为串行调度。,定义：,如果调度,S,中的任意两个事务,Ti,和,Tj,，如果,Ti,的所有操作都先于,Tj,的所有操作，或者相反，则称,S,为,串行调度,。,注意：,在串行调度中每一个事务都是在下一个事务开始执行之前提交。因此，,串行调度没有并发性,，故每一个串行调度都是一个正确的执行。,13,5,、并发调度,如果在一个调度中，各个事务交叉地执行，这个调度称为并发调度。,14,定义：,多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为,可串行化的调度,。,6,、可串行化的调度,如果一个事务集的并发调度与某一串行调度是等价的，则称该并发调度是可串行化的。,15,7,、串行化定理,定理：,一个调度,S,是可串行化的，当且仅当它的串行图是,无环的。,串行图：,设,S,是若干事务,T1,T2,Tn,的一个调度，,S,的串行图,SG(S),是一个有向图，其构成规则如下：,1,）图中的结点表示事务,2,）如果,O,i,和,O,j,是冲突操作，且,O,i,先于,O,j,执行，则在图中有一条边,T,i,T,j,。,16,R,1,(X),W,1,(X),R,3,(X),W,3,(Z),R,2,(X),W,2,(Y),W,1,(Y),T,2,T,1,T,3,R,1,(X),W,1,(X),R,3,(X),W,3,(X),R,2,(X),W,2,(Y),W,1,(Y),T,2,T,1,T,3,例：,17,8,、等价的串行调度：,如果,SG(S),是无环的，则,S,等价于,SG(S),的任一拓扑排序。,T,2,T,1,T,3,拓扑排序为：,T2,，,T1,，,T3,T,1,T,2,T,3,拓扑排序为：,T1,T3,T2,或为：,T1,T2,T3,18,W,0,(X),W,0,(Y),W,0,(Z),R,1,(X),R,1,(Z),W,1,(X),R,3,(Z),W,3,(Y),W,3,(Z),R,4,(X),R,4,(Y),R,4,(Z),R,2,(X),W,2,(Y),调度,S,的串行图,拓扑排序为：,T0,，,T2,，,T1,，,T3,，,T4,或为：,T0,，,T2,，,T3,，,T1,，,T4,T,0,T,1,T,2,T,3,T,4,19,Read(A),Read(B),Read(C),Write(C),Read(D),Write(C),Read(C),Write(D),Write(B),T,T,2,T,3,可串行化调度,20,1,）某一事务在对数据进行读、写之前，先要申请并获得对该数据的封锁。,2,）在释放一个封锁之后，事务不再申请和获得任何其它封锁。,说明：,规则,1,避免了两个冲突操作同时存取同一数据。规则,2,把每个事务分为两个阶段：上升段和下降段。,上升,下降,每一事务只有得到全部锁以后才放锁。,四、两段锁协议,(2PL,协议,),21,例：对事务,T,1,和,T,2,用两段锁协议加锁的过程,T,1,：,R,1,(X)W,1,(Y),T,2,：,W,2,(X)W,2,(Y),Slock X,Xlock Y,Unlock X,Unlock Y,Xlock X,Xlock Y,Unlock X,Unlock Y,22,2PL,调度优点：简单 缺点：易死锁,例如：对于如下两个事务采用两段锁协议,T,1,：,R,1,(X)W,1,(Y),T,2,：,W,2,(Y)W,2,(X),T1,与,T2,的一个调度过程：,1,初始时，没有事务占有锁,2,调度器接到,R,1,(X),，对,X,加读锁，执行,R,1,(X),。,3,调度器接到,W,2,(Y),，对,Y,加写锁，执行,W,2,(Y),4,调度器接到,W,2,(X),，,T2,等待,5,调度器接到,W,1,(Y),，,T1,等待,这样就造成了死锁。,23,定理：,任何一个遵从,2PL,协议的调度都是可串行化的。,说明：事务遵守,2PL,协议是可串行化调度的充分条件，而不是必要条件。即若并发事务都遵守,2PL,协议，则对这些事务的任何并发调度策略都是可串行化的；若对并发事务的一个调度是可串行化的，不一定所有事务都符合,2PL,协议。,注：三级封锁协议是符合,2PL,协议的,24,两段锁协议（续）,T,1,Slock B,读,B=2,Y=B,Xlock A,A=Y+1,写回,A=3,Unlock B,Unlock A,T,2,Slock A,等待,等待,等待,等待,等待,Slock A,读,A=3,Y=A,Xlock B,B=Y+1,写回,B=4,Unlock B,Unlock A,T,1,Slock B,读,B=2,Y=B,Unlock B,Xlock A,A=Y+1,写回,A=3,Unlock A,T,2,Slock A,等待,等待,等待,等待,Slock A,读,A=3,X=A,Unlock A,Xlock B,B=X+1,写回,B=4,Unlock B,(a),遵守两段锁协议,(b),不遵守两段锁协议,T,1,Slock B,读,B=2,Y=B,Unlock B,Xlock A,A=Y+1,写回,A=3,Unlock A,T,2,Slock A,读,A=2,X=A,Unlock A,Xlock B,等待,Xlock B,B=X+1,写回,B=3,Unlock B,(c),不遵守两段锁协议,25,例题,1,设,T,1,，,T,2,，,T,3,是如下的三个事务,T,1,：,A,：,=A+2,T,2,：,A,：,=A*2,T,3,：,A,：,=A,2,设,A,的初值为,0,：,若这三个事务允许并发执行，讨论他们可能实施的调度，请一一列举并求每种调度的结果,26,解：六种可能的调度,T,1,T,2,T,3,结果：,16,T,1,T,3,T,2,结果：,8,T,2,T,1,T,3,结果：,4,T,2,T,3,T,1,结果：,2,T,3,T,1,T,2,结果：,4,T,3,T,2,T,1,结果：,2,例题分析,27,例题,2,T,1,T,2,T,3,T,4,Write(y),Read(x),Read(y),Write(x),Write(x),Write(z),Read(z),Write(x),根据如图调度，判断其是冲突可串行化的吗？为什么？如果调度是冲突可串行化的，请给出与之等价的一个串行调度序列。,28,根据调度,S,得到串行图：,T,3,T,1,T,2,T,4,T,1,T,2,T,3,T,4,由于图中不存在环，故调度,S,是可串行化的，与之等,价的一个串行调度序列为：,29,例题,3,设有两个事务,T1,、,T2,，其并发操作如图所示，下面说法正确的是（）,A.,该操作不存在问题,B.,该操作丢失修改,C.,该操作不能重复读,D.,该操作读“脏”数据,T1,T2,读,A=10,A=A-5,写回,读,A=10,A=A-8,写回,
展开阅读全文