并發(fā)控制市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

第十一章并發(fā)控制一、問題產(chǎn)生二、并發(fā)控制概述三、封鎖四、活鎖和死鎖五、并發(fā)調(diào)度可串行性六、兩段鎖協(xié)議七、封鎖粒度八、小結(jié)并發(fā)控制第1頁(yè)一、問題產(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è)并發(fā)控制第2頁(yè)問題產(chǎn)生（續(xù)）不一樣多事務(wù)執(zhí)行方式(1)事務(wù)串行執(zhí)行每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其它事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源特點(diǎn)T1T2T3事務(wù)串行執(zhí)行方式并發(fā)控制第3頁(yè)問題產(chǎn)生（續(xù)）(2)交叉并發(fā)方式（InterleavedConcurrency）在單處理機(jī)系統(tǒng)中，事務(wù)并行執(zhí)行是這些并行事務(wù)并行操作輪番交叉運(yùn)行單處理機(jī)系統(tǒng)中并行事務(wù)并沒有真正地并行運(yùn)行，但能夠降低處理機(jī)空閑時(shí)間，提升系統(tǒng)效率并發(fā)控制第4頁(yè)問題產(chǎn)生（續(xù)）事務(wù)交叉并發(fā)執(zhí)行方式并發(fā)控制第5頁(yè)問題產(chǎn)生（續(xù)）(3)同時(shí)并發(fā)方式（simultaneousconcurrency）多處理機(jī)系統(tǒng)中，每個(gè)處理機(jī)能夠運(yùn)行一個(gè)事務(wù)，多個(gè)處理機(jī)能夠同時(shí)運(yùn)行多個(gè)事務(wù)，實(shí)現(xiàn)多個(gè)事務(wù)真正并行運(yùn)行并發(fā)控制第6頁(yè)問題產(chǎn)生（續(xù)）事務(wù)并發(fā)執(zhí)行帶來問題會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)情況可能會(huì)存取和存放不正確數(shù)據(jù)，破壞事務(wù)一致性和數(shù)據(jù)庫(kù)一致性并發(fā)控制第7頁(yè)二、并發(fā)控制概述并發(fā)控制機(jī)制任務(wù)對(duì)并發(fā)操作進(jìn)行正確調(diào)度確保事務(wù)隔離性確保數(shù)據(jù)庫(kù)一致性并發(fā)控制第8頁(yè)T1修改被T2覆蓋了！并發(fā)控制概述（續(xù)）并發(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ī)票，修改余額A←A-1，所以A為15，把A寫回?cái)?shù)據(jù)庫(kù)；④乙售票點(diǎn)也賣出一張機(jī)票，修改余額A←A-1，所以A為15，把A寫回?cái)?shù)據(jù)庫(kù)結(jié)果明明賣出兩張機(jī)票，數(shù)據(jù)庫(kù)中機(jī)票余額只降低1并發(fā)控制第9頁(yè)并發(fā)控制概述（續(xù)）這種情況稱為數(shù)據(jù)庫(kù)不一致性，是由并發(fā)操作引發(fā)。在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)操作序列調(diào)度是隨機(jī)。若按上面調(diào)度序列執(zhí)行，甲事務(wù)修改就被丟失。原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)修改并發(fā)控制第10頁(yè)并發(fā)控制概述（續(xù)）并發(fā)操作帶來數(shù)據(jù)不一致性丟失修改（LostUpdate）不可重復(fù)讀（Non-repeatableRead）讀“臟”數(shù)據(jù)（DirtyRead）記號(hào)R(x):讀數(shù)據(jù)xW(x):寫數(shù)據(jù)x

并發(fā)控制第11頁(yè)1.丟失修改兩個(gè)事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2提交結(jié)果破壞了T1提交結(jié)果，造成T1修改被丟失。上面飛機(jī)訂票例子就屬這類并發(fā)控制第12頁(yè)丟失修改（續(xù)）T1T2①R(A)=16②R(A)=16③A←A-1W(A)=15W④A←A-1W(A)=15丟失修改并發(fā)控制第13頁(yè)2.不可重復(fù)讀不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。并發(fā)控制第14頁(yè)不可重復(fù)讀（續(xù)）不可重復(fù)讀包含三種情況：(1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不一樣值并發(fā)控制第15頁(yè)不可重復(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，與第一次讀取值不一致T1T2①R(A)=50R(B)=100求和=150②R(B)=100B←B*2(B)=200③R(A)=50R(B)=200和=250(驗(yàn)算不對(duì))不可重復(fù)讀

比如：并發(fā)控制第16頁(yè)不可重復(fù)讀（續(xù)）(2)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了一些數(shù)據(jù)統(tǒng)計(jì)后，事務(wù)T2刪除了其中部分統(tǒng)計(jì)，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)覺一些統(tǒng)計(jì)消失了(3)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取一些數(shù)據(jù)統(tǒng)計(jì)后，事務(wù)T2插入了一些統(tǒng)計(jì)，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)覺多了一些統(tǒng)計(jì)。后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（PhantomRow）并發(fā)控制第17頁(yè)3.讀“臟”數(shù)據(jù)讀“臟”數(shù)據(jù)是指：事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤事務(wù)T2讀取同一數(shù)據(jù)后，T1因?yàn)槟撤N原因被撤消這時(shí)T1已修改過數(shù)據(jù)恢復(fù)原值，T2讀到數(shù)據(jù)就與數(shù)據(jù)庫(kù)中數(shù)據(jù)不一致T2讀到數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確數(shù)據(jù)并發(fā)控制第18頁(yè)讀“臟”數(shù)據(jù)（續(xù)）T1T2①R(C)=100C←C*2W(C)=200②R(C)=200③ROLLBACKC恢復(fù)為100比如讀“臟”數(shù)據(jù)

T1將C值修改為200，T2讀到C為200T1因?yàn)槟撤N原因撤消，其修改作廢，C恢復(fù)原值100這時(shí)T2讀到C為200，與數(shù)據(jù)庫(kù)內(nèi)容不一致，就是“臟”數(shù)據(jù)

并發(fā)控制第19頁(yè)并發(fā)控制概述（續(xù)）數(shù)據(jù)不一致性：因?yàn)椴l(fā)操作破壞了事務(wù)隔離性并發(fā)控制就是要用正確方式調(diào)度并發(fā)操作，使一個(gè)用戶事務(wù)執(zhí)行不受其它事務(wù)干擾，從而防止造成數(shù)據(jù)不一致性并發(fā)控制第20頁(yè)并發(fā)控制概述（續(xù)）并發(fā)控制主要技術(shù)有封鎖(Locking)時(shí)間戳(Timestamp)樂觀控制法商用DBMS普通都采取封鎖方法并發(fā)控制第21頁(yè)三、封鎖1、什么是封鎖2、基本封鎖類型3、鎖相容矩陣并發(fā)控制第22頁(yè)1、什么是封鎖封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象（比如表、統(tǒng)計(jì)等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖加鎖后事務(wù)T就對(duì)該數(shù)據(jù)對(duì)象有了一定控制，在事務(wù)T釋放它鎖之前，其它事務(wù)不能更新此數(shù)據(jù)對(duì)象。并發(fā)控制第23頁(yè)2、基本封鎖類型一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后終究擁有什么樣控制由封鎖類型決定?；痉怄i類型排它鎖（ExclusiveLocks，簡(jiǎn)記為X鎖）共享鎖（ShareLocks，簡(jiǎn)記為S鎖）并發(fā)控制第24頁(yè)排它鎖排它鎖又稱為寫鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類型鎖，直到T釋放A上鎖確保其它事務(wù)在T釋放A上鎖之前不能再讀取和修改A并發(fā)控制第25頁(yè)共享鎖共享鎖又稱為讀鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則其它事務(wù)只能再對(duì)A加S鎖，而不能加X鎖，直到T釋放A上S鎖確保其它事務(wù)能夠讀A，但在T釋放A上S鎖之前不能對(duì)A做任何修改并發(fā)控制第26頁(yè)3、鎖相容矩陣Y=Yes，相容請(qǐng)求N=No，不相容請(qǐng)求

T1T2XS-XNNYSNYY-YYY并發(fā)控制第27頁(yè)鎖相容矩陣（續(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)求被拒絕并發(fā)控制第28頁(yè)使用封鎖機(jī)制處理丟失修改問題T1T2①XlockA②R(A)=16XlockA③A←A-1等候W(A)=15等候Commit等候UnlockA等候④取得XlockAR(A)=15A←A-1⑤W(A)=14CommitUnlockA例：事務(wù)T1在讀A進(jìn)行修改之前先對(duì)A加X鎖當(dāng)T2再請(qǐng)求對(duì)A加X鎖時(shí)被拒絕T2只能等候T1釋放A上鎖后T2取得對(duì)AX鎖這時(shí)T2讀到A已經(jīng)是T1更新過值15T2按此新A值進(jìn)行運(yùn)算，并將結(jié)果值A(chǔ)=14送回到磁盤。防止了丟失T1更新。沒有丟失修改并發(fā)控制第29頁(yè)使用封鎖機(jī)制處理不可重復(fù)讀問題T1T2①SlockASlockBR(A)=50R(B)=100求和=150②XlockB等候等候③R(A)=50等候R(B)=100等候求和=150等候Commit等候UnlockA等候UnlockB等候④取得XlockBR(B)=100B←B*2⑤W(B)=200CommitUnlockB事務(wù)T1在讀A，B之前，先對(duì)A，B加S鎖其它事務(wù)只能再對(duì)A，B加S鎖，而不能加X鎖，即其它事務(wù)只能讀A，B，而不能修改當(dāng)T2為修改B而申請(qǐng)對(duì)BX鎖時(shí)被拒絕只能等候T1釋放B上鎖T1為驗(yàn)算再讀A，B，這時(shí)讀出B仍是100，求和結(jié)果仍為150，即可重復(fù)讀T1結(jié)束才釋放A，B上S鎖。T2才取得對(duì)BX鎖可重復(fù)讀并發(fā)控制第30頁(yè)使用封鎖機(jī)制處理讀“臟”數(shù)據(jù)問題T1T2①XlockCR(C)=100C←C*2W(C)=200②SlockC等候③ROLLBACK等候(C恢復(fù)為100)等候UnlockC等候④取得SlockCR(C)=100⑤CommitCUnlockC例事務(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ù)

并發(fā)控制第31頁(yè)四、活鎖和死鎖封鎖技術(shù)能夠有效地處理并行操作一致性問題，但也帶來一些新問題死鎖活鎖并發(fā)控制第32頁(yè)1、活鎖事務(wù)T1封鎖了數(shù)據(jù)R事務(wù)T2又請(qǐng)求封鎖R，于是T2等候。T3也請(qǐng)求封鎖R，當(dāng)T1釋放了R上封鎖之后系統(tǒng)首先同意了T3請(qǐng)求，T2依然等候。T4又請(qǐng)求封鎖R，當(dāng)T3釋放了R上封鎖之后系統(tǒng)又同意了T4請(qǐng)求……T2有可能永遠(yuǎn)等候，這就是活鎖情形并發(fā)控制第33頁(yè)活鎖（續(xù)）活鎖并發(fā)控制第34頁(yè)活鎖（續(xù)）防止活鎖：采取先來先服務(wù)策略當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)按請(qǐng)求封鎖先后次序?qū)@些事務(wù)排隊(duì)該數(shù)據(jù)對(duì)象上鎖一旦釋放，首先同意申請(qǐng)隊(duì)列中第一個(gè)事務(wù)取得鎖并發(fā)控制第35頁(yè)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é)束，形成死鎖

并發(fā)控制第36頁(yè)死鎖（續(xù)）T1T2lockR1??LockR2??LockR2.?等候?等候LockR1等候等候等候等候?死鎖并發(fā)控制第37頁(yè)處理死鎖方法兩類方法1.預(yù)防死鎖2.死鎖診療與解除并發(fā)控制第38頁(yè)1.死鎖預(yù)防產(chǎn)生死鎖原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其它事務(wù)封鎖數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等候。預(yù)防死鎖發(fā)生就是要破壞產(chǎn)生死鎖條件并發(fā)控制第39頁(yè)死鎖預(yù)防（續(xù)）預(yù)防死鎖方法一次封鎖法次序封鎖法并發(fā)控制第40頁(yè)(1)一次封鎖法要求每個(gè)事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，不然就不能繼續(xù)執(zhí)行存在問題降低系統(tǒng)并發(fā)度難于事先準(zhǔn)確確定封鎖對(duì)象并發(fā)控制第41頁(yè)(2)次序封鎖法次序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象要求一個(gè)封鎖次序，全部事務(wù)都按這個(gè)次序?qū)嵤┓怄i。次序封鎖法存在問題維護(hù)成本數(shù)據(jù)庫(kù)系統(tǒng)中封鎖數(shù)據(jù)對(duì)象極多，而且在不停地改變。難以實(shí)現(xiàn)：極難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象

并發(fā)控制第42頁(yè)死鎖預(yù)防（續(xù)）結(jié)論在操作系統(tǒng)中廣為采取預(yù)防死鎖策略并不很適合數(shù)據(jù)庫(kù)特點(diǎn)DBMS在處理死鎖問題上更普遍采取是診療并解除死鎖方法并發(fā)控制第43頁(yè)2.死鎖診療與解除死鎖診療超時(shí)法事務(wù)等候圖法并發(fā)控制第44頁(yè)(1)超時(shí)法假如一個(gè)事務(wù)等候時(shí)間超出了要求時(shí)限，就認(rèn)為發(fā)生了死鎖優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)有可能誤判死鎖時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)覺并發(fā)控制第45頁(yè)(2)等候圖法用事務(wù)等候圖動(dòng)態(tài)反應(yīng)全部事務(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并發(fā)控制第46頁(yè)等候圖法（續(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，在大回路中又有小回路

并發(fā)控制第47頁(yè)等候圖法（續(xù)）并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等候圖，檢測(cè)事務(wù)。假如發(fā)覺圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。并發(fā)控制第48頁(yè)死鎖診療與解除（續(xù)）解除死鎖選擇一個(gè)處理死鎖代價(jià)最小事務(wù)，將其撤消釋放此事務(wù)持有全部鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去并發(fā)控制第49頁(yè)五、并發(fā)調(diào)度可串行性DBMS對(duì)并發(fā)事務(wù)不一樣調(diào)度可能會(huì)產(chǎn)生不一樣結(jié)果什么樣調(diào)度是正確？

并發(fā)控制第50頁(yè)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)度并發(fā)控制第51頁(yè)可串行化調(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)度策略并發(fā)控制第52頁(yè)串行化調(diào)度,正確調(diào)度T1T2SlockBY=R(B)=2UnlockBXlockAA=Y+1=3W(A)UnlockASlockAX=R(A)=3UnlockAXlockBB=X+1=4W(B)UnlockB串行調(diào)度(a)假設(shè)A、B初值均為2。按T1→T2次序執(zhí)行結(jié)果為A=3，B=4串行調(diào)度策略,正確調(diào)度并發(fā)控制第53頁(yè)串行化調(diào)度,正確調(diào)度T1T2SlockAX=R(A)=2UnlockAXlockBB=X+1=3W(B)UnlockBSlockBY=R(B)=3UnlockBXlockAA=Y+1=4W(A)UnlockA串行調(diào)度(b)假設(shè)A、B初值均為2。T2→T1次序執(zhí)行結(jié)果為B=3，A=4

串行調(diào)度策略,正確調(diào)度并發(fā)控制第54頁(yè)不可串行化調(diào)度，錯(cuò)誤調(diào)度T1T2SlockBY=R(B)=2SlockAX=R(A)=2UnlockBUnlockAXlockAA=Y+1=3W(A)XlockBB=X+1=3W(B)UnlockAUnlockB不可串行化調(diào)度

執(zhí)行結(jié)果與(a)、(b)結(jié)果都不一樣是錯(cuò)誤調(diào)度并發(fā)控制第55頁(yè)可串行化調(diào)度，正確調(diào)度T1T2SlockBY=R(B)=2UnlockBXlockASlockAA=Y+1=3等候W(A)等候UnlockA等候X=R(A)=3UnlockAXlockBB=X+1=4W(B)UnlockB可串行化調(diào)度

執(zhí)行結(jié)果與串行調(diào)度(a)執(zhí)行結(jié)果相同是正確調(diào)度并發(fā)控制第56頁(yè)2沖突可串行化調(diào)度可串行化調(diào)度充分條件一個(gè)調(diào)度Sc在確保沖突操作次序不變情況下，經(jīng)過交換兩個(gè)事務(wù)不沖突操作次序得到另一個(gè)調(diào)度Sc‘，假如Sc’是串行，稱調(diào)度Sc為沖突可串行化調(diào)度一個(gè)調(diào)度是沖突可串行化，一定是可串行化調(diào)度并發(fā)控制第57頁(yè)沖突可串行化調(diào)度（續(xù)）沖突操作沖突操作是指不一樣事務(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)并發(fā)控制第58頁(yè)沖突可串行化調(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)交換：Sc2＝r1(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)度并發(fā)控制第59頁(yè)沖突可串行化調(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)不滿足沖突可串行化。不過調(diào)度L2是可串行化，因?yàn)長(zhǎng)2執(zhí)行結(jié)果與調(diào)度L1相同，Y值都等于T2值，X值都等于T3值并發(fā)控制第60頁(yè)六、兩段鎖協(xié)議封鎖協(xié)議利用封鎖方法時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則何時(shí)申請(qǐng)封鎖持鎖時(shí)間何時(shí)釋放封鎖等兩段封鎖協(xié)議(Two-PhaseLocking，簡(jiǎn)稱2PL)是最慣用一個(gè)封鎖協(xié)議，理論上證實(shí)使用兩段封鎖協(xié)議產(chǎn)生是可串行化調(diào)度并發(fā)控制第61頁(yè)兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議指全部事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖

在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要取得對(duì)該數(shù)據(jù)封鎖在釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和取得任何其它封鎖并發(fā)控制第62頁(yè)兩段鎖協(xié)議（續(xù)）“兩段”鎖含義事務(wù)分為兩個(gè)階段第一階段是取得封鎖，也稱為擴(kuò)展階段事務(wù)能夠申請(qǐng)取得任何數(shù)據(jù)項(xiàng)上任何類型鎖，不過不能釋放任何鎖第二階段是釋放封鎖，也稱為收縮階段事務(wù)能夠釋放任何數(shù)據(jù)項(xiàng)上任何類型鎖，不過不能再申請(qǐng)任何鎖并發(fā)控制第63頁(yè)兩段鎖協(xié)議（續(xù)）例事務(wù)Ti恪守兩段鎖協(xié)議，其封鎖序列是：SlockASlockBXlockCUnlockBUnlockAUnlockC；|← 擴(kuò)展階段 →| |← 收縮階段→|事務(wù)Tj不恪守兩段鎖協(xié)議，其封鎖序列是：

SlockAUnlockASlockBXlockCUnlockCUnlockB；并發(fā)控制第64頁(yè)兩段鎖協(xié)議（續(xù)）事務(wù)T1事務(wù)T2Slock(A)R(A=260)Slock(C)R(C=300)Xlock(A)W(A=160)Xlock(C)W(C=250)Slock(A)Slock(B)等候R(B=1000)等候Xlock(B)等候W(B=1100)等候Unlock(A)等候R(A=160)Xlock(A)Unlock(B)W(A=210)Unlock(C)恪守兩段鎖協(xié)議可串行化調(diào)度左圖調(diào)度是恪守兩段鎖協(xié)議，所以一定是一個(gè)可串行化調(diào)度。并發(fā)控制第65頁(yè)兩段鎖協(xié)議（續(xù)）事務(wù)恪守兩段鎖協(xié)議是可串行化調(diào)度充分條件，而不是必要條件。若并發(fā)事務(wù)都恪守兩段鎖協(xié)議，則對(duì)這些事務(wù)任何并發(fā)調(diào)度策略都是可串行化若并發(fā)事務(wù)一個(gè)調(diào)度是可串行化，不一定全部事務(wù)都符合兩段鎖協(xié)議并發(fā)控制第66頁(yè)兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議與預(yù)防死鎖一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，不然就不能繼續(xù)執(zhí)行，所以一次封鎖法恪守兩段鎖協(xié)議不過兩段鎖協(xié)議并不要求事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，所以恪守兩段鎖協(xié)議事務(wù)可能發(fā)生死鎖并發(fā)控制第67頁(yè)兩段鎖協(xié)議（續(xù)）[例]恪守兩段鎖協(xié)議事務(wù)發(fā)生死鎖T1SlockBR(B)=2

XlockA等候等候T2

SlockAR(A)=2

XlockA等候恪守兩段鎖協(xié)議事務(wù)可能發(fā)生死鎖

并發(fā)控制第68頁(yè)七、封鎖粒度封鎖對(duì)象大小稱為封鎖粒度(Granularity)封鎖對(duì)象：邏輯單元，物理單元例：在關(guān)系數(shù)據(jù)庫(kù)中，封鎖對(duì)象：邏輯單元:屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理統(tǒng)計(jì)等并發(fā)控制第69頁(yè)選擇封鎖粒度標(biāo)準(zhǔn)封鎖粒度與系統(tǒng)并發(fā)度和并發(fā)控制開銷親密相關(guān)。封鎖粒度越大，數(shù)據(jù)庫(kù)所能夠封鎖數(shù)據(jù)單元就越少，并發(fā)度就越小，系統(tǒng)開銷也越小；封鎖粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越大并發(fā)控制第70頁(yè)選擇封鎖粒度標(biāo)準(zhǔn)（續(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è)元組加鎖，開銷極大并發(fā)控制第71頁(yè)選擇封鎖粒度標(biāo)準(zhǔn)（續(xù)）多粒度封鎖(MultipleGranularityLocking)在一個(gè)系統(tǒng)中同時(shí)支持各種封鎖粒度供不一樣事務(wù)選擇選擇封鎖粒度同時(shí)考慮封鎖開銷和并發(fā)度兩個(gè)原因，適當(dāng)選擇封鎖粒度需要處理多個(gè)關(guān)系大量元組用戶事務(wù)：以數(shù)據(jù)庫(kù)為封鎖單位需要處理大量元組用戶事務(wù)：以關(guān)系為封鎖單元只處理少許元組用戶事務(wù)：以元組為封鎖單位并發(fā)控制第72頁(yè)1、多粒度封鎖多粒度樹以樹形結(jié)構(gòu)來表示多級(jí)封鎖粒度根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小數(shù)據(jù)粒度

并發(fā)控制第73頁(yè)多粒度封鎖（續(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í)粒度樹并發(fā)控制第74頁(yè)多粒度封鎖協(xié)議允許多粒度樹中每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)全部后代結(jié)點(diǎn)也被加以一樣類型鎖在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：顯式封鎖和隱式封鎖并發(fā)控制第75頁(yè)顯式封鎖和隱式封鎖顯式封鎖:直接加到數(shù)據(jù)對(duì)象上封鎖隱式封鎖:該數(shù)據(jù)對(duì)象沒有獨(dú)立加鎖，是因?yàn)槠渖霞?jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖顯式封鎖和隱式封鎖效果是一樣并發(fā)控制第76頁(yè)顯式封鎖和隱式封鎖（續(xù)）系統(tǒng)檢驗(yàn)封鎖沖突時(shí)要檢驗(yàn)顯式封鎖還要檢驗(yàn)隱式封鎖比如事務(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必須等候

并發(fā)控制第77頁(yè)顯式封鎖和隱式封鎖（續(xù)）對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢驗(yàn)

該數(shù)據(jù)對(duì)象有沒有顯式封鎖與之沖突

全部上級(jí)結(jié)點(diǎn)檢驗(yàn)本事務(wù)顯式封鎖是否與該數(shù)據(jù)對(duì)象上隱式封鎖沖突：(由上級(jí)結(jié)點(diǎn)已加封鎖造成）全部下級(jí)結(jié)點(diǎn)看上面顯式封鎖是否與本事務(wù)隱式封鎖（將加到下級(jí)結(jié)點(diǎn)封鎖）沖突并發(fā)控制第78頁(yè)2、意向鎖引進(jìn)意向鎖（intentionlock）目標(biāo)提升對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢驗(yàn)效率并發(fā)控制第79頁(yè)意向鎖(續(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)系加意向鎖并發(fā)控