數(shù)據(jù)庫(kù)原理十一章課件.ppt

數(shù)據(jù)庫(kù)原理,主講：趙海霞,河南科技大學(xué)電信學(xué)院,第十一章 并發(fā)控制,并發(fā)控制概述 封鎖 封鎖協(xié)議 活鎖和死鎖 并發(fā)調(diào)度的可串行性 兩段鎖協(xié)議 封鎖的粒度,問(wèn)題的產(chǎn)生,多用戶數(shù)據(jù)庫(kù)系統(tǒng)的存在 允許多個(gè)用戶同時(shí)使用的數(shù)據(jù)庫(kù)系統(tǒng) 飛機(jī)定票數(shù)據(jù)庫(kù)系統(tǒng) 銀行數(shù)據(jù)庫(kù)系統(tǒng) 特點(diǎn)：在同一時(shí)刻并發(fā)運(yùn)行的事務(wù)數(shù)可達(dá)數(shù)百個(gè),數(shù)據(jù)庫(kù)系統(tǒng)中的并發(fā),如果事務(wù)順序執(zhí)行，即一個(gè)事務(wù)完全結(jié)束后，另一個(gè)事務(wù)才開(kāi)始，則稱這種執(zhí)行方式為串行訪問(wèn)(serial access) 如果DBMS可以同時(shí)接納多個(gè)事務(wù)，事務(wù)可以在時(shí)間上重疊執(zhí)行，則稱這種執(zhí)行方式為并發(fā)訪問(wèn)(concurrent access),交叉并發(fā)和同時(shí)并發(fā),在單CPU系統(tǒng)中，同一時(shí)間只能有一個(gè)事務(wù)占用CPU，各個(gè)事務(wù)交叉地使用CPU，這種并發(fā)方式稱為交叉并發(fā)(interleaved concurrency) 在多CPU系統(tǒng)中，可以允許多個(gè)事務(wù)同時(shí)占有CPU，這種并發(fā)方式稱為同時(shí)并發(fā)(simultaneous concurrency),并發(fā)的目的,改善系統(tǒng)的資源利用率 對(duì)一個(gè)事務(wù)來(lái)講，在不同的執(zhí)行階段需要不同的資源，有時(shí)需要CPU，有時(shí)需要訪問(wèn)磁盤(pán)，有時(shí)需要通信。如果事務(wù)并發(fā)執(zhí)行，可以交叉地利用這些資源，有利于提高系統(tǒng)的資源利用率 改善短事務(wù)的響應(yīng)時(shí)間,T1,T2,11.1 并發(fā)控制概述,事務(wù)ACID特性可能遭到破壞的原因之一是多個(gè)事務(wù)對(duì)數(shù)據(jù)庫(kù)的并發(fā)操作 DBMS的并發(fā)控制子系統(tǒng)負(fù)責(zé)協(xié)調(diào)并發(fā)事務(wù)的執(zhí)行，保證數(shù)據(jù)庫(kù)的一致性不受破壞。同時(shí)避免用戶得到不正確的數(shù)據(jù)。,T1 T2 Tn,DB (consistency constraints),示例,結(jié)果明明賣(mài)出兩張機(jī)票，數(shù)據(jù)庫(kù)中機(jī)票余額只減少1,機(jī)票數(shù)量A,A=16,A=15,A=15,售票點(diǎn),售票點(diǎn),A=16,A=16,出售1,出售1,事務(wù)甲,事務(wù)乙,示例（續(xù)）,這種情況稱為數(shù)據(jù)庫(kù)的不一致性，是由并發(fā)操作引起的。 在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的。 若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。 原因：第4步中乙事務(wù)修改A并寫(xiě)回后覆蓋了甲事務(wù)的修改,事務(wù)并發(fā)操作帶來(lái)的問(wèn)題,并發(fā)操作引起的數(shù)據(jù)不一致性包括三類(lèi) 丟失修改 不可重復(fù)讀 讀臟數(shù)據(jù),事務(wù)并發(fā)帶來(lái)的丟失修改,A、丟失修改問(wèn)題 兩個(gè)事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失。 上面飛機(jī)訂票例子就屬此類(lèi),A、丟失修改問(wèn)題,A的初值為16，事務(wù)T1對(duì)A減1，事務(wù)T2對(duì)A減1 。,在時(shí)間t7丟失了事務(wù)T1的更新。,事務(wù)并發(fā)帶來(lái)的丟失修改,并發(fā)操作引起的不可重復(fù)讀,B、不可重復(fù)讀 不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無(wú)法再現(xiàn)前一次讀取結(jié)果。,并發(fā)操作引起的不可重復(fù)讀,B、不可重復(fù)讀 不可重復(fù)讀包括三種情況： (1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值,T1 讀A=1,B=2 求A+B=3 讀A=1,B=4 求A+B=5,T2 讀B=2 B=B*2 寫(xiě)回B=4,并發(fā)操作引起的不可重復(fù)讀,（2）事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄消失了 (3)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（Phantom Row）,事務(wù)并發(fā)帶來(lái)的讀臟數(shù)據(jù),C、讀“臟”數(shù)據(jù) 讀“臟”數(shù)據(jù)是指： 事務(wù)T1修改某一數(shù)據(jù)，并將其寫(xiě)回磁盤(pán) 事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷(xiāo) 這時(shí)T1已修改過(guò)的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)不一致 T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù),C、讀“臟”數(shù)據(jù),事務(wù)T1對(duì)C乘2，但未提交，事務(wù)T4讀未提交的A值，而T1做ROLLBACK操作。,在時(shí)間t4，事務(wù)T4讀了未提交的值。,事務(wù)并發(fā)帶來(lái)的讀臟數(shù)據(jù),小結(jié),產(chǎn)生上述三類(lèi)不一致性的主要原因 并發(fā)操作破壞了事務(wù)的隔離性，事務(wù)間相互干擾 三種主要解決技術(shù) 封鎖技術(shù) (Locking) 時(shí)間戳技術(shù)(Timestamp) 樂(lè)觀控制法 商用的DBMS一般都采用封鎖方法,11.2 封鎖,概念 事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象(如數(shù)據(jù)庫(kù)、表、記錄等)操作之前，首先向系統(tǒng)發(fā)出加鎖請(qǐng)求以便獲得對(duì)數(shù)據(jù)對(duì)象相應(yīng)的控制 在事務(wù)T釋放它所獲得的鎖之前，其他事務(wù)不能更新此數(shù)據(jù)對(duì)象,鎖的類(lèi)型,一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制由封鎖的類(lèi)型決定。 排它鎖(eXclusive lock)：寫(xiě)鎖 若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類(lèi)型的鎖，直到T釋放A上的鎖 保證其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A 共享鎖(Share lock)：讀鎖 若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則事務(wù)T可以讀A但不能修改A，其它事務(wù)只能再對(duì)A加S鎖，而不能加X(jué)鎖，直到T釋放A上的S鎖 保證其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對(duì)A做任何修改,鎖的相容矩陣,Y：相容的請(qǐng)求 N：不相容的請(qǐng)求,T1,T2,T1,T2,T1,T2,Xlock A,獲得Xlock A,讀A = 16,A = A -1,寫(xiě)回A = 15,Commit,Unlock A,Xlock A,等待,等待,獲得Xlock A,讀A = 15,Commit,Unlock A,等待,等待,A = A -1,寫(xiě)回A = 14,Slock A,Slock B,讀A = 50,求和 = 150,讀A = 50,Commit,Unlock A,Xlock B,等待,等待,獲得Xlock B,讀B = 100,Commit,Unlock B,等待,等待,B = B * 2,寫(xiě)回B = 200,讀B = 100,讀B = 100,求和 = 150,Unlock B,等待,等待,等待,等待,Xlock C,讀C = 100,C= C * 2,寫(xiě)回C = 200,Rollback (C恢復(fù)為100),Unlock C,Slock C,等待,等待,獲得Slock C,讀C = 100,Commit,Unlock C,等待,沒(méi)有丟失修改,可重復(fù)讀,不讀臟數(shù)據(jù),用封鎖機(jī)制解決三種數(shù)據(jù)不一致性的示例,11.3 活鎖和死鎖問(wèn)題,封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)題，但也帶來(lái)一些新的問(wèn)題 死鎖 活鎖,活鎖問(wèn)題,活鎖 舉例說(shuō)明： 事務(wù)T1封鎖某數(shù)據(jù)后，事務(wù)T2請(qǐng)求封鎖未獲得并等待，而T1釋放鎖后，事務(wù)T3請(qǐng)求封鎖并獲得，T3釋放鎖后，事務(wù)T4請(qǐng)求封鎖并獲得T2可能永遠(yuǎn)等待 解決辦法：采用先來(lái)先服務(wù)的策略,死鎖問(wèn)題,死鎖 舉例說(shuō)明： 事務(wù)T1和T2各自封鎖了數(shù)據(jù)R1和R2后，又各自請(qǐng)求封鎖R2和R1，因都無(wú)法獲得而等待對(duì)方釋放的現(xiàn)象 解決的兩類(lèi)方法 預(yù)防死鎖 允許發(fā)生死鎖，采用一定手段定期診斷并解除死鎖,死鎖的預(yù)防,一次封鎖法 辦法：每個(gè)事務(wù)一次將所有要使用的數(shù)據(jù)全部加鎖 存在問(wèn)題？降低系統(tǒng)并發(fā)度；難于事先精確確定封鎖對(duì)象 順序封鎖法 辦法：預(yù)先規(guī)定數(shù)據(jù)對(duì)象的封鎖順序，所有事務(wù)均按此順序 存在問(wèn)題？維護(hù)成本：數(shù)據(jù)庫(kù)系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極多，并且在不斷地變化；難以實(shí)現(xiàn)：很難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象,在操作系統(tǒng)上廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫(kù)的特點(diǎn) 因此DBMS普遍采用診斷并解除死鎖的辦法,死鎖的診斷與解決,死鎖的診斷 超時(shí)法 辦法：等待時(shí)間超過(guò)規(guī)定的時(shí)限 問(wèn)題？ 等待圖法 辦法：畫(huà)等待圖，發(fā)現(xiàn)回路 死鎖的解決 檢測(cè)到死鎖，選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，強(qiáng)行撤銷(xiāo)，使其它事務(wù)可以繼續(xù)下去 恢復(fù)撤銷(xiāo)事務(wù)所執(zhí)行的數(shù)據(jù)修改操作,11.4 事務(wù)調(diào)度的可串行性,引言 DBMS對(duì)并發(fā)事務(wù)不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果 什么樣的調(diào)度是正確的？ 概念 可串行化的調(diào)度：多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同 可串行性是并發(fā)事務(wù)操作是否正確的判別準(zhǔn)則,事務(wù)調(diào)度的可串行性,為了保證并發(fā)操作的正確性，DBMS的并發(fā)控制機(jī)制必須提供一定的手段來(lái)保證調(diào)度是可串行化的 保證事務(wù)調(diào)度可串行性的策略 事務(wù)排它式執(zhí)行(資源無(wú)法充分共享) 兩段鎖(Two-Phase Locking, 2PL)協(xié)議 其它，如時(shí)間戳(TimeStamp)方法等 DBMS普通采用封鎖方法實(shí)現(xiàn)并發(fā)操作調(diào)度的可串行性,并發(fā)事務(wù)的不同調(diào)度策略,T1,T2,T1,T2,T1,T2,Slock B,Y = B = 2,Unlock B,Xlock A,A = Y + 1,寫(xiě)回A(=3),Unlock A,X = A = 3,Unlock A,寫(xiě)回B(=4),Unlock B,Slock A,Xlock B,B = X + 1,a 串行調(diào)度,c 不可串行化的調(diào)度 (結(jié)果與a,b不同，錯(cuò)誤調(diào)度),Slock B,Y = B = 2,Unlock B,Xlock A,A = Y + 1,寫(xiě)回A(=3),Unlock A,X = A = 2,Unlock A,寫(xiě)回B(=3),Unlock B,Slock A,Xlock B,B = X + 1,Slock B,Y = B = 2,Unlock B,Xlock A,A = Y + 1,寫(xiě)回A(=3),Unlock A,Slock A,X = A = 3,Unlock A,寫(xiě)回B(=4),Unlock B,Xlock B,B = X + 1,等待,等待,等待,T1,T2,Slock B,Y = B = 3,Unlock B,Xlock A,A = Y + 1,寫(xiě)回A(=4),Unlock A,X = A = 2,Unlock A,寫(xiě)回B(=3),Unlock B,Slock A,Xlock B,B = X + 1,d 可串行化的調(diào)度 (結(jié)果與a相同，正確調(diào)度),T1: 讀B; A=B+1; 寫(xiě)回A; T2: 讀A; B=A+1; 寫(xiě)回B; A,B初值均為2,b 串行調(diào)度,沖突可串行化調(diào)度,可串行化調(diào)度的充分條件 一個(gè)調(diào)度Sc在保證沖突操作的次序不變的情況下，通過(guò)交換兩個(gè)事務(wù)不沖突操作的次序得到另一個(gè)調(diào)度Sc，如果Sc是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度 一個(gè)調(diào)度是沖突可串行化，一定是可串行化的調(diào)度,沖突可串行化調(diào)度（續(xù)）,沖突操作 沖突操作是指不同的事務(wù)對(duì)同一個(gè)數(shù)據(jù)的讀寫(xiě)操作和寫(xiě)寫(xiě)操作 Ri (x)與Wj(x) /* 事務(wù)Ti讀x，Tj寫(xiě)x*/ Wi(x)與Wj(x) /* 事務(wù)Ti寫(xiě)x，Tj寫(xiě)x*/ 其他操作是不沖突操作 不同事務(wù)的沖突操作和同一事務(wù)的兩個(gè)操作不能交換(Swap),沖突可串行化調(diào)度（續(xù)）,例今有調(diào)度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)交換： Sc2r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Sc2等價(jià)于一個(gè)串行調(diào)度T1，T2，Sc1沖突可串行化的調(diào)度,沖突可串行化調(diào)度（續(xù)）,沖突可串行化調(diào)度是可串行化調(diào)度的充分條件，不是必要條件。還有不滿足沖突可串行化條件的可串行化調(diào)度。 例有3個(gè)事務(wù) T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X) 調(diào)度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一個(gè)串行調(diào)度。 調(diào)度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖突可串行化。但是調(diào)度L2是可串行化的，因?yàn)長(zhǎng)2執(zhí)行的結(jié)果與調(diào)度L1相同，Y的值都等于T2的值，X的值都等于T3的值,11.5 兩段鎖協(xié)議,封鎖協(xié)議 運(yùn)用封鎖方法時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請(qǐng)封鎖 持鎖時(shí)間 何時(shí)釋放封鎖等 兩段封鎖協(xié)議(Two-Phase Locking，簡(jiǎn)稱2PL)是最常用的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可串行化調(diào)度,兩段鎖協(xié)議（續(xù)）,概念：事務(wù)對(duì)數(shù)據(jù)項(xiàng)的加鎖和解鎖分為兩個(gè)階段完成 獲得封鎖：在對(duì)數(shù)據(jù)讀寫(xiě)之前首先申請(qǐng)并獲得封鎖； 釋放封鎖：在釋放一個(gè)封鎖后不再申請(qǐng)和獲得任何其他封鎖,兩段鎖協(xié)議（續(xù)）,兩段”鎖的含義 事務(wù)分為兩個(gè)階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段 事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類(lèi)型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類(lèi)型的鎖，但是不能再申請(qǐng)任何鎖,兩段鎖協(xié)議（續(xù)）,如遵守兩段鎖協(xié)議的事務(wù) Slock A Slock B Xlock C . Unlock B Unlock A Unlock C 如不遵守兩段鎖協(xié)議的事務(wù) Slock A Unlock A Slock B . Xlock C Unlock C Unlock B,兩段鎖協(xié)議的性質(zhì),兩段鎖協(xié)議是可串行化調(diào)度的充分條件，但不是必要條件 若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的； 若對(duì)并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都符合兩段鎖協(xié)議 兩段鎖協(xié)議可以保證并發(fā)事務(wù)的正確性，但可能發(fā)生死鎖,T1,T2,T1,T2,T1,T2,Slock B,讀B=2,Y=B,A = Y+1,寫(xiě)回A = 3,Unlock B,Unlock A,Slock A,等待,等待,讀A = 3,Unlock B,Unlock A,等待,等待,Y = A,寫(xiě)回B(=4),Slock B,讀B=2,Y=B,Xlock A,A=Y+1,Slock A,等待,等待,讀A = 3,Xlock B,B=X+1,等待,等待,X = A,Unlock A,Unlock B,寫(xiě)回A(=3),Unlock A,Slock B,讀B = 2,Xlock A,Slock A,等待,Xlock B,等待,可串行調(diào)度 遵守兩段鎖協(xié)議,可串行調(diào)度 不遵守兩段鎖協(xié)議,遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖,關(guān)于兩段鎖協(xié)議,Xlock A,等待,Xlock B,B=Y+1,寫(xiě)回B(=4),Unlock B,讀A = 2,等待,11.6 封鎖的粒度,封鎖的粒度即封鎖對(duì)象的大小，如 邏輯單元：屬性、元組、關(guān)系、索引、數(shù)據(jù)庫(kù)等 物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、 塊等,封鎖粒度與系統(tǒng)并發(fā)的關(guān)系,封鎖的數(shù)據(jù)單元就越,封鎖的粒度越,少,并發(fā)度就越,系統(tǒng)的開(kāi)銷(xiāo)也越,大,低,小,封鎖的數(shù)據(jù)單元就越,封鎖的粒度越