淺析并發事務的調度

徐愛蕓

摘要：事務是并發控制的基本單位，多個事務的并發操作可能會破壞事務的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.