并发控制市公开课一等奖省赛课获奖课件

第十一章并发控制一、问题产生二、并发控制概述三、封锁四、活锁和死锁五、并发调度可串行性六、两段锁协议七、封锁粒度八、小结并发控制第1页一、问题产生多用户数据库系统存在允许多个用户同时使用数据库系统飞机定票数据库系统银行数据库系统特点：在同一时刻并发运行事务数可达数百个并发控制第2页问题产生（续）不一样多事务执行方式(1)事务串行执行每个时刻只有一个事务运行，其它事务必须等到这个事务结束以后方能运行不能充分利用系统资源，发挥数据库共享资源特点T1T2T3事务串行执行方式并发控制第3页问题产生（续）(2)交叉并发方式（InterleavedConcurrency）在单处理机系统中，事务并行执行是这些并行事务并行操作轮番交叉运行单处理机系统中并行事务并没有真正地并行运行，但能够降低处理机空闲时间，提升系统效率并发控制第4页问题产生（续）事务交叉并发执行方式并发控制第5页问题产生（续）(3)同时并发方式（simultaneousconcurrency）多处理机系统中，每个处理机能够运行一个事务，多个处理机能够同时运行多个事务，实现多个事务真正并行运行并发控制第6页问题产生（续）事务并发执行带来问题会产生多个事务同时存取同一数据情况可能会存取和存放不正确数据，破坏事务一致性和数据库一致性并发控制第7页二、并发控制概述并发控制机制任务对并发操作进行正确调度确保事务隔离性确保数据库一致性并发控制第8页T1修改被T2覆盖了！并发控制概述（续）并发操作带来数据不一致性实例[例1]飞机订票系统中一个活动序列①甲售票点(甲事务)读出某航班机票余额A，设A=16；②乙售票点(乙事务)读出同一航班机票余额A，也为16；③甲售票点卖出一张机票，修改余额A←A-1，所以A为15，把A写回数据库；④乙售票点也卖出一张机票，修改余额A←A-1，所以A为15，把A写回数据库结果明明卖出两张机票，数据库中机票余额只降低1并发控制第9页并发控制概述（续）这种情况称为数据库不一致性，是由并发操作引发。在并发操作情况下，对甲、乙两个事务操作序列调度是随机。若按上面调度序列执行，甲事务修改就被丢失。原因：第4步中乙事务修改A并写回后覆盖了甲事务修改并发控制第10页并发控制概述（续）并发操作带来数据不一致性丢失修改（LostUpdate）不可重复读（Non-repeatableRead）读“脏”数据（DirtyRead）记号R(x):读数据xW(x):写数据x

并发控制第11页1.丢失修改两个事务T1和T2读入同一数据并修改，T2提交结果破坏了T1提交结果，造成T1修改被丢失。上面飞机订票例子就属这类并发控制第12页丢失修改（续）T1T2①R(A)=16②R(A)=16③A←A-1W(A)=15W④A←A-1W(A)=15丢失修改并发控制第13页2.不可重复读不可重复读是指事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。并发控制第14页不可重复读（续）不可重复读包含三种情况：(1)事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不一样值并发控制第15页不可重复读（续）T1读取B=100进行运算T2读取同一数据B，对其进行修改后将B=200写回数据库。T1为了对读取值校对重读B，B已为200，与第一次读取值不一致T1T2①R(A)=50R(B)=100求和=150②R(B)=100B←B*2(B)=200③R(A)=50R(B)=200和=250(验算不对)不可重复读

比如：并发控制第16页不可重复读（续）(2)事务T1按一定条件从数据库中读取了一些数据统计后，事务T2删除了其中部分统计，当T1再次按相同条件读取数据时，发觉一些统计消失了(3)事务T1按一定条件从数据库中读取一些数据统计后，事务T2插入了一些统计，当T1再次按相同条件读取数据时，发觉多了一些统计。后两种不可重复读有时也称为幻影现象（PhantomRow）并发控制第17页3.读“脏”数据读“脏”数据是指：事务T1修改某一数据，并将其写回磁盘事务T2读取同一数据后，T1因为某种原因被撤消这时T1已修改过数据恢复原值，T2读到数据就与数据库中数据不一致T2读到数据就为“脏”数据，即不正确数据并发控制第18页读“脏”数据（续）T1T2①R(C)=100C←C*2W(C)=200②R(C)=200③ROLLBACKC恢复为100比如读“脏”数据

T1将C值修改为200，T2读到C为200T1因为某种原因撤消，其修改作废，C恢复原值100这时T2读到C为200，与数据库内容不一致，就是“脏”数据

并发控制第19页并发控制概述（续）数据不一致性：因为并发操作破坏了事务隔离性并发控制就是要用正确方式调度并发操作，使一个用户事务执行不受其它事务干扰，从而防止造成数据不一致性并发控制第20页并发控制概述（续）并发控制主要技术有封锁(Locking)时间戳(Timestamp)乐观控制法商用DBMS普通都采取封锁方法并发控制第21页三、封锁1、什么是封锁2、基本封锁类型3、锁相容矩阵并发控制第22页1、什么是封锁封锁就是事务T在对某个数据对象（比如表、统计等）操作之前，先向系统发出请求，对其加锁加锁后事务T就对该数据对象有了一定控制，在事务T释放它锁之前，其它事务不能更新此数据对象。并发控制第23页2、基本封锁类型一个事务对某个数据对象加锁后终究拥有什么样控制由封锁类型决定。基本封锁类型排它锁（ExclusiveLocks，简记为X锁）共享锁（ShareLocks，简记为S锁）并发控制第24页排它锁排它锁又称为写锁若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型锁，直到T释放A上锁确保其它事务在T释放A上锁之前不能再读取和修改A并发控制第25页共享锁共享锁又称为读锁若事务T对数据对象A加上S锁，则其它事务只能再对A加S锁，而不能加X锁，直到T释放A上S锁确保其它事务能够读A，但在T释放A上S锁之前不能对A做任何修改并发控制第26页3、锁相容矩阵Y=Yes，相容请求N=No，不相容请求

T1T2XS-XNNYSNYY-YYY并发控制第27页锁相容矩阵（续）在锁相容矩阵中：最左边一列表示事务T1已经取得数据对象上锁类型，其中横线表示没有加锁。最上面一行表示另一事务T2对同一数据对象发出封锁请求。T2封锁请求能否被满足用矩阵中Y和N表示Y表示事务T2封锁要求与T1已持有锁相容，封锁请求能够满足N表示T2封锁请求与T1已持有锁冲突，T2请求被拒绝并发控制第28页使用封锁机制处理丢失修改问题T1T2①XlockA②R(A)=16XlockA③A←A-1等候W(A)=15等候Commit等候UnlockA等候④取得XlockAR(A)=15A←A-1⑤W(A)=14CommitUnlockA例：事务T1在读A进行修改之前先对A加X锁当T2再请求对A加X锁时被拒绝T2只能等候T1释放A上锁后T2取得对AX锁这时T2读到A已经是T1更新过值15T2按此新A值进行运算，并将结果值A=14送回到磁盘。防止了丢失T1更新。没有丢失修改并发控制第29页使用封锁机制处理不可重复读问题T1T2①SlockASlockBR(A)=50R(B)=100求和=150②XlockB等候等候③R(A)=50等候R(B)=100等候求和=150等候Commit等候UnlockA等候UnlockB等候④取得XlockBR(B)=100B←B*2⑤W(B)=200CommitUnlockB事务T1在读A，B之前，先对A，B加S锁其它事务只能再对A，B加S锁，而不能加X锁，即其它事务只能读A，B，而不能修改当T2为修改B而申请对BX锁时被拒绝只能等候T1释放B上锁T1为验算再读A，B，这时读出B仍是100，求和结果仍为150，即可重复读T1结束才释放A，B上S锁。T2才取得对BX锁可重复读并发控制第30页使用封锁机制处理读“脏”数据问题T1T2①XlockCR(C)=100C←C*2W(C)=200②SlockC等候③ROLLBACK等候(C恢复为100)等候UnlockC等候④取得SlockCR(C)=100⑤CommitCUnlockC例事务T1在对C进行修改之前，先对C加X锁，修改其值后写回磁盘T2请求在C上加S锁，因T1已在C上加了X锁，T2只能等候T1因某种原因被撤消，C恢复为原值100T1释放C上X锁后T2取得C上S锁，读C=100。防止了T2读“脏”数据不读“脏”数据

并发控制第31页四、活锁和死锁封锁技术能够有效地处理并行操作一致性问题，但也带来一些新问题死锁活锁并发控制第32页1、活锁事务T1封锁了数据R事务T2又请求封锁R，于是T2等候。T3也请求封锁R，当T1释放了R上封锁之后系统首先同意了T3请求，T2依然等候。T4又请求封锁R，当T3释放了R上封锁之后系统又同意了T4请求……T2有可能永远等候，这就是活锁情形并发控制第33页活锁（续）活锁并发控制第34页活锁（续）防止活锁：采取先来先服务策略当多个事务请求封锁同一数据对象时按请求封锁先后次序对这些事务排队该数据对象上锁一旦释放，首先同意申请队列中第一个事务取得锁并发控制第35页2、死锁事务T1封锁了数据R1T2封锁了数据R2T1又请求封锁R2，因T2已封锁了R2，于是T1等候T2释放R2上锁接着T2又申请封锁R1，因T1已封锁了R1，T2也只能等候T1释放R1上锁这么T1在等候T2，而T2又在等候T1，T1和T2两个事务永远不能结束，形成死锁

并发控制第36页死锁（续）T1T2lockR1••LockR2••LockR2.•等候•等候LockR1等候等候等候等候•死锁并发控制第37页处理死锁方法两类方法1.预防死锁2.死锁诊疗与解除并发控制第38页1.死锁预防产生死锁原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其它事务封锁数据对象加锁，从而出现死等候。预防死锁发生就是要破坏产生死锁条件并发控制第39页死锁预防（续）预防死锁方法一次封锁法次序封锁法并发控制第40页(1)一次封锁法要求每个事务必须一次将全部要使用数据全部加锁，不然就不能继续执行存在问题降低系统并发度难于事先准确确定封锁对象并发控制第41页(2)次序封锁法次序封锁法是预先对数据对象要求一个封锁次序，全部事务都按这个次序实施封锁。次序封锁法存在问题维护成本数据库系统中封锁数据对象极多，而且在不停地改变。难以实现：极难事先确定每一个事务要封锁哪些对象

并发控制第42页死锁预防（续）结论在操作系统中广为采取预防死锁策略并不很适合数据库特点DBMS在处理死锁问题上更普遍采取是诊疗并解除死锁方法并发控制第43页2.死锁诊疗与解除死锁诊疗超时法事务等候图法并发控制第44页(1)超时法假如一个事务等候时间超出了要求时限，就认为发生了死锁优点：实现简单缺点有可能误判死锁时限若设置得太长，死锁发生后不能及时发觉并发控制第45页(2)等候图法用事务等候图动态反应全部事务等候情况事务等候图是一个有向图G=(T，U)T为结点集合，每个结点表示正运行事务U为边集合，每条边表示事务等候情况若T1等候T2，则T1，T2之间划一条有向边，从T1指向T2并发控制第46页等候图法（续）事务等候图图(a)中，事务T1等候T2，T2等候T1，产生了死锁图(b)中，事务T1等候T2，T2等候T3，T3等候T4，T4又等候T1，产生了死锁图(b)中，事务T3可能还等候T2，在大回路中又有小回路

并发控制第47页等候图法（续）并发控制子系统周期性地（比如每隔数秒）生成事务等候图，检测事务。假如发觉图中存在回路，则表示系统中出现了死锁。并发控制第48页死锁诊疗与解除（续）解除死锁选择一个处理死锁代价最小事务，将其撤消释放此事务持有全部锁，使其它事务能继续运行下去并发控制第49页五、并发调度可串行性DBMS对并发事务不一样调度可能会产生不一样结果什么样调度是正确？

并发控制第50页1、可串行化调度可串行化(Serializable)调度多个事务并发执行是正确，当且仅当其结果与按某一次序串行地执行这些事务时结果相同可串行性(Serializability)是并发事务正确调度准则一个给定并发调度，当且仅当它是可串行化，才认为是正确调度并发控制第51页可串行化调度（续）[例]现在有两个事务，分别包含以下操作：事务T1：读B；A=B+1；写回A事务T2：读A；B=A+1；写回B现给出对这两个事务不一样调度策略并发控制第52页串行化调度,正确调度T1T2SlockBY=R(B)=2UnlockBXlockAA=Y+1=3W(A)UnlockASlockAX=R(A)=3UnlockAXlockBB=X+1=4W(B)UnlockB串行调度(a)假设A、B初值均为2。按T1→T2次序执行结果为A=3，B=4串行调度策略,正确调度并发控制第53页串行化调度,正确调度T1T2SlockAX=R(A)=2UnlockAXlockBB=X+1=3W(B)UnlockBSlockBY=R(B)=3UnlockBXlockAA=Y+1=4W(A)UnlockA串行调度(b)假设A、B初值均为2。T2→T1次序执行结果为B=3，A=4

串行调度策略,正确调度并发控制第54页不可串行化调度，错误调度T1T2SlockBY=R(B)=2SlockAX=R(A)=2UnlockBUnlockAXlockAA=Y+1=3W(A)XlockBB=X+1=3W(B)UnlockAUnlockB不可串行化调度

执行结果与(a)、(b)结果都不一样是错误调度并发控制第55页可串行化调度，正确调度T1T2SlockBY=R(B)=2UnlockBXlockASlockAA=Y+1=3等候W(A)等候UnlockA等候X=R(A)=3UnlockAXlockBB=X+1=4W(B)UnlockB可串行化调度

执行结果与串行调度(a)执行结果相同是正确调度并发控制第56页2冲突可串行化调度可串行化调度充分条件一个调度Sc在确保冲突操作次序不变情况下，经过交换两个事务不冲突操作次序得到另一个调度Sc‘，假如Sc’是串行，称调度Sc为冲突可串行化调度一个调度是冲突可串行化，一定是可串行化调度并发控制第57页冲突可串行化调度（续）冲突操作冲突操作是指不一样事务对同一个数据读写操作和写写操作Ri(x)与Wj(x) /*事务Ti读x，Tj写x*/Wi(x)与Wj(x) /*事务Ti写x，Tj写x*/其它操作是不冲突操作不一样事务冲突操作和同一事务两个操作不能交换(Swap)并发控制第58页冲突可串行化调度（续）［例］今有调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)把w2(A)与r1(B)w1(B)交换，得到：r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)再把r2(A)与r1(B)w1(B)交换：Sc2＝r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)Sc2等价于一个串行调度T1，T2，Sc1冲突可串行化调度并发控制第59页冲突可串行化调度（续）冲突可串行化调度是可串行化调度充分条件，不是必要条件。还有不满足冲突可串行化条件可串行化调度。[例]有3个事务T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)调度L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)是一个串行调度。调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。不过调度L2是可串行化，因为L2执行结果与调度L1相同，Y值都等于T2值，X值都等于T3值并发控制第60页六、两段锁协议封锁协议利用封锁方法时，对数据对象加锁时需要约定一些规则何时申请封锁持锁时间何时释放封锁等两段封锁协议(Two-PhaseLocking，简称2PL)是最惯用一个封锁协议，理论上证实使用两段封锁协议产生是可串行化调度并发控制第61页两段锁协议（续）两段锁协议指全部事务必须分两个阶段对数据项加锁和解锁

在对任何数据进行读、写操作之前，事务首先要取得对该数据封锁在释放一个封锁之后，事务不再申请和取得任何其它封锁并发控制第62页两段锁协议（续）“两段”锁含义事务分为两个阶段第一阶段是取得封锁，也称为扩展阶段事务能够申请取得任何数据项上任何类型锁，不过不能释放任何锁第二阶段是释放封锁，也称为收缩阶段事务能够释放任何数据项上任何类型锁，不过不能再申请任何锁并发控制第63页两段锁协议（续）例事务Ti恪守两段锁协议，其封锁序列是：SlockASlockBXlockCUnlockBUnlockAUnlockC；|← 扩展阶段 →| |← 收缩阶段→|事务Tj不恪守两段锁协议，其封锁序列是：

SlockAUnlockASlockBXlockCUnlockCUnlockB；并发控制第64页两段锁协议（续）事务T1事务T2Slock(A)R(A=260)Slock(C)R(C=300)Xlock(A)W(A=160)Xlock(C)W(C=250)Slock(A)Slock(B)等候R(B=1000)等候Xlock(B)等候W(B=1100)等候Unlock(A)等候R(A=160)Xlock(A)Unlock(B)W(A=210)Unlock(C)恪守两段锁协议可串行化调度左图调度是恪守两段锁协议，所以一定是一个可串行化调度。并发控制第65页两段锁协议（续）事务恪守两段锁协议是可串行化调度充分条件，而不是必要条件。若并发事务都恪守两段锁协议，则对这些事务任何并发调度策略都是可串行化若并发事务一个调度是可串行化，不一定全部事务都符合两段锁协议并发控制第66页两段锁协议（续）两段锁协议与预防死锁一次封锁法一次封锁法要求每个事务必须一次将全部要使用数据全部加锁，不然就不能继续执行，所以一次封锁法恪守两段锁协议不过两段锁协议并不要求事务必须一次将全部要使用数据全部加锁，所以恪守两段锁协议事务可能发生死锁并发控制第67页两段锁协议（续）[例]恪守两段锁协议事务发生死锁T1SlockBR(B)=2

XlockA等候等候T2

SlockAR(A)=2

XlockA等候恪守两段锁协议事务可能发生死锁

并发控制第68页七、封锁粒度封锁对象大小称为封锁粒度(Granularity)封锁对象：逻辑单元，物理单元例：在关系数据库中，封锁对象：逻辑单元:属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等物理单元：页（数据页或索引页）、物理统计等并发控制第69页选择封锁粒度标准封锁粒度与系统并发度和并发控制开销亲密相关。封锁粒度越大，数据库所能够封锁数据单元就越少，并发度就越小，系统开销也越小；封锁粒度越小，并发度较高，但系统开销也就越大并发控制第70页选择封锁粒度标准（续）例若封锁粒度是数据页，事务T1需要修改元组L1，则T1必须对包含L1整个数据页A加锁。假如T1对A加锁后事务T2要修改A中元组L2，则T2被迫等候，直到T1释放A。假如封锁粒度是元组，则T1和T2能够同时对L1和L2加锁，不需要相互等候，提升了系统并行度。又如，事务T需要读取整个表，若封锁粒度是元组，T必须对表中每一个元组加锁，开销极大并发控制第71页选择封锁粒度标准（续）多粒度封锁(MultipleGranularityLocking)在一个系统中同时支持各种封锁粒度供不一样事务选择选择封锁粒度同时考虑封锁开销和并发度两个原因，适当选择封锁粒度需要处理多个关系大量元组用户事务：以数据库为封锁单位需要处理大量元组用户事务：以关系为封锁单元只处理少许元组用户事务：以元组为封锁单位并发控制第72页1、多粒度封锁多粒度树以树形结构来表示多级封锁粒度根结点是整个数据库，表示最大数据粒度叶结点表示最小数据粒度

并发控制第73页多粒度封锁（续）例：三级粒度树。根结点为数据库，数据库子结点为关系，关系子结点为元组。数据库关系Rn关系R1元组元组元组元组………………三级粒度树并发控制第74页多粒度封锁协议允许多粒度树中每个结点被独立地加锁对一个结点加锁意味着这个结点全部后代结点也被加以一样类型锁在多粒度封锁中一个数据对象可能以两种方式封锁：显式封锁和隐式封锁并发控制第75页显式封锁和隐式封锁显式封锁:直接加到数据对象上封锁隐式封锁:该数据对象没有独立加锁，是因为其上级结点加锁而使该数据对象加上了锁显式封锁和隐式封锁效果是一样并发控制第76页显式封锁和隐式封锁（续）系统检验封锁冲突时要检验显式封锁还要检验隐式封锁比如事务T要对关系R1加X锁系统必须搜索其上级结点数据库、关系R1还要搜索R1下级结点，即R1中每一个元组假如其中某一个数据对象已经加了不相容锁，则T必须等候

并发控制第77页显式封锁和隐式封锁（续）对某个数据对象加锁，系统要检验

该数据对象有没有显式封锁与之冲突

全部上级结点检验本事务显式封锁是否与该数据对象上隐式封锁冲突：(由上级结点已加封锁造成）全部下级结点看上面显式封锁是否与本事务隐式封锁（将加到下级结点封锁）冲突并发控制第78页2、意向锁引进意向锁（intentionlock）目标提升对某个数据对象加锁时系统检验效率并发控制第79页意向锁(续)假如对一个结点加意向锁，则说明该结点下层结点正在被加锁对任一结点加基本锁，必须先对它上层结点加意向锁比如，对任一元组加锁时，必须先对它所在数据库和关系加意向锁并发控