數據庫系統概論AnIntroductiontoDatabaseSystem第十一章

并發控制1xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結2xuyuezhu@

(1)事務串行執行每個時刻只有一個事務運行，其他事務必須等到這個事務結束以后方能運行不能充分利用系統資源，發揮數據庫共享資源的特點多事務執行方式3xuyuezhu@(2)交叉并發方式（interleavedconcurrency）事務的并行執行是這些并行事務的并行操作輪流交叉運行是單處理機系統中的并發方式，能夠減少處理機的空閑時間，提高系統的效率4xuyuezhu@(3)同時并發方式（simultaneousconcurrency）多處理機系統中，每個處理機可以運行一個事務，多個處理機可以同時運行多個事務，實現多個事務真正的并行運行最理想的并發方式，但受制于硬件環境更復雜的并發方式機制5xuyuezhu@事務并發執行帶來的問題可能會存取和存儲不正確的數據，破壞事務的隔離性和數據庫的一致性DBMS必須提供并發控制機制并發控制機制是衡量一個DBMS性能的重要標志之一6xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結7xuyuezhu@11.1并發控制概述并發控制機制的任務對并發操作進行正確調度保證事務的隔離性保證數據庫的一致性8xuyuezhu@T1的修改被T2覆蓋了！

讀A=16

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

②

③A←A-1

寫回A=15

④事務T2事務T1數據不一致實例：飛機訂票系統9xuyuezhu@并發操作帶來的數據不一致性丟失修改（lostupdate）不可重復讀（non-repeatableread）讀“臟”數據（dirtyread）10xuyuezhu@圖11.1三種數據不一致性T1T2①讀A=16

②

③A←A-1

寫回A=15

④

讀A=16

A←A-1寫回A=15(a)丟失修改11xuyuezhu@1.丟失修改丟失修改是指事務1與事務2從數據庫中讀入同一數據并修改事務2的提交結果破壞了事務1提交的結果，導致事務1的修改被丟失。12xuyuezhu@圖11.1三種數據不一致性(續)

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

①

讀A=50

讀B=100

求和=150②

③讀A=50

讀B=200

求和=250(驗算不對)T2T1(b)不可重復讀13xuyuezhu@2.不可重復讀不可重復讀是指事務1讀取數據后，事務2執行更新操作，使事務1無法再現前一次讀取結果。14xuyuezhu@三類不可重復讀事務1讀取某一數據后：1。事務2對其做了修改，當事務1再次讀該數據時，得到與前一次不同的值。2.事務2刪除了其中部分記錄，當事務1再次讀取數據時，發現某些記錄神密地消失了。3.事務2插入了一些記錄，當事務1再次按相同條件讀取數據時，發現多了一些記錄.

后兩種不可重復讀有時也稱為幻影現象（phantomrow）15xuyuezhu@圖11.1三種數據不一致性(續)

讀C=200

①讀C=100C←C*2

寫回C②

③ROLLBACKC恢復為100T2T1(c)讀“臟”數據16xuyuezhu@3.讀“臟”數據事務1修改某一數據，并將其寫回磁盤事務2讀取同一數據后事務1由于某種原因被撤消，這時事務1已修改過的數據恢復原值事務2讀到的數據就與數據庫中的數據不一致，是不正確的數據，又稱為“臟”數據。17xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結18xuyuezhu@11.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣19xuyuezhu@一、什么是封鎖封鎖就是事務T在對某個數據對象（例如表、記錄等）操作之前，先向系統發出請求，對其加鎖加鎖后事務T就對該數據對象有了一定的控制，在事務T釋放它的鎖之前，其它的事務不能更新此數據對象。封鎖是實現并發控制的一個非常重要的技術20xuyuezhu@11.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣21xuyuezhu@二、基本封鎖類型DBMS通常提供了多種類型的封鎖。一個事務對某個數據對象加鎖后究竟擁有什么樣的控制是由封鎖的類型決定的。基本封鎖類型排它鎖（eXclusivelock，簡記為X鎖）共享鎖（Sharelock，簡記為S鎖）22xuyuezhu@

排它鎖

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

T1T2XS-XNNYSNYY-YYY26xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結27xuyuezhu@11.3封鎖協議在運用X鎖和S鎖對數據對象加鎖時，需要約定一些規則：封鎖協議（LockingProtocol）何時申請X鎖或S鎖持鎖時間、何時釋放不同的封鎖協議，在不同的程度上為并發操作的正確調度提供一定的保證常用的封鎖協議：三級封鎖協議28xuyuezhu@1級封鎖協議事務T在修改數據R之前必須先對其加X鎖，直到事務結束才釋放正常結束（COMMIT）非正常結束（ROLLBACK）1級封鎖協議可防止丟失修改在1級封鎖協議中，如果是讀數據，不需要加鎖的，所以它不能保證可重復讀和不讀“臟”數據。29xuyuezhu@1級封鎖協議T1T2①

XlockA

獲得②

讀A=16

③A←A-1

寫回A=15CommitUnlockA④

⑤

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

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

讀A=15①

XlockA

獲得②

讀A=16

A←A-1

寫回A=15③

④RollbackUnlockA

T2T1讀“臟”數據31xuyuezhu@1級封鎖協議

XlockB

獲得

讀B=100B←B*2

寫回B=200CommitUnlockB①讀A=50

讀B=100

求和=150②③讀A=50

讀B=200

求和=250(驗算不對)T2T1不可重復讀32xuyuezhu@

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

SclockA

獲得讀A=50UnlockA②SclockB

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

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

獲得讀A=50UnlockA

SclockB

獲得讀B=200UnlockB

求和=250(驗算不對)

T2T1(續)34xuyuezhu@

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

SlockA

讀A=50

SlockB

讀B=100

求和=150②

③讀A=50

讀B=100

求和=150CommitUnlockAUnlockB④

⑤

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

可重復讀36xuyuezhu@3級封鎖協議T1T2①

XlockC

讀C=100C←C*2

寫回C=200②

③ROLLBACK(C恢復為100)UnlockC④

⑤

SlockC等待等待等待等待獲得SlockC讀C=100CommitCUnlockC不讀“臟”數據37xuyuezhu@4．封鎖協議小結三級協議的主要區別什么操作需要申請封鎖何時釋放鎖（即持鎖時間）38xuyuezhu@封鎖協議小結(續)39xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結40xuyuezhu@11.4活鎖和死鎖封鎖技術可以有效地解決并行操作的一致性問題，但也帶來一些新的問題死鎖活鎖41xuyuezhu@11.4.1活鎖42xuyuezhu@如何避免活鎖采用先來先服務的策略：當多個事務請求封鎖同一數據對象時按請求封鎖的先后次序對這些事務排隊該數據對象上的鎖一旦釋放，首先批準申請隊列中第一個事務獲得鎖。43xuyuezhu@11.4.2死鎖

T1T2

Xlock

R1...XlockR2等待等待等待...XlockR2..Xlock

R1等待等待.44xuyuezhu@

解決死鎖的方法

兩類方法1.預防死鎖2.死鎖的診斷與解除45xuyuezhu@1.死鎖的預防產生死鎖的原因是兩個或多個事務都已封鎖了一些數據對象，然后又都請求對已為其他事務封鎖的數據對象加鎖，從而出現死等待。預防死鎖的發生就是要破壞產生死鎖的條件46xuyuezhu@死鎖的預防（續）預防死鎖的方法一次封鎖法順序封鎖法47xuyuezhu@2.死鎖的診斷與解除允許死鎖發生解除死鎖由DBMS的并發控制子系統定期檢測系統中是否存在死鎖一旦檢測到死鎖，就要設法解除48xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結49xuyuezhu@11.5并發調度的可串行性一、什么樣的并發操作調度是正確的二、如何保證并發操作的調度是正確的50xuyuezhu@一、什么樣的并發操作調度是正確的計算機系統對并行事務中并行操作的調度是的隨機的，而不同的調度可能會產生不同的結果。將所有事務串行起來的調度策略一定是正確的調度策略。如果一個事務運行過程中沒有其他事務在同時運行，也就是說它沒有受到其他事務的干擾，那么就可以認為該事務的運行結果是正常的或者預想的51xuyuezhu@什么樣的并發操作調度是正確的（續）以不同的順序串行執行事務也有可能會產生不同的結果，但由于不會將數據庫置于不一致狀態，所以都可以認為是正確的。幾個事務的并行執行是正確的，當且僅當其結果與按某一次序串行地執行它們時的結果相同。這種并行調度策略稱為可串行化（Serializable）的調度。52xuyuezhu@什么樣的并發操作調度是正確的（續）可串行性是并行事務正確性的唯一準則例：現在有兩個事務，分別包含下列操作：事務1：讀B；A=B+1；寫回A；

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

假設A的初值為2，B的初值為2。53xuyuezhu@結果：A=3；B=4A=4；B=354xuyuezhu@11.5并發調度的可串行性一、什么樣的并發操作調度是正確的二、如何保證并發操作的調度是正確的55xuyuezhu@二、如何保證并發操作的調度是正確的為了保證并行操作的正確性，DBMS的并行控制機制必須提供一定的手段來保證調度是可串行化的。從理論上講，在某一事務執行時禁止其他事務執行的調度策略一定是可串行化的調度，這也是最簡單的調度策略，但這種方法實際上是不可行的，因為它使用戶不能充分共享數據庫資源。56xuyuezhu@如何保證并發操作的調度是正確的（續）保證并發操作調度正確性的方法封鎖方法：兩段鎖（Two-PhaseLocking，簡稱2PL）協議時標方法樂觀方法57xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結58xuyuezhu@11.6兩段鎖協議兩段鎖協議的內容1.在對任何數據進行讀、寫操作之前，事務首先要獲得對該數據的封鎖2.在釋放一個封鎖之后，事務不再獲得任何其他封鎖。59xuyuezhu@第十一章并發控制11.1并發控制概述11.2封鎖11.3封鎖協議11.4活鎖和死鎖11.5并發調度的可串行性11.6兩段鎖協議11.7封鎖的粒度11.8小結60xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖61xuyuezhu@11.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則62xuyuezhu@一、什么是封鎖粒度X鎖和S鎖都是加在某一個數據對象上的封鎖的對象:邏輯單元，物理單元例：在關系數據庫中，封鎖對象：邏輯單元:屬性值、屬性值集合、元組、關系、索引項、整個索引、整個數據庫等物理單元：頁（數據頁或索引頁）、物理記錄等63xuyuezhu@11.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則64xuyuezhu@二、選擇封鎖粒度的原則封鎖的粒度越大系統被封鎖的對象少并發度小系統開銷小選擇封鎖粒度：考慮封鎖機構和并發度兩個因素對系統開銷與并發度進行權衡小多高大65xuyuezhu@選擇封鎖粒度的原則（續）需要處理多個關系的大量元組的用戶事務：以數據庫為封鎖單位；需要處理大量元組的用戶事務：以關系為封鎖單元；只處理少量元組的用戶事務：以元組為封鎖單位66xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖67xuyuezhu@11.7.2多粒度封鎖多粒度樹以樹形結構來表示多級封鎖粒度根結點是整個數據庫，表示最大的數據粒度葉結點表示最小的數據粒度

68xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖69xuyuezhu@11.7.3意向鎖引進意向鎖（intentionlock）目的提高對某個數據對象加鎖時系統的檢查效率70xuyuezhu@什么是意向鎖對任一結點加基本鎖，必須先對它的上層結點加意向鎖如果對一個結點加意向鎖，則說明該結點的下層結點正在被加鎖71xuyuezhu@常用意向鎖意向共享鎖(IntentShareLock，簡稱IS鎖)意向排它鎖(IntentExclusiveLock，簡稱IX鎖)共享意向排它鎖(ShareIntentExclusiveLock，簡稱SIX鎖)72xuyuezhu@意向鎖（續）意向鎖的相容矩陣

T1T2SXISIXSIX-

SYNYNNY