華科數(shù)據(jù)庫系統(tǒng)原理第十一章-并發(fā)控制

11.1事務(wù)（transaction）1、定義構(gòu)成一個獨立邏輯工作單位的數(shù)據(jù)庫操作集?！ひ粭lSQL語句；·一組SQL語句序列；·一個包含對DB操作的應(yīng)用程序。2、構(gòu)成方式①顯式BEGINTRANSACTION···ENDTRANSACTION/COMMIT/ROLLBACK其中：COMMIT：提交，事務(wù)對DB修改寫回到磁盤上的DB中去。ROLLBACK：回滾，撤消對DB之修改，回滾到事務(wù)開始狀態(tài)。第11章并發(fā)控制1②

缺省·一條SQL語句·COMMIT/ROLLBACK3、事務(wù)的ACID性質(zhì)1）原子性（Atomicity）①

定義事務(wù)是一個不可分割的工作單元，其對DB的操作要么都做，要么都不做。②

目標保證DB數(shù)據(jù)的正確性（轉(zhuǎn)帳問題）。③技術(shù)·日志十ROLLBACK（UNDO）（意外終止）；·并發(fā)控制（交叉執(zhí)行）?！崿F(xiàn)由DBMS自動完成。22）一致性（consistency）

①

定義——事務(wù)的執(zhí)行必須是將DB從一個正確（一致）狀態(tài)轉(zhuǎn)換到另一個正確（一致）狀態(tài)。如：轉(zhuǎn)帳問題中，A有100萬人民幣是一個正確狀態(tài)，減去50萬，轉(zhuǎn)到B帳上50萬，DB從一個正確狀態(tài)轉(zhuǎn)變另一個正確狀態(tài)，這兩個操作，若只做其中一個，則不能實現(xiàn)DB從一個正確狀態(tài)轉(zhuǎn)到另一個正確狀態(tài)，破壞了事務(wù)一致性。②目標保證DB數(shù)據(jù)正確性（防止丟失更新、讀臟、讀不可重復(fù)）。③技術(shù)并發(fā)控制。④實現(xiàn)·用戶定義事務(wù)（保證相關(guān)操作在一個事務(wù)中）；·DBMS維護之。33）隔離性（isolation）①定義——一個事務(wù)中對DB的操作及使用的數(shù)據(jù)與其它并發(fā)事務(wù)無關(guān)，并發(fā)執(zhí)行的事務(wù)間不能互相干擾。②

目標防止鏈式夭折。③

技術(shù)并發(fā)控制。④

實現(xiàn)DBMS自動實現(xiàn)。4）持久性（durability）①

定義——一個已提交事務(wù)對DB的更新是永久性的，不受后來故障的影響。②

目標保證DB可靠性4③

技術(shù)·提交持久（內(nèi)存是揮發(fā)裝置，外存是抗揮發(fā)裝置）。（事務(wù)終止前應(yīng)完成commit）·備份＋日志。④

實現(xiàn)DBMS恢復(fù)子系統(tǒng)實現(xiàn)之。

511.2并發(fā)控制1、問題的提出問題1）丟失更新（lostupdate）——兩個以上事務(wù)從DB中讀入同一數(shù)據(jù)并修改之，其中一事務(wù)的提交結(jié)果破壞了另一事務(wù)的提交結(jié)果，導(dǎo)致該事務(wù)對DB的修改被丟失。

6例：

按ti執(zhí)行：·TA在t1處從DB中讀入X值（為100），TB在t2處讀入值（100）·TA在t3執(zhí)行X-1并寫回DB，DB中X值為99·TB在t4執(zhí)行X-1并寫回DB，DB中X值為99。·TB對X的修改履蓋了TA對X修改，使TA之修改丟失。（若為飛機訂票，則TA、TB實賣2張票，但系統(tǒng)中只表現(xiàn)賣了一張票）

7Sc1=RA(X)RB(X)WA(X)WB(X)調(diào)度的文本表達方式：8問題2）讀不可重復(fù)（readnorepeatable）——同一事務(wù)重復(fù)讀同一數(shù)據(jù)，但獲得結(jié)果不同。①

一事務(wù)讀取后，另一事條對之進行了修改例：

9按ti執(zhí)行：·TA第一次在t1處讀B為100；·TB在t2處修改并寫回DB，B為200；·TA在t3處讀B（為校對用），B為200；·TA兩次讀B，（第二次為校對用），讀結(jié)果不同（一次100，另一次為200）。②

一事務(wù)讀取數(shù)據(jù)后，另一并發(fā)事務(wù)刪去了其中部分數(shù)據(jù)（少了）。（幻行現(xiàn)象：Phantomrow）③

一事務(wù)讀取數(shù)據(jù)后，另一事務(wù)插入了一些新數(shù)據(jù)（多了）。（幻行現(xiàn)象）10Sc2=RA(A)RA(B)RB(B)WB(B)RA(A)RA(B)調(diào)度的文本表達方式：11問題3）讀“臟”數(shù)據(jù)

(readdirty)——讀未提交的隨后又被撤消(Rollback)的數(shù)據(jù)。

例：

SC3=RA(X)WA(X)RB(X)WA(X)12接上例：SC3=RA(X)WA(X)RB(X)WA(X)按ti執(zhí)行：·TA在t1讀x(100)并修改為200后寫回磁盤DB中；·TB在t2讀x為200；·TA在t3處撤消對x修改，x恢復(fù)為100；·TB此時讀出的x（200）數(shù)據(jù)與DB實際值(100)不一致，即TB讀到的不正確的“臟”數(shù)據(jù)。2.上述問題的原因多事務(wù)并發(fā)操作DB被壞了事務(wù)的隔離性，導(dǎo)致了數(shù)據(jù)不一致性。3.方法并發(fā)控制(正確的并發(fā)操作調(diào)度策略)。

1311.2封鎖11.2.1概述1、什么是封鎖：并發(fā)控制的一種技術(shù)。并發(fā)控制方法①鎖（Locking）——商用主要方法②樂觀（Optimistic）③時標（timestamping）2、封鎖規(guī)則①將要存取的數(shù)據(jù)須先申請加鎖；②已被加鎖的數(shù)據(jù)不能再加不相容鎖；③一旦退出使用應(yīng)立即釋放鎖；④未被加鎖的數(shù)據(jù)不可對之解鎖。1411.2.2申請時機1、事務(wù)·無死鎖；·鎖開銷少；·并發(fā)性低。2、一個SQL語句·并發(fā)性高；·鎖開銷大；·死鎖；·申請頻繁。1511.2.3申請方式1、顯式應(yīng)事務(wù)的要求直接加到數(shù)據(jù)對象上2、隱式該數(shù)據(jù)對象沒有獨立加鎖，由于數(shù)據(jù)對象的多粒度層次結(jié)構(gòu)中的上級結(jié)點加了鎖，使該數(shù)據(jù)對象隱含的加了相同類型的鎖。1611.2.4封鎖類型1、排它鎖（X鎖：exclusivelock）——若事務(wù)Ti持有數(shù)據(jù)Di的X鎖，則Ti可讀、寫Di，其它任何事務(wù)不能再對Di加任何鎖，直至Ti釋放該X鎖。X鎖用于寫保護，防止丟失更新。

相容矩陣：

172、共享鎖（S鎖：sharelock）——若事務(wù)Ti持有數(shù)據(jù)Di的S鎖，則其它事務(wù)仍可對Di加S鎖，但不可加X鎖，直到Ti釋放該S鎖。一旦施加S鎖，讀可共享，但其它事務(wù)不可改。S鎖用于讀操作。相容矩陣：

183、封鎖類型的相容矩陣T1T2

XS－Y相容的請求N不相容的請求XNNYSNYY－YYY19對應(yīng)問題1：加鎖解決丟失更新20對應(yīng)問題3：加鎖解決讀臟21對應(yīng)問題2：加鎖解決不可重復(fù)讀2211.3活鎖和死鎖11.3.1活鎖（livelock）1、含義——事務(wù)因故永遠處于等待狀態(tài)。2、方法FCFS——先來先服務(wù)。11.3.2死鎖（deadlock）1、含義——兩個或兩個以上事務(wù)均處于等待狀態(tài)，每個事務(wù)都在等待其中另一個事務(wù)封鎖的數(shù)據(jù)，導(dǎo)致任何事務(wù)都不能繼續(xù)執(zhí)行的現(xiàn)象稱為死鎖。

23242、產(chǎn)生條件①

互斥（排它性控制）；②

不可剝奪（釋放前，其它事務(wù)不能剝奪）；③

部分分配（每次申請一部分，申請新的時，仍占用已獲得者）；④

環(huán)路（循環(huán)鏈中，每事務(wù)獲得數(shù)據(jù)同時又被另一事務(wù)請求）。3、死鎖處理1）預(yù)防——防止產(chǎn)生條件之一發(fā)生。①

一次封鎖法——每個事務(wù)事先一次獲得其需數(shù)據(jù)的全部鎖。如：TA獲得所有數(shù)據(jù)A、B鎖，TA連續(xù)執(zhí)行，TB等待；TA執(zhí)行完后釋放A、B鎖，TB繼續(xù)執(zhí)行，不會發(fā)生死鎖。特征：簡單；無死鎖；粒度大，并發(fā)性低；難以確定封鎖對象（DB常變化，只好擴大封鎖范圍）。25②

順序封鎖法——事務(wù)按預(yù)先確定的數(shù)據(jù)封鎖順序?qū)嵭蟹怄i。上例中：設(shè)封鎖順序：A→B；T1、T2均按此順序申請鎖；若T1先獲得A、B鎖；T2則先申請A鎖，等待；T1釋放A、B鎖；T2獲得鎖運行。特征：無死鎖；順序難以維護；封鎖對象難以確定（運行時確定封鎖對象）。262）診斷與解除A）超時法B）等待圖法①

構(gòu)造一事務(wù)等待圖；②

周期性檢測該等待圖；③

判斷存在回路否；④

存在，則撤消某一事務(wù)選擇一個處理死鎖代價最小的事務(wù)（NP難度問題），釋放所有鎖，使其它事務(wù)繼續(xù)運行。2711.4并發(fā)操作調(diào)度11.4.1正確性標準1）單個事務(wù)——若非并發(fā)的執(zhí)行，每個事務(wù)都能保證DB的正確性。

（上述問題，都是因事務(wù)并發(fā)執(zhí)行產(chǎn)生）2）多個事務(wù)——多個事務(wù)以任意串行方式執(zhí)行都能保證DB的正確性。給定三個事務(wù)：T1，

T2，

T3。T1→T2→T3T1→T3→T2T2→T1→T3T2→T3→T1T3→T1→T2T3→T2→T1

顯然，任何一事務(wù)并發(fā)執(zhí)行時禁止其它事務(wù)執(zhí)行，總能保證DB正確性，但不利于數(shù)據(jù)共享。283）可串行化調(diào)度（serialigableity）——當且僅當多個事務(wù)并發(fā)執(zhí)行的結(jié)果與這些事務(wù)按某一順序串行執(zhí)行的結(jié)果相同時，則該并發(fā)執(zhí)行是可串行化的。（可串行化調(diào)度是并發(fā)事務(wù)正確性的唯一準則）例：有兩個事務(wù)TA，TB（A=10,B=2,C=0）包含如下操作序列TA：讀B；A:=B+1；寫回A；TB：讀C；讀A；B:=A+1；寫回B；則至少可能有四種不同的調(diào)度方式。

29①

串行調(diào)度1

先執(zhí)行TA，再執(zhí)行TB——RA(B)WA(A)RB(C)RB(A)WB(B)；結(jié)果：A=3，B=4。30②串行調(diào)度2

先執(zhí)行TB，再執(zhí)行TA——RB(C)RB(A)WB(B)RA(B)WA(A)；執(zhí)行結(jié)果：A=12，B=11。31③

交錯執(zhí)行(不可串行化)調(diào)度

兩事務(wù)TA、TB按ti并發(fā)執(zhí)行——RA(B)RB(C)RB(A)WA(A)WB(B)，結(jié)果為A=3，B=11。按事務(wù)并發(fā)可串行化的正確性準則，本結(jié)果錯誤，其結(jié)果與TA、TB兩個串行執(zhí)行的任何結(jié)果（A=3，B=4；A=12，B=11）均不同。

32④

交錯執(zhí)行(可串行化)調(diào)度

按ti交錯執(zhí)行——RA(B)RB(C)WA(A)RB(A)WB(B)；執(zhí)行結(jié)果：A=3，B=4。該結(jié)果正確，因為與串行化調(diào)度1結(jié)果相同，該調(diào)度是可串行化調(diào)度。

3311.4.2沖突可串行化調(diào)度——可串行化調(diào)度的充分而非必要條件。

沖突操作

①

Ri(x)與Wj(x)②Wi(x)與Wj(x)

操作順序的交換（可交換、不可交換）——不同事務(wù)的沖突操作和同一事務(wù)的兩個操作均是不可交換的。否則可能使操作序列的結(jié)果不等價。

在可交換的前提下，若干事務(wù)的操作交換順序的結(jié)果是一個串行調(diào)度，則稱這些事務(wù)是沖突可串行化的。

34例：Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

經(jīng)過沖突等價的操作交換，得到如下調(diào)度序列

Sc2=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)

顯然，Sc2等價于先執(zhí)行T1再執(zhí)行T2的串行調(diào)度，因此，Sc1是一個沖突可串行化的調(diào)度。例：有三個事務(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)

L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)

L1是一個串行調(diào)度，L2不能實現(xiàn)沖突可串行化，但是L2是可串行化的，因為其結(jié)果等價于L1的結(jié)果。35問題思考沖突可串行化：在完全驗證可串行化難以實施的情況下尋找接近答案的解決方案還有沒有更好的等價方案？

視圖可串行化3611.5兩段鎖（2PL：two-phaselocking）協(xié)議11.5.1概述1)封鎖協(xié)議的概念——申請、持有和釋放鎖的規(guī)則。2)目的——實現(xiàn)正確的并發(fā)操作調(diào)度。 3)鎖協(xié)議的類別①支持一致性維護的三級封鎖協(xié)議；②支持并發(fā)調(diào)度可串行化的兩段鎖協(xié)議；③避免死鎖協(xié)議。11.5.2兩階段鎖1）含義事務(wù)分為兩個階段，第一階段稱為擴展階段（獲得鎖）；第二階段稱為收縮階段（釋放鎖）。37例：T1封鎖序列：SlockA…SlockB…XlockC…UnlockB…UnlockA…UnlockC；正確的遵守2PL協(xié)議，所有獲得鎖均在釋放鎖之前。例：T2封鎖序列：SlockA…UnlockA…SlockB…XlockC…UnlockC…UnlockB；不正確（未遵守2PL協(xié)議）：不是所有申請鎖均在釋放之前。382）策略①

在對任何數(shù)據(jù)讀、寫之前，須先獲得該數(shù)據(jù)鎖（且）；②

在釋放一個封鎖之后，該事務(wù)不能再申請任何其它鎖。3）目標實現(xiàn)并發(fā)操作調(diào)度的可串行化。（釋放一個鎖之后又繼續(xù)去獲得另一個鎖的事務(wù)仍然可能產(chǎn)生錯誤結(jié)果）394）定理若所有事務(wù)都遵守2PL協(xié)議，則對這些事務(wù)的所有并發(fā)調(diào)度策略都是可串行化的。證明步驟：①

按Lock、UnLock操作中wait關(guān)系的序列建立有向圖G；②假設(shè)不是可串行化調(diào)度；③G中必存在沖突環(huán)路（蟲洞定理）：Ti1→Ti2→……→Tjp→Ti1；其中某個沖突事務(wù)獲得鎖的前提是前面的沖突事務(wù)釋放鎖。④Ti1解鎖后又有Ti1加鎖；⑤“④”與Ti1的兩階段事務(wù)假設(shè)矛盾。證畢5）說明2PL協(xié)議是可串行化的充分條件，不是必要條件。遵守兩階段鎖協(xié)議的事務(wù)可能發(fā)生死鎖。

40例①：2PL可串行調(diào)度

TA、TB各自的所有申請獲得鎖均在釋放之前，符合2PL協(xié)議的可串行調(diào)度。

41例②

不符合2PL可串行化調(diào)度

42顯然不符合2PL協(xié)議結(jié)果A=3，B=4可串行化調(diào)度。6）2PL類型①

嚴格2PL協(xié)議（strict2PL-P）

X封鎖必須保留到事務(wù)的Commit操作。避免級聯(lián)回滾。②

精確2PL協(xié)議（rigorous2PL-P）所有封鎖都必須保留到commit操作。按照提交的順序串行化。4311.6封鎖粒度（granularity）——被封鎖數(shù)據(jù)的范圍。1、邏輯單元整個DB、整個關(guān)系、整個索引、元組、索引項、屬性值集、屬性值。2、物理單元塊、數(shù)據(jù)頁、索引頁。3、評價1）粒度大：被封鎖對象少，并發(fā)性差，開銷小。2）粒度小：被封鎖對象多，并發(fā)性高，開銷大。444、一般策略1）需常存取多個關(guān)系的大量元組時宜采用DB級粒度；2）需常存取單個關(guān)系大量元組時宜采用關(guān)系級；3）需常存取單個關(guān)系少量元組時宜采用元組級；4）一般不采用屬性級；5）物理單元一般不宜采用。5、一般規(guī)則1）鎖住了大范圍，則不再申請鎖住其中部分；2）反之亦然。

45多粒度鎖封鎖協(xié)議

對結(jié)點的加鎖意味著后裔結(jié)點也被加以同樣類型的鎖。封鎖方式1）顯式——直接施加在結(jié)點本身2）隱式——由于上級結(jié)點的封鎖導(dǎo)致的本節(jié)點隱含著施加了相同類型的鎖。46多粒度鎖申請的授予條件1）檢查數(shù)據(jù)對象上有無顯式封鎖與之沖突；2）檢查上級結(jié)點上有無封鎖與本結(jié)點沖突；3）檢查下級結(jié)點上有無封鎖與本結(jié)點沖突。47校驗已有的隱式封鎖沖突校驗欲施加的隱式封鎖的沖突6、意向鎖如果對某個結(jié)點加意向鎖，則表示該結(jié)點的某個子孫結(jié)點正在或擬施加相應(yīng)的非意向鎖。對任一結(jié)點加鎖時，必須先對它的上層結(jié)點加意向鎖?！岣呦到y(tǒng)并發(fā)度，減少加鎖和解鎖的開銷，被商用產(chǎn)品廣泛采用。1）IS鎖表示某個子孫結(jié)點擬加S鎖2）IX鎖表示某個子孫結(jié)點擬加X鎖