1、2022-5-26An Introduction to Database System數據庫系統概論數據庫系統概論An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制2022-5-26An Introduction to Database System問題的產生問題的產生v多用戶數據庫系統的存在 允許多個用戶同時使用的數據庫系統n飛機定票數據庫系統n銀行數據庫系統 特點：在同一時刻并發(fā)運行的事務數可達數百個 2022-5-26An Introduction to Database System問題的產生（續(xù)）問題的產生（續(xù)）v 不同的多事務執(zhí)行

2、方式 (1)事務串行執(zhí)行 每個時刻只有一個事務運行，其他事務必須等到這個事務結束以后方能運行 不能充分利用系統資源，發(fā)揮數據庫共享資源的特點T1T2T3事務的串行執(zhí)行方式2022-5-26An Introduction to Database System問題的產生（續(xù)）問題的產生（續(xù)）(2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機系統中，事務的并行執(zhí)行是這些并行事務的并行操作輪流交叉運行 單處理機系統中的并行事務并沒有真正地并行運行，但能夠減少處理機的空閑時間，提高系統的效率2022-5-26An Introduction to Database Syste

3、m問題的產生（續(xù)）問題的產生（續(xù)）事務的交叉并發(fā)執(zhí)行方式2022-5-26An Introduction to Database System問題的產生（續(xù)）問題的產生（續(xù)） (3)同時并發(fā)方式（simultaneous concurrency） 多處理機系統中，每個處理機可以運行一個事務，多個處理機可以同時運行多個事務，實現多個事務真正的并行運行2022-5-26An Introduction to Database System問題的產生（續(xù)）問題的產生（續(xù)）v事務并發(fā)執(zhí)行帶來的問題 會產生多個事務同時存取同一數據的情況 可能會存取和存儲不正確的數據，破壞事務一致性和數據庫的一致性2022

4、-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database System11.1 并發(fā)控制概述并發(fā)控制概述v并發(fā)控制機制的任務 對并發(fā)操作進行正確調度 保證事務的隔離性 保證數據庫的一致性2022-5-26An Introduction to Database Sys

5、temT1的修改被的修改被T2覆蓋了！覆蓋了！并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)）并發(fā)操作帶來數據的不一致性實例并發(fā)操作帶來數據的不一致性實例例1飛機訂票系統中的一個活動序列 甲售票點(甲事務)讀出某航班的機票余額A，設A=16； 乙售票點(乙事務)讀出同一航班的機票余額A，也為16； 甲售票點賣出一張機票，修改余額AA-1，所以A為15，把A寫回數據庫； 乙售票點也賣出一張機票，修改余額AA-1，所以A為15，把A寫回數據庫 n 結果明明賣出兩張機票，數據庫中機票余額只減少1 2022-5-26An Introduction to Database System并發(fā)控制概述（續(xù)）并發(fā)控制概述

6、（續(xù)）v 這種情況稱為數據庫的不一致性，是由并發(fā)操作引起的。v 在并發(fā)操作情況下，對甲、乙兩個事務的操作序列的調度是隨機的。v 若按上面的調度序列執(zhí)行，甲事務的修改就被丟失。 原因：第4步中乙事務修改A并寫回后覆蓋了甲事務的修改2022-5-26An Introduction to Database System并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)）v并發(fā)操作帶來的數據不一致性 丟失修改（Lost Update） 不可重復讀（Non-repeatable Read） 讀“臟”數據（Dirty Read）v記號 R(x):讀數據x W(x):寫數據x 2022-5-26An Introductio

7、n to Database System1. 丟失修改丟失修改v兩個事務T1和T2讀入同一數據并修改，T2的提交結果破壞了T1提交的結果，導致T1的修改被丟失。v上面飛機訂票例子就屬此類 2022-5-26An Introduction to Database System丟失修改（續(xù)）丟失修改（續(xù)）T1T2 R(A)=16R(A)=16 AA-1 W(A)=15AA-1W(A)=15丟失修改2022-5-26An Introduction to Database System2. 不可重復讀不可重復讀v不可重復讀是指事務T1讀取數據后，事務T2 執(zhí)行更新操作，使T1無法再現前一次讀取結果。2

8、022-5-26An Introduction to Database System不可重復讀（續(xù)）不可重復讀（續(xù)）v不可重復讀包括三種情況：(1)事務T1讀取某一數據后，事務T2對其做了修改，當事務T1再次讀該數據時，得到與前一次不同的值 2022-5-26An Introduction to Database System不可重復讀（續(xù)）不可重復讀（續(xù)）n T1讀取B=100進行運算n T2讀取同一數據B，對其進行修改后將B=200寫回數據庫。n T1為了對讀取值校對重讀B，B已為200，與第一次讀取值不一致 T1T2 R(A)=50 R(B)=100求和=150R(B)=100BB*2(

9、B)=200 R(A)=50R(B)=200和=250(驗算不對)不可重復讀 例如：2022-5-26An Introduction to Database System不可重復讀（續(xù)）不可重復讀（續(xù)）(2)事務T1按一定條件從數據庫中讀取了某些數據記錄后，事務T2刪除了其中部分記錄，當T1再次按相同條件讀取數據時，發(fā)現某些記錄消失了 (3)事務T1按一定條件從數據庫中讀取某些數據記錄后，事務T2插入了一些記錄，當T1再次按相同條件讀取數據時，發(fā)現多了一些記錄。 后兩種不可重復讀有時也稱為幻影現象（Phantom Row）2022-5-26An Introduction to Database

10、 System3. 讀讀“臟臟”數據數據 讀“臟”數據是指：n事務T1修改某一數據，并將其寫回磁盤n事務T2讀取同一數據后，T1由于某種原因被撤銷n這時T1已修改過的數據恢復原值，T2讀到的數據就與數據庫中的數據不一致nT2讀到的數據就為“臟”數據，即不正確的數據 2022-5-26An Introduction to Database System讀讀“臟臟”數據（續(xù)）數據（續(xù)）T1T2 R(C)=100 CC*2 W(C)=200R(C)=200ROLLBACK C恢復為100例如例如讀“臟”數據 n T1將C值修改為200，T2讀到C為200n T1由于某種原因撤銷，其修改作廢，C恢復原

11、值100n 這時T2讀到的C為200，與數據庫內容不一致，就是“臟”數據 2022-5-26An Introduction to Database System并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)）v數據不一致性：由于并發(fā)操作破壞了事務的隔離性v并發(fā)控制就是要用正確的方式調度并發(fā)操作，使一個用戶事務的執(zhí)行不受其他事務的干擾，從而避免造成數據的不一致性 2022-5-26An Introduction to Database System并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)）v并發(fā)控制的主要技術 有封鎖(Locking) 時間戳(Timestamp) 樂觀控制法v商用的DBMS一般都采用封鎖方法 2

12、022-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database System11.2 封鎖封鎖v什么是封鎖v基本封鎖類型v鎖的相容矩陣2022-5-26An Introduction to Database System什么是封鎖什么是封鎖v封鎖就是事務T在對某個數

13、據對象（例如表、記錄等）操作之前，先向系統發(fā)出請求，對其加鎖v加鎖后事務T就對該數據對象有了一定的控制，在事務T釋放它的鎖之前，其它的事務不能更新此數據對象。2022-5-26An Introduction to Database System基本封鎖類型基本封鎖類型v 一個事務對某個數據對象加鎖后究竟擁有什么樣的控制由封鎖的類型決定。v 基本封鎖類型 排它鎖（Exclusive Locks，簡記為X鎖） 共享鎖（Share Locks，簡記為S鎖）2022-5-26An Introduction to Database System排它鎖排它鎖v排它鎖又稱為寫鎖v若事務T對數據對象A加上X鎖

14、，則只允許T讀取和修改A，其它任何事務都不能再對A加任何類型的鎖，直到T釋放A上的鎖v保證其他事務在T釋放A上的鎖之前不能再讀取和修改A 2022-5-26An Introduction to Database System共享鎖共享鎖v共享鎖又稱為讀鎖v若事務T對數據對象A加上S鎖，則其它事務只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖v保證其他事務可以讀A，但在T釋放A上的S鎖之前不能對A做任何修改 2022-5-26An Introduction to Database System鎖的相容矩陣鎖的相容矩陣Y=Yes，相容的請求，相容的請求N=No，不相容的請求，不相容的請求 T

15、2 T1XS-XNNYSNYY-YYY2022-5-26An Introduction to Database System鎖的相容矩陣（續(xù)）鎖的相容矩陣（續(xù)）在鎖的相容矩陣中：v 最左邊一列表示事務T1已經獲得的數據對象上的鎖的類型，其中橫線表示沒有加鎖。v 最上面一行表示另一事務T2對同一數據對象發(fā)出的封鎖請求。v T2的封鎖請求能否被滿足用矩陣中的Y和N表示 Y表示事務T2的封鎖要求與T1已持有的鎖相容，封鎖請求可以滿足 N表示T2的封鎖請求與T1已持有的鎖沖突，T2的請求被拒絕2022-5-26An Introduction to Database System使用封鎖機制解決丟失修改

16、問題使用封鎖機制解決丟失修改問題T1T2 Xlock A R(A)=16Xlock A AA-1等待 W(A)=15等待 Commit等待 Unlock A等待獲得Xlock AR(A)=15AA-1W(A)=14CommitUnlock A例：例：n 事務T1在讀A進行修改之前先對A加X鎖n 當T2再請求對A加X鎖時被拒絕n T2只能等待T1釋放A上的鎖后T2獲得對A的X鎖n 這時T2讀到的A已經是T1更新過的值15n T2按此新的A值進行運算，并將結果值A=14送回到磁盤。避免了丟失T1的更新。沒有丟失修改沒有丟失修改2022-5-26An Introduction to Database

17、 System使用封鎖機制解決不可重復讀問題使用封鎖機制解決不可重復讀問題T1T2 Slock ASlock BR(A)=50R(B)=100求和=150Xlock B等待等待 R(A)=50等待R(B)=100等待求和=150等待Commit等待Unlock A等待Unlock B等待獲得XlockBR(B)=100BB*2W(B)=200CommitUnlock Bn 事務T1在讀A，B之前，先對A，B加S鎖n 其他事務只能再對A，B加S鎖，而不能加X鎖，即其他事務只能讀A，B，而不能修改n 當T2為修改B而申請對B的X鎖時被拒絕只能等待T1釋放B上的鎖n T1為驗算再讀A，B，這時讀出的

18、B仍是100，求和結果仍為150，即可重復讀n T1結束才釋放A，B上的S鎖。T2才獲得對B的X鎖 可重復讀可重復讀2022-5-26An Introduction to Database System使用封鎖機制解決讀使用封鎖機制解決讀“臟臟”數據問數據問題題T1T2 Xlock CR(C)=100CC*2W(C)=200Slock C等待 ROLLBACK等待(C恢復為100)等待Unlock C等待獲得Slock CR(C)=100Commit CUnlock C例例n 事務T1在對C進行修改之前，先對C加X鎖，修改其值后寫回磁盤n T2請求在C上加S鎖，因T1已在C上加了X鎖，T2只能

19、等待n T1因某種原因被撤銷，C恢復為原值100n T1釋放C上的X鎖后T2獲得C上的S鎖，讀C=100。避免了T2讀“臟”數據不讀不讀“臟臟”數據數據 2022-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database System11.3 活鎖和死鎖活鎖和死鎖v封

20、鎖技術可以有效地解決并行操作的一致性問題，但也帶來一些新的問題 死鎖 活鎖2022-5-26An Introduction to Database System11.3.1 活鎖活鎖v 事務T1封鎖了數據Rv 事務T2又請求封鎖R，于是T2等待。v T3也請求封鎖R，當T1釋放了R上的封鎖之后系統首先批準了T3的請求，T2仍然等待。v T4又請求封鎖R，當T3釋放了R上的封鎖之后系統又批準了T4的請求v T2有可能永遠等待，這就是活鎖的情形 2022-5-26An Introduction to Database System活鎖（續(xù)）活鎖（續(xù)）活活 鎖鎖2022-5-26An Introdu

21、ction to Database System活鎖（續(xù)）活鎖（續(xù)）v避免活鎖：采用先來先服務的策略 當多個事務請求封鎖同一數據對象時 按請求封鎖的先后次序對這些事務排隊 該數據對象上的鎖一旦釋放，首先批準申請隊列中第一個事務獲得鎖2022-5-26An Introduction to Database System11.3.2 死鎖死鎖v 事務T1封鎖了數據R1v T2封鎖了數據R2v T1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖v 接著T2又申請封鎖R1，因T1已封鎖了R1，T2也只能等待T1釋放R1上的鎖v 這樣T1在等待T2，而T2又在等待T1，T1和T2兩個

22、事務永遠不能結束，形成死鎖 2022-5-26An Introduction to Database System死鎖（續(xù)）死鎖（續(xù)）T1T2lock R1Lock R2Lock R2.等待等待Lock R1等待等待等待等待死 鎖2022-5-26An Introduction to Database System解決死鎖的方法解決死鎖的方法兩類方法1. 預防死鎖2. 死鎖的診斷與解除2022-5-26An Introduction to Database System1. 死鎖的預防死鎖的預防v 產生死鎖的原因是兩個或多個事務都已封鎖了一些數據對象，然后又都請求對已為其他事務封鎖的數據對象加

23、鎖，從而出現死等待。v 預防死鎖的發(fā)生就是要破壞產生死鎖的條件2022-5-26An Introduction to Database System死鎖的預防（續(xù)）死鎖的預防（續(xù)）預防死鎖的方法v 一次封鎖法v 順序封鎖法2022-5-26An Introduction to Database System(1)一次封鎖法一次封鎖法v要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續(xù)執(zhí)行v存在的問題 降低系統并發(fā)度 難于事先精確確定封鎖對象2022-5-26An Introduction to Database System(2)順序封鎖法順序封鎖法v 順序封鎖法是預先對數據對象規(guī)

24、定一個封鎖順序，所有事務都按這個順序實行封鎖。v 順序封鎖法存在的問題 維護成本 數據庫系統中封鎖的數據對象極多，并且在不斷地變化。 難以實現：很難事先確定每一個事務要封鎖哪些對象 2022-5-26An Introduction to Database System死鎖的預防（續(xù)）死鎖的預防（續(xù)）v結論 在操作系統中廣為采用的預防死鎖的策略并不很適合數據庫的特點 DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法2022-5-26An Introduction to Database System2. 死鎖的診斷與解除死鎖的診斷與解除v死鎖的診斷n超時法n事務等待圖法 2022-5

25、-26An Introduction to Database System(1) 超時法超時法v 如果一個事務的等待時間超過了規(guī)定的時限，就認為發(fā)生了死鎖v 優(yōu)點：實現簡單v 缺點 有可能誤判死鎖 時限若設置得太長，死鎖發(fā)生后不能及時發(fā)現2022-5-26An Introduction to Database System(2)等待圖法等待圖法v 用事務等待圖動態(tài)反映所有事務的等待情況 事務等待圖是一個有向圖G=(T，U) T為結點的集合，每個結點表示正運行的事務 U為邊的集合，每條邊表示事務等待的情況 若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T22022-5-26An Int

26、roduction to Database System等待圖法（續(xù)）等待圖法（續(xù)） 事務等待圖n 圖(a)中，事務T1等待T2，T2等待T1，產生了死鎖n 圖(b)中，事務T1等待T2，T2等待T3，T3等待T4，T4又等待T1，產生了死鎖 n 圖(b)中，事務T3可能還等待T2，在大回路中又有小的回路 2022-5-26An Introduction to Database System等待圖法（續(xù)）等待圖法（續(xù)）v并發(fā)控制子系統周期性地（比如每隔數秒）生成事務等待圖，檢測事務。如果發(fā)現圖中存在回路，則表示系統中出現了死鎖。2022-5-26An Introduction to Datab

27、ase System死鎖的診斷與解除（續(xù)）死鎖的診斷與解除（續(xù)）v解除死鎖 選擇一個處理死鎖代價最小的事務，將其撤消 釋放此事務持有的所有的鎖，使其它事務能繼續(xù)運行下去2022-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database System11.4 并發(fā)調度的

28、可串行性并發(fā)調度的可串行性vDBMS對并發(fā)事務不同的調度可能會產生不同的結果v什么樣的調度是正確的？2022-5-26An Introduction to Database System11.4.1 可串行化調度可串行化調度v可串行化(Serializable)調度n多個事務的并發(fā)執(zhí)行是正確的，當且僅當其結果與按某一次序串行地執(zhí)行這些事務時的結果相同v可串行性(Serializability) 是并發(fā)事務正確調度的準則 一個給定的并發(fā)調度，當且僅當它是可串行化的，才認為是正確調度 2022-5-26An Introduction to Database System可串行化調度（續(xù)）可串行化調

29、度（續(xù)）例現在有兩個事務，分別包含下列操作： 事務T1：讀B；A=B+1；寫回A 事務T2：讀A；B=A+1；寫回B現給出對這兩個事務不同的調度策略 2022-5-26An Introduction to Database System串行化調度串行化調度,正確的調度正確的調度T1T2Slock BY=R(B)=2Unlock BXlock AA=Y+1=3W(A)Unlock ASlock AX=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B串行調度(a)n 假設A、B的初值均為2。n 按T1T2次序執(zhí)行結果為A=3，B=4 n 串行調度策略,正確的調度 2

30、022-5-26An Introduction to Database System串行化調度串行化調度,正確的調度正確的調度T1T2Slock AX=R(A)=2Unlock AXlock BB=X+1=3W(B)Unlock BSlock BY=R(B)=3Unlock BXlock AA=Y+1=4W(A)Unlock A串行調度(b)n 假設A、B的初值均為2。n T2T1次序執(zhí)行結果為B=3，A=4 n 串行調度策略,正確的調度 2022-5-26An Introduction to Database System不可串行化調度，錯誤的調度不可串行化調度，錯誤的調度T1T2Slock

31、 BY=R(B)=2Slock AX=R(A)=2Unlock BUnlock AXlock AA=Y+1=3W(A)Xlock BB=X+1=3W(B)Unlock AUnlock B不可串行化的調度 n 執(zhí)行結果與(a)、(b)的結果都不同n 是錯誤的調度 2022-5-26An Introduction to Database System可串行化調度，正確的調度可串行化調度，正確的調度T1T2Slock BY=R(B)=2Unlock BXlock ASlock AA=Y+1=3等待W(A)等待Unlock A等待X=R(A)=3Unlock AXlock BB=X+1=4W(B)Un

32、lock B可串行化的調度 n 執(zhí)行結果與串行調度(a)的執(zhí)行結果相同n 是正確的調度 2022-5-26An Introduction to Database System11.4.2 沖突可串行化調度沖突可串行化調度v具有什么樣性質的調度是可串行化調度？v如何判斷調度是可串行化調度？ 本節(jié)給出判斷可串行化調度的本節(jié)給出判斷可串行化調度的必要條件。必要條件。2022-5-26An Introduction to Database System沖突可串行化調度（續(xù)）沖突可串行化調度（續(xù)）沖突操作沖突操作v 沖突操作是指不同的事務對同一個數據的讀寫操作和寫寫操作 Ri (x)與Wj(x) /*

33、事務Ti讀x，Tj寫x*/ Wi(x)與Wj(x) /* 事務Ti寫x，Tj寫x*/v 其他操作是不沖突操作v 不同事務的沖突操作和同一事務的兩個操作不能交換(Swap) 2022-5-26An Introduction to Database System11.4.2 沖突可串行化調度沖突可串行化調度v可串行化調度的充分條件充分條件 一個調度Sc在保證沖突操作沖突操作的次序不變的情況下，通過交換兩個事務不沖突操作的次序得到另一個調度Sc，如果Sc是串行的，稱調度Sc為沖突可串行化的調度 一個調度是沖突可串行化，一定是可串行化的調度2022-5-26An Introduction to Dat

34、abase System沖突可串行化調度（續(xù)）沖突可串行化調度（續(xù)）例今有調度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等價于一個串行調度T1，T2，Sc1沖突可串行化的調度2022-5-26An Introduction to Database System沖突可串行化調度（續(xù)）沖

35、突可串行化調度（續(xù)）v 沖突可串行化調度是可串行化調度的充分條件，不是必要條件。還有不滿足沖突可串行化條件的可串行化調度。 例有3個事務 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)不滿足沖突可串行化。但是調度L2是可串行化的，因為L2執(zhí)行的結果與調度L1相同，Y的值都等于T2的值，X的值都等于T3的值 2022-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11

36、.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database System11.5 兩段鎖協議兩段鎖協議v 封鎖協議 運用封鎖方法時，對數據對象加鎖時需要約定一些規(guī)則 何時申請封鎖 持鎖時間 何時釋放封鎖等v 兩段封鎖協議(Two-Phase Locking，簡稱2PL)是最常用的一種封鎖協議，理論上證明使用兩段封鎖協議產生的是可串行化調度2022-5-26An Introducti

37、on to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）v兩段鎖協議 指所有事務必須分兩個階段對數據項加鎖和解鎖 n在對任何數據進行讀、寫操作之前，事務首先要獲得對該數據的封鎖n 在釋放一個封鎖之后，事務不再申請和獲得任何其他封鎖2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）v “兩段”鎖的含義事務分為兩個階段 第一階段是獲得封鎖，也稱為擴展階段 事務可以申請獲得任何數據項上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務可以釋放任何數據項上的任何類型的鎖，但是不能再申請任何鎖

38、 2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）例事務Ti遵守兩段鎖協議，其封鎖序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock C；|擴展階段| 收縮階段 |事務Tj不遵守兩段鎖協議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B；2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）事務T1事務T2Slock(A)R(A=260)

39、Slock(C)R(C=300)Xlock(A)W(A=160)Xlock( C )W(C=250)Slock(A)Slock(B)等待R(B=1000)等待Xlock(B)等待W(B=1100) 等待Unlock(A)等待R(A=160)Xlock(A)Unlock(B)W(A=210)Unlock( C )遵守兩段鎖協議的可串行化調度n 左圖的調度是遵守兩段鎖協議的，因此一定是一個可串行化調度。2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）v 事務遵守兩段鎖協議是可串行化調度的充分條件，而不是必要條件。v 若并發(fā)事務都

40、遵守兩段鎖協議，則對這些事務的任何并發(fā)調度策略都是可串行化的v 若并發(fā)事務的一個調度是可串行化的，不一定所有事務都符合兩段鎖協議 2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協議（續(xù)）v兩段鎖協議與防止死鎖的一次封鎖法 一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協議 但是兩段鎖協議并不要求事務必須一次將所有要使用的數據全部加鎖，因此遵守兩段鎖協議的事務可能發(fā)生死鎖2022-5-26An Introduction to Database System兩段鎖協議（續(xù)）兩段鎖協

41、議（續(xù)）例 遵守兩段鎖協議的事務發(fā)生死鎖T1Slock BR(B)=2 Xlock A等待等待等待等待T2 Slock AR(A)=2 Xlock A等待等待遵守兩段鎖協議的事務可能發(fā)生死鎖 2022-5-26An Introduction to Database System第十一章第十一章 并發(fā)控制并發(fā)控制11.1 并發(fā)控制概述并發(fā)控制概述11.2 封鎖封鎖11.3 活鎖和死鎖活鎖和死鎖11.4 并發(fā)調度的可串行性并發(fā)調度的可串行性11.5 兩段鎖協議兩段鎖協議11.6 封鎖的粒度封鎖的粒度11.7 小結小結2022-5-26An Introduction to Database Syst

42、em封鎖粒度封鎖粒度v 封鎖對象的大小稱為封鎖粒度(Granularity) v 封鎖的對象：邏輯單元，物理單元 例：在關系數據庫中，封鎖對象： 邏輯單元: 屬性值、屬性值集合、元組、關系、索引項、整個索引、整個數據庫等 物理單元：頁（數據頁或索引頁）、物理記錄等2022-5-26An Introduction to Database System選擇封鎖粒度原則選擇封鎖粒度原則v封鎖粒度與系統的并發(fā)度和并發(fā)控制的開銷密切相關。 封鎖的粒度越大，數據庫所能夠封鎖的數據單元就越少，并發(fā)度就越小，系統開銷也越小； 封鎖的粒度越小，并發(fā)度較高，但系統開銷也就越大2022-5-26An Introdu

43、ction to Database System選擇封鎖粒度的原則（續(xù)）選擇封鎖粒度的原則（續(xù)）例v 若封鎖粒度是數據頁，事務T1需要修改元組L1，則T1必須對包含L1的整個數據頁A加鎖。如果T1對A加鎖后事務T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。v 如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖，不需要互相等待，提高了系統的并行度。v 又如，事務T需要讀取整個表，若封鎖粒度是元組，T必須對表中的每一個元組加鎖，開銷極大 2022-5-26An Introduction to Database System選擇封鎖粒度的原則（續(xù)）選擇封鎖粒度的原則（續(xù)）v 多粒度封

44、鎖(Multiple Granularity Locking) 在一個系統中同時支持多種封鎖粒度供不同的事務選擇v 選擇封鎖粒度 同時考慮封鎖開銷和并發(fā)度兩個因素，適當選擇封鎖粒度 需要處理多個關系的大量元組的用戶事務：以數據庫為封鎖單位 需要處理大量元組的用戶事務：以關系為封鎖單元 只處理少量元組的用戶事務：以元組為封鎖單位2022-5-26An Introduction to Database System11.6.1 多粒度封鎖多粒度封鎖v多粒度樹 以樹形結構來表示多級封鎖粒度 根結點是整個數據庫，表示最大的數據粒度 葉結點表示最小的數據粒度 2022-5-26An Introducti

45、on to Database System多粒度封鎖（續(xù)）多粒度封鎖（續(xù)）例：三級粒度樹。根結點為數據庫，數據庫的子結點為關系，關系的子結點為元組。數據庫數據庫關系關系Rn關系關系R1元組元組元組元組元組元組元組元組 三級粒度樹三級粒度樹2022-5-26An Introduction to Database System多粒度封鎖協議多粒度封鎖協議v允許多粒度樹中的每個結點被獨立地加鎖v對一個結點加鎖意味著這個結點的所有后裔結點也被加以同樣類型的鎖v在多粒度封鎖中一個數據對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖2022-5-26An Introduction to Database Sys

46、tem顯式封鎖和隱式封鎖顯式封鎖和隱式封鎖v顯式封鎖: 直接加到數據對象上的封鎖v隱式封鎖: 該數據對象沒有獨立加鎖，是由于其上級結點加鎖而使該數據對象加上了鎖v顯式封鎖和隱式封鎖的效果是一樣的2022-5-26An Introduction to Database System顯式封鎖和隱式封鎖（續(xù)）顯式封鎖和隱式封鎖（續(xù)）v 系統檢查封鎖沖突時n 要檢查顯式封鎖n 還要檢查隱式封鎖v 例如事務T要對關系R1加X鎖 系統必須搜索其上級結點數據庫、關系R1 還要搜索R1的下級結點，即R1中的每一個元組 如果其中某一個數據對象已經加了不相容鎖，則T必須等待 2022-5-26An Introdu

47、ction to Database System顯式封鎖和隱式封鎖（續(xù)）顯式封鎖和隱式封鎖（續(xù)）v 對某個數據對象加鎖，系統要檢查 該數據對象有無顯式封鎖與之沖突 所有上級結點檢查本事務的顯式封鎖是否與該數據對象上的隱式封鎖沖突：(由上級結點已加的封鎖造成的） 所有下級結點看上面的顯式封鎖是否與本事務的隱式封鎖（將加到下級結點的封鎖）沖突2022-5-26An Introduction to Database System11.6.2 意向鎖意向鎖v引進意向鎖（intention lock）目的 提高對某個數據對象加鎖時系統的檢查效率2022-5-26An Introduction to Database System意向鎖意向鎖(續(xù)續(xù))v 如果對一個結點加意向鎖，則說明該結點的下層結點正在被加鎖v 對任一結點加基本鎖，必須先對它的上層結點加意向鎖v 例如，對任一元組加鎖時，必須先對它所在的數據庫和關系加意向鎖 2022-5-26An Introduction to Database System常用意向鎖常用意向鎖v意向共享鎖(Intent Share Lock，簡稱IS鎖)v意向排它鎖(Intent Exclusive Lock，簡稱IX鎖)v共享意向排它鎖(Share Intent Exclusive Lock，簡稱SIX鎖)2022