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