數(shù)據(jù)庫系統(tǒng)概論高等教育出版社chp11

1、數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論 An Introduction to Database System 第十一章第十一章 并發(fā)控制并發(fā)控制 主要內(nèi)容：本章主要介紹數(shù)據(jù)庫的并發(fā)控制主要內(nèi)容：本章主要介紹數(shù)據(jù)庫的并發(fā)控制 機制的概念及保證并發(fā)執(zhí)行正確性的原則。機制的概念及保證并發(fā)執(zhí)行正確性的原則。 重點難點：并發(fā)控制、重點難點：并發(fā)控制、 鎖協(xié)議、鎖協(xié)議、 并發(fā)控制的并發(fā)控制的 正確性準則等概念。正確性準則等概念。 多用戶數(shù)據(jù)庫系統(tǒng)的存在 允許多個用戶同時使用的數(shù)據(jù)庫系統(tǒng) n飛機定票數(shù)據(jù)庫系統(tǒng) n銀行數(shù)據(jù)庫系統(tǒng) 特點：在同一時刻并發(fā)運行的事務數(shù)可達數(shù)百個 不同的多事務執(zhí)行方式 (1)事務串行執(zhí)行 每個

2、時刻只有一個事務運行，其 他事務必須等到這個事務結束以 后方能運行 不能充分利用系統(tǒng)資源，發(fā)揮數(shù) 據(jù)庫共享資源的特點 T1 T2 T3 事務的串行執(zhí)行方式 (2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機系統(tǒng)中，事務的并行執(zhí)行是這些并行事務 的并行操作輪流交叉運行 單處理機系統(tǒng)中的并行事務并沒有真正地并行運行， 但能夠減少處理機的空閑時間，提高系統(tǒng)的效率 事務的交叉并發(fā)執(zhí)行方式 (3)同時并發(fā)方式（simultaneous concurrency） 多處理機系統(tǒng)中，每個處理機可以運行一個事務， 多個處理機可以同時運行多個事務，實現(xiàn)多個事務 真正的并行運行 一個簡

3、單的銀行數(shù)據(jù)庫系統(tǒng)一個簡單的銀行數(shù)據(jù)庫系統(tǒng) 設每個帳號在數(shù)據(jù)庫中具有一條數(shù)據(jù)庫記設每個帳號在數(shù)據(jù)庫中具有一條數(shù)據(jù)庫記 錄，用以記錄這個帳號的存款數(shù)量和其他信息。錄，用以記錄這個帳號的存款數(shù)量和其他信息。 設有兩個事務設有兩個事務T0和和T1， 事務事務T0從帳號從帳號A轉轉2000 元到帳號元到帳號B；事務；事務T1從帳號從帳號A轉轉20%的款到帳的款到帳 號號B。 T 0和和T 1的定義如下：的定義如下： 例例: 事務并發(fā)執(zhí)行帶來的問題 T0: read(A); T1: read(A); A:=A-2000; temp:=A*0.2; write(A); A:=A-temp; read(B)

4、; write(A); B:=B+2000; read(B); write(B) B:=B+temp; write(B) 假設用假設用A和和B表示帳號表示帳號A和帳號和帳號B的存款數(shù)量；的存款數(shù)量； A、B的初值為的初值為10000和和20000。如果這兩個事務順。如果這兩個事務順 序執(zhí)行，可以有兩種方案。序執(zhí)行，可以有兩種方案。 一種是先執(zhí)行一種是先執(zhí)行T0后執(zhí)行后執(zhí)行T1，如圖，如圖a所示。所示。 另一種是先執(zhí)行另一種是先執(zhí)行T1后執(zhí)行后執(zhí)行T0，如圖，如圖b所示。所示。 結果正確 結果錯誤 對于對于N N個事務，一個事務，一 定最多有定最多有N!N!種正確種正確 的串行調度。并行的串行調

5、度。并行 調度將產(chǎn)生不一致調度將產(chǎn)生不一致 狀態(tài)。狀態(tài)。 并發(fā)事務的可串行化并發(fā)事務的可串行化 可串行化并行調度策略：幾個事務的并行執(zhí)行是正確可串行化并行調度策略：幾個事務的并行執(zhí)行是正確 的，當且僅當其結果與按某一次序串行執(zhí)行它們時的結果的，當且僅當其結果與按某一次序串行執(zhí)行它們時的結果 相同。相同?？纱行允遣⑿惺聞照_性的惟一準則可串行性是并行事務正確性的惟一準則。 會產(chǎn)生多個事務同時存取同一數(shù)據(jù)的情況 可能會存取和存儲不正確的數(shù)據(jù)，破壞事務一致性和 數(shù)據(jù)庫的一致性 事務并發(fā)執(zhí)行帶來的問題 DBMS的一個重要任務就是要有一種機制去保證事務在的一個重要任務就是要有一種機制去保證事務在 并發(fā)

6、的存取和修改數(shù)據(jù)的時候數(shù)據(jù)的完整性不被破壞，并發(fā)的存取和修改數(shù)據(jù)的時候數(shù)據(jù)的完整性不被破壞， 同時同時 確保這些事務能正確的運行并取得正確的結果。確保這些事務能正確的運行并取得正確的結果。 并發(fā)控制就并發(fā)控制就 是一種在多用戶環(huán)境下對數(shù)據(jù)庫進行并發(fā)操作規(guī)范的機制。是一種在多用戶環(huán)境下對數(shù)據(jù)庫進行并發(fā)操作規(guī)范的機制。 1. 并發(fā)帶來的好處和問題并發(fā)帶來的好處和問題 (1) 并發(fā)的優(yōu)點并發(fā)的優(yōu)點 改善系統(tǒng)的資源利用率。改善系統(tǒng)的資源利用率。 (2) 并發(fā)所引起的問題并發(fā)所引起的問題 在并發(fā)執(zhí)行過程中如果不對并發(fā)執(zhí)行的事務通過某種在并發(fā)執(zhí)行過程中如果不對并發(fā)執(zhí)行的事務通過某種 機制加以控制，機制加以

7、控制， 將有可能產(chǎn)生數(shù)據(jù)的不一致性等問題。將有可能產(chǎn)生數(shù)據(jù)的不一致性等問題。 以飛機訂票系統(tǒng)為例的一個活動序列：以飛機訂票系統(tǒng)為例的一個活動序列： 甲售票點（甲事務）讀出某航班的機票余額，甲售票點（甲事務）讀出某航班的機票余額， 設；設； 乙售票點（乙事務）讀出同一航班的機票余額，乙售票點（乙事務）讀出同一航班的機票余額， 也為；也為； 甲售票點賣出一張機票，甲售票點賣出一張機票， 修改余額修改余額， 變?yōu)?，變?yōu)椋?把寫回數(shù)據(jù)庫；把寫回數(shù)據(jù)庫； 乙售票點也賣出一張機票，乙售票點也賣出一張機票， 修改余額修改余額， 也變?yōu)?，也變?yōu)椋?把寫回數(shù)據(jù)庫。把寫回數(shù)據(jù)庫。 結果是明明賣出兩張結果是明明賣出

8、兩張 機票，機票， 但數(shù)據(jù)庫中機票余額只減少。但數(shù)據(jù)庫中機票余額只減少。 這種情況稱為這種情況稱為數(shù)據(jù)庫的不一致性數(shù)據(jù)庫的不一致性。 這種不這種不 一致性是由一致性是由并發(fā)操作引起并發(fā)操作引起的。的。 在并發(fā)操作情況下，在并發(fā)操作情況下， 對甲、對甲、 乙兩個事務的操作序列的調度是隨機的。乙兩個事務的操作序列的調度是隨機的。 若按上面的調度序列執(zhí)行，若按上面的調度序列執(zhí)行， 甲事務的修改就被丟甲事務的修改就被丟 失。失。 這是由于第步中乙事務修改并寫回后覆這是由于第步中乙事務修改并寫回后覆 蓋了甲事務的修改。蓋了甲事務的修改。 可見，可見， 若對并發(fā)的事務訪問若對并發(fā)的事務訪問 數(shù)據(jù)庫的操作不

9、進行有效控制，數(shù)據(jù)庫的操作不進行有效控制， 數(shù)據(jù)庫中的數(shù)據(jù)數(shù)據(jù)庫中的數(shù)據(jù) 就有可能變?yōu)椴徽_，就有可能變?yōu)椴徽_， 從而影響數(shù)據(jù)的正確性。從而影響數(shù)據(jù)的正確性。 注： 并發(fā)操作帶來的數(shù)據(jù)不一致性通常分為三類：并發(fā)操作帶來的數(shù)據(jù)不一致性通常分為三類： 丟失修丟失修 改、不可重復讀和讀改、不可重復讀和讀“臟臟”數(shù)據(jù)。數(shù)據(jù)。 丟失修改丟失修改（Lost Update）。 丟失修改是由于兩個事務對同一數(shù)據(jù)并發(fā)地寫入所引丟失修改是由于兩個事務對同一數(shù)據(jù)并發(fā)地寫入所引 起的，起的， 常稱為寫后寫沖突（常稱為寫后寫沖突（Write-Write Conflict）。）。 上上 面飛機訂票例子就屬此類。面飛機訂

10、票例子就屬此類。 不可重復讀不可重復讀（Non-Repeatable Read）。 不可重復讀是指事務不可重復讀是指事務T1讀取數(shù)據(jù)后，事務讀取數(shù)據(jù)后，事務T2執(zhí)行更新執(zhí)行更新 操作，操作， 使使1無法再現(xiàn)前一次讀取結果。無法再現(xiàn)前一次讀取結果。 具體地講，具體地講， 不可不可 重復讀包括三種情況重復讀包括三種情況： （a） 事務事務T1讀取某一數(shù)據(jù)后，讀取某一數(shù)據(jù)后， 事務事務T2對其對其 作了修改，作了修改， 當事務當事務T1再次讀該數(shù)據(jù)時，再次讀該數(shù)據(jù)時， 得到與前得到與前 一次不同的值。一次不同的值。 時刻事務T1事務T2數(shù)據(jù)庫X的值 t0read(X)X=30 t1read(X)X=

11、30 t2X:X+10 t3write(X)X=40 t4X=30是一個過時的數(shù)據(jù) （b） 事務事務T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù)按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù) 記錄后，記錄后， 事務事務T2刪除了其中部分記錄，刪除了其中部分記錄， 當當T1再次按相再次按相 同條件讀取數(shù)據(jù)時，同條件讀取數(shù)據(jù)時， 發(fā)現(xiàn)某些記錄神秘的消失了。發(fā)現(xiàn)某些記錄神秘的消失了。 （c） 事務事務T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)按一定條件從數(shù)據(jù)庫中讀取了某些數(shù) 據(jù)記錄后，據(jù)記錄后， 事務事務T2插入了一些記錄，插入了一些記錄， 當當T1再次按相同再次按相同 條件讀取數(shù)據(jù)時，條件讀取數(shù)據(jù)時， 發(fā)現(xiàn)多了一些記錄。

12、發(fā)現(xiàn)多了一些記錄。 后兩種不可重復讀有時也稱為后兩種不可重復讀有時也稱為幻影（幻影（Phantom Row）現(xiàn)象）現(xiàn)象。 讀讀“臟臟”數(shù)據(jù)（數(shù)據(jù)（irty Read）。）。 讀讀“臟臟”數(shù)據(jù)是指兩個或多個事務并發(fā)執(zhí)行時，數(shù)據(jù)是指兩個或多個事務并發(fā)執(zhí)行時， 事務事務 T1修改了某一數(shù)據(jù)，修改了某一數(shù)據(jù)， 并將其寫回磁盤，并將其寫回磁盤， 事務事務T2在這之后讀在這之后讀 取了同一數(shù)據(jù)，取了同一數(shù)據(jù)， 此時事務此時事務T1在未正式提交之前由于某種原在未正式提交之前由于某種原 因被撤銷，因被撤銷， 系統(tǒng)就要對事務系統(tǒng)就要對事務T1已修改過的數(shù)據(jù)恢復原值，已修改過的數(shù)據(jù)恢復原值， 這樣事務這樣事務T2

13、讀的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)產(chǎn)生了不一致，讀的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)產(chǎn)生了不一致， 稱這種數(shù)據(jù)為稱這種數(shù)據(jù)為“臟臟”數(shù)據(jù)。數(shù)據(jù)。 產(chǎn)生上述三類數(shù)據(jù)不一致性的產(chǎn)生上述三類數(shù)據(jù)不一致性的 主要原因是并發(fā)操作破壞了事務的隔離性。主要原因是并發(fā)操作破壞了事務的隔離性。 時刻事務T1事務T2數(shù)據(jù)庫X的值 t0read(X)X=10 t1X:X*X t2write(X)X=100 t3read(X)X=100 t4ROLLBACK T 數(shù)據(jù)不一致性：數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務的隔離性由于并發(fā)操作破壞了事務的隔離性 T 并發(fā)控制就是要用并發(fā)控制就是要用正確的方式調度并發(fā)操作正確的方式調度并發(fā)操作，使

14、一個用戶，使一個用戶 事務的執(zhí)行不受其他事務的干擾，從而避免造成數(shù)據(jù)的不事務的執(zhí)行不受其他事務的干擾，從而避免造成數(shù)據(jù)的不 一致性一致性 并發(fā)控制的主要技術并發(fā)控制的主要技術 封鎖封鎖(Locking) 時間戳時間戳(Timestamp) 樂觀控制法樂觀控制法 商用的商用的DBMS一般都采用封鎖方法一般都采用封鎖方法 什么是封鎖 基本封鎖類型 鎖的相容矩陣 封鎖封鎖 封鎖是實現(xiàn)并發(fā)控制的一個非常重要的技術。封鎖是實現(xiàn)并發(fā)控制的一個非常重要的技術。 (1) 封鎖的定義及類型封鎖的定義及類型。 所謂封鎖就是事務在對某個數(shù)據(jù)對象（如表、所謂封鎖就是事務在對某個數(shù)據(jù)對象（如表、 記錄等）記錄等） 操作

15、之前，操作之前， 先向系統(tǒng)發(fā)出請求，先向系統(tǒng)發(fā)出請求， 對其加鎖。對其加鎖。 加鎖后事務就加鎖后事務就 對該數(shù)據(jù)對象有了一定的控制，對該數(shù)據(jù)對象有了一定的控制， 在事務釋放它的鎖之前，在事務釋放它的鎖之前， 其他的事務不能更新此數(shù)據(jù)對象。其他的事務不能更新此數(shù)據(jù)對象。 加鎖必須滿足一定的協(xié)議，加鎖必須滿足一定的協(xié)議， 即鎖協(xié)議（即鎖協(xié)議（Locking Protocol）。）。 基本的封鎖類型有兩種：基本的封鎖類型有兩種： 排它鎖（排它鎖（Exclusive Lock, 簡稱簡稱 X鎖）和共享鎖（鎖）和共享鎖（Share Locks, 簡稱簡稱S鎖）。鎖）。 排它鎖排它鎖(又稱寫鎖又稱寫鎖)：

16、 若事務對數(shù)據(jù)對象加上鎖，若事務對數(shù)據(jù)對象加上鎖， 則只允許讀取和修改，則只允許讀取和修改， 其他任何事務都不能再對其他任何事務都不能再對 加任何類型的鎖，加任何類型的鎖， 直至直至T釋放其鎖為止。釋放其鎖為止。 這就保證了其這就保證了其 他事務在釋放上的鎖之前不能再讀取和修改。他事務在釋放上的鎖之前不能再讀取和修改。 共享鎖（又稱為讀鎖）：共享鎖（又稱為讀鎖）： 若事務對數(shù)據(jù)對象加上若事務對數(shù)據(jù)對象加上 鎖，鎖， 則事務可以讀但不能修改，則事務可以讀但不能修改， 其他事物只能其他事物只能 再對加鎖，再對加鎖， 而不能加鎖，而不能加鎖， 直到釋放上的鎖。直到釋放上的鎖。 這就保證了其他事物可以

17、讀，這就保證了其他事物可以讀， 但在釋放上的鎖之但在釋放上的鎖之 前不能對做任何修改。前不能對做任何修改。 表 封鎖類型的相容矩陣 T1T2 Xlock A R(A)=16 Xlock A AA-1等待 W(A)=15等待 Commit等待 Unlock A等待 獲得Xlock A R(A)=15 AA-1 W(A)=14 Commit Unlock A 例：例： T1T2 Slock A Slock B R(A)=50 R(B)=100 求和=150 Xlock B 等待 等待 R(A)=50等待 R(B)=100等待 求和=150等待 Commit等待 Unlock A等待 Unlock

18、B等待 獲得XlockB R(B)=100 BB*2 W(B)=200 Commit Unlock B T1T2 Xlock C R(C)=100 CC*2 W(C)=200 Slock C 等待 ROLLBACK等待 (C恢復為100)等待 Unlock C等待 獲得Slock C R(C)=100 Commit C Unlock C 例例 封鎖技術可以有效地解決并行操作的一致性問題，但封鎖技術可以有效地解決并行操作的一致性問題，但 也帶來一些新的問題也帶來一些新的問題 死鎖死鎖 活鎖活鎖 T 事務事務T1封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R T 事務事務T2又請求封鎖又請求封鎖R，于是，于是T2等待。等

19、待。 T T3也請求封鎖也請求封鎖R，當，當T1釋放了釋放了R上的封鎖之后系統(tǒng)首先批上的封鎖之后系統(tǒng)首先批 準了準了T3的請求，的請求，T2仍然等待。仍然等待。 T T4又請求封鎖又請求封鎖R，當，當T3釋放了釋放了R上的封鎖之后系統(tǒng)又批準上的封鎖之后系統(tǒng)又批準 了了T4的請求的請求 T T2有可能永遠等待，這就是有可能永遠等待，這就是活鎖活鎖的情形的情形 避免活鎖：采用避免活鎖：采用先來先服務先來先服務的策略。的策略。 當多個事務請求封鎖同一數(shù)據(jù)對象時當多個事務請求封鎖同一數(shù)據(jù)對象時 按請求封鎖的先后次序對這些事務排隊按請求封鎖的先后次序對這些事務排隊 該數(shù)據(jù)對象上的鎖一旦釋放，首先批準申請

20、隊列中第該數(shù)據(jù)對象上的鎖一旦釋放，首先批準申請隊列中第 一個事務獲得鎖一個事務獲得鎖 T 事務事務T1封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R1 T T2封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R2 T T1又請求封鎖又請求封鎖R2，因，因T2已封鎖了已封鎖了R2，于是，于是T1等待等待T2釋放釋放 R2上的鎖上的鎖 T 接著接著T2又申請封鎖又申請封鎖R1，因，因T1已封鎖了已封鎖了R1，T2也只能等待也只能等待 T1釋放釋放R1上的鎖上的鎖 T 這樣這樣T1在等待在等待T2，而，而T2又在等待又在等待T1，T1和和T2兩個事務永兩個事務永 遠不遠不能結束，形成能結束，形成死鎖死鎖 T1T2 lock R1 Lock R2 Lo

21、ck R2. 等待 等待Lock R1 等待等待 等待等待 兩類方法 1. 預防死鎖 2. 死鎖的診斷與解除 T 產(chǎn)生死鎖的原因是兩個或多個事務都已封鎖了一些數(shù)據(jù)對 象，然后又都請求對已為其他事務封鎖的數(shù)據(jù)對象加鎖， 從而出現(xiàn)死等待。 T 預防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件 預防死鎖的方法 一次封鎖法 順序封鎖法 要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖， 否則就不能繼續(xù)執(zhí)行否則就不能繼續(xù)執(zhí)行 存在的問題存在的問題 降低系統(tǒng)并發(fā)度降低系統(tǒng)并發(fā)度 難于事先精確確定封鎖對象難于事先精確確定封鎖對象 順序封鎖法是預先對數(shù)據(jù)對象規(guī)定一個封鎖順序

22、，所有事 務都按這個順序實行封鎖。 順序封鎖法存在的問題 維護成本 數(shù)據(jù)庫系統(tǒng)中封鎖的數(shù)據(jù)對象極多，并且在不斷地變 化。 難以實現(xiàn)：很難事先確定每一個事務要封鎖哪些對象 結論結論 在操作系統(tǒng)中廣為采用的預防死鎖的策略并不很適合在操作系統(tǒng)中廣為采用的預防死鎖的策略并不很適合 數(shù)據(jù)庫的特點數(shù)據(jù)庫的特點 DBMS在解決死鎖的問題上更普遍采用的是診斷并解在解決死鎖的問題上更普遍采用的是診斷并解 除死鎖的方法除死鎖的方法 死鎖的診斷死鎖的診斷 n超時法超時法 n事務等待圖法事務等待圖法 T 如果一個事務的等待時間超過了規(guī)定的時限，就認為如果一個事務的等待時間超過了規(guī)定的時限，就認為 發(fā)生了死鎖發(fā)生了死鎖

23、 T 優(yōu)點：實現(xiàn)簡單優(yōu)點：實現(xiàn)簡單 T 缺點缺點 有可能誤判死鎖有可能誤判死鎖 時限若設置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn)時限若設置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn) 用事務等待圖動態(tài)反映所有事務的等待情況用事務等待圖動態(tài)反映所有事務的等待情況 事務等待圖是一個有向圖事務等待圖是一個有向圖G=(T，U) T為結點的集合，每個結點表示正運行的事務為結點的集合，每個結點表示正運行的事務 U為邊的集合，每條邊表示事務等待的情況為邊的集合，每條邊表示事務等待的情況 若若T1等待等待T2，則，則T1，T2之間劃一條有向邊，從之間劃一條有向邊，從T1指向指向 T2 事務等待圖 n 圖圖(a)中，事務中，事務T1

24、等待等待T2，T2等待等待T1，產(chǎn)生了死鎖，產(chǎn)生了死鎖 n 圖圖(b)中，事務中，事務T1等待等待T2，T2等待等待T3，T3等待等待T4，T4又等待又等待 T1，產(chǎn)生了死鎖，產(chǎn)生了死鎖 n 圖圖(b)中，事務中，事務T3可能還等待可能還等待T2，在大回路中又有小的回路，在大回路中又有小的回路 并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務 等待圖，檢測事務。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中等待圖，檢測事務。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中 出現(xiàn)了死鎖。出現(xiàn)了死鎖。 解除死鎖解除死鎖 選擇一個處理死鎖代價最小的事務，將其撤消選擇一個處理死鎖代價

25、最小的事務，將其撤消 釋放此事務持有的所有的鎖，使其它事務能繼續(xù)運行釋放此事務持有的所有的鎖，使其它事務能繼續(xù)運行 下去下去 DBMS對并發(fā)事務不同的調度可能會產(chǎn)生不同的結果 什么樣的調度是正確的？ 可串行化(Serializable)調度 n多個事務的并發(fā)執(zhí)行是正確的，當且僅當其結果與 按某一次序串行地執(zhí)行這些事務時的結果相同 可串行性(Serializability) 是并發(fā)事務正確調度的準則 一個給定的并發(fā)調度，當且僅當它是可串行化的， 才認為是正確調度 例現(xiàn)在有兩個事務，分別包含下列操作： 事務T1：讀B；A=B+1；寫回A 事務T2：讀A；B=A+1；寫回B 現(xiàn)給出對這兩個事務不同的

26、調度策略 T1T2 Slock B Y=R(B)=2 Unlock B Xlock A A=Y+1=3 W(A) Unlock A Slock A X=R(A)=3 Unlock A Xlock B B=X+1=4 W(B) Unlock B 串行調度(a) n 假設A、B的初值均為2。 n 按T1T2次序執(zhí)行結果 為A=3，B=4 n 串行調度策略,正確的調度 T1T2 Slock A X=R(A)=2 Unlock A Xlock B B=X+1=3 W(B) Unlock B Slock B Y=R(B)=3 Unlock B Xlock A A=Y+1=4 W(A) Unlock A

27、串行調度(b) n 假設A、B的初值均為2。 n T2T1次序執(zhí)行結果為B=3， A=4 n 串行調度策略,正確的調度 T1T2 Slock B Y=R(B)=2 Slock A X=R(A)=2 Unlock B Unlock A Xlock A A=Y+1=3 W(A) Xlock B B=X+1=3 W(B) Unlock A Unlock B 不可串行化的調度 n 執(zhí)行結果與(a)、(b)的結 果都不同 n 是錯誤的調度 T1T2 Slock B Y=R(B)=2 Unlock B Xlock A Slock A A=Y+1=3等待 W(A)等待 Unlock A等待 X=R(A)=3

28、 Unlock A Xlock B B=X+1=4 W(B) Unlock B 可串行化的調度 n 執(zhí)行結果與串行調度 (a)的執(zhí)行結果相同 n 是正確的調度 可串行化調度的充分條件充分條件 一個調度Sc在保證沖突操作沖突操作的次序不變的情況下，通 過交換兩個事務不沖突操作的次序得到另一個調度Sc， 如果Sc是串行的，稱調度Sc為沖突可串行化的調度 一個調度是沖突可串行化，一定是可串行化的調度 沖突操作沖突操作 沖突操作是指不同的事務對同一個數(shù)據(jù)的讀寫操作和寫寫 操作 Ri (x)與Wj(x) /* 事務Ti讀x，Tj寫x*/ Wi(x)與Wj(x) /* 事務Ti寫x，Tj寫x*/ 其他操作

29、是不沖突操作 不同事務的沖突操作和同一事務的兩個操作不能交換 (Swap) 例今有調度 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)交換： Sc2=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Sc2等價于一個串行調度T1，T2，Sc1沖突可串行化的調 度 沖突可串行化調度是可串行化調度的充分條件，不是必要 條件。還有不滿足沖突可串行化條件的可串行化

30、調度。 例有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的值 封鎖協(xié)議 運用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)則 何時申請封鎖 持鎖時間 何時釋放封鎖等 兩段封鎖協(xié)議(Two-Phase Locking，簡稱2PL)是最常用 的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是 可串行化

31、調度 兩段鎖協(xié)議 指所有事務必須分兩個階段對數(shù)據(jù)項加鎖和解鎖 n在對任何數(shù)據(jù)進行讀、寫操作之前，事務首先要獲得 對該數(shù)據(jù)的封鎖 n 在釋放一個封鎖之后，事務不再申請和獲得任何其他 封鎖 “兩段”鎖的含義 事務分為兩個階段 第一階段是獲得封鎖，也稱為擴展階段 事務可以申請獲得任何數(shù)據(jù)項上的任何類型的鎖， 但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務可以釋放任何數(shù)據(jù)項上的任何類型的鎖，但是 不能再申請任何鎖 例 事務Ti遵守兩段鎖協(xié)議，其封鎖序列是 ： Slock A Slock B Xlock C Unlock B Unlock A Unlock C； |擴展階段| 收縮階段 |

32、 事務Tj不遵守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B； 圖 可串行化調度 如圖中如圖中,(a)和和(b)都是可串行化的調度，都是可串行化的調度， 但但(a) 中中T 1和和T 2都是遵守兩段鎖協(xié)議，都是遵守兩段鎖協(xié)議， (b)中中T1和和T 2不是遵守兩段鎖協(xié)議。不是遵守兩段鎖協(xié)議。 事務遵守兩段鎖協(xié)議是可串行化調度的充分條件，而不是 必要條件。 若并發(fā)事務都遵守兩段鎖協(xié)議，則對這些事務的任何并發(fā) 調度策略都是可串行化的 若并發(fā)事務的一個調度是可串行化的，不一定所有事務都 符合兩段鎖協(xié)議 兩段鎖協(xié)議與防

33、止死鎖的一次封鎖法 一次封鎖法要求每個事務必須一次將所有要使用的數(shù) 據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法 遵守兩段鎖協(xié)議 但是兩段鎖協(xié)議并不要求事務必須一次將所有要使用 的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務可能發(fā) 生死鎖 例 遵守兩段鎖協(xié)議的事務發(fā)生死鎖 T1 Slock B R(B)=2 Xlock A 等待等待 等待等待 T2 Slock A R(A)=2 Xlock A 等待等待 遵守兩段鎖協(xié)議的事務可能發(fā)生死鎖 封鎖對象的大小稱為封鎖粒度(Granularity) 封鎖的對象：邏輯單元，物理單元 例：在關系數(shù)據(jù)庫中，封鎖對象： 邏輯單元: 屬性值、屬性值集合、元組、關系、

34、索引項、 整個索引、整個數(shù)據(jù)庫等 物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等 封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密切相關。 封鎖的粒度越大，數(shù)據(jù)庫所能夠封鎖的數(shù)據(jù)單元就越 少，并發(fā)度就越小，系統(tǒng)開銷也越??； 封鎖的粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越大 例 若封鎖粒度是數(shù)據(jù)頁，事務T1需要修改元組L1，則T1必 須對包含L1的整個數(shù)據(jù)頁A加鎖。如果T1對A加鎖后事務 T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。 如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖， 不需要互相等待，提高了系統(tǒng)的并行度。 事務T需要讀取整個表，若封鎖粒度是元組，T必須對表中 的每一個元組加

35、鎖，開銷極大 多粒度封鎖(Multiple Granularity Locking) 在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務選擇 選擇封鎖粒度 同時考慮封鎖開銷和并發(fā)度兩個因素，適當選擇封鎖粒 度 需要處理多個關系的大量元組的用戶事務：以數(shù)據(jù)庫 為封鎖單位 需要處理大量元組的用戶事務：以關系為封鎖單元 只處理少量元組的用戶事務：以元組為封鎖單位 多粒度樹 以樹形結構來表示多級封鎖粒度 根結點是整個數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度 葉結點表示最小的數(shù)據(jù)粒度 例：三級粒度樹。根結點為數(shù)據(jù)庫，數(shù)據(jù)庫的子結點為關系， 關系的子結點為元組。 數(shù)據(jù)庫數(shù)據(jù)庫 關系關系Rn 關系關系R1 元組元組元組元組元組

36、元組元組元組 三級粒度樹三級粒度樹 T 允許多粒度樹中的每個結點被獨立地加鎖允許多粒度樹中的每個結點被獨立地加鎖 T 對一個結點加鎖意味著這個結點的所有對一個結點加鎖意味著這個結點的所有后裔結點也被加以后裔結點也被加以 同樣類型的鎖同樣類型的鎖 T 在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式封鎖：在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式封鎖：顯式顯式 封鎖和隱式封鎖封鎖和隱式封鎖 顯式封鎖顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖直接加到數(shù)據(jù)對象上的封鎖 隱式封鎖隱式封鎖: 該數(shù)據(jù)對象沒有獨立加鎖，是由于其上級結點該數(shù)據(jù)對象沒有獨立加鎖，是由于其上級結點 加鎖而使該數(shù)據(jù)對象加上了鎖加鎖而使該數(shù)據(jù)對象加

37、上了鎖 顯式封鎖和隱式封鎖的效果是一樣的顯式封鎖和隱式封鎖的效果是一樣的 T 系統(tǒng)檢查封鎖沖突時系統(tǒng)檢查封鎖沖突時 n要檢查顯式封鎖要檢查顯式封鎖 n還要檢查隱式封鎖還要檢查隱式封鎖 例如事務例如事務T要對關系要對關系R1加加X鎖鎖 系統(tǒng)必須搜索其上級結點數(shù)據(jù)庫、關系系統(tǒng)必須搜索其上級結點數(shù)據(jù)庫、關系R1 還要搜索還要搜索R1的下級結點，即的下級結點，即R1中的每一個元組中的每一個元組 如果其中某一個數(shù)據(jù)對象已經(jīng)加了不相容鎖，則如果其中某一個數(shù)據(jù)對象已經(jīng)加了不相容鎖，則T必須必須 等待等待 T 對某個數(shù)據(jù)對象加鎖，系統(tǒng)要檢查對某個數(shù)據(jù)對象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對象該數(shù)據(jù)對象 有無顯式封鎖與之

38、沖突有無顯式封鎖與之沖突 所有上級結點所有上級結點 檢查本事務的顯式封鎖是否與該數(shù)據(jù)對象上的隱式檢查本事務的顯式封鎖是否與該數(shù)據(jù)對象上的隱式 封鎖沖突：封鎖沖突：(由上級結點已加的封鎖造成的）由上級結點已加的封鎖造成的） 所有下級結點所有下級結點 看上面的顯式封鎖是否與本事務的隱式封鎖看上面的顯式封鎖是否與本事務的隱式封鎖（將加將加 到下級結點的封鎖到下級結點的封鎖）沖突沖突 引進意向鎖（intention lock）目的 提高對某個數(shù)據(jù)對象加鎖時系統(tǒng)的檢查效率 T 如果對一個結點加意向鎖，則說明該結點的如果對一個結點加意向鎖，則說明該結點的下層結點下層結點正在正在 被加鎖被加鎖 T 對任一結

39、點加基本鎖，必須對任一結點加基本鎖，必須先先對它的上層結點對它的上層結點加意向鎖加意向鎖 T 例如，對任一元組加鎖時，必須先對它所在的數(shù)據(jù)庫和關例如，對任一元組加鎖時，必須先對它所在的數(shù)據(jù)庫和關 系加意向鎖系加意向鎖 意向共享鎖意向共享鎖(Intent Share Lock，簡稱，簡稱IS鎖鎖) 意向排它鎖意向排它鎖(Intent Exclusive Lock，簡稱，簡稱IX鎖鎖) 共享意向排它鎖共享意向排它鎖(Share Intent Exclusive Lock，簡稱，簡稱 SIX鎖鎖) IS鎖鎖 如果對一個數(shù)據(jù)對象加如果對一個數(shù)據(jù)對象加IS鎖，表示它的后裔結點擬鎖，表示它的后裔結點擬 （意向）加（意向）加S鎖。鎖。 例如：事