Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2018712
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类: 服务器与存储

2011-01-11 16:50:52

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

个人对两阶段锁保证可串行化的理解:
首先说明一些使用到的定义,在一次调度中:
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产生的输出是一个无环图,即可串行化


阅读(6688) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~