《最新并发控制技术PPT课件》由会员分享，可在线阅读，更多相关《最新并发控制技术PPT课件（39页珍藏版）》请在金锄头文库上搜索。
1、并发控制技术并发控制技术单用户和多用户系统单用户和多用户系统4数据库系统一般可以分为单用户系统和数据库系统一般可以分为单用户系统和多用户系统。多用户系统。单用户系统单用户系统在任何时刻只允许一个用户使用的数据库系统。在任何时刻只允许一个用户使用的数据库系统。多用户系统多用户系统允许多个用户同时使用数据库的系统。允许多个用户同时使用数据库的系统。并发控制的必要性并发控制的必要性读读“脏脏”数据数据(Dirty Read) 是指事务是指事务T1修改某一数据，修改某一数据，并将其写回磁盘，事务并将其写回磁盘，事务T2读取同一数据后，读取同一数据后，T1由由于某种原因被撤销，这时于某种原因被撤销，这时
2、T1已修改过的数据恢复已修改过的数据恢复为原值，为原值，T2读到的数据就与数据库中的不一致，读到的数据就与数据库中的不一致，则则T2读到的数据就为读到的数据就为“脏脏”数据。数据。T1T2读读C=100C=C*2写回写回C读读C=200ROLLBACKC恢复为恢复为100并发控制并发控制4封锁的定义封锁的定义封锁就是事务封锁就是事务T在对某个数据对象如表、记在对某个数据对象如表、记录等操作之前，先向系统发出请求，对其加录等操作之前，先向系统发出请求，对其加锁，从而对该数据对象有了一定的控制，在锁，从而对该数据对象有了一定的控制，在事务事务T释放它的锁之前，其他事务不能更新释放它的锁之前，其他事
3、务不能更新此数据对象。此数据对象。封锁是并发控制的一个非常重要的技术。封锁是并发控制的一个非常重要的技术。并发控制并发控制4封锁的类型封锁的类型排它锁（X锁，锁，eXclusive lock）：事务）：事务T对对数据对象数据对象A加上加上X锁，则只允许锁，则只允许T读取和修读取和修改改A，其它事务对，其它事务对A的任何封锁请求都不能的任何封锁请求都不能成功（因而不能读取和修改成功（因而不能读取和修改R），直至），直至T释释放放A上的上的X锁。锁。共享锁（S锁，锁，Share lock）：事务）：事务T对数据对数据对象对象A加上加上S锁，则事务锁，则事务T可以读取但不能可以读取但不能修改修改A，
4、其它事务只能对，其它事务只能对A加加S锁（因而可锁（因而可以读取以读取A），而不能对），而不能对A的加的加X锁（因而不锁（因而不能修改能修改A），直到），直到T释放释放A上的上的S锁。锁。并发控制并发控制相容矩阵相容矩阵不相容请求不相容请求相容请求相容请求并发控制并发控制4一级封锁协议一级封锁协议事务事务T在修改数据在修改数据R之前必须对其加之前必须对其加X锁，直锁，直到事务结束才释放。事务结束包括正常结束到事务结束才释放。事务结束包括正常结束(COMMIT)和非正常结束和非正常结束(ROLLBACK)。一级封锁协议可以防止丢失修改，并保证事一级封锁协议可以防止丢失修改，并保证事务务T是可恢复
5、的。在一级封锁协议中，如果是可恢复的。在一级封锁协议中，如果仅仅是读数据而不对其进行修改，是不需要仅仅是读数据而不对其进行修改，是不需要对其加锁的，因此它不能保证可重复读和不对其加锁的，因此它不能保证可重复读和不读读“脏脏”数据。数据。并发控制并发控制T1T2XLOCK A获得获得读读A=16XLOCK AA=A-1写回写回A=15COMMITUNLOCK A等待等待等待等待等待等待等待等待获得获得XLOCK A读读A=15A=A-1写回写回A=14COMMITUNLOCK A没有丢失修改并发控制并发控制4二级锁协议二级锁协议二级锁协议是：一级锁协议加上事务二级锁协议是：一级锁协议加上事务T在
6、读在读取数据取数据R之前必须先对其加之前必须先对其加S锁，读完后即锁，读完后即可释放可释放S锁。二级锁除了防止丢失修改，还锁。二级锁除了防止丢失修改，还可以进一步防止读可以进一步防止读“脏脏”数据。但由于读完后数据。但由于读完后即可释放即可释放S锁，所以不能保证可重复读。锁，所以不能保证可重复读。并发控制并发控制T1T2XLOCK C获得获得读读C=100C=C*2写回写回C200SLOCK CROLLBACKC恢复为恢复为100UNLOCK C等待等待等待等待等待等待获得获得SLOCK C读读C=100COMMITUNLOCK C不读脏数据并发控制并发控制4三级锁协议三级锁协议三级锁协议是：
7、一级锁协议加上事务三级锁协议是：一级锁协议加上事务T在读在读取取R之前必须对其加之前必须对其加S锁，直到事务结束才锁，直到事务结束才释放。三级封锁协议除了防止丢失修改和读释放。三级封锁协议除了防止丢失修改和读“脏脏”数据以外，还进一步防止了不可重复读。数据以外，还进一步防止了不可重复读。并发控制并发控制T1T2SLOCK A获得获得SLOCK B获得获得读读A=50读读B=100求和求和150XLOCK B读读A50读读B100求和求和=150COMMITUNLOCK AUNLOCK B等待等待等待等待等待等待等待等待等待等待等待等待T1T2等待等待等待等待等待等待等待等待获得获得XLOCK
8、B读读B100B=B*2 写回写回B =200COMMITUNLOCK B可重复读并发控制并发控制X锁锁S锁锁一致性保证一致性保证操作操作结束结束释放释放事务事务结束结束释放释放操作操作结束结束释放释放事务事务结束结束释放释放不丢不丢失修失修改改不读不读“脏脏”数数据据可重可重复读复读一级封锁一级封锁协议协议 二级封锁二级封锁协议协议 三级封锁三级封锁协议协议 并发控制并发控制T1T2T3T4SLOCK RXLOCK R等待等待SLOCK RUNLOCK R等待等待操作操作SLOCK R等待等待操作操作操作操作等待等待等待等待UNLOCK R操作操作等待等待操作操作活锁并发控制并发控制4死锁死
9、锁(Deadlock)定义定义在数据库运行期间，如果存在一个事务集合在数据库运行期间，如果存在一个事务集合 =T0，T1，Tn，使得，使得T0等待等待T1持有的数持有的数据项锁，据项锁， ， Tn-1等待等待Tn持有的数据项锁，持有的数据项锁， Tn等待等待T1持有的数据项锁，则称系统处于死持有的数据项锁，则称系统处于死锁状态，锁状态， 称为死锁事务集合。称为死锁事务集合。并发控制并发控制4死锁的例子死锁的例子如果事务如果事务T1封锁了数据封锁了数据R1，T2封锁了数据封锁了数据R2，然后，然后T1又请求封锁又请求封锁R2，因，因T2已封锁了已封锁了R2，于是于是T1等待等待T2释放释放R2上
10、的锁。接着，上的锁。接着，T2又申又申请封锁请封锁R1，因，因T1已经封锁了已经封锁了R1，T2也只能等也只能等待待T1释放释放R1上的锁。这样就出现了上的锁。这样就出现了T1在等待在等待T2，而，而T2又在等待又在等待T1的局面，的局面，T1和和T2两个事两个事务永远不能结束，形成死锁。务永远不能结束，形成死锁。并发控制并发控制4解决死锁的方法解决死锁的方法预防死锁预防死锁死锁检测和恢复死锁检测和恢复并发控制并发控制4预防死锁预防死锁一次封锁法一次封锁法一次封锁法要求每个事务必须一次将其所有要使用的数据一次封锁法要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行。一次加锁法可以
11、有效地防止全部加锁，否则就不能执行。一次加锁法可以有效地防止死锁的发生，但由于需要扩大加锁的范围，因此降低了系死锁的发生，但由于需要扩大加锁的范围，因此降低了系统的并发度。统的并发度。顺序封锁法顺序封锁法顺序封锁法是预先对数据对象规定一个封锁顺序，所有的顺序封锁法是预先对数据对象规定一个封锁顺序，所有的事务都要按照这个顺序实行封锁。顺序封锁法可以有效地事务都要按照这个顺序实行封锁。顺序封锁法可以有效地防止死锁，但其实施由于数据库中数据的不断变化和事务防止死锁，但其实施由于数据库中数据的不断变化和事务封锁要求的动态提出而难度很大。封锁要求的动态提出而难度很大。并发控制并发控制4死锁检测死锁检测超
12、时法超时法如果一个事务的等待时间超过了规定的期限，就如果一个事务的等待时间超过了规定的期限，就认为发生了死锁。认为发生了死锁。等待图法等待图法事务等待图是一个有向回路事务等待图是一个有向回路G=(T, U)。T为结点为结点的集合，每个结点表示正在运行的事务；的集合，每个结点表示正在运行的事务；U为边为边的集合，每条边表示事务等待的情况。若的集合，每条边表示事务等待的情况。若T1等等待待T2，则，则T1，T2之间画一条有向边，从之间画一条有向边，从T1指向指向T2。事务等待图动态地反映了所有事务的等待。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性的检测事务等待图，情况。并发控制
13、子系统周期性的检测事务等待图，如果发现图中存在回路，则表示系统出现死锁。如果发现图中存在回路，则表示系统出现死锁。并发控制并发控制T2T1T3事务号事务号占有资源号占有资源号请求资源号请求资源号T1R1R2T2R2R3T3R3R1并发控制并发控制4死锁恢复死锁恢复DBMS的并发控制子系统一旦检测到系统中的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。对于所撤销的事务
14、所务得以继续运行下去。对于所撤销的事务所作的操作必须加以恢复。作的操作必须加以恢复。事务的调度与可串行性事务的调度与可串行性串行调度串行调度在串行调度中，属于同一事务的指令紧挨在一起。在串行调度中，属于同一事务的指令紧挨在一起。对于有对于有n个事务的事务组，可以有个事务的事务组，可以有n！个有效调度。！个有效调度。并行调度并行调度在并行调度中，来自不同事务的指令可以交叉执在并行调度中，来自不同事务的指令可以交叉执行。行。事务的调度与可串行性事务的调度与可串行性4问题：计算机系统对并发事务中并发操作问题：计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能产生的调度是随机的，而不同的调
15、度可能产生不同的结果，那么哪个结果是正确的呢？不同的结果，那么哪个结果是正确的呢？4定义：多个事务的并发执行是正确的，当定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行的执行它且仅当其结果与按某一次序串行的执行它们时的结果相同，我们称这种调度策略为们时的结果相同，我们称这种调度策略为可串行化调度。一个给定的并发调度，当可串行化调度。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调且仅当它是可串行化的，才认为是正确调度。度。并发控制并发控制4两段锁协议两段锁协议(Two-phase Locking)内容内容在对任何数据进行读、写操作之前，事务首在对任何数据进行读、写操作
16、之前，事务首先要获得对该数据的封锁。先要获得对该数据的封锁。在释放一个封锁之后，事务不再获得任何其在释放一个封锁之后，事务不再获得任何其它封锁。它封锁。并发控制并发控制所谓两阶段锁协议的含义是指所有事务必须所谓两阶段锁协议的含义是指所有事务必须分两个阶段对数据项加锁和解锁。第一阶段分两个阶段对数据项加锁和解锁。第一阶段是获得封锁也称扩展阶段。在这一阶段，事是获得封锁也称扩展阶段。在这一阶段，事务可以申请获得任何数据项上的任何类型的务可以申请获得任何数据项上的任何类型的封锁，但不能释放任何锁。第二阶段是释放封锁，但不能释放任何锁。第二阶段是释放阶段，也称收缩阶段。在这阶段，事务可以阶段，也称收缩
17、阶段。在这阶段，事务可以释放任何数据项上的任何类型的封锁，但是释放任何数据项上的任何类型的封锁，但是不能够再申请任何锁。不能够再申请任何锁。定理：若所有事务均遵从两段锁协议，则这定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。些事务的所有并行调度都是可串行化的。并发控制并发控制T1T2SLOCK B得到得到读读B= 2Y=BXLOCK ASLOCK A等待等待A=Y+1写回写回A=3UNLOCK BUNLOCK A等待等待等待等待等待等待等待等待T1T2SLOCK A得到得到读读A=3Y=AXLOCK B得到得到B=Y+1写回写回B=4UNLOCK BUNLOCK A
18、并发控制并发控制4封锁粒度封锁粒度 封锁对象的大小称为封锁粒度封锁对象的大小称为封锁粒度封锁对象：包括逻辑单元，如封锁对象：包括逻辑单元，如:属性值、属性值集合、属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库；和元组、关系、某索引项、整个索引、整个数据库；和物理单元如：物理页、块。物理单元如：物理页、块。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度小，则并发度高，封锁机构复杂，开销高。封锁粒度小，则并发度高，封锁机构复杂，开销高。如果在一个系统中同时支持多种封锁粒度供不同的事如果在一个系统中同时支持多种封锁粒度供不同的事务
19、选择是比较理想的，这种封锁方法称为多粒度封锁务选择是比较理想的，这种封锁方法称为多粒度封锁（Multiple Granularity Locking）。选择封锁粒度时）。选择封锁粒度时应同时考虑封锁开销和并发度两个因素，适当选择封应同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以达到最优效果。锁粒度以达到最优效果。并发控制并发控制4多粒度树多粒度树多粒度树的根结点是整个数据库，表示最大多粒度树的根结点是整个数据库，表示最大的粒度。叶结点表示最小的粒度。的粒度。叶结点表示最小的粒度。数据库关系Rn关系R1元组元组元组元组并发控制并发控制4多粒度封锁协议多粒度封锁协议多粒度封锁协议允许多粒度树
20、中的每个结点多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以因此，在多粒度封锁中一个数据对象可能以两种方式封锁，即：两种方式封锁，即：显式封锁是应事务的要求直接加到数据对象上的显式封锁是应事务的要求直接加到数据对象上的封锁。封锁。隐式封锁是该数据对象没有独立加锁，是由于其隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。上级结点加锁而使该数据对象加上了锁。并发控制并发控制4意向锁意向锁
21、一般的，对某个数据对象加锁，系统要检查该数据一般的，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁冲突；还要检查其所有下级结点，看上的隐式封锁冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突。效率面的显式封锁是否与本事务的隐式封锁冲突。效率很低，因此引入了意向锁。很低，因此引入了意向锁。意向锁的含义是如果对一个结点加意向锁，则说明意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加
22、锁；对任一结点加锁时，该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。必须先对它的上层结点加意向锁。并发控制并发控制4三种常用的意向锁三种常用的意向锁意向共享锁（意向共享锁（Intent Share Lock，简称，简称IS锁）锁）如果要对一个数据对象加如果要对一个数据对象加IS锁，表示它的后裔结点拟（意锁，表示它的后裔结点拟（意向）加向）加S锁。锁。意向排它锁（意向排它锁（Intent Exclusive Lock ，简称，简称IX锁）锁）如果要对一个数据对象加如果要对一个数据对象加IX锁，表示它的后裔结点拟（意锁，表示它的后裔结点拟（意向）加向）加X锁。锁。意向共享排它锁（意向共享排它锁（ Share Intent Exclusive Lock ，简称简称SIX锁）锁）如果要对一个数据对象加如果要对一个数据对象加SIX锁，表示对它加锁，表示对它加S锁，再加锁，再加IX锁，即锁，即SIX=S+IX。并发控制并发控制T1 T2SXISIXSIXSYNYNNYXNNNNNYISYNYYYYIXNNYYNYSIXNNYNNYYYYYYY结束语结束语谢谢大家聆听！谢谢大家聆听！39
