第8章 并發(fā)控制

1、silberschatz, korth and sudarshan16.1database system concepts 3rd editionn本章內(nèi)容參考本章內(nèi)容參考:數(shù)據(jù)庫概念數(shù)據(jù)庫概念(第四版第四版) by a. silberschatzchapter 16 concurrency control補充內(nèi)容補充內(nèi)容n本章內(nèi)容特色本章內(nèi)容特色:若干協(xié)議，實現(xiàn)時編程較難若干協(xié)議，實現(xiàn)時編程較難理論上有難度，細致（如時間戳，等候圖等）理論上有難度，細致（如時間戳，等候圖等）有些協(xié)議至今沒有實現(xiàn)有些協(xié)議至今沒有實現(xiàn)n本章要解決的關(guān)鍵問題：本章要解決的關(guān)鍵問題：如何實現(xiàn)隔離性，保證一致性如何實現(xiàn)

2、隔離性，保證一致性silberschatz, korth and sudarshan16.2database system concepts 3rd editionnintroduction to isolationndependency model of isolationntransaction dependency relationsn基于鎖的協(xié)議基于鎖的協(xié)議n基于時間戳的協(xié)議基于時間戳的協(xié)議n基于驗證的協(xié)議基于驗證的協(xié)議n多粒度多粒度n多版本多版本n死鎖處理死鎖處理n插入與刪除操作插入與刪除操作n索引結(jié)構(gòu)中的并發(fā)索引結(jié)構(gòu)中的并發(fā)silberschatz, korth and sudar

3、shan16.3database system concepts 3rd editionintroduction to isolationn系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)vs. 不變式不變式(invariant) “如果向如果向emp 插入一個記錄，相應地必須向插入一個記錄，相應地必須向zip 插入一條記錄。插入一條記錄?！?“如果如果emp的一個副本被更新的一個副本被更新,其余副本也必須以同樣的方式被更新。其余副本也必須以同樣的方式被更新?！?“如果一個程序改變了帳戶余額，有關(guān)的修改必須記錄在案。如果一個程序改變了帳戶余額，有關(guān)的修改必須記錄在案?！眓如果滿足所有這些不變式，則系統(tǒng)狀態(tài)被認為是一致的如果滿

4、足所有這些不變式，則系統(tǒng)狀態(tài)被認為是一致的n通常一個狀態(tài)在向另外一個新的且一致性狀態(tài)轉(zhuǎn)換時，通常一個狀態(tài)在向另外一個新的且一致性狀態(tài)轉(zhuǎn)換時，可能會出現(xiàn)短暫的不一致可能會出現(xiàn)短暫的不一致n例如，向例如，向emp 表插入一條記錄，不可能使表插入一條記錄，不可能使emp 以及以及zip 索引的插入完全同步索引的插入完全同步n幾乎任何一個涉及多個對象更新的變換，都會使它們之幾乎任何一個涉及多個對象更新的變換，都會使它們之間有短暫的不一致性間有短暫的不一致性silberschatz, korth and sudarshan16.4database system concepts 3rd editioni

5、ntroduction to isolationn為了應付這些短暫的不一致性，將多個相關(guān)操作以組的方式形成事務(wù)，以為了應付這些短暫的不一致性，將多個相關(guān)操作以組的方式形成事務(wù)，以保持一致性的約束保持一致性的約束.一個從一致性的系統(tǒng)狀態(tài)開始的事務(wù)，其間會導致臨時一個從一致性的系統(tǒng)狀態(tài)開始的事務(wù)，其間會導致臨時的不一致狀態(tài)，但是在事務(wù)結(jié)束時系統(tǒng)會進入一個新的一致狀態(tài)的不一致狀態(tài)，但是在事務(wù)結(jié)束時系統(tǒng)會進入一個新的一致狀態(tài)n事務(wù)是一致性的單位，這就是事務(wù)事務(wù)是一致性的單位，這就是事務(wù)acid特性中的特性中的c (一致性一致性)的含義的含義n如果事務(wù)是隔離地一一在運行，那么每一個事務(wù)可以知道其上一個事

6、務(wù)所如果事務(wù)是隔離地一一在運行，那么每一個事務(wù)可以知道其上一個事務(wù)所導致的一致性狀態(tài)導致的一致性狀態(tài)n但是，但是， 如果多個事務(wù)并發(fā)執(zhí)行，那么某些事務(wù)的輸入和后續(xù)行為或許會不如果多個事務(wù)并發(fā)執(zhí)行，那么某些事務(wù)的輸入和后續(xù)行為或許會不一致，即使每一個隔離執(zhí)行的事務(wù)都是正確的一致，即使每一個隔離執(zhí)行的事務(wù)都是正確的,并發(fā)事務(wù)的執(zhí)行必須加以控并發(fā)事務(wù)的執(zhí)行必須加以控制以便正確的程序不會失效制以便正確的程序不會失效n這就是事務(wù)這就是事務(wù)acid特性中的特性中的i(隔離性隔離性)的含義的含義silberschatz, korth and sudarshan16.5database system conc

7、epts 3rd editionintroduction to isolationn實現(xiàn)隔離最簡單的方式就是一次只運行一個程序?qū)崿F(xiàn)隔離最簡單的方式就是一次只運行一個程序 (事務(wù)事務(wù),前提是前提是:n如果所有的程序都很短小，如果所有數(shù)據(jù)可以集中存放如果所有的程序都很短小，如果所有數(shù)據(jù)可以集中存放在主存中，且如果所有的數(shù)據(jù)都由一個處理器來存取，在主存中，且如果所有的數(shù)據(jù)都由一個處理器來存取，這時沒必要考慮并發(fā)來存取這時沒必要考慮并發(fā)來存取這些程序可以簡單地以這些程序可以簡單地以順序方式執(zhí)行順序方式執(zhí)行n問題是，這些情況中包含了太多的問題是，這些情況中包含了太多的”如果如果”n因此，系統(tǒng)必須以某種方

8、式提供并發(fā)控制，保證隔離性因此，系統(tǒng)必須以某種方式提供并發(fā)控制，保證隔離性，使之滿足并發(fā)的第一法則，使之滿足并發(fā)的第一法則n人們已經(jīng)嘗試過許多種提供自動隔離的方法人們已經(jīng)嘗試過許多種提供自動隔離的方法n其中，一個公認可行的解決方案就是封鎖其中，一個公認可行的解決方案就是封鎖silberschatz, korth and sudarshan16.6database system concepts 3rd editionintroduction to isolationn對封鎖方法，仍有一系列費解的問題對封鎖方法，仍有一系列費解的問題n如果并發(fā)控制機制代價過高，會使得代價高于收益。通如果并發(fā)控制機

9、制代價過高，會使得代價高于收益。通常，復雜的算法實現(xiàn)起來和執(zhí)行起來也比較復雜常，復雜的算法實現(xiàn)起來和執(zhí)行起來也比較復雜n第二法則主張使用簡單的算法第二法則主張使用簡單的算法silberschatz, korth and sudarshan16.7database system concepts 3rd editionintroduction to isolationn最簡單的封鎖協(xié)議是給每個對象加一個鎖。如果這個需要鎖同時授最簡單的封鎖協(xié)議是給每個對象加一個鎖。如果這個需要鎖同時授于另外一個事務(wù)，該事務(wù)將等待這個鎖被釋放于另外一個事務(wù)，該事務(wù)將等待這個鎖被釋放n封鎖是一種實現(xiàn)串行化的機制，這樣

10、就確保任一時刻僅僅只有一個封鎖是一種實現(xiàn)串行化的機制，這樣就確保任一時刻僅僅只有一個事務(wù)在存取一個對象事務(wù)在存取一個對象n通過細化鎖的粒度（鎖覆蓋的數(shù)據(jù)多少），可以提高并發(fā)度通過細化鎖的粒度（鎖覆蓋的數(shù)據(jù)多少），可以提高并發(fā)度n鎖的概念可以追溯到幾千年以前，它是緊接著門之后的發(fā)明鎖的概念可以追溯到幾千年以前，它是緊接著門之后的發(fā)明n現(xiàn)在這個概念（思想）在操作系統(tǒng)領(lǐng)域里已經(jīng)很普遍了現(xiàn)在這個概念（思想）在操作系統(tǒng)領(lǐng)域里已經(jīng)很普遍了, 在該領(lǐng)域在該領(lǐng)域中，鎖又被稱為中，鎖又被稱為: 信號量（信號量（ semaphores），）， 管程（管程（ monitors） 臨界區(qū)（臨界區(qū)（ critical

11、sections ），）， 串行重用資源（串行重用資源（ serially reuseable reuseable resources ）silberschatz, korth and sudarshan16.8database system concepts 3rd editionintroduction to isolationn事務(wù)系統(tǒng)對并發(fā)控制的主要貢獻是，進一步提煉了原有事務(wù)系統(tǒng)對并發(fā)控制的主要貢獻是，進一步提煉了原有的這些思想，納入了自動封鎖以及把事務(wù)的這些思想，納入了自動封鎖以及把事務(wù)undo/redo 算算法同封鎖算法結(jié)合起來法同封鎖算法結(jié)合起來n這種方法給應用程序開發(fā)者一個極

12、簡單的并發(fā)控制和異這種方法給應用程序開發(fā)者一個極簡單的并發(fā)控制和異常處理的模型常處理的模型n事務(wù)處理系統(tǒng)自動地申請加鎖并且登錄日志以維護事務(wù)處理系統(tǒng)自動地申請加鎖并且登錄日志以維護acid 特性特性n應用程序設(shè)計人員可能疏忽并發(fā)控制問題，除非存在著應用程序設(shè)計人員可能疏忽并發(fā)控制問題，除非存在著許多事務(wù)存取同一個對象而引起的性能問題許多事務(wù)存取同一個對象而引起的性能問題,所謂的熱點所謂的熱點（hotspots hotspots）n隔離性理論是允許自動封鎖而帶來的重要結(jié)果隔離性理論是允許自動封鎖而帶來的重要結(jié)果silberschatz, korth and sudarshan16.9databa

13、se system concepts 3rd editiondependency model of isolationn理解隔離性結(jié)果最簡單的方式，是根據(jù)事務(wù)的輸入和輸理解隔離性結(jié)果最簡單的方式，是根據(jù)事務(wù)的輸入和輸出來理解出來理解n事務(wù)要么讀一個對象查看其狀態(tài)，要么寫一個對象改變事務(wù)要么讀一個對象查看其狀態(tài)，要么寫一個對象改變對象的狀態(tài)對象的狀態(tài)n設(shè)想創(chuàng)建和消除對象只不過是改寫其狀態(tài)而已。以這種設(shè)想創(chuàng)建和消除對象只不過是改寫其狀態(tài)而已。以這種粗略的方式來看，事務(wù)可以看作是一連串對象的讀寫操粗略的方式來看，事務(wù)可以看作是一連串對象的讀寫操作作n兩個不同事務(wù)對同一個對象的讀操作不會破壞一致性，兩

14、個不同事務(wù)對同一個對象的讀操作不會破壞一致性，因為讀操作不會改變對象的狀態(tài)（假定其狀態(tài)初始是一因為讀操作不會改變對象的狀態(tài)（假定其狀態(tài)初始是一致的）致的）n因此，只有寫操作有可能帶來問題因此，只有寫操作有可能帶來問題silberschatz, korth and sudarshan16.10database system concepts 3rd editiondependency model of isolationn同一事務(wù)對同一個對象的兩個寫操作也不會違同一事務(wù)對同一個對象的兩個寫操作也不會違反一致性，反一致性， acid特性假定事務(wù)知道它正在干什特性假定事務(wù)知道它正在干什么么nacid

15、特性假定：如果事務(wù)隔離地運行，最終會特性假定：如果事務(wù)隔離地運行，最終會正確地轉(zhuǎn)換系統(tǒng)狀態(tài)正確地轉(zhuǎn)換系統(tǒng)狀態(tài)n因此，只有兩個并發(fā)事務(wù)之間同寫操作有關(guān)聯(lián)因此，只有兩個并發(fā)事務(wù)之間同寫操作有關(guān)聯(lián)的的交叉操才可能造成不一致性或是違背隔離的的交叉操才可能造成不一致性或是違背隔離性性silberschatz, korth and sudarshan16.11database system concepts 3rd editiondependency model of isolationsilberschatz, korth and sudarshan16.12database system concep

16、ts 3rd editionstatic vs. dynamic allocationsilberschatz, korth and sudarshan16.13database system concepts 3rd editionstatic vs. dynamic allocationn動態(tài)分配系統(tǒng)中，每一個事務(wù)都被看作是一系動態(tài)分配系統(tǒng)中，每一個事務(wù)都被看作是一系列的行為動作而不是輸入輸出集列的行為動作而不是輸入輸出集n每個動作的請求都在其出現(xiàn)時按需調(diào)度。當一每個動作的請求都在其出現(xiàn)時按需調(diào)度。當一個動作存取一個特定的對象時，對象被動態(tài)地個動作存取一個特定的對象時，對象被動態(tài)地分配給事

17、務(wù)分配給事務(wù)n例如，只有銀行帳戶記錄和其它的一些特別的例如，只有銀行帳戶記錄和其它的一些特別的事務(wù)將要存取的記錄分配給該事務(wù)事務(wù)將要存取的記錄分配給該事務(wù), 出納員才能出納員才能運行一個銀行事務(wù)運行一個銀行事務(wù)n這樣針對不同帳戶的事務(wù)可以并發(fā)地且隔離地這樣針對不同帳戶的事務(wù)可以并發(fā)地且隔離地執(zhí)行執(zhí)行silberschatz, korth and sudarshan16.14database system concepts 3rd editiontransaction dependency relationsn圖中顯示了兩個在對象圖中顯示了兩個在對象e 上的事務(wù)上的事務(wù)t1 和和t2 ，所可能有

18、，所可能有的三種讀寫執(zhí)行序列操作的三種讀寫執(zhí)行序列操作read-write, write-read, write-writen沒有沒有read-read 依賴，因為讀同一個版本的多個事依賴，因為讀同一個版本的多個事務(wù)不會產(chǎn)生對另外一個版本的依賴務(wù)不會產(chǎn)生對另外一個版本的依賴silberschatz, korth and sudarshan16.15database system concepts 3rd editiontransaction dependency relationsn一個依賴圖可以看作一個時間序列一個依賴圖可以看作一個時間序列:如果事務(wù)如果事務(wù)t1 到事務(wù)到事務(wù)t2 有一條邊，

19、那么有一條邊，那么t1 訪問的對象隨后會被訪問的對象隨后會被t2 訪訪問，并且這些訪問中至少有一個產(chǎn)生一個新的版本問，并且這些訪問中至少有一個產(chǎn)生一個新的版本在這種意義上，在這種意義上， 在這種意義上，在這種意義上，t1 在在 t2之前運行之前運行在事務(wù)的純順序執(zhí)行之中，在事務(wù)的純順序執(zhí)行之中， t1運行結(jié)束，再運行運行結(jié)束，再運行t2 t結(jié)束，所有的結(jié)束，所有的依賴箭頭都是從依賴箭頭都是從t1 指向指向t2 n隔離定理的主要結(jié)論是：任何一個沒有環(huán)的依賴圖都暗示了隔離定理的主要結(jié)論是：任何一個沒有環(huán)的依賴圖都暗示了事務(wù)的一種隔離執(zhí)行方式事務(wù)的一種隔離執(zhí)行方式silberschatz, kort

20、h and sudarshan16.16database system concepts 3rd editionthe three badtransaction dependenciesn一個令人驚奇的結(jié)論是：這三種不一致的基本形式覆蓋了所一個令人驚奇的結(jié)論是：這三種不一致的基本形式覆蓋了所有的情況，如果他們可以被防止發(fā)生，那將不會有并發(fā)異常有的情況，如果他們可以被防止發(fā)生，那將不會有并發(fā)異常，事務(wù)將表現(xiàn)為隔離運行的狀態(tài)，事務(wù)將表現(xiàn)為隔離運行的狀態(tài)silberschatz, korth and sudarshan16.17database system concepts 3rd edition

21、formal model of isolationn為了更精確地描述并發(fā)和恢復的問題，需要一個為了更精確地描述并發(fā)和恢復的問題，需要一個形式化的模型。因為，這些問題是復雜而又微妙形式化的模型。因為，這些問題是復雜而又微妙的，而形式化有助于擺脫描述問題的，而形式化有助于擺脫描述問題n“隔離性隔離性”的幾種等價定義的幾種等價定義直觀定義直觀定義:依據(jù)用戶事務(wù)特性，直觀定義是為了方便應用程序設(shè)依據(jù)用戶事務(wù)特性，直觀定義是為了方便應用程序設(shè)計人員和用戶用來描述系統(tǒng)的行為計人員和用戶用來描述系統(tǒng)的行為形式化定義形式化定義:依據(jù)系統(tǒng)執(zhí)行的過程和依賴圖，形式化定義是為了依據(jù)系統(tǒng)執(zhí)行的過程和依賴圖，形式化定義

22、是為了陳述和證明隔離性的性質(zhì)。陳述和證明隔離性的性質(zhì)。操作上的定義操作上的定義:依據(jù)封鎖協(xié)議，操作上的定義是為了用來指導系依據(jù)封鎖協(xié)議，操作上的定義是為了用來指導系統(tǒng)的實現(xiàn)。統(tǒng)的實現(xiàn)。n下面將要對沖突可串行性作形式化描述，給出嚴下面將要對沖突可串行性作形式化描述，給出嚴格定義格定義silberschatz, korth and sudarshan16.18database system concepts 3rd edition插曲插曲:畫的圓沒有說的圓圓畫的圓沒有說的圓圓n把想明白的事情表達清楚是作科研的基本功把想明白的事情表達清楚是作科研的基本功,下面是從下面是從let開始開始的一種下定義的

23、方法。的一種下定義的方法。n例如例如:圓的定義圓的定義定義定義1:右邊的圖形稱為圓右邊的圖形稱為圓(通俗，但不及格通俗，但不及格)定義定義2:到一點的距離相等的軌跡稱為圓到一點的距離相等的軌跡稱為圓(及格及格)定義定義3:在一個平面上到一點的距離相等的軌跡稱為圓在一個平面上到一點的距離相等的軌跡稱為圓(良良)定義定義4:let o be a point over planet p, r = 0, and d(x, y) be the distance between points x and y.then the set c=x | x in p , d(x,o)=r is said to b

24、e the circle with center o and radius r. (信息完整信息完整,嚴格規(guī)范嚴格規(guī)范,所以所以:優(yōu)優(yōu))n嚴格定義好處嚴格定義好處:有了符號體系（模型），為后續(xù)研究奠定基礎(chǔ)有了符號體系（模型），為后續(xù)研究奠定基礎(chǔ)silberschatz, korth and sudarshan16.19database system concepts 3rd editionformal model of isolationn隔離性隔離性(用戶定義用戶定義1):n事務(wù)處理系統(tǒng)可以并發(fā)地執(zhí)行事務(wù)，但它的結(jié)果事務(wù)處理系統(tǒng)可以并發(fā)地執(zhí)行事務(wù)，但它的結(jié)果如同順序執(zhí)行一樣。就應用程序而言，

25、事務(wù)好象如同順序執(zhí)行一樣。就應用程序而言，事務(wù)好象是在沒有并發(fā)的情況下運行；事務(wù)的確切執(zhí)行順是在沒有并發(fā)的情況下運行；事務(wù)的確切執(zhí)行順序是由系統(tǒng)控制的，系統(tǒng)行為等價于事務(wù)的某種序是由系統(tǒng)控制的，系統(tǒng)行為等價于事務(wù)的某種順序執(zhí)行，其造成的表面現(xiàn)象是一個事務(wù)執(zhí)行完順序執(zhí)行，其造成的表面現(xiàn)象是一個事務(wù)執(zhí)行完畢后，下一個事務(wù)才開始執(zhí)行畢后，下一個事務(wù)才開始執(zhí)行silberschatz, korth and sudarshan16.20database system concepts 3rd editionformal model of isolationn隔離性隔離性(用戶定義用戶定義2)：這是更為程

26、序化的定義，稱：這是更為程序化的定義，稱事務(wù)事務(wù)t與其它事務(wù)是隔離的，如果：與其它事務(wù)是隔離的，如果：（0） t不會重寫其它事務(wù)的臟數(shù)據(jù)不會重寫其它事務(wù)的臟數(shù)據(jù)（1） t所寫的數(shù)據(jù)，在所寫的數(shù)據(jù)，在t提交（提交（commit work ）之前，不會被其它事）之前，不會被其它事務(wù)讀或者寫務(wù)讀或者寫（2） t不讀臟數(shù)據(jù)不讀臟數(shù)據(jù)（3）在）在t提交之前，其它事務(wù)不會寫提交之前，其它事務(wù)不會寫t所要讀的數(shù)據(jù)所要讀的數(shù)據(jù)條件條件(0) 和和 (1)排除了丟失修改排除了丟失修改, (2) 防止了讀臟數(shù)據(jù)防止了讀臟數(shù)據(jù) (3)防止了不可重復防止了不可重復讀讀n用用bernstein, hadzilacos,

27、 goodman1987,p.36 的記法，定義的記法，定義1是是sr ，定義，定義2是兩階段封鎖（是兩階段封鎖（ 2pl）n sr 2pl ：一些隔離性方法比這里描述的封鎖機制更具一般性一些隔離性方法比這里描述的封鎖機制更具一般性silberschatz, korth and sudarshan16.21database system concepts 3rd editionformal model: actions and transactionssilberschatz, korth and sudarshan16.22database system concepts 3rd editi

28、onformal model: simple transactionn系統(tǒng)支持系統(tǒng)支持對象上的動作對象上的動作read，write ，xlock ，slock ，unlock三個一般性的動作三個一般性的動作 begin ，commit，rollbackn一個簡化事務(wù)是由一個簡化事務(wù)是由read，write， xlock，slock，unlock 等動作組成的等動作組成的silberschatz, korth and sudarshan16.23database system concepts 3rd editionlocks cover actions(10/21)silberschatz,

29、korth and sudarshan16.24database system concepts 3rd editionwell formed and two-phasedtransactionssilberschatz, korth and sudarshan16.25database system concepts 3rd editionwell formed and two-phasedtransactionssilberschatz, korth and sudarshan16.26database system concepts 3rd editiontransaction hist

30、oryn一組事務(wù)的所有動作序列，在保持各自順序的情況下，一組事務(wù)的所有動作序列，在保持各自順序的情況下，歸并成的一個單一序列，我們稱之為這組事務(wù)的一個歸并成的一個單一序列，我們稱之為這組事務(wù)的一個調(diào)調(diào)度度n最簡單的調(diào)度是首先運行一個事務(wù)的所有動作，然后再最簡單的調(diào)度是首先運行一個事務(wù)的所有動作，然后再運行另外一個事務(wù)的所有動作，如此一直下去，這樣的運行另外一個事務(wù)的所有動作，如此一直下去，這樣的“一次一個事務(wù)一次一個事務(wù)”的調(diào)度稱為的調(diào)度稱為串行調(diào)度串行調(diào)度(serial history)n調(diào)度的定義暗指了每個動作作為對象狀態(tài)的一個調(diào)度的定義暗指了每個動作作為對象狀態(tài)的一個acid 轉(zhuǎn)轉(zhuǎn)換：即

31、每個動作是當作一個換：即每個動作是當作一個acid 步驟來執(zhí)行的步驟來執(zhí)行的n下面的問題是，對給定的一組下面的問題是，對給定的一組acid 動作，如何既能并發(fā)動作，如何既能并發(fā)執(zhí)行這些動作，而又保持事務(wù)的隔離性執(zhí)行這些動作，而又保持事務(wù)的隔離性silberschatz, korth and sudarshan16.27database system concepts 3rd editionsummary of definitionsn事務(wù)是在對象上的事務(wù)是在對象上的 read，write ，slock和和xlock 動作的序列，它以動作的序列，它以commit 或或 rollback動作結(jié)尾動

32、作結(jié)尾n含含commit或或rollback的一般事務(wù)可以轉(zhuǎn)化成為簡化的一般事務(wù)可以轉(zhuǎn)化成為簡化事務(wù)，它只含事務(wù)，它只含read, write,slock,xlock和和 unlock動作動作n如果事務(wù)的每個如果事務(wù)的每個read，write，unlock 都被相應的都被相應的鎖覆蓋，且所有的鎖都是在事務(wù)結(jié)束時釋放，那么我們鎖覆蓋，且所有的鎖都是在事務(wù)結(jié)束時釋放，那么我們稱這樣的事務(wù)是稱這樣的事務(wù)是規(guī)范的規(guī)范的n如果一個事務(wù)可以分成兩個階段，只請求封鎖的擴展階如果一個事務(wù)可以分成兩個階段，只請求封鎖的擴展階段，和只釋放封鎖的收縮階段，那么我們稱之為段，和只釋放封鎖的收縮階段，那么我們稱之為兩階

33、段兩階段的事務(wù)的事務(wù)silberschatz, korth and sudarshan16.28database system concepts 3rd editionsilberschatz, korth and sudarshan16.29database system concepts 3rd editionsilberschatz, korth and sudarshan16.30database system concepts 3rd editionn鎖兼容性矩陣鎖兼容性矩陣n如果事務(wù)對某數(shù)據(jù)項的鎖請求與其他事務(wù)在該數(shù)據(jù)項如果事務(wù)對某數(shù)據(jù)項的鎖請求與其他事務(wù)在該數(shù)據(jù)項上已有的鎖兼容上

34、已有的鎖兼容, 則請求被批準則請求被批準n任意數(shù)目的事務(wù)可對同一數(shù)據(jù)持有共享鎖任意數(shù)目的事務(wù)可對同一數(shù)據(jù)持有共享鎖; 但若一事務(wù)但若一事務(wù)對某數(shù)據(jù)持有排他鎖對某數(shù)據(jù)持有排他鎖, 則其他事務(wù)不得持有該數(shù)據(jù)上的則其他事務(wù)不得持有該數(shù)據(jù)上的任何鎖任何鎖n若不能授予鎖若不能授予鎖, 則使請求事務(wù)等待持有不兼容鎖的所有則使請求事務(wù)等待持有不兼容鎖的所有其他事務(wù)釋放鎖其他事務(wù)釋放鎖. 然后才可授予鎖然后才可授予鎖silberschatz, korth and sudarshan16.31database system concepts 3rd editionn執(zhí)行封鎖的事務(wù)例執(zhí)行封鎖的事務(wù)例: t2: l

35、ock-s(a); read (a); unlock(a); lock-s(b); read (b); unlock(b); display(a+b)n上例中的封鎖不足以保證可串行化上例中的封鎖不足以保證可串行化 若若a和和b 在讀操作之間被修改在讀操作之間被修改, 則顯示的總和是錯誤的則顯示的總和是錯誤的n鎖協(xié)議鎖協(xié)議是所有事務(wù)在請求與釋放鎖時遵守的規(guī)則集合是所有事務(wù)在請求與釋放鎖時遵守的規(guī)則集合n鎖協(xié)議對可能出現(xiàn)的調(diào)度集合加以限制鎖協(xié)議對可能出現(xiàn)的調(diào)度集合加以限制silberschatz, korth and sudarshan16.32database system concepts 3

36、rd editionn考慮下面的部分調(diào)度考慮下面的部分調(diào)度nt3 和和t4 都不能繼續(xù)都不能繼續(xù) 執(zhí)行執(zhí)行l(wèi)ock-s(b) 使使t4 等待等待t3 釋放它持有的釋放它持有的b上的上的鎖鎖, 而執(zhí)行而執(zhí)行 lock-x(a) 使使t3 等待等待t4 釋放它持有的釋放它持有的a上的鎖上的鎖n這種情形稱為死鎖這種情形稱為死鎖n為處理死鎖為處理死鎖, t3 或或t4 必須回滾并釋放它持有的鎖必須回滾并釋放它持有的鎖silberschatz, korth and sudarshan16.33database system concepts 3rd editionn多數(shù)鎖協(xié)議中都存在潛在的死鎖可能性多數(shù)

37、鎖協(xié)議中都存在潛在的死鎖可能性. 但為了鎖機制但為了鎖機制的好處的好處, 這個缺陷的引入是可以容忍的這個缺陷的引入是可以容忍的n如果并發(fā)控制管理器設(shè)計的不好還可能出現(xiàn)如果并發(fā)控制管理器設(shè)計的不好還可能出現(xiàn)餓死餓死n例如例如:一個事務(wù)可能在等待給數(shù)據(jù)項加一個事務(wù)可能在等待給數(shù)據(jù)項加x-鎖鎖, 同時一系列其他事務(wù)在同時一系列其他事務(wù)在請求并被授予同一數(shù)據(jù)項上的請求并被授予同一數(shù)據(jù)項上的s-鎖鎖同一事務(wù)因死鎖而被重復回滾同一事務(wù)因死鎖而被重復回滾n并發(fā)控制管理器可設(shè)計成能夠防止餓死并發(fā)控制管理器可設(shè)計成能夠防止餓死silberschatz, korth and sudarshan16.34datab

38、ase system concepts 3rd editionn兩階段封鎖協(xié)議預備兩階段封鎖協(xié)議預備: 封鎖資源與獲得服務(wù)的直觀解釋封鎖資源與獲得服務(wù)的直觀解釋silberschatz, korth and sudarshan16.35database system concepts 3rd editionn兩階段封鎖協(xié)議預備兩階段封鎖協(xié)議預備:封鎖資源與獲得服務(wù)的直觀解釋封鎖資源與獲得服務(wù)的直觀解釋silberschatz, korth and sudarshan16.36database system concepts 3rd editionn兩階段封鎖協(xié)議預備兩階段封鎖協(xié)議預備: 封鎖資

39、源與獲得服務(wù)的直觀解釋封鎖資源與獲得服務(wù)的直觀解釋silberschatz, korth and sudarshan16.37database system concepts 3rd editionn兩階段封鎖協(xié)議預備兩階段封鎖協(xié)議預備:封鎖資源與獲得服務(wù)的直觀解釋封鎖資源與獲得服務(wù)的直觀解釋silberschatz, korth and sudarshan16.38database system concepts 3rd editionn兩階段鎖不能避免死鎖兩階段鎖不能避免死鎖n兩階段鎖不能避免級聯(lián)回滾兩階段鎖不能避免級聯(lián)回滾n但用但用嚴格嚴格(strict)兩階段鎖兩階段鎖的改進協(xié)議可避免

40、的改進協(xié)議可避免: 事務(wù)必須保持它的所有排他鎖直至提交事務(wù)必須保持它的所有排他鎖直至提交/夭折夭折n嚴密嚴密(rigorous)兩階段鎖兩階段鎖更加嚴格更加嚴格: 所有鎖都必所有鎖都必須保持到事務(wù)提交須保持到事務(wù)提交/夭折夭折,在這種協(xié)議中事務(wù)可在這種協(xié)議中事務(wù)可按它們提交的次序串行化按它們提交的次序串行化silberschatz, korth and sudarshan16.39database system concepts 3rd editionn存在用兩階段鎖不能得到的沖突可串行化調(diào)度存在用兩階段鎖不能得到的沖突可串行化調(diào)度n即即: 給定不遵守兩階段鎖的事務(wù)給定不遵守兩階段鎖的事務(wù)ti

41、, 可以找到使可以找到使用兩階段鎖的事務(wù)用兩階段鎖的事務(wù)tj 及及ti 與與tj 的一個不是沖突的一個不是沖突可串行化的調(diào)度可串行化的調(diào)度n然而然而, 在缺少額外信息在缺少額外信息(如數(shù)據(jù)存取次序如數(shù)據(jù)存取次序)的情況的情況下下, 兩階段鎖對沖突可串行化要求來說是必要兩階段鎖對沖突可串行化要求來說是必要的的silberschatz, korth and sudarshan16.40database system concepts 3rd editionn帶有鎖轉(zhuǎn)換的兩階段鎖帶有鎖轉(zhuǎn)換的兩階段鎖: 第一階段第一階段: （趨勢：擴大封鎖，減少共享）（趨勢：擴大封鎖，減少共享） 可獲得可獲得 loc

42、k-s可獲得可獲得 lock-x可轉(zhuǎn)換可轉(zhuǎn)換 lock-s 到到 lock-x (升級升級) 第二階段第二階段:（趨勢：擴大共享，減少封鎖）（趨勢：擴大共享，減少封鎖）可釋放可釋放 lock-s可釋放可釋放 lock-x可轉(zhuǎn)換可轉(zhuǎn)換 lock-x 到到 lock-s (降級降級)n本協(xié)議確保可串行化本協(xié)議確?？纱谢? 但仍依靠程序員插入各種封鎖指令但仍依靠程序員插入各種封鎖指令silberschatz, korth and sudarshan16.41database system concepts 3rd editionn事務(wù)事務(wù)ti 發(fā)出標準的讀發(fā)出標準的讀/寫指令寫指令, 無需使用顯式

43、的封鎖調(diào)用無需使用顯式的封鎖調(diào)用n操作操作read(d) 的處理如下的處理如下:(把方便留給用戶，把困難留給系統(tǒng)） if ti 在d上有鎖 then read(d) else begin 如有必要則等待直至沒有事務(wù)在如有必要則等待直至沒有事務(wù)在d上有上有l(wèi)ock-x 授予授予ti 在在d上的上的lock-s; read(d) endsilberschatz, korth and sudarshan16.42database system concepts 3rd editionnwrite(d) 如下處理如下處理: if ti 在在d上有上有 lock-x then write(d) else

44、 begin 如有必要則等待直至沒有事務(wù)在如有必要則等待直至沒有事務(wù)在d上有任何鎖上有任何鎖, if ti 在在d上有上有l(wèi)ock-s then 將將d上的鎖升級到上的鎖升級到 lock-x else 授予授予ti 在在d上的上的 lock-x write(d) end;n所有鎖在提交所有鎖在提交/夭折之后釋放夭折之后釋放silberschatz, korth and sudarshan16.43database system concepts 3rd editionn鎖管理器鎖管理器可實現(xiàn)為單獨的進程可實現(xiàn)為單獨的進程, 事務(wù)向它發(fā)送加鎖與釋事務(wù)向它發(fā)送加鎖與釋放鎖請求放鎖請求n鎖管理器通過

45、發(fā)送鎖授予消息來回答鎖請求鎖管理器通過發(fā)送鎖授予消息來回答鎖請求(或死鎖時或死鎖時發(fā)送請事務(wù)回滾的消息發(fā)送請事務(wù)回滾的消息)n請求事務(wù)等待請求事務(wù)等待, 直至它的請求被回答直至它的請求被回答n鎖管理器維護一個稱為鎖管理器維護一個稱為鎖表鎖表的數(shù)據(jù)結(jié)構(gòu)來記錄授予的的數(shù)據(jù)結(jié)構(gòu)來記錄授予的鎖和掛起的請求鎖和掛起的請求n鎖表通常實現(xiàn)為以被鎖數(shù)據(jù)項的名字為索引的內(nèi)存散鎖表通常實現(xiàn)為以被鎖數(shù)據(jù)項的名字為索引的內(nèi)存散列表列表silberschatz, korth and sudarshan16.44database system concepts 3rd editionsilberschatz, korth

46、 and sudarshan16.45database system concepts 3rd editionn黑色矩形表示已授予的鎖黑色矩形表示已授予的鎖, 白色白色矩形表示等待的請求矩形表示等待的請求n鎖表記錄授予或請求的鎖的類型鎖表記錄授予或請求的鎖的類型n新請求加入到對某數(shù)據(jù)項的請求新請求加入到對某數(shù)據(jù)項的請求隊列的末尾隊列的末尾, 并且如果與所有以并且如果與所有以前的鎖兼容則被授予前的鎖兼容則被授予n釋放鎖請求導致請求被刪除釋放鎖請求導致請求被刪除, 并并且其后的請求被檢查看看現(xiàn)在是且其后的請求被檢查看看現(xiàn)在是否可以授予否可以授予n如果事務(wù)夭折如果事務(wù)夭折, 則該事務(wù)的所有則該事務(wù)的

47、所有等待或已批準的請求都被刪除等待或已批準的請求都被刪除n鎖管理器可能保存每個事務(wù)持有鎖管理器可能保存每個事務(wù)持有的鎖的列表的鎖的列表, 以便對此高效地實以便對此高效地實現(xiàn)現(xiàn)silberschatz, korth and sudarshan16.46database system concepts 3rd editionhash表實現(xiàn)表實現(xiàn), 高效高效)silberschatz, korth and sudarshan16.47database system concepts 3rd editionn基于圖的協(xié)議是相對于兩階段鎖協(xié)議的另一選基于圖的協(xié)議是相對于兩階段鎖協(xié)議的另一選擇擇n在所有數(shù)

48、據(jù)項集合在所有數(shù)據(jù)項集合d = d1, d2 ,., dh 上定義一上定義一個偏序個偏序(讀作goes to 或先于先于)如果如果di dj 則存取則存取di 和和dj 的任何事務(wù)都必須先存的任何事務(wù)都必須先存取取di 后存取后存取dj集合集合d可視為可視為有向無圈圖有向無圈圖(特例為樹特例為樹(有根的圖有根的圖),表示表示數(shù)據(jù)的加工流程數(shù)據(jù)的加工流程)稱為數(shù)據(jù)庫圖稱為數(shù)據(jù)庫圖n樹協(xié)議樹協(xié)議是圖協(xié)議的一種簡單形式是圖協(xié)議的一種簡單形式silberschatz, korth and sudarshan16.48database system concepts 3rd editionsilbers

49、chatz, korth and sudarshan16.49database system concepts 3rd editionn樹協(xié)議確保沖突可串行化且可避免死鎖樹協(xié)議確保沖突可串行化且可避免死鎖n樹協(xié)議中釋放鎖可比兩階段鎖協(xié)議更早發(fā)生樹協(xié)議中釋放鎖可比兩階段鎖協(xié)議更早發(fā)生較短等待時間較短等待時間, 增加并發(fā)度增加并發(fā)度協(xié)議無死鎖協(xié)議無死鎖, 不需回滾不需回滾事務(wù)的夭折仍然可能導致級聯(lián)回滾事務(wù)的夭折仍然可能導致級聯(lián)回滾 (教材中對此有改進方法教材中對此有改進方法)n然而然而, 在樹封鎖協(xié)議中在樹封鎖協(xié)議中, 事務(wù)可能對它不需要存取的數(shù)據(jù)項事務(wù)可能對它不需要存取的數(shù)據(jù)項加鎖加鎖(可能誅連

50、可能誅連(冤枉封鎖了冤枉封鎖了)太多子孫，誅九族太多子孫，誅九族)增加鎖開銷以及額外的等待時間增加鎖開銷以及額外的等待時間潛在的并發(fā)度降低潛在的并發(fā)度降低n樹協(xié)議可產(chǎn)生兩階段鎖協(xié)議不能產(chǎn)生的調(diào)度樹協(xié)議可產(chǎn)生兩階段鎖協(xié)議不能產(chǎn)生的調(diào)度, 反之亦然反之亦然.樹協(xié)議與樹協(xié)議與2pl沒絕對的強弱，各有用武之地沒絕對的強弱，各有用武之地silberschatz, korth and sudarshan16.50database system concepts 3rd editionn兩種時間戳，分別對事務(wù)，對數(shù)據(jù)兩種時間戳，分別對事務(wù)，對數(shù)據(jù)n每個事務(wù)進入系統(tǒng)時被賦予一個時間戳，若一個老事務(wù)每個事務(wù)進入

51、系統(tǒng)時被賦予一個時間戳，若一個老事務(wù)ti 具有時間戳具有時間戳ts(ti)，則一個新事務(wù)，則一個新事務(wù)tj 被賦予時間戳被賦予時間戳ts(tj) 使得使得ts(ti) ts(tj) n該協(xié)議管理并發(fā)執(zhí)行該協(xié)議管理并發(fā)執(zhí)行, 使得時間戳決定了串行化次序使得時間戳決定了串行化次序n為了保證這種行為為了保證這種行為, 該協(xié)議為每個數(shù)據(jù)該協(xié)議為每個數(shù)據(jù)q維護兩個時間戳值維護兩個時間戳值w-timestamp(q):成功執(zhí)行了成功執(zhí)行了write(q)的所有事務(wù)中的最大時間戳的所有事務(wù)中的最大時間戳r-timestamp(q):成功執(zhí)行了成功執(zhí)行了read(q)的所有事務(wù)中的最大時間戳的所有事務(wù)中的最大

52、時間戳n注注:學習時間戳協(xié)議的方法學習時間戳協(xié)議的方法聽講課，有時不能立即反應和理解聽講課，有時不能立即反應和理解需用例子，畫出時間軸，調(diào)度，需要細心體會需用例子，畫出時間軸，調(diào)度，需要細心體會silberschatz, korth and sudarshan16.51database system concepts 3rd editionn假設(shè)事務(wù)假設(shè)事務(wù)ti 發(fā)出了發(fā)出了read(q) 1. 若若ts(ti) w-timestamp(q)，則，則ti 需要讀需要讀q 的已經(jīng)的已經(jīng)被寫覆蓋了的一個值，因此，被寫覆蓋了的一個值，因此， read 操作被拒絕，操作被拒絕， ti 回滾回滾 2.

53、若若ts(ti) r-timestamp(q)，則，則read 操作執(zhí)行，并操作執(zhí)行，并且且r-timestamp(q) 置為置為r-timestamp(q) 與與ts(ti)的的最大值最大值n時戳讀法則：讀舊回卷（時戳讀法則：讀舊回卷（roll back原義，電影膠片卷原義，電影膠片卷回重放）回重放）silberschatz, korth and sudarshan16.52database system concepts 3rd editionn假設(shè)事務(wù)假設(shè)事務(wù)ti 發(fā)出發(fā)出write(q):若若ts(ti) r-timestamp(q), 則則ti 要產(chǎn)生的要產(chǎn)生的q 值是值是過去曾需要

54、的過去曾需要的, 而系統(tǒng)假設(shè)該值永遠不會產(chǎn)生而系統(tǒng)假設(shè)該值永遠不會產(chǎn)生. 于是于是, write 操作被拒絕操作被拒絕, ti 回滾回滾若若ts(ti) w-timestamp(q), 則則ti 試圖寫一個過時試圖寫一個過時的的q值值,因此因此, 這個這個write 操作被拒絕操作被拒絕, ti 回滾回滾否則否則,執(zhí)行執(zhí)行write 操作操作, 且且w-timestamp(q) 置為置為ts(ti)n時間戳寫法則：寫先于讀或以舊蓋新，否則回卷時間戳寫法則：寫先于讀或以舊蓋新，否則回卷n結(jié)論結(jié)論: 時間戳排序協(xié)議可確保任何沖突的時間戳排序協(xié)議可確保任何沖突的read 和和write 操作都能按照

55、時間戳序執(zhí)行操作都能按照時間戳序執(zhí)行silberschatz, korth and sudarshan16.53database system concepts 3rd editionn針對若干數(shù)據(jù)項的、時間戳為針對若干數(shù)據(jù)項的、時間戳為1, 2, 3, 4, 5的事務(wù)的一個部分調(diào)度的事務(wù)的一個部分調(diào)度silberschatz, korth and sudarshan16.54database system concepts 3rd editionn時間戳保證了可串行性，有絕對時間戳，等候圖不會有循環(huán)（時間戳保證了可串行性，有絕對時間戳，等候圖不會有循環(huán)（ 按按資歷分配資源）資歷分配資源） n

56、因此因此, 優(yōu)先圖中沒有圈優(yōu)先圖中沒有圈n時間戳協(xié)議確保沒有死鎖時間戳協(xié)議確保沒有死鎖, 因為沒有事務(wù)會等待因為沒有事務(wù)會等待n但是但是, 調(diào)度可能導致級聯(lián)回滾調(diào)度可能導致級聯(lián)回滾, 并且甚至可能不可恢復并且甚至可能不可恢復n先生沒有晉升成功，后生晉升后也要作廢先生沒有晉升成功，后生晉升后也要作廢較小時間戳事務(wù)較大時間戳事務(wù)silberschatz, korth and sudarshan16.55database system concepts 3rd editionn時間戳排序協(xié)議的問題時間戳排序協(xié)議的問題:假如假如ti 夭折，但夭折，但tj 已經(jīng)讀了已經(jīng)讀了ti 所寫的一個數(shù)據(jù)項所寫的一

57、個數(shù)據(jù)項則則tj 必須夭折，若必須夭折，若tj 已被允許較早提交，則該調(diào)度是不可恢已被允許較早提交，則該調(diào)度是不可恢復的復的進一步，任何讀了進一步，任何讀了tj 所寫的數(shù)據(jù)項的事務(wù)必須夭折所寫的數(shù)據(jù)項的事務(wù)必須夭折這可能導致級聯(lián)回滾：即一個回滾鏈這可能導致級聯(lián)回滾：即一個回滾鏈silberschatz, korth and sudarshan16.56database system concepts 3rd editionn解決方案解決方案:1.事務(wù)到最后才寫事務(wù)到最后才寫(at the end of its processing)2.所有寫動作作為一個原子（定先進和發(fā)獎金一起寫盤）所有寫動作

58、作為一個原子（定先進和發(fā)獎金一起寫盤）3.事務(wù)中止后重新開始，且重新給時間戳事務(wù)中止后重新開始，且重新給時間戳silberschatz, korth and sudarshan16.57database system concepts 3rd editionn是時間戳排序協(xié)議的修正版本，其中過時是時間戳排序協(xié)議的修正版本，其中過時write 操作在操作在某些情況下可以忽略某些情況下可以忽略n當當ti 試圖寫數(shù)據(jù)項試圖寫數(shù)據(jù)項q, 若若 ts(ti) w-timestamp(q), 則則ti 正試圖寫一個過時的正試圖寫一個過時的q值。因此，不是按時間戳排序值。因此，不是按時間戳排序協(xié)議要求的那樣

59、回滾協(xié)議要求的那樣回滾ti，這個，這個write 操作可以忽略（其操作可以忽略（其他情況下此協(xié)議與按時間戳排序協(xié)議相同）他情況下此協(xié)議與按時間戳排序協(xié)議相同）nthomas寫規(guī)則允許更多的潛在并發(fā)性，但不同于前面寫規(guī)則允許更多的潛在并發(fā)性，但不同于前面的協(xié)議，它允許做某些非沖突可串行化但是視圖可串的協(xié)議，它允許做某些非沖突可串行化但是視圖可串行化的調(diào)度（即最終結(jié)果等價于某個串行調(diào)度）行化的調(diào)度（即最終結(jié)果等價于某個串行調(diào)度）silberschatz, korth and sudarshan16.58database system concepts 3rd editionn思路思路:大膽先做，做

60、了再驗證，即不要坐而論道，遲遲大膽先做，做了再驗證，即不要坐而論道，遲遲不動不動n事務(wù)事務(wù)ti 的執(zhí)行分成三個階段的執(zhí)行分成三個階段: 1. 讀與執(zhí)行階段讀與執(zhí)行階段: 事務(wù)事務(wù)ti 的的write操作只寫到臨時局部變操作只寫到臨時局部變量量 2. 有效性檢查階段有效性檢查階段: 事務(wù)事務(wù)ti 執(zhí)行執(zhí)行“有效性檢查有效性檢查”來決定來決定局部變量的值是否可以寫到數(shù)據(jù)庫而不違反可串行化局部變量的值是否可以寫到數(shù)據(jù)庫而不違反可串行化 3. 寫階段寫階段: 若若ti 通過有效性檢查通過有效性檢查, 則更新數(shù)據(jù)庫則更新數(shù)據(jù)庫; 否則否則ti 回滾回滾silberschatz, korth and su