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

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