第十一章：并發(fā)控制-數(shù)據(jù)庫系統(tǒng)概論課件

1、數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第十一章 并發(fā)控制An Introduction to Database SystemAn Introduction to Database Sy問題的產(chǎn)生多用戶數(shù)據(jù)庫系統(tǒng)的存在 允許多個用戶同時使用的數(shù)據(jù)庫系統(tǒng)飛機(jī)定票數(shù)據(jù)庫系統(tǒng)銀行數(shù)據(jù)庫系統(tǒng) 特點(diǎn)：在同一時刻并發(fā)運(yùn)行的事務(wù)數(shù)可達(dá)數(shù)百個 An Introduction to Database System問題的產(chǎn)生多用戶數(shù)據(jù)庫系統(tǒng)的存在An Introductio問題的產(chǎn)生（續(xù)）不同的多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行每個時刻只有一個事務(wù)運(yùn)行，其他事務(wù)必須等到這

2、個事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源的特點(diǎn)T1T2T3事務(wù)的串行執(zhí)行方式An Introduction to Database System問題的產(chǎn)生（續(xù)）不同的多事務(wù)執(zhí)行方式 T1T2T3事務(wù)的串行問題的產(chǎn)生（續(xù)）(2)交叉并發(fā)方式（Interleaved Concurrency）在單處理機(jī)系統(tǒng)中，事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運(yùn)行單處理機(jī)系統(tǒng)中的并行事務(wù)并沒有真正地并行運(yùn)行，但能夠減少處理機(jī)的空閑時間，提高系統(tǒng)的效率An Introduction to Database System問題的產(chǎn)生（續(xù)）(2)交叉并發(fā)方式（Interleaved 問題的

3、產(chǎn)生（續(xù)）事務(wù)的交叉并發(fā)執(zhí)行方式An Introduction to Database System問題的產(chǎn)生（續(xù)）事務(wù)的交叉并發(fā)執(zhí)行方式An Introduc問題的產(chǎn)生（續(xù)） (3)同時并發(fā)方式（simultaneous concurrency）多處理機(jī)系統(tǒng)中，每個處理機(jī)可以運(yùn)行一個事務(wù)，多個處理機(jī)可以同時運(yùn)行多個事務(wù)，實(shí)現(xiàn)多個事務(wù)真正的并行運(yùn)行An Introduction to Database System問題的產(chǎn)生（續(xù)） (3)同時并發(fā)方式（simultaneou問題的產(chǎn)生（續(xù)）事務(wù)并發(fā)執(zhí)行帶來的問題會產(chǎn)生多個事務(wù)同時存取同一數(shù)據(jù)的情況 可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)一致性和

4、數(shù)據(jù)庫的一致性An Introduction to Database System問題的產(chǎn)生（續(xù)）事務(wù)并發(fā)執(zhí)行帶來的問題An Introduc第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro11.1 并發(fā)控制概述并發(fā)控制機(jī)制的任務(wù)對并發(fā)操作進(jìn)行正確調(diào)度保證事務(wù)的隔離性保證數(shù)據(jù)庫的一致性An Introduction to Database System11.1 并發(fā)

5、控制概述并發(fā)控制機(jī)制的任務(wù)An IntrodT1的修改被T2覆蓋了！并發(fā)控制概述（續(xù)）并發(fā)操作帶來數(shù)據(jù)的不一致性實(shí)例例1飛機(jī)訂票系統(tǒng)中的一個活動序列 甲售票點(diǎn)(甲事務(wù))讀出某航班的機(jī)票余額A，設(shè)A=16； 乙售票點(diǎn)(乙事務(wù))讀出同一航班的機(jī)票余額A，也為16； 甲售票點(diǎn)賣出一張機(jī)票，修改余額AA-1，所以A為15，把A寫回?cái)?shù)據(jù)庫； 乙售票點(diǎn)也賣出一張機(jī)票，修改余額AA-1，所以A為15，把A寫回?cái)?shù)據(jù)庫 結(jié)果明明賣出兩張機(jī)票，數(shù)據(jù)庫中機(jī)票余額只減少1 An Introduction to Database SystemT1的修改被T2覆蓋了！并發(fā)控制概述（續(xù)）并發(fā)操作帶來數(shù)據(jù)的并發(fā)控制概述（續(xù)）

6、這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作引起的。在并發(fā)操作情況下，對甲、乙兩個事務(wù)的操作序列的調(diào)度是隨機(jī)的。若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)的修改An Introduction to Database System并發(fā)控制概述（續(xù)）這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作并發(fā)控制概述（續(xù)）并發(fā)操作帶來的數(shù)據(jù)不一致性丟失修改（Lost Update）不可重復(fù)讀（Non-repeatable Read）讀“臟”數(shù)據(jù)（Dirty Read）記號R(x):讀數(shù)據(jù)xW(x):寫數(shù)據(jù)x An Introduction to Database

7、System并發(fā)控制概述（續(xù)）并發(fā)操作帶來的數(shù)據(jù)不一致性An Intro1. 丟失修改兩個事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失。上面飛機(jī)訂票例子就屬此類 An Introduction to Database System1. 丟失修改兩個事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提丟失修改（續(xù)）丟失修改An Introduction to Database System丟失修改（續(xù)）丟失修改An Introduction to 2. 不可重復(fù)讀不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2 執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。An In

8、troduction to Database System2. 不可重復(fù)讀不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2A不可重復(fù)讀（續(xù)）不可重復(fù)讀包括三種情況：(1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時，得到與前一次不同的值 An Introduction to Database System不可重復(fù)讀（續(xù)）不可重復(fù)讀包括三種情況：An Introdu不可重復(fù)讀（續(xù)）T1讀取B=100進(jìn)行運(yùn)算T2讀取同一數(shù)據(jù)B，對其進(jìn)行修改后將B=200寫回?cái)?shù)據(jù)庫。T1為了對讀取值校對重讀B，B已為200，與第一次讀取值不一致 不可重復(fù)讀 例如：An Introduction

9、to Database System不可重復(fù)讀（續(xù)）T1讀取B=100進(jìn)行運(yùn)算不可重復(fù)讀 例如：不可重復(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）An Introduction to Database System不可重復(fù)讀（續(xù)）(2)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了某些3. 讀“臟”數(shù)據(jù) 讀“臟”數(shù)據(jù)是

10、指：事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷這時T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù) An Introduction to Database System3. 讀“臟”數(shù)據(jù) 讀“臟”數(shù)據(jù)是指：An Introd讀“臟”數(shù)據(jù)（續(xù)）例如讀“臟”數(shù)據(jù) T1將C值修改為200，T2讀到C為200T1由于某種原因撤銷，其修改作廢，C恢復(fù)原值100這時T2讀到的C為200，與數(shù)據(jù)庫內(nèi)容不一致，就是“臟”數(shù)據(jù) An Introduction to Database System讀“臟”數(shù)據(jù)（續(xù)

11、）例如讀“臟”數(shù)據(jù) T1將C值修改為200，并發(fā)控制概述（續(xù)）數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離性并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使一個用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性 An Introduction to Database System并發(fā)控制概述（續(xù)）數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離并發(fā)控制概述（續(xù)）并發(fā)控制的主要技術(shù)有封鎖(Locking)時間戳(Timestamp)樂觀控制法商用的DBMS一般都采用封鎖方法 An Introduction to Database System并發(fā)控制概述（續(xù)）并發(fā)控制的主要技術(shù)An Introduc

12、t第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro11.2 封鎖什么是封鎖基本封鎖類型鎖的相容矩陣An Introduction to Database System11.2 封鎖什么是封鎖An Introduction t什么是封鎖封鎖就是事務(wù)T在對某個數(shù)據(jù)對象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請求，對其加鎖加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的控制，在事務(wù)T

13、釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對象。An Introduction to Database System什么是封鎖封鎖就是事務(wù)T在對某個數(shù)據(jù)對象（例如表、記錄等）操基本封鎖類型一個事務(wù)對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控制由封鎖的類型決定?；痉怄i類型排它鎖（Exclusive Locks，簡記為X鎖）共享鎖（Share Locks，簡記為S鎖）An Introduction to Database System基本封鎖類型一個事務(wù)對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控制排它鎖排它鎖又稱為寫鎖若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對A加任何類型的

14、鎖，直到T釋放A上的鎖保證其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A An Introduction to Database System排它鎖排它鎖又稱為寫鎖An Introduction to 共享鎖共享鎖又稱為讀鎖若事務(wù)T對數(shù)據(jù)對象A加上S鎖，則其它事務(wù)只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖保證其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對A做任何修改 An Introduction to Database System共享鎖共享鎖又稱為讀鎖An Introduction to 鎖的相容矩陣Y=Yes，相容的請求N=No，不相容的請求 T1 T2XS-XNNYSNYY

15、-YYYAn Introduction to Database System鎖的相容矩陣Y=Yes，相容的請求 T1 鎖的相容矩陣（續(xù)）在鎖的相容矩陣中：最左邊一列表示事務(wù)T1已經(jīng)獲得的數(shù)據(jù)對象上的鎖的類型，其中橫線表示沒有加鎖。最上面一行表示另一事務(wù)T2對同一數(shù)據(jù)對象發(fā)出的封鎖請求。T2的封鎖請求能否被滿足用矩陣中的Y和N表示Y表示事務(wù)T2的封鎖要求與T1已持有的鎖相容，封鎖請求可以滿足N表示T2的封鎖請求與T1已持有的鎖沖突，T2的請求被拒絕An Introduction to Database System鎖的相容矩陣（續(xù)）在鎖的相容矩陣中：An Introduct使用封鎖機(jī)制解決丟失修

16、改問題例：事務(wù)T1在讀A進(jìn)行修改之前先對A加X鎖當(dāng)T2再請求對A加X鎖時被拒絕T2只能等待T1釋放A上的鎖后T2獲得對A的X鎖這時T2讀到的A已經(jīng)是T1更新過的值15T2按此新的A值進(jìn)行運(yùn)算，并將結(jié)果值A(chǔ)=14送回到磁盤。避免了丟失T1的更新。沒有丟失修改An Introduction to Database System使用封鎖機(jī)制解決丟失修改問題例：事務(wù)T1在讀A進(jìn)行修改之前先使用封鎖機(jī)制解決不可重復(fù)讀問題事務(wù)T1在讀A，B之前，先對A，B加S鎖其他事務(wù)只能再對A，B加S鎖，而不能加X鎖，即其他事務(wù)只能讀A，B，而不能修改當(dāng)T2為修改B而申請對B的X鎖時被拒絕只能等待T1釋放B上的鎖T1為

17、驗(yàn)算再讀A，B，這時讀出的B仍是100，求和結(jié)果仍為150，即可重復(fù)讀T1結(jié)束才釋放A，B上的S鎖。T2才獲得對B的X鎖 可重復(fù)讀An Introduction to Database System使用封鎖機(jī)制解決不可重復(fù)讀問題事務(wù)T1在讀A，B之前，先對A使用封鎖機(jī)制解決讀“臟”數(shù)據(jù)問題例事務(wù)T1在對C進(jìn)行修改之前，先對C加X鎖，修改其值后寫回磁盤T2請求在C上加S鎖，因T1已在C上加了X鎖，T2只能等待T1因某種原因被撤銷，C恢復(fù)為原值100T1釋放C上的X鎖后T2獲得C上的S鎖，讀C=100。避免了T2讀“臟”數(shù)據(jù)不讀“臟”數(shù)據(jù) An Introduction to Database S

18、ystem使用封鎖機(jī)制解決讀“臟”數(shù)據(jù)問題例事務(wù)T1在對C進(jìn)行修改之前第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro11.3 活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題死鎖活鎖An Introduction to Database System11.3 活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性11.3.1 活鎖事務(wù)T1封鎖了

19、數(shù)據(jù)R事務(wù)T2又請求封鎖R，于是T2等待。T3也請求封鎖R，當(dāng)T1釋放了R上的封鎖之后系統(tǒng)首先批準(zhǔn)了T3的請求，T2仍然等待。T4又請求封鎖R，當(dāng)T3釋放了R上的封鎖之后系統(tǒng)又批準(zhǔn)了T4的請求T2有可能永遠(yuǎn)等待，這就是活鎖的情形 An Introduction to Database System11.3.1 活鎖事務(wù)T1封鎖了數(shù)據(jù)RAn Introduc活鎖（續(xù)）活 鎖An Introduction to Database System活鎖（續(xù)）活 鎖An Introduction to Da活鎖（續(xù)）避免活鎖：采用先來先服務(wù)的策略當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時按請求封鎖的先后次序?qū)@些事

20、務(wù)排隊(duì)該數(shù)據(jù)對象上的鎖一旦釋放，首先批準(zhǔn)申請隊(duì)列中第一個事務(wù)獲得鎖An Introduction to Database System活鎖（續(xù)）避免活鎖：采用先來先服務(wù)的策略An Introdu11.3.2 死鎖事務(wù)T1封鎖了數(shù)據(jù)R1T2封鎖了數(shù)據(jù)R2T1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖接著T2又申請封鎖R1，因T1已封鎖了R1，T2也只能等待T1釋放R1上的鎖這樣T1在等待T2，而T2又在等待T1，T1和T2兩個事務(wù)永遠(yuǎn)不能結(jié)束，形成死鎖 An Introduction to Database System11.3.2 死鎖事務(wù)T1封鎖了數(shù)據(jù)R1An Int

21、rod死鎖（續(xù)）死 鎖An Introduction to Database System死鎖（續(xù)）死 鎖An Introduction to 解決死鎖的方法兩類方法1. 預(yù)防死鎖2. 死鎖的診斷與解除An Introduction to Database System解決死鎖的方法兩類方法An Introduction to 1. 死鎖的預(yù)防產(chǎn)生死鎖的原因是兩個或多個事務(wù)都已封鎖了一些數(shù)據(jù)對象，然后又都請求對已被其他事務(wù)封鎖的數(shù)據(jù)對象加鎖，從而出現(xiàn)死等待。預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件An Introduction to Database System1. 死鎖的預(yù)防產(chǎn)生死鎖的原因是

22、兩個或多個事務(wù)都已封鎖了一些死鎖的預(yù)防（續(xù)）預(yù)防死鎖的方法 一次封鎖法 順序封鎖法An Introduction to Database System死鎖的預(yù)防（續(xù)）預(yù)防死鎖的方法An Introduction(1)一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行存在的問題降低系統(tǒng)并發(fā)度難于事先精確確定封鎖對象An Introduction to Database System(1)一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加(2)順序封鎖法順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務(wù)都按這個順序?qū)嵭蟹怄i。順序封鎖法存在的問題維護(hù)成本 數(shù)據(jù)庫系統(tǒng)中

23、封鎖的數(shù)據(jù)對象極多，并且在不斷地變化。難以實(shí)現(xiàn)：很難事先確定每一個事務(wù)要封鎖哪些對象 T1T2D3D4事物T2只能封D1，D2的鎖，不能封D4An Introduction to Database System(2)順序封鎖法順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，死鎖的預(yù)防（續(xù)）結(jié)論在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫的特點(diǎn)DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法An Introduction to Database System死鎖的預(yù)防（續(xù)）結(jié)論An Introduction to D2. 死鎖的診斷與解除死鎖的診斷超時法事務(wù)等待圖法 An Int

24、roduction to Database System2. 死鎖的診斷與解除死鎖的診斷An Introductio(1) 超時法如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為發(fā)生了死鎖優(yōu)點(diǎn)：實(shí)現(xiàn)簡單缺點(diǎn)有可能誤判死鎖時限若設(shè)置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn)An Introduction to Database System(1) 超時法如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為(2)等待圖法用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況事務(wù)等待圖是一個有向圖G=(T，U)T為結(jié)點(diǎn)的集合，每個結(jié)點(diǎn)表示正運(yùn)行的事務(wù)U為邊的集合，每條邊表示事務(wù)等待的情況若T1等待T2，則T1，T2之間劃一條有向邊，從

25、T1指向T2An Introduction to Database System(2)等待圖法用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況An I等待圖法（續(xù)）事務(wù)等待圖圖(a)中，事務(wù)T1等待T2，T2等待T1，產(chǎn)生了死鎖圖(b)中，事務(wù)T1等待T2，T2等待T3，T3等待T4，T4又等待T1，產(chǎn)生了死鎖 圖(b)中，事務(wù)T3可能還等待T2，在大回路中又有小的回路 An Introduction to Database System等待圖法（續(xù)）事務(wù)等待圖圖(a)中，事務(wù)T1等待T2，T2等等待圖法（續(xù)）并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等待圖，檢測事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系

26、統(tǒng)中出現(xiàn)了死鎖。An Introduction to Database System等待圖法（續(xù)）并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)死鎖的診斷與解除（續(xù)）解除死鎖選擇一個處理死鎖代價(jià)最小的事務(wù)，將其撤消釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去An Introduction to Database System死鎖的診斷與解除（續(xù)）解除死鎖An Introduction第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Databas

27、e System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro11.4 并發(fā)調(diào)度的可串行性DBMS對并發(fā)事務(wù)不同的調(diào)度可能會產(chǎn)生不同的結(jié)果什么樣的調(diào)度是正確的？An Introduction to Database System11.4 并發(fā)調(diào)度的可串行性DBMS對并發(fā)事務(wù)不同的調(diào)度可11.4.1 可串行化調(diào)度可串行化(Serializable)調(diào)度多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行這些事務(wù)時的結(jié)果相同可串行性(Serializability)是并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度 An Introducti

28、on to Database System11.4.1 可串行化調(diào)度可串行化(Serializable可串行化調(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)度策略 An Introduction to Database System可串行化調(diào)度（續(xù)）例現(xiàn)在有兩個事務(wù)，分別包含下列操作：A串行化調(diào)度,正確的調(diào)度串行調(diào)度(a)假設(shè)A、B的初值均為2。按T1T2次序執(zhí)行結(jié)果為A=3，B=4 串行調(diào)度策略,正確的調(diào)度 An Introduction to Database System串行化調(diào)度,正確的調(diào)度串

29、行調(diào)度(a)假設(shè)A、B的初值均為2。串行化調(diào)度,正確的調(diào)度串行調(diào)度(b)假設(shè)A、B的初值均為2。T2T1次序執(zhí)行結(jié)果為B=3，A=4 串行調(diào)度策略,正確的調(diào)度 An Introduction to Database System串行化調(diào)度,正確的調(diào)度串行調(diào)度(b)假設(shè)A、B的初值均為2。不可串行化調(diào)度，錯誤的調(diào)度不可串行化的調(diào)度 執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同是錯誤的調(diào)度 An Introduction to Database System不可串行化調(diào)度，錯誤的調(diào)度不可串行化的調(diào)度 執(zhí)行結(jié)果與(a)可串行化調(diào)度，正確的調(diào)度可串行化的調(diào)度 執(zhí)行結(jié)果與串行調(diào)度(a)的執(zhí)行結(jié)果相同是正確的調(diào)度

30、 An Introduction to Database System可串行化調(diào)度，正確的調(diào)度可串行化的調(diào)度 執(zhí)行結(jié)果與串行調(diào)度(11.4.2 沖突可串行化調(diào)度可串行化調(diào)度的充分條件一個調(diào)度Sc在保證沖突操作的次序不變的情況下，通過交換兩個事務(wù)不沖突操作的次序得到另一個調(diào)度Sc，如果Sc是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度一個調(diào)度是沖突可串行化，一定是可串行化的調(diào)度An Introduction to Database System11.4.2 沖突可串行化調(diào)度可串行化調(diào)度的充分條件An 沖突可串行化調(diào)度（續(xù)）沖突操作沖突操作是指不同的事務(wù)對同一個數(shù)據(jù)的讀寫操作和寫寫操作Ri (x)與Wj

31、(x) /* 事務(wù)Ti讀x，Tj寫x*/Wi(x)與Wj(x) /* 事務(wù)Ti寫x，Tj寫x*/其他操作是不沖突操作不同事務(wù)的沖突操作不能交換(Swap) An Introduction to Database System沖突可串行化調(diào)度（續(xù)）沖突操作An Introduction沖突可串行化調(diào)度（續(xù)）例今有調(diào)度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)交換： Sc2r1(A)w1(A

32、)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)Sc2等價(jià)于一個串行調(diào)度T1，T2，Sc1沖突可串行化的調(diào)度An Introduction to Database System沖突可串行化調(diào)度（續(xù)）例今有調(diào)度Sc1=r1(A)w1(沖突可串行化調(diào)度（續(xù)）沖突可串行化調(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(X) W3(X)是一個串行調(diào)度。調(diào)度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖

33、突可串行化。但是調(diào)度L2是可串行化的，因?yàn)長2執(zhí)行的結(jié)果與調(diào)度L1相同，Y的值都等于T2的值，X的值都等于T3的值 An Introduction to Database System沖突可串行化調(diào)度（續(xù)）沖突可串行化調(diào)度是可串行化調(diào)度的充分條第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro11.5 兩段鎖協(xié)議封鎖協(xié)議 運(yùn)用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)

34、則 何時申請封鎖持鎖時間何時釋放封鎖等兩段封鎖協(xié)議(Two-Phase Locking，簡稱2PL)是最常用的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可串行化調(diào)度An Introduction to Database System11.5 兩段鎖協(xié)議封鎖協(xié)議An Introduction兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議 指所有事務(wù)必須分兩個階段對數(shù)據(jù)項(xiàng)加鎖和解鎖 在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對該數(shù)據(jù)的封鎖 在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其他封鎖An Introduction to Database System兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議An Introducti

35、on t兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義事務(wù)分為兩個階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段事務(wù)可以申請獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請任何鎖 An Introduction to Database System兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義An Introductio兩段鎖協(xié)議（續(xù)）例事務(wù)Ti遵守兩段鎖協(xié)議，其封鎖序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock C；|擴(kuò)展階段| 收縮階段 |事務(wù)Tj不遵守兩段鎖協(xié)議，其封鎖序

36、列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B；An Introduction to Database System兩段鎖協(xié)議（續(xù)）例An Introduction to Da兩段鎖協(xié)議（續(xù)）遵守兩段鎖協(xié)議的可串行化調(diào)度左圖的調(diào)度是遵守兩段鎖協(xié)議的，因此一定是一個可串行化調(diào)度。An Introduction to Database System兩段鎖協(xié)議（續(xù)）遵守兩段鎖協(xié)議的可串行化調(diào)度左圖的調(diào)度是遵守兩段鎖協(xié)議（續(xù)）事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對這些事務(wù)的任何并發(fā)調(diào)度策

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

38、（續(xù)）例 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖T1Slock BR(B)=2Xlock A等待等待T2Slock AR(A)=2Xlock A等待遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖 An Introduction to Database System兩段鎖協(xié)議（續(xù)）例 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖T1T第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述An Intro封鎖粒度封鎖對象的大小稱為

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

40、選擇封鎖粒度原則封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密切相選擇封鎖粒度的原則（續(xù)）例若封鎖粒度是數(shù)據(jù)頁，事務(wù)T1需要修改元組L1，則T1必須對包含L1的整個數(shù)據(jù)頁A加鎖。如果T1對A加鎖后事務(wù)T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖，不需要互相等待，提高了系統(tǒng)的并行度。又如，事務(wù)T需要讀取整個表，若封鎖粒度是元組，T必須對表中的每一個元組加鎖，開銷極大 An Introduction to Database System選擇封鎖粒度的原則（續(xù)）例An Introduction t選擇封鎖粒度的原則（續(xù)）多粒度封鎖(Mul

41、tiple Granularity Locking) 在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務(wù)選擇選擇封鎖粒度 同時考慮封鎖開銷和并發(fā)度兩個因素，適當(dāng)選擇封鎖粒度需要處理多個關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫為封鎖單位需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元只處理少量元組的用戶事務(wù)：以元組為封鎖單位An Introduction to Database System選擇封鎖粒度的原則（續(xù)）多粒度封鎖(Multiple Gra11.6.1 多粒度封鎖多粒度樹以樹形結(jié)構(gòu)來表示多級封鎖粒度根結(jié)點(diǎn)是整個數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度 An Introduction to D

42、atabase System11.6.1 多粒度封鎖多粒度樹An Introductio多粒度封鎖（續(xù)）例：三級粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。數(shù)據(jù)庫關(guān)系Rn關(guān)系R1元組元組元組元組 三級粒度樹An Introduction to Database System多粒度封鎖（續(xù)）例：三級粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)多粒度封鎖協(xié)議允許多粒度樹中的每個結(jié)點(diǎn)被獨(dú)立地加鎖對一個結(jié)點(diǎn)加鎖意味著這個結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的鎖在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖An Introduction to Database System

43、多粒度封鎖協(xié)議允許多粒度樹中的每個結(jié)點(diǎn)被獨(dú)立地加鎖An In顯式封鎖和隱式封鎖顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖隱式封鎖: 該數(shù)據(jù)對象沒有獨(dú)立加鎖，是由于其上級結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對象加上了鎖顯式封鎖和隱式封鎖的效果是一樣的An Introduction to Database System顯式封鎖和隱式封鎖顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖An 顯式封鎖和隱式封鎖（續(xù)）系統(tǒng)檢查封鎖沖突時要檢查顯式封鎖還要檢查隱式封鎖例如事務(wù)T要對關(guān)系R1加X鎖系統(tǒng)必須搜索其上級結(jié)點(diǎn)數(shù)據(jù)庫、關(guān)系R1還要搜索R1的下級結(jié)點(diǎn)，即R1中的每一個元組如果其中某一個數(shù)據(jù)對象已經(jīng)加了不相容鎖，則T必須等待 An Int

44、roduction to Database System顯式封鎖和隱式封鎖（續(xù)）系統(tǒng)檢查封鎖沖突時An Introd顯式封鎖和隱式封鎖（續(xù)）對某個數(shù)據(jù)對象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對象有無顯式封鎖與之沖突 所有上級結(jié)點(diǎn)檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對象上的隱式封鎖沖突：(由上級結(jié)點(diǎn)已加的封鎖造成的）所有下級結(jié)點(diǎn)看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級結(jié)點(diǎn)的封鎖）沖突An Introduction to Database System顯式封鎖和隱式封鎖（續(xù)）對某個數(shù)據(jù)對象加鎖，系統(tǒng)要檢查An 11.6.2 意向鎖引進(jìn)意向鎖（intention lock）目的提高對某個數(shù)據(jù)對象加鎖時系統(tǒng)

45、的檢查效率An Introduction to Database System11.6.2 意向鎖引進(jìn)意向鎖（intention lock意向鎖(續(xù))如果對一個結(jié)點(diǎn)加意向鎖，則說明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖對任一結(jié)點(diǎn)加基本鎖，必須先對它的上層結(jié)點(diǎn)加意向鎖例如，對任一元組加鎖時，必須先對它所在的數(shù)據(jù)庫和關(guān)系加意向鎖 An Introduction to Database System意向鎖(續(xù))如果對一個結(jié)點(diǎn)加意向鎖，則說明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正常用意向鎖意向共享鎖(Intent Share Lock，簡稱IS鎖)意向排它鎖(Intent Exclusive Lock，簡稱IX鎖)共享意向排它鎖(S

46、hare Intent Exclusive Lock，簡稱SIX鎖)An Introduction to Database System常用意向鎖意向共享鎖(Intent Share Lock，簡意向鎖（續(xù)）IS鎖如果對一個數(shù)據(jù)對象加IS鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加S鎖。 例如：若對表加IS鎖，表示正在對某元組加S鎖；反之：事務(wù)T1要對R1中某個元組加S鎖，則要首先對關(guān)系R1和數(shù)據(jù)庫加IS鎖 An Introduction to Database System意向鎖（續(xù)）IS鎖An Introduction to Da意向鎖（續(xù)）IX鎖如果對一個數(shù)據(jù)對象加IX鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加X鎖。 例如：事務(wù)T1要對R1中某個元組加X鎖，則要首先對關(guān) 系R1和數(shù)據(jù)庫加IX鎖