试证明,若并发事务遵守两段锁协议,则对这些事务的并发调度是可串行化的。
证明:首先以两个并发事务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)对称因此,若并发事务遵守两段锁协议,在不发生死锁的情况下,对这些事务的并发调度一定是可串行化的。证毕。
免费的网站请分享给朋友吧