【从零开始学习计算机科学】数据库系统（七）并发控制技术

并发控制技术

数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取和／或修改同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。所以数据库管理系统必须提供并发控制机制。

封锁

封锁是实现并发控制的一个有效措施。

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

引入锁机制是为了保证数据的一致性(事务的隔离性)和提高系统的并发处理能力，或者说，为保了证应用的有效性。

给数据加锁的方式有许多种，目前我们考虑以下两种：

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

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

S锁的目的是增强并发能力，因为可能95%以上的应用是读数据，更新应用的频率非常小。但是，没有S锁，系统的发处理能力会大大降低，仅比串行调度略好。

封锁协议

仅有封锁未必能保证调度的可串行化，因此我们需要一组加锁规则来保证调度的可串行化，因此，就引入了封锁协议。

具体来讲，封锁协议约定了对数据对象何时申请X锁或S锁，持续时间、何时释放等一系列规则。
对封锁方式规定不同的规则，就形成了各种不同的封锁协议。

封锁会带来的问题

活锁（饥饿）：如果事务$T_1$封锁了数据R，事务$T_2$又请求封锁数据R，于是$T_2$等待；$T_3$也请求封锁数据R，当$T_1$释放了R上的锁之后，系统首先批准了$T_3$的请求，$T_2$任然等待；然后$T_4$又请求封锁R，当$T_3$释放R上的锁之后，系统又批准了$T_4$的请求$\cdots$ $T_2$有可能永远等待，这就是活锁的情况。避免活锁的简单方法是：采用先来先服务策略。

死锁：如果事务$T_1$封锁了数据$R_1$，$T_2$封锁了数据$R_2$，然后$T_1$又请求封锁$R_2$，因$T_2$封锁了$R_2$，于是$T_1$等待$T_2$释放$R_2$上的锁；接着$T_2$又请求封锁$R_1$，因$T_1$封锁了$R_1$，于是$T_2$等待$T_1$释放$R_1$上的锁。这样就出现了$T_1$在等待$T_2$,而$T_2$又在等待$T_1$的局面，$T_1$、$T_2$两个事务永远不能结束，形成死锁。

解决死锁有两种思路，分别是死锁的预防和死锁的恢复。

死锁预防：预先防止死锁发生，保证系统永不进入死锁状态。

死锁检测与恢复：允许系统进入死锁状态，但要周期性地检测系统有无死锁。如果有，则把系统从死锁中恢复过来。

两种策略都会引起事务回滚。如果系统进入死锁状态的概率相对较高，则通常采用死锁预防策略；否则使用死锁检测与恢复更有效。

预防死锁的两种方法

一种方法是通过对加锁请求进行排序或者要求同时获得所有的锁来保证不会发生循环等待。这种方法又有以下两种子方法

一次封锁法：一次性将所有要使用的数据全部加锁，否则就不能继续执行。这种方法存在的问题主要有在事务开始前通常很难预知哪些数据项需要封锁。数据项使用率可能很低，因为许多数据项可能封锁很长时间却用不到。

顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按照这个顺序实施封锁。这种方法存在的问题有：数据库在动态地不断变化，要维护这样的资源的封锁顺序非常困难，成本很高。事务的封锁请求可以随着事务的执行而动态地决定，很难实现确定每一个事务要封锁哪些对象，因此很难按规定的顺序去施加封锁。

另一种方法比较接近死锁恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。

预防死锁的第二种方法，也是最有效的方法就是采用抢占与事务回滚技术。

在这种方法里，赋予每个事务一个唯一的时间戳，系统利用时间戳来决定事务应当等待还是回滚。但并发控制仍使用封锁机制。

若一个事务回滚，则该事务重启时保持原有的时间戳。

利用时间戳的两种不同的死锁预防机制如下：
等待-死亡(wait-die)机制：基于非抢占技术；
受伤-等待(wound-wait)机制 ：基于抢占技术。

等待-死亡机制

这种机制基于非抢占技术。当事务$T_i$申请的数据项当前被$T_j$持有，仅当TS($T_i$) < TS($T_j$)时，允许$T_i$等待。否则，$T_i$回滚。

受伤-等待机制

这种机制基于抢占技术，是wait-die的相反机制。当事务$T_i$申请的数据项当前被$T_j$持有，仅当TS($T_i$) > TS($T_j$)时，允许$T_i$等待。否则，$T_i$抢占$T_j$持有的数据项，而$T_j$回滚。

等待-死亡与受伤-等待的区别

等待区别：在等待-死亡机制中，较老的事务必须等待较新的事务释放它所持有的数据项。因此，事务变得越老，它越要等待。与此相反，在受伤-等待机制中，较老的事务从不等待较新的事务；

回滚区别：在等待-死亡机制中，如果事务$T_k$由于申请的数据项当前被$T_j$持有而死亡并回滚，则当事务$T_k$重启时它可能重新发出相同的申请序列。如果该数据项仍被$T_j$持有，则$T_k$将再度死亡。因此，$T_k$在获得所需数据项之前可能死亡多次。而在受伤-等待机制中，如果$T_i$申请的数据项当前被$T_j$持有而引起$T_j$受伤并回滚，则当$T_j$重启并发出相同的申请序列时，$T_j$会等待而不是回滚。

死锁的诊断与解除（普遍采用的方法）

死锁检测（deadlock detection）即探查和识别死锁的方法。这种策略并不采取任何动作来使死锁不出现，而是系统事件触发执行一个检测算法。

也即在系统运行过程中，及时地探查和识别死锁的存在，并识别出处于死锁之中的进程和资源等。

死锁恢复（deadlock recovery）是指当检测并识别出系统中出现处于死锁之中的一组进程时，如何使系统恢复到正常状态并继续执行下去。

死锁恢复主要有以下几种方法：

超时法：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。存在的问题：时间设置太短，有可能误判死锁；时间设置太长，死锁发生后不能及时发现。

等待图法：事务等待图是一个有向图G =（T,U），T为结点的集合，每个结点表示正在运行的事务；U为边的集合，表示事务等待情况，若事务$T_1$等待$T_2$，则在$T_1$、$T_2$之间画一条有向边，从$T_1$指向$T_2$。

事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（如每隔数秒）生成事务等待图，并进行检测。如果发现图中存在回路，则表示系统中出现了死锁。并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有的锁，使其他事务得以运行下去。

死锁的解除还考虑一下三个方面：

选择牺牲者：给定处于死锁状态的事务集，为了解除死锁，我们必须决定回滚哪一个事务来打破死锁。我们应该选择使回滚代价最小的事务作为牺牲者，例如该事务已计算了多久？该事务已使用了多少数据项？完成该事务还需要多少数据项？回滚该事务将牵涉多少事务？

回滚：决定回滚多远：是彻底回滚，即中止该事务而后重启；还是部分回滚，即只回滚到可以解除死锁为止。

避免饿死：避免同一事务总是作为回滚代价最小的事务而被选中。最常用的方法就是在代价因素中包含回滚次数。

常用的封锁协议

一级封锁协议

一级封锁协议是：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。

一级封锁协议可以防止丢失修改(因为事务结束前都禁止其它事务进行数据修改)，并保证事务T是可恢复的。使用一级封锁协议可以解决丢失修改问题。

在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，它不能保证可重复读和不读“脏”数据。

二级封锁协议

二级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后方可释放S锁。
二级封锁协议除防止了丢失修改，还可以进一步防止读“脏”数据（确保在数据读取期间没有其它事务修改）。但在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。

三级封锁协议

三级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。

三级封锁协议除防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。（因为直到事务结束前，由于加了S锁，始终不会有其它事务对其进行修改）。

封锁协议级别越高，一致性程度越高。

两段锁协议

两段锁协议是指所有的事务必须分两个阶段对数据项加锁和解锁。即事务分两个阶段，第一个阶段是获得封锁。事务可以获得任何数据项上的任何类型的锁，但是不能释放；第二阶段是释放封锁，事务可以释放任何数据项上的任何类型的锁，但不能申请。

第一阶段是获得封锁的阶段，称为扩展阶段（增长阶段）：其实也就是该阶段可以进入加锁操作，在对任何数据进行读操作之前要申请获得S锁，在进行写操作之前要申请并获得X锁，加锁不成功，则事务进入等待状态，直到加锁成功才继续执行。就是加锁后就不能解锁了。

第二阶段是释放封锁的阶段，称为收缩阶段（缩减阶段）：当事务释放一个封锁后，事务进入封锁阶段，在该阶段只能进行解锁而不能再进行加锁操作。

注意，两阶段所要求释放锁的操作不是必须要在事务的末尾，而且，两阶段封锁协议保证冲突可串行化，但是冲突可串行化未必符合两阶段封锁。

除了调度可串行化外，调度还应该是无级联的。在两阶段封锁协议下，级联回滚可能发生。
级联回滚可以通过将两阶段封锁修改为严格两阶段封锁协议( strict two phase locking protocol )加以避免。这个协议除了要求封锁是两阶段之外,还要求事务持有的所有排他锁必须在事务提交后方可释放。这个要求保证未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读这些数据。

另一个两阶段封锁的变体是强两阶段封锁协议( rigorous two-phase locking poco),它要求事务提交之前不得释放任何锁。我们很容易验证在强两阶段封锁条件下，事务可以按其提交的顺序串行化。

锁转换

在带锁转换的两阶段封锁协议中，第一阶段能申请lock-S 能申请lock-X；能将lock-S 转换为lock-X (upgrade升级)。第二阶段能释放 lock-S；能释放 lock-X；能将lock-X 转换为(downgrade降级)。

带锁转换的两阶段封锁协议确保了冲突可串行化。

基于事务读、写请求，自动生成加锁、解锁指令：

    事务进行read(Q)操作时，系统产生一条lock-S(Q)指令，然后read(Q)指令。

    事务进行write（Q）操作时，系统检查该事务是否持有Q的共享锁，若有，则upgrade（Q），然后write（Q）；若无，系统发出lock-X（Q）指令，然后write（Q）。

事务提交或中止后，该事务持有的所有锁都释放

锁机制的实现

当一条锁请求消息到达时，如果相应数据项的链表存在，在该链表末尾增加一个记录；否则，新建一个仅包含该请求记录的链表。

在当前没有加锁的数据项上总是授予第一次加锁请求，但当事务向已被加锁的数据项申请加锁时，只有当该请求与当前持有的锁相容，并且所有先前的请求都已授予锁的条件下，锁管理器才为该请求授予锁，否则，该请求只好等待。

当锁管理器收到一个事务的解锁消息时，它将与该事务相对应的数据项链表中的记录删除，然后检查随后的记录，如果有，如前所述，就看该请求能否被授权，如果能，锁管理器授权该请求并处理其后记录，如果还有，类似地一个接一个地处理。
如果一个事务中止，锁管理器删除该事务产生的正在等待加锁的所有请求。

基于图的协议

基本思路是：若要开发“非两阶段封锁的、但要求保证冲突可串行化的”协议，则一般需要每个事务如何存取数据库的附加信息。

基于图的协议可以开发各种不同模型，一类最简单的模型是偏序，其要求所有数据项集合D满足一种偏序‘$\to$’，即D = { d 1 , d 2 , … , d h } \{d_1,d_2,\ldots, d_h\} {d1​,d2​,…,dh​}，对任何i，都有$d_i\to d_{i+1}$。
这种偏序的本质含意是要求：如果 $d_i\to d_j$ ，那么任何访问$d_i$和$d_j$的事务，都必须保证$d_i$先于$d_j$被访问。即所有事务对D中数据项的访问，都必须遵从偏序约束。偏序意味着集合D可以视为是一个有向无环图。

树形协议

树形协议就是一种简单的基于图的协议。
树形协议是一种特殊的偏序关系，所有数据项按照从上到下的父子关系，排出一种偏序(所有事务需按此偏序访问数据项)。

在树形协议( tree protocol )中，可用的加锁指令只有lock-X。每个事务T对一数据项最多能加一次锁，并且必须遵从以下规则：T的首次加锁可以对任何数据项进行。此后，T对数据项Q加锁的前提是T当前持有Q的父项上的锁。对数据项解锁可以随时进行。

数据项被T加锁并解锁后，T’不能再对该数据项加锁。所有满足树形协议的调度是冲突可串行化的。

(一般地)树形协议调度都是可串行化的调度。并且，树形协议不会产生死锁。但是，树形协议的缺点是树形协议不能保证可恢复性。

为了保证可恢复性，只需将树形协议修改为在事务结束前不允许释放任何X锁(牺牲一定的并发度)。

并且，树形协议不能保证无级联回滚。为了保证无级联回滚，需将树形协议修改为在事务结束前不允许释放任何X锁(牺牲一定的并发度)。

树形协议优点是：树形协议保证了冲突可串行化；同时不会产生死锁，不需要回滚；树形协议可较早地释放锁，以减少事务间的等待时间，从而可增强调度的并发性。

树形协议缺点是树形协议不能保证事务的可恢复性；事务不能保证不发生级联回滚；事务有可能会给那些根本不访问的数据项加锁，从而增加了锁的开销和额外的等待时间，引起并发性降低。

多粒度封锁协议

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

以关系数据库为例，封锁对象可以是这样一些逻辑单元:属性值、属性值的集合、元组、关系、索引项、整个索引直至整个数据库；也可以是这样一些物理单元：页(数据页或索引页)、块等。

封锁粒度与系统的并发度和并发控制的开销密切相关。直观地看，封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；反之，封锁的粒度越小，并发度较高，但系统开销也就越大。

在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁（multiple granularity locking）。

选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以求得最优的效果。

因此，多粒度锁即允许使用多种粒度/大小不同的锁。

多粒度封锁协议的主要内容包括：允许多粒度层次图中的每一个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。

一个数据对象可以以两种方式被封锁：

显示封锁：直接加到数据对象上。

隐式封锁：该数据对象没有显示地被封锁，是由于其上级结点加锁而使得该数据对象加了锁。
但无论一个数据对象是以哪一种方式被加锁，其效果是一样的。

若事务$T_i$要封锁文件$F_a$中的某记录$r_a$，由于$T_i$显式的给$F_a$加锁，意味着$r_a$被隐式加锁。那么，当事务$T_j$申请对$r_a$加锁时，由于$r_a$上没有显式锁，所以系统必须从根结点到$r_a$进行搜索，如果发现路径上有某个结点持有不相容的锁，则$T_j$等待。

若事务$T_i$希望封锁整个数据库，只需要对根结点加锁。但是由于需要判断树中其他结点是否持有不相容锁，因此需要搜索整个树，效率就非常低。

因此，引进了一种新型锁——意向锁。

如果一个结点加上意向锁，意味着要在树的较低层进行显式加锁。在一个结点显式加锁前，该结点的全部祖先结点均加上意向锁。

因此，事务不必搜索整棵树就能判定能否成功对一个结点加锁。

目前常用的多粒度锁有：

IS锁。如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加 S锁。例如，要对某个元组加 S锁，则要首先对关系和数据库加 IS锁。

IX锁。如果对一个数据对象加 IX锁，表示它的后裔结点拟（意向）加 X锁。例如，要对某个元组加 X锁，则要首先对关系和数据库加 IX锁。

SIX锁。如果对一个数据对象加 SIX锁，表示对它加S锁，再加IX锁，即 SIX = S + IX。例如对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。

多粒度封锁协议要求的规则

事务$T_i$必须遵守锁类型相容矩阵。

事务$T_i$必须首先封锁树的根节点，并且可以加任意类型的锁。

仅当$T_i$当前对Q的父结点具有IX或IS锁时，Ti对节点Q可加S或IS锁。

仅当$T_i$当前对Q的父结点具有IX或SIX锁时，Ti对节点Q可以加X、SIX或IX锁。

仅当$T_i$未曾对任何结点解锁时，Ti可对节点加锁（也就是说，Ti是两阶段的）。

仅当$T_i$当前不持有Q的子结点的锁时，Ti可对节点Q解锁。

因此，多粒度协议要求加锁按自顶向下的顺序，而锁的释放则按自底向上的顺序。

以以下情况为例

假设事务$T_1$读文件$F_a$的记录$r_{a1}$，那么$T_1$需要给数据库、区域$A_1$，以及$F_a$加IS锁，最后给$r_{a1}$加S锁。

假设事务$T_2$要修改文件$F_a$的记录$r_{a2}$，那么，$T_2$需要给数据库、区域$A_1$，以及$F_a$加IX锁，最后给$r_{a2}$加X锁。

假设事务$T_3$要读取文件$F_a$的所有记录，那么，$T_3$需要给数据库、区域$A_1$加IS锁，最后给$F_a$加S锁。

假设事务$T_4$要读取整个数据库。它在给数据库加S锁后就可读取。

$T_1$、$T_3$与$T_4$可以并发的存取数据库。事务$T_2$可以与$T_1$并发执行，但不能与$T_3$或$T_4$并发执行。

多粒度封锁协议可以保证可串行性，增强了并发性，减少了锁开销，但是可能存在死锁。

时间戳排序协议

在目前的封锁协议中，每一对冲突事务的次序是在执行时由二者申请的，由类型不相容的第一个锁决定可串行化次序。

另一种决定可串行化次序的方法是事先选定事务的次序。其中最常用的方法是时间戳排序机制。

对于系统中每一个事务$T_i$，我们把一个唯一的固定时间戳和它联系起来，此时间戳记为TS（$T_i$）。该时间戳是在事务$T_i$开始执行前由数据库系统赋予的。若事务$T_i$已赋予时间戳TS（$T_i$），此时有一个新事务$T_j$进入系统，则TS（$T_i$）< TS（$T_j$）。

实现这种机制可以采用下面两个简单的方法：使用系统时钟的值作为时间戳；即，事务的时间戳等于该事务进入系统时的时钟值。使用逻辑计数器，每赋予一个时间戳，计数器增加计数；即，事务的时间戳等于该事务进入系统时的计数器值。

事务的时间戳决定了调度中事务串行化的顺序。即，若TS（$T_i$）< TS（$T_j$），则DBMS必须保证所产生的调度等价于Ti出现在Tj之前的某个串行调度。

在时间戳机制中，每个数据项Q需要和以下两个重要的时间戳相关联：

W-TS(Q)：表示当前已成功执行write(Q)的所有事务的最大时间戳；

R-TS(Q)：表示当前已成功执行read(Q)的所有事务的最大时间戳。

每当有新的read(Q)或write(Q)指令成功执行，这两个时间戳就被更新。

时间戳排序协议是按照事务的时间戳顺序来处理事务之间的冲突操作，满足该协议的任何调度都能保证是冲突可串行化的；是无死锁，因为冲突的事务被回滚重启并赋予新的时间戳，而不是等待执行。

运作方式

假设事务$T_i$发出read(Q)操作（事务时间戳小于冲突操作时间戳时回滚）：

若TS($T_i$) < W-TS(Q)，则$T_i$需要读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚；

若TS($T_i$) $\ge$ W-TS(Q)，则执行read操作，而R-TS(Q)的值被设为R-TS(Q)与TS($T_i$)中的较大者。

假设事务$T_i$发出write(Q)操作：

若TS($T_i$) < R-TS(Q)，则$T_i$产生的Q值是先前所需要的值，但系统已假定该值不会被产生。因此，write操作被拒绝，$T_i$回滚；

若TS(Ti) < W-TS(Q)，则$T_i$产生的Q值已过时。因此，write操作被拒绝，$T_i$回滚；

其他情况，系统执行write操作，并将W-TS(Q)的值设为TS($T_i$)。

一调度如下图，时间戳分别为1, 2, 3, 4, 5 ，即TS($T_i$)=i，i=1，$\dots$，5。

按照实际执行顺序，其调度如下所示：

    1，R-timestamp( X ) = 5正常读

    2，R-timestamp( Y ) = 2正常读

    3，R-timestamp( Y ) = 2正常读(不更新)

    4，W-timestamp( Y ) = 3正常写(需检查)

    5，W-timestamp( Z ) = 3正常写

    6，R-timestamp( W ) = 5正常读

    7，异常读,撤消事务T2(需检查)

    8，R-timestamp( X ) = 5正常读(不更新)

    9，R-timestamp( W ) = 5正常读(不更新)

    10，异常写,撤消事务T3

    11，W-timestamp( Y ) = 5正常写(需检查)

    12，W-timestamp( Z ) = 5正常写

调度优先图

调度优先图为一有向图，顶点代表事务，每条弧描述一个冲突操作；$T_i\to T_j$表示$T_i$和$T_j$为冲突操作，且$T_i$先于$T_j$。此时，若若$T_i$读Q，仅$T_j$写Q为冲突操作，而按规则，这时必$T_i$ < $T_j$(否则$T_i$撤销)。若$T_i$写Q，$T_j$读Q或写Q均是冲突操作，而按规则，这两种情形均$T_i$ < $T_j$(否则$T_i$撤销)。

优先图中的弧都是从小时间戳到大时间戳。因此，在调度优先图中没有环。

时间戳排序协议不仅保证冲突可串行化(因为冲突操作按时间戳顺序进行处理)，时间戳排序协议还保证不会出现死锁现象（因为不要求事务加锁，也不需等待）。但是，时间戳排序协议的调度一般是不可恢复，不能防止级联回滚的。

快照隔离

快照隔离是在事务开始执行时给它数据库的一份快照。事务在该快照上操作，和其他并发事务完全隔离。快照中的数据值仅包括已经提交的事务所写的值。其不能保证可串行化。

快照隔离对只读事务来说是理想的，不需要等待。对与更新事务，需要在更新写入数据库之前，处理与其他并发更新的事务之间存在的潜在冲突。

以更新操作为例，按照先提交者获胜( first comitter wins )方法，当事务T进人部分提交状态，将以下操作作为一个原子操作执行：

检查是否有与T并发执行的事务，对于T打算写人的某些数据，该事务已经将更新写人数据库。
如果发现这样的事务，则T中止。

如果没有发现这样的事务，则T提交，并且将更新写人数据库。

按照先更新者获胜( first updater wins )方法，系统采用一种仅用于更新操作的锁机制(读操作不受此影响，因为它们不获得锁)。当事务T试图更新一个数据项时，它请求该数据项的一个写锁。如果没有另一个并发事务持有该锁，则获得锁后执行以下步骤：

如果这个数据项已经被任何并发事务更新，则T中止。否则T能够执行其操作，可能包括提交。
然而，如果另一个并发事务T’ 已经持有该数据项的写锁，则T不能执行，并且执行以下规则：
T等待直到T’中止或提交。

如果T’中止，则锁被释放并且T可以获得锁。当获得锁后，执行前面描述的对于并发事务的更新检查，如果有另一个并发事务更新过该数据项，则T中止，否则，执行其操作。

如果T’提交，则T必须中止。

当事务提交或中止时，锁被释放。

基于有效性检查的协议

在这个协议中，每个事务$T_i$的执行分为三个阶段。

读取和执行阶段：事务$T_i$只写入临时局部变量，即读入数据和写临时局部变量。

验证阶段：事务$T_i$执行“验证测试”确定是否可以在不违反可序列化性的情况下执行。

写入阶段：如果验证了$T_i$，则更新将应用于数据库；否则，$T_i$将回滚。

并发执行事务的三个阶段可以交错进行交替，但每个事务都必须按顺序经历这三个阶段。
为简单起见，假设验证和写入阶段以原子和串行方式同时发生。即一次只有一个事务执行验证/写入。这也称为乐观并发控制，因为事务完全执行，并且希望在验证期间一切顺利(而封锁协议和时间戳排序协议等，称为悲观并发协议，他们检查到冲突时，或强迫事务等待或回滚)。

每个事务有三个时间戳：

开始（$T_i$）：$T_i$开始执行的时间(读操作的时间)；

验证（$T_i$）：$T_i$进入验证阶段的时间；

完成（$T_i$）：$T_i$完成其写入阶段的时间。

合法性检查应满足：若TS($T_i$) < TS($T_k$)，等价的串行调度应满足$T_i$在$T_k$之前完成效果。

可序列化顺序由验证时给定的时间戳决定，以提高并发性。因此，TS（$T_i$）被赋予验证值（$T_i$）。即令: TS($T_i$) = Validation($T_i$)。

这个协议很有用，如果冲突发生的概率很低，它可以提供更大程度的并发性。因为序列化顺序不是预先决定的，而且必须回滚的事务相对较少。

如果对于具有TS（$T_i$）< TS（$T_j$）的所有$T_i$，以下任一条件成立：

1，完成（$T_i$）< 开始（$T_j$）；

2，开始（$T_j$）< 完成（$T_i$）< 验证（$T_j$），且$T_i$写的数据项集与$T_j$读的数据项集不相交。

然后验证成功，可以提交$T_j$。否则，验证失败，$T_j$被中止。
可串行化说明：其可按照$T_i$，$T_j$的顺序进行（冲突）串行化。

考虑以下例子

其不满足：完成（T25）< 开始（T26），其满足：开始（T26）< 完成（T25）< 验证（T26），因此，验证成功，通过有效性检查。