1、.四級(jí)數(shù)據(jù)庫(kù)第八章-事務(wù)調(diào)度與并發(fā)控制8.1 并發(fā)控制概述在第七章中己經(jīng)講到，事務(wù)是并發(fā)控制的基本單位，保證事務(wù)ACID特性是事務(wù)處理的重要任務(wù)，而事務(wù)ACID特性可能遭到破壞的原因之一是多個(gè)事務(wù)對(duì)數(shù)據(jù)庫(kù)的并發(fā)操作造成的。為了保證事務(wù)的隔離性更一般，為了保證數(shù)據(jù)庫(kù)的一致性，DBMS需要對(duì)并發(fā)操作進(jìn)行正確調(diào)度。這些就是數(shù)據(jù)庫(kù)管理系統(tǒng)中并發(fā)控制機(jī)制的責(zé)任。下面先來看一個(gè)例子，說明并發(fā)操作帶來的數(shù)據(jù)的不一致性問題?？紤]飛機(jī)訂票系統(tǒng)中的一個(gè)活動(dòng)序列：甲售票點(diǎn)（甲事務(wù)）讀出某航班的機(jī)票余額A，設(shè)A=16；乙售票點(diǎn)（乙事務(wù)）讀出同一航班的機(jī)票余額A，也為16；甲售票點(diǎn)賣出一張機(jī)票，修改余額A Al，所以A

2、為15，把A寫回?cái)?shù)據(jù)庫(kù)；乙售票點(diǎn)也賣出一張機(jī)票，修改余額A Al，所以A為15，把A寫回?cái)?shù)據(jù)庫(kù)。結(jié)果明明賣出兩張機(jī)票，數(shù)據(jù)庫(kù)中機(jī)票余額只減少1。這種情況稱為數(shù)據(jù)庫(kù)的不一致性。這種不一致性是由并發(fā)操作引起的。在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的。若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。這是由于第步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)的修改。仔細(xì)分析并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：丟失修改、不可重復(fù)讀和讀“臟”數(shù)據(jù)，如圖8.1所示。1丟失修改（Lost Update）兩個(gè)事務(wù)T1和 T2。讀入同一數(shù)據(jù)并修改，T2提交的結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失，如

3、圖8.1（a）所示。上面飛機(jī)訂票例子就屬此類。 圖8.12不可重復(fù)讀（Non-Repeatable Read）不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，重復(fù)T2執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。具體地講，不可重復(fù)讀包括三種情況：（1）事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值。例如在圖8.1（b）中，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，與第1次讀取值不一致。（2）事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相

4、同條件讀取數(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í)也稱為幻影（Phantom Row）現(xiàn)象。3讀“臟”數(shù)據(jù)（Dirty Read）讀“臟”數(shù)據(jù)是指事務(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ù)。例如在圖8.1（C）中T1將C值修改為200，T2讀到C為200，而T1由于某種原因撤銷，其修改作廢，C恢

5、復(fù)原值100，這時(shí)T2讀到的C為200，與數(shù)據(jù)庫(kù)內(nèi)容不一致就是“臟”數(shù)據(jù)。產(chǎn)生上述三類數(shù)據(jù)不一致性的主要原因是并發(fā)操作破壞了事務(wù)的隔離性。并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使一個(gè)用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性。另一方面，對(duì)數(shù)據(jù)庫(kù)的應(yīng)用有時(shí)允許某些不一致性，例如有些統(tǒng)計(jì)工作涉及數(shù)據(jù)量很大，讀到一些“臟”數(shù)據(jù)對(duì)統(tǒng)計(jì)精度沒什么影響，這時(shí)可以降低對(duì)一致性的要求以減少系統(tǒng)開銷。并發(fā)控制的主要技術(shù)是封鎖（Locking）。例如在飛機(jī)訂票例子中，甲事務(wù)要修改A，若在讀出A前先鎖住A，其他事務(wù)就不能再讀取和修改A了，直到甲修改并寫回A后解除了對(duì)A的封鎖為止。這樣，就不會(huì)丟失

6、甲的修改。8.2 封鎖（Locking）封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)。所謂封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象例如表、記錄等操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖。加鎖后事T就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)T釋放它的鎖之前，其他的事務(wù)不能更新此數(shù)據(jù)對(duì)象。確切的控制由封鎖的類型決定。基本的封鎖類型有兩種：排它鎖（Exclusive Locks，簡(jiǎn)稱X鎖）和共享鎖（Share Locks，簡(jiǎn)稱S鎖）。排它鎖又稱為寫鎖。若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其他任何事務(wù)都不能再對(duì)A加任何類型的鎖，直到T釋放A上的鎖。這就保證了其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A。共享

7、鎖又稱為讀鎖。若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則事務(wù)T可以讀A但不能修改A，其他事務(wù)只能再對(duì)A加S鎖，而不能加X鎖，直到T釋放A上的S鎖。這就保證了其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對(duì)A做任何修改。排它鎖與共享鎖的控制方式可以用圖8.2的相容矩陣來表示。圖8.2在圖8.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的

8、請(qǐng)求被拒絕。8.3 封鎖協(xié)議在運(yùn)用X鎖和S鎖這兩種基本封鎖，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，還需要約定一些規(guī)則，例如何時(shí)申請(qǐng)X鎖或S鎖、持鎖時(shí)間、何時(shí)釋放等。稱這些規(guī)則為封鎖協(xié)議（Locking Protocol）。對(duì)封鎖方式規(guī)定不同的規(guī)則，就形成了各種不同的封鎖協(xié)議。下面介紹三級(jí)封鎖協(xié)議。對(duì)并發(fā)操作的不正確調(diào)度可能會(huì)帶來丟失修改、不可重復(fù)讀和讀“臟”數(shù)據(jù)等不一致性問題，三級(jí)封鎖協(xié)議分別在不同程度上解決了這一問題。為并發(fā)操作的正確調(diào)度提供一定的保證。不同級(jí)別的封鎖協(xié)議達(dá)到的系統(tǒng)一致性級(jí)別是不同的。一、一級(jí)封鎖協(xié)議一級(jí)封鎖協(xié)議是：事務(wù)T在修改數(shù)據(jù)R之前必須先對(duì)其加X鎖，直到事務(wù)結(jié)束才釋放。事務(wù)結(jié)束包括正常結(jié)束

9、（COMMIT）和非正常結(jié)束（ROLLBACK）。一級(jí)封鎖協(xié)議可防止丟失修改，并保證事務(wù)T是可恢復(fù)的。例如圖8.3（a）使用一級(jí)封鎖協(xié)議解決了圖8.1（a）中的丟失修改問題。圖8.3（a）事務(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í)它讀到的A己經(jīng)是T1更新過的值15，再按此新的A值進(jìn)行運(yùn)算，并將結(jié)果值A(chǔ)=14送回到磁盤。這樣就避免了丟失T1的更新。在一級(jí)封鎖協(xié)議中，如果僅僅是讀數(shù)據(jù)不對(duì)其進(jìn)行修改，是不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。二、二級(jí)封鎖協(xié)議二級(jí)封鎖協(xié)議是：一級(jí)封鎖協(xié)議加上事務(wù)T在讀取

10、數(shù)據(jù)R之前必須先對(duì)其加S鎖，讀完后即可釋放S鎖。二級(jí)封鎖協(xié)議除防止了丟失修改，還可進(jìn)一步防止讀“臟”數(shù)據(jù)。例如圖8.3（C）使用二級(jí)封鎖協(xié)議解決了圖8.1（c）中的讀“臟”數(shù)據(jù)問題。圖8.3（c）中，事務(wù)T1在對(duì) C進(jìn)行修改之前，先對(duì) C加 X鎖，修改其值后寫回磁盤。這時(shí)T2請(qǐng)求在 C上加 S鎖，因 T1己在C上加了 X鎖，T2只能等待。T1因某種原因被撤銷，C恢復(fù)為原值100，T1釋放 C上的 X鎖后T2獲得C上的 S鎖，讀 C=100。這就避免了T2讀“臟”數(shù)據(jù)。在二級(jí)封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀。三、三級(jí)封鎖協(xié)議三級(jí)封鎖協(xié)議是：一級(jí)封鎖協(xié)議加上事務(wù)T在讀

11、取數(shù)據(jù)R之前必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放。三級(jí)封鎖協(xié)議除防止了丟失修改和不讀“臟”數(shù)據(jù)外，還進(jìn)一步防止了不可重復(fù)讀。例如圖8.3（b）使用三級(jí)封鎖協(xié)議解決了圖8.1（b）不可重復(fù)讀問題。圖8.3（b）中，事務(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鎖。上述三級(jí)協(xié)議的主要區(qū)別在于什么操作需要申請(qǐng)封鎖，以及何時(shí)釋

12、放鎖（即持鎖時(shí)間）。三個(gè)級(jí)別的封鎖協(xié)議可以總結(jié)為表8.1。圖8.3表8.18.4 活鎖和死鎖和操作系統(tǒng)一樣，封鎖的方法可能引起活鎖和死鎖。一、活鎖如果事務(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)等待，這就是活鎖的情形，如圖8.4（a）所示。避免活鎖的簡(jiǎn)單方法是采用先來先服務(wù)的策略。當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)，封鎖子系統(tǒng)按請(qǐng)求封鎖的先后次序?qū)κ聞?wù)排隊(duì)，數(shù)據(jù)對(duì)象上的鎖一旦釋放就批準(zhǔn)申請(qǐng)隊(duì)列中第1個(gè)事務(wù)獲得鎖。二、

13、死鎖如果事務(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上的鎖。這樣就出現(xiàn)了T1在等待T2，而T2又在等待T1的局面，T1和T2兩個(gè)事務(wù)永遠(yuǎn)不能結(jié)束，形成死鎖。如圖8.4（b）所示。死鎖的問題在操作系統(tǒng)和一般并行處理中已做了深入研究，目前在數(shù)據(jù)庫(kù)中解決死鎖問題主要有兩類方法，一類方法是采取一定措施來預(yù)防死鎖的發(fā)生，另一類方法是允許發(fā)生死鎖，采用一定手段定期診斷系統(tǒng)中有無死鎖，若有則解除之。 1死鎖的預(yù)防在數(shù)據(jù)庫(kù)中，產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了

14、一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。防止死鎖的發(fā)生其實(shí)就是要破壞產(chǎn)生死鎖的條件。預(yù)防死鎖通常有兩種方法；（1）一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行。如圖8.4（b）的例子中，如果事務(wù)T1將數(shù)據(jù)對(duì)象R1和R2一次加鎖，T1就可以執(zhí)行下去，而T2等待。T1執(zhí)行完后釋放R1，R2上的鎖，T2繼續(xù)執(zhí)行。這樣就不會(huì)發(fā)生死鎖。一次封鎖法雖然可以有效地防止死鎖的發(fā)生，但也存在問題。第一，一次就將以后要用到的全部數(shù)據(jù)加鎖，勢(shì)必?cái)U(kuò)大了封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度。第二，數(shù)據(jù)庫(kù)中數(shù)據(jù)是不斷變化的，原來不要求封鎖的數(shù)據(jù)，

15、在執(zhí)付過程中可能會(huì)變成封鎖對(duì)象，所以很難事先精確地確定每個(gè)事務(wù)所要封鎖的數(shù)據(jù)對(duì)象，為此只能擴(kuò)大封鎖范圍，將事務(wù)在執(zhí)行過程中可能要封鎖的數(shù)據(jù)對(duì)象全部加鎖，這就進(jìn)一步降低了并發(fā)度。（2）順序封鎖法順序劫鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。例如在B樹結(jié)構(gòu)的索引中，可規(guī)定封鎖的順序必須是從根結(jié)點(diǎn)開始，然后是下一級(jí)的子女結(jié)點(diǎn)，逐級(jí)封鎖。順序封鎖法可以有效地防止死鎖，但也同樣存在問題。第一，數(shù)據(jù)庫(kù)系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護(hù)這樣的資源的封鎖順序非常困難；成本很高。第二，事務(wù)的封鎖請(qǐng)求可以隨著事務(wù)的執(zhí)行而動(dòng)態(tài)地訣定，很難事先確定每

16、一個(gè)事務(wù)要封鎖哪些對(duì)象，因此也就很難按規(guī)定的順序去施加封鎖?？梢?，在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫(kù)的特點(diǎn)，因此DBMS在解決死鎖的問題上普遍采用的是診斷并解除死鎖的方法2死鎖的診斷與解除數(shù)據(jù)庫(kù)系統(tǒng)中診斷死鎖的方法與操作系統(tǒng)類似，一般使用超時(shí)法或事務(wù)等待圖法。（1）超時(shí)法如果一個(gè)事務(wù)的等待時(shí)間超過了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖。超時(shí)法實(shí)現(xiàn)簡(jiǎn)單，但其不足也很明顯。一是有可能誤判死鎖，事務(wù)因?yàn)槠渌蚴沟却龝r(shí)間超過時(shí)限，系統(tǒng)會(huì)誤認(rèn)為發(fā)生了死鎖。二是時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)。（2）等待圖法事務(wù)等待圖是一個(gè)有向圖G（T，U）。T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)；

17、U為邊的集合，每條邊表示事務(wù)等待的情況。若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2。事務(wù)等待圖動(dòng)態(tài)地反映了所有事務(wù)的等待情況。并發(fā)控制子系統(tǒng)周期性地（比如每隔1 min）檢測(cè)事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。DBMS的并發(fā)控制子系統(tǒng)一旦檢測(cè)到系統(tǒng)中存在死鎖，就要設(shè)法解除。通常采用的方法是選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤銷，釋放此事務(wù)持有的所有的鎖，使其他事務(wù)得以繼續(xù)運(yùn)行下去。當(dāng)然，對(duì)撤銷的事務(wù)所執(zhí)行的數(shù)據(jù)修改操作必須加以恢復(fù)。8.5 并發(fā)調(diào)度的可串行性計(jì)算機(jī)系統(tǒng)對(duì)并發(fā)事務(wù)中并發(fā)操作的調(diào)度是隨機(jī)的，而不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果，那么哪個(gè)結(jié)果是正

18、確的，哪個(gè)是不正確的呢？如果一個(gè)事務(wù)運(yùn)行過程中沒有其他事務(wù)同時(shí)運(yùn)行，也就是說它沒有受到其他事務(wù)的干擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正常的或者預(yù)想的。因此將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。雖然以不同的順序串行執(zhí)行事務(wù)可能會(huì)產(chǎn)生不同的結(jié)果，但由子不會(huì)將數(shù)據(jù)庫(kù)置于不一致狀態(tài)，所以都是正確的。定義 多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同，我們稱這種調(diào)度策略為可串行化（Serializable）的調(diào)度?？纱行裕⊿erializability）是并發(fā)事務(wù)正確性的準(zhǔn)則。按這個(gè)準(zhǔn)則規(guī)定，一個(gè)給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度

19、。例如，現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作：事務(wù)T1：讀B；A=B+1；寫回A；事務(wù)T2：讀A；B=A+1；寫回B；假設(shè)A，B的初值均為2。按T1T2次序執(zhí)行結(jié)果為A=3，B=4；按T2T1次序執(zhí)行結(jié)果為B=3，A=4。圖85給出了對(duì)這兩個(gè)事務(wù)的三種不同的調(diào)度策略。圖8.5（a）和（b）為兩種不同的串行調(diào)度策略，雖然執(zhí)行結(jié)果不同，但它們都是正確的調(diào)度；圖8.5（c）產(chǎn)兩個(gè)事務(wù)是交錯(cuò)執(zhí)行的；由于其執(zhí)行結(jié)果與（a），（b）的結(jié)果都不同，所以是錯(cuò)誤的調(diào)度；圖8.5（d）中兩個(gè)事務(wù)也是交錯(cuò)執(zhí)行的，其執(zhí)行結(jié)果與串行調(diào)度（a）執(zhí)行結(jié)果相同，所以是正確的調(diào)度。圖8.5 為了保證并發(fā)操作的正確性，DBMS的并發(fā)

20、控制機(jī)制必須提供一定的手段來保證調(diào)度是可串行化的。從理論上講，在某一事務(wù)執(zhí)行時(shí)禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡(jiǎn)單的調(diào)度策略，但這種方法實(shí)際上是不可取的，這使用戶不能充分共享數(shù)據(jù)庫(kù)資源。目前DBMS普遍采用封鎖方法實(shí)現(xiàn)并發(fā)操作調(diào)度的可串行性，從而保證調(diào)度的正確性。 兩段鎖（Two-Phase Locking，簡(jiǎn)稱 2PL）協(xié)議就是保證并發(fā)調(diào)度可串行性的封鎖協(xié)議。除此之外還有其他一些方法，如時(shí)標(biāo)方法、樂觀方法等來保證調(diào)度的正確性。8.6 兩段鎖協(xié)議所謂兩段鎖協(xié)議是指所有事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖。在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，首先要申請(qǐng)并獲得對(duì)該數(shù)據(jù)的封鎖；在

21、釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和獲得任何其他封鎖。所謂“兩段”鎖的含義是，事務(wù)分為兩個(gè)階段，第一階段是獲得封鎖，也稱為擴(kuò)展階段。在這階段，事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖。第二階段是釋放封鎖，也稱為收縮階段。在這階段，事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請(qǐng)任何鎖。例如事務(wù)T1遵守兩段鎖協(xié)議，其封鎖序列是：可以證明，若并發(fā)執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的。需要說明的是，事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。也就是說；若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化

22、的：若對(duì)并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都符合兩段鎖協(xié)議。在圖8.6中，（a）和（b）都是可串行化的調(diào)度，但（a）中T1和T2都遵守兩段鎖協(xié)議，（b）中T1和T2不遵守兩段鎖協(xié)議。又如圖8.5中（d）是可串行化的調(diào)度，但T1和T2也不遵守兩段鎖協(xié)議。另外要注意兩段鎖協(xié)議和防止死鎖的一次封鎖法的異同之處。一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議；但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖，如圖8.7所示。圖8.6、8.78.7.1 多粒度封鎖下面討論多粒度封鎖，

23、首先定義多粒度樹。多粒度樹的根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度。葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度。圖8.8給出了一個(gè)三級(jí)粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。圖8.8然后，來討論多粒度封鎖的封鎖協(xié)議。多粒度封鎖協(xié)議允許多粒度樹中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖。對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的鎖。因此，在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖，顯式封鎖和隱式封鎖。顯式封鎖是應(yīng)事務(wù)的要求直接加到數(shù)據(jù)對(duì)象上的封鎖；隱式封鎖是該數(shù)據(jù)對(duì)象沒有獨(dú)立加鎖，是由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖。多粒度封鎖方法中，顯式封鎖和隱式封鎖的效果是一樣的，因此系統(tǒng)檢

24、查封鎖沖突時(shí)不僅要檢查顯式封鎖還要檢查隱式封鎖。例如事務(wù)T要對(duì)關(guān)系R1加X鎖。系統(tǒng)必須搜索其上級(jí)結(jié)點(diǎn)數(shù)據(jù)庫(kù)、關(guān)系R1以及R1中的每一個(gè)元組，如果其中某一個(gè)數(shù)據(jù)對(duì)象己經(jīng)加了不相容鎖，則T必須等待。一般地，對(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)的封鎖）沖突。顯然，這樣的檢查方法效率很低。為此人們引進(jìn)了一種新型鎖，稱為意向鎖（Intention Lock）。8.7.2 意向鎖意向鎖的含義是

25、如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖；對(duì)任一結(jié)點(diǎn)加鎖時(shí)，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖。例如，對(duì)任一元組加鎖時(shí)，必須先對(duì)它所在的關(guān)系加意向鎖。于是，事務(wù)T要對(duì)關(guān)系R1加 X鎖時(shí)，系統(tǒng)只要檢查根結(jié)點(diǎn)數(shù)據(jù)庫(kù)和關(guān)系R1是否己加了不相容的鎖，而不再需要搜索和檢查尺中的每一個(gè)元組是否加了X鎖。下面介紹三種常用的意向鎖：意向共享鎖（Intent Share Lock，簡(jiǎn)稱IS鎖）；意向排它鎖（Intent Exclusive Lock，簡(jiǎn)稱IX鎖）；共享意向排它鎖（Share Intent Exclusive Lock，簡(jiǎn)稱SIX鎖）。1IS鎖如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加IS鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加 S鎖。例如，要對(duì)某個(gè)元組加 S鎖，則要首先對(duì)關(guān)系和數(shù)據(jù)庫(kù)加 IS鎖。2IX鎖如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加 IX鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加 X鎖。例如，要對(duì)某個(gè)元組加 X鎖，則要首先對(duì)關(guān)系和數(shù)據(jù)庫(kù)加 IX鎖。3SIX鎖如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加 SIX鎖，表示對(duì)它加 S鎖，再加IX鎖，即 SIX=SIX。例如對(duì)某個(gè)表加 SIX鎖，則表示該事務(wù)要讀整個(gè)表（所以要對(duì)該表加 S鎖），同時(shí)會(huì)更新個(gè)別元組（所以要對(duì)該表加 IX鎖）。