Conflic Serializability
定義Conflicting Operations：
定義Conlict Serializable：
如果某種調(diào)度S使得事務(wù)的前驅(qū)圖是無(wú)環(huán)的，那么說(shuō)明這個(gè)調(diào)度S是conflict serializable，如果有環(huán)，則說(shuō)明這個(gè)調(diào)度S不滿足conflict serializable。
Strict Two Phase Locking 就是在2PL的基礎(chǔ)之上，增加以下限制：
all locks are released together when transaction completes, either:
- Transaction has committed. OR
- Transaction has aborted.
以解決Cascading Aborts的問(wèn)題。
需要思考，為什么滿足無(wú)環(huán)，就是可串行的？因?yàn)榭梢酝ㄟ^(guò)移動(dòng)操作，使得兩個(gè)T1和T2和串行的結(jié)果一樣。見(jiàn)https://www.youtube.com/watch?v=h8Xzy6DANzw
兩階段鎖
兩階段鎖是數(shù)據(jù)庫(kù)事務(wù)中的一種concurrency control method，它可以保證多個(gè)事務(wù)的可串行化（serializability）。說(shuō)白了就是保證事務(wù)的ACID。兩階段鎖協(xié)議可以保證調(diào)度是滿足Conlict Serializable的。
兩段鎖協(xié)議是指每個(gè)事務(wù)的執(zhí)行可以分為兩個(gè)階段：生長(zhǎng)階段（加鎖階段）和衰退階段（解鎖階段）。
加鎖階段：在該階段可以進(jìn)行加鎖操作。在對(duì)任何數(shù)據(jù)進(jìn)行讀操作之前要申請(qǐng)并獲得S鎖，在進(jìn)行寫(xiě)操作之前要申請(qǐng)并獲得X鎖。加鎖不成功，則事務(wù)進(jìn)入等待狀態(tài)，直到加鎖成功才繼續(xù)執(zhí)行。
解鎖階段：當(dāng)事務(wù)釋放了一個(gè)封鎖以后，事務(wù)進(jìn)入解鎖階段，在該階段只能進(jìn)行解鎖操作不能再進(jìn)行加鎖操作。
另外要注意兩段鎖協(xié)議和防止死鎖的一次封鎖法的異同之處。一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議；但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖。
可以證明，若并發(fā)執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的。
我們可以證明，在使用兩段鎖協(xié)議的情況下，T1、T2、Tn的前驅(qū)圖里，是不會(huì)有環(huán)路出現(xiàn)的。證明的方法可以用反證法。不妨假設(shè)T1 T2 T3的前驅(qū)圖，形成了一個(gè)環(huán)：T1 -> T2 -> T3 -> T1，并且T1、T2、T3都遵守兩段鎖，那么就有下圖：
A、B、C是需要加鎖的資源。
t1 t2 t3...t7是各個(gè)事務(wù)中加鎖、解鎖的時(shí)間。
由兩階段鎖的協(xié)議可知，T1必須釋放了A的鎖，T2才可能加上A的鎖，所以t2<t3。同理，可知：
t1 < t2 < t3 < t4 < t5 < t6 < t7。
t2是release(A)操作，t7是lock(c)操作，我們知道兩階段鎖協(xié)議中，開(kāi)始release鎖后，就不再允許加鎖了，得出矛盾。
