浅析并发事务的调度

徐爱芸

摘要：事务是并发控制的基本单位，多个事务的并发操作可能会破坏事务的ACID特性，为了保证事务的隔离性和一致性，DBMS必须对并发操作进行正确调度，多个事务并发执行时，对并发操作的调度是随机的，只有可串行化调度才能保证并发执行的正确性。

关键词：事务;并发执行;调度策略;可串行化调度

1 前言

调度（Schedule）是对若干事务的操作按照它们的执行时间安排的一个操作序列（顺序），同一个事务中的操作在调度中的执行顺序是固定不变的。

2 串行调度

若调度S中的多个事务依次执行，每个事务T中的操作都是连续执行的，这种调度是串行调度。将所有事务串行起来的调度策略一定是正确的调度策略。

现在有两个事务，分别包含下列操作：

事务T1：读B;A=B+1;写回A;        事务T2：读A;B=A+1;写回B;

假设：A，B的初值均为2。

则：若T1->T2，A=3   B=4;          若T2->T1，A=4   B=3;

无论哪种串行调度，结果都是正确的。

串行执行由于每个时刻只有一个事务运行，其它事务必须等到这个事务结束以后方能运行，因此不能充分利用系统资源，发挥数据库共享资源的特点。

3 并发调度

若多个事务按一定调度策略同时执行，这种交叉执行称为并发执行。由于计算机系统对并发操作的调度是随机的，而且不同的调度可能会产生不同的结果，事务的并发执行并不能保证事务的正确性。什么样的并发操作调度是正确的？

3.1 可串行化（Serializable）调度

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

①事务T1：Slock B;Y=B=2;Unlock B;Xlock A

②事务T2：Slock A; 等待

③事务T1：A=Y+1;写回A（=3）;Unlock A

④事务T2：X=A=3;Unlock A;Xlock B;B=X+1;写回B（=4）;Unlock B

最后执行的结果：A=3  B=4，与串行执行的结果相同，则这种并发调度是正确的。

3.2不可串行化调度

①事务T1：Slock B;Y=B=2

②事务T2：Slock A;X=A=2

③事务T1：Unlock B

④事务T2：Unlock A

⑤事务T1：Xlock A;A=Y+1;写回A（=3）

⑥事务T2：Xlock B;B=X+1;写回B（=3）

⑦事务T1：Unlock A

⑧事务T2：Unlock B

最后执行的结果：A=3  B=3，与串行执行的结果不相同，则这种并发调度是错误的。

3.3冲突可串行化调度

冲突操作是指分属不同事务但对同一数据进行的读写操作和写写操作，即 Ri（X）和Wj（X）; Wi（X）和Rj（X） ;Wi（x）和Wj（X）三种操作对。在保证一个调度中冲突操作次序不变的前提下，若通过交换不同事务的不冲突操作的次序，能够得到一个串行调度，则该调度是冲突可串行化的调度。一个调度是冲突可串行化的，一定是可串行化的调度。

在一个调度中，改变不同事务的非冲突操作的顺序不影响数据库的状态，不同事务的冲突操作和同一事务的两个操作的顺序不能改變。一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc，如果S是串行的，称调度Sc为冲突可串行化的调度。不同事务的冲突操作和同一事务的两个操作不能交换（Swap）。

如对两个事务T1、T2的调度

S1=R1（A）W1（A）R2（A）W2（A）R1（B）W1（B）R2（B）W2（B）

①把W2（A）与R1（B）W1（B）交换，得到R1（A）W1（A）R2（A）R1（B）W2（A）W1（B）R2（B）W2（B）

②再把R2（A）与R1（B）交换，得到R1（A）W1（A）R1（B）R2（A）W1（B）W2（A）R2（B）W2（B）

③最后把R2（A）与W1（B）交换，得到R1（A）W1（A）R1（B）W1（B）R2（A）W2（A）R2（B）W2（B）

是一个串行调度T1、T2，故S1是冲突可串行化调度。

冲突可串行化调度一定是可串行化调度，但可串行化调度不一定是冲突可串行化调度，

例如：S1=W1（B）W1（A）W2（B）W2（A）W3（A）是串行调度，而调度S2=W1（B）W2（B）W2（A）W1（A）W3（A）不满足冲突可串行化，但调度S2与S1的执行结果相同，A的值都等于W3（A），B的值都等于W2（B）。因此S2是可串行化调度，但不是冲突可串行化调度。

4 结束语

为保证数据库的一致性，只有可串行化调度才允许运行，而两段锁协议是保证并发调度可串行化的协议，使用两段锁协议产生的是可串行化调度。若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。

参考文献：

[1]宋金玉，陈萍，陈刚.数据库原理与应用（第2版）清华大学出版社，2011.6.

[2]何玉洁 数据库系统教程（第2版）人民邮电出版社，2015.12.