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