第11章并发控制.

并发控制第11章要点并发操作及影响并发操作的可串行性并发控制及实现技术序言事务并行地运行可充分利用系统资源，事务是并发控制的基本单位多用户数据库系统中允许多个用户同时使用数据库，即在同一时刻可能有多个事务并行运行同时并行方式单处理机系统中，事务并行实际上是这些事务的并行操作轮流交叉运行交叉并行方式并发控制机制的提出当多个用户并发地存取数据库时可能出现多个事务同时存取同一数据的情况，并发控制机制将对这些并发操作加以控制以保证每个事务的ACID特性，确保数据库的一致性并发控制机制是衡量某DBMS系统性能的指标之一11.1并发控制概述这种数据库的不一致是由并发操作引起的机票数量AA=16读读A=A-1A=A-1A=15A=15售票点售票点A=16A=16出售1出售1事务T1事务T2并发操作引起的丢失修改并发操作引起的数据不一致性包括三类丢失修改不可重复读读脏数据丢失修改事务T1对数据的修改被事务T2的修改覆盖T1读A=16A=A-1写回A＝15T2读A=16A=A-1写回A＝15并发操作引起的不可重复读不可重复读事务T1读取某一数据后，事务T2对其做了修改，当T1按同样条件再读时得到不同的值事务T1读取某些数据后，事务T2删除(或插入)了一些记录，当T1按同样条件再读时发现少(或多)了一些记录T1读A=1,B=2求A+B=3读A=1,B=4求A+B=5T2读B=2B=B*2写回B=4并发操作引起的读脏数据读脏数据事务T1修改了某数据并写回磁盘，事务T2读取了同一数据后，T1由于某种原因被撤销，被修改的值复原，此时T2读到的数据与数据库中的数据不一致T1读C=1C=C*2写回C=2ROLLBACKC恢复为1T2读C=2小结产生上述三类不一致性的主要原因并发操作破坏了事务的隔离性，事务间相互干扰并发控制的主要技术封锁技术(Locking)★时间戳技术(Timestamp)其他11.2封锁概念事务T在对某个数据对象(如数据库、表、记录等)操作之前，首先向系统发出加锁请求以便获得对数据对象相应的控制在事务T释放它所获得的锁之前，其他事务不能更新此数据对象锁的类型排它锁(eXclusivelock)：写锁若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁共享锁(Sharelock)：读锁若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁锁的相容矩阵Y：相容的请求N：不相容的请求T2T1XS-XS-T2T1XS-XNNYSNYY-YYY11.3封锁协议有了两种基本封锁，还需要什么约定？封锁协议的概念何时申请加锁、持锁时间、何时释放等规则不同的封锁协议所达到的系统一致性不同三个级别的封锁协议一级封锁协议内容：事务T在修改数据R之前必须先对其加X锁，直至事务结束•事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）评价：是否可解决•丢失修改？•可重复读？•读脏数据？可防止×不能保证×不能防止三个级别的封锁协议二级封锁协议内容：•读数据前加S锁，读完即释放•写数据前加X锁直至事务结束评价：是否可解决•丢失修改？•可重复读？•读脏数据？可防止×不能保证可防止三个级别的封锁协议三级封锁协议内容：•读数据前加S锁直至事务结束•写数据前加X锁直至事务结束评价：是否可解决•丢失修改？•可重复读？•读脏数据？可防止能保证可保证T1T2T1T2T1T2XlockA获得XlockA读A=16A=A-1写回A=15CommitUnlockAXlockA等待等待获得XlockA读A=15CommitUnlockA等待等待A=A-1写回A=14SlockASlockB读A=50求和=150读A=50CommitUnlockAXlockB等待等待获得XlockB读B=100CommitUnlockB等待等待B=B*2写回B=200读B=100读B=100求和=150UnlockB等待等待等待等待XlockC读C=100C=C*2写回C=200Rollback(C恢复为100)UnlockCSlockC等待等待获得SlockC读C=100CommitUnlockC等待没有丢失修改可重复读不读脏数据用封锁机制解决三种数据不一致性的示例不同级别的封锁协议X锁S锁一致性保证操作结束释放事务结束释放操作结束释放事务结束释放不丢失修改不读脏数据可重复性一级二级三级11.4活锁和死锁问题活锁举例说明：•事务T1封锁某数据后，事务T2请求封锁未获得并等待，而T1释放锁后，事务T3请求封锁并获得，T3释放锁后，事务T4请求封锁并获得……T2可能永远等待解决办法：采用先来先服务的策略死锁问题死锁举例说明：•事务T1和T2各自封锁了数据R1和R2后，又各自请求封锁R2和R1，因都无法获得而等待对方释放的现象解决的两类方法•预防死锁•允许发生死锁，采用一定手段定期诊断并解除死锁死锁的预防一次封锁法办法：每个事务一次将所有要使用的数据全部加锁存在问题？顺序封锁法办法：预先规定数据对象的封锁顺序，所有事务均按此顺序存在问题？在操作系统上广为采用的预防死锁的策略并不很适合数据库的特点因此DBMS普遍采用诊断并解除死锁的办法死锁的诊断与解决死锁的诊断超时法•办法：等待时间超过规定的时限•问题？等待图法•办法：画等待图，发现回路死锁的解决检测到死锁，选择一个处理死锁代价最小的事务，强行撤销，使其它事务可以继续下去恢复撤销事务所执行的数据修改操作11.5事务调度的可串行性引言DBMS需对多个并发事务进行运行调度能将所有事务串行起来的调度策略不会破坏数据库的不一致性，故而总是正确的概念可串行化的调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同可串行性是并发事务操作是否正确的判别准则事务调度的可串行性为了保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的保证事务调度可串行性的策略事务排它式执行(资源无法充分共享)两段锁(Two-PhaseLocking,2PL)协议其它，如时间戳(TimeStamp)方法等DBMS普通采用封锁方法实现并发操作调度的可串行性★并发事务的不同调度策略T1T2T1T2T1T2SlockBY=B=2UnlockBXlockAA=Y+1写回A(=3)UnlockAX=A=3UnlockA写回B(=4)UnlockBSlockAXlockBB=X+1a串行调度c不可串行化的调度(结果与a,b不同，错误调度)SlockBY=B=2UnlockBXlockAA=Y+1写回A(=3)UnlockAX=A=2UnlockA写回B(=3)UnlockBSlockAXlockBB=X+1SlockBY=B=2UnlockBXlockAA=Y+1写回A(=3)UnlockASlockAX=A=3UnlockA写回B(=4)UnlockBXlockBB=X+1等待等待等待T1T2SlockBY=B=3UnlockBXlockAA=Y+1写回A(=4)UnlockAX=A=2UnlockA写回B(=3)UnlockBSlockAXlockBB=X+1d可串行化的调度(结果与a相同，正确调度)T1:读B;A=B+1;写回A;T2:读A;B=A+1;写回B;A,B初值均为2b串行调度11.6两段锁协议概念：事务对数据项的加锁和解锁分为两个阶段完成获得封锁：在对数据读写之前首先申请并获得封锁；释放封锁：在释放一个封锁后不再申请和获得任何其他封锁如遵守两段锁协议的事务SlockA…SlockB…XlockC...UnlockB…UnlockA…UnlockC如不遵守两段锁协议的事务SlockA…UnlockA…SlockB...XlockC…UnlockC…UnlockB两段锁协议的性质两段锁协议是可串行化调度的充分条件，但不是必要条件若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的；若对并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议两段锁协议可以保证并发事务的正确性，但可能发生死锁T1T2T1T2T1T2SlockB读B=2Y=BA=Y+1写回A=3UnlockBUnlockASlockA等待等待读A=3UnlockBUnlockA等待等待Y=A写回B(=4)SlockB读B=2Y=BXlockAA=Y+1SlockA等待等待读A=3XlockBB=X+1等待等待X=AUnlockAUnlockB写回A(=3)UnlockASlockB读B=2XlockASlockA等待XlockB等待可串行调度遵守两段锁协议可串行调度不遵守两段锁协议遵守两段锁协议的事务发生死锁关于两段锁协议XlockA等待XlockBB=Y+1写回B(=4)UnlockB读A=2等待11.7封锁的粒度封锁的粒度即封锁对象的大小，如逻辑单元：属性、元组、关系、索引、数据库等物理单元：页、块等封锁粒度对并发控制的影响封锁粒度越大，并发度越小，系统封锁开销越小；封锁粒度越小，并发度越高，系统封锁开销越大；封锁粒度修改属性？修改关系？如何选择封锁粒度？多粒度封锁定义：一个系统中同时支持多种封锁粒度供不同事务选择的方法术语：结点、上层结点、后裔结点多粒度树显式封锁(应事务要求直接加锁)隐式封锁(由于上层结点加锁而加锁)数据库关系R1关系Rn元组元组元组元组多粒度封锁的问题操作办法对某个数据对象加锁，系统要检查该对象上有无显式封锁与之冲突；还要检查所有上级结点，看本事务的显式封锁是否与该对象上的隐式封锁冲突；还有检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突问题：检查效率低数据库关系R1关系Rn元组元组元组元组意向锁概念：如果对以一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁三种意向锁意向共享锁(IS)意向排它锁(IX)共享意向排它锁(SIX)=S+IX•对某个表加SIX，表示该事务要读整个表，同时会更新个别元组扩充的封锁相容矩阵锁的强度的偏序关系T1T2SXISIXSIX-SYNYNNYXNNNNNYISYNYYYYIXNNYYNYSIXNNYNNY-YYYYYYXSIXSIXIS—具有意向锁的多粒度封锁方法的特点任意事务要对一个数据对象加锁，必须先对其上层结点加意向锁。申请封锁时按自上而下的次序进行，释放封锁时按自下而上的次序进行该方法提高了系统的并发度，减少了加锁和解锁的开销