,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据库系统概论,*,数据库系统概论,并发控制,1,数据库系统概论,数据库系统概论并发控制1数据库系统概论,内容提要,并发控制是数据库管理系统的重要组成部分，通过本章的学习，应重点掌握：,并发控制带来的新问题,封锁及封锁协议,并发调度的可串行性,两段锁协议,2,数据库系统概论,内容提要并发控制是数据库管理系统的重要组成部分，通过本章的学,概述,在单处理机系统中，事务的并行执行实际上是这些并行事务的并行操作轮流交叉运行，称为,交叉并发方式。,在多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行，称为,同时并发方式。,并发的目的：,改善系统的资源利用率,改善短事务的响应时间,3,数据库系统概论,概述在单处理机系统中，事务的并行执行实际上是这些并行事务的并,例子,飞机订票系统中的活动序列：,甲售票点读出某航班的机票余额,A，,设,A=16,乙售票点读出同一航班的机票余额,A，,也为,16,甲售票点卖出一张机票，修改余额,AA-1，,把,A=15,写回数据库,乙售票点也卖出一张机票，修改余额,AA-1，,把,A=15,写回数据库,这种情况称为数据库的不一致性，是由并发控制引起的。,4,数据库系统概论,例子飞机订票系统中的活动序列：4数据库系统概论,数据不一致性（1）,丢失修改：,两个事务,T1,和,T2,读入同一数据并修改，,T2,提交的结果破坏了,T1,提交的结果，导致,T1,的修改被丢失。,“写写冲突”,读“脏”数据：,事务,T1,修改某一数据，并将其写回磁盘，事务,T2,读取同一数据后，,T1,由于某种原因被撤销，这时,T1,已修改过的数据恢复原值，,T2,读到的数据就与数据库中的数据不一致，则,T2,读到的数据就为“脏”数据，即不正确的数据。,“读写冲突”,5,数据库系统概论,数据不一致性（1）丢失修改：两个事务T1和T2读入同一数据并,数据不一致性（2）,不可重复读：,事务,T1,读取数据后，事务,T2,执行更新操作，使,T1,无法再现前一次的读取结果。,“读写冲突”,产生原因：并发操作破坏了事务的隔离性,并发控制的任务：用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，避免造成数据的不一致性。,并发控制的主要方法：封锁,6,数据库系统概论,数据不一致性（2）不可重复读：事务T1读取数据后，事务T2执,三种数据不一致性,T1,T2,T1,T2,T1,T2,读,A=16,读,A=50,读,B=100,求和=150,读,C=100 CC*2,写,C=200,读,A=16,读,B=100,BB*2,写,B=200,读,C=200,AA-1,写,A=15,读,A=50,读,B=200,求和=250,ROLLBACK,C=100,AA-1,写,A=15,7,数据库系统概论,三种数据不一致性T1T2T1T2T1T2读A=16读A=50,封锁（Locking）(1),封锁：事务,T,在对某个数据对象操作之前，先向系统发出请求，对其加锁。,封锁类型：排它锁（,X,锁）和共享锁（,S,锁）,排它锁：又称写锁，若事务,T,对数据对象,A,加上,X,锁，则只允许,T,读取和修改,A，,其它任何事务都不能再对,A,加任何类型的锁，直到,T,释放,A,上的,X,锁。,共享锁：又称读锁，若事务,T,对数据对象,A,加上,S,锁，则事务,T,可以读,A,但不能修改,A，,其它事务只能再对,A,加,S,锁，而不能加,X,锁，直到,T,释放,A,上的,S,锁。,8,数据库系统概论,封锁（Locking）(1)封锁：事务T在对某个数据对象操作,封锁（Locking）(2),X,锁和,S,锁的控制方式可有相容矩阵表示。,最左边表示,T1,已经获得的锁的类型，最上面表示,T2,的封锁请求,-表示没有加锁。,Y,表示相容，请求可以满足；,N,表示冲突，请求被拒绝。,T1 T2,X,S,-,X,N,N,Y,S,N,Y,Y,-,Y,Y,Y,9,数据库系统概论,封锁（Locking）(2)X锁和S锁的控制方式可有相容矩阵,一级封锁协议,加锁必须遵守一定的规则，称为封锁协议。,一级封锁协议：,事务,T,在修改数据,R,之前必须先对其加,X,锁，直到事务结束才释放。事务结束包括正常结束（,COMMIT）,和非正常结束（,ROLLBACK）。,一级封锁协议中，如果是读数据不修改，是不需要加锁的，可防止丢失修改。,10,数据库系统概论,一级封锁协议加锁必须遵守一定的规则，称为封锁协议。10数据库,二级封锁协议,二级封锁协议：,在一级封锁协议基础上，加上事务,T,在读数据,R,之前必须先对其加上,S,锁，读完后即可释放,S,锁。,在二级封锁协议中，由于读完数据后即可释放,S,锁，所以它不能保证可重复读。,11,数据库系统概论,二级封锁协议二级封锁协议：在一级封锁协议基础上，加上事务T在,三级封锁协议,三级封锁协议：,一级封锁协议加上事务,T,在读取数据,R,之前必须先对其加,S,锁，直到事务结束才释放。,三级封锁协议除了防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。,上述三级协议的主要区别在于：什么操作需要申请封锁，以及何时释放锁。,12,数据库系统概论,三级封锁协议三级封锁协议：一级封锁协议加上事务T在读取数据R,不同级别的封锁协议,X,锁,S,锁,一致性保证,操作结束释放,事务结束释放,操作结束释放,事务结束释放,不丢失修改,不读脏数据,可重复读,一级封锁协议,二级封锁协议,三级封锁协议,13,数据库系统概论,不同级别的封锁协议X锁S锁一致性保证操作结束释放事务结束释放,活锁,若某数据对象加了,S,锁，这时若有其它事务申请对它的,X,锁，则需等待。但此时若有其它事务申请对它的,S,锁，按相容矩阵，应可获准。如果不断有事务申请对此数据对象的,S,锁，以致它始终被,S,锁占有，而,X,锁的申请迟迟不能获准。这种现象叫,活锁。,避免活锁的简单方法是采用,“先来先服务”,的策略。,14,数据库系统概论,活锁若某数据对象加了S锁，这时若有其它事务申请对它的X锁，则,死锁,一个事务如果申请锁而未获准，则需等待其它事务释放锁。如果事务中出现循环等待时，如果不加干预，则会一直等待下去，这叫,死锁。,对付死锁的方法：,检测死锁，发现死锁后处理死锁,防止死锁,15,数据库系统概论,死锁一个事务如果申请锁而未获准，则需等待其它事务释放锁。如果,死锁的诊断（1）,超时法：如果一个事务的等待时间超过了某个时限，就认为发生死锁。,特点：,优点：简单,缺点：一是事务因其它原因（如系统负荷太重、通信受阻等）而使事务等待时间超过时限，可能被误判死锁。二是时限的设置。,16,数据库系统概论,死锁的诊断（1）超时法：如果一个事务的等待时间超过了某个时限,死锁的诊断（2）,等待图法：等待图是一个有向图,G=(T,U)。,T,为结点的集合，每个结点表示正在运行的事务,U,为边的集合，每条边表示事务等待的情况,当且仅当等待图中出现回路时，死锁发生。,当运行的事务比较多时，维护等待图和检测回路的开销较大，影响系统的性能。,方法是周期性的进行死锁检测。死锁检测周期的确定用实验方法确定最佳值,。,17,数据库系统概论,死锁的诊断（2）等待图法：等待图是一个有向图G=(T,U)。,死锁的解除（1）,出现死锁后，必须由,DBMS,干预。处理如下：,在循环等待的事务中，选一个事务作为“牺牲者”，给其它事务让路,撤销牺牲的事务，释放其获得的锁及其它资源,将释放的锁让给等待它的事务,被牺牲的事务可以有两种处理：,发消息给有关用户，由用户向系统再交付该事务,由,DBMS,重新启动该事务,注：被牺牲的事务应等待一段时间才能交付系统，否则可能再发生死锁。,18,数据库系统概论,死锁的解除（1）出现死锁后，必须由DBMS干预。处理如下：1,死锁的解除（2）,选择哪个事务作为牺牲者，由下列几种选法：,选择最迟交付的事务作为牺牲者,选择获得锁最少的事务作为牺牲者,选择撤销代价最小的事务作为牺牲者,19,数据库系统概论,死锁的解除（2）选择哪个事务作为牺牲者，由下列几种选法：19,死锁的预防一次封锁法,一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁。,缺点：,有些数据对象过早的加锁，降低了并发度,如果有些事务需要访问的“热点”数据比较多，其它事务总是不断的占有其中某些数据，不能一次获得所需要数据的全部，就会一直等待下去，易发生活锁。,20,数据库系统概论,死锁的预防一次封锁法一次封锁法：要求每个事务必须一次将所有,死锁的预防顺序封锁法,顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。,缺点：,数据库中一般是按内容访问，而不是按名访问，所以很难预先确定所有的访问对象,数据经常变动，次序也经常调整,上述两种方法用于数据库系统不实际。,21,数据库系统概论,死锁的预防顺序封锁法顺序封锁法：预先对数据对象规定一个封锁,死锁的预防事务重执（1）,事务重执：当事务申请锁而未获准时，不是一律等待，而是让一些事务撤销重执。,为区别事务开始执行的先后，每个事务开始执行时，赋予一个唯一的、随时间增长的整数，称为时间标记，记为,ts。,如两个事务,TA,和,TB，,若,ts（TA）ts（TB），,表明,TA,比,TB“,年老”,事务重执有两种策略,等待死亡策略,击伤等待策略,22,数据库系统概论,死锁的预防事务重执（1）事务重执：当事务申请锁而未获准时，,死锁的预防事务重执（2）,等待死亡策略,设,TB,持有某对象数据的锁，当,TA,申请同一数据的锁发生冲突时，按如下规则处理：,If ts(TA)ts(TB)then TA waits;,else,rollback TB；/*wound*/,restrat TB with the same ts(TB);,总是年轻的事务等待年老的事务。,24,数据库系统概论,死锁的预防事务重执（3）击伤等待策略24数据库系统概论,死锁的预防事务重执（4）,上述两种策略中，当冲突发生时，总是以年轻的事务作为牺牲品。因为年轻的事务随着时间的流逝，总会变成年老的事务，不致永远成为牺牲品。,25,数据库系统概论,死锁的预防事务重执（4）上述两种策略中，当冲突发生时，总是,并发调度的可串行性（1）,定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为,可串行化的调度。,可串行性是并发事务正确性的准则。按这个规则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是,正确调度。,对于,n,个事务，可有,n!,中排列次序，即有,n!,种串行调度。,26,数据库系统概论,并发调度的可串行性（1）定义：多个事务的并发执行是正确的，当,并发调度的可串行性（2）,一个调度,S,是否可串行化，可用前趋图来测试。前趋图是有向图，点表示所有参与调度的事务对于边，当满足下列条件之一时，加入：,R,i,(x),在,W,j,(x),之前,W,i,(x),在,R,j,(x),之前,W,i,(x),在,W,j,(x),之前,若前趋图中有回路，则,S,显然不等价于任何串行调度，若无回路，则可用拓扑排序得到一个串行调度。,27,数据库系统概论,并发调度的可串行性（2）一个调度S是否可串行化，可用前趋图来,并发调度的可串行性（3）,设有事务集,T1,T2,T3,T4,的一个调度：,S=W,3,(y)R,1,(x)R,2,(y)W,3,(x)W,2,(x)W,3,(z)R,4,(z)W,4,(x),试检验,S,是否可串行化。,分别分析对,x,y,z,的所有操作，画出前趋图。,T2,T1 T4 T1,T3,T2,T4,T3,28,数据库系统概论,并发调度的可串行性（3）设有事务集T1,T2,T3,T4,并发调度的可串行性（4）,可串行化调度和串行调度是有区别的：,前者交叉执行各事务操作，在效果上相当于事务的某