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

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

2、個(gè)事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(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ī)的空閑時(shí)間，提高系統(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)同時(shí)并發(fā)方式（simultaneous concurrency）多處理機(jī)系統(tǒng)中，每個(gè)處理機(jī)可以運(yùn)行一個(gè)事務(wù)，多個(gè)處理機(jī)可以同時(shí)運(yùn)行多個(gè)事務(wù)，實(shí)現(xiàn)多個(gè)事務(wù)真正的并行運(yùn)行An Introduction to Database System問題的產(chǎn)生（續(xù)） (3)同時(shí)并發(fā)方式（simultaneou問題的產(chǎn)生（續(xù)）事務(wù)并發(fā)執(zhí)行帶來(lái)的問題會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情況 可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞事務(wù)一致性和

4、數(shù)據(jù)庫(kù)的一致性An Introduction to Database System問題的產(chǎn)生（續(xù)）事務(wù)并發(fā)執(zhí)行帶來(lái)的問題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ù)對(duì)并發(fā)操作進(jìn)行正確調(diào)度保證事務(wù)的隔離性保證數(shù)據(jù)庫(kù)的一致性An Introduction to Database System11.1 并發(fā)

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

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

7、System并發(fā)控制概述（續(xù)）并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性An Intro1. 丟失修改兩個(gè)事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失。上面飛機(jī)訂票例子就屬此類 An Introduction to Database System1. 丟失修改兩個(gè)事務(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無(wú)法再現(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對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值 An Introduction to Database System不可重復(fù)讀（續(xù)）不可重復(fù)讀包括三種情況：An Introdu不可重復(fù)讀（續(xù)）T1讀取B=100進(jìn)行運(yùn)算T2讀取同一數(shù)據(jù)B，對(duì)其進(jìn)行修改后將B=200寫回?cái)?shù)據(jù)庫(kù)。T1為了對(duì)讀取值校對(duì)重讀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ù)庫(kù)中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄消失了 (3)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（Phantom Row）An Introduction to Database System不可重復(fù)讀（續(xù)）(2)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了某些3. 讀“臟”數(shù)據(jù) 讀“臟”數(shù)據(jù)是

10、指：事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷這時(shí)T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(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這時(shí)T2讀到的C為200，與數(shù)據(jù)庫(kù)內(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ā)操作，使一個(gè)用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性 An Introduction to Database System并發(fā)控制概述（續(xù)）數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離并發(fā)控制概述（續(xù)）并發(fā)控制的主要技術(shù)有封鎖(Locking)時(shí)間戳(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在對(duì)某個(gè)數(shù)據(jù)對(duì)象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖加鎖后事務(wù)T就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)T

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

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

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

16、改問題例：事務(wù)T1在讀A進(jìn)行修改之前先對(duì)A加X鎖當(dāng)T2再請(qǐng)求對(duì)A加X鎖時(shí)被拒絕T2只能等待T1釋放A上的鎖后T2獲得對(duì)A的X鎖這時(shí)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之前，先對(duì)A，B加S鎖其他事務(wù)只能再對(duì)A，B加S鎖，而不能加X鎖，即其他事務(wù)只能讀A，B，而不能修改當(dāng)T2為修改B而申請(qǐng)對(duì)B的X鎖時(shí)被拒絕只能等待T1釋放B上的鎖T1為

17、驗(yàn)算再讀A，B，這時(shí)讀出的B仍是100，求和結(jié)果仍為150，即可重復(fù)讀T1結(jié)束才釋放A，B上的S鎖。T2才獲得對(duì)B的X鎖 可重復(fù)讀An Introduction to Database System使用封鎖機(jī)制解決不可重復(fù)讀問題事務(wù)T1在讀A，B之前，先對(duì)A使用封鎖機(jī)制解決讀“臟”數(shù)據(jù)問題例事務(wù)T1在對(duì)C進(jìn)行修改之前，先對(duì)C加X鎖，修改其值后寫回磁盤T2請(qǐng)求在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在對(duì)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ù)可以有效地解決并行操作的一致性問題，但也帶來(lái)一些新的問題死鎖活鎖An Introduction to Database System11.3 活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性11.3.1 活鎖事務(wù)T1封鎖了

19、數(shù)據(jù)R事務(wù)T2又請(qǐng)求封鎖R，于是T2等待。T3也請(qǐng)求封鎖R，當(dāng)T1釋放了R上的封鎖之后系統(tǒng)首先批準(zhǔn)了T3的請(qǐng)求，T2仍然等待。T4又請(qǐng)求封鎖R，當(dāng)T3釋放了R上的封鎖之后系統(tǒng)又批準(zhǔn)了T4的請(qǐng)求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ù)）避免活鎖：采用先來(lái)先服務(wù)的策略當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)按請(qǐng)求封鎖的先后次序?qū)@些事

20、務(wù)排隊(duì)該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖An Introduction to Database System活鎖（續(xù)）避免活鎖：采用先來(lái)先服務(wù)的策略An Introdu11.3.2 死鎖事務(wù)T1封鎖了數(shù)據(jù)R1T2封鎖了數(shù)據(jù)R2T1又請(qǐng)求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖接著T2又申請(qǐng)封鎖R1，因T1已封鎖了R1，T2也只能等待T1釋放R1上的鎖這樣T1在等待T2，而T2又在等待T1，T1和T2兩個(gè)事務(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)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已被其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件An Introduction to Database System1. 死鎖的預(yù)防產(chǎn)生死鎖的原因是

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

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

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

25、T1指向T2An Introduction to Database System(2)等待圖法用事務(wù)等待圖動(dòng)態(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ù)等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系

26、統(tǒng)中出現(xiàn)了死鎖。An Introduction to Database System等待圖法（續(xù)）并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)死鎖的診斷與解除（續(xù)）解除死鎖選擇一個(gè)處理死鎖代價(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對(duì)并發(fā)事務(wù)不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果什么樣的調(diào)度是正確的？An Introduction to Database System11.4 并發(fā)調(diào)度的可串行性DBMS對(duì)并發(fā)事務(wù)不同的調(diào)度可11.4.1 可串行化調(diào)度可串行化(Serializable)調(diào)度多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行這些事務(wù)時(shí)的結(jié)果相同可串行性(Serializability)是并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則一個(gè)給定的并發(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)在有兩個(gè)事務(wù)，分別包含下列操作：事務(wù)T1：讀B；A=B+1；寫回A事務(wù)T2：讀A；B=A+1；寫回B現(xiàn)給出對(duì)這兩個(gè)事務(wù)不同的調(diào)度策略 An Introduction to Database System可串行化調(diào)度（續(xù)）例現(xiàn)在有兩個(gè)事務(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)度，錯(cuò)誤的調(diào)度不可串行化的調(diào)度 執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同是錯(cuò)誤的調(diào)度 An Introduction to Database System不可串行化調(diào)度，錯(cuò)誤的調(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)度的充分條件一個(gè)調(diào)度Sc在保證沖突操作的次序不變的情況下，通過交換兩個(gè)事務(wù)不沖突操作的次序得到另一個(gè)調(diào)度Sc，如果Sc是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度一個(gè)調(diào)度是沖突可串行化，一定是可串行化的調(diào)度An Introduction to Database System11.4.2 沖突可串行化調(diào)度可串行化調(diào)度的充分條件An 沖突可串行化調(diào)度（續(xù)）沖突操作沖突操作是指不同的事務(wù)對(duì)同一個(gè)數(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à)于一個(gè)串行調(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個(gè)事務(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)是一個(gè)串行調(diào)度。調(diào)度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖

33、突可串行化。但是調(diào)度L2是可串行化的，因?yàn)長(zhǎng)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í)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)

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

35、on t兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義事務(wù)分為兩個(gè)階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請(qǐ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é)議的，因此一定是一個(gè)可串行化調(diào)度。An Introduction to Database System兩段鎖協(xié)議（續(xù)）遵守兩段鎖協(xié)議的可串行化調(diào)度左圖的調(diào)度是遵守兩段鎖協(xié)議（續(xù)）事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策

37、略都是可串行化的若并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都符合兩段鎖協(xié)議 An Introduction to Database System兩段鎖協(xié)議（續(xù)）事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議與防止死鎖的一次封鎖法一次封鎖法要求每個(gè)事務(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封鎖粒度封鎖對(duì)象的大小稱為

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

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

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

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

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

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

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

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