DB11數(shù)據(jù)庫第十一章教學(xué).pptVIP

第11章 并發(fā)控制,問題的產(chǎn)生,多用戶數(shù)據(jù)庫系統(tǒng)的存在 允許多個(gè)用戶同時(shí)使用的數(shù)據(jù)庫系統(tǒng) 飛機(jī)定票數(shù)據(jù)庫系統(tǒng) 銀行數(shù)據(jù)庫系統(tǒng) 特點(diǎn)：在同一時(shí)刻并發(fā)運(yùn)行的事務(wù)數(shù)可達(dá)數(shù)百個(gè),不同的多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行 每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行 不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源的特點(diǎn),T1,T2,T3,事務(wù)的串行執(zhí)行方式,第11章 并發(fā)控制,(2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機(jī)系統(tǒng)中，事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運(yùn)行 單處理機(jī)系統(tǒng)中的并行事務(wù)并沒有真正地并行運(yùn)行，但能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率,第11章 并發(fā)控制,事務(wù)的交叉并發(fā)執(zhí)行方式,第11章 并發(fā)控制,(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)行,第11章 并發(fā)控制,事務(wù)并發(fā)執(zhí)行帶來的問題 會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情況 可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞事務(wù)一致性和數(shù)據(jù)庫的一致性,第11章 并發(fā)控制,并發(fā)控制概述 封鎖 活鎖和死鎖 并發(fā)調(diào)度的可串行性 兩段鎖協(xié)議 封鎖的粒度,第11章 并發(fā)控制,11.1 并發(fā)控制概述,并發(fā)控制機(jī)制的任務(wù) 對(duì)并發(fā)操作進(jìn)行正確調(diào)度 保證事務(wù)的隔離性 保證數(shù)據(jù)庫的一致性,并發(fā)操作帶來數(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ù)庫； 乙售票點(diǎn)也賣出一張機(jī)票，修改余額AA-1，所以A為15，把A寫回?cái)?shù)據(jù)庫 結(jié)果明明賣出兩張機(jī)票，數(shù)據(jù)庫中機(jī)票余額只減少1,11.1 并發(fā)控制概述,這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作引起的。 在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的。 若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。 原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)的修改,11.1 并發(fā)控制概述,并發(fā)操作帶來的數(shù)據(jù)不一致性 丟失修改（Lost Update） 不可重復(fù)讀（Non-repeatable Read） 讀“臟”數(shù)據(jù)（Dirty Read） 記號(hào) R(x):讀數(shù)據(jù)x W(x):寫數(shù)據(jù)x,11.1 并發(fā)控制概述,1. 丟失修改,兩個(gè)事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失。 上面飛機(jī)訂票例子就屬此類,11.1 并發(fā)控制概述,丟失修改,11.1 并發(fā)控制概述,2. 不可重復(fù)讀,不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。,11.1 并發(fā)控制概述,不可重復(fù)讀包括三種情況： (1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值,T1讀取B=100進(jìn)行運(yùn)算 T2讀取同一數(shù)據(jù)B，對(duì)其進(jìn)行修改后將B=200寫回?cái)?shù)據(jù)庫。 T1為了對(duì)讀取值校對(duì)重讀B，B已為200，與第一次讀取值不一致,不可重復(fù)讀,例如：,11.1 并發(fā)控制概述,(2)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄消失了 (3)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（Phantom Row）,11.1 并發(fā)控制概述,3. 讀“臟”數(shù)據(jù),讀“臟”數(shù)據(jù)是指： 事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤 事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷 這時(shí)T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致 T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù),11.1 并發(fā)控制概述,例如,讀“臟”數(shù)據(jù),T1將C值修改為200，T2讀到C為200 T1由于某種原因撤銷，其修改作廢，C恢復(fù)原值100 這時(shí)T2讀到的C為200，與數(shù)據(jù)庫內(nèi)容不一致，就是“臟”數(shù)據(jù),11.1 并發(fā)控制概述,數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離性 并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使一個(gè)用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性,11.1 并發(fā)控制概述,并發(fā)控制的主要技術(shù) 有封鎖(Locking) 時(shí)間戳(Timestamp) 樂觀控制法 商用的DBMS一般都采用封鎖方法,11.1 并發(fā)控制概述,11.2 封鎖,什么是封鎖 基本封鎖類型 鎖的相容矩陣,什么是封鎖,封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖 加鎖后事務(wù)T就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)T釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對(duì)象。,11.2 封鎖,基本封鎖類型,一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制由封鎖的類型決定。 基本封鎖類型 排它鎖（Exclusive Locks，簡(jiǎn)記為X鎖） 共享鎖（Share Locks，簡(jiǎn)記為S鎖）,11.2 封鎖,排它鎖,排它鎖又稱為寫鎖 若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類型的鎖，直到T釋放A上的鎖 保證其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A,11.2 封鎖,共享鎖,共享鎖又稱為讀鎖 若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則其它事務(wù)只能再對(duì)A加S鎖，而不能加X鎖，直到T釋放A上的S鎖 保證其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對(duì)A做任何修改,11.2 封鎖,鎖的相容矩陣,11.2 封鎖,在鎖的相容矩陣中： 最左邊一列表示事務(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)求被拒絕,11.2 封鎖,使用封鎖機(jī)制解決丟失修改問題,例：,事務(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更新過的值15 T2按此新的A值進(jìn)行運(yùn)算，并將結(jié)果值A(chǔ)=14送回到磁盤。避免了丟失T1的更新。,沒有丟失修改,11.2 封鎖,使用封鎖機(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為驗(yàn)算再讀A，B，這時(shí)讀出的B仍是100，求和結(jié)果仍為150，即可重復(fù)讀 T1結(jié)束才釋放A，B上的S鎖。T2才獲得對(duì)B的X鎖,可重復(fù)讀,11.2 封鎖,使用封鎖機(jī)制解決讀“臟”數(shù)據(jù)問題,例,事務(wù)T1在對(duì)C進(jìn)行修改之前，先對(duì)C加X鎖，修改其值后寫回磁盤 T2請(qǐng)求在C上加S鎖，因T1已在C上加了X鎖，T2只能等待 T1因某種原因被撤銷，C恢復(fù)為原值100 T1釋放C上的X鎖后T2獲得C上的S鎖，讀C=100。避免了T2讀“臟”數(shù)據(jù),不讀“臟”數(shù)據(jù),11.2 封鎖,一級(jí)封鎖協(xié)議 事務(wù)T在修改數(shù)據(jù)之前必須先對(duì)其加X鎖，直到事務(wù)結(jié)束才釋放。 二級(jí)封鎖協(xié)議 一級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，讀完后即可釋放S鎖。 三級(jí)封鎖協(xié)議 一級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放。,11.2 封鎖,對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，還需要約定一些規(guī)則，稱這些規(guī)則為封鎖協(xié)議,11.3 活鎖和死鎖,封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題 死鎖 活鎖,11.3.1 活鎖,事務(wù)T1封鎖了數(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)等待，這就是活鎖的情形,活 鎖,11.3.1 活鎖,避免活鎖：采用先來先服務(wù)的策略 當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí) 按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì) 該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖,11.3.1 活鎖,11.3.2 死鎖,事務(wù)T1封鎖了數(shù)據(jù)R1 T2封鎖了數(shù)據(jù)R2 T1又請(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é)束，形成死鎖,死鎖,11.3.2 死鎖,解決死鎖的方法,兩類方法 1. 預(yù)防死鎖 2. 死鎖的診斷與解除,11.3.2 死鎖,1. 死鎖的預(yù)防,產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。 預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件,11.3.2 死鎖,預(yù)防死鎖的方法 一次封鎖法 順序封鎖法,11.3.2 死鎖,(1)一次封鎖法,要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行 存在的問題 降低系統(tǒng)并發(fā)度 難于事先精確確定封鎖對(duì)象,11.3.2 死鎖,(2)順序封鎖法,順序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。 順序封鎖法存在的問題 維護(hù)成本 數(shù)據(jù)庫系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極多，并且在不斷地變化。 難以實(shí)現(xiàn)：很難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象,11.3.2 死鎖,結(jié)論 在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫的特點(diǎn) DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法,11.3.2 死鎖,2. 死鎖的診斷與解除,死鎖的診斷 超時(shí)法 事務(wù)等待圖法,11.3.2 死鎖,(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),11.3.2 死鎖,(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之間劃一條有向邊，從T1指向T2,11.3.2 死鎖,等待圖法（續(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，在大回路中又有小的回路,11.3.2 死鎖,解除死鎖 選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消 釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去,并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖,11.3.2 死鎖,11.4 并發(fā)調(diào)度的可串行性,DBMS對(duì)并發(fā)事務(wù)不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果 什么樣的調(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)度,例現(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)度策略,11.4.1 可串行化調(diào)度,串行調(diào)度(a),假設(shè)A、B的初值均為2。 按T1T2次序執(zhí)行結(jié)果為A=3，B=4 串行調(diào)度策略,正確的調(diào)度,11.4.1 可串行化調(diào)度,串行調(diào)度(b),假設(shè)A、B的初值均為2。 T2T1次序執(zhí)行結(jié)果為B=3，A=4 串行調(diào)度策略,正確的調(diào)度,11.4.1 可串行化調(diào)度,不可串行化的調(diào)度,執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同 是錯(cuò)誤的調(diào)度,11.4.1 可串行化調(diào)度,可串行化的調(diào)度,執(zhí)行結(jié)果與串行調(diào)度(a)的執(zhí)行結(jié)果相同 是正確的調(diào)度,11.4.1 可串行化調(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)度,沖突操作 沖突操作是指不同的事務(wù)對(duì)同一個(gè)數(shù)據(jù)的讀寫操作和寫寫操作 Ri (x)與Wj(x) /* 事務(wù)Ti讀x，Tj寫x*/ Wi(x)與Wj(x) /* 事務(wù)Ti寫x，Tj寫x*/ 其他操作是不沖突操作 不同事務(wù)的沖突操作和同一事務(wù)的兩個(gè)操作不能交換(Swap),11.4.2 沖突可串行化調(diào)度,例今有調(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)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Sc2等價(jià)于一個(gè)串行調(diào)度T1，T2，Sc1沖突可串行化的調(diào)度,11.4.2 沖突可串行化調(diào)度,11.5 兩段鎖協(xié)議,封鎖協(xié)議 運(yùn)用封鎖方法時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請(qǐng)封鎖 持鎖時(shí)間 何時(shí)釋放封鎖等 兩段封鎖協(xié)議(Two-Phase Locking，簡(jiǎn)稱2PL)是最常用的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可串行化調(diào)度,兩段鎖協(xié)議 指所有事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖 在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖 在釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和獲得任何其他封鎖,11.5 兩段鎖協(xié)議,“兩段”鎖的含義 事務(wù)分為兩個(gè)階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段 事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請(qǐng)任何鎖,11.5 兩段鎖協(xié)議,例 事務(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；,11.5 兩段鎖協(xié)議,遵守兩段鎖協(xié)議的可串行化調(diào)度,左圖的調(diào)度是遵守兩段鎖協(xié)議的，因此一定是一個(gè)可串行化調(diào)度,11.5 兩段鎖協(xié)議,事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。 若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的 若并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都符合兩段鎖協(xié)議,11.5 兩段鎖協(xié)議,兩段鎖協(xié)議與防止死鎖的一次封鎖法 一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議 但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖,11.5 兩段鎖協(xié)議,11.6 封鎖的粒度,封鎖對(duì)象的大小稱為封鎖粒度(Granularity) 封鎖的對(duì)象：邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫中，封鎖對(duì)象： 邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫等 物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等,封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密切相關(guān)。 封鎖的粒度越大，數(shù)據(jù)庫所能夠封鎖的數(shù)據(jù)單元就越少，并發(fā)度就越小，系統(tǒng)開銷也越??； 封鎖的粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越大,11.6 封鎖的粒度,選擇封鎖粒度原則,例 若封鎖粒度是數(shù)據(jù)頁，事務(wù)T1需要修改元組L1，則T1必須對(duì)包含L1的整個(gè)數(shù)據(jù)頁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è)元組加鎖，開銷極大,11.6 封鎖的粒度,11.6 封鎖的粒度,多粒度封鎖(Multiple Granularity Locking) 在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇 選擇封鎖粒度 同時(shí)考慮封鎖開銷和并發(fā)度兩個(gè)因素，適當(dāng)選擇封鎖粒度 需要處理多個(gè)關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫為封鎖單位 需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元 只處理少量元組的用戶事務(wù)：以元組為封鎖單位,多粒度樹 以樹形結(jié)構(gòu)來表示多級(jí)封鎖粒度 根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度 葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度,11.6.1 多粒度封鎖,例：三級(jí)粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。,三級(jí)粒度樹,11.6.1 多粒度封鎖,允許多粒度樹中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖 對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的鎖 在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：顯式封鎖和隱式封鎖,11.6.1 多粒度封鎖,顯式封鎖: 直接加到數(shù)據(jù)對(duì)象上的封鎖 隱式封鎖: 該數(shù)據(jù)對(duì)象沒有獨(dú)立加鎖，是由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖 顯式封鎖和隱式封鎖的效果是一樣的,11.6.1 多粒度封鎖,系統(tǒng)檢查封鎖沖突時(shí) 要檢查顯式封鎖 還要檢查隱式封鎖 例如事務(wù)T要對(duì)關(guān)系R1加X鎖 系統(tǒng)必須搜索其上級(jí)結(jié)點(diǎn)數(shù)據(jù)庫、關(guān)系R1 還要搜索R1的下級(jí)結(jié)點(diǎn)，即R1中的每一個(gè)元組 如果其中某一個(gè)數(shù)據(jù)對(duì)象已經(jīng)加了不相容鎖，則T必須等待,11.6.1 多粒度封鎖,對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對(duì)象 有無顯式封鎖與之沖突 所有上級(jí)結(jié)點(diǎn) 檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式封鎖沖突：(由上級(jí)結(jié)點(diǎn)已加的封鎖造成的） 所有下級(jí)結(jié)點(diǎn) 看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級(jí)結(jié)點(diǎn)的封鎖）沖突,11.6.1 多粒度封鎖,11.6.2 意向鎖