资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章并发控制技术,第八章并发控制技术,1,并发控制,为什么要并发执行事务？,为什么要进行并发控制？,如何进行并发控制？,如何解决并发控制可能带来的问题？,如何保证并发控制的灵活性和效率？,并发控制为什么要并发执行事务？,2,为什么要并发执行事务（一）,串行执行方式,T2,T1,Time,Read B (10),Read A (16),B = B- 1,(9),A = A-1,(15),Write B,Write A,为什么要并发执行事务（一）串行执行方式T2T1TimeRea,3,为什么要并发执行事务（二）,并发执行方式,T2,T1,Time,Read B (10),Read A (16),B = B- 1,(9),A = A-1,(15),Write B,Write A,为什么要并发执行事务（二）并发执行方式T2T1TimeRea,4,为什么要并发执行事务（三）,并发执行的优点,一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的,吞吐量,，,改善系统的资源的,利用率,。,系统中存在着周期不等的各种事务，串行会导致难以预测的时延。采用并发会减少,平均响应时间,，,特别是改善短事务的响应时间。,为什么要并发执行事务（三）并发执行的优点,5,并发执行的问题：丢失修改,两个事务T,1,和T,2,读入同一数据并修改， T,2,提交的结果破坏了T,1,提交的结果，导致T,1,的修改被丢失。,T2,T1,Time,C=200,Read C (200),Read C (200),C=C-100,(100,),C = C-100,(100),Write C,C=100,C = 100,Write C,C=100,并发执行的问题：丢失修改两个事务T1和T2读入同一数据并修改,6,并发执行的问题：不可重复读,事务T,1,读取某一数据后，事务T,2,对其做了修改，当事务T,1,再次读取该数据时，得到与前一次不同的值。,T2,T1,Time,D=1,Read D(1),Read D (1),Read D,(0),Write D,D=0,D=D-1(0),并发执行的问题：不可重复读事务T1读取某一数据后，事务T2对,7,并发执行的问题：不可重复读之幻影行,事务T1按照一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按照相同条件读取数据时，发现某些记录神秘的消失了。,T1,T2,Time,Select count (*) From SC,Where Cno = C1,返回2行,Delete,S1,C1,80,S2,C1,70,S1,C1,80,S2,C1,70,Select count (*) From SCWhere Cno=C1,返回1行,并发执行的问题：不可重复读之幻影行事务T1按照一定条件从数,8,并发执行的问题：不可重复读之幻影行,事务T1按照一定条件从数据库中读取了某些数据记录后，事务T2插入了一些记录，当T1再次按照相同条件读取数据时，发现多了一些记录。,T1,T2,Time,Select count (*) From SCWhere Cno = C1,返回2行,Insert,S3,C1,60,S1,C1,80,S2,C1,70,S3,C1,60,S1,C1,80,S2,C1,70,Select count (*) From SCWhere Cno = C1,返回3行,并发执行的问题：不可重复读之幻影行事务T1按照一定条件从数,9,并发执行的问题：读“脏”数据,读“脏”数据(Dirty Read) 是指事务T,1,修改某一数据，并将其写回磁盘，事务T,2,读取同一数据后，T,1,由于某种原因被撤销，这时T,1,已修改过的数据恢复为原值，T,2,读到的数据就与数据库中的不一致，则T,2,读到的数据就为“脏”数据。,T2,T1,Time,C=0,Read C (10000),Read C (0),C=C+10000,(10000),C=10000,Write C,C=0,Rollback,可能执行,错误的操作,并发执行的问题：读“脏”数据读“脏”数据(Dirty Rea,10,并发控制的必要性,需要进行并发控制的原因：,如果不进行并发控制，当多个事务并发执行的时候，有可能会相互影响，从而读取或者存储不正确的数据，破坏数据库的一致性。,并发控制的必要性需要进行并发控制的原因：,11,并发控制（一）,并发执行事务情况分析：,T1:读或写数据项A, T2:读或写数据项B,T1:读数据项A, T2:读数据项A,T1:写数据项A, T2:写数据项A,T1:读数据项A, T2:写数据项A,T1:写数据项A, T2:读数据项A,总结，造成并发执行事务问题的原因是：,多个事务同时存取同一个数据集合，,并且其中至少有一个事务对该数据集合进行了更新操作,没有问题,没有问题,丢失修改,不可重复读,读“脏”数据,并发控制（一）并发执行事务情况分析：没有问题没有问题丢,12,并发控制（二）,解决问题的思路,避免不同事务同时对同一数据进行可能导致数据不一致的操作。,采用的技术封锁（Locking）,封锁就是事务T在对某个数据对象如表、记录等操作之前，先向系统发出请求，对其加锁，从而对该数据对象有了一定的控制，在事务T释放它的锁之前，其他事务不能更新此数据对象。,并发控制（二）解决问题的思路,13,并发控制（三）,封锁的类型,排它锁,（X锁，eXclusive lock）：事务T对数据对象A加上X锁，则只允许T读取和修改A，其它事务对A的任何封锁请求都不能成功（因而不能读取和修改R），直至T释放A上的X锁。,共享锁,（S锁，Share lock）：事务T对数据对象A加上S锁，则事务T可以读取但不能修改A，其它事务只能对A加S锁（因而可以读取A），而不能对A的加X锁（因而不能修改A），直到T释放A上的S锁。,并发控制（三）封锁的类型,14,并发控制（四）,相容矩阵,不相容请求,相容请求,并发控制（四）相容矩阵不相容请求相容请求,15,并发控制（五）,一级封锁协议,事务T在修改数据R之前必须对其加X锁，直到事务结束才释放。事务结束包括正常结束(COMMIT)和非正常结束(ROLLBACK)。,一级封锁协议可以防止丢失修改，并保证事务T是可恢复的。在一级封锁协议中，如果仅仅是读数据而不对其进行修改，是不需要对其加锁的，因此它不能保证可重复读和不读“脏”数据。,并发控制（五）一级封锁协议,16,并发控制（六）,T,1,T,2,XLOCK C成功,读C=200,XLOCK C,C=C-100,写回C=100,COMMIT,UNLOCK C,等待,等待,等待,等待,XLOCK C成功,读C=100,C=C-100,写回C=0,COMMIT,UNLOCK C,可以避免丢失修改,并发控制（六）T1T2XLOCK C成功读C=200XLOC,17,并发控制（七）,T,1,T,2,读D=1,XLOCK D成功,读D1,D=D-1,写回D0,COMMIT,UNLOCK D,读D0,COMMIT,不能避免不可重复读,并发控制（七）T1T2读D=1XLOCK D成功读D0不能,18,并发控制（八）,T,1,T,2,XLOCK C成功,读C=0,C=C+10000,写回C,读C=10000,ROLLBACK,C恢复为0,UNLOCK C,不能避免读脏数据,并发控制（八）T1T2XLOCK C成功读C=10000RO,19,并发控制（九）,二级锁协议,二级锁协议是：一级锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。,二级锁除了防止丢失修改，还可以进一步防止读“脏”数据。但由于读完后即可释放S锁，所以不能保证可重复读。,并发控制（九）二级锁协议,20,并发控制（十）,T,1,T,2,XLOCK C成功,读C=0,C=C10000,写回C10000,SLOCK C,ROLLBACK,C恢复为0,UNLOCK C,等待,等待,等待,SLOCK C成功,读C=0,COMMIT,UNLOCK C,不读脏数据,并发控制（十）T1T2XLOCK C成功SLOCK CROL,21,并发控制（十一）,T,1,T,2,SLOCK D成功,读D=1,UNLOCK D,XLOCK D成功,读D1,D = D-1,写回D0,COMMIT,UNLOCK D,SLOCK D成功,读D = 0,COMMIT,UNLOCK D,不能避免不可重复读,并发控制（十一）T1T2SLOCK D成功XLOCK D成功,22,并发控制（十二）,三级锁协议,三级锁协议是：一级锁协议加上事务T在读取R之前必须对其加S锁，直到事务结束才释放。三级封锁协议除了防止丢失修改和读“脏”数据以外，还进一步防止了不可重复读。,并发控制（十二）三级锁协议,23,并发控制（十三）,T,1,T,2,SLOCK D获得,读D=1,XLOCK D,读D=1,COMMIT,UNLOCK D,等待,等待,等待,获得XLOCK D,读D1,D=D-1,写回D=0,COMMIT,UNLOCK D,可重复读,并发控制（十三）T1T2SLOCK D获得XLOCK D读D,24,并发控制（十四）,X锁,S锁,一致性保证,操作结束释放,事务结束释放,操作结束释放,事务结束释放,不丢失修改,不读“脏”数据,可重复读,一级封锁协议,二级封锁协议,三级封锁协议,并发控制（十四）X锁S锁一致性保证操作结束释放事务结束释放操,25,并发控制（十五）,问题：,是否使用的锁协议级别越高越好呢？,SQL-92标准中的隔离级别,Read Uncommitted（一级锁协议）,Read Committed（二级锁协议）,Repeatable Read（三级锁协议）,Serializable,SQL Server中设置隔离级别的方法,SET TRANSACTION ISOLATION LEVEL ,并发控制（十五）问题：,26,死锁与活锁（一）,T1,T2,T3,T4,SLOCK R,XLOCK R,等待,SLOCK R,UNLOCK R,等待,操作,SLOCK R,等待,操作,操作,等待,等待,UNLOCK R,操作,等待,操作,活锁,死锁与活锁（一）T1T2T3T4SLOCK RXLOCK,27,死锁与活锁（二）,死锁(Deadlock),定义,在数据库运行期间，如果存在一个事务集合,=T,0,，T,1,，,，T,n,，使得T,0,等待,T,1,持有的数据项锁，,，,T,n-1,等待,T,n,持有的数据项锁，,T,n,等待,T,0,持有的数据项锁，则称系统处于死锁状态，,称为死锁事务集合。,死锁与活锁（二）死锁(Deadlock),28,死锁与活锁（三）,T,1,T,2,LOCK R1成功,对R1进行操作,LOCK R2成功,对R2进行操作,LOCK R2,等待,LOCK R1,等待,死锁,死锁与活锁（三）T1T2LOCK R1成功LOCK R2成功,29,死锁与活锁（四）,解决死锁的方法,预防死锁,死锁检测和恢复,死锁与活锁（四）解决死锁的方法,30,死锁与活锁（五）,预防死锁,一次封锁法,一次封锁法要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行。,一次加锁法可以有效地防止死锁的发生，但由于需要扩大加锁的范围，因此降低了系统的并发度。,顺序封锁法,顺序封锁法是预先对数据对象规定一个封锁顺序，所有的事务都要按照这个顺序实行封锁。,顺序封锁法可以有效地防止死锁，但其实施由于数据库中数据的不断变化和事务封锁要求的动态提出而难度很大。,死锁与活锁（五）预防死锁,31,死锁与活锁（六）一次封锁法,T,1,T,2,LOCK R1，R2成功,对R1，R2进行操作,LOCK R1,R2,COMMIT,UNLOCK R1, R2,等待,等待,等待,LOCK R1,R2,对R1,R2进行操作,COMMIT,UNLOCK R1, R2,死锁与活锁（六）一次封锁法T1T2LOCK R1，R2成功,32,死锁与活锁（七）顺序封锁法,T,1,T,2,LOCK R1成功,对R1进行操作,LOCK R1,LOCK R2成功,对R2进行操作,COMMIT,UNLOCK R1,R2,等待,等待,等待,等待,等待,LOCK R1成功,对R1进行操作,LOCK R2成功,对R2进行操作,COMMIT,UNLOCK R1，R2,死锁与活锁（七）顺序封锁法T1T2LOCK R1成功LOC,33,死锁与活锁（六）,死锁检测,超时法,如果一个事务的等待时间超过了规定的期限，就认为发生了死锁。,等待图法,事务等待图是一个有向回路G=(T, U)。T为结点的集合，每个结点表示正在运行的事务；U为边的集合，每条边表示事务等待的情况。若T1等待T2，则T1，T2之间画一条有向边，从T1指向T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性的检测事务等待图，如果发现图中存在回路，则表示系统出现死锁。,死锁与活锁（六）死锁检测,34,死锁与活锁（七）,T2,T1,T3,事务号,占有资源号,请求资源号,T1,R1,R2,T2,R2,R3,T3,R3,R1,死锁与活锁（七）T2T1T3事务号占有资源号请求资源号T1R,35,死锁与活锁（八）,死锁恢复,DBMS的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。对于所撤销的事务所作的操作必须加以恢复。,死锁与活锁（八）死锁恢复,36,事务的调度与可串行性,串行调度,在串行调度中，属于同一事务的指令紧挨在一起。,对于有n个事务的事务组，可以有n！个有效调度。,并行调度,在并行调度中，来自不同事务的指令可以交叉执行。,事务的调度与可串行性串行调度,37,可串行性调度（一）,问题：计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能产生不同的结果，那么哪个结果是正确的呢？,定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行的执行它们时的结果相同，我们称这种调度策略为可串行化调度。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。,可串行性调度（一）问题：计算机系统对并发事务中并发操作的调度,38,可串行性调度（二）,T,1,T,2,SLOCK B成功,Y=B= 2,UNLOCK B,XLOCK A,A=Y+1,写回A(=3),UNLOCK A,SLOCK A,X=A=3,UNLOCK A,XLOCK B,B=X+1,写回B(=4),UNLOCK B,T,1,T,2,SLOCK A,X=A=2,UNLOCK A,XLOCK B,B=X+1,写回B(=3),UNLOCK B,SLOCK B成功,Y=B=3,UNLOCK B,XLOCK A,A=Y+1,写回A(=4),UNLOCK A,可串行性调度（二）T1T2SLOCK B成功SLOCK AT,39,可串行性调度（三）,T,1,T,2,SLOCK B,Y=B=2,SLOCK A,X=A=2,UNLOCK B,UNLOCK A,XLOCK A,A=Y+1,写回A(=3),XLOCK B,B=X+1,写回B(=3),UNLOCK A,UNLOCK B,T,1,T,2,SLOCK B成功,Y=B=2,UNLOCK B,XLOCK A,SLOCK A,A=Y+1,写回A(=3),UNLOCK A,等待,等待,等待,X=A=3,UNLOCK A,XLOCK B,B=X+1,写回B(=4),UNLOCK B,可串行性调度（三）T1T2SLOCK BSLOCK AUNL,40,可串行性调度（四）,两段锁协议(Two-phase Locking),在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。,在释放一个封锁之后，事务不再获得任何其它封锁。,可串行性调度（四）两段锁协议(Two-phase Locki,41,可串行性调度（五）,所谓两阶段锁协议的含义是指所有事务必须分两个阶段对数据项加锁和解锁。第一阶段是获得封锁也称扩展阶段。在这一阶段，事务可以申请获得任何数据项上的任何类型的封锁，但不能释放任何锁。第二阶段是释放阶段，也称收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的封锁，但是不能够再申请任何锁。,定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。,可串行性调度（五）所谓两阶段锁协议的含义是指所有事务必须分两,42,可串行性调度（六）,T,1,T,2,SLOCK B成功,读B= 2,Y=B,XLOCK A,SLOCK A,等待,A=Y+1,写回A=3,UNLOCK B,UNLOCK A,等待,等待,等待,等待,T,1,T,2,SLOCK A成功,读A=3,Y=A,XLOCK B成功,B=Y+1,写回B=4,UNLOCK B,UNLOCK A,可串行性调度（六）T1T2SLOCK B成功SLOCK A等,43,可串行性调度（七）,T,1,T,2,SLOCK B成功,读B= 2,Y=B,ULOCK B,XLOCK A,SLOCK A,等待,A=Y+1,写回A=3,UNLOCK A,等待,等待,等待,等待,T,1,T,2,SLOCK A成功,读A=3,Y=A,UNLOCK A,XLOCK B成功,B=Y+1,写回B=4,UNLOCK B,可串行性调度（七）T1T2SLOCK B成功SLOCK A等,44,可串行性调度（八）,两阶段锁协议与死锁,T,1,T,2,SLOCK B成功,读B=2,SLOCK A成功,读A=2,XLOCK A,等待,等待,XLOCK B,等待,可串行性调度（八）两阶段锁协议与死锁T1T2SLOCK B成,45,多粒度封锁（一）,封锁粒度 封锁对象的大小称为封锁粒度,封锁对象：包括逻辑单元，如:属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库；和物理单元如：物理页、块。,封锁粒度大，则并发度低，封锁机构简单，开销小。,封锁粒度小，则并发度高，封锁机构复杂，开销高。,如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁（Multiple Granularity Locking）。选择封锁粒度时应同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以达到最优效果。,多粒度封锁（一）封锁粒度 封锁对象的大小称为封锁粒度,46,多粒度封锁（二）,多粒度树,多粒度树的根结点是整个数据库，表示最大的粒度。叶结点表示最小的粒度。,数据库,关系R,n,关系R,1,元组,元组,元组,元组,多粒度封锁（二）多粒度树数据库关系Rn关系R1元组元组,47,多粒度封锁（三）,多粒度封锁协议,多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两种方式封锁，即：,显式封锁是应事务的要求直接加到数据对象上的封锁。,隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。,多粒度封锁（三）多粒度封锁协议,48,多粒度封锁（四）,意向锁,一般的，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突。效率很低，因此引入了意向锁。,意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。,多粒度封锁（四）意向锁,49,多粒度封锁（五）,三种常用的意向锁,意向共享锁（Intent Share Lock，简称IS锁）,如果要对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。,意向排它锁（Intent Exclusive Lock ，简称IX锁）,如果要对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。,意向共享排它锁（ Share Intent Exclusive Lock ，简称SIX锁）,如果要对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX。,多粒度封锁（五）三种常用的意向锁,50,多粒度封锁（六）,T,1,T,2,S,X,IS,IX,SIX,S,Y,N,Y,N,N,Y,X,N,N,N,N,N,Y,IS,Y,N,Y,Y,Y,Y,IX,N,N,Y,Y,N,Y,SIX,N,N,Y,N,N,Y,Y,Y,Y,Y,Y,Y,多粒度封锁（六）T1 T2SXISIXSIXSYNYNN,51,
展开阅读全文