第11章 并发控制——复习笔记

第11章 并发控制

复习笔记

一、并发控制概述

01并发控制的责任

事务是并发控制的基本单位，保证事务ACID特性是事务处理的重要任务，而事务ACID特性可能遭到破坏的原因之一是多个事务对数据库的并发操作造成的。为了保证事务的隔离性和一致性，DBMS需要对并发操作进行正确调度。这些就是数据库管理系统中并发控制机制的责任。

02数据不一致及其原因

并发操作带来的数据不一致性主要包括丢失修改、不可重复读和读“脏”数据。产生三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性。

并发控制的主要技术有封锁（Locking）、时间戳（Timestamp）和乐观控制法，商用的DBMS一般都采用封锁方法。

二、封锁

01定义

封锁是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T 就对该数据对象有了一定的控制，在事务T释放它的锁之前，其他事务不能更新此数据对象。

02分类

基本的封锁类型有两种：排他锁（exclusive locks，简称X锁）和共享锁（sharelocks，简称S锁）。

（1）排他锁

排他锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁为止。

（2）共享锁

共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁为止。

排他锁与共享锁的控制方式可以用图11-1所示的相容矩阵（compatibility matrix）来表示。

图11-1 封锁类型的相容矩阵

三、封锁协议

01一级封锁协议

一级封锁协议是指事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMTT）和非正常结束（ROLLBACK）。一级封锁协议可防止丢失修改，并保证事务T是可恢复的。

02二级封锁协议

二级封锁协议是指在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S 锁，读完后即可释放S锁。二级封锁协议除防止了丢失修改，还可进一步防止读“脏”数据。

03三级封锁协议

三级封锁协议是指在一级封锁协议的基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。三级封锁协议除了防止丢失修改和读“脏”数据外，还进一步防止了不可重复读。

三级封锁协议可以总结为表11-1。

表11-1 不同级别的封锁协议和一致性保证

四、活锁和死锁

01活锁

（1）定义

如果事务T₁封锁了数据R，事务T₂又请求封锁R，于是T₂等待。T₃也请求封锁R，当T₁释放了R上的封锁之后系统首先批准了T₃的请求，T₂仍然等待。然后T₄又请求封锁R，当T₃释放了R上的封锁之后系统又批准了T₄的请求……T₂有可能永远等待，这就是活锁的情形，如图11-2所示。

图11-2 死锁与活锁示例

（2）避免的方法

避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。

02死锁

（1）定义

如果事务T₁封锁了数据R₁，T₂封锁了数据R₂，然后T₁又请求封锁R₂，因T₂已封锁了R₂，于是T₁等待T₂释放R₂上的锁；接着T₂又申请封锁R₁，因T₁已封锁了R₁，T₂也只能等待T₁释放R₁上的锁。

（2）避免的方法

在数据库中解决死锁问题主要有两类方法，一类方法是采取一定措施来预防死锁的发生，另一类方法是允许发生死锁，采用一定手段定期诊断系统中有无死锁，若有则解除之。

①死锁的预防

在数据库中，产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已被其他事务封锁的数据对象加锁，从而出现死等待。防止死锁的发生其实就是要破坏产生死锁的条件。预防死锁通常有以下两种方法。

a.一次封锁法

一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。一次封锁法虽然可以有效地防止死锁的发生，但也存在问题。

第一，一次就将以后要用到的全部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度；

第二，数据库中数据是不断变化的，原来不要求封锁的数据在执行过程中可能会变成封锁对象，所以很难事先精确地确定每个事务所要封锁的数据对象，为此只能扩大封锁范围，将事务在执行过程中可能要封锁的数据对象全部加锁，这就进一步降低了并发度。

b.顺序封锁法

顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。顺序封锁法可以有效地防止死锁，但也同样存在问题。

第一，数据库系统中封锁的数据对象极多，并且随数据的插入、删除等操作而不断地变化，要维护这样的资源的封锁顺序非常困难，成本很高。

第二，事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁。

②死锁的诊断与解除

数据库系统中诊断死锁的方法与操作系统类似，一般使用超时法或事务等待图法。

a.超时法

如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。超时法实现简单，但其不足也很明显。

第一，有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会误认为发生了死锁。

第二，时限若设置得太长，死锁发生后不能及时发现。

b.等待图法

事务等待图是一个有向图G=（T，U）。T为结点的集合，每个结点表示正运行的事务；U为边的集合，每条边表示事务等待的情况。若T₁等待T₂，则T₁，T₂之间划一条有向边，从T₁指向T₂。如图11-3所示。

图11-3 事务等待图

事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地生成事务等待图，并进行检测。如果发现图中存在回路，则表示系统中出现了死锁。

五、并发调度的可串行性

01可串行化调度

多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同，称这种调度策略为可串行化（serializable）调度。可串行性（serializability）是并发事务正确调度的准则。

02冲突可串行化调度

（1）冲突操作

冲突操作是指不同的事务对同一个数据的读写操作和写写操作，其他操作是不冲突操作。不同事务的冲突操作和同一事务的两个操作是不能交换（swap）的。

（2）冲突可串行调度

一个调度Sc在保证冲突操作的次序不变的情况F，通过交换两个事务不冲突操作的次序得到另一个调度Sc′，如果Sc′是串行的，称调度Sc为冲突可串行化的调度。若一个调度是冲突可串行化，则一定是可串行化的调度。

六、两段锁协议

为了保证并发调度的正确性，DBMS 的并发控制机制必须提供一定的手段来保证调度是可串行化的。目前DBMS 普遍采用两段锁（Two Phase Locking，简称2PL）协议的方法实现并发调度的可串行性，从而保证调度的正确性。

01定义

两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁；在释放一个封锁之后，事务不再申请和获得任何其他封锁。“两段”锁的含义是，事务分为两个阶段。第一阶段是获得封锁；第二阶段是释放封锁。

02两段锁协议和一次封锁法的异同点

（1）相同点

一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议。

（2）不同点

两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，遵守两段锁协议的事务可能发生死锁。

七、封锁的粒度

01封锁粒度

封锁对象的大小称为封锁粒度（Granularity）。封锁对象可以是逻辑单元，也可以是物理单元。

（1）封锁粒度与系统的关系

封锁粒度与系统的并发度和并发控制的开销密切相关。

①封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；

②封锁的粒度越小，并发度较高，但系统开销也就越大。

（2）粒度的选择

在一个系统中同时支持多种封锁粒度供不同的事务选择的封锁方法称为多粒度封锁。选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以求得最优的效果。

①需要处理大量元组的事务可以以关系为封锁粒度；

②需要处理多个关系的大量元组的事务可以以数据库为封锁粒度；③对于处理少量元组的用户事务，以元组为封锁粒度比较合适。

02多粒度封锁

（1）结构

多粒度树的根结点是整个数据库，表示最大的数据粒度。叶结点表示最小的数据粒度。如图11-4所示定义了一个三级多粒度树。

图11-4 三级粒度树

（2）显式封锁和隐式封锁

多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两种方式封锁，显式封锁和隐式封锁。

①显式封锁

显式封锁是应事务的要求直接加到数据对象上的封锁。

②隐式封锁

隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。

（3）检查封锁方法

系统检查封锁冲突时不仅要检查显式封锁还要检查隐式封锁。

①对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；

②检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁冲突；

③检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突。

03意向锁

如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁：对一结点加锁时，必须先对它的上层结点加意向锁。三种常用的意向锁包括意向共享锁（Intent Share Lock，简称IS锁）；意向排它锁（Intent Exclusive Lock，简称IX锁）；共享意向排它锁（Share Intent Exclusive Lock，简称SIX锁）。

（1）IS锁

如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。

（2）IX锁

如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。

（3）SIX锁

如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX。

如图11-5所示给出了这些锁的相容矩阵，从中可以发现这5种锁的强度如图11-5所示的偏序关系。锁的强度是指它对其他锁的排斥程度。

图11-5 加上意向锁之后锁的相容矩阵与偏序关系

申请封锁时应该按自上而下的次序进行，释放封锁时则应该按自下而上的次序进行。具有意向锁的多粒度封锁方法提高了系统的并发度，减少了加锁和解锁的开销。

八、其他并发控制机制

01时间戳方法

时间戳方法给每一个事务盖上一个时标，即事务开始执行的时间。每个事务具有唯一的时问戳，并按照这个时间戳来解决事务的冲突操作。如果发生冲突操作，就回滚具有较早时间戳的事务，以保证其他事务的正常执行，被回滚的事务被赋予新的时间戳并从头开始执行。

02乐观控制法

乐观控制法认为事务执行时很少发生冲突，因此不对事务进行特殊的管制，而是让它自由执行，事务提交前再进行正确性检查。如果检查后发现该事务执行中出现过冲突并影响了可串行性，则拒绝提交并回滚该事务。乐观控制法又被称为验证方法（certifier）。

03多版本控制

多版本并发控制（MultiVersion Concurrency Control，MVCC）是指在数据库中通过维护数据对象的多个版本信息来实现高效并发控制的种策略。

（1）多版本并发控制

版本（version）是指数据库中数据对象的一个快照，记录了数据对象某个时刻的状态。随着计算机系统存储设备价格的不断降低，可以考虑为数据库系统的数据对象保留多个版本，以提高系统的并发操作程度。

①多版本协议描述

假设版本Q_k具有小于或等于TS（T）的最大时间戳。

a.若事务T发出read（Q），则返回版本Q的内容。

b.若事务T发出write（Q），则：当TS（T）<R-timestamp（Q_k）1对，回滚T；当TS（Tl=w-timestamp（Q_k）时，覆盖Q_k的内容；否则，创建Q的新版本。

②优点

a.消除了数据库中数据对象读和写操作的冲突；

b.提高了系统的性能；

c.提高事务的并发度。

（2）改进的多版本并发控制

多版本协议可以进一步改进。区分事务的类型为只读事务和更新事务。对于只读事务，发生冲突的可能性很小，可以采用多版本时间戳。对于更新事务，采用较保守的两阶段封锁（2PL）协议。这样的混合协议称为MV2PL。