基本介紹
- 中文名：可串列化調度
- 外文名：Serializable schedule
- 學科：計算機科學
- 套用：判斷並行事務操作是否正確
- 準則：可串列性
- 協定：兩段所協定、封鎖粒度
調度簡介,事務,衝突操作,兩段鎖協定,封鎖粒度,關鍵字解釋,調度,串列調度,示例,
調度簡介
計算機系統對並發事務中並發操作的調度是隨機的，而不同的調度可能會產生不同的結果。在計算機中，多個事務的並發執行是正確的，若且唯若其結果與按某一次序串列地執行它們時的結果相同，我們稱這種調度策略為可串列化（Serializable）調度。其中可串列性判斷並行事務操作是否正確的判別準則。兩段鎖協定就是保證並發調度可串列性的封鎖協定。
事務
事務是用於訪問和修改各種數據項的一個程式單位。事務也可以被看做是一系列相關讀和寫操作。被訪問的數據可以分散地存放在同一檔案的不同記錄中，也可放在多個檔案中。只有對分布在不同位置的同一數據所進行的讀和寫(含修改)操作全部完成時，才能再以託付操作(Commit Operation)來終止事務。
事務是恢復和並發控制的基本單位。
事務應該具有4個屬性：原子性、一致性、隔離性、持久性。這四個屬性通常稱為ACID特性。
原子性（atomicity）。一個事務是一個不可分割的工作單位，事務中包括的諸操作要么都做，要么都不做。
一致性（consistency）。事務必須是使資料庫從一個一致性狀態變到另一個一致性狀態。一致性與原子性是密切相關的。
隔離性（isolation）。一個事務的執行不能被其他事務干擾。即一個事務內部的操作及使用的數據對並發的其他事務是隔離的，並發執行的各個事務之間不能互相干擾。
持久性（durability）。持久性也稱永久性（permanence），指一個事務一旦提交，它對資料庫中數據的改變就應該是永久性的。接下來的其他操作或故障不應該對其有任何影響。
衝突操作
衝突操作是指不同的事務對同一個數據的讀寫操作和寫寫操作
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；
事務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 |
