數據庫的并發控制
?
?
1、為什么要進行并發控制
?
??? 數據庫是共享資源，通常有許多個事務同時在運行。當多個事務并發地存取數據庫時就會產生同時讀取/修改同一數據的情況。若對并發操作不加控制就可能會存取和存儲不正確的數據，破壞數據庫的一致性。所以數據庫管理系統必須提供并發控制機制。
?
??? 在單處理機系統中，事務的并行執行實際上是這些并行事務的并行操作輪流交叉運行，稱為交叉并發方式。
??? 在多處理機系統中，每個處理機可以運行一個事務，多個處理機可以同時運行多個事務，實現多個事務真正的并行運行，稱為同時并發方式。
?
??? 使用并發的目的：一是改善系統的資源利用率，二是改善短事務的響應時間。
?
2、并發操作可能會產生哪幾類數據不一致？用什么方法能避免？
??? 并發操作帶來的數據不一致性包括三類：丟失修改、不可重復讀、讀“臟”數據。
??? (1)丟失修改<lost update>：兩個事務T1和T2讀入同一數據并修改，T2提交的結果破壞了(覆蓋了)T1提交的結果，導致T1的修改被丟失。
????? --丟失修改是“寫-寫沖突”
??? (2)不可重復讀<Non-Repeatable Read>：不可重復讀是指事務T1讀取數據后，事務執行更新操作，使T1無法再現前一次讀取結果。
????? --不可重復讀是“讀-寫沖突”
??? (3)讀“臟”數據<Dirty Read>：讀“臟”數據是指事務T1修改某一數據，并將其寫回磁盤，事務讀取同一數據后，T1由于某種原因被撤銷，這時T1已修改過的數據恢復原值，讀到的數據就與數據庫中的數據不一致，則讀到的數據就為“臟”數據，即不正確的數據。
????? --讀“臟”數據是“讀-寫沖突”
?
??? 避免不一致性的方法和技術就是并發控制。最常用的并發控制技術是封鎖技術。也可以用其他技術，例如在分布式數據庫系統中可以采用時間戳方法來進行并發控制。它的任務就是用正確的方式調度并發操作，使一個用戶事務的執行不受其它事務的干擾，避免造成數據的不一致性。
3、什么是封鎖？基本的封鎖類型及其含義？
?
??? 封鎖就是事務 T 在對某個數據對象例如表、記錄等操作之前，先向系統發出請求，對其加鎖。加鎖后事務 T 就對該數據對象有了一定的控制，在事務 T 釋放它的鎖之前，其他的事務不能更新此數據對象。
??? 封鎖是實現并發控制的一個非常重要的技術。
?
??? 封鎖類型：排它鎖(Exclusive Locks|X鎖)和共享鎖(Share Locks|S鎖)
??? 排它鎖：又稱寫鎖，若事務 T 對數據對象 A 加上 X 鎖，則只允許 T 讀取和修改 A，其它任何事務都不能再對 A 加任何類型的鎖，直到 T 釋放 A 上的 X 鎖。
??? 共享鎖：又稱讀鎖，若事務 T 對數據對象 A 加上 S 鎖，則事務 T 可以讀 A 但不能修改 A，其它事務只能再對 A 加 S 鎖，而不能加 X 鎖，直到 T 釋放 A 上的 S 鎖。
?
??? X鎖和S鎖的相容矩陣：(最左邊表示T1已經獲得的鎖的類型，最上面表示T2的封鎖請求，-表示沒有加鎖)
?
|
??? T2
?T1
|
S
|
X
|
-
|
|
S
|
Y
|
N
|
Y
|
|
X
|
N
|
N
|
Y
|
|
-
|
Y
|
Y
|
Y
|
?
?
4、封鎖協議的類型和概念
?
??? 一級封鎖協議：事務 T 在修改數據 R 之前必須先對其加 X 鎖，直到事務結束才釋放。事務結束包括正常結束(COMMIT)和非正常結束(ROLLBACK)。
??? ----一級封鎖協議中，如果是讀數據不修改，是不需要加鎖的，可防止丟失修改。
?
沒有丟失修改：
|
T1
|
T2
|
|
① Xlock A
|
|
|
??????? 獲得
|
|
|
② 讀A=16
|
|
|
|
Xlock A
|
|
③A←A-1
|
等待
|
|
??????? 寫回
|
等待
|
|
A=15
|
等待
|
|
??? Commit
|
等待
|
|
??? Unlock A
|
等待
|
|
④
|
獲得Xlock A
|
|
|
讀A=15
|
|
|
A←A-1
|
|
|
寫回A=14
|
|
⑤
|
Commit
|
|
|
Unlock A
|
?
不能重復讀：
|
T1
|
T2
|
|
①讀A=50
|
|
|
?? 讀B=150
|
|
|
?? 求和 =150
|
|
|
②
|
? Xlock B
|
|
|
??? 獲得?
|
|
|
??? 讀B=100
|
|
|
??? B←B*2
|
|
|
????? 寫回
|
|
|
B=200
|
|
|
? Commit
|
|
|
? Unlock B
|
|
③讀A=50
|
|
|
?? 讀B=200
|
|
|
?? 求和 =250
|
|
|
?(驗算不對)
|
|
?
??? 二級封鎖協議：在一級封鎖協議基礎上，加上事務T在讀數據R之前必須先對其加上S鎖，讀完后即可釋放S鎖。
??? ----在二級封鎖協議中，由于讀完數據后即可釋放S鎖，所以它不能保證可重復讀。
?
依舊不可重復讀：
|
T1
|
T2
|
|
①Slock A
|
|
|
????? 獲得
|
|
|
????? 讀A=50
|
|
|
??? Unlock A
|
|
|
②Slock B
|
|
|
????? 獲得
|
Xlock B
|
|
????? 讀B=100
|
等待
|
|
??? Unlock B
|
獲得Xlock B
|
|
③求和 =150
|
讀B=100
|
|
|
B←B*2
|
|
|
寫回B=200
|
|
|
Commit?
|
|
|
Unlock B?
|
|
④Slock A
|
|
|
????? 獲得
|
|
|
????? 讀A=50
|
|
|
??? Unlock A
|
|
|
??? Slock B
|
|
|
????? 獲得
|
|
|
????? 讀B=200
|
|
|
??? Unlock B
|
|
|
??? 求和=250
|
|
|
?(驗算不對)
|
|
?
??? 三級封鎖協議：一級封鎖協議加上事務T在讀取數據R之前必須先對其加S鎖，直到事務結束才釋放。
??? ----三級封鎖協議除了防止了丟失修改和不讀“臟”數據外，還進一步防止了不可重復讀。?
?
可重復讀：
|
T1
|
T2
|
|
①Slock A
|
|
|
????? 讀A=50
|
|
|
? Slock B
|
|
|
????? 讀B=100
|
|
|
? 求和 =150
|
|
|
②
|
Xlock B
|
|
|
等待
|
|
③? 讀A=50
|
等待
|
|
????? 讀B=100
|
等待
|
|
????? 求和=150
|
等待
|
|
??? Commit
|
等待
|
|
??? Unlock A
|
等待
|
|
??? Unlock B
|
等待
|
|
④
|
獲得Xlock B
|
|
|
讀B=100
|
|
|
B←B*2
|
|
|
寫回B=200
|
|
|
??? Commit
|
|
|
??? Unlock B
|
?
不讀“臟”數據：
|
T1
|
T2
|
|
①Xlock C
|
|
|
????? 讀A=100
|
|
|
????? C←C*2
|
|
|
????? 寫回C=200
|
|
|
②
|
Slock C
|
|
|
等待
|
|
③ROLLBACK
|
等待
|
|
? (C恢復為100)
|
等待
|
|
? Unlock C
|
等待
|
|
④
|
獲得Slock C
|
|
|
讀C=100
|
|
|
Commit C
|
|
⑤
|
Unlock C
|
?
封鎖協議總結：
|
|
X鎖
|
S鎖
|
一致性保證
|
|
|
操作結束釋放
|
事務結束釋放
|
操作結束釋放
|
事務結束釋放
|
不丟失修改
|
不讀臟數據
|
可重復讀
|
|
1級封鎖
|
|
√
|
|
|
√
|
|
|
|
2級封鎖
|
|
√
|
√
|
|
√
|
√
|
|
|
3級封鎖
|
|
√
|
|
√
|
√
|
√
|
√
|
?
?
5、什么是“活鎖”？什么是“死鎖”？以及避免方法。
?
??? 若某數據對象加了 S 鎖，這時若有其它事務申請對它的 X 鎖，則需等待。但此時若有其它事務申請對它的 S 鎖，按相容矩陣，應可獲準。如果不斷有事務申請對此數據對象的 S 鎖，以致它始終被 S 鎖占有，而 X 鎖的申請遲遲不能獲準——這種現象叫活鎖。
??? 避免活鎖的簡單方法是采用“先來先服務”策略，即T1用S鎖鎖住A，T2申請X鎖等待，此時T3申請S鎖也不獲準，因為T2尚未得到服務。
?
??? 一個事務如果申請鎖而未獲準，則需等待其它事務釋放鎖。如果事務中出現循環等待時，如果不加干預，則會一直等待下去——這叫死鎖。
??? 避免死鎖主要有兩種方法：一次封鎖法 & 順序封鎖法
?
???
一次封鎖法
：要求每個事務必須一次將所有要使用的數據全部加鎖。
??? 缺點：
??? 1.有些數據對象過早的加鎖，降低了并發度。
??? 2.如果有些事務需要訪問的“熱點”數據比較多，其它事務總是不斷的占有其中某些數據，不能一次獲得所需要數據的全部，就會一直等待下去，易發生活鎖。
??? 3.難以確定封鎖對象
?
??? 順序封鎖法：預先對數據對象規定一個封鎖順序,所有事務都按這個順序實行封鎖.
??? 缺點:
??? 1.數據庫中一般是按內容訪問，而不是按名訪問，所以很難預先確定所有的訪問對象
??? 2.數據經常變動，次序也經常調整，維護成本很高
?
??? 總得來說，以上這兩種在操作系統中廣泛使用的預防死鎖策略都不太適合在數據庫中使用，在數據庫中使用比較廣泛的方法是：診斷&解除。
具體來說就是允許死鎖的發生，但設置規則診斷出現死鎖后即進行解除。
?
6、列舉死鎖的診斷方法以及解除方法？
?
??? 死鎖診斷主要有以下兩種方法：
?
??? 超時法：如果一個事務的等待時間超過了某個時限，就認為發生死鎖。
??? 優點：簡單
??? 缺點：一是事務因其它原因(如系統負荷太重,通信受阻等)而使事務等待時間超過時限，可能被誤判死鎖。二是時限的設置。
?
??? 等待圖法：等待圖是一個有向圖G=(T,U)。T為結點的集合，每個結點表示正在運行的事務；U為邊的集合，每條邊表示事務等待的情況。當且僅當等待圖中出現回路時，死鎖發生。
??? 優點：比較準確
??? 缺點：維護成本高
?
??? 死鎖的解除方法(必須由DBMS干預)：
?
??? 1.在循環等待的事務中，選一個事務作為“犧牲者”，給其它事務讓路
??? 2.撤銷犧牲的事務，釋放其獲得的鎖及其它資源
??? 3.將釋放的鎖讓給等待它的事務
??? 4.被犧牲的事務可以有兩種處理：
??????? * 發消息給有關用戶，由用戶向系統再交付該事務
??????? * 由DBMS重新啟動該事務
??? 注：被犧牲的事務應等待一段時間才能交付系統，否則可能再發生死鎖。
??? 犧牲者的選擇方法：
?
??? 1.選擇最遲交付的事務作為犧牲者
??? 2.選擇獲得鎖最少的事務作為犧牲者
??? 3.選擇撤銷代價最小的事務作為犧牲者?
?
7、什么樣的并發調度是正確的調度？
?
??? 可串行化 (Serializable) 的調度是正確的調度。
??? 可串行化的調度的定義：多個事務的并發執行是正確的，當且僅當其結果與按某一次序串行執行它們時的結果相同，稱這種調度策略為可串行化的調度。
??? 注：一般不可串行化的并發調度產生的結果都會與串行調度結果有誤差。
?
??? 兩段鎖協議(2PL)是保證并發調度可串行化的封鎖協議。
?
??? 兩段鎖協議是指所有事務必須分兩個階段對是數據項加鎖和解鎖。
??? 在對任何數據進行讀、寫操作之前，首先要申請并獲得對該數據的封鎖——擴展階段
??? 在釋放一個封鎖之后，事物不再申請和獲得任何其它封鎖——收縮階段
??? 若并發執行的所有事務均遵守兩段鎖協議，則對這些事務的任何并發調度策略都可是可串行化。(充分條件)(可用反證法證明)
?
??? 兩段鎖協議和一次封鎖法的異同：
??? 一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，因此遵守兩段鎖協議
??? 兩段鎖協議并不要求事務必須一次將所有要使用的數據全部加鎖，因此可能會發生死鎖?
?
??? 證明若并發事務遵守兩段鎖協議，則對這些事務的并發調度是可串行化的
?
??? 首先以兩個并發事務 Tl 和T2為例，存在多個并發事務的情形可以類推。根據可串行化定義可知，事務不可串行化只可能發生在下列兩種情況：
???
(l) 事務 Tl 寫某個數據對象 A ，T2讀或寫 A ;
??? (2) 事務 Tl 讀或寫某個數據對象 A ，T2寫 A 。
?
??? 下面稱 A 為潛在沖突對象。
?
??? 設 Tl 和T2訪問的潛在沖突的公共對象為{A1,A2,…,An}。不失一般性，假設這組潛在沖突對象中 X ={A1,A2,…,Ai}均符合情況(1)，Y ={Ai+1,…,An｝符合情況(2)。
?
??? Tl 需要 XlockX ①
??? T2 需要 Slockx 或 Xlockx ②
?
??? 1) 如果操作①先執行，則 Tl 獲得鎖，T2等待，由于遵守兩段鎖協議，Tl 在成功獲得 X 和 Y 中全部對象及非潛在沖突對象的鎖后，才會釋放鎖。這時如果存在 w∈X 或 Y ，T2已獲得 w 的鎖，則出現死鎖；否則，Tl 在對X、Y中對象全部處理完畢后，T2才能執行。這相當于按 Tl 、T2的順序串行執行，根據可串行化定義，Tl 和T2的調度是可串行化的。
?
??? 2) 操作 ② 先執行的情況與(l)對稱因此，若并發事務遵守兩段鎖協議，在不發生死鎖的情況下，對這些事務的并發調度一定是可串行化的。證畢。
8、為什么要引進意向鎖？意向鎖的含義是什么？
?
??? 引進意向鎖是為了提高封鎖子系統的效率。該封鎖子系統支持多種封鎖粒度。
?
??? 原因是：在多粒度封鎖方法中一個數據對象可能以兩種方式加鎖——顯式封鎖和隱式封鎖。因此系統在對某一數據對象加鎖時不僅要檢查該數據對象上有無(顯式和隱式)封鎖與之沖突，還要檢查其所有上級結點和所有下級結點，看申請的封鎖是否與這些結點上的(顯式和隱式)封鎖沖突。顯然，這樣的檢查方法效率很低。為此引進了意向鎖。
?
???
意向鎖
的含義是：對任一結點加鎖時，必須先對它的上層結點加意向鎖。例如事務 T 要對某個元組加 X 鎖，則首先要對關系和數據庫加 ix 鎖。換言之，對關系和數據庫加 ix 鎖，表示它的后裔結點——某個元組擬(意向)加 X 鎖。
?
??? 引進意向鎖后，系統對某一數據對象加鎖時不必逐個檢查與下一級結點的封鎖沖突了。例如，事務 T 要對關系 R 加 X 鎖時，系統只要檢查根結點數據庫和 R 本身是否已加了不相容的鎖(如發現已經加了 ix ，則與 X 沖突)，而不再需要搜索和檢查 R 中的每一個元組是否加了 X 鎖或 S 鎖。
?
?
?
?
?
附錄：
---------
比較詳細的PPT介紹：
?
解題答案來源：
?
?
?
?