第八章 并发控制

第八章并发控制执行方式1.事务串行执行：即每个时刻只有一个事务运行，其他事物必须等到这个事务结束以后方能运行。2.单处理系统：并行事务的并行操作轮流交叉运行，称为交叉并发方式。3.多处理系统：真正的并发运行。同时并发方式在多处理系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行，这种并行方式称为同时并发方式。并发控制机制是衡量一个数据库管理系统性能的重要标志之一。第一节并发控制概述下面我们先来看一个例子，说明并发操作带来的数据的不一致性问题。考虑飞机订票系统中的一个活动序列：①售票点（甲事务）读出某航班的机票余额A，设A=16。②售票点（乙事务）读出同一航班的机票余额A，也为16。③售票点卖出一张机票，修改余额A←A-1。所以A为15，把A写回数据库。④售票点也卖出一张机票，修改余额A←A-1，所以A为15，把A写回数据库。结果明明卖出两张机票，数据库中机票余额只减少1。仔细分析并发操作带来的数据不一致性包括三类：1.丢失修改2.不可重复读3.读“脏”数据。1．丢失修改（LostUpdate）两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。上面飞机订票例子就属此类。2．不可重复读（Non-Repeatableread）不可重复读是指事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。具体地讲，不可重复读包括三种情况：⑴事务T1读取某一数据后，事务T2对其做了修改，当事务1再次读该数据时，得到与前一次不同的值。例如，T1读取B=100进行运算；T2读取同一数据B，对其进行修改后将B=200写回数据库；T1为了对读取值校对重读B，B已为200，与第一次读取值不一致。⑵事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录神秘地消失了。⑶事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。3．读“脏”数据（dirtyread）读“脏”数据是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤消，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为脏数据即不正确的数据。上述三类数据不一致性的主要原因并发操作破坏了事务的隔离性。解决方法：并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性。并发控制的主要技术是封锁（Locking）第二节封锁点击进入。第二节封锁封锁：是实现并发控制的一个非常重要的技术。封锁：所谓封锁，就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。基本的封锁类型有两种:排它锁(ExclusiveLocks，简记为X锁)；共享锁(ShareLocks，简记为S锁)。排它锁：排它锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其它事务在T释放A上的锁之前不能再读取和修改A。共享锁：共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A，但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其它事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。第三节封锁协议在运用X锁和S锁这两种基本封锁，对数据对象加锁时，还需要约定一些规则，例如应何时申请X锁或S锁、持锁时间、何时释放等。我们称这些规则为：封锁协议（LockingProtocol）。对封锁方式规定不同的规则，就形成了各种不同的封锁协议。下面介绍三级封锁协议。三级封锁协议对并发操作的不正确调度可能会带来丢失修改、不可重复读和读“脏”数据等不一致性问题，三级封锁协议分别在不同程度上解决了这一问题。为并发操作的正确调度提供一定的保证。不同级别的封锁协议达到的系统一致性级别是不同的。一、一级封锁协议一级封锁协议是：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。说明一级封锁协议可防止丢失修改，并保证事务T是可恢复的。在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。二、二级封锁协议二级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。说明二级封锁协议除防止了丢失修改，还可进一步防止读“脏”数据。三、三级封锁协议三级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。说明：三级封锁协议除防止了丢失修改和不读‘脏’数据外，还进一步防止了不可重复读。第四节活锁和死锁点击进入第四节活锁和死锁和操作系统一样，封锁的方法可能引起活锁和死锁。一．活锁活锁：如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求，......，T2有可能永远等待，这就是活锁的情形。避免活锁的简单方法避免活锁的简单方法是采用先来先服务的策略。二．死锁死锁：如果事务T1封锁了数据R1，T2封锁了数据R2，然后T1又请求封锁R2，因T2已封锁了R2，于是T1等待T2释放R2上的锁。接着T2又申请封锁R1，因T1已封锁了R1，T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。死锁的预防：在数据库中，产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已被其他事务封锁的数据对象加锁，从而出现死等待。防止死锁的发生其实就是要破坏产生死锁的条件。防止死锁的发生其实就是要破坏产生死锁的条件。预防死锁通常有两种方法：一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。一次封锁法虽然可以有效地防止死锁的发生。但也存在问题，一次就将以后要用到的全部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度。顺序封锁法顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。顺序封锁法可以有效地防止死锁，但也同样存在问题。事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象。因此也就很难按规定的顺序去施加封锁。可见，在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点，因此DBMS在解决死锁的问题上普遍采用的是诊断并解除死锁的方法。2.死锁的诊断与解除①超时法如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。超时法实现简单，但其不足也很明显。一、是有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会误认为发生了死锁。二、是时限若设置得太长，死锁发生后不能及时发现。②等待图法事务等待图是一个有向图G=(T,U)。T为结点的集合，每个结点表示正运行的事务；U为边的集合，每条边表示事务等待的情况。若T1等待T2,则T1、T2之间划一条有向边，从T1指向T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如每隔1分钟）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。检测解除系统中存在死锁DBMS的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务得以继续运行下去。当然，对撤消的事务所执行的数据修改操作必须加以恢复。第五节并发调度和可串行性点击进入第五节并发调度和可串行性计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能会产生不同的结果，那么哪个结果是正确的，哪个是不正确的呢？如果一个事务运行过程中没有其他事务同时运行，也就是说它没有受到其他事务的干扰，那么就可以认为该事务的运行结果是正常的或者预想的。正确的调度策略因此将所有事务串行起来的调度策略一定是正确的调度策略。虽然以不同的顺序串行执行事务可能会产生不同的结果，但由于不会将数据库置于不一致状态，所以都是正确的。定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。我们称这种调度策略为：可串行化（Serializable）的调度。例如，现在有两个事务，分别包含下列操作：事务T1：读B；A=B+1；写回A；事务T2：读A；B=A+1；写回B；假设A、B的初值均为2。按T1-T2的次序执行，结果为A=3,B=4；按T2-T1的次序执行，结果为B=3,A=4。图8.5给出了对这两个事务的几种不同的调度策略。(a)和(b)为两种不同的串行调度策略，虽然执行结果不同，但它们都是正确的调度。(c)中两个事务是交错执行的，由于其执行结果与(a)、(b)的结果都不同，所以是错误的调度。(d)中两个事务也是交错执行的，其执行结果与串行调度(a)的执行结果相同，所以是正确的调度。为了保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。目前DBMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。两段锁（Two-PhaseLocking，简称2PL）协议就是保证并发调度可串行性的封锁协议。除此之外还有其他一些方法，如时标方法、乐观方法等来保证调度的正确性。第六节两段锁协议点击进入第六节两段锁协议两段锁协议：所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁，在释放一个封锁之后，事务不再申请和获得任何其他封锁。所谓“两段”锁的含义是，事务分为两个阶段，第一阶段是获得封锁，也称为扩展阶段。这在阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。第二阶段是释放封锁，也称为收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。如事务T2不遵守两段锁协议，其封锁序列是：SlockA…UnlockA…SlockB…XlockC…UnlockC…UnlockB；可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。另外要注意两段锁协议和防止死锁的一次封锁法的异同之处。一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议；但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁，如图8.7所示。第七节封锁的粒度封锁的对象的大小称为封锁粒度（Granularity）。封锁的对象封锁的对象可以是逻辑单元，也可以是物理单元。以关系数据库为例，封锁对象可以是这样一些逻辑单元:属性值、属性值的集合、元组、关系、索引项、整个索引直至整个数据库；也可以是这样一些物理单元:页(数据页或索引页)、块等。封锁粒度与系统的并发度和并发控制的开销密切相关。直观地看，封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；反之，封锁的粒度越小，并发度较高，但系统开销也就越大。多粒度封锁因此,如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁（multiplegranularitylocking）。选择封锁粒度选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以求得最优的效果。一般说来，需要处理大量元组的事务可以以关系为封锁粒度；需要处理多个关系的大量元组的事务可以以数据库为封锁