并发控制课件

併發控制

併發控制概述多事務執行方式(1)事務串行執行每個時刻只有一個事務運行，其他事務必須等到這個事務結束以後方能運行不能充分利用系統資源，發揮資料庫共用資源的特點併發控制（續）(2)交叉併發方式（interleavedconcurrency）事務的並行執行是這些並行事務的並行操作輪流交叉運行是單處理機系統中的併發方式，能夠減少處理機的空閒時間，提高系統的效率併發控制（續）(3)同時併發方式（simultaneousconcurrency）多處理機系統中，每個處理機可以運行一個事務，多個處理機可以同時運行多個事務，實現多個事務真正的並行運行最理想的併發方式，但受制於硬體環境更複雜的併發方式機制事務併發執行帶來的問題可能會存取和存儲不正確的數據，破壞事務的隔離性和數據庫的一致性DBMS必須提供併發控制機制併發控制機制是衡量一個DBMS性能的重要標誌之一8.1併發控制概述併發控制機制的任務對併發操作進行正確調度保證事務的隔離性保證資料庫的一致性T1的修改被T2覆蓋了！

讀A=16

A←A-3寫回A=13①讀A=16

②

③A←A-1

寫回A=15

④事務T2事務T1數據不一致實例：飛機訂票系統併發操作帶來的數據不一致性丟失修改（lostupdate）不可重複讀（non-repeatableread）讀“髒”數據（dirtyread）1.丟失修改丟失修改是指事務1與事務2從資料庫中讀入同一數據並修改事務2的提交結果破壞了事務1提交的結果，導致事務1的修改被丟失。2.不可重複讀不可重複讀是指事務1讀取數據後，事務2執行更新操作，使事務1無法再現前一次讀取結果。三類不可重複讀事務1讀取某一數據後：1。事務2對其做了修改，當事務1再次讀該數據時，得到與前一次不同的值。2.事務2刪除了其中部分記錄，當事務1再次讀取數據時，發現某些記錄神密地消失了。3.事務2插入了一些記錄，當事務1再次按相同條件讀取數據時，發現多了一些記錄。後兩種不可重複讀有時也稱為幻影現象（phantomrow）3.讀“髒”數據事務1修改某一數據，並將其寫回磁片事務2讀取同一數據後事務1由於某種原因被撤銷，這時事務1已修改過的數據恢復原值事務2讀到的數據就與資料庫中的數據不一致，是不正確的數據，又稱為“髒”數據。圖8.1三種數據不一致性T1T2①讀A=16

②

③A←A-1

寫回A=15

④

讀A=16

A←A-1寫回A=15(a)丟失修改圖8.1三種數據不一致性(續)

讀B=100B←B*2寫回B=200

①讀A=50

讀B=100

求和=150②

③讀A=50

讀B=200

求和=250(驗算不對)T2T1(b)不可重複讀圖8.1三種數據不一致性(續)

讀C=200

①讀C=100C←C*2

寫回C②

③ROLLBACKC恢復為100T2T1(c)讀“髒”數據第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.2封鎖一、什麼是封鎖二、基本封鎖類型三、基本鎖的相容矩陣一、什麼是封鎖封鎖就是事務T在對某個數據對象（例如表、記錄等）操作之前，先向系統發出請求，對其加鎖加鎖後事務T就對該數據對象有了一定的控制，在事務T釋放它的鎖之前，其他的事務不能更新此數據對象。封鎖是實現併發控制的一個非常重要的技術8.2封鎖一、什麼是封鎖二、基本封鎖類型三、基本鎖的相容矩陣二、基本封鎖類型DBMS通常提供了多種類型的封鎖。一個事務對某個數據對象加鎖後究竟擁有什麼樣的控制是由封鎖的類型決定的。基本封鎖類型排它鎖（eXclusivelock，簡記為X鎖）共用鎖（Sharelock，簡記為S鎖）

排它鎖

排它鎖又稱為寫鎖若事務T對數據對象A加上X鎖，則只允許T讀取和修改A，其他任何事務都不能再對A加任何類型的鎖，直到T釋放A上的鎖共用鎖共用鎖又稱為讀鎖若事務T對數據對象A加上S鎖，則其他事務只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖8.2封鎖一、什麼是封鎖二、基本封鎖類型三、基本鎖的相容矩陣三、鎖的相容矩陣Y=Yes，相容的請求N=No，不相容的請求

T1T2XS-XNNYSNYY-YYY第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.3封鎖協議在運用X鎖和S鎖對數據對象加鎖時，需要約定一些規則：封鎖協議（LockingProtocol）何時申請X鎖或S鎖持鎖時間、何時釋放不同的封鎖協議，在不同的程度上為併發操作的正確調度提供一定的保證常用的封鎖協議：三級封鎖協議1級封鎖協議事務T在修改數據R之前必須先對其加X鎖，直到事務結束才釋放正常結束（COMMIT）非正常結束（ROLLBACK）1級封鎖協議可防止丟失修改在1級封鎖協議中，如果是讀數據，不需要加鎖的，所以它不能保證可重複讀和不讀“髒”數據。1級封鎖協議T1T2①

XlockA

獲得②

讀A=16

③A←A-1

寫回A=15CommitUnlockA④

⑤

XlockA等待等待等待等待獲得XlockA讀A=15A←A-1寫回A=14CommitUnlockA

沒有丟失修改1級封鎖協議

讀A=15①

XlockA

獲得②

讀A=16

A←A-1

寫回A=15③

④RollbackUnlockA

T2T1讀“髒”數據1級封鎖協議

XlockB

獲得

讀B=100B←B*2

寫回B=200CommitUnlockB①讀A=50

讀B=100

求和=150②③讀A=50

讀B=200

求和=250(驗算不對)T2T1不可重複讀

2級封鎖協議1級封鎖協議+事務T在讀取數據R前必須先加S鎖，讀完後即可釋放S鎖2級封鎖協議可以防止丟失修改和讀“髒”數據。在2級封鎖協議中，由於讀完數據後即可釋放S鎖，所以它不能保證可重複讀。2級封鎖協議不可重複讀①

SclockA

獲得讀A=50UnlockA②SclockB

獲得讀B=100UnlockB③求和=150

XlockB等待等待獲得XlockB讀B=100B←B*2寫回B=200CommitUnlockBT2T1④SclockA

獲得讀A=50UnlockA

SclockB

獲得讀B=200UnlockB

求和=250(驗算不對)

T2T1(續)

3級封鎖協議1級封鎖協議+事務T在讀取數據R之前必須先對其加S鎖，直到事務結束才釋放3級封鎖協議可防止丟失修改、讀髒數據和不可重複讀。3級封鎖協議T1T2①

SlockA

讀A=50

SlockB

讀B=100

求和=150②

③讀A=50

讀B=100

求和=150CommitUnlockAUnlockB④

⑤

XlockB等待等待等待等待等待等待等待等待獲得XlockB讀B=100B←B*2寫回B=200CommitUnlockB

可重複讀3級封鎖協議T1T2①

XlockC

讀C=100C←C*2

寫回C=200②

③ROLLBACK(C恢復為100)UnlockC④

⑤

SlockC等待等待等待等待獲得SlockC讀C=100CommitCUnlockC不讀“髒”數據4．封鎖協議小結三級協議的主要區別什麼操作需要申請封鎖何時釋放鎖（即持鎖時間）封鎖協議小結(續)第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.4活鎖和死鎖封鎖技術可以有效地解決並行操作的一致性問題，但也帶來一些新的問題死鎖活鎖8.4.1活鎖如何避免活鎖採用先來先服務的策略：當多個事務請求封鎖同一數據對象時按請求封鎖的先後次序對這些事務排隊該數據對象上的鎖一旦釋放，首先批准申請佇列中第一個事務獲得鎖。8.4.2死鎖

T1T2

XlockR1...XlockR2等待等待等待...XlockR2..Xlock

R1等待等待.

解決死鎖的方法

兩類方法1.預防死鎖2.死鎖的診斷與解除1.死鎖的預防產生死鎖的原因是兩個或多個事務都已封鎖了一些數據對象，然後又都請求對已為其他事務封鎖的數據對象加鎖，從而出現死等待。預防死鎖的發生就是要破壞產生死鎖的條件死鎖的預防（續）預防死鎖的方法一次封鎖法順序封鎖法（1）一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續執行一次封鎖法存在的問題：降低併發度擴大封鎖範圍將以後要用到的全部數據加鎖，勢必擴大了封鎖的範圍，從而降低了系統的併發度一次封鎖法（續）難於事先精確確定封鎖對象資料庫中數據是不斷變化的，原來不要求封鎖的數據，在執行過程中可能會變成封鎖對象，所以很難事先精確地確定每個事務所要封鎖的數據對象解決方法：將事務在執行過程中可能要封鎖的數據對象全部加鎖，這就進一步降低了併發度。（2）順序封鎖法順序封鎖法是預先對數據對象規定一個封鎖順序，所有事務都按這個順序實行封鎖。順序封鎖法存在的問題維護成本高資料庫系統中可封鎖的數據對象極其眾多，並且隨數據的插入、刪除等操作而不斷地變化，要維護這樣極多而且變化的資源的封鎖順序非常困難，成本很高順序封鎖法（續）難於實現事務的封鎖請求可以隨著事務的執行而動態地決定，很難事先確定每一個事務要封鎖哪些對象，因此也就很難按規定的順序去施加封鎖。例：規定數據對象的封鎖順序為A,B,C,D,E。事務T3起初要求封鎖數據對象B,C,E，但當它封鎖了B,C後，才發現還需要封鎖A，這樣就破壞了封鎖順序.死鎖的預防（續）結論在操作系統中廣為採用的預防死鎖的策略並不很適合資料庫的特點DBMS在解決死鎖的問題上更普遍採用的是診斷並解除死鎖的方法2.死鎖的診斷與解除允許死鎖發生解除死鎖由DBMS的併發控制子系統定期檢測系統中是否存在死鎖一旦檢測到死鎖，就要設法解除檢測死鎖：超時法如果一個事務的等待時間超過了規定的時限，就認為發生了死鎖優點：實現簡單缺點有可能誤判死鎖時限若設置得太長，死鎖發生後不能及時發現等待圖法用事務等待圖動態反映所有事務的等待情況事務等待圖是一個有向圖G=(T，U)T為結點的集合，每個結點表示正運行的事務U為邊的集合，每條邊表示事務等待的情況若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2併發控制子系統週期性地（比如每隔1min）檢測事務等待圖，如果發現圖中存在回路，則表示系統中出現了死鎖。死鎖的診斷與解除（續）解除死鎖選擇一個處理死鎖代價最小的事務，將其撤銷，釋放此事務持有的所有的鎖，使其他事務能繼續運行下去。第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.5併發調度的可串行性一、什麼樣的併發操作調度是正確的二、如何保證併發操作的調度是正確的8.5併發調度的可串行性一、什麼樣的併發操作調度是正確的二、如何保證併發操作的調度是正確的一、什麼樣的併發操作調度是正確的電腦系統對並行事務中並行操作的調度是的隨機的，而不同的調度可能會產生不同的結果。將所有事務串行起來的調度策略一定是正確的調度策略。如果一個事務運行過程中沒有其他事務在同時運行，也就是說它沒有受到其他事務的干擾，那麼就可以認為該事務的運行結果是正常的或者預想的什麼樣的併發操作調度是正確的（續）以不同的順序串行執行事務也有可能會產生不同的結果，但由於不會將資料庫置於不一致狀態，所以都可以認為是正確的。幾個事務的並行執行是正確的，當且僅當其結果與按某一次序串行地執行它們時的結果相同。這種並行調度策略稱為可串行化（Serializable）的調度。什麼樣的併發操作調度是正確的（續）可串行性是並行事務正確性的唯一準則例：現在有兩個事務，分別包含下列操作：事務1：讀B；A=B+1；寫回A；

事務2：讀A；B=A+1；寫回B；

假設A的初值為2，B的初值為2。什麼樣的併發操作調度是正確的（續）對這兩個事務的不同調度策略串行執行串行調度策略1串行調度策略2交錯執行不可串行化的調度可串行化的調度(a)串行調度策略，正確的調度SlockBY=B=2UnlockBXlockAA=Y+1寫回A(=3)UnlockA

SlockAX=A=3UnlockAXlockBB=X+1寫回B(=4)UnlockB

T1T2(b)串行調度策略，正確的調度

SlockBY=B=3UnlockBXlockAA=Y+1寫回A(=4)UnlockA

SlockA

X=A=2UnlockAXlockBB=X+1寫回B(=3)UnlockB

T1T2(c)不可串行化的調度SlockBY=B=2

UnlockB

XlockAA=Y+1寫回A(=3)

UnlockA

SlockAX=A=2

UnlockA

XlockBB=X+1寫回B(=3)

UnlockBT1T2(c)不可串行化的調度(續)由於其執行結果與(a)、(b)的結果都不同，所以是錯誤的調度。(d)可串行化的調度SlockBY=B=2UnlockBXlockA

A=Y+1寫回A(=3)UnlockA

SlockA

等待等待等待X=A=3UnlockAXlockBB=X+1寫回B(=4)UnlockBT1T2(d)可串行化的調度（續）由於其執行結果與串行調度（a）的執行結果相同，所以是正確的調度。8.5併發調度的可串行性一、什麼樣的併發操作調度是正確的二、如何保證併發操作的調度是正確的二、如何保證併發操作的調度是正確的為了保證並行操作的正確性，DBMS的並行控制機制必須提供一定的手段來保證調度是可串行化的。從理論上講，在某一事務執行時禁止其他事務執行的調度策略一定是可串行化的調度，這也是最簡單的調度策略，但這種方法實際上是不可行的，因為它使用戶不能充分共用資料庫資源。如何保證併發操作的調度是正確的（續）保證併發操作調度正確性的方法封鎖方法：兩段鎖（Two-PhaseLocking，簡稱2PL）協議時標方法樂觀方法第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.6兩段鎖協議兩段鎖協議的內容1.在對任何數據進行讀、寫操作之前，事務首先要獲得對該數據的封鎖2.在釋放一個封鎖之後，事務不再獲得任何其他封鎖。兩段鎖協議（續）“兩段”鎖的含義事務分為兩個階段

第一階段是獲得封鎖，也稱為擴展階段；第二階段是釋放封鎖，也稱為收縮階段。兩段鎖協議（續）例：事務1的封鎖序列：SlockA...SlockB...XlockC...UnlockB...UnlockA...UnlockC；事務2的封鎖序列：SlockA...UnlockA...SlockB...XlockC...UnlockC...UnlockB；事務1遵守兩段鎖協議，而事務2不遵守兩段協議。兩段鎖協議（續）並行執行的所有事務均遵守兩段鎖協議，則對這些事務的所有並行調度策略都是可串行化的。

所有遵守兩段鎖協議的事務，其並行執行的結果一定是正確的事務遵守兩段鎖協議是可串行化調度的充分條件，而不是必要條件可串行化的調度中，不一定所有事務都必須符合兩段鎖協議。兩段鎖協議（續）T1SlockB讀B=2Y=BXlockA

A=Y+1寫回A=3UnlockBUnlockA

T2

SlockA

等待等待等待等待等待SlockA讀A=3Y=AXlockBB=Y+1寫回B=4UnlockBUnlockA

T1SlockB讀B=2Y=BUnlockBXlockA

A=Y+1寫回A=3UnlockA

T2

SlockA等待等待等待等待SlockA讀A=3X=AUnlockAXlockBB=X+1寫回B=4UnlockB

(a)遵守兩段鎖協議

(b)不遵守兩段鎖協議T1SlockB讀B=2Y=BUnlockBXlockAA=Y+1寫回A=3UnlockAT2

SlockA讀A=2X=AUnlockAXlockB等待XlockBB=X+1寫回B=3UnlockB

(c)不遵守兩段鎖協議兩段鎖協議（續）兩段鎖協議與防止死鎖的一次封鎖法一次封鎖法要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續執行，因此一次封鎖法遵守兩段鎖協議但是兩段鎖協議並不要求事務必須一次將所有要使用的數據全部加鎖，因此遵守兩段鎖協議的事務可能發生死鎖兩段鎖協議（續）圖8.7遵守兩段鎖協議的事務發生死鎖T1SlockB讀B=2

XlockA等待等待T2

SlockA讀A=2

XlockA等待兩段鎖協議（續）兩段鎖協議與三級封鎖協議兩類不同目的的協議兩段鎖協議保證併發調度的正確性三級封鎖協議在不同程度上保證數據一致性遵守第三級封鎖協議必然遵守兩段協議第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.7封鎖的粒度8.7.1封鎖粒度8.7.2多粒度封鎖8.7.3意向鎖8.7.1封鎖粒度一、什麼是封鎖粒度二、選擇封鎖粒度的原則一、什麼是封鎖粒度X鎖和S鎖都是加在某一個數據對象上的封鎖的對象:邏輯單元，物理單元例：在關係資料庫中，封鎖對象：邏輯單元:屬性值、屬性值集合、元組、關係、索引項、整個索引、整個資料庫等物理單元：頁（數據頁或索引頁）、物理記錄等什麼是封鎖粒度（續）封鎖對象可以很大也可以很小例：對整個資料庫加鎖對某個屬性值加鎖封鎖對象的大小稱為封鎖的粒度(Granularity)多粒度封鎖(multiplegranularitylocking)在一個系統中同時支持多種封鎖粒度供不同的事務選擇8.7.1封鎖粒度一、什麼是封鎖粒度二、選擇封鎖粒度的原則二、選擇封鎖粒度的原則封鎖的粒度越大，小，系統被封鎖的對象少，多，併發度小，高，系統開銷小，大，選擇封鎖粒度：考慮封鎖機構和併發度兩個因素對系統開銷與併發度進行權衡選擇封鎖粒度的原則（續）需要處理多個關係的大量元組的用戶事務：以資料庫為封鎖單位；需要處理大量元組的用戶事務：以關係為封鎖單元；只處理少量元組的用戶事務：以元組為封鎖單位8.7封鎖的粒度8.7.1封鎖粒度8.7.2多粒度封鎖8.7.3意向鎖8.7.2多粒度封鎖多粒度樹以樹形結構來表示多級封鎖粒度根結點是整個資料庫，表示最大的數據粒度葉結點表示最小的數據粒度

多粒度封鎖（續）例：三級粒度樹。根結點為數據庫，資料庫的子結點為關係，關係的子結點為元組。資料庫關係Rn關係R1元組元組元組元組………………多粒度封鎖協議

允許多粒度樹中的每個結點被獨立地加鎖對一個結點加鎖意味著這個結點的所有後裔結點也被加以同樣類型的鎖在多粒度封鎖中一個數據對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖顯式封鎖和隱式封鎖顯式封鎖:直接加到數據對象上的封鎖隱式封鎖:由於其上級結點加鎖而使該數據對象加上了鎖顯式封鎖和隱式封鎖的效果是一樣的對某個數據對象加鎖時系統檢查的內容

該數據對象有無顯式封鎖與之衝突

所有上級結點檢查本事務的顯式封鎖是否與該數據對象上的隱式封鎖衝突：(由上級結點封鎖造成的）所有下級結點看上面的顯式封鎖是否與本事務的隱式封鎖（將加到下級結點的封鎖）衝突。8.7封鎖的粒度8.7.1封鎖粒度8.7.2多粒度封鎖8.7.3意向鎖8.7.3意向鎖引進意向鎖（intentionlock）目的提高對某個數據對象加鎖時系統的檢查效率什麼是意向鎖對任一結點加基本鎖，必須先對它的上層結點加意向鎖如果對一個結點加意向鎖，則說明該結點的下層結點正在被加鎖意向鎖(續)例：對任一元組r加鎖，先關係R加意向鎖事務T要對關係R加X鎖,系統只要檢查根結點數據庫和關係R是否已加了不相容的鎖，不需要搜索和檢查R中的每一個元組是否加了X鎖常用意向鎖意向共用鎖(IntentShareLock，簡稱IS鎖)意向排它鎖(IntentExclusiveLock，簡稱IX鎖)共用意向排它鎖(ShareIntentExclusiveLock，簡稱SIX鎖)意向鎖（續）IS鎖如果對一個數據對象加IS鎖，表示它的後裔結點擬（意向）加S鎖。

例：要對某個元組加S鎖，則要首先對關係和數據庫加IS鎖意向鎖（續）IX鎖如果對一個數據對象加IX鎖，表示它的後裔結點擬（意向）加X鎖。例：要對某個元組加X鎖，則要首先對關係和數據庫加IX鎖。意向鎖（續）SIX鎖如果對一個數據對象加SIX鎖，表示對它加S鎖，再加IX鎖，即SIX=S+IX。例：對某個表加SIX鎖，則表示該事務要讀整個表（所以要對該表加S鎖），同時會更新個別元組（所以要對該表加IX鎖）。意向鎖（續）意向鎖的相容矩陣

T1T2SXISIXSIX-

SYNYNNYXNNNNNYISYNYYYYIXNNYYNYSIXNNYNNY-YYYYYY意向鎖（續）鎖的強度鎖的強度是指它對其他鎖的排斥程度一個事務在申請封鎖時以強鎖代替弱鎖是安全的，反之則不然SIXXSIX

-IS意向鎖（續）具有意向鎖的多粒度封鎖方法申請封鎖時應該按自上而下的次序進行；釋放封鎖時則應該按自下而上的次序進行

例：事務T要對一個數據對象加鎖，必須先對它的上層結點加意向鎖第八章併發控制8.1併發控制概述8.2封鎖8.3封鎖協議8.4活鎖和死鎖8.5併發調度的可串行性8.6兩段鎖協議8.7封鎖的粒度8.8Oracle的併發控制8.9小結8.8Oracle的併發控制Oracle採用封鎖技術保證併發操作的可串行性

Oracle鎖的種類字典鎖數據鎖（亦稱DML鎖）1.字典鎖ORACLEDBMS內部用於對字典表的封鎖由DBMS在必要的時候自動加鎖和釋放鎖，用戶無權控制字典鎖類型語法分析鎖DDL鎖2.數據鎖數據鎖類型共用鎖（S鎖）