DB11數(shù)據(jù)庫教學(xué)市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

1、第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è) 第1頁不一樣多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其它事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源特點(diǎn)T1T2T3事務(wù)串行執(zhí)行方式第11章 并發(fā)控制第2頁(2)交叉并發(fā)方式（Interleaved Concurrency）在單處理機(jī)系統(tǒng)中，事務(wù)并行執(zhí)行是這些并行事務(wù)并行操作輪番交叉運(yùn)行單處理機(jī)系統(tǒng)中并行事務(wù)并沒有真正地并行運(yùn)行，但能夠降低處理機(jī)空閑時(shí)間，提升系統(tǒng)效率第11章 并發(fā)控制第3頁

2、事務(wù)交叉并發(fā)執(zhí)行方式第11章 并發(fā)控制第4頁 (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ā)控制第5頁事務(wù)并發(fā)執(zhí)行帶來問題會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)情況 可能會(huì)存取和存放不正確數(shù)據(jù)，破壞事務(wù)一致性和數(shù)據(jù)庫一致性第11章 并發(fā)控制第6頁并發(fā)控制概述封鎖活鎖和死鎖并發(fā)調(diào)度可串行性兩段鎖協(xié)議封鎖粒度第11章 并發(fā)控制第7頁11.1 并發(fā)控制概述并發(fā)控制機(jī)制任務(wù)對(duì)并發(fā)操作進(jìn)行正確調(diào)度確保事務(wù)隔離性確保數(shù)據(jù)庫一致性第8頁并發(fā)操作帶來數(shù)據(jù)不一致性實(shí)例例1飛機(jī)訂票系統(tǒng)

3、中一個(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ā)控制概述第9頁這種情況稱為數(shù)據(jù)庫不一致性，是由并發(fā)操作引發(fā)。在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)操作序列調(diào)度是隨機(jī)。若按上面調(diào)度序列執(zhí)行，甲事務(wù)修改就被丟失。原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)修改11.1 并發(fā)控制概述第10頁并發(fā)操作帶來數(shù)據(jù)不一致性丟失修改（

4、Lost Update）不可重復(fù)讀（Non-repeatable Read）讀“臟”數(shù)據(jù)（Dirty Read）記號(hào)R(x):讀數(shù)據(jù)xW(x):寫數(shù)據(jù)x 11.1 并發(fā)控制概述第11頁1. 丟失修改兩個(gè)事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2提交結(jié)果破壞了T1提交結(jié)果，造成T1修改被丟失。上面飛機(jī)訂票例子就屬這類11.1 并發(fā)控制概述第12頁T1T2 R(A)=16R(A)=16 AA-1 W(A)=15WAA-1W(A)=15丟失修改11.1 并發(fā)控制概述第13頁2. 不可重復(fù)讀不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。11.1 并發(fā)控制概述不可重復(fù)

5、讀包含三種情況：(1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，得到與前一次不一樣值 第14頁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，與第一次讀取值不一致 T1T2 R(A)=50R(B)=100求和=150R(B)=100BB*2(B)=200 R(A)=50R(B)=200和=250(驗(yàn)算不對(duì))不可重復(fù)讀 比如：11.1 并發(fā)控制概述第15頁(2)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了一些數(shù)據(jù)統(tǒng)計(jì)后，事務(wù)T2刪除了其中部分統(tǒng)計(jì)，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)覺一些統(tǒng)計(jì)消失了

6、(3)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取一些數(shù)據(jù)統(tǒng)計(jì)后，事務(wù)T2插入了一些統(tǒng)計(jì)，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)覺多了一些統(tǒng)計(jì)。 后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（Phantom Row）11.1 并發(fā)控制概述第16頁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ù)庫中數(shù)據(jù)不一致T2讀到數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確數(shù)據(jù) 11.1 并發(fā)控制概述第17頁T1T2 R(C)=100 CC*2 W(C)=200R(C)=200ROLLBACK C恢復(fù)為100比如讀“臟”數(shù)據(jù) T1

7、將C值修改為200，T2讀到C為200T1因?yàn)槟撤N原因撤消，其修改作廢，C恢復(fù)原值100這時(shí)T2讀到C為200，與數(shù)據(jù)庫內(nèi)容不一致，就是“臟”數(shù)據(jù) 11.1 并發(fā)控制概述第18頁數(shù)據(jù)不一致性：因?yàn)椴l(fā)操作破壞了事務(wù)隔離性并發(fā)控制就是要用正確方式調(diào)度并發(fā)操作，使一個(gè)用戶事務(wù)執(zhí)行不受其它事務(wù)干擾，從而防止造成數(shù)據(jù)不一致性 11.1 并發(fā)控制概述第19頁并發(fā)控制主要技術(shù)有封鎖(Locking)時(shí)間戳(Timestamp)樂觀控制法商用DBMS普通都采取封鎖方法 11.1 并發(fā)控制概述第20頁11.2 封鎖什么是封鎖基本封鎖類型鎖相容矩陣第21頁什么是封鎖封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象（比如表、統(tǒng)計(jì)等

8、）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖加鎖后事務(wù)T就對(duì)該數(shù)據(jù)對(duì)象有了一定控制，在事務(wù)T釋放它鎖之前，其它事務(wù)不能更新此數(shù)據(jù)對(duì)象。11.2 封鎖第22頁基本封鎖類型一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后終究擁有什么樣控制由封鎖類型決定?；痉怄i類型排它鎖（Exclusive Locks，簡(jiǎn)記為X鎖）共享鎖（Share Locks，簡(jiǎn)記為S鎖）11.2 封鎖第23頁排它鎖排它鎖又稱為寫鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類型鎖，直到T釋放A上鎖確保其它事務(wù)在T釋放A上鎖之前不能再讀取和修改A 11.2 封鎖第24頁共享鎖共享鎖又稱為讀鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加

9、上S鎖，則其它事務(wù)只能再對(duì)A加S鎖，而不能加X鎖，直到T釋放A上S鎖確保其它事務(wù)能夠讀A，但在T釋放A上S鎖之前不能對(duì)A做任何修改 11.2 封鎖第25頁鎖相容矩陣Y=Yes，相容請(qǐng)求N=No，不相容請(qǐng)求 T2 T1XS-XNNYSNYY-YYY11.2 封鎖第26頁在鎖相容矩陣中：最左邊一列表示事務(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 封鎖第27頁使用封鎖機(jī)制處理丟失

10、修改問題T1T2 Xlock A R(A)=16Xlock A AA-1等候 W(A)=15等候 Commit等候 Unlock A等候取得Xlock AR(A)=15AA-1W(A)=14CommitUnlock A例：事務(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更新。沒有丟失修改11.2 封鎖第28頁使用封鎖機(jī)制處理不可重復(fù)讀問題T1T2 Slock ASlock BR(A)=50R(B)=100求和=150Xlock

11、B等候等候 R(A)=50等候R(B)=100等候求和=150等候Commit等候Unlock A等候Unlock B等候取得XlockBR(B)=100BB*2W(B)=200CommitUnlock 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ì)BX鎖時(shí)被拒絕只能等候T1釋放B上鎖T1為驗(yàn)算再讀A，B，這時(shí)讀出B仍是100，求和結(jié)果仍為150，即可重復(fù)讀T1結(jié)束才釋放A，B上S鎖。T2才取得對(duì)BX鎖 可重復(fù)讀11.2 封鎖第29頁使用封鎖機(jī)制處理讀“臟”數(shù)據(jù)問題T1T2 Xlock CR(C)=

12、100CC*2W(C)=200Slock C等候 ROLLBACK等候(C恢復(fù)為100)等候Unlock C等候取得Slock CR(C)=100Commit CUnlock C例事務(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ù) 11.2 封鎖第30頁一級(jí)封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)之前必須先對(duì)其加X鎖，直到事務(wù)結(jié)束才釋放。二級(jí)封鎖協(xié)議一級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，讀完后即可釋放

13、S鎖。三級(jí)封鎖協(xié)議一級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放。11.2 封鎖對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，還需要約定一些規(guī)則，稱這些規(guī)則為封鎖協(xié)議第31頁11.3 活鎖和死鎖封鎖技術(shù)能夠有效地處理并行操作一致性問題，但也帶來一些新問題死鎖活鎖第32頁11.3.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)等候，這就是活鎖情形 第33頁活 鎖11.3.1 活鎖第34頁防止活鎖：采取先來先服務(wù)策略當(dāng)多個(gè)事務(wù)

14、請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)按請(qǐng)求封鎖先后次序?qū)@些事務(wù)排隊(duì)該數(shù)據(jù)對(duì)象上鎖一旦釋放，首先同意申請(qǐng)隊(duì)列中第一個(gè)事務(wù)取得鎖11.3.1 活鎖第35頁11.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é)束，形成死鎖 第36頁T1T2lock R1Lock R2Lock R2.等候等候Lock R1等候等候等候等候死鎖11.3.2 死鎖第37頁處理死鎖方法兩類方法1. 預(yù)防死鎖2. 死鎖診療與解

15、除11.3.2 死鎖第38頁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 死鎖第39頁預(yù)防死鎖方法 一次封鎖法 次序封鎖法11.3.2 死鎖第40頁(1)一次封鎖法要求每個(gè)事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，不然就不能繼續(xù)執(zhí)行存在問題降低系統(tǒng)并發(fā)度難于事先準(zhǔn)確確定封鎖對(duì)象11.3.2 死鎖第41頁(2)次序封鎖法次序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象要求一個(gè)封鎖次序，全部事務(wù)都按這個(gè)次序?qū)嵤┓怄i。次序封鎖法存在問題維護(hù)成本 數(shù)據(jù)庫系統(tǒng)中封鎖數(shù)據(jù)對(duì)象極多，而且在不停地改變。難以實(shí)

16、現(xiàn)：極難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象 11.3.2 死鎖第42頁結(jié)論在操作系統(tǒng)中廣為采取預(yù)防死鎖策略并不很適合數(shù)據(jù)庫特點(diǎn)DBMS在處理死鎖問題上更普遍采取是診療并解除死鎖方法11.3.2 死鎖第43頁2. 死鎖診療與解除死鎖診療超時(shí)法事務(wù)等候圖法 11.3.2 死鎖第44頁(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ā)覺11.3.2 死鎖第45頁(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ù)等候情況若

17、T1等候T2，則T1，T2之間劃一條有向邊，從T1指向T211.3.2 死鎖第46頁等候圖法（續(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 死鎖第47頁解除死鎖選擇一個(gè)處理死鎖代價(jià)最小事務(wù)，將其撤消釋放此事務(wù)持有全部鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等候圖，檢測(cè)事務(wù)。假如發(fā)覺圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖11.3.2 死鎖第48頁11.4 并發(fā)調(diào)度可串行性DBMS對(duì)并發(fā)事

18、務(wù)不一樣調(diào)度可能會(huì)產(chǎn)生不一樣結(jié)果什么樣調(diào)度是正確？第49頁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)度 第50頁例現(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)度第51頁T1T2Slock BY=R(B)=2Unlock BXlock AA=Y+1=3W(A)Unl

19、ock ASlock AX=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B串行調(diào)度(a)假設(shè)A、B初值均為2。按T1T2次序執(zhí)行結(jié)果為A=3，B=4 串行調(diào)度策略,正確調(diào)度 11.4.1 可串行化調(diào)度第52頁T1T2Slock AX=R(A)=2Unlock AXlock BB=X+1=3W(B)Unlock BSlock BY=R(B)=3Unlock BXlock AA=Y+1=4W(A)Unlock A串行調(diào)度(b)假設(shè)A、B初值均為2。T2T1次序執(zhí)行結(jié)果為B=3，A=4 串行調(diào)度策略,正確調(diào)度 11.4.1 可串行化調(diào)度第53頁T1T2Slock B

20、Y=R(B)=2Slock AX=R(A)=2Unlock BUnlock AXlock AA=Y+1=3W(A)Xlock BB=X+1=3W(B)Unlock AUnlock B不可串行化調(diào)度 執(zhí)行結(jié)果與(a)、(b)結(jié)果都不一樣是錯(cuò)誤調(diào)度 11.4.1 可串行化調(diào)度第54頁T1T2Slock BY=R(B)=2Unlock BXlock ASlock AA=Y+1=3等候W(A)等候Unlock A等候X=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B可串行化調(diào)度 執(zhí)行結(jié)果與串行調(diào)度(a)執(zhí)行結(jié)果相同是正確調(diào)度 11.4.1 可串行化調(diào)度第55頁11.4

21、.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)度第56頁沖突操作沖突操作是指不一樣事務(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)度第57頁例今有調(diào)度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2

22、(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)度第58頁11.5 兩段鎖協(xié)議封鎖協(xié)議 利用封鎖方法時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請(qǐng)封鎖持鎖時(shí)間何時(shí)釋放封鎖等兩段封鎖協(xié)議(Two-Phase Locking，簡(jiǎn)稱2PL)是最慣用一個(gè)封鎖協(xié)議，理論上證實(shí)使用兩段封鎖協(xié)議產(chǎn)生是

23、可串行化調(diào)度第59頁兩段鎖協(xié)議 指全部事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖 在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要取得對(duì)該數(shù)據(jù)封鎖 在釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和取得任何其它封鎖11.5 兩段鎖協(xié)議第60頁“兩段”鎖含義事務(wù)分為兩個(gè)階段 第一階段是取得封鎖，也稱為擴(kuò)展階段事務(wù)能夠申請(qǐng)取得任何數(shù)據(jù)項(xiàng)上任何類型鎖，不過不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段事務(wù)能夠釋放任何數(shù)據(jù)項(xiàng)上任何類型鎖，不過不能再申請(qǐng)任何鎖 11.5 兩段鎖協(xié)議第61頁例事務(wù)Ti恪守兩段鎖協(xié)議，其封鎖序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock

24、C；| 擴(kuò)展階段 | | 收縮階段 |事務(wù)Tj不恪守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B；11.5 兩段鎖協(xié)議第62頁事務(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)度左圖

25、調(diào)度是恪守兩段鎖協(xié)議，所以一定是一個(gè)可串行化調(diào)度11.5 兩段鎖協(xié)議第63頁事務(wù)恪守兩段鎖協(xié)議是可串行化調(diào)度充分條件，而不是必要條件。若并發(fā)事務(wù)都恪守兩段鎖協(xié)議，則對(duì)這些事務(wù)任何并發(fā)調(diào)度策略都是可串行化若并發(fā)事務(wù)一個(gè)調(diào)度是可串行化，不一定全部事務(wù)都符合兩段鎖協(xié)議 11.5 兩段鎖協(xié)議第64頁兩段鎖協(xié)議與預(yù)防死鎖一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，不然就不能繼續(xù)執(zhí)行，所以一次封鎖法恪守兩段鎖協(xié)議不過兩段鎖協(xié)議并不要求事務(wù)必須一次將全部要使用數(shù)據(jù)全部加鎖，所以恪守兩段鎖協(xié)議事務(wù)可能發(fā)生死鎖11.5 兩段鎖協(xié)議第65頁11.6 封鎖粒度封鎖對(duì)象大小稱為封鎖粒度(Gran

26、ularity) 封鎖對(duì)象：邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫中，封鎖對(duì)象：邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫等物理單元：頁（數(shù)據(jù)頁或索引頁）、物理統(tǒng)計(jì)等第66頁封鎖粒度與系統(tǒng)并發(fā)度和并發(fā)控制開銷親密相關(guān)。封鎖粒度越大，數(shù)據(jù)庫所能夠封鎖數(shù)據(jù)單元就越少，并發(fā)度就越小，系統(tǒng)開銷也越?。环怄i粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越大11.6 封鎖粒度選擇封鎖粒度標(biāo)準(zhǔn)第67頁例若封鎖粒度是數(shù)據(jù)頁，事務(wù)T1需要修改元組L1，則T1必須對(duì)包含L1整個(gè)數(shù)據(jù)頁A加鎖。假如T1對(duì)A加鎖后事務(wù)T2要修改A中元組L2，則T2被迫等候，直到T1釋放A。假如封鎖粒度是元組，則T1和

27、T2能夠同時(shí)對(duì)L1和L2加鎖，不需要相互等候，提升了系統(tǒng)并行度。又如，事務(wù)T需要讀取整個(gè)表，若封鎖粒度是元組，T必須對(duì)表中每一個(gè)元組加鎖，開銷極大 11.6 封鎖粒度第68頁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ù)：以元組為封鎖單位第69頁多粒度樹以樹形結(jié)構(gòu)來表示多級(jí)封鎖粒度根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫，表示最大數(shù)據(jù)粒度葉結(jié)點(diǎn)表示

28、最小數(shù)據(jù)粒度11.6.1 多粒度封鎖第70頁例：三級(jí)粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫子結(jié)點(diǎn)為關(guān)系，關(guān)系子結(jié)點(diǎn)為元組。數(shù)據(jù)庫關(guān)系Rn關(guān)系R1元組元組元組元組 三級(jí)粒度樹11.6.1 多粒度封鎖第71頁允許多粒度樹中每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)全部后代結(jié)點(diǎn)也被加以一樣類型鎖在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：顯式封鎖和隱式封鎖11.6.1 多粒度封鎖第72頁顯式封鎖: 直接加到數(shù)據(jù)對(duì)象上封鎖隱式封鎖: 該數(shù)據(jù)對(duì)象沒有獨(dú)立加鎖，是因?yàn)槠渖霞?jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖顯式封鎖和隱式封鎖效果是一樣11.6.1 多粒度封鎖第73頁系統(tǒng)檢驗(yàn)封鎖沖突時(shí)要檢驗(yàn)顯式封鎖還要檢驗(yàn)隱式封鎖比如事務(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 多粒度封鎖第74頁對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢驗(yàn) 該數(shù)據(jù)對(duì)象有沒有顯式封鎖與之沖突 全