并发控制概述

在讨论数据库并发之前我们先引入事务的概念：

数据库事务通常包含了一个序列的对数据库的读/写操作（一个单元的一系列SQL语句的集合）。

我们引入事务无非是为了实现以下两个目的：

为数据库操作序列提供一个从失败中恢复到正常状态的方法，同时提供数据库即使在异常状态下仍能保持一致性的方法。（即系统的错误恢复）当多个应用程序并发访问数据库时，可以在这些应用程序之间提供一个隔离方法，以保证彼此之间的操作不会互相干扰。（即并发数据库访问）当事务被提交给数据库管理系统（DataBaseManagerService，DBMS）之后，DBMS需要确保该事务中的所有操作都成功完成且其结果被永久储存在数据库中，如果事务中有的操作没有成功完成，则事务中的所有操作都需要回滚，回到事务执行前的状态。同时，该事务对数据库或者其他事务的执行不会产生影响，即所有的事务都好像在独立的执行。

了解了事务的概念后，我们来引入并发，在最原始的单处理机系统中，事务只能一个一个地序列执行，即每个时刻之后一个事务执行，上一个事务执行完成之后下一个事务才有机会执行，如下图（a）所示，这样做的缺点很明显，就是计算机资源的利用率很低(比如A事务需要使用CPU资源，B事务需要使用IO资源，二者所需的资源不冲突，但是在序列方式下同一时刻只能利用到CPU或只能利用到IO，资源使用率很低)。为了提高资源的利用率，出现了一种叫做交叉并发的方式，即让不同事务分时间段进行交叉执行，这样可以减少处理机的空闲时间，如下图（b）所示。

上面描述的是单处理机的情况，可以发现这种情况下没有实现真正的并行执行，导致计算机资源利用率较低，这时就引入了多处理机下的并发执行，即当计算机有多个处理机时，就可以同时在不同的处理机上执行不同的事务，这样做到真正意义上的并发执行，这样做的优点是计算机的资源利用率得到了有效提高，缺点就是由于并发会产生很多序列执行时不会产生的冲突和错误，会引起数据库的不一致性，为了解决这一缺点，我们就需要对数据库中的并发进行控制，这也是我们本文的重点，即数据库系统的并发控制。

并发操作引起的资料不一致性包括三个方面：

丢失修改(lost update)：卖票问题，A代表票的余量，事务X集合事务Y将A读入，假设此时A=10，事务X将票卖出一张即A=A-1=9，将A写入，数据库中A此时为9，事务Y也将票卖出一张即A=A-1=9，将A写入数据库即数据库中此时A=9，可是明明卖出去了两张票，相当于事务X对A的修改丢失了。不可重复读(non-repeatable read)：不可重复读是指事务T1读取资料后，事务T2对数据库执行更新操作，致使事务T1无法再现前一次读取的结果。具体来说分为以下三类情况T1读取资料后T2对资料进行修改，导致T1之后读取的数值与之前读取的不一样T1读取资料之后T2对资料进行删除，导致T1之后再按相同条件读取的资料少了一部分T1读取资料之后T2对资料进行插入，导致T1之后再按相同条件读取的资料多了一部分 后两种情况有时也称为幻影/幻读现象。

3 . 读脏资料：事务T1将资料修改后写入数据库，T2此时将资料读取，T2读取后T1又由于某种原因撤销了之前的对资料的修改，导致T2读取的资料与原数据库中的资料不一致，即脏资料。

产生上述三类错误的原因在于并发操作破坏了事务的隔离性，而数据库系统的并发控制就是为了解决这一问题从而保证不同事务之间可以独立执行、各自不受影响，目前并发控制的主要技术有：封锁、时间戳、乐观控制法、多版本并发控制等。

本文我们讲解目前大多数数据库都在采用的并发控制技术，即封锁（Locking）技术。

封锁

排他锁（写锁），exclusive Locks，简称X锁：若事务T对资料物件A加写锁，则只允许T读取和修改A，其他事务都不能再对A加任何型别的锁，直到T释放A上的锁为止。共享锁（读锁），Share Locks，简称S锁：若事务T对资料物件A加读锁，则只允许T可以读取但不能修改A，其他事务只能再对A加读锁，而不能加写锁，直到T释放A上的读锁为止。封锁协议

在运用X锁和S锁这两种基本封锁对资料物件加锁时，还需要约定一些规则，例如何时申请X锁或S锁、持锁时间、何时释放等，这些规则称为封锁协议。

针对不同的事务隔离级别，有不同的封锁协议，这里介绍四级封锁协议：

一级封锁协议：事务T在修改资料R之前必须先对其加写锁，直到事务结束才释放。一级封锁协议防止了丢失修改，但不能保证可重复读和不读脏资料。二级封锁协议：在一级封锁协议的基础上增加事务T在读资料R前必须加读锁，读完就可以释放。二级封锁协议进一步防止读脏资料，但不能保证可重复读。三级封锁协议：一级封锁协议的基础上增加事务T在读资料R前必须加读锁，直到事务结束才释放。三阶封锁协议除了防止丢失修改和读脏资料外，进一步防止了不可重复读。四级封锁协议：四级封锁协议是对三级封锁协议的增强，其实现机制也最为简单，直接对事务中所读取或者更改的资料所在的表加表锁，也就是说，其他事务不能 读写 该表中的任何资料。

活锁和死锁

避免活锁的方案就是先来先服务，即谁先申请锁，谁先得到锁，即如果事务T2先申请了资料D的锁，这是当资料D的锁释放后一定将资料D的锁给事务T2，而不会给其他事务，这样就保证了不会出现活锁。

死锁：事务T1持有资料D1的锁，还需要资料D2的锁才能继续执行，即在等待资料D2的锁，事务T2持有D2的锁，还需要资料D1的锁，即在等待资料D1的锁，这样事务T1和事务T2相互等待，陷入死锁。

目前在数据库中解决死锁主要有两类方法：

采取预防措施来预防死锁允许死锁发生，定期采用一定手段检测死锁，若检测到发生了死锁，则将死锁解除死锁的预防

一次封锁法

将事务执行过程中所使用的资料一次性全部加锁，这样就不会发生某个事务由于等待某个资料的锁而出现死锁的情况。缺点是可能会需要扩大锁的范围，降低并发度。

顺序封锁法

预先对资料物件排个序，所有事务都按照这个顺序来实施封锁。

缺点是维护资源的封锁顺序很困难。

死锁的诊断与解除

超时法

如果某个事务等待某个锁超过一定时间就认为它出现了死锁。

缺点是如果超时时间设定过短会导致本来没有发生死锁的事务被误判为发生了死锁，如果超时时间设定过大，不能及时发现死锁。

等待图法

如上图，如果T1等待T2，则画一条从T1指向T2的有向边，若T2等待T1，则画一条从T2指向T1的有向边，依次类推，这样就可以构成一个图，如果检测到图中有回路，则说明出现了死锁。

检测到死锁之后就需要解除死锁，现在一般采用的解除死锁的方法是选择一个处理死锁代价最小的事务进行取消，释放其占有的锁，以使其他事务可以正常执行。

并发控制的可序列性

可序列化排程

可序列化排程的定义：多个事务的并发执行是正确的，当且仅当其执行结果与按照个顺序序列地执行这些事物时的结果相同，将这种排程策略称为可序列化排程。

其实说白了，就是如果按照当前的排程方案执行完所有事务后，数据库中资料的状态和以任意顺序序列执行所有事务的结果相同，则当前的排程方案就是正确的排程，即可序列化排程（可以将当前排程等价为某个序列化的排程）。

冲突可序列化排程

我们首先明确什么是冲突操作，冲突操作是指不同事务对同一资料的读写操作和写写操作：

除了(1)式中的两组读写组合，其他任何操作都是不冲突的操作。

我们在进行事务排程的时候应该注意，不同事务的冲突操作和同一事务的两个操作时不能交换的，比如(1)式中，

现在我们来定义冲突可序列化排程：一个排程Sc，在保证不改变冲突操作的次序的前提下，通过交换不同事务之间的不冲突操作，最后得到了一个可序列化的事务序列，则称Sc为冲突可序列化排程。

我们来以一个例项进行说明：

对于排程Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

w2(A)与r1(B)w1(B)是不冲突操作，交换二者得到：Sc2=r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)r2(A)与r1(B)w1(B)是不冲突操作，交换二者得到：Sc3=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)得到的Sc3刚好是以事务T1、事务T2的顺序序列执行的结果，所以Sc1是冲突可序列化的排程。

学会判断一个排程是否是冲突可序列化的排程后，我们就可以引入如下结论了：

冲突可序列化排程是可序列化排程的充分条件，也就是说，如果一个排程是冲突可序列化排程，其一定是可序列化排程(但是反过来说是不对的，即如果一个排程室可序列化排程，其不一定是冲突可序列化排程)。

以上结论可以作为判断一个排程是否是可序列化排程的原则。

总结