第11章-并发控制课件

*,数据库系统,*,第十一章 并发控制,本章要求：,1、了解并发操作可能产生的数据不一致性,2、掌握并发控制的技术：封锁机制、三级封锁协议、,活锁的避免、死锁的预防、诊断及解除,3、掌握并发调度的正确性标准和技术（可串行性、,两段锁协议）,8/9/2024,1,数据库系统,本章要求：1、了解并发操作可能产生的数据不一致性8/20/2,1 并发控制概述,在多用户数据库系统中，当多个用户并发存取数据库时就会产生多个事务同时存取同一数据的情形。若不加控制，可能会存取和存储不正确的数据，造成数据库的不一致性。,在并发操作情况下，对事务的操作序列的调度是随机的，考虑飞机订票系统，若按下面的序列调度：,考虑飞机订票系统中的一个活动序列：,甲售票点读出某航班的机票余额A，设 A=16，,乙售票点读出同一航班的机票余额A，也为16，,8/9/2024,2,数据库系统,1 并发控制概述 在多用户数据库系统中，当,甲售票点卖出一张机票，修改余额 A,A1，,A变为15，把A 写回数据库,乙售票点也卖出一张机票，修改余额 A,A1，,A也为15，把A写回数据库。,卖出两张机票，而余额只减少1。错误！,这种情况就造成数据库的不一致性，这种不一致性是由并发操作引起的。,并发操作带来的数据不一致性包括三类：,8/9/2024,3,数据库系统,甲售票点卖出一张机票，修改余额 AA1，卖出两张机,一、并发操作可能造成的不一致性,1、丢失修改,：,两事务读出同一数据并修改，先写回的数据修改丢失,时间 事务T1 事务 T2,A,16,读出A=,读出A=,A,A1,写回A=,A,A1,写回A=,15,A,T1的修改丢失,16,15,15,16,15,A,我的数据呢？,8/9/2024,4,数据库系统,一、并发操作可能造成的不一致性时间 事务T1,2、不可重复读,事务T1读取某一数据，事务T2读取并修改了同一数据；,事务T1为了对读取值进行校对再读此数据，得到了不同的结果。,时间 事务T1 事务 T2,读出A=50，B=100,求和=150,读出B=100,计算 B,B,2，写回B,读出A=50，B=,求和=,200,250,T1读出B的值与原来的不符，验算结果不对,8/9/2024,5,数据库系统,2、不可重复读时间 事务T1,有三种情况可造成不可重复读,（1）,事务T1读取某一数据后，事务,T2对其做了修改,，事务T1再次读取该数据时，发现与前次不同；,（2）,事务T1按一定条件读取了某些数据记录后，事务,T2删除,了其中的部分记录，事务T1再次按相同条件读取记录时，发现有些记录不存在；,（3）,事务T1按一定条件读取了某些数据记录后，事务,T2插入了一些记录,，事务T1再次按相同条件读取记录时，发现多了一些记录。,8/9/2024,6,数据库系统,有三种情况可造成不可重复读8/20/20236数据库系统,3、读出“脏”数据,事务T1修改某一数据，事务T2读取同一数据；,事务T1由于某种原因被撤消，则T2读到的就是“脏”数据。,时间 事务T1 事务 T2,读出C=100,计算 C,C,2，写回C,ROLLBACK,C恢复为100,“脏”数据,读出,C=200,T2读出的数据无效,C=200,8/9/2024,7,数据库系统,3、读出“脏”数据时间 事务T1,产生上述三类不一致性的主要原因就是,并发操作破坏了事务的隔离性。,并发控制,就是要用正确的方式调度并发操作，使某个事务的执行不受其它事务的干扰。,并发控制的技术是封锁，即事务在修改某个对象前，先锁住该对象，不允许其它事务读取或修改该对象，修改完毕或事务完成后再将锁打开。,8/9/2024,8,数据库系统,产生上述三类不一致性的主要原因就是并发操作破,2 封锁（Locking）,封锁的类型：,排它锁,（Exclusive Lock，简称,X锁,，又称,互斥锁,）：,若事务T对数据对象R加上X锁，则只允许T读、写R，禁止其它事务对R加任何锁，相应地其它事务就无法读、写对象R。,共享锁,（Shared Lock，简称,S锁,）：,若事务T对数据对象R加上S锁，则T可以读R，但不可以写R，且其它事务可以对R加S锁、但禁止加X锁。这保证了事务T在释放R的S锁之前，其它事务只可以读R，不可以修改R。,8/9/2024,9,数据库系统,2 封锁（Locking）封锁的类型：排它锁（Exclu,附加知识点,（,参见P295例2图11.4,）：,1、封锁协议（Locking Protocol）,在运用X锁和S锁对数据对象加锁时，对何时申请X锁或S锁、持锁时间、何时释放等的一些约定。,2、三级封锁协议,基本方法：,事务在读数据对象R时先上S锁，封锁后才能读R，否则需等待；,事务在写数据对象R时先上X锁，封锁后才能写R，否则需等待；,何时,释放锁,（,Unlock,）？,8/9/2024,10,数据库系统,附加知识点（参见P295例2图11.4）：2、三级封锁协议,根据上锁的类型和释放锁的时机，分为三种情况。,1,级封锁协议,:,事务T在修改数据对象R之前必须先对其加X锁，直到事务结束才释放。,2,级封锁协议,:,1级封锁协议+事务T在读取数据对象R之前必须先对其加S锁，,读,完即释放S锁,。,3,级封锁协议,:,1级封锁协议+事务T在读取数据对象R之前必须先对其加S锁，,S,锁也是直到事务结束才释放,。,8/9/2024,11,数据库系统,根据上锁的类型和释放锁的时机，分为三种情况。1级封锁协议:2,1,级封锁协议,:,事务T在修改数据对象R之前必须先对其加X锁，直到,事务结束,才释放。,分析：,时间 事务T1 事务 T2,请求X锁,对A加X锁,读出A=16,请求X锁,等待,A,A1,写回A=15,Commit,释放X锁,对A加X锁,读出A=15,A,A1,写回A=14,Commit,释放X锁,作用：,防止丢失修改,保证事务是可恢复的,8/9/2024,12,数据库系统,1级封锁协议:分析：时间 事务T1 事务,2,级封锁协议,:,1级封锁协议+事务T在读取数据对象R之前必须先对其加S锁，读完即释放S锁。,分析：,作用：,防止丢失修改,时间 事务T1 事务 T2,请求X锁,对C加X锁,读出C=100,计算 C,C,2,写回C,ROLLBACK,（C恢复为100）,释放X锁,请求S锁,等待,防止读“脏”数据,对C加S锁,读出C=100,释放S锁,保证事务是可恢复的,8/9/2024,13,数据库系统,2级封锁协议:分析：作用：防止丢失修改时间,3,级封锁协议,:,1级封锁协议+事务T在读取数据对象R之前必须先对其加S锁，S锁也是直到事务结束才释放。,分析：,作用：,防止丢失修改,对A加S锁,对B加S锁,读出A=50，B=100,求和=150,对B请求X锁,等待,读出A=50，B=100,求和=150,Commit,释放A、B上的S锁,时间 事务T1 事务 T2,对B加X锁,读出B=100,计算 B,B,2，写回B,Commit,释放X锁,防止读“脏”数据,保证可重复,读,保证事务是可恢复的,8/9/2024,14,数据库系统,3级封锁协议:分析：作用：防止丢失修改 对A加S锁,对R1上X锁,对R2上X锁,对R2请求X锁,等待,对R1请求X锁,等待,3 活锁和死锁,使用封锁机制，得不到锁的事务就要等待，这可能出现下述局面：,T1,T2,T1和T2将,永远等待下去,8/9/2024,15,数据库系统,对R1上X锁3 活锁和死锁 使用封锁,1、活锁（Livelock）：,数据对象不断处于上锁、开锁的交替状态，某个事务有可能为该对象上锁，但始终没有得到上锁机会而永久等待下去的情形。例如：,T1 T2 T3 T4 .,封锁R,请求封锁R 请求封锁R,等待 请求封锁R 等待,释放锁,封锁R,等待,释放锁,封锁R,如此下去，T2可能永远不能封锁R。,8/9/2024,16,数据库系统,1、活锁（Livelock）：T1,避免活锁,：如采用先来先服务策略。,2、死锁（Deadlock）：,多个事务因封锁冲突（竞争资源）而永远等待下去的情形。如,（课件p15例子）,死锁问题的解决方法,预防死锁,诊断死锁并解除,一次封锁法,顺序封锁法,超时法,等待图法,（1）一次封锁法,每个事务必须将所要求的数据对象全部上锁后才能执行读写操作，否则释放占用的资源。,存在的问题,使数据的上锁时间增长，降低了系统的并发度。,8/9/2024,17,数据库系统,避免活锁：如采用先来先服务策略。2、死锁（Deadloc,很难确定事务执行期间需封锁的数据对象。有些一开始不需要封锁的对象，随着数据库数据的变化，可能变成封锁对象，为避免此种情况发生，只能扩大封锁范围。,（2）顺序封锁法,对所有数据对象规定一个封锁顺序，所有事务均按这个顺,序实行封锁。,存在的问题,：,很难维护数据对象的封锁顺序，因为数据对象很多并在不断,地增加、减少。,很难确定事务需封锁那些对象，从而很难按规定的顺序封锁。,预防死锁的策略不很适合数据库的特点，DBMS普遍采用,诊断死锁并解除的方法。,8/9/2024,18,数据库系统,很难确定事务执行期间需封锁的数据对象。有些一开始不需要,（3）超时法,当一个事务的等待时间超过了规定的时限，就认为发生了死锁。,存在的问题：,时限规定的太短，可能误判死锁，规定的太长，又不能及时发现死锁。因此很难确定一个合理的时限。,（4）等待图法,用一个有向图表示事务等待的情况。图中节点表示事务，边表示事务间的等待关系。并发控制子系统定时检查此图，若发现有回路，则产生死锁。,发生死锁时，解除死锁的方法：,选择一个处理代价最小的事务，将其撤消。,ROLLBACK,8/9/2024,19,数据库系统,（3）超时法（4）等待图法发生死锁时，解除死锁的方法：ROL,4 并发调度的可串行性,多事务并发执行，对并发操作的调度是随机的，如何保证正确性？,1、调度（Schedule）：,若干个事务的操作构成的序列。,2、串行与并发,对调度S中的两个事务Ti和Tj，若S中Ti的操作都在Tj的操作之前（或反之），则称Ti、Tj是,串行执行,的；否则称作是,并发执行,的。,若调度S中的所有事务都是串行执行的，则称S是,串行,的（Serial）。,8/9/2024,20,数据库系统,4 并发调度的可串行性 多事务并发执行，对并,3、可串行化（Serializable）,多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度为可串行化的调度。,调度,可串行化的,不可串行化的,串行的,并发的,并发的,所有事务串行起来的调度策略一定是正确的调度策略。尽管一组事务可能有多个串行调度序列，且产生的执行结果不一定相同，但每个序列都不会将数据库置于不一致状态。,8/9/2024,21,数据库系统,3、可串行化（Serializable）调度可串行化的串行的,4、一点说明,：,对若干个事务，不同的并发调度策略其最终的执行结果不一定完全相同。但只要它们的调度是可串行化的，则都是正确调度。,如：事务T1：读B；A,B+1；写回A。,事务T2：读A；B,A+1；写回B。,T1 T2,读B,A,B+1,写A,读A,B,A+1,写B,T1 T2,读A,B,A+1,写B,读B,A,B+1,写A,T1 T2,读B,读A,A,B+1,写A,B,A+1,写B,结果,A=3,B=4,假设T1、T2执行前,A=2，B=2,A=4,B=3,A=3,B=3,8/9/2024,22,数据库系统,4、一点说明：如：事务T1：读B；AB+1；写回A。T,T1 T2,读B,读A,A,B+1,写A,B,A+1,写B,T1 T2,读B,读A,A,B+1,写A,B,A+1,写B,分析右边的调度：,若采用2级封锁协议，,则可能得到这样的调度,仍是不可串行化的调度,若采用3级封锁协议，,则可能得到这样的调度,永久等待，造成死锁,Slock B,Unlock B,Slock A,Unlock A,Xlock A,Unlock A,Xlock B,Unlock B,Slock B,读B,Slock A,读A,Xlock A,A,B+1,Xlock B,写A,Unlock A,Unlock B,B,A+1,写B,Unlock A,Unlock B,因此，三级封锁协议不能保证得到可串行化的调度，也会造成死锁。,8/9/2024,23,数据库系统,T1 T2 T1,5 两段锁协议,1、两段封锁协议,（也称,两相上锁协议,）,（2-Phase-Locking Protocol，简写,2PL,）,（1）在对任何数据进行读、写操作之前，事务首先要申请并获得对该数据的封锁（读时S锁，写时X锁）；,（2）在释放一个封锁之后，事务不再申请和获得新的封锁。,例：,Lock A Lock B Lock C,Unlock B Unlock A Unlock C,Lock A Lock B,Unlock B,Lock C,Unlock A Unlock C,含义,：事务封锁分两个阶段,第一阶段是,扩展阶段,（Growing Phase），只进行上锁,第二阶段是,收缩阶段,（Shrinking Phase）,只进行解锁,8/9/2024,24,数据库系统,5 两段锁协议1、两段封锁协议（也称两相上锁协议）例：含义,2、2PL的正确性,定理,：若所有事务都遵守两段封锁协议，则对这些事务的任何并发调度策略都是可串行化的。,3、说明,2PL是并发控制正确性的充分条件，但不是必要条件。,即若所有事务都遵守2PL，则这些事务的任何并发调度都是可串行化的，反之，一个并发调度是可串行化的，不一定所有事务都遵守2PL。（参见P299图11.7（d）,8/9/2024,25,数据库系统,2、2PL的正确性3、说明 2PL是并发控制正确性的充,Lock A Lock B Lock C,Unlock B Unlock A Unlock C,允许读写,不允许读写,此时才允许读写,预防死锁的,一次封锁法,2PL,2PL会产生死锁（参见P302图11.9）。,2PL不隐含预防死锁的一次封锁法，但一次封锁法肯定遵守2PL。,8/9/2024,26,数据库系统,Lock A Lock B Lock C,6 封锁的粒度,1、封锁的粒度（Granularity）,封锁对象的大小。可以是数据库、表、记录、字段等。,粒度大，封锁开销小，但影响共享,粒度小，封锁开销大，但共享性好,2、多粒度封锁（,Multiple Granularity Locking),同时支持多种封锁粒度供不同事务选择的封锁方法。,多粒度封锁方法依赖的数据结构-多粒度树,将数据库中的数据对象按相互关系和粒度大小组织成的树型结构，其中根结点表示最大数据粒度，通常为整个数据库，叶结点表示最小数据粒度。,8/9/2024,27,数据库系统,6 封锁的粒度1、封锁的粒度（Granularity）粒度,多粒度封锁协议,允许对多粒度树中的每个结点独立地加锁，并且对每一个结点加锁隐含着对其后裔结点也加以同样的锁。,由事务直接加到数据对象上的封锁称为,显式封锁,，因上级结点加锁而引起下级对象被封锁，称为,隐式封锁,。,显式封锁与隐式封锁的效果是一样的。,多粒度封锁方法,为对某数据对象加锁，系统要检查：,该对象有无显式封锁与之冲突；,该对象的上级结点有无显式封锁与之冲突；,该对象的下级结点有无显式封锁与之冲突；,当无任何冲,突时方能加,锁成功。,3、意向锁,用来指示下级结点正在被加锁的锁。对任一结点加锁时，必须先对其上级结点加意向锁。,8/9/2024,28,数据库系统,多粒度封锁协议当无任何冲3、意向锁8/20/202328数据,作用,：,减少加锁时的封锁冲突检查工作量。只需检查上级结点与 本结点是否已加了不相容的锁，并通过本结点的意向锁了解下级结点是否有不相容的锁，从而不必再检查下级结点。,三种意向锁,意向共享锁（IS锁）,如果要对某个对象加S锁，需先对其上级对象加IS锁。,意向排它锁（IX锁）,如果要对某个对象加X锁，需先对其上级对象加IX锁。,共享意向排它锁（SIX锁）,如果要对某对象加S锁，并对其下级对象加X锁，则应对该对象加SIX锁。,意向锁的封锁和释放顺序,封锁：自上而下,释放：自下而上,8/9/2024,29,数据库系统,作用：减少加锁时的封锁冲突检查工作量。只需检查上级结点与,