两阶段锁(2PL)可串行性证明

来自《信息事务系统》并发控制与恢复的理论、算法与实践一书的描述

个人对两阶段锁保证可串行化的理解：

首先说明一些使用到的定义，在一次调度中：

1.冲突：设两个事务t1和t2，p1是事务t1中的一个操作，q2是事务t2中的一个操作，如果p1和q2共同访问一个数据，并且p1、q2中有一个是写操作，则称p1、q2是冲突的。

2.将事务作为点，冲突作为边，构造一个有向图，称为冲突图。根据某可串行化定理的证明：如果冲突图中不存在环，那么这个调度是可串行化的。对1中的描述，如果在调度中p1出现在q2的前面，则在冲突图中有一条从t1指向t2的边。

例如，如下的调度：

s = r1(x) r2(x) w1(x) r3(x) w3(x) w2(y) c3 c2 w1(y) c1

其中，r/w表示读/写操作，后面的数字表示该操作属于哪个事务，括号中的操作的数据，c表示事务提交(例如r1(x)表示事务1对x进行读操作)

对于这个调度，用冲突图来表示就是具有以下边的图：

t2->t1 因为r2(x)与w1(x)冲突，且r2(x)先出现

t2->t3 因为r2(x)与w3(x)冲突，且r2(x)先出现

t1->t3 因为r1(x)和w3(x)冲突，且r1(x)先出现

对2PL协议保证可串行性的证明：

1.首先，2PL保证在每个事务内，所有加锁操作都在解锁操作之前(即将加锁和解锁严格的区分为两个阶段)。

2.对冲突图中的t1指向t2的边(t1->t2)，假设它们的冲突操作为如上所描述的p1、q2，那么当t2对数据x上锁时，t1必须已经释放了对x的锁，为了方便描述，将这种关系表示为p1

3.假设冲突图G上存在一条路径t1->t2->t3->t4，则依据2中的描述，对数据x的上锁操作必然满足这种关系：p1

4.假设G是有环的，比如存在t1->t2->t3->t4->t1的环，那么必然有p1

对于4，其实可以这样描述：p1操作其实包含了三个步骤，加锁lock(x)、读写数据rw(x)、解锁realese(x)。那么p1

所以,2PL产生的输出是一个无环图，即可串行化