-
可串行化調度
鎖定
- 中文名
- 可串行化調度
- 外文名
- Serializable schedule
- 學 科
- 計算機科學
- 應 用
- 判斷並行事務操作是否正確
- 準 則
- 可串行性
- 協 議
- 兩段所協議、封鎖粒度
可串行化調度調度簡介
計算機系統對併發事務中併發操作的調度是隨機的，而不同的調度可能會產生不同的結果。在計算機中，多個事務的併發執行是正確的，當且僅當其結果與按某一次序串行地執行它們時的結果相同，我們稱這種調度策略為可串行化（Serializable）調度。
[1]
其中可串行性判斷並行事務操作是否正確的判別準則。兩段鎖協議就是保證併發調度可串行性的封鎖協議。
可串行化調度事務
可串行化調度流程
事務是恢復和併發控制的基本單位。
事務應該具有4個屬性：原子性、一致性、隔離性、持久性。這四個屬性通常稱為ACID特性。
原子性（atomicity）。一個事務是一個不可分割的工作單位，事務中包括的諸操作要麼都做，要麼都不做。
一致性（consistency）。事務必須是使數據庫從一個一致性狀態變到另一個一致性狀態。一致性與原子性是密切相關的。
隔離性（isolation）。一個事務的執行不能被其他事務干擾。即一個事務內部的操作及使用的數據對併發的其他事務是隔離的，併發執行的各個事務之間不能互相干擾。
可串行化調度衝突操作
Ri (x)與Wj(x) /* 事務Ti讀x，Tj寫x*/
Wi(x)與Wj(x) /* 事務Ti寫x，Tj寫x*/
其他操作是不衝突操作
不同事務的衝突操作和同一事務的兩個操作不能交換(Commute) ,否則會影響執行的效果。
[例]今有調度Sc1= 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)w1(B)w2(A) r2 (B)w2(B)再把 r2 (A)與 r1 (B)w1(B)交換： Sc2= r1 (A)w1(A) r1 (B)w1(B) r2 (A)w2(A) r2 (B)w2(B)Sc2等價於一個串行調度T1，T2，Sc1衝突可串行化的調度 衝突可串行化調度是可串行化調度的充分條件，不是必要條件。還有不滿足衝突可串行化條件的可串行化調度，稱為目標可串行化(view serializability)的調度。 [例]有3個事務, L1和L2是目標等價的（view equivalence） T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)調度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一個串行調度。調度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足衝突可串行化。但是調度L2是可串行化的，因為L2執行的結果與調度L1相同，Y的值都等於T2的值，X的值都等於T3的值
可串行化調度兩段鎖協議
事務分為兩個階段
第一階段是獲得封鎖，也稱為擴展階段 。
事務可以申請獲得任何數據項上的任何類型的鎖，但是不能釋放任何鎖 。
第二階段是釋放封鎖，也稱為收縮階段 。
事務可以釋放任何數據項上的任何類型的鎖，但是不能再申請任何鎖。
例
事務Ti遵守兩段鎖協議，其封鎖序列是 ：
Slock A Slock B XlockC Unlock B Unlock A UnlockC；
|← 擴展階段 →| |← 收縮階段 →|
事務Tj不遵守兩段鎖協議，其封鎖序列是：
Slock A Unlock A Slock B XlockC UnlockC Unlock B；
事務遵守兩段鎖協議是可串行化調度的充分條件，而不是必要條件。
若併發事務都遵守兩段鎖協議，則對這些事務的任何併發調度策略都是可串行化的 。
若併發事務的一個調度是可串行化的，不一定所有事務都符合兩段鎖協議 。
兩段鎖協議與防止死鎖的一次封鎖法 。
一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續執行，因此一次封鎖法遵守兩段鎖協議 。
可串行化調度封鎖粒度
封鎖對象的大小稱為封鎖粒度(Granularity)
封鎖的對象：邏輯單元，物理單元
例：在關係數據庫中，封鎖對象：
邏輯單元: 屬性值、屬性值集合、元組、關係、索引項、整個索引、整個數據庫等
物理單元：頁（數據頁或索引頁）、物理記錄等
封鎖粒度與系統的併發度和併發控制的開銷密切相關。
封鎖的粒度越大，數據庫所能夠封鎖的數據單元就越少，併發度就越小，系統開銷也越小；
例
若封鎖粒度是數據頁，事務T1需要修改元組L1，則T1必須對包含L1的整個數據頁A加鎖。如果T1對A加鎖後事務T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。
如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖，不需要互相等待，提高了系統的並行度。
又如，事務T需要讀取整個表，若封鎖粒度是元組，T必須對錶中的每一個元組加鎖，開銷極大。
可串行化調度關鍵詞解釋
可串行化調度調度
調度是一個或多個事務的重要操作按時間排序的一個序列。
例1 考慮兩個事務以及它們的動作按照某些順序執行時的數據庫的影響。T1和T2的重要動作如表1所示。
表1 兩個事務
T1 | T2 |
READ(A,t) | READ(A,s) |
t := t + 100 | s := s*2 |
WRITE(A,t) | WRITE(A,s) |
READ(B,t) | READ(B,s) |
t := t + 100 | s := s*2 |
WRTIE(B,t) | WRITE(B,s) |
可串行化調度串行調度
如果一個調度的動作首先是一個事務的所有動作，然後是另一個事務的所有動作，以此類推，而沒有動作的混合，那麼我們説這一調度是串行的。
例2 對錶1中的事務而言，兩個串口調度，一個是T1在T2前，而另一個是T2是T1之前，初態為A=B=25。
表2 T1在T2前的串行調度
T1 | T2 | A | B |
25 | 25 | ||
READ(A,t) | |||
t := t + 100 | |||
WRITE(A,t) | 125 | ||
READ(B,t) | |||
t := t + 100 | |||
WRTIE(B,t) | 125 | ||
READ(A,s) | |||
s := s*2 | |||
WRITE(A,s) | 250 | ||
READ(B,s) | |||
s := s*2 | |||
WRITE(B,s) | 250 |
表3 T2在T1前的串行調度
T1 | T2 | A | B |
25 | 25 | ||
READ(A,s) | |||
s:=s*2 | |||
WRITE(A,s) | 50 | ||
READ(B,s) | |||
s:=s*2 | |||
WRTIE(B,s) | 50 | ||
READ(A,t) | |||
t:=t+100 | |||
WRITE(A,t) | 150 | ||
READ(B,t) | |||
t:=t+100 | |||
WRITE(B,t) | 150 |
可串行化調度示例
事務的正確性原則告訴我們，每個串行調度都將保持數據庫狀態的一致性。
通常，不管數據庫初態怎樣，一個調度對數據庫狀態的影響都和某個串行調度相同，我們就説這個調度是可串行化的。
例3 表4是例1中事務的一個調度，此調度是可串行化的，但不是串行的。表5不是可串行化的。
表4 一個非串行的可串行化調度
T1 | T2 | A | B |
25 | 25 | ||
READ(A,t) | |||
t := t + 100 | |||
WRITE(A,t) | 125 | ||
READ(A,s) | |||
s := s*2 | |||
WRITE(A,s) | 250 | ||
READ(B,t) | |||
t := t + 100 | |||
WRTIE(B,t) | 125 | ||
READ(B,s) | |||
s := s*2 | |||
WRITE(B,s) | 250 |
表5 一個非串行的非可串行化的調度
T1 | T2 | A | B |
25 | 25 | ||
READ(A,t) | |||
t := t + 100 | |||
WRITE(A,t) | 125 | ||
READ(A,s) | |||
s := s*2 | |||
WRITE(A,s) | 250 | ||
READ(B,s) | |||
s := s*2 | |||
WRITE(B,s) | 50 | ||
READ(B,t) | |||
t := t + 100 | |||
WRTIE(B,t) | 150 |
