一、并发控制概述
允许多个用户同时使用的数据库系统称为多用户数据库系统。例如飞机订票数据库系统、银行数据库系统等都是多用户数据库系统。在这样的系统中，在同一时刻并发运行的事务数可达数百个。
事务可以一个一个地串行执行，即每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行。事务在执行过程中需要不同的资源，有时需要CPU，有时需要存取数据库，有时需要I/O，有时需要通信。如果事务串行执行，则许多系统资源将处于空闲状态。因此，为了充分利用系统资源发挥数据库共享资源的特点，应该允许多个事务并行地执行
如下：设T1，T2，T3是如下三个事务，其中R为数据库中某个数据项，设R的初值为0。
T1：R：= R+5
T2：R：= R*3
T3：R：= 2
若允许三个事务并行执行，我们可以列出所有可能的正确结果。
（1）T1-T2-T3： R=2
（2）T1-T3-T2： R=6
（3）T2-T1-T3： R=2
（4）T2-T3-T1： R=7
（5）T3-T1-T2： R=21
（6）T3-T2-T1： R=11
二、数据库的不一致问题
事务并发执行带来的问题：会产生多个事务同时存取同一数据的情况；可能会存取和存储不正确的数据，破坏事务一致性和数据库的一致性
举个例子，说明并发操作带来的数据不一致问题：
在飞机订票系统中的一个活动序列
1．甲售票点(T1)读出某航班的机票余额A，设A=100；
2．乙售票点(T2)读出同一航班的机票余额A，也为100；
3．甲售票点卖出十张机票，修改余额A←A-10，所以A为90，把A写回数据库；
4．乙售票点也卖出十张机票，修改余额A←A-10，所以A为90，把A写回数据库。
结果卖出二十张机票，数据库中机票余额只减少10。造成这种情况的原因是第4步中乙事务修改A并写回后覆盖了甲事务的修改。
我们把这种情况称为数据这种情况称为数据库的不一致性，是由并发操作引起的。在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。若按上面的调度序列执行，甲事务的修改就被丢失。
当并发事物以不受控制的方式进行执行时，可能会出现一些问题。并发操作带来的数据不一致性包括三类：丢失更新问题（Lost Update），不可重复读问题（Non-repeatable Read）和读“脏”数据问题（Dirty Read）。
2.1 丢失更新问题
当两个事物访问相同的数据库项时就会出现丢失更新的问题，使得某些数据库项的值会不正确。换句话说，如果事务T1和事务T2都是先读一条记录，然后进行修改，那么第一个更新的影响将被第二个更新所覆盖。上面的飞机订票的例子就属此类
事务T1 事务T2
1 读A=100
2 A=100
3 A=A-10,写回A=90
4 A=A-10,写回A=90
从这个表中可以观察到，当第二个事务T2开始读取A的值时，第一个事务T1还没有提交。因此，事务T2仍然是在A=100这个值上进行操作，得到结果A=90。同时，事务T1将A=90这个值写回到磁盘存储中，这样它就立即被事务T2重写了。因此，在整个过程中丢失了卖出10张票
2.2 不可重复读问题
当某个事务在一些数据集上计算一些汇总（集合）函数，而其他的事务正在修改这些数据时就会出现不可重复读（或者更新不一致的检索）问题。这个问题是事务可能在一些数据被更改之前读取而另一些数据是在被更改之后读取，因此产生了不一致的结果。在不可重复读中，事务T1读取一个记录，然后在事务T2更改这个记录时进行一些其他的处理。现在，如果事物T1重新读取这个记录，则新的值将和之前的值不一致。
不可重复读包括三种情况：
（1）事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值。
（2）事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录消失了。
（3）事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。
后两种不可重复读有时也称为幻影现象（Phantom Row）
事务T1 事务T2
1 读A=100，B=200，求和A+B=300
2 读B=200，B=B*2，B=400
3 读A=100，B=400，求和A+B=500(验算结果不对)
2.3 读“脏”数据问题
当一个事务修改数据，却由于某些原因使得事务失败了，而被修改的数据库项在被修改回原来的原始值之前又被其他的事务访问了，这是就会出现读“脏”数据的问题。
也就是说，事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，T2读到的数据就为“脏”数据，即不正确的数据。
事务T1 事务T2
1 读A=100，A=A*2，A=200
2 读A=200
3 ROLLBACK，A恢复为100
三、封锁
封锁是并发控制中的加锁方法，是实现并发控制的一个非常重要的技术。
锁是与数据项有关的一个变量，它描述了数据项的状态，这个状态反映了在数据项上可进行的操作。它防止第二个事务在第一个事务完成它全部活动之前，对数据库记录进行访问。
打个比方，事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其他的事务不能更新此数据对象。
通常，在数据库中每个数据项都有一个锁。锁作为同步化并发事务对数据库访问的一种手段而被广泛使用。因此，封锁模式用于允许并发执行兼容的操作。换句话说，可交换的活动是兼容的。封锁是并发控制最常使用的形式，而且它也是大多数应用程序所选择的方法。
基本的封锁类型有两种: 排他锁(Exclusive Locks，简称X锁，也称写锁) 和共享锁(Share Locks，简称S锁，也称读锁)。
3.1 排他锁
排他锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。
3.2 共享锁
共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。
T1\T2 X S 无锁
X N N Y
S N Y Y
无锁 Y Y Y
如表所示，最左边一列表示事务T1已经获得的数据对象上的锁的类型。最上面一行表示另一事务T2对同一数据对象发出的封锁请求。T2的封锁请求能否被满足用矩阵中的Y和N表示，Y表示事务T2的封锁要求与T1已持有的锁相容，封锁请求可以满足，N表示T2的封锁请求与T1已持有的锁冲突，T2的请求被拒绝。
四、封锁协议
在运用X锁和S锁这两种基本锁对数据对象加锁时，还需要约定一些规则，例如何时申请X锁或S锁、持锁时间、何时释放等。这些规则被称为封锁协议（Locking Protocol）。对封锁方式规定不同的规则，就形成了各种不同的封锁协议。下面介绍三级封锁协议。
4.1 一级封锁协议
一级封锁协议是：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。
一级封锁协议可防止丢失修改，并保证事务T是可恢复的，在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。
4.2 二级封锁协议
二级封锁协议是：在一级封锁协议基础上，事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。
二级封锁协议除防止了丢失修改，还可进一步防止读“脏”数据。在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。
4.3 三级封锁协议
三级封锁协议是：在一级封锁协议基础上，事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。
三级封锁协议除防止了丢失修改和读“脏”数据外，还进一步防止了不可重复读。
上述三级协议的主要区别在于什么操作需要申请封锁，以及何时释放锁(即持锁时间)。
五、活锁和死锁
和操作系统一样，封锁的方法可能引起活锁和死锁。死锁(DeadLock)和活锁(LiveLock)是并发应用程序经常发生的问题，也是多线程编程中的重要概念。以下是对死锁和活锁的形象描述。
现有一条路，两个人宽，从两个相对的方向迎面走来两个人A和B。
死锁的情况： A和B两个人都不愿意给对方让路，所以A和B都在等对方先让路，导致谁也过不去。
活锁的情况：A和B两个人都主动给别人让路。A往左移，同时B往右移；A往右移，同时B往左移。 A和B在移动的时候，同时挡住对方，导致谁也过不去。
5.1 活锁
如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求……，T2有可能永远等待，这就是活锁（LiveLock）的情形。
T1 T2 T3 T4
Lock R … … …
… Lock R … …
… 等待 Lock R …
… 等待 等待 Lock R
Unlock 等待 Lock R 等待
… 等待 … 等待
… 等待 Unlock 等待
… 等待 … Lock R
… 等待 … …
避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。
5.2 死锁
死锁（DeadLock）是集合中的两个（或多个）事务同时等待集合中的其他事务释放锁的情况。所有的事务都不能继续执行了，因为集合中的每个事务都在一个等待队列中，等待集合中的一个其他事物释放数据项上的锁。
T1 T2
Lock R1 …
… Lock R2
… …
Lock R2 …
等待 …
等待 Lock R1
等待 …
… …
… …
如果事务T1封锁了数据R1，T2封锁了数据R2，然后T1又请求封锁R2，因T2已封锁了R2，于是T1等待T2释放R2上的锁。接着T2又申请封锁R1，因T1已封锁了R1，T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。死锁也成为循环等待情形，这里两个事物互相等待（直接或间接）资源。因此在死锁中，两个事物互相排斥访问下一个所需的记录来完成它们的事务，也称为死亡拥抱（Deadly Embrace）。
5.3 死锁的检测和预防
死锁检测是由DBMS实现的一个定期检测，以确定是否由于某些原因使得事务的等待时间超过了预定限制的情况。死锁出现的频率主要与查询负荷以及数据库的物理组织有关。为了计算死锁的发生频率，Gray在1981年提出了每秒产生的死锁是多个程序的个数的平方和事务大小的四次方的论断。检测和预防死锁的基本模式有如下三种：
（1）从不允许死锁发生（死锁预防）
（2）当某事物被阻塞时检测死锁（死锁检测）
（3）定期地检查死锁（死锁避免）
六、并发调度的可串行性
多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，我们称这种调度策略为可串行化（Serializable）的调度。
可串行性（Serializability）： 是并发事务正确性的准则。按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。
现在有两个事务，A和B的初始值均为2：
事务T1：读B；A=B+1；写回A
事务T2：读A；B=A+1；写回B
分别按照T1至T2和T2至T1给出这两个事务不同的调度策略
串行调度A
T1 T2
Slock B
Y=R(B)=2
Unlock B
Xlock A
A=Y+1=3
W(A)
Unlock A
Slock A
X=R(A)=3
Unlock A
Xlock B
BX+1=4
W(B)
Unlock B
串行调度B
T1 T2
Slock A
X=R(A)=2
Unlock A
Xlock B
BX+1=3
W(B)
Unlock B
Slock B
Y=R(B)=3
Unlock B
Xlock A
A=Y+1=4
W(A)
Unlock A
不可串行化的调度C
T1 T2
Slock B
Y=R(B)=2
Slock A
X=R(A)=2
Unlock B
Unlock A
Xlock A
A=Y+1=3
W(A)
Xlock B
B=X+1=3
W(B)
Unlock A
Unlock B
可串行化的调度D
T1 T2
Slock B
Y=R(B)=2
Unlock B
Xlock A
Slock A
A=Y+1=3 等待
W(A) 等待
Unlock A 等待
X=R(A)=3
Unlock A
Xlock B
B=X+1=4
W(B)
Unlock B
为了保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。
从理论上讲，在某一事务执行时禁止其他事务执行的调度策略一定是可串行化的调度，这也是最简单的调度策略。但这种方法实际上是不可取的，因为它使得用户不能充分共享数据库资源。目前DBMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。
两段锁（Two-Phase Locking，简称2PL）协议就是保证并发调度可串行性的封锁协议。除此之外还有其他一些方法，如时间方法、乐观方法等来保证调度的正确性。
七、两段锁协议
两段锁协议(Two-Phase Locking，简称2PL) 是控制并发处理的一个方法或一个协议。在两段锁中，所有的封锁操作都在第一个解锁操作之前。因此，如果事务中的所有加锁操作（比如read_lock、write_lock）都在第一个解锁操作之前，则称此事务是遵循两段锁协议的。
所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁。在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁；在释放一个封锁之后，事务不再申请和获得任何其他封锁。
事务分为两个阶段，第一阶段是获得封锁，也称为增长阶段，在这个阶段事务获得所有需要的锁而不释放任何数据上的锁。一旦获得了所有的锁，事务就处在它的锁定点。第二阶段是释放封锁，也称为收缩阶段，在这个阶段事务释放全部的锁，并且不能再获得任何新锁。
上述两阶段锁有下述规则保证：
（1）两个事务不能有冲突的锁。
（2）在同一个事务中，任何解锁操作都不能在加锁操作之前。
（3）在获得所有的锁之前不影响任何数据，即在事务处于它的锁定点时才能影响数据
事务T1遵守两段锁协议，其封锁序列是 ：
Slock A Slock B Xlock C Unlock B Unlock A Unlock C；
事务T2不遵守两段锁协议，其封锁序列是：
Slock A Unlock A Slock B Xlock C Unlock C Unlock B；
八、锁的粒度
数据库基本上是作为命名的数据项的集合，由并发控制程序选择的作为保护单位的数据项的大小称为粒度（Granularity）。
封锁对象可以是逻辑单元，也可以是物理单元。
粒度是由并发控制子系统控制的独立的数据单位，在基于锁的并发控制机制中，粒度是一个可加锁单位。锁的粒度表明加锁使用的级别。在最通常的情况下，锁的粒度是数据页。大多数商业数据库系统都提供了不同的加锁粒度。加锁可以发生在下述级别上：
数据库级
表级 页级
行（元组）级
属性（字段）级
8.1 数据库级锁
在数据库级锁上，整个数据库被加锁。因此，在事务T1执行期间拒绝事务T2使用数据库中的任何表。
8.2 表级锁
在表级锁上，对整个表进行加锁。因此，在事务T1使用这个表时拒绝事务T2访问表中的任何行（元组）。如果某个事务希望访问一些表，则每个表都被加锁。但两个事物可以访问相同的数据库，只要它们访问的表不同即可。
表级锁的限制比数据库级锁少，但当有很多事务等待访问相同的表时会引起阻塞，尤其是当事务需要访问相同表的不同部分而且彼此没有相互干扰时，这个条件就成为一个问题。表级锁不适合多用户DBMS。
8.3 页级锁
在页级锁上，整个磁盘页（或磁盘块）被加锁。一个表能够跨多个页，而一个页也可以包含一个或者多个表的若干行（元组）。
页级锁最适合多用户DBMS。
8.4行级锁
在行级锁上，对特定的行（或元组）进行加锁，对数据库中的每个表的每一行进行加锁。DBMS允许并发事务访问同一个表的不同行，即使这些行位于相同的页上。
行级锁比数据库级锁、表级锁或页级锁的限制要少很多，行级锁提高了数据的可获得性，但是对于行级锁的管理需要很高的成本。
8.5 属性（或字段）级锁
在属性级锁上，对特定的属性（或字段）进行加锁。属性级锁允许并发事务访问相同的行，只要这些事务是访问行中的不同属性即可。
属性集锁为多用户数据访问产生了最大的灵活性，但它需要很高的系统开销。
九、并发控制的时间戳方法
时间戳是由DBMS创建的唯一标识符，用于表示事务的相对启动时间。时间戳可以看成是事务的启动时间。由此，时间戳是并发控制的一个方法，在这个方法中，每个事务被赋予一个事务时间戳。事务时间戳是一个单调增长的数字，它通常是基于系统时钟的。事务被管理成按时间戳顺序进行，时间戳也可以通过每当新事务启动时增加一个局部计数器的方法产生，时间戳的值产生一个显式的顺序，这个顺序是事务提交给DBMS的顺序。时间戳必须有两个性质，即唯一性和单调性。唯一性假设不存在相同的时间戳值，单调性假设时间戳值总是增加的。在相同事务中对数据库的Read和Write操作必须有相同的时间戳。DBMS按时间戳顺序执行冲突操作，因此确保了事务的可串行性。如果两个事物冲突了，则通常是停止一个事务，重新调度这个事务并赋予一个新的时间戳值。
9.1 粒度时间戳
粒度时间戳是最后一个事务访问它的时间戳的一个记录，一个活动事务访问的每个粒度必须有一个粒度时间戳。可以保留最后一个读和写访问的每个记录。如果它们的存储包括粒度，粒度时间戳可能对读访问引起额外的写操作。粒度时间戳表中的每一项由粒度标识符和事物时间戳组成，同时维护从表中删除的包含最大（最近的）粒度时间戳的记录。对粒度时间戳的查找可以使用粒度标识符，也可以使用最大被删除的时间戳。
9.2 时间戳排序
下述是基于时间戳的并发控制方法中的三个基本算法：
（1）总时间戳排序
总时间戳排序算法依赖于在时间戳排序中对访问粒度的维护，他是在冲突访问中终止一个事务。读和写的访问之间没有区别。因此，对每个粒度时间戳来说只需要一个值。
（2）部分时间戳排序
只排序不可交换的活动来提高总的时间戳排序。在这种情况下，同时存储读和写粒度时间戳。这个算法允许比最后一个更改粒度的事务晚的任何事务读取粒度。如果某个事务试图更改之前已经被事务访问的粒度，则终止此事务。部分时间戳排序算法比总时间戳排序算法终止的事务少，但是其代价是需要存储粒度时间戳的额外空间。
（3）多版本时间戳排序
此算法存储几个被更改粒度的版本，允许事务为它访问的所有粒度查看一致的版本集合。因此，这个算法降低了重新启动那些有写—写冲突的事务而产生的冲突。每次对粒度的更新都创建一个新的版本，这个版本包含相关的粒度时间戳。因此，多版本的时间戳等于或只刚刚小于此事务的时间戳。
9.3 解决时间戳中的冲突
为处理时间戳算法中的冲突，让包含在冲突中的一些事务等待并终止其他的一些事务。下面是时间戳中主要的冲突解决策略：
等待—死亡（Wait-Die）： 如果新的事务已经首先访问了粒度的话，则旧的事务等待新的事务。如果新的事务试图在旧的并发事务之后访问粒度，则新的事务被终止（死亡）并重新启动。
受伤—等待（Wound-Wait）： 如果新的事务试图在旧的并发事务之后访问一个粒度，则先悬挂（受伤）新的事务。如果新的事务已经访问了两者都希望的粒度的话，则旧的事务将等待新的事务提交。
终止事务的处理是冲突解决方案中一个重要的方面。在这种情况下，被终止的事务是正在请求访问的事务，这个事务必须用一个新的时间戳重新启动。如果与其他事务有冲突的话，事务有可能被重复终止。由于出现冲突而使得之前的访问粒度被终止的事务可以用相同的时间戳重新启动，通过消除出现事务被持续地关在外面的可能性，这种方法将获得高的优先权。
9.4 时间戳的缺点
（1）存储在数据库中的每个值需要两个附加的时间戳字段，一个用于存储最后读此字段（属性）的时间，另一个用于存储最后更改此字段的时间。
（2）它增加了内存需求以及处理数据库的开销。
