第11章數(shù)據(jù)庫系統(tǒng)概論

1、問題的產(chǎn)生問題的產(chǎn)生 l多用戶數(shù)據(jù)庫系統(tǒng)的存在 允許多個用戶同時使用的數(shù)據(jù)庫系統(tǒng) n飛機定票數(shù)據(jù)庫系統(tǒng) n銀行數(shù)據(jù)庫系統(tǒng) 特點：在同一時刻并發(fā)運行的事務(wù)數(shù)可達(dá)數(shù)百個 問題的產(chǎn)生（續(xù)）問題的產(chǎn)生（續(xù)） l不同的多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行 每個時刻只有一個事務(wù)運行，其他 事務(wù)必須等到這個事務(wù)結(jié)束以后方 能運行 不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù) 庫共享資源的特點 T1 T2 T3 事務(wù)的串行執(zhí)行方式 問題的產(chǎn)生（續(xù)）問題的產(chǎn)生（續(xù)） (2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機系統(tǒng)中，事務(wù)的并行執(zhí)行是這些并行事務(wù)的 并行操作輪流交叉運行 單處理機系統(tǒng)中的并行

2、事務(wù)并沒有真正地并行運行，但 能夠減少處理機的空閑時間，提高系統(tǒng)的效率 問題的產(chǎn)生（續(xù)）問題的產(chǎn)生（續(xù)） 事務(wù)的交叉并發(fā)執(zhí)行方式 問題的產(chǎn)生（續(xù)）問題的產(chǎn)生（續(xù)） (3)同時并發(fā)方式（simultaneous concurrency） 多處理機系統(tǒng)中，每個處理機可以運行一個事務(wù)， 多個處理機可以同時運行多個事務(wù)，實現(xiàn)多個事 務(wù)真正的并行運行 問題的產(chǎn)生（續(xù)）問題的產(chǎn)生（續(xù)） l事務(wù)并發(fā)執(zhí)行帶來的問題 會產(chǎn)生多個事務(wù)并發(fā)/同時存取同一數(shù)據(jù)的情況 可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)的隔 離性和數(shù)據(jù)庫的一致性 DBMS必須提供并發(fā)控制機制 并發(fā)控制機制是衡量一個DBMS性能的重要標(biāo)志之一 第十一

3、章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 11.1 并發(fā)控制概述并發(fā)控制概述 l并發(fā)控制的單位并發(fā)控制的單位事務(wù)事務(wù) l并發(fā)控制機制的任務(wù)并發(fā)控制機制的任務(wù) 對并發(fā)操作進(jìn)行正確調(diào)度正確調(diào)度 保證事務(wù)的隔離性事務(wù)的隔離性 保證數(shù)據(jù)庫的一致性數(shù)據(jù)庫的一致性 T1的修改被的修改被T2覆蓋了！覆蓋了！ 并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)） 并發(fā)操作帶來數(shù)據(jù)的不一致性實例并發(fā)操作帶來數(shù)據(jù)的不一致性實

4、例 例1飛機訂票系統(tǒng)中的一個活動序列 甲售票點(甲事務(wù))讀出某航班的機票余額A，設(shè)A=16； 乙售票點(乙事務(wù))讀出同一航班的機票余額A，也為16； 甲售票點賣出一張機票，修改余額AA-1，所以A為15，把A寫回數(shù)據(jù)庫； 乙售票點也賣出一張機票，修改余額AA-1，所以A為15，把A寫回數(shù)據(jù) 庫 n結(jié)果明明賣出兩張機票，數(shù)據(jù)庫中機票余額只減少1 并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)） l這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作引起的。 l在并發(fā)操作情況下，對甲、乙兩個事務(wù)的操作序列的調(diào)度是隨 機的。 l若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。 原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)

5、的修改 并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)） l并發(fā)操作帶來的數(shù)據(jù)不一致性并發(fā)操作帶來的數(shù)據(jù)不一致性 丟失修改（丟失修改（Lost Update） lW-W conflict 不可重復(fù)讀（不可重復(fù)讀（Non-repeatable Read） lR-W conflict 讀讀“臟臟”數(shù)據(jù)（數(shù)據(jù)（Dirty Read） lW-R conflict l記號 R(x)：讀數(shù)據(jù)x W(x)：寫數(shù)據(jù)x 1. 丟失修改丟失修改 l兩個事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提 交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被 丟失。 l上面飛機訂票例子就屬此類 丟失修改（續(xù)）丟失修改（續(xù)） T1T2 R(A)=

6、16 R(A)=16 AA-1 W(A)=15 AA-1 W(A)=15 2. 不可重復(fù)讀不可重復(fù)讀 l不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2 執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。 不可重復(fù)讀（續(xù)）不可重復(fù)讀（續(xù)） l不可重復(fù)讀包括三種情況： (1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修 改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時，得到與前一 次不同的值 不可重復(fù)讀（續(xù)）不可重復(fù)讀（續(xù)） nT1讀取B=100進(jìn)行運算 nT2讀取同一數(shù)據(jù)B，對其進(jìn) 行修改后將B=200寫回數(shù)據(jù) 庫。 nT1為了對讀取值校對重讀B， B已為200，與第一次讀取值 不一致 T1T2 R(A)=50 R(B)=10

7、0 求和=150 R(B)=100 BB*2 W(B)=200 R(A)=50 R(B)=200 求和=250 (驗算不對) 不可重復(fù)讀（續(xù)）不可重復(fù)讀（續(xù)） (2)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除 了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄 消失了 (3)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了 一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時也稱為幻影幻影現(xiàn)象（Phantom Row） 3. 讀讀“臟臟”數(shù)據(jù)數(shù)據(jù) 讀“臟”數(shù)據(jù)是指： n事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤 n事務(wù)T2讀取

8、同一數(shù)據(jù)后，T1由于某種原因被撤銷 n這時T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù) 就與數(shù)據(jù)庫中的數(shù)據(jù)不一致 nT2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù) 讀讀“臟臟”數(shù)據(jù)（續(xù)）數(shù)據(jù)（續(xù)） T1T2 R(C)=100 CC*2 W(C)=200 R(C)=200 ROLLBACK C恢復(fù)為100 n T1將C值修改為200， T2讀到C為200 n T1由于某種原因撤 銷，其修改作廢，C 恢復(fù)原值100 n 這時T2讀到的C為 200，與數(shù)據(jù)庫內(nèi)容 不一致，就是“臟” 數(shù)據(jù) 并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)） l數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔事務(wù)的隔 離性離性 l并發(fā)控制就是要

9、用正確的方式調(diào)度調(diào)度并發(fā)操作， 使一個用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾， 從而避免造成數(shù)據(jù)的不一致性 并發(fā)控制概述（續(xù)）并發(fā)控制概述（續(xù)） l并發(fā)控制的主要技術(shù) 封鎖封鎖(Locking) 時間戳(Timestamp)：將事務(wù)進(jìn)行全局排序， 使較早啟動的事務(wù)在沖突中擁有較高的優(yōu)先權(quán) 樂觀控制法：讓事務(wù)盡可能地執(zhí)行，在提交時 系統(tǒng)才進(jìn)行沖突檢測，如有沖突發(fā)生，重新啟 動該事務(wù) l商用的DBMS一般都采用封鎖方法 第十一章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段

10、鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 11.2 封鎖封鎖 l什么是封鎖 l基本封鎖類型 l鎖的相容矩陣 什么是封鎖什么是封鎖 封鎖就是事務(wù)T在對某個數(shù)據(jù)對象（例如表、 記錄等）操作之前，先向系統(tǒng)發(fā)出請求，對其 加鎖加鎖。加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的 控制控制，在事務(wù)T釋放它的鎖之前，其它事務(wù)不能 更新此數(shù)據(jù)對象。 基本封鎖類型基本封鎖類型 l一個事務(wù)對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控 制由封鎖的類型封鎖的類型決定。 l基本封鎖類型基本封鎖類型 排它鎖排它鎖（Exclusive Locks，簡記為X鎖鎖） 共享鎖共享鎖（Share Locks，簡記為S

11、鎖鎖） 排它鎖排它鎖 l排它鎖又稱為寫鎖寫鎖 l若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀讀 取和修改取和修改A，其它任何事務(wù)都不能再對不能再對A加任加任 何類型的鎖何類型的鎖，直到T釋放A上的鎖 l保證其他事務(wù)在T釋放A上的鎖之前不能再讀不能再讀 取和修改取和修改A 共享鎖共享鎖 l共享鎖又稱為讀鎖讀鎖 l若事務(wù)T對數(shù)據(jù)對象A加上S鎖，則事務(wù)T可以可以 讀讀A但不能修改但不能修改A，其它事務(wù)只能再對只能再對A加加S鎖，鎖， 而不能加而不能加X鎖鎖，直到T釋放A上的S鎖 l保證其他事務(wù)可以讀可以讀A，但在T釋放A上的S鎖 之前不能對不能對A做任何修改做任何修改 鎖的相容矩陣鎖的相容矩陣 Y=Y

12、es，相容的請求，相容的請求 N=No，不相容的請求，不相容的請求 T1 T2 XS- XNNY SNYY -YYY 鎖的相容矩陣（續(xù)）鎖的相容矩陣（續(xù)） 在鎖的相容矩陣中： l最左邊一列表示事務(wù)T1已經(jīng)獲得的數(shù)據(jù)對象上的鎖的類型， 其中橫線表示沒有加鎖。 l最上面一行表示另一事務(wù)T2對同一數(shù)據(jù)對象發(fā)出的封鎖請 求。 lT2的封鎖請求能否被滿足用矩陣中的Y和N表示 Y表示事務(wù)T2的封鎖要求與T1已持有的鎖相容，封鎖請求可 以滿足 N表示T2的封鎖請求與T1已持有的鎖沖突，T2的請求被拒絕 使用封鎖機制解決丟失修改問題使用封鎖機制解決丟失修改問題 T1T2 Xlock A R(A)=16 Xlo

13、ck A 等待 AA-1等待 W(A)=15等待 Commit等待 Unlock A等待 獲得Xlock A R(A)=15 AA-1 W(A)=14 Commit Unlock A n 事務(wù)T1在讀A進(jìn)行修改 之前先對先對A加加X鎖鎖 n 當(dāng)T2再請求對A加X鎖時 被拒絕 n T2只能等待T1釋放A上 的鎖后T2獲得對A的X鎖 n 這時T2讀到的A已經(jīng)是 T1更新過的值15 n T2按此新的A值進(jìn)行運 算，并將結(jié)果值A(chǔ)=14送 回到磁盤。避免了丟失 T1的更新。 沒有丟失修改沒有丟失修改 使用封鎖機制解決不可重復(fù)讀問題使用封鎖機制解決不可重復(fù)讀問題 T1T2 Slock A, Slock B

14、 R(A)=50, R(B)=100 求和=150 Xlock B 等待 R(A)=50, R(B)=100等待 求和=150等待 Commit等待 Unlock A, Unlock B等待 獲XlockB R(B)=100 BB*2 W(B)=200 Commit Unlock B n 事務(wù)T1在讀A，B之前，先對A，B加S 鎖 n 其他事務(wù)只能再對A，B加S鎖，而不能 加X鎖，即其他事務(wù)只能讀A，B，而 不能修改 n 當(dāng)T2為修改B而申請對B的X鎖時被拒 絕只能等待T1釋放B上的鎖 n T1為驗算再讀A，B，這時讀出的B仍 是100，求和結(jié)果仍為150，即可重復(fù)讀 n T1結(jié)束才釋放A，B

15、上的S鎖。T2才獲 得對B的X鎖 可重復(fù)讀可重復(fù)讀 使用封鎖機制解決讀使用封鎖機制解決讀“臟臟”數(shù)據(jù)問題數(shù)據(jù)問題 T1T2 Xlock C R(C)=100 CC*2 W(C)=200 Slock C 等待 ROLLBACK等待 (C恢復(fù)為100)等待 Unlock C等待 獲得Slock C R(C)=100 Commit C Unlock C n 事務(wù)T1在對C進(jìn)行修改之前，先對C加 X鎖，修改其值后寫回磁盤 n T2請求在C上加S鎖，因T1已在C上加 了X鎖，T2只能等待 n T1因某種原因被撤銷，C恢復(fù)為原值 100 n T1釋放C上的X鎖后T2獲得C上的S鎖， 讀C=100。避免了T

16、2讀“臟”數(shù)據(jù) 不讀不讀“臟臟”數(shù)據(jù)數(shù)據(jù) 第十一章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 11.3 活鎖和死鎖活鎖和死鎖 l封鎖技術(shù)可以有效地解決并行操作的一致性問 題，但也帶來一些新的問題 死鎖 活鎖 11.3.1 活鎖活鎖 l事務(wù)T1封鎖了數(shù)據(jù)R l事務(wù)T2又請求封鎖R，于是T2等待。 lT3也請求封鎖R，當(dāng)T1釋放了R上的封鎖之后系統(tǒng)首 先批準(zhǔn)了T3的請求，T2仍然等待。 lT4又請

17、求封鎖R，當(dāng)T3釋放了R上的封鎖之后系統(tǒng)又 批準(zhǔn)了T4的請求 lT2有可能永遠(yuǎn)等待，這就是活鎖活鎖的情形 活鎖（續(xù)）活鎖（續(xù)） 活鎖（續(xù)）活鎖（續(xù)） l避免活鎖：采用先來先服務(wù)先來先服務(wù)的策略 當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時 按請求封鎖的先后次序?qū)@些事務(wù)排隊 該數(shù)據(jù)對象上的鎖一旦釋放，首先批準(zhǔn)申請隊列中 第一個事務(wù)獲得鎖 11.3.2 死鎖死鎖 l事務(wù)T1封鎖了數(shù)據(jù)R1 lT2封鎖了數(shù)據(jù)R2 lT1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2 釋放R2上的鎖 l接著T2又申請封鎖R1，因T1已封鎖了R1，T2也只能 等待T1釋放R1上的鎖 l這樣T1在等待T2，而T2又在等待T1，

18、T1和T2兩個事 務(wù)永遠(yuǎn)不能結(jié)束，形成死鎖死鎖 死鎖（續(xù)）死鎖（續(xù)） T1T2 lock R1 Lock R2 Lock R2. 等待 等待Lock R1 等待等待 等待等待 解決死鎖的方法解決死鎖的方法 兩類方法 1. 預(yù)防死鎖預(yù)防死鎖 2. 死鎖的診斷與解除死鎖的診斷與解除 1. 死鎖的預(yù)防死鎖的預(yù)防 l產(chǎn)生死鎖的原因是兩個或多個事務(wù)都已封鎖了一些數(shù) 據(jù)對象，然后又都請求對已為其他事務(wù)封鎖的數(shù)據(jù)對 象加鎖，從而出現(xiàn)死等待。 l預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件破壞產(chǎn)生死鎖的條件 死鎖的預(yù)防（續(xù)）死鎖的預(yù)防（續(xù)） 預(yù)防死鎖的方法 l 一次封鎖法一次封鎖法 l 順序封鎖法順序封鎖法 (1)

19、一次封鎖法一次封鎖法 l要求每個事務(wù)必須一次性一次性將所有要使用的數(shù)據(jù)全 部加鎖，否則就不能繼續(xù)執(zhí)行 l存在的問題 降低系統(tǒng)并發(fā)度 l一次就將以后要用到的全部數(shù)據(jù)加鎖，勢必擴(kuò)大了封鎖的范圍，從而 降低了系統(tǒng)的并發(fā)度。 難于事先精確確定封鎖對象 (2)順序封鎖法順序封鎖法 l順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序封鎖順序，所 有事務(wù)都按這個順序?qū)嵭蟹怄i。 l順序封鎖法存在的問題 維護(hù)成本 l數(shù)據(jù)庫系統(tǒng)中封鎖的數(shù)據(jù)對象極多，并且在不斷地變化。 難以實現(xiàn)：很難事先確定每一個事務(wù)要封鎖哪些對 象 死鎖的預(yù)防（續(xù)）死鎖的預(yù)防（續(xù)） l結(jié)論 在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適 合數(shù)據(jù)庫的特點

20、 DBMS在解決死鎖的問題上更普遍采用的是診斷并診斷并 解除死鎖的方法解除死鎖的方法 2. 死鎖的診斷與解除死鎖的診斷與解除 l由DBMS的并發(fā)控制子系統(tǒng)定期檢測系統(tǒng)中是否 存在死鎖，一旦檢測到死鎖，就要設(shè)法解除。 l死鎖的診斷死鎖的診斷 n超時法超時法 n事務(wù)等待圖法事務(wù)等待圖法 (1) 超時法超時法 l如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為 發(fā)生了死鎖 l優(yōu)點：實現(xiàn)簡單 l缺點 有可能誤判死鎖 時限若設(shè)置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn) (2)等待圖法等待圖法 l用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況動態(tài)反映所有事務(wù)的等待情況 事務(wù)等待圖是一個有向圖有向圖G=(T，U) T為結(jié)點的集

21、合，每個結(jié)點表示正運行的事務(wù) U為邊的集合，每條邊表示事務(wù)等待的情況 若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2 等待圖法（續(xù)）等待圖法（續(xù)） 事務(wù)等待圖 n 圖(a)中，事務(wù)T1等待T2，T2等待T1，產(chǎn)生了死鎖 n 圖(b)中，事務(wù)T1等待T2，T2等待T3，T3等待T4，T4又等待 T1，產(chǎn)生了死鎖 n 圖(b)中，事務(wù)T3可能還等待T2，在大回路中又有小的回路 等待圖法（續(xù)）等待圖法（續(xù)） l并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生 成事務(wù)等待圖，檢測事務(wù)。如果發(fā)現(xiàn)圖中存在 回路回路，則表示系統(tǒng)中出現(xiàn)了死鎖。 死鎖的診斷與解除（續(xù)）死鎖的診斷與解除（續(xù)） l解除死鎖

22、選擇一個處理死鎖代價最小處理死鎖代價最小的事務(wù)，將其 撤消撤消 釋放釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能 繼續(xù)運行下去 第十一章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 lDBMS對并發(fā)事務(wù)不同的調(diào)度可能會產(chǎn)生不同 的結(jié)果 l什么樣的調(diào)度是正確的？ 11.4.1 可串行化調(diào)度可串行化調(diào)度 l可串行化(Serializable)調(diào)度 n多個事務(wù)

23、的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按 某一次序串行執(zhí)行這些事務(wù)時的結(jié)果相同某一次序串行執(zhí)行這些事務(wù)時的結(jié)果相同 l可串行性(Serializability) 是并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則 一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才 認(rèn)為是正確調(diào)度認(rèn)為是正確調(diào)度 可串行化調(diào)度（續(xù)）可串行化調(diào)度（續(xù)） 例現(xiàn)在有兩個事務(wù)，分別包含下列操作： 事務(wù)T1：讀B；A=B+1；寫回A 事務(wù)T2：讀A；B=A+1；寫回B 現(xiàn)給出對這兩個事務(wù)不同的調(diào)度策略 串行化調(diào)度串行化調(diào)度,正確的調(diào)度正確的調(diào)度 T1T2 Sloc

24、k 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 串行調(diào)度(a) n 假設(shè)A、B的初值均 為2。 n 按T1T2次序執(zhí)行 結(jié)果為A=3，B=4 n 串行調(diào)度策略,正 確的調(diào)度 串行化調(diào)度串行化調(diào)度,正確的調(diào)度正確的調(diào)度 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)

25、 Unlock A 串行調(diào)度(b) n 假設(shè)A、B的初值均為 2。 n T2T1次序執(zhí)行結(jié)果 為B=3，A=4 n 串行調(diào)度策略,正 確的調(diào)度 不可串行化調(diào)度，錯誤的調(diào)度不可串行化調(diào)度，錯誤的調(diào)度 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 不可串行化的調(diào)度 n 執(zhí)行結(jié)果與(a)、(b) 的結(jié)果都不同 n 是錯誤的調(diào)度 可串行化調(diào)度，正確的調(diào)度可串行化調(diào)度，正確的調(diào)度 T1T2 Slock B Y=R(B)

26、=2 Unlock B Xlock A Slock A A=Y+1=3等待 W(A)等待 Unlock A等待 X=R(A)=3 Unlock A Xlock B B=X+1=4 W(B) Unlock B 可串行化的調(diào)度 n 執(zhí)行結(jié)果與串行 調(diào)度(a)的執(zhí)行結(jié) 果相同 n 是正確的調(diào)度 11.4.2 沖突可串行化調(diào)度沖突可串行化調(diào)度 l可串行化調(diào)度的充分條件充分條件 一個調(diào)度Sc在保證沖突操作的次序不變保證沖突操作的次序不變的情況下，通過 交換兩個事務(wù)不沖突操作的次序交換兩個事務(wù)不沖突操作的次序得到另一個調(diào)度Sc， 如果Sc是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度 一個調(diào)度是沖突可串行化，一

27、定是可串行化的調(diào)度一個調(diào)度是沖突可串行化，一定是可串行化的調(diào)度 沖突可串行化調(diào)度（續(xù)）沖突可串行化調(diào)度（續(xù)） 沖突操作沖突操作 l沖突操作是指不同的事務(wù)對同一個數(shù)據(jù)的讀寫操作和寫 寫操作 Ri (x)與Wj(x) /* 事務(wù)Ti讀x，Tj寫x*/ Wi(x)與Wj(x) /* 事務(wù)Ti寫x，Tj寫x*/ l其他操作是不沖突操作 l不同事務(wù)的沖突操作和同一事務(wù)的兩個操作不能交換不同事務(wù)的沖突操作和同一事務(wù)的兩個操作不能交換 (Swap) 沖突可串行化調(diào)度（續(xù)）沖突可串行化調(diào)度（續(xù)） 例今有調(diào)度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) 把w2(A)與

28、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等價于一個串行調(diào)度T1，T2，Sc1沖突可串行化的調(diào)度 沖突可串行化調(diào)度（續(xù)）沖突可串行化調(diào)度（續(xù)） l沖突可串行化調(diào)度是可串行化調(diào)度的充分條件充分條件，不是必要 條件。還有不滿足沖突可串行化條件的可串行化調(diào)度。 例有3個事務(wù) T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X) 調(diào)度L1=W1(Y)W1(X)W2(Y)W2

29、(X) W3(X)是一個串行調(diào)度。 調(diào)度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖突可串行 化。但是調(diào)度L2是可串行化的，因為L2執(zhí)行的結(jié)果與調(diào)度L1 相同，Y的值都等于T2的值，X的值都等于T3的值 第十一章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 l封鎖協(xié)議 運用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)則 何時申請封鎖何時申請封鎖

30、持鎖時間持鎖時間 何時釋放封鎖等何時釋放封鎖等 l兩段封鎖協(xié)議(Two-Phase Locking，簡稱2PL)是最常用的 一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可使用兩段封鎖協(xié)議產(chǎn)生的是可 串行化調(diào)度串行化調(diào)度 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） l兩段鎖協(xié)議 指所有事務(wù)必須分兩個階段兩個階段對數(shù)據(jù)項加鎖和解鎖 n在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲 得對該數(shù)據(jù)的封鎖 n在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其 他封鎖 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） l“兩段”鎖的含義 事務(wù)分為兩個階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段第一階段是獲得封鎖，也稱為擴(kuò)展階段 事務(wù)可以申請

31、獲得任何數(shù)據(jù)項上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段第二階段是釋放封鎖，也稱為收縮階段 事務(wù)可以釋放任何數(shù)據(jù)項上的任何類型的鎖，但是不能再申請任何鎖 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） 例 事務(wù)Ti遵守兩段鎖協(xié)議，其封鎖序列是 ： Slock A Slock B Xlock C Unlock B Unlock A Unlock C； |擴(kuò)展階段| 收縮階段 | 事務(wù)Tj不遵守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B； 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） 事務(wù)T1事務(wù)T2 Slo

32、ck(A) R(A=260) 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 ) 遵守兩段鎖協(xié)議的可串行化調(diào)度遵守兩段鎖協(xié)議的可串行化調(diào)度 n 左圖的調(diào)度是遵守兩段鎖 協(xié)議的，因此一定是一個 可串行化調(diào)度。 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） l事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而事務(wù)遵守兩段鎖協(xié)

33、議是可串行化調(diào)度的充分條件，而 不是必要條件。不是必要條件。 l若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對這些事務(wù)的任何若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對這些事務(wù)的任何 并發(fā)調(diào)度策略都是可串行化的并發(fā)調(diào)度策略都是可串行化的 l若并發(fā)事務(wù)的一個調(diào)度是可串行化的，不一定所有事若并發(fā)事務(wù)的一個調(diào)度是可串行化的，不一定所有事 務(wù)都符合兩段鎖協(xié)議務(wù)都符合兩段鎖協(xié)議 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） l兩段鎖協(xié)議與防止死鎖的一次封鎖法 一次封鎖法要求每個事務(wù)必須一次將所有要使用的 數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封一次封 鎖法遵守兩段鎖協(xié)議鎖法遵守兩段鎖協(xié)議 但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使 用

34、的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可遵守兩段鎖協(xié)議的事務(wù)可 能發(fā)生死鎖能發(fā)生死鎖 兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議（續(xù)） 例 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖 T1 Slock B R(B)=2 Xlock A 等待等待 等待等待 T2 Slock A R(A)=2 Xlock A 等待等待 遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖 第十一章第十一章 并發(fā)控制并發(fā)控制 11.1 并發(fā)控制概述并發(fā)控制概述 11.2 封鎖封鎖 11.3 活鎖和死鎖活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議兩段鎖協(xié)議 11.6 封鎖的粒度封鎖的粒度 11.7 小結(jié)小結(jié) 封鎖粒度封鎖粒度 l

35、封鎖對象的大小稱為封鎖粒度封鎖對象的大小稱為封鎖粒度(Granularity) l封鎖的對象：邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫中，封鎖對象： 邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、索引項、 整個索引、整個數(shù)據(jù)庫等 物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等 選擇封鎖粒度原則選擇封鎖粒度原則 l封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密 切相關(guān)切相關(guān) 封鎖的粒度越大，數(shù)據(jù)庫所能夠封鎖的數(shù)據(jù)單元就 越少，并發(fā)度就越小，系統(tǒng)開銷也越??； 封鎖的粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越 大 選擇封鎖粒度的原則（續(xù)）選擇封鎖粒度的原則（續(xù)） 例 l若封鎖粒度

36、是數(shù)據(jù)頁，事務(wù)T1需要修改元組L1，則T1必須 對包含L1的整個數(shù)據(jù)頁A加鎖。如果T1對A加鎖后事務(wù)T2 要修改A中元組L2，則T2被迫等待，直到T1釋放A。 l如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖， 不需要互相等待，提高了系統(tǒng)的并行度。 l又如，事務(wù)T需要讀取整個表，若封鎖粒度是元組，T必須 對表中的每一個元組加鎖，開銷極大 選擇封鎖粒度的原則（續(xù)）選擇封鎖粒度的原則（續(xù)） l多粒度封鎖多粒度封鎖(Multiple Granularity Locking) 在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務(wù)選擇 l選擇封鎖粒度 同時考慮封鎖開銷封鎖開銷和并發(fā)度并發(fā)度兩個因素，適

37、當(dāng)選擇封鎖粒度 需要處理多個關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫為封鎖單位 需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元 只處理少量元組的用戶事務(wù)：以元組為封鎖單位 11.6.1 多粒度封鎖多粒度封鎖 l多粒度樹多粒度樹 以樹形結(jié)構(gòu)來表示多級封鎖粒度 根結(jié)點是整個數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度 葉結(jié)點表示最小的數(shù)據(jù)粒度 多粒度封鎖（續(xù)）多粒度封鎖（續(xù)） 例：三級粒度樹。根結(jié)點為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)點為 關(guān)系，關(guān)系的子結(jié)點為元組。 數(shù)據(jù)庫數(shù)據(jù)庫 關(guān)系關(guān)系Rn 關(guān)系關(guān)系R1 元組元組元組元組元組元組元組元組 三級粒度樹三級粒度樹 多粒度封鎖協(xié)議多粒度封鎖協(xié)議 l允許多粒度樹中的每個結(jié)點被獨立地加鎖 l對

38、一個結(jié)點加鎖意味著這個結(jié)點的所有后裔結(jié)對一個結(jié)點加鎖意味著這個結(jié)點的所有后裔結(jié) 點也被加以同樣類型的點也被加以同樣類型的鎖 l在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式 封鎖：顯式封鎖和隱式封鎖 顯式封鎖和隱式封鎖顯式封鎖和隱式封鎖 l顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖 l隱式封鎖: 該數(shù)據(jù)對象沒有獨立加鎖，是由于 其上級結(jié)點加鎖而使該數(shù)據(jù)對象加上了鎖 l顯式封鎖和隱式封鎖的效果是一樣的 顯式封鎖和隱式封鎖（續(xù)）顯式封鎖和隱式封鎖（續(xù)） l系統(tǒng)檢查封鎖沖突時 n要檢查顯式封鎖 n還要檢查隱式封鎖 l例如事務(wù)T要對關(guān)系R1加X鎖 系統(tǒng)必須搜索其上級結(jié)點數(shù)據(jù)庫、關(guān)系R1 還要搜索R1的下級結(jié)點，即

39、R1中的每一個元組 如果其中某一個數(shù)據(jù)對象已經(jīng)加了不相容鎖，則T必須等待 顯式封鎖和隱式封鎖（續(xù)）顯式封鎖和隱式封鎖（續(xù)） l對某個數(shù)據(jù)對象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對象 有無顯式封鎖與之沖突 所有上級結(jié)點 檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對象上的隱式封鎖沖突： (由上級結(jié)點已加的封鎖造成的） 所有下級結(jié)點 看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級結(jié)點 的封鎖）沖突 11.6.2 意向鎖意向鎖 l引進(jìn)意向鎖（intention lock）目的 提高對某個數(shù)據(jù)對象加鎖時系統(tǒng)的檢查效率 意向鎖意向鎖(續(xù)續(xù)) l如果對一個結(jié)點加意向鎖，則說明該結(jié)點的下層結(jié)點該結(jié)點的下層結(jié)點 正在被加鎖正在被加鎖 l對任一結(jié)點加基本鎖，必須先對它的上層結(jié)點加意向先對它的上層結(jié)點加意向 鎖鎖 l例如，對任一元組加鎖時，必須先對它所在的數(shù)據(jù)庫 和關(guān)系加意向鎖 常用意向鎖常用意向鎖 l意向共享鎖(Intent Share Lock，簡稱IS鎖) l意向排它鎖(Intent Exclusive Lock，簡稱IX鎖) l共享意向排它鎖(Share Intent Exclusive Lock，