數(shù)據(jù)庫系統(tǒng)11.ppt

1、數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第十一章 并發(fā)控制,DBMS功能總結,創(chuàng)建數(shù)據(jù)庫 創(chuàng)建表 創(chuàng)建支持結構（如索引） 讀取數(shù)據(jù)庫數(shù)據(jù) 更新（插入、修改或刪除）數(shù)據(jù)庫數(shù)據(jù) 維護數(shù)據(jù)庫結構 執(zhí)行規(guī)則、并發(fā)控制、提供安全性 執(zhí)行備份和恢復,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,事務并發(fā)執(zhí)行帶來的問題,可能會存取和存儲不正確的數(shù)據(jù)，破壞事務的隔離性和數(shù)據(jù)庫的一致性 DBMS必須提供并發(fā)控制機制 并發(fā)控制機制是衡量一個

2、DBMS性能的重要標志之一,11.1 并發(fā)控制概述,并發(fā)控制保證一個用戶的工作不會對另一個用戶的工作產生不合理的影響。 并發(fā)控制的核心是數(shù)據(jù)訪問性。在極端的情況下，一旦有一個用戶訪問數(shù)據(jù)，數(shù)據(jù)被鎖定不能訪問。這能保證數(shù)據(jù)是最新的。 通常情況下，數(shù)據(jù)是可訪問的，即使數(shù)據(jù)在更新時。,1. 并發(fā)控制的任務,對并發(fā)操作進行正確調度 保證事務的隔離性 保證數(shù)據(jù)庫的一致性,2. 并發(fā)操作帶來的數(shù)據(jù)不一致性,丟失修改（lost update） 不可重復讀（non-repeatable read） 讀“臟”數(shù)據(jù)（dirty read）,(1). 丟失修改,丟失修改是指事務1與事務2從數(shù)據(jù)庫中讀入同一數(shù)據(jù)并修改

3、，事務2的提交結果破壞了事務1提交的結果，導致事務1的修改被丟失。,T1的修改被T2覆蓋了！,(2) 不可重復讀,不可重復讀是指事務1讀取數(shù)據(jù)后，事務2執(zhí)行更新操作，使事務1無法再現(xiàn)前一次讀取結果。,(2) 不可重復讀,三類不可重復讀,事務1讀取某一數(shù)據(jù)后： 1. 事務2對其做了修改，當事務1再次讀該數(shù)據(jù)時，得到與前一次不同的值。 2. 事務2刪除了其中部分記錄，當事務1再次讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄神密地消失了。 3. 事務2插入了一些記錄，當事務1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復讀有時也稱為幻影現(xiàn)象（phantom row）,(2) 不可重復讀（按相同的條件讀）,

4、(2) 不可重復讀（按相同的條件讀和插入）,(3) 讀“臟”數(shù)據(jù),事務1修改某一數(shù)據(jù)，并將其寫回磁盤 事務2讀取同一數(shù)據(jù)后 事務1由于某種原因被撤消，這時事務1已修改過的數(shù)據(jù)恢復原值 事務2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致，是不正確的數(shù)據(jù)，又稱為“臟”數(shù)據(jù)。,(3) 讀“臟”數(shù)據(jù),第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,11.2 封鎖,為了避免并發(fā)問題，在將要修改某些數(shù)據(jù)行或表時禁止其它事務讀取、修改、寫入數(shù)據(jù)，這種方法稱資源鎖定。,用戶A,讀取Item10

5、0 假定為10 2.將Item100的 數(shù)量減少5 3.寫入Item100,1.讀取Item100 假定為10 2.將Item100的 數(shù)量減少3 3.寫入Item100,1.讀取Item100(為A) 2.讀取Item100(為B) 3.將Item100的數(shù)量設置為5(為A) 4.為A寫入Item100 5.將Item100的數(shù)量設置為7(為B) 6.為B寫入Item100,用戶B,數(shù)據(jù)庫服務器上的處理順序：交叉并發(fā)執(zhí)行,用戶A,讀取Item100假定為10 2.將Item100的數(shù)量減少5 3.寫入Item100,1.讀取Item100假定為10 2.將Item100的數(shù)量減少3 3.寫入

6、Item100,1.鎖定Item100 (為A) 2.讀取Item100(為A)，數(shù)量為10 3.鎖定Item100 (為B);無法執(zhí)行，B等待 4.將Item100的數(shù)量設置為5(為A) 5.為A寫入Item100 6.釋放A對Item100的鎖定 7.鎖定Item100 (為B) 8.讀取Item100(為B)，數(shù)量為5 9.將Item100的數(shù)量設置為2(為B) 10.為B寫入Item100 11.釋放B對Item100的鎖定,用戶B,數(shù)據(jù)庫服務器上的處理順序,A事務,B事務,一、顯示封鎖和隱式封鎖,由DBMS執(zhí)行的鎖定稱隱式封鎖(Implicit lock) 由用戶編寫命令行執(zhí)行的鎖定

7、稱顯式封鎖(Explicit lock),二、封鎖類型,DBMS通常提供了多種類型的封鎖。一個事務對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控制是由封鎖的類型決定的。 基本封鎖類型 排它鎖（eXclusive lock，簡記為X鎖） 共享鎖（Share lock，簡記為S鎖）,排它鎖(exclusive lock) Xlock,排它鎖又稱為寫鎖 若事務T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務都不能再對A加任何類型的鎖，直到T釋放A上的鎖,共享鎖(shared lock) Slock,共享鎖又稱為讀鎖 若事務T對數(shù)據(jù)對象A加上S鎖，則其它事務只能再對A加S鎖，而不能加X鎖，直到T釋

8、放A上的S鎖,三、鎖的相容矩陣,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,11.3 封鎖協(xié)議,在運用X鎖和S鎖對數(shù)據(jù)對象加鎖時，需要約定一些規(guī)則：封鎖協(xié)議（Locking Protocol） 何時申請X鎖或S鎖 持鎖時間、何時釋放 不同的封鎖協(xié)議，在不同的程度上為并發(fā)操作的正確調度提供一定的保證 常用的封鎖協(xié)議：三級封鎖協(xié)議,一級封鎖協(xié)議,事務T在修改數(shù)據(jù)R之前必須先對其加X鎖，直到事務結束才釋放 正常結束（COMMIT） 非正常結束（ROLLBACK） 一級封

9、鎖協(xié)議可防止丟失修改 在一級封鎖協(xié)議中，如果是讀數(shù)據(jù)，是不需要加鎖的，所以它不能保證可重復讀和不讀“臟”數(shù)據(jù)。,一級封鎖協(xié)議,沒有丟失修改,一級封鎖協(xié)議,讀“臟”數(shù)據(jù),一級封鎖協(xié)議,不可重復讀,二級封鎖協(xié)議,一級封鎖協(xié)議+事務T在讀取數(shù)據(jù)R前必須先加S鎖，讀完后即可釋放S鎖 二級封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)。 在二級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復讀。,二級封鎖協(xié)議,不讀“臟”數(shù)據(jù),二級封鎖協(xié)議,不可重復讀,三級封鎖協(xié)議,1級封鎖協(xié)議 + 事務T在讀取數(shù)據(jù)R之前必須先對其加S鎖，直到事務結束才釋放 3級封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復讀。,三級封

10、鎖協(xié)議,可重復讀,三級封鎖協(xié)議,不讀“臟”數(shù)據(jù),4封鎖協(xié)議小結,三級協(xié)議的主要區(qū)別 什么操作需要申請X鎖或S鎖 何時釋放鎖（即持鎖時間）,封鎖協(xié)議小結(續(xù)),第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,11.4 活鎖和死鎖,封鎖技術可以有效地解決并行操作的一致性問題，但也帶來一些新的問題 活鎖 死鎖,11.4.1 活鎖,T2永遠等待！,如何避免活鎖,采用先來先服務的策略： 當多個事務請求封鎖同一數(shù)據(jù)對象時 按請求封鎖的先后次序對這些事務排隊 該數(shù)據(jù)對象上的鎖一旦釋

11、放，首先批準申請隊列中第一個事務獲得鎖。,11.4.2 死鎖,T1 T2,解決死鎖的方法,兩類方法 1. 采取一定措施來預防死鎖的發(fā)生 2. 允許死鎖發(fā)生，采用一定手段定期診斷系統(tǒng)中有無死鎖，若有則解除之。,1. 死鎖的預防,產生死鎖的原因是兩個或多個事務都已封鎖了一些數(shù)據(jù)對象，然后又都請求對已為其他事務封鎖的數(shù)據(jù)對象加鎖，從而出現(xiàn)死等待。 預防死鎖的發(fā)生就是要破壞產生死鎖的條件,死鎖的預防（續(xù)）,預防死鎖的方法 一次封鎖法 順序封鎖法,（1）一次封鎖法,要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行 一次封鎖法存在的問題： 降低并發(fā)度 難于事先精確確定封鎖對象,（2）順序

12、封鎖法,順序封鎖法是預先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務都按這個順序實行封鎖。 順序封鎖法存在的問題 維護成本高 數(shù)據(jù)庫系統(tǒng)中可封鎖的數(shù)據(jù)對象極其眾多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護這樣極多而且變化的資源的封鎖順序非常困難，成本很高,順序封鎖法（續(xù)）,難于實現(xiàn) 事務的封鎖請求可以隨著事務的執(zhí)行而動態(tài)地決定，很難事先確定每一個事務要封鎖哪些對象，因此也就很難按規(guī)定的順序去施加封鎖。 例：規(guī)定數(shù)據(jù)對象的封鎖順序為A,B,C,D,E。事務T3起初要求封鎖數(shù)據(jù)對象B,C,E，但當它封鎖了B,C后，才發(fā)現(xiàn)還需要封鎖A，這樣就破壞了封鎖順序.,死鎖的預防（續(xù)）,結論 在操作系統(tǒng)中廣為

13、采用的預防死鎖的策略并不很適合數(shù)據(jù)庫的特點 DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法,2. 死鎖的診斷與解除,允許死鎖發(fā)生 解除死鎖 由DBMS的并發(fā)控制子系統(tǒng)定期檢測系統(tǒng)中是否存在死鎖 一旦檢測到死鎖，就要設法解除,檢測死鎖：超時法,如果一個事務的等待時間超過了規(guī)定的時限，就認為發(fā)生了死鎖 優(yōu)點：實現(xiàn)簡單 缺點 有可能誤判死鎖，事物因為其他原因使得等待時間超過時限，系統(tǒng)會誤認為發(fā)生了死鎖。 時限若設置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn),死鎖的診斷與解除（續(xù)）,解除死鎖 選擇一個處理死鎖代價最小的事務，將其撤消，釋放此事務持有的所有的鎖，使其它事務能繼續(xù)運行下去。,第十一章 并

14、發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,11.5 并發(fā)調度的可串行性,并發(fā)調度的可串行性是并行執(zhí)行事務正確性的唯一準則。 一、什么樣的并發(fā)操作調度是正確的 二、如何保證并發(fā)操作的調度是正確的,一、什么樣的并發(fā)操作調度是正確的,計算機系統(tǒng)對并行事務中并行操作的調度是隨機的，而不同的調度可能會產生不同的結果。 例：現(xiàn)在有兩個事務，分別包含下列操作： 事務1：讀B；A=B+1；寫回A； 事務2：讀A；B=A+1；寫回B； 假設A的初值為2，B的初值為2。,什么樣的并發(fā)操作調度是

15、正確的,對這兩個事務的不同調度策略 串行執(zhí)行 串行調度策略1 串行調度策略2 交錯執(zhí)行 不可串行化的調度 可串行化的調度,(a) 串行調度策略，正確的調度,Slock B Y=B=2 Unlock B Xlock A A=Y+1 寫回A(=3) Unlock A,Slock A X=A=3 Unlock A Xlock B B=X+1 寫回B(=4) Unlock B,T1,T2,(b) 串行調度策略，正確的調度,Slock B Y=B=3 Unlock B Xlock A A=Y+1 寫回A(=4) Unlock A,SlockA X=A=2 Unlock A Xlock B B=X+1 寫

16、回B(=3) Unlock B,T1,T2,(c) 不可串行化的調度,Slock B Y=B=2 Unlock B Xlock A A=Y+1 寫回A(=3) Unlock A,Slock A X=A=2 Unlock A Xlock B B=X+1 寫回B(=3) Unlock B,T1,T2,由于其執(zhí)行結果與(a)、(b)的結果都不同，所以是錯誤的調度。,(d) 可串行化的調度,Slock B Y=B=2 Unlock B Xlock A A=Y+1 寫回A(=3) Unlock A,Slock A 等待 等待 等待 X=A=3 Unlock A Xlock B B=X+1 寫回B(=4)

17、 Unlock B,T1,T2,由于其執(zhí)行結果與串行調度（a）的執(zhí)行結果相同，所以是正確的調度。,將所有事務串行起來的調度策略一定是正確的調度策略。將此結果作為并發(fā)操作調度是否正確的判斷標準。,什么樣的并發(fā)操作調度是正確的,以不同的順序串行執(zhí)行事務也有可能會產生不同的結果，但由于不會將數(shù)據(jù)庫置于不一致狀態(tài)，所以都可以認為是正確的。 幾個事務的并行執(zhí)行是正確的，當且僅當其結果與按某一次序串行地執(zhí)行它們時的結果相同。這種并行調度策略稱為可串行化（Serializable）的調度。,11.5 并發(fā)調度的可串行性,一、什么樣的并發(fā)操作調度是正確的 二、如何保證并發(fā)操作的調度是正確的,二、如何保證并發(fā)操

18、作的調度是正確的,為了保證并行操作的正確性，DBMS的并行控制機制必須提供一定的手段來保證調度是可串行化的。 從理論上講，在某一事務執(zhí)行時禁止其他事務執(zhí)行的調度策略一定是可串行化的調度，這也是最簡單的調度策略，但這種方法實際上是不可行的，因為它使用戶不能充分共享數(shù)據(jù)庫資源。,如何保證并發(fā)操作的調度是正確的(續(xù)),保證并發(fā)操作調度正確性的方法 封鎖方法：兩段鎖（Two-Phase Locking，簡稱2PL）協(xié)議 時標方法 樂觀方法,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7

19、封鎖的粒度,11.6 兩段鎖協(xié)議,兩段鎖協(xié)議的內容 1. 在對任何數(shù)據(jù)進行讀、寫操作之前，事務首先要獲得對該數(shù)據(jù)的封鎖 2. 在釋放一個封鎖之后，事務不再獲得任何其他封鎖。,兩段鎖協(xié)議（續(xù)）,“兩段”鎖的含義 事務分為兩個階段 第一階段是獲得封鎖，也稱為擴展階段； 第二階段是釋放封鎖，也稱為收縮階段。,兩段鎖協(xié)議（續(xù)）,例： 事務1的封鎖序列： Slock A . Slock B . Xlock C . Unlock B . Unlock A . Unlock C； 事務2的封鎖序列： Slock A . Unlock A . Slock B . Xlock C . Unlock C . Un

20、lock B； 事務1遵守兩段鎖協(xié)議，而事務2不遵守兩段協(xié)議。,兩段鎖協(xié)議（續(xù)）,并行執(zhí)行的所有事務均遵守兩段鎖協(xié)議，則對這些事務的所有并行調度策略都是可串行化的。 所有遵守兩段鎖協(xié)議的事務，其并行執(zhí)行的結果一定是正確的 事務遵守兩段鎖協(xié)議是可串行化調度的充分條件，而不是必要條件 可串行化的調度中，不一定所有事務都必須符合兩段鎖協(xié)議。,兩段鎖協(xié)議（續(xù)）,兩段鎖協(xié)議與防止死鎖的一次封鎖法 一次封鎖法要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議 但是兩段鎖協(xié)議并不要求事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務可能發(fā)生死鎖,兩

21、段鎖協(xié)議（續(xù)）,圖11.7 遵守兩段鎖協(xié)議的事務發(fā)生死鎖,T1 Slock B 讀B=2 Xlock A 等待 等待,T2 Slock A 讀A=2 Xlock B 等待,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 封鎖協(xié)議 11.4 活鎖和死鎖 11.5 并發(fā)調度的可串行性 11.6 兩段鎖協(xié)議 11.7 封鎖的粒度,11.7 封鎖的粒度,封鎖可以針對數(shù)據(jù)庫、表、數(shù)據(jù)行、索引等數(shù)據(jù)庫對象。封鎖對象的大小稱鎖定粒度。 粒度大的封鎖，DBMS容易管理，但易引發(fā)沖突 粒度小的封鎖，DBMS要跟蹤許多細節(jié)內容，不易管理,1. 選擇封鎖粒度的原則,封鎖的粒度越 大，小， 系統(tǒng)

22、被封鎖的對象 少，多， 并發(fā)度 小，高， 系統(tǒng)開銷 小，大， 選擇封鎖粒度： 考慮封鎖開銷和并發(fā)度兩個因素，適當選擇封鎖粒度以求得最優(yōu)的效果。,選擇封鎖粒度的原則（續(xù)）,需要處理多個關系的大量元組的用戶事務：以數(shù)據(jù)庫為封鎖單位； 需要處理大量元組的用戶事務：以關系為封鎖單元； 只處理少量元組的用戶事務：以元組為封鎖單位,2. 多粒度封鎖,在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務選擇，這種封鎖方法稱為多粒度封鎖(multiple granularity locking) 。 多粒度樹 以樹形結構來表示多級封鎖粒度 根結點是整個數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度 葉結點表示最小的數(shù)據(jù)粒度,多粒度封鎖（續(xù)）,例：三級粒度樹。根結點為數(shù)據(jù)庫，數(shù)據(jù)庫的子結點為關系，關系的子結點為元組。,多粒度封鎖協(xié)議,允許多粒度樹中的每個結點被獨立地加鎖 對一個結點加鎖意味著這個結點的所有后裔結點也被加以同樣類型的鎖 在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖,顯式封鎖和隱式封鎖,顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖 隱式封鎖: 由于其上級結點加鎖而使該數(shù)據(jù)對象加上了鎖 顯式封鎖和隱式封鎖的效果是一樣的,對某個數(shù)據(jù)對象加鎖時系統(tǒng)檢查的內容,該數(shù)據(jù)對象 有無顯式封鎖與之沖突 所有上級結點 檢查本事務的顯