数据库系统概论并发控制

数据库系统概论并发控制数据库系统概论1第1页，共50页，2023年，2月20日，星期六数据库系统概论27.1事务的基本概念一、什么是事务二、如何定义事务三、事务的特性第2页，共50页，2023年，2月20日，星期六数据库系统概论3一、什么是事务事务(Transaction)是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位事务和程序是两个概念在关系数据库中，一个事务可以是一条SQL语句，一组SQL语句或整个程序一个应用程序通常包含多个事务事务是恢复和并发控制的基本单位第3页，共50页，2023年，2月20日，星期六数据库系统概论4二、如何定义事务显式定义方式

BEGINTRANSACTIONBEGINTRANSACTIONSQL语句1SQL语句1

SQL语句2SQL语句2

。。。。。。。。。。

COMMITROLLBACK隐式方式当用户没有显式地定义事务时，DBMS按缺省规定自动划分事务第4页，共50页，2023年，2月20日，星期六数据库系统概论5事务结束COMMIT事务正常结束提交事务的所有操作（读+更新）事务中所有对数据库的更新永久生效ROLLBACK事务异常终止事务运行的过程中发生了故障，不能继续执行回滚事务的所有更新操作事务滚回到开始时的状态第5页，共50页，2023年，2月20日，星期六数据库系统概论6三、事务的特性(ACID特性)事务的ACID特性：原子性（Atomicity）一致性（Consistency）隔离性（Isolation）持续性（Durability）第6页，共50页，2023年，2月20日，星期六数据库系统概论71.原子性事务是数据库的逻辑工作单位事务中包括的诸操作要么都做，要么都不做第7页，共50页，2023年，2月20日，星期六数据库系统概论82.一致性事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态一致性状态：数据库中只包含成功事务提交的结果不一致状态：数据库中包含失败事务的结果第8页，共50页，2023年，2月20日，星期六数据库系统概论9一致性与原子性银行转帐：从帐号A中取出一万元，存入帐号B。定义一个事务，该事务包括两个操作这两个操作要么全做，要么全不做全做或者全不做，数据库都处于一致性状态。如果只做一个操作，数据库就处于不一致性状态。

B=B+1

A=A-1BA第9页，共50页，2023年，2月20日，星期六数据库系统概论103.隔离性对并发执行而言一个事务的执行不能被其他事务干扰一个事务内部的操作及使用的数据对其他并发事务是隔离的并发执行的各个事务之间不能互相干扰第10页，共50页，2023年，2月20日，星期六数据库系统概论11T1的修改被T2覆盖了！

读A=16

A←A-3写回A=13①读A=16

②

③A←A-1

写回A=15

④T2T1第11页，共50页，2023年，2月20日，星期六数据库系统概论124.持续性持续性也称永久性（Permanence）一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其执行结果有任何影响。第12页，共50页，2023年，2月20日，星期六数据库系统概论13事务的特性保证事务ACID特性是事务处理的任务破坏事务ACID特性的因素多个事务并行运行时，不同事务的操作交叉执行事务在运行过程中被强行停止第13页，共50页，2023年，2月20日，星期六数据库系统概论14内容提要并发控制是数据库管理系统的重要组成部分，通过本章的学习，应重点掌握：并发控制带来的新问题封锁及封锁协议并发调度的可串行性两段锁协议第14页，共50页，2023年，2月20日，星期六数据库系统概论15概述在单处理机系统中，事务的并行执行实际上是这些并行事务的并行操作轮流交叉运行，称为交叉并发方式。在多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行，称为同时并发方式。并发的目的：改善系统的资源利用率改善短事务的响应时间第15页，共50页，2023年，2月20日，星期六数据库系统概论16例子飞机订票系统中的活动序列：①甲售票点读出某航班的机票余额A，设A=16②乙售票点读出同一航班的机票余额A，也为16③甲售票点卖出一张机票，修改余额A←A-1，把A=15写回数据库④乙售票点也卖出一张机票，修改余额A←A-1，把A=15写回数据库这种情况称为数据库的不一致性，是由并发控制引起的。第16页，共50页，2023年，2月20日，星期六数据库系统概论17数据不一致性（1）丢失修改：两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。“写—写冲突”读“脏”数据：事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为“脏”数据，即不正确的数据。“读—写冲突”第17页，共50页，2023年，2月20日，星期六数据库系统概论18数据不一致性（2）不可重复读：事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次的读取结果。“读—写冲突”产生原因：并发操作破坏了事务的隔离性并发控制的任务：用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，避免造成数据的不一致性。并发控制的主要方法：封锁第18页，共50页，2023年，2月20日，星期六数据库系统概论19三种数据不一致性T1T2T1T2T1T2读A=16读A=50读B=100求和=150读C=100C←C*2写C=200读A=16读B=100B←B*2写B=200读C=200A←A-1写A=15读A=50读B=200求和=250ROLLBACKC=100A←A-1写A=15第19页，共50页，2023年，2月20日，星期六数据库系统概论20封锁（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锁。第20页，共50页，2023年，2月20日，星期六数据库系统概论21封锁（Locking）(2)X锁和S锁的控制方式可有相容矩阵表示。最左边表示T1已经获得的锁的类型，最上面表示T2的封锁请求,-表示没有加锁。Y表示相容，请求可以满足；N表示冲突，请求被拒绝。T1T2XS-XNNYSNYY-YYY第21页，共50页，2023年，2月20日，星期六数据库系统概论22一级封锁协议加锁必须遵守一定的规则，称为封锁协议。一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。一级封锁协议中，如果是读数据不修改，是不需要加锁的，可防止丢失修改。第22页，共50页，2023年，2月20日，星期六数据库系统概论23二级封锁协议二级封锁协议：在一级封锁协议基础上，加上事务T在读数据R之前必须先对其加上S锁，读完后即可释放S锁。在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。第23页，共50页，2023年，2月20日，星期六数据库系统概论24三级封锁协议三级封锁协议：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。三级封锁协议除了防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。上述三级协议的主要区别在于：什么操作需要申请封锁，以及何时释放锁。第24页，共50页，2023年，2月20日，星期六数据库系统概论25不同级别的封锁协议X锁S锁一致性保证操作结束释放事务结束释放操作结束释放事务结束释放不丢失修改不读脏数据可重复读一级封锁协议√√二级封锁协议√√√√三级封锁协议√√√√√第25页，共50页，2023年，2月20日，星期六数据库系统概论26活锁若某数据对象加了S锁，这时若有其它事务申请对它的X锁，则需等待。但此时若有其它事务申请对它的S锁，按相容矩阵，应可获准。如果不断有事务申请对此数据对象的S锁，以致它始终被S锁占有，而X锁的申请迟迟不能获准。这种现象叫活锁。避免活锁的简单方法是采用“先来先服务”的策略。第26页，共50页，2023年，2月20日，星期六数据库系统概论27死锁一个事务如果申请锁而未获准，则需等待其它事务释放锁。如果事务中出现循环等待时，如果不加干预，则会一直等待下去，这叫死锁。对付死锁的方法：检测死锁，发现死锁后处理死锁防止死锁第27页，共50页，2023年，2月20日，星期六数据库系统概论28死锁的诊断（1）超时法：如果一个事务的等待时间超过了某个时限，就认为发生死锁。特点：优点：简单缺点：一是事务因其它原因（如系统负荷太重、通信受阻等）而使事务等待时间超过时限，可能被误判死锁。二是时限的设置。第28页，共50页，2023年，2月20日，星期六数据库系统概论29死锁的诊断（2）等待图法：等待图是一个有向图G=(T,U)。T为结点的集合，每个结点表示正在运行的事务U为边的集合，每条边表示事务等待的情况当且仅当等待图中出现回路时，死锁发生。当运行的事务比较多时，维护等待图和检测回路的开销较大，影响系统的性能。方法是周期性的进行死锁检测。死锁检测周期的确定用实验方法确定最佳值。

第29页，共50页，2023年，2月20日，星期六数据库系统概论30死锁的解除（1）出现死锁后，必须由DBMS干预。处理如下：在循环等待的事务中，选一个事务作为“牺牲者”，给其它事务让路撤销牺牲的事务，释放其获得的锁及其它资源将释放的锁让给等待它的事务被牺牲的事务可以有两种处理：发消息给有关用户，由用户向系统再交付该事务由DBMS重新启动该事务注：被牺牲的事务应等待一段时间才能交付系统，否则可能再发生死锁。第30页，共50页，2023年，2月20日，星期六数据库系统概论31死锁的解除（2）选择哪个事务作为牺牲者，由下列几种选法：选择最迟交付的事务作为牺牲者选择获得锁最少的事务作为牺牲者选择撤销代价最小的事务作为牺牲者第31页，共50页，2023年，2月20日，星期六数据库系统概论32死锁的预防—一次封锁法一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁。缺点：有些数据对象过早的加锁，降低了并发度如果有些事务需要访问的“热点”数据比较多，其它事务总是不断的占有其中某些数据，不能一次获得所需要数据的全部，就会一直等待下去，易发生活锁。第32页，共50页，2023年，2月20日，星期六数据库系统概论33死锁的预防—顺序封锁法顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。缺点：数据库中一般是按内容访问，而不是按名访问，所以很难预先确定所有的访问对象数据经常变动，次序也经常调整上述两种方法用于数据库系统不实际。第33页，共50页，2023年，2月20日，星期六数据库系统概论34死锁的预防—事务重执（1）事务重执：当事务申请锁而未获准时，不是一律等待，而是让一些事务撤销重执。为区别事务开始执行的先后，每个事务开始执行时，赋予一个唯一的、随时间增长的整数，称为时间标记，记为ts。如两个事务TA和TB，若ts（TA）<ts（TB），表明TA比TB“年老”事务重执有两种策略等待—死亡策略击伤—等待策略第34页，共50页，2023年，2月20日，星期六数据库系统概论35死锁的预防—事务重执（2）等待—死亡策略设TB持有某对象数据的锁，当TA申请同一数据的锁发生冲突时，按如下规则处理：Ifts(TA)<ts(TB)thenTAwaits;else{rollbackTA；/*die*/restratTAwiththesamets(TA);}总是年老的事务等待年轻的事务。第35页，共50页，2023年，2月20日，星期六数据库系统概论36死锁的预防—事务重执（3）击伤—等待策略设TB持有某对象数据的锁，当TA申请同一数据的锁发生冲突时，按如下规则处理：Ifts(TA)>ts(TB)thenTAwaits;else{rollbackTB；/*wound*/restratTBwiththesamets(TB);}总是年轻的事务等待年老的事务。第36页，共50页，2023年，2月20日，星期六数据库系统概论37死锁的预防—事务重执（4）上述两种策略中，当冲突发生时，总是以年轻的事务作为牺牲品。因为年轻的事务随着时间的流逝，总会变成年老的事务，不致永远成为牺牲品。第37页，共50页，2023年，2月20日，星期六数据库系统概论38并发调度的可串行性（1）定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为可串行化的调度。可串行性是并发事务正确性的准则。按这个规则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。对于n个事务，可有n!中排列次序，即有n!种串行调度。第38页，共50页，2023年，2月20日，星期六数据库系统概论39并发调度的可串行性（2）一个调度S是否可串行化，可用前趋图来测试。前趋图是有向图，点表示所有参与调度的事务对于边，当满足下列条件之一时，加入：Ri(x)在Wj(x)之前Wi(x)在Rj(x)之前Wi(x)在Wj(x)之前若前趋图中有回路，则S显然不等价于任何串行调度，若无回路，则可用拓扑排序得到一个串行调度。第39页，共50页，2023年，2月20日，星期六数据库系统概论40并发调度的可串行性（3）设有事务集{T1,T2,T3,T4}的一个调度：

S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)试检验S是否可串行化。分别分析对x,y,z的所有操作，画出前趋图。

T2

T1T4T1,T3,T2,T4T3第40页，共50页，2023年，2月20日，星期六数据库系统概论41并发调度的可串行性（4）可串行化调度和串行调度是有区别的：前者交叉执行各事务操作，在效果上相当于事务的某一串行执行后者完全是串行执行各事务，失去并发意义，不能充分利用系统资源DBMS并发控制的任务就是保证事务执行的可串行化，比较有效的方法是要求DBMS按一定的封锁协议调度事务，以保证其执行可串行化。两段锁协议（2PL）就是保证并发调度可串行化的封锁协议。第41页，共50页，2023年，2月20日，星期六数据库系统概论42两段锁协议（1）两段锁协议是指所有事务必须分两个阶段对是数据项加锁和解锁在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁。——扩展阶段在释放一个封锁之后，事物不再申请和获得任何其它封锁。——收缩阶段若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都可是可串行化。（充分条件）（可用反证法证明）第42页，共50页，2023年，2月20日，星期六数据库系统概论43两段锁协议（2）两段锁协议和一次封锁法的异同：一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此可能会发生死锁第43页，共50页，2023年，2月20日，星期六数据库系统概论44封锁的粒度定义：封锁对象的大小。封锁的对象：可以是逻辑单元：属性、属性值的集合、元组、关系、索引项、整个索引、整个数据库也可以是物理单元：页（数据页或索引页）、块封锁粒度一系统的并发度和并发控制开销相关封锁粒度越大，并发度越小，系统开销越小封锁粒度越小，并发度较高，系统开销越大第44页，共50页，2023年，2月20日，星期六数据库系统概论45多粒度封锁如果在一个系统中同时支持多种封锁粒度供不同的事务选择，这种封锁方法称为多粒度封锁多粒度封锁，一个数据对象可能以两种方式被封锁：显式封锁：应事务的要求直接加锁于该数据对象隐式封锁：该数据对象没有加锁，而是由于它的上级被封锁，应此这个数据对象被隐含地封锁了为了方便加锁引起的冲突，引进了意向锁（INTENTION

LOCK）第45页，共50页，2023年，2月20日，星期六数据库系统概论46意向锁（1）含义：如果对一个结点加意向锁，则说明该结点的下级结点正在被加锁；对任一结点加锁时必须先对其上级结点加意向锁。意向共享锁(IS)：如果对一个数据对象加IS锁，表示它的后裔结点加了或拟（意向）加S锁意向排它锁(IX)：如果对一个数据对象加IX锁，表示它的后裔结点加了或拟（意向）加X锁共享意向排它锁(SIX)：如果对一个数据对象加SIX锁，表示它加了S锁，再加IX锁。即SIX=S+IX。如读整个关系，修改其中元组，则该关系加SIX锁第46页，共50页，2023年，2月20日，星期六数据库系统概论47意向锁（2）各种锁的相容矩阵T1T2SXISIXSIX-SYNY