徐愛蕓

摘要：事務(wù)是并發(fā)控制的基本單位，多個事務(wù)的并發(fā)操作可能會破壞事務(wù)的ACID特性，為了保證事務(wù)的隔離性和一致性，DBMS必須對并發(fā)操作進(jìn)行正確調(diào)度，多個事務(wù)并發(fā)執(zhí)行時，對并發(fā)操作的調(diào)度是隨機(jī)的，只有可串行化調(diào)度才能保證并發(fā)執(zhí)行的正確性。

關(guān)鍵詞：事務(wù);并發(fā)執(zhí)行;調(diào)度策略;可串行化調(diào)度

1 前言

調(diào)度（Schedule）是對若干事務(wù)的操作按照它們的執(zhí)行時間安排的一個操作序列（順序），同一個事務(wù)中的操作在調(diào)度中的執(zhí)行順序是固定不變的。

2 串行調(diào)度

若調(diào)度S中的多個事務(wù)依次執(zhí)行，每個事務(wù)T中的操作都是連續(xù)執(zhí)行的，這種調(diào)度是串行調(diào)度。將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。

現(xiàn)在有兩個事務(wù)，分別包含下列操作：

事務(wù)T1：讀B;A=B+1;寫回A;? ? ? ? 事務(wù)T2：讀A;B=A+1;寫回B;

假設(shè)：A，B的初值均為2。

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

無論哪種串行調(diào)度，結(jié)果都是正確的。

串行執(zhí)行由于每個時刻只有一個事務(wù)運(yùn)行，其它事務(wù)必須等到這個事務(wù)結(jié)束以后方能運(yùn)行，因此不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源的特點。

3 并發(fā)調(diào)度

若多個事務(wù)按一定調(diào)度策略同時執(zhí)行，這種交叉執(zhí)行稱為并發(fā)執(zhí)行。由于計算機(jī)系統(tǒng)對并發(fā)操作的調(diào)度是隨機(jī)的，而且不同的調(diào)度可能會產(chǎn)生不同的結(jié)果，事務(wù)的并發(fā)執(zhí)行并不能保證事務(wù)的正確性。什么樣的并發(fā)操作調(diào)度是正確的？

3.1 可串行化（Serializable）調(diào)度

多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時的結(jié)果相同，稱這種調(diào)度為可串行化的調(diào)度，可串行化調(diào)度是并行事務(wù)正確性的唯一準(zhǔn)則。

①事務(wù)T1：Slock B;Y=B=2;Unlock B;Xlock A

②事務(wù)T2：Slock A; 等待

③事務(wù)T1：A=Y+1;寫回A（=3）;Unlock A

④事務(wù)T2：X=A=3;Unlock A;Xlock B;B=X+1;寫回B（=4）;Unlock B

最后執(zhí)行的結(jié)果：A=3? B=4，與串行執(zhí)行的結(jié)果相同，則這種并發(fā)調(diào)度是正確的。

3.2不可串行化調(diào)度

①事務(wù)T1：Slock B;Y=B=2

②事務(wù)T2：Slock A;X=A=2

③事務(wù)T1：Unlock B

④事務(wù)T2：Unlock A

⑤事務(wù)T1：Xlock A;A=Y+1;寫回A（=3）

⑥事務(wù)T2：Xlock B;B=X+1;寫回B（=3）

⑦事務(wù)T1：Unlock A

⑧事務(wù)T2：Unlock B

最后執(zhí)行的結(jié)果：A=3? B=3，與串行執(zhí)行的結(jié)果不相同，則這種并發(fā)調(diào)度是錯誤的。

3.3沖突可串行化調(diào)度

沖突操作是指分屬不同事務(wù)但對同一數(shù)據(jù)進(jìn)行的讀寫操作和寫寫操作，即 Ri（X）和Wj（X）; Wi（X）和Rj（X） ;Wi（x）和Wj（X）三種操作對。在保證一個調(diào)度中沖突操作次序不變的前提下，若通過交換不同事務(wù)的不沖突操作的次序，能夠得到一個串行調(diào)度，則該調(diào)度是沖突可串行化的調(diào)度。一個調(diào)度是沖突可串行化的，一定是可串行化的調(diào)度。

在一個調(diào)度中，改變不同事務(wù)的非沖突操作的順序不影響數(shù)據(jù)庫的狀態(tài)，不同事務(wù)的沖突操作和同一事務(wù)的兩個操作的順序不能改變。一個調(diào)度Sc在保證沖突操作的次序不變的情況下，通過交換兩個事務(wù)不沖突操作的次序得到另一個調(diào)度Sc，如果S是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度。不同事務(wù)的沖突操作和同一事務(wù)的兩個操作不能交換（Swap）。

如對兩個事務(wù)T1、T2的調(diào)度

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）

是一個串行調(diào)度T1、T2，故S1是沖突可串行化調(diào)度。

沖突可串行化調(diào)度一定是可串行化調(diào)度，但可串行化調(diào)度不一定是沖突可串行化調(diào)度，

例如：S1=W1（B）W1（A）W2（B）W2（A）W3（A）是串行調(diào)度，而調(diào)度S2=W1（B）W2（B）W2（A）W1（A）W3（A）不滿足沖突可串行化，但調(diào)度S2與S1的執(zhí)行結(jié)果相同，A的值都等于W3（A），B的值都等于W2（B）。因此S2是可串行化調(diào)度，但不是沖突可串行化調(diào)度。

4 結(jié)束語

為保證數(shù)據(jù)庫的一致性，只有可串行化調(diào)度才允許運(yùn)行，而兩段鎖協(xié)議是保證并發(fā)調(diào)度可串行化的協(xié)議，使用兩段鎖協(xié)議產(chǎn)生的是可串行化調(diào)度。若并發(fā)執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的。事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。

參考文獻(xiàn)：

[1]宋金玉，陳萍，陳剛.數(shù)據(jù)庫原理與應(yīng)用（第2版）清華大學(xué)出版社，2011.6.

[2]何玉潔 數(shù)據(jù)庫系統(tǒng)教程（第2版）人民郵電出版社，2015.12.