第8章数据库系统技术.ppt

* 不可串行化 read(A); T1 T2 T1 T2 B := B - 10 write(B); A := A - 50 write(A); read(B); B := B + 50 write(B); read(A); A := A - 50 write(A); read(B); B := B + 50 write(B); A=960￥ B=2040￥ A=950￥ B=2050￥ read(A); A := A + 10 write(A); read(B); B := B - 10 write(B); read(A); A := A + 10 write(A); read(B); A=1010￥ B=2000￥ A=950￥ B=2050￥ A=950￥ B=1990￥ A=1000, B=2000 * 调度可串行化的测试 前趋图 有向图G=V,E V—顶点的集合，包含所有参与调度的事务。 E—边的集合，通过分析冲突操作来决定。如果下列条件之一成立，可在E中加边Ti→Tj： Ri(x)在Wj(x)之前 Wi(x)在Rj(x)之前 Wi(x)在Wj(x)之前 S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 最后，看构造好的前趋图中是否有环路，如果有，则该调度不可串行化；否则，可串行化。 T1 T2 T3 T4 前趋图 * 可串行化时，决定等价串行调度序列的算法： 由于无环路，必有入度为0的顶点。将它们及其有关的边从图中移去并将这些顶点存入一个队列。 对剩下的图作同样处理，不过移出的顶点要队列中已有顶点之后。 重复1，2直至所有顶点移入队列为止。 例对{T1,T2,T3,T4}的一个调度s S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 它是否可串行化？如可串行化找出其等价的串行执行序列。 * S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) T1 T2 T3 T4 T2 T3 T4 队列:T1 T2 T4 队列:T1,T3 T4 队列:T1,T3,T2 等价串行序列：T1→T3→T2→T4 空 * 两段锁协议（续） 并行执行的所有事务均遵守两段锁协议，则对这些事务的所有并行调度策略都是可串行化的。 所有遵守两段锁协议的事务，其并行执行的结果一定是正确的。 事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。即可串行化的调度中，不一定所有事务都必须符合两段锁协议。 * 两段锁协议（续） T1 Slock B 读B=2 Y=B Xlock A ? ? A=Y+1 写回A=3 Unlock B Unlock A ? ? ? ? T2 ? ? ? ? Slock A 等待 等待 等待 等待 等待 Slock A 读A=3 Y=A Xlock B B=Y+1 写回B=4 Unlock B Unlock A? T1 Slock B 读B=2 Y=B Unlock B Xlock A ? ? A=Y+1 写回A=3 Unlock A ? ? ? ? ? ? ? ? ? T2 ? ? ? ? ? Slock A 等待 等待 等待 等待 Slock A 读A=3 X=A Unlock A Xlock B B=X+1 写回B=4 Unlock B? (a) 遵守两段锁协议 (b) 不遵守两段锁协议 T1 Slock B 读B=2 Y=B Unlock B Xlock A A=Y+1 写回A=3 Unlock A T2 ?? Slock A 读A=2 X=A Unlock A Xlock B 等待 Xlock B B=X+1 写回B=3 Unlock B? (c) 不遵守两段锁协议 * 两段锁协议（续） 两段锁协议与防止死锁的一次封锁法 一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁 * 两段锁协议（续） 图 遵守两段锁协议的事务发生死锁 T1 Slock B 读B=2 ? ? Xlock A 等待 等待 T2 ? ? Slock A 读A=2 ? Xlock B 等待 * 发现死锁 超时法 即一个事务在等待的时间超过了规定的时限后就认为发生了死锁。 这种方法非常不可靠，如果设置的等待时限长，则不能及时发现死锁；如果设置的等待时限短，则可能会将没有发生死锁的事务误判为死锁。 * 发现死锁 等待图法 即通过有向图判定事务是否是可串行化的，如果是则说明没有发生死锁，否则