并发控制技术

《并发控制技术》由会员分享，可在线阅读，更多相关《并发控制技术（38页珍藏版）》请在装配图网上搜索。

1、第八章第八章并发控制技术并发控制技术单用户和多用户系统单用户和多用户系统4数据库系统一般可以分为单用户系统和数据库系统一般可以分为单用户系统和多用户系统。多用户系统。单用户系统单用户系统 在任何时刻只允许一个用户使用的数据库系统。在任何时刻只允许一个用户使用的数据库系统。多用户系统多用户系统 允许多个用户同时使用数据库的系统。允许多个用户同时使用数据库的系统。事务的并发执行事务的并发执行4并行并行 Vs 串行串行 基本比较基本比较 并行事务会破坏数据库的一致性。并行事务会破坏数据库的一致性。串行事务效率低。串行事务效率低。并行的优点并行的优点 一个事务由不同的步骤组成，所涉及的系统资源也不同。

2、一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的这些步骤可以并发执行，以提高系统的吞吐量。系统中存在着周期不等的各种事务，串行会导致难于预测系统中存在着周期不等的各种事务，串行会导致难于预测的时延。如果各个事务所涉及的是数据库的不同部分，采的时延。如果各个事务所涉及的是数据库的不同部分，采用并发会减少用并发会减少平均响应时间。并发控制的必要性并发控制的必要性4对数据库的并发操作可能导致下列问题：对数据库的并发操作可能导致下列问题：丢失修改丢失修改(Lost Update)两个事务两个事务T1和和T2读入同一数据并修改，读入同一数据并修改，T2提交的结果破提交

3、的结果破坏了坏了T1提交的结果，导致提交的结果，导致T1的修改被丢失。的修改被丢失。T1读读A=16A=A-1写回写回A=15T2读读A=16A=A-1写回写回A=15并发控制的必要性并发控制的必要性 不可重复读不可重复读(Non-Repeatable Read)指事务指事务T1读读取数据后，事务取数据后，事务T2执行更新操作，使执行更新操作，使T1无法再现无法再现前一次读取的结果。具体的讲，不可重复读包括前一次读取的结果。具体的讲，不可重复读包括三种情况：三种情况：事务事务T1读取某一数据后，事务读取某一数据后，事务T2对其作了修改，当事务对其作了修改，当事务T1再次读取该数据时，得到与前一

4、次不同的值。再次读取该数据时，得到与前一次不同的值。事务事务T1按照一定条件从数据库中读取了某些数据记录后，按照一定条件从数据库中读取了某些数据记录后，事务事务T2删除了其中部分记录，当删除了其中部分记录，当T1再次按照相同条件读再次按照相同条件读取数据时，发现某些记录神秘的消失了。取数据时，发现某些记录神秘的消失了。事务事务T1按照一定条件从数据库中读取了某些数据记录后，按照一定条件从数据库中读取了某些数据记录后，事务事务T2插入了一些记录，当插入了一些记录，当T1再次按照相同条件读取数再次按照相同条件读取数据时，发现多了一些记录。据时，发现多了一些记录。后两种不可重复读有时也称作幻影（后两

5、种不可重复读有时也称作幻影（Phantom Row）现）现象。象。并发控制的必要性并发控制的必要性T1读读A=50读读B100求和求和=150读读A50读读B200求和求和250T2读读B100B=B*2写回写回B200并发控制的必要性并发控制的必要性T1select*from SCwhere CNO=C01 and SNO=S01select*from SCwhere CNO=C01 and SNO=S01T2Delete From SCWhere CNO=C01 and SNO=S01并发控制的必要性并发控制的必要性T1select*from SCwhere CNO=C01 and SNO

6、=S01select*from SCwhere CNO=C01 and SNO=S01T2insert into SC values(S01,C01,null)并发控制的必要性并发控制的必要性 读读“脏脏”数据数据(Dirty Read)是指事务是指事务T1修改某一数修改某一数据，并将其写回磁盘，事务据，并将其写回磁盘，事务T2读取同一数据后，读取同一数据后，T1由于某种原因被撤销，这时由于某种原因被撤销，这时T1已修改过的数据已修改过的数据恢复为原值，恢复为原值，T2读到的数据就与数据库中的不一读到的数据就与数据库中的不一致，则致，则T2读到的数据就为读到的数据就为“脏脏”数据。数据。T1读

7、读C=100C=C*2写回写回CROLLBACKC恢复为恢复为100T2读读C=200并发控制并发控制4封锁的定义封锁的定义 封锁就是事务封锁就是事务T在对某个数据对象如表、记在对某个数据对象如表、记录等操作之前，先向系统发出请求，对其录等操作之前，先向系统发出请求，对其加锁，从而对该数据对象有了一定的控制，加锁，从而对该数据对象有了一定的控制，在事务在事务T释放它的锁之前，其他事务不能更释放它的锁之前，其他事务不能更新此数据对象。新此数据对象。封锁是并发控制的一个非常重要的技术。封锁是并发控制的一个非常重要的技术。并发控制并发控制4封锁的类型封锁的类型 排它锁（X锁，锁，eXclusive

8、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锁

9、。锁。并发控制并发控制相容矩阵相容矩阵不相容请求不相容请求相容请求相容请求T1 T2XSXNNSNY并发控制并发控制4一级封锁协议一级封锁协议 事务事务T在修改数据在修改数据R之前必须对其加之前必须对其加X锁，直锁，直到事务结束才释放。事务结束包括正常结束到事务结束才释放。事务结束包括正常结束(COMMIT)和非正常结束和非正常结束(ROLLBACK)。一级封锁协议可以防止丢失修改，并保证事一级封锁协议可以防止丢失修改，并保证事务务T是可恢复的。在一级封锁协议中，如果是可恢复的。在一级封锁协议中，如果仅仅是读数据而不对其进行修改，是不需要仅仅是读数据而不对其进行修改，是不需要对其加锁的，因此它

10、不能保证可重复读和不对其加锁的，因此它不能保证可重复读和不读读“脏脏”数据。数据。并发控制并发控制T1XLOCK A获得获得读读A=16A=A-1写回写回A=15COMMITUNLOCK AT2XLOCK A等待等待等待等待等待等待等待等待获得获得XLOCK A读读A=15A=A-1写回写回A=14COMMITUNLOCK A没有丢失修改并发控制并发控制4二级锁协议二级锁协议 二级锁协议是：一级锁协议加上事务二级锁协议是：一级锁协议加上事务T在读在读取数据取数据R之前必须先对其加之前必须先对其加S锁，读完后即锁，读完后即可释放可释放S锁。二级锁除了防止丢失修改，还锁。二级锁除了防止丢失修改，还

11、可以进一步防止读可以进一步防止读“脏脏”数据。但由于读完数据。但由于读完后即可释放后即可释放S锁，所以不能保证可重复读。锁，所以不能保证可重复读。并发控制并发控制T1XLOCK C获得获得读读C=100C=C*2写回写回C200ROLLBACKC恢复为恢复为100UNLOCK CT2SLOCK C等待等待等待等待等待等待获得获得SLOCK C读读C=100COMMITUNLOCK C不读脏数据并发控制并发控制4三级锁协议三级锁协议 三级锁协议是：一级锁协议加上事务三级锁协议是：一级锁协议加上事务T在读在读取取R之前必须对其加之前必须对其加S锁，直到事务结束才锁，直到事务结束才释放。三级封锁协议

12、除了防止丢失修改和读释放。三级封锁协议除了防止丢失修改和读“脏脏”数据以外，还进一步防止了不可重复数据以外，还进一步防止了不可重复读。读。并发控制并发控制T1SLOCK A获得获得SLOCK B获得获得读读A=50读读B=100求和求和150读读A50读读B100求和求和=150COMMITUNLOCK AUNLOCK BT2XLOCK B等待等待等待等待等待等待等待等待等待等待等待等待T1T2等待等待等待等待等待等待等待等待获得获得XLOCK B读读B100B=B*2 写回写回B=200COMMITUNLOCK B可重复读并发控制并发控制X锁锁S锁锁一致性保证一致性保证操作操作结束结束释放释

13、放事务事务结束结束释放释放操作操作结束结束释放释放事务事务结束结束释放释放不丢不丢失修失修改改不读不读“脏脏”数据数据可重可重复读复读一级封锁一级封锁协议协议 二级封锁二级封锁协议协议 三级封锁三级封锁协议协议 并发控制并发控制T1SLOCK RUNLOCK RT2XLOCK R等待等待等待等待等待等待等待等待等待等待等待等待T3SLOCK R操作操作操作操作UNLOCK RT4SLOCK R操作操作操作操作操作操作活锁并发控制并发控制4死锁死锁(Deadlock)定义定义在数据库运行期间，如果存在一个事务集合在数据库运行期间，如果存在一个事务集合=T0，T1，Tn，使得，使得T0等待等待T1

14、持有的持有的数据项锁，数据项锁，Tn-1等待等待Tn持有的数据项锁，持有的数据项锁，Tn等待等待T1持有的数据项锁，则称系统处于死持有的数据项锁，则称系统处于死锁状态，锁状态，称为死锁事务集合。称为死锁事务集合。并发控制并发控制4死锁的例子死锁的例子如果事务如果事务T1封锁了数据封锁了数据R1，T2封锁了数据封锁了数据R2，然后然后T1又请求封锁又请求封锁R2，因，因T2已封锁了已封锁了R2，于，于是是T1等待等待T2释放释放R2上的锁。接着，上的锁。接着，T2又申请又申请封锁封锁R1，因，因T1已经封锁了已经封锁了R1，T2也只能等待也只能等待T1释放释放R1上的锁。这样就出现了上的锁。这样

15、就出现了T1在等待在等待T2，而而T2又在等待又在等待T1的局面，的局面，T1和和T2两个事务永两个事务永远不能结束，形成死锁。远不能结束，形成死锁。并发控制并发控制4解决死锁的方法解决死锁的方法预防死锁预防死锁死锁检测和恢复死锁检测和恢复并发控制并发控制4预防死锁预防死锁 一次封锁法一次封锁法 一次封锁法要求每个事务必须一次将其所有要使用的数据一次封锁法要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行。一次加锁法可以有效地防止全部加锁，否则就不能执行。一次加锁法可以有效地防止死锁的发生，但由于需要扩大加锁的范围，因此降低了系死锁的发生，但由于需要扩大加锁的范围，因此降低了系统

16、的并发度。统的并发度。顺序封锁法顺序封锁法 顺序封锁法是预先对数据对象规定一个封锁顺序，所有的顺序封锁法是预先对数据对象规定一个封锁顺序，所有的事务都要按照这个顺序实行封锁。顺序封锁法可以有效地事务都要按照这个顺序实行封锁。顺序封锁法可以有效地防止死锁，但其实施由于数据库中数据的不断变化和事务防止死锁，但其实施由于数据库中数据的不断变化和事务封锁要求的动态提出而难度很大。封锁要求的动态提出而难度很大。并发控制并发控制4死锁检测死锁检测 超时法超时法 如果一个事务的等待时间超过了规定的期限，就如果一个事务的等待时间超过了规定的期限，就认为发生了死锁。认为发生了死锁。等待图法等待图法 事务等待图是

17、一个有向回路事务等待图是一个有向回路G=(T,U)。T为结点为结点的集合，每个结点表示正在运行的事务；的集合，每个结点表示正在运行的事务；U为边为边的集合，每条边表示事务等待的情况。若的集合，每条边表示事务等待的情况。若T1等等待待T2，则，则T1，T2之间画一条有向边，从之间画一条有向边，从T1指向指向T2。事务等待图动态地反映了所有事务的等待。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性的检测事务等待图，情况。并发控制子系统周期性的检测事务等待图，如果发现图中存在回路，则表示系统出现死锁。如果发现图中存在回路，则表示系统出现死锁。并发控制并发控制T2T1T3事务号事务号占

18、有资源号占有资源号请求资源号请求资源号T1R1R2T2R2R3T3R3R1并发控制并发控制4死锁恢复死锁恢复 DBMS的并发控制子系统一旦检测到系统中的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。对于所撤销的事务所务得以继续运行下去。对于所撤销的事务所作的操作必须加以恢复。作的操作必须加以恢复。事务的调度与可串行性事务的调度与可串行性 串行调度串行调度 在串行调度

19、中，属于同一事务的指令紧挨在一起。在串行调度中，属于同一事务的指令紧挨在一起。对于有对于有n个事务的事务组，可以有个事务的事务组，可以有n！个有效调！个有效调度。度。并行调度并行调度 在并行调度中，来自不同事务的指令可以交叉执在并行调度中，来自不同事务的指令可以交叉执行。行。事务的调度与可串行性事务的调度与可串行性4问题：计算机系统对并发事务中并发操作问题：计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能产生的调度是随机的，而不同的调度可能产生不同的结果，那么哪个结果是正确的呢？不同的结果，那么哪个结果是正确的呢？4定义：多个事务的并发执行是正确的，当定义：多个事务的并发执行是正

20、确的，当且仅当其结果与按某一次序串行的执行它且仅当其结果与按某一次序串行的执行它们时的结果相同，我们称这种调度策略为们时的结果相同，我们称这种调度策略为可串行化调度。一个给定的并发调度，当可串行化调度。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调且仅当它是可串行化的，才认为是正确调度。度。并发控制并发控制4两段锁协议两段锁协议(Two-phase Locking)内容内容在对任何数据进行读、写操作之前，事务在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。首先要获得对该数据的封锁。在释放一个封锁之后，事务不再获得任何在释放一个封锁之后，事务不再获得任何其它封锁。其它封

21、锁。并发控制并发控制 所谓两阶段锁协议的含义是指所有事务必须所谓两阶段锁协议的含义是指所有事务必须分两个阶段对数据项加锁和解锁。第一阶段分两个阶段对数据项加锁和解锁。第一阶段是获得封锁也称扩展阶段。在这一阶段，事是获得封锁也称扩展阶段。在这一阶段，事务可以申请获得任何数据项上的任何类型的务可以申请获得任何数据项上的任何类型的封锁，但不能释放任何锁。第二阶段是释放封锁，但不能释放任何锁。第二阶段是释放阶段，也称收缩阶段。在这阶段，事务可以阶段，也称收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的封锁，但是释放任何数据项上的任何类型的封锁，但是不能够再申请任何锁。不能够再申请任何锁。定理：

22、若所有事务均遵从两段锁协议，则这定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。些事务的所有并行调度都是可串行化的。并发控制并发控制T1SLOCK B得到得到读读B=2Y=BXLOCK AA=Y+1写回写回A=3UNLOCK BUNLOCK AT2SLOCK A等待等待等待等待等待等待等待等待等待等待T1T2SLOCK A得到得到读读A=3Y=AXLOCK B得到得到B=Y+1写回写回B=4UNLOCK BUNLOCK A并发控制并发控制4封锁粒度封锁粒度 封锁对象的大小称为封锁粒度封锁对象的大小称为封锁粒度 封锁对象：包括逻辑单元，如封锁对象：包括逻辑单元，如:属性

23、值、属性值集合、属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库；和元组、关系、某索引项、整个索引、整个数据库；和物理单元如：物理页、块。物理单元如：物理页、块。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度小，则并发度高，封锁机构复杂，开销高。封锁粒度小，则并发度高，封锁机构复杂，开销高。如果在一个系统中同时支持多种封锁粒度供不同的事如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁务选择是比较理想的，这种封锁方法称为多粒度封锁（Multiple Granularity Lockin

24、g）。选择封锁粒度时）。选择封锁粒度时应同时考虑封锁开销和并发度两个因素，适当选择封应同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以达到最优效果。锁粒度以达到最优效果。并发控制并发控制4多粒度树多粒度树 多粒度树的根结点是整个数据库，表示最大多粒度树的根结点是整个数据库，表示最大的粒度。叶结点表示最小的粒度。的粒度。叶结点表示最小的粒度。数据库关系Rn关系R1元组元组元组元组并发控制并发控制4多粒度封锁协议多粒度封锁协议 多粒度封锁协议允许多粒度树中的每个结点多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结

25、点也被加以同样类型的锁。结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以因此，在多粒度封锁中一个数据对象可能以两种方式封锁，即：两种方式封锁，即：显式封锁是应事务的要求直接加到数据对象上的显式封锁是应事务的要求直接加到数据对象上的封锁。封锁。隐式封锁是该数据对象没有独立加锁，是由于其隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。上级结点加锁而使该数据对象加上了锁。并发控制并发控制4意向锁意向锁 一般的，对某个数据对象加锁，系统要检查该数据一般的，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上对象上有

26、无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁冲突；还要检查其所有下级结点，看上的隐式封锁冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突。效率面的显式封锁是否与本事务的隐式封锁冲突。效率很低，因此引入了意向锁。很低，因此引入了意向锁。意向锁的含义是如果对一个结点加意向锁，则说明意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。必须先对它的上层结点加意向锁。并发控制并发

27、控制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