问题 问答题 论述题

试证明,若并发事务遵守两段锁协议,则对这些事务的并发调度是可串行化的。

答案

参考答案:

证明:首先以两个并发事务Tl和T2为例,存在多个并发事务的情形可以类推。根据可串行化定义可知,事务不可串行化只可能发生在下列两种情况:

(l)事务Tl写某个数据对象A,T2读或写A;

(2)事务Tl读或写某个数据对象A,T2写A。

下面称A为潜在冲突对象。

设Tl和T2访问的潜在冲突的公共对象为{A1,A2…,An}。不失一般性,假设这组潜在冲突对象中X=(A1,A2,…,Ai}均符合情况1。Y={Ai+1,…,An}符合所情况(2)。

VX∈x,Tl需要XlockX①

T2需要Slockx或Xlockx②

1)如果操作①先执行,则Tl获得锁,T2等待

由于遵守两段锁协议,Tl在成功获得x和Y中全部对象及非潜在冲突对象的锁后,才会释放锁。

这时如果存在w∈x或Y,T2已获得w的锁,则出现死锁;否则,Tl在对x、Y中对象全部处理完毕后,T2才能执行。这相当于按Tl、T2的顺序串行执行,根据可串行化定义,Tl和几的调度是可串行化的。

2)操作②先执行的情况与(l)对称因此,若并发事务遵守两段锁协议,在不发生死锁的情况下,对这些事务的并发调度一定是可串行化的。证毕。

单项选择题
选择题