第17講事務(wù)并發(fā)控制

1、第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制數(shù)據(jù)庫(kù)原理與應(yīng)用第第8章章 事務(wù)管理事務(wù)管理 并發(fā)控制并發(fā)控制 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制本章內(nèi)容本章內(nèi)容 事務(wù)的概念事務(wù)的概念 事務(wù)管理事務(wù)管理 恢復(fù)恢復(fù) 并發(fā)控制并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制事務(wù)的概念及其特性原子性、一致性、隔離性、持久性原子性、一致性、隔離性、持久性恢復(fù)技術(shù)日志文件日志文件數(shù)據(jù)轉(zhuǎn)儲(chǔ)數(shù)據(jù)轉(zhuǎn)儲(chǔ)回顧回顧第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制故障及恢復(fù)事務(wù)內(nèi)部故障的恢復(fù)事務(wù)內(nèi)部故障的恢復(fù)UNDO系統(tǒng)故障的恢復(fù)系統(tǒng)故障的恢復(fù)UNDO + REDO介質(zhì)故障的恢復(fù)介質(zhì)故障的恢復(fù)重裝后備副本重裝后備副本+

2、 REDO（ UNDO + REDO）回顧回顧第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制回顧回顧一致性一致性原子性原子性隔離性隔離性持久性持久性并發(fā)事務(wù)并發(fā)事務(wù)的交錯(cuò)執(zhí)的交錯(cuò)執(zhí)行行故障故障恢復(fù)技術(shù)恢復(fù)技術(shù)并發(fā)控制并發(fā)控制故障故障一致性一致性 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制事務(wù)的特性 隔離性隔離性（ Isolation ） 多事務(wù)并發(fā)執(zhí)行的整體效果必須等同于某一多事務(wù)并發(fā)執(zhí)行的整體效果必須等同于某一次序下事務(wù)順序（串行）執(zhí)行的效果。次序下事務(wù)順序（串行）執(zhí)行的效果。回顧回顧第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制本章內(nèi)容本章內(nèi)容 事務(wù)的概念事務(wù)的概念 事務(wù)管理事務(wù)管理 恢復(fù)恢復(fù) 并

3、發(fā)控制并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)事務(wù)的必要性 事務(wù)在執(zhí)行過(guò)程中需要不同的資源。事務(wù)在執(zhí)行過(guò)程中需要不同的資源。 事務(wù)串行執(zhí)行，許多系統(tǒng)資源會(huì)處于空事務(wù)串行執(zhí)行，許多系統(tǒng)資源會(huì)處于空閑狀態(tài)。閑狀態(tài)。 為充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享為充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn)，允許多個(gè)事務(wù)并行地執(zhí)行資源的特點(diǎn)，允許多個(gè)事務(wù)并行地執(zhí)行.并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制 當(dāng)多用戶并發(fā)地存取數(shù)據(jù)庫(kù)時(shí)就會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)當(dāng)多用戶并發(fā)地存取數(shù)據(jù)庫(kù)時(shí)就會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情況，并發(fā)執(zhí)行的事務(wù)之間的相互影存取同一數(shù)據(jù)的

4、情況，并發(fā)執(zhí)行的事務(wù)之間的相互影響可能導(dǎo)致數(shù)據(jù)庫(kù)狀態(tài)的不一致。響可能導(dǎo)致數(shù)據(jù)庫(kù)狀態(tài)的不一致。各個(gè)事務(wù)的一致性并不能保證數(shù)據(jù)庫(kù)就處于一致性的各個(gè)事務(wù)的一致性并不能保證數(shù)據(jù)庫(kù)就處于一致性的狀態(tài)，并發(fā)執(zhí)行的事務(wù)間還必須具有隔離性。狀態(tài)，并發(fā)執(zhí)行的事務(wù)間還必須具有隔離性。保證并發(fā)執(zhí)行的事務(wù)能保持隔離性的整個(gè)過(guò)程稱為并保證并發(fā)執(zhí)行的事務(wù)能保持隔離性的整個(gè)過(guò)程稱為并發(fā)控制（發(fā)控制（concurrency-control）。）。DBMS 的并發(fā)控制管理器采用一定并發(fā)控制技術(shù)來(lái)實(shí)的并發(fā)控制管理器采用一定并發(fā)控制技術(shù)來(lái)實(shí)現(xiàn)并發(fā)控制。現(xiàn)并發(fā)控制。 并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的

5、并發(fā)控制事務(wù)的調(diào)度 多個(gè)事務(wù)中的并發(fā)操作按照它們的執(zhí)行多個(gè)事務(wù)中的并發(fā)操作按照它們的執(zhí)行時(shí)間排序形成的一個(gè)操作序列稱為調(diào)度時(shí)間排序形成的一個(gè)操作序列稱為調(diào)度。 同一個(gè)事務(wù)的操作在調(diào)度中的執(zhí)行順序是固同一個(gè)事務(wù)的操作在調(diào)度中的執(zhí)行順序是固定不變的。定不變的。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制事務(wù)的調(diào)度 串行調(diào)度串行調(diào)度 每個(gè)事務(wù)每個(gè)事務(wù)T T的操作都是連續(xù)執(zhí)行；的操作都是連續(xù)執(zhí)行； 多個(gè)事務(wù)依次執(zhí)行多個(gè)事務(wù)依次執(zhí)行, ,不存在事務(wù)之間的交錯(cuò)不存在事務(wù)之間的交錯(cuò)執(zhí)行。執(zhí)行。 非串行調(diào)度非串行調(diào)度 并發(fā)事務(wù)中操作的不同交叉執(zhí)行次序就構(gòu)并發(fā)事務(wù)中操作的不同交叉執(zhí)

6、行次序就構(gòu)成了不同的非串行調(diào)度。成了不同的非串行調(diào)度。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制的必要性并發(fā)控制的必要性事務(wù)的調(diào)度 串行調(diào)度串行調(diào)度優(yōu)點(diǎn)優(yōu)點(diǎn) 事務(wù)的串行調(diào)度不會(huì)破壞數(shù)據(jù)庫(kù)的一致性的狀事務(wù)的串行調(diào)度不會(huì)破壞數(shù)據(jù)庫(kù)的一致性的狀態(tài)；態(tài)；缺點(diǎn)缺點(diǎn) 不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn)。的特點(diǎn)。衡量事務(wù)調(diào)度正確性衡量事務(wù)調(diào)度正確性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制的必要性并發(fā)控制的必要性事務(wù)的調(diào)度 串行調(diào)度串行調(diào)度T1T2TimeRead(X,t) t:=t-50Write(X,t)

7、Read(Y,t) t:=t+50Write(Y)(a)Read(X,s) s:=s+100Write(X,s)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)(b)(b)Read(X,s) s:=s+100Write(X,s)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制的必要性并發(fā)控制的必要性事務(wù)的調(diào)度 串行調(diào)度串行調(diào)度T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)(a)(a)Read(X,s) s:=s*2Write(X,s)T1T2Tim

8、eRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)(b)(b)Read(X,s) s:=s*2Write(X,s)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制的必要性并發(fā)控制的必要性事務(wù)的調(diào)度 非串行調(diào)度非串行調(diào)度T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)(a)(a)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s

9、) s:=s+100Write(X,s)(b)(b)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題 主要體現(xiàn)在如下幾個(gè)方面主要體現(xiàn)在如下幾個(gè)方面 更新丟失（更新丟失（Lost Update） 臟讀（臟讀（Dirty Read） 不可重復(fù)讀（不可重復(fù)讀（Non_Repeatable Read） 并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】從客戶從客戶A A的賬戶（的賬戶（500500元）中同時(shí)轉(zhuǎn)賬元）中同時(shí)轉(zhuǎn)賬5050元和元和100100元給客元給客戶戶B B和客戶和客戶C C。 時(shí)間步驟步驟終端終端1A賬戶值賬戶值終端終端21 1

10、500Read(A，t1) ;2 2Read(A，t1) ; t1 := t1-100; 3 3 t1 := t1-50; 400Write(A，t1); 4 4Write(A，t1);450Read(C，t2) ; 5 5Read(B，t2) ; t2 := t2+100; 6 6t2 := t2+50; Write(C，t2);7 7Write(B，t2);并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題 更新丟失更新丟失（Lost Update） 兩個(gè)事務(wù)分別讀入同一數(shù)據(jù)并進(jìn)行更新，后兩個(gè)事務(wù)分別讀入同一數(shù)據(jù)并進(jìn)行更新，后提交的事務(wù)

11、的結(jié)果覆蓋了先提交的事務(wù)的結(jié)提交的事務(wù)的結(jié)果覆蓋了先提交的事務(wù)的結(jié)果，導(dǎo)致先提交的事務(wù)的更新被丟失。果，導(dǎo)致先提交的事務(wù)的更新被丟失。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 更新丟失更新丟失非串行調(diào)非串行調(diào)度度(A)并發(fā)控制的必要性并發(fā)控制的必要性T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)事務(wù)事務(wù)T1更新更新 X 事務(wù)事務(wù)T2更新更新 X 事務(wù)事務(wù)T2讀讀 X 事務(wù)事務(wù)T1讀讀 X 事務(wù)事務(wù)T1對(duì)對(duì)X的更新丟失的更新丟失 第第

12、17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題 臟讀臟讀（Dirty Read） 一事務(wù)讀取了還沒(méi)有提交事務(wù)所寫(xiě)的數(shù)據(jù)一事務(wù)讀取了還沒(méi)有提交事務(wù)所寫(xiě)的數(shù)據(jù)（臟數(shù)據(jù)）。（臟數(shù)據(jù)）。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 讀臟數(shù)據(jù)讀臟數(shù)據(jù)并發(fā)控制的必要性并發(fā)控制的必要性T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)事務(wù)事務(wù)T1失敗失敗ROLLBACK事務(wù)事務(wù)T1T1更新更新X X 事務(wù)事務(wù)T2讀了臟讀了臟數(shù)據(jù)數(shù)據(jù)

13、X 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題不可重復(fù)讀不可重復(fù)讀（Non_Repeatable Read） 事務(wù)多次發(fā)出同一查詢而得到不同的結(jié)果。事務(wù)多次發(fā)出同一查詢而得到不同的結(jié)果。 事務(wù)事務(wù)T1讀取數(shù)據(jù)后，事務(wù)讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操執(zhí)行更新操作，使得作，使得T1無(wú)法再現(xiàn)前一次讀取的結(jié)果無(wú)法再現(xiàn)前一次讀取的結(jié)果。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 不可重復(fù)讀不可重復(fù)讀并發(fā)控制的必要性并發(fā)控制的必要性T1T2TimeRead(X,t)Read(Y,s)sum:=t+sRead(X,t)Read(Y,s)sum:=t

14、+sRead(X,s) s:=s+100Write(X,s)事務(wù)事務(wù)T2更新更新X 錯(cuò)誤求和錯(cuò)誤求和 X 值不可重復(fù)讀值不可重復(fù)讀第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題 不可重復(fù)讀不可重復(fù)讀事務(wù)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其作了修改，當(dāng)對(duì)其作了修改，當(dāng)事務(wù)事務(wù)T1再次讀取該數(shù)據(jù)時(shí)，得到與前一次不同的值。再次讀取該數(shù)據(jù)時(shí)，得到與前一次不同的值。 事務(wù)事務(wù)T1按一定的條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)（如按一定的條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)（如記錄）后，事務(wù)記錄）后，事務(wù)T2刪除了其中部分?jǐn)?shù)據(jù)（記錄），當(dāng)刪除了其中部分?jǐn)?shù)據(jù)（記錄），當(dāng)T1再次按

15、相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些數(shù)據(jù)（記錄再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些數(shù)據(jù)（記錄）神秘失蹤了。）神秘失蹤了。 事務(wù)事務(wù)T1按一定的條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)（如記按一定的條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)（如記錄）后，事務(wù)錄）后，事務(wù)T2插入了一些數(shù)據(jù)（記錄），當(dāng)插入了一些數(shù)據(jù)（記錄），當(dāng) T1再再次按相同的條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些數(shù)據(jù)（記次按相同的條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些數(shù)據(jù)（記錄）。錄）。 幻影（幻影（ Phantom Row ）現(xiàn)象）現(xiàn)象并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題主要原因主要原因事務(wù)的非串行調(diào)度所產(chǎn)生的并發(fā)操

16、作破壞了事務(wù)的隔事務(wù)的非串行調(diào)度所產(chǎn)生的并發(fā)操作破壞了事務(wù)的隔離性。離性。解決的方法解決的方法對(duì)并發(fā)執(zhí)行的事務(wù)進(jìn)行控制，即用正確的方法調(diào)度并對(duì)并發(fā)執(zhí)行的事務(wù)進(jìn)行控制，即用正確的方法調(diào)度并發(fā)事務(wù)，發(fā)事務(wù)，使得一個(gè)事務(wù)的執(zhí)行不受其他事務(wù)的干擾，使得一個(gè)事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免數(shù)據(jù)的不一致性。從而避免數(shù)據(jù)的不一致性。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化多個(gè)事務(wù)的串行調(diào)度不會(huì)破壞數(shù)據(jù)庫(kù)的一多個(gè)事務(wù)的串行調(diào)度不會(huì)破壞數(shù)據(jù)庫(kù)的一致性的狀態(tài)。致性的狀態(tài)。如果事務(wù)是一致的，多個(gè)事務(wù)并發(fā)執(zhí)行的如果事務(wù)是一致的，多個(gè)事務(wù)并發(fā)執(zhí)行的整體效果等同

17、于某一次序下事務(wù)順序（串整體效果等同于某一次序下事務(wù)順序（串行）執(zhí)行的效果，那么該并發(fā)調(diào)度將保持行）執(zhí)行的效果，那么該并發(fā)調(diào)度將保持?jǐn)?shù)據(jù)庫(kù)的一致性。數(shù)據(jù)庫(kù)的一致性。可串行性可串行性作為并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則。作為并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 可串行化調(diào)度（可串行化調(diào)度（Serializable） 若一個(gè)具有若一個(gè)具有n n個(gè)事務(wù)的調(diào)度個(gè)事務(wù)的調(diào)度S S等價(jià)等價(jià)于由這些于由這些相相同同n n個(gè)事務(wù)組成的一個(gè)個(gè)事務(wù)組成的一個(gè)串行調(diào)度串行調(diào)度SS ，那么，那么S S就是可串行化。就是可串行化。 等價(jià)是指對(duì)于任意

18、的數(shù)據(jù)庫(kù)初始狀態(tài)，調(diào)等價(jià)是指對(duì)于任意的數(shù)據(jù)庫(kù)初始狀態(tài)，調(diào)度度S和調(diào)度和調(diào)度S的的執(zhí)行效果相同執(zhí)行效果相同。 并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制并發(fā)控制的必要性并發(fā)控制的必要性T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s*2Write(X,s)Read(Y,s) s:=s*2Write(Y,s)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s*2Write

19、(X,s)Read(Y,s) s:=s*2Write(Y,s)非串行的可串行化調(diào)度非串行的可串行化調(diào)度 非可串行化的調(diào)度非可串行化的調(diào)度 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 可串行化調(diào)度可串行化調(diào)度 對(duì)于一個(gè)給定的非串行調(diào)度，當(dāng)且僅當(dāng)它是對(duì)于一個(gè)給定的非串行調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度。可串行化的，才認(rèn)為是正確調(diào)度。 大多數(shù)并發(fā)控制管理器真正實(shí)現(xiàn)的是一個(gè)更大多數(shù)并發(fā)控制管理器真正實(shí)現(xiàn)的是一個(gè)更強(qiáng)的要求，稱為強(qiáng)的要求，稱為沖突可串行化沖突可串行化。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 沖突可串

20、行化調(diào)度沖突可串行化調(diào)度 沖突操作沖突操作調(diào)度中的一對(duì)連續(xù)的動(dòng)作（讀操作或?qū)懖僬{(diào)度中的一對(duì)連續(xù)的動(dòng)作（讀操作或?qū)懖僮鳎?，如果它們的順序交換，那么涉及的作），如果它們的順序交換，那么涉及的事務(wù)中至少有一個(gè)的行為會(huì)改變，則這對(duì)事務(wù)中至少有一個(gè)的行為會(huì)改變，則這對(duì)動(dòng)作就是沖突的。動(dòng)作就是沖突的。 不同事務(wù)對(duì)不同事務(wù)對(duì)同一數(shù)據(jù)對(duì)象同一數(shù)據(jù)對(duì)象的的讀寫(xiě)操作讀寫(xiě)操作是沖突是沖突的的 并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 沖突可串行化調(diào)度沖突可串行化調(diào)度 沖突操作沖突操作 ri(X)和和wi(X)總是沖突的?？偸菦_突的。 wi(X)和和wj(X)是沖

21、突的。是沖突的。 ri(X)和和wj(X)是沖突的，是沖突的，wi(X) 和和rj(X)也是。也是。并發(fā)控制的必要性并發(fā)控制的必要性ri(X)和和wi(X)分別表示事分別表示事務(wù)務(wù)Ti讀和寫(xiě)數(shù)據(jù)讀和寫(xiě)數(shù)據(jù)X 寫(xiě)讀沖突引起會(huì)引起不可寫(xiě)讀沖突引起會(huì)引起不可重復(fù)讀和臟讀現(xiàn)象重復(fù)讀和臟讀現(xiàn)象 寫(xiě)寫(xiě)沖突會(huì)引寫(xiě)寫(xiě)沖突會(huì)引起更新丟失起更新丟失第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 沖突可串行化調(diào)度沖突可串行化調(diào)度 如果將任一調(diào)度通過(guò)一系列相鄰動(dòng)作的非沖如果將任一調(diào)度通過(guò)一系列相鄰動(dòng)作的非沖突交換轉(zhuǎn)換為另一個(gè)調(diào)度，則這兩個(gè)調(diào)度是突交換轉(zhuǎn)換為另一個(gè)調(diào)度，則這兩個(gè)調(diào)度是沖突等價(jià)沖突等價(jià)的。

22、的。 如果一個(gè)調(diào)度沖突等價(jià)于一個(gè)串行調(diào)度，那如果一個(gè)調(diào)度沖突等價(jià)于一個(gè)串行調(diào)度，那么稱該調(diào)度是么稱該調(diào)度是沖突可串行化的沖突可串行化的。并發(fā)控制的必要性并發(fā)控制的必要性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例】對(duì)于如下調(diào)度r1(A)；w1(A)；r2(A)；w2(A)；r1(B)；w1(B)；r2(B)；w2(B)這個(gè)調(diào)度是否是沖突可串行化的？并發(fā)控制的必要性并發(fā)控制的必要性r1(A)；w1(A)；r2(A)；w2(A)；r1(B)；w1(B)；r2(B)；w2(B)r1(A)；w1(A)；r1(B)；r2(A)；w1(B)；w2(A)；r2(B)；w2(B)r1(A)；w1(A)；r2

23、(A)；r1(B)；w2(A)；w1(B)；r2(B)；w2(B)r1(A)；w1(A)；r1(B)；w1(B)；r2(A)；w2(A)；r2(B)；w2(B) r1(A)；w1(A)；r1(B)；w1(B)；r2(A)；w2(A)；r2(B)；w2(B) T1 T2調(diào)度是沖突可調(diào)度是沖突可串行化的串行化的第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例】有3個(gè)事務(wù)T1：w1(A); w1(B); T2：w2(A); w2(B); T3：w3(B);調(diào)度S1： w1(A);w1(B);w2(A);w2(B); w3(B);為一可能的串行調(diào)度。 調(diào)度調(diào)度S2： w1(A);w2(A);w2(B);

24、w1(B);w3(B);是否為可串行化的調(diào)度，是否是沖突可串行化調(diào)度？是否為可串行化的調(diào)度，是否是沖突可串行化調(diào)度？并發(fā)控制的必要性并發(fā)控制的必要性S2不是沖突可串行化不是沖突可串行化S2可串行化的調(diào)度可串行化的調(diào)度：具有與具有與S1S1一樣的效果一樣的效果 沖突可串行化調(diào)度是可串行化調(diào)度的充分條件，而不是必要條件。沖突可串行化調(diào)度是可串行化調(diào)度的充分條件，而不是必要條件。第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制非串行調(diào)度的可串行化 沖突可串行化調(diào)度沖突可串行化調(diào)度沖突可串行化是可串行化的一個(gè)充分條件，即沖突沖突可串行化是可串行化的一個(gè)充分條件，即沖突可串行化調(diào)度是可串行化調(diào)度。可串行化調(diào)度

25、是可串行化調(diào)度。沖突可串行化對(duì)一個(gè)可串行化調(diào)度來(lái)說(shuō)并不是必要沖突可串行化對(duì)一個(gè)可串行化調(diào)度來(lái)說(shuō)并不是必要的，但它是商用的，但它是商用DBMS在需要保證可串行化時(shí)通常在需要保證可串行化時(shí)通常使用的條件。使用的條件。DBMS的并發(fā)控制管理器采用一定的技術(shù)來(lái)保證調(diào)的并發(fā)控制管理器采用一定的技術(shù)來(lái)保證調(diào)度是可串行化的（或沖突可串行化的）。度是可串行化的（或沖突可串行化的）。并發(fā)控制的必要性并發(fā)控制的必要性DBMS采用封鎖技術(shù)實(shí)現(xiàn)并采用封鎖技術(shù)實(shí)現(xiàn)并發(fā)調(diào)度的可串行性發(fā)調(diào)度的可串行性第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制基于鎖的并發(fā)控制的基本思想 當(dāng)一個(gè)事務(wù)當(dāng)一個(gè)事務(wù)T T在對(duì)其需要的數(shù)據(jù)對(duì)象進(jìn)在對(duì)其

26、需要的數(shù)據(jù)對(duì)象進(jìn)行行操作之前操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其其加鎖加鎖（也稱封鎖）。（也稱封鎖）。 加鎖后加鎖后事務(wù)事務(wù)T T就對(duì)該數(shù)據(jù)對(duì)象有了一定就對(duì)該數(shù)據(jù)對(duì)象有了一定的的控制控制，在事務(wù)，在事務(wù)T T釋放它的鎖之前，其釋放它的鎖之前，其他事務(wù)不能更新此數(shù)據(jù)對(duì)象。他事務(wù)不能更新此數(shù)據(jù)對(duì)象。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制鎖 封鎖模式封鎖模式 共享鎖（共享鎖（ Share Locks） 簡(jiǎn)稱簡(jiǎn)稱 S 鎖，又稱為讀鎖。鎖，又稱為讀鎖。 排他鎖（排他鎖（ Exclusive Locks） 簡(jiǎn)稱簡(jiǎn)稱 X 鎖，又稱為寫(xiě)鎖。鎖，又稱為寫(xiě)鎖。封鎖技術(shù)封鎖技術(shù)

27、第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制鎖 封鎖模式封鎖模式 共享鎖共享鎖若事務(wù)若事務(wù)T T對(duì)數(shù)據(jù)對(duì)象對(duì)數(shù)據(jù)對(duì)象A A加上加上S S鎖鎖，則事務(wù)，則事務(wù)T T可以可以讀讀A A但但不能修改不能修改A A，其它事務(wù)只能再，其它事務(wù)只能再對(duì)對(duì)A A加加S S鎖，而不能加鎖，而不能加X(jué) X鎖，直到鎖，直到T T釋放釋放A A上上的的S S鎖。鎖。保證了其它事務(wù)可以讀保證了其它事務(wù)可以讀A A，但在，但在T T釋放釋放A A上上的的S S鎖之前不能對(duì)鎖之前不能對(duì)A A做任何修改。做任何修改。 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制鎖 封鎖模式封鎖模式 排他鎖排他鎖若事務(wù)若事務(wù)T

28、T對(duì)數(shù)據(jù)對(duì)象對(duì)數(shù)據(jù)對(duì)象A A加上加上X X鎖鎖，則只允許，則只允許T T讀取和修改讀取和修改A A，其它任何事務(wù)都不能再對(duì)，其它任何事務(wù)都不能再對(duì)A A加任何類(lèi)型的鎖，直到加任何類(lèi)型的鎖，直到T T釋放釋放A A上的鎖。上的鎖。保證了其它事務(wù)在事務(wù)保證了其它事務(wù)在事務(wù)T T釋放釋放A A上的鎖之前上的鎖之前不能再讀取和修改不能再讀取和修改A A。 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制鎖 相容性矩陣相容性矩陣 描述在已知同一數(shù)據(jù)庫(kù)對(duì)象上可能已經(jīng)被加描述在已知同一數(shù)據(jù)庫(kù)對(duì)象上可能已經(jīng)被加鎖的情況下何時(shí)能同意其他封鎖請(qǐng)求的策略鎖的情況下何時(shí)能同意其他封鎖請(qǐng)求的策略 YYY-YY

29、NSYNNX-SX T2T1事務(wù)事務(wù)T1獲得獲得的鎖的鎖事務(wù)事務(wù)T2T2申請(qǐng)的鎖申請(qǐng)的鎖Y=Yes 相容的請(qǐng)求相容的請(qǐng)求N=No 不相容的請(qǐng)求不相容的請(qǐng)求封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制鎖 封的升級(jí)封的升級(jí) 一個(gè)想要讀一個(gè)想要讀A A并將為并將為A A寫(xiě)入新值的事務(wù)寫(xiě)入新值的事務(wù)T T首先首先獲得獲得A A上的一個(gè)共享鎖，而僅在后來(lái)當(dāng)上的一個(gè)共享鎖，而僅在后來(lái)當(dāng)T T準(zhǔn)備準(zhǔn)備好為好為A A寫(xiě)入新值時(shí)將鎖升級(jí)為排他鎖。寫(xiě)入新值時(shí)將鎖升級(jí)為排他鎖。 允許鎖的升級(jí)將會(huì)使并發(fā)執(zhí)行的事務(wù)提早執(zhí)允許鎖的升級(jí)將會(huì)使并發(fā)執(zhí)行的事務(wù)提早執(zhí)行或提前完成，行或提前完成，提高事務(wù)的執(zhí)行效率提

30、高事務(wù)的執(zhí)行效率。 不加區(qū)別地使鎖升級(jí)將會(huì)帶來(lái)新的并且可能不加區(qū)別地使鎖升級(jí)將會(huì)帶來(lái)新的并且可能更嚴(yán)重的更嚴(yán)重的死鎖死鎖問(wèn)題。問(wèn)題。 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制封鎖協(xié)議（Locking Protocal） 在運(yùn)用鎖技術(shù)時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)的在運(yùn)用鎖技術(shù)時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)的一些約定規(guī)則，例如何時(shí)一些約定規(guī)則，例如何時(shí)申請(qǐng)鎖申請(qǐng)鎖、持鎖持鎖時(shí)間時(shí)間、何時(shí)釋放鎖何時(shí)釋放鎖等。等。 約定不同的規(guī)則就形成了各種不同的鎖約定不同的規(guī)則就形成了各種不同的鎖協(xié)議協(xié)議 兩階段鎖協(xié)議兩階段鎖協(xié)議（Two-Phase Locking Protocol，2PL） 封鎖技術(shù)封鎖技術(shù)第第

31、17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制封鎖技術(shù)封鎖技術(shù)T1T2TimeSlock (X)Slock (X)；Read(X,t) t:=t-50Xlock (X)Xlock (X)；Write(X,t)Unlock( X)Unlock( X)Slock (Y)Slock (Y)；Read(Y,t) t:=t+50Xlock (Y)Xlock (Y)；Write(Y)Unlock( Y)Unlock( Y)Slock (X)Slock (X)；Read(X,s) s:=s*2Xlock (X)Xlock (X)；Write(X,s)Unlock( X)Unlock( X)Slock (Y)Sloc

32、k (Y)；Read(Y,s) s:=s*2Xlock (Y)Xlock (Y)；Write(Y,s)Unlock( Y)Unlock( Y)加鎖后是可串行化的嗎？加鎖后是可串行化的嗎？第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制兩階段封鎖協(xié)議對(duì)一個(gè)事務(wù)中封鎖操作的順序進(jìn)行限制，要求在每個(gè)對(duì)一個(gè)事務(wù)中封鎖操作的順序進(jìn)行限制，要求在每個(gè)事務(wù)中，所有封鎖請(qǐng)求先于所有解鎖請(qǐng)求。事務(wù)中，所有封鎖請(qǐng)求先于所有解鎖請(qǐng)求。 獲鎖階段獲鎖階段（擴(kuò)展階段）（擴(kuò)展階段） 事務(wù)要申請(qǐng)完成事務(wù)操作所需要的所有鎖，以事務(wù)要申請(qǐng)完成事務(wù)操作所需要的所有鎖，以后不能再申請(qǐng)新的鎖。后不能再申請(qǐng)新的鎖。 釋放鎖階段釋放鎖階段（收

33、縮階段）（收縮階段） 事務(wù)釋放所申請(qǐng)的所有鎖，也不能再申請(qǐng)任何事務(wù)釋放所申請(qǐng)的所有鎖，也不能再申請(qǐng)任何鎖。鎖。 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制兩階段鎖協(xié)議【例例】 Slock A Slock B Xlock C Unlock B Unlock A Unlock C； Slock A Unlock A Slock B Xlock C Unlock C Unlock B ； 事務(wù)事務(wù) Ti 遵循兩階段鎖協(xié)議，其封鎖序列是：遵循兩階段鎖協(xié)議，其封鎖序列是： | 擴(kuò)展階段擴(kuò)展階段 | | 收縮階段收縮階段 | 事務(wù)事務(wù) Ti 不遵循兩階段鎖協(xié)議，其封鎖序列是：不遵循兩階段鎖

34、協(xié)議，其封鎖序列是： 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制兩階段鎖協(xié)議 遵循兩階段封鎖協(xié)議的并發(fā)事務(wù)的遵循兩階段封鎖協(xié)議的并發(fā)事務(wù)的任何任何并發(fā)調(diào)度策略都是并發(fā)調(diào)度策略都是沖突可串行化沖突可串行化的。的。 許多許多DBMS的并發(fā)控制管理器采用嚴(yán)格的兩的并發(fā)控制管理器采用嚴(yán)格的兩階段鎖協(xié)議來(lái)實(shí)現(xiàn)可串行性。階段鎖協(xié)議來(lái)實(shí)現(xiàn)可串行性。 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制兩階段鎖協(xié)議 嚴(yán)格的兩階段鎖協(xié)議嚴(yán)格的兩階段鎖協(xié)議 事務(wù)事務(wù)T在在讀一個(gè)數(shù)據(jù)庫(kù)對(duì)象讀一個(gè)數(shù)據(jù)庫(kù)對(duì)象前必須獲得該數(shù)據(jù)對(duì)象前必須獲得該數(shù)據(jù)對(duì)象上的上的讀鎖讀鎖。 事務(wù)事務(wù)T在在更新一個(gè)數(shù)據(jù)庫(kù)對(duì)

35、象更新一個(gè)數(shù)據(jù)庫(kù)對(duì)象前必須獲得該數(shù)據(jù)對(duì)前必須獲得該數(shù)據(jù)對(duì)象上的象上的寫(xiě)鎖寫(xiě)鎖。若事務(wù)。若事務(wù)T已具有該數(shù)據(jù)對(duì)象上的讀鎖已具有該數(shù)據(jù)對(duì)象上的讀鎖，則必須將讀鎖，則必須將讀鎖升級(jí)升級(jí)到寫(xiě)鎖。到寫(xiě)鎖。若事務(wù)若事務(wù)B對(duì)數(shù)據(jù)對(duì)象的封鎖請(qǐng)求與事務(wù)對(duì)數(shù)據(jù)對(duì)象的封鎖請(qǐng)求與事務(wù)A已獲得的已獲得的鎖鎖不相容不相容時(shí)，事務(wù)時(shí)，事務(wù)B將處于將處于等待等待狀態(tài)，直到事務(wù)狀態(tài)，直到事務(wù)A釋放其所擁有的鎖為止。釋放其所擁有的鎖為止。事務(wù)所獲得的鎖將一直保持到事務(wù)所獲得的鎖將一直保持到事務(wù)結(jié)束事務(wù)結(jié)束才才釋放釋放。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制封鎖技術(shù)封鎖技術(shù)T1T2TimeSlock (X)Sl

36、ock (X)；Read(X,t) t:=t-50Xlock (X)Xlock (X)；Write(X,t)Unlock( X)Unlock( X)Slock (Y)Slock (Y)；Read(Y,t) t:=t+50Xlock (Y)Xlock (Y)；Write(Y)Unlock( Y)Unlock( Y)Slock (X)Slock (X)；Read(X,s) s:=s*2Xlock (X)Xlock (X)；Write(X,s)Unlock( X)Unlock( X)Slock (Y)Slock (Y)；Read(Y,s) s:=s*2Xlock (Y)Xlock (Y)；Write

37、(Y,s)Unlock( Y)Unlock( Y)采用采用2PL來(lái)實(shí)現(xiàn)可串行化來(lái)實(shí)現(xiàn)可串行化第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制封鎖技術(shù)封鎖技術(shù)T1T2TimeSlock (X)Slock (X)；Read(X,t) t:=t-50Xlock (X)Xlock (X)；Write(X,t)Slock (Y)Slock (Y)；Read(Y,t) t:=t+50Xlock (Y)Xlock (Y)；Write(Y)Unlock( X)Unlock( X)Unlock( Y)Unlock( Y)Slock (X)Slock (X)被拒絕被拒絕 （事務(wù)等待）（事務(wù)等待） ：Slock (X)S

38、lock (X)；Read(X,s) s:=s*2Xlock (X)Xlock (X)；Write(X,s)Slock (Y)Slock (Y)；Read(Y,s) s:=s*2Xlock (Y)Xlock (Y)；Write(Y,s)Unlock( X)Unlock( X)Unlock( Y) Unlock( Y) 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s

39、:=s+100Write(X,s)事務(wù)事務(wù)T1失敗失敗ROLLBACK事務(wù)事務(wù)T1T1更新更新X X 事務(wù)事務(wù)T2讀了臟讀了臟數(shù)據(jù)數(shù)據(jù)X 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用利用嚴(yán)格嚴(yán)格兩階段封鎖協(xié)議解決兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock X第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖

40、技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock X第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock XXlock X第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段

41、封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Xlock XWrite(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock X第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Xlock XWrite(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X

42、,s)Slock X申請(qǐng)申請(qǐng)Slock X第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Xlock XWrite(X,t)Slock YRead(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock X申請(qǐng)申請(qǐng)Slock X等待等待：第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t

43、) t:=t-50Xlock XWrite(X,t)Slock YRead(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Slock X申請(qǐng)申請(qǐng)Slock X等待等待：事務(wù)事務(wù)T1失敗失敗ROLLBACK第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Xlock XWrite(X,t)Slock YRead(Y,t)Read(X,s) s:=s+100Write(X,s)Slock X申請(qǐng)申請(qǐng)Slock X

44、等待等待： ROLLBACKUnlock XUnlock Y第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】利用嚴(yán)格兩階段封鎖協(xié)議解決利用嚴(yán)格兩階段封鎖協(xié)議解決“臟讀臟讀”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Xlock XWrite(X,t)Slock YRead(Y,t)Read(X,s) s:=s+100Write(X,s)Slock X申請(qǐng)申請(qǐng)Slock X等待等待： ROLLBACKUnlock XUnlock YSlock X事務(wù)事務(wù)T2不會(huì)再不會(huì)再讀臟數(shù)據(jù)讀臟數(shù)據(jù)X 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【思考題思考題】利用嚴(yán)格兩階段鎖協(xié)

45、議解決利用嚴(yán)格兩階段鎖協(xié)議解決“更新丟失更新丟失 ”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)事務(wù)事務(wù)T1對(duì)對(duì)X的更新丟失的更新丟失 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【思考題思考題】利用嚴(yán)格兩階段鎖協(xié)議解決利用嚴(yán)格兩階段鎖協(xié)議解決“更新丟失更新丟失 ”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)Slock XSlock XT1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read

46、(X,s) s:=s+100Write(X,s)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【思考題思考題】利用嚴(yán)格兩階段鎖協(xié)議解決利用嚴(yán)格兩階段鎖協(xié)議解決“更新丟失更新丟失 ”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)Slock XSlock XT1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【思考題思考題】利用嚴(yán)格兩階段鎖協(xié)議解決利用嚴(yán)格兩階段鎖協(xié)議解決“更新丟失更新丟失 ”問(wèn)題問(wèn)題封鎖技術(shù)封鎖技術(shù)Slock XSlock XT1T2Time

47、Read(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Xlock XXlock X鎖請(qǐng)求被拒絕，事務(wù)等待鎖請(qǐng)求被拒絕，事務(wù)等待 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 【思考題思考題】利用嚴(yán)格兩階段鎖協(xié)議解決利用嚴(yán)格兩階段鎖協(xié)議解決“不可重復(fù)讀不可重復(fù)讀”問(wèn)問(wèn)題題封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t)Read(Y,s)sum:=t+sRead(X,t)Read(Y,s)sum:=t+sRead(X,s) s:=s+100Write(X,s)X 值不可重復(fù)讀值不可重復(fù)讀第第1

48、7講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖（deadlock） 并發(fā)執(zhí)行的事務(wù)由于競(jìng)爭(zhēng)資源達(dá)到一個(gè)存在死鎖并發(fā)執(zhí)行的事務(wù)由于競(jìng)爭(zhēng)資源達(dá)到一個(gè)存在死鎖的狀態(tài)。的狀態(tài)。 根據(jù)并發(fā)事務(wù)的等待狀態(tài)根據(jù)并發(fā)事務(wù)的等待狀態(tài) 活死鎖（簡(jiǎn)稱活死鎖（簡(jiǎn)稱“活鎖活鎖”） 死死鎖（簡(jiǎn)稱死死鎖（簡(jiǎn)稱“死鎖死鎖”）。）。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 活鎖（livelock）并發(fā)事務(wù)中有并發(fā)事務(wù)中有部分事務(wù)部分事務(wù)因封鎖申請(qǐng)得不到滿足所因封鎖申請(qǐng)得不到滿足所處的處的長(zhǎng)期等待長(zhǎng)期等待狀態(tài)。狀態(tài)。其它的事務(wù)仍然可以繼續(xù)運(yùn)行下去。其它的事務(wù)仍然可以繼續(xù)運(yùn)行下去。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的

49、并發(fā)控制事務(wù)的并發(fā)控制T1 T2 Time Slock A . . .Unlock A;Xlock A 等待等待 . . .T3Slock A . . .Unlock A;T4Slock A . . .Unlock A;【例例】活鎖活鎖封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 活鎖解決方法解決方法 先來(lái)先服務(wù)先來(lái)先服務(wù)當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)，按請(qǐng)求封鎖的當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)，按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì)。先后次序?qū)@些事務(wù)排隊(duì)。該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖。一個(gè)事務(wù)獲得鎖

50、。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖每個(gè)事務(wù)都可能擁有一部分每個(gè)事務(wù)都可能擁有一部分鎖鎖，并因申，并因申請(qǐng)其它事務(wù)所持有的請(qǐng)其它事務(wù)所持有的鎖鎖而等待，由此產(chǎn)生而等待，由此產(chǎn)生的的循環(huán)等待循環(huán)等待現(xiàn)象?，F(xiàn)象。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】死鎖死鎖封鎖技術(shù)封鎖技術(shù)Slock XSlock XT1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)Xlock XXlock X鎖請(qǐng)求被拒絕，事務(wù)等待鎖請(qǐng)求被拒絕，事務(wù)

51、等待 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 解決方法解決方法 預(yù)防死鎖預(yù)防死鎖對(duì)事務(wù)進(jìn)行管理，使死鎖永遠(yuǎn)都不可能形對(duì)事務(wù)進(jìn)行管理，使死鎖永遠(yuǎn)都不可能形成成 死鎖的診斷和解除死鎖的診斷和解除允許死鎖發(fā)生，再檢測(cè)死鎖并進(jìn)行解除允許死鎖發(fā)生，再檢測(cè)死鎖并進(jìn)行解除 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 預(yù)防死鎖預(yù)防死鎖 一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行部加鎖，否則就不能繼續(xù)執(zhí)行降低系統(tǒng)并發(fā)度降低系統(tǒng)并發(fā)度難于事先精確確定封鎖對(duì)象難于事先精確確定封鎖對(duì)象【比較比較】一次性

52、封鎖法與二階段封鎖協(xié)議一次性封鎖法與二階段封鎖協(xié)議封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制Time【例例】一次性封鎖法一次性封鎖法封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制【例例】一次性封鎖法一次性封鎖法Xlock XXlock YCommit;Unlock A;Unlock B封鎖技術(shù)封鎖技術(shù)T1T2TimeRead(X,t) t:=t-50Write(X,t)Read(Y,t) t:

53、=t+50Write(Y)Read(X,s) s:=s+100Write(X,s)事務(wù)等待事務(wù)等待 第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 預(yù)防死鎖預(yù)防死鎖 順序封鎖法順序封鎖法預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。都按這個(gè)順序?qū)嵭蟹怄i。維護(hù)成本大：數(shù)據(jù)庫(kù)系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極維護(hù)成本大：數(shù)據(jù)庫(kù)系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極多，并且在不斷地變化。多，并且在不斷地變化。難以實(shí)現(xiàn)：很難事先確定每一個(gè)事務(wù)要封鎖哪難以實(shí)現(xiàn)：很難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象。些對(duì)象。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 死

54、鎖的檢測(cè)和解除死鎖的檢測(cè)和解除 超時(shí)法超時(shí)法 事務(wù)等待圖法事務(wù)等待圖法 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除 超時(shí)法超時(shí)法如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖就認(rèn)為發(fā)生了死鎖優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)缺點(diǎn) 有可能誤判死鎖有可能誤判死鎖 時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除 等待圖法等待圖法 用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況

55、；用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況； 并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路事務(wù)等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。，則表示系統(tǒng)中出現(xiàn)了死鎖。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 事務(wù)等待圖事務(wù)等待圖事務(wù)等待圖是一個(gè)有向圖事務(wù)等待圖是一個(gè)有向圖G=(T，U ） T：結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)。結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)。 U：邊的集合，每條邊表示事務(wù)等待的情況。邊的集合，每條邊表示事務(wù)等待的情況。 若若T1等待等待T2，則，則T1，

56、T2之間劃一條有向邊，之間劃一條有向邊，從從T1指向指向T2。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 死鎖 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除 選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消；選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消； 釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去。行下去。封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 并發(fā)控制管理器通過(guò)給數(shù)據(jù)庫(kù)對(duì)象加鎖來(lái)實(shí)并發(fā)控制管理器通過(guò)給數(shù)據(jù)庫(kù)對(duì)象加鎖來(lái)實(shí)現(xiàn)事務(wù)隔離性，也會(huì)增加事務(wù)的響應(yīng)時(shí)間，減現(xiàn)事務(wù)隔離性，也會(huì)增加事務(wù)的響應(yīng)時(shí)間，減少事務(wù)吞吐量。少事務(wù)吞吐量。多粒

57、度封鎖多粒度封鎖 事務(wù)的隔離性級(jí)別事務(wù)的隔離性級(jí)別 封鎖技術(shù)封鎖技術(shù)第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 多粒度封鎖 封鎖粒度封鎖粒度 封鎖對(duì)象單元的大小稱為封鎖粒度封鎖對(duì)象單元的大小稱為封鎖粒度(Granularity) 封鎖的對(duì)象封鎖的對(duì)象 邏輯單元邏輯單元屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等 物理單元物理單元頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制學(xué)號(hào)姓名性別年齡S1張三男20S2李四女21S3劉敏男2

58、2鎖鎖事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制學(xué)號(hào)姓名性別年齡S1張三男20S2李四女21S3劉敏男22鎖鎖鎖鎖鎖鎖事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 封鎖的粒度越大（小），并發(fā)度就越封鎖的粒度越大（小），并發(fā)度就越低（高），并發(fā)控制開(kāi)銷(xiāo)越?。ù螅┑停ǜ撸l(fā)控制開(kāi)銷(xiāo)越?。ù螅┑诘?7講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 多粒度封鎖(Multiple Granularity Locking) 多粒度封鎖多粒度封鎖 在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇使用選擇使用 選擇封鎖粒度選擇封鎖粒度 同時(shí)考慮封鎖開(kāi)銷(xiāo)和并發(fā)度兩

59、個(gè)因素，適當(dāng)選擇封同時(shí)考慮封鎖開(kāi)銷(xiāo)和并發(fā)度兩個(gè)因素，適當(dāng)選擇封鎖粒度鎖粒度事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 多粒度封鎖多粒度鎖的組織多粒度鎖的組織多粒度樹(shù)多粒度樹(shù) 以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度 根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度度 葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制例：三級(jí)粒度樹(shù)數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)關(guān)系關(guān)系R Rn n關(guān)系關(guān)系R R1 1元組元組1 1元組元組n n元組元組n n元組元組1 1 X鎖鎖(X)(X)

60、 對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類(lèi)型的鎖。結(jié)點(diǎn)也被加以同樣類(lèi)型的鎖。事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制第第17講講 事務(wù)的并發(fā)控制事務(wù)的并發(fā)控制 多粒度封鎖多粒度封鎖協(xié)議多粒度封鎖協(xié)議 要在任何結(jié)點(diǎn)上加要在任何結(jié)點(diǎn)上加S或或X鎖，必須從層次結(jié)構(gòu)的根鎖，必須從層次結(jié)構(gòu)的根結(jié)點(diǎn)開(kāi)始。結(jié)點(diǎn)開(kāi)始。 對(duì)樹(shù)中任一結(jié)點(diǎn)加普通鎖前，必須先對(duì)它的上層對(duì)樹(shù)中任一結(jié)點(diǎn)加普通鎖前，必須先對(duì)它的上層結(jié)點(diǎn)加結(jié)點(diǎn)加意向鎖意向鎖；如果對(duì)一個(gè)結(jié)點(diǎn)加上意向鎖，則；如果對(duì)一個(gè)結(jié)點(diǎn)加上意向鎖，則說(shuō)明將對(duì)該結(jié)點(diǎn)的下層結(jié)點(diǎn)加鎖。說(shuō)明將對(duì)該結(jié)點(diǎn)的下層結(jié)點(diǎn)加鎖。 對(duì)多粒度樹(shù)中的每一個(gè)結(jié)