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

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

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

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

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

①

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

目標防止鏈式夭折。③

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

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

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

目標保證DB可靠性4③

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

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

511.2并發(fā)控制1、問題的提出問題1）丟失更新（lostupdate）——兩個以上事務從DB中讀入同一數(shù)據(jù)并修改之，其中一事務的提交結果破壞了另一事務的提交結果，導致該事務對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?！B對X的修改履蓋了TA對X修改，使TA之修改丟失。（若為飛機訂票，則TA、TB實賣2張票，但系統(tǒng)中只表現(xiàn)賣了一張票）

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

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

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

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

一事務讀取數(shù)據(jù)后，另一事務插入了一些新數(shù)據(jù)（多了）。（幻行現(xiàn)象）10Sc2=RA(A)RA(B)RB(B)WB(B)RA(A)RA(B)調度的文本表達方式：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恢復為100；·TB此時讀出的x（200）數(shù)據(jù)與DB實際值(100)不一致，即TB讀到的不正確的“臟”數(shù)據(jù)。2.上述問題的原因多事務并發(fā)操作DB被壞了事務的隔離性，導致了數(shù)據(jù)不一致性。3.方法并發(fā)控制(正確的并發(fā)操作調度策略)。

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

相容矩陣：

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

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

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

23242、產生條件①

互斥（排它性控制）；②

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

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

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

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

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

構造一事務等待圖；②

周期性檢測該等待圖；③

判斷存在回路否；④

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

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

T2，

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

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

29①

串行調度1

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

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

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

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

32④

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

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

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

沖突操作

①

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

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

在可交換的前提下，若干事務的操作交換順序的結果是一個串行調度，則稱這些事務是沖突可串行化的。

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

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

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

顯然，Sc2等價于先執(zhí)行T1再執(zhí)行T2的串行調度，因此，Sc1是一個沖突可串行化的調度。例：有三個事務T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)，兩種調度方案：

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

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

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

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

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

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

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

40例①：2PL可串行調度

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

41例②

不符合2PL可串行化調度

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

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

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

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

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

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