并發(fā)控制技術(shù)

數(shù)據(jù)庫(kù)系統(tǒng)概AnIntroductiontoDatabase1 第十一章并發(fā)控2第十一章并發(fā)11.1小 11.1并發(fā)允許多個(gè)用戶(hù)同時(shí)使銀行數(shù)據(jù)庫(kù)系特點(diǎn)：在同一時(shí)刻并發(fā)運(yùn)行的事務(wù)數(shù)可 并發(fā)控制概多事務(wù)執(zhí)行事務(wù)串行執(zhí)每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事務(wù)必須等到這個(gè)事務(wù) 方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn) 事務(wù) 并發(fā)控制（續(xù)(2)交叉并發(fā)方式（interleaved事務(wù)的并行執(zhí)行是這些并行事務(wù)的并是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的 并發(fā)控制（續(xù) 事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)可能會(huì)存取和 不正確的數(shù)據(jù)，破壞 DBMS 并發(fā)并發(fā)控制機(jī)制的任對(duì)并發(fā)操作進(jìn)行保證事務(wù) 保證數(shù)據(jù)庫(kù)的一致 ①②R(A)③A←A-W(A)④T1的修改被T2覆蓋 并發(fā)操作帶丟失修改（lost不可重復(fù)讀（non-repeatable讀“臟”數(shù)據(jù)（dirty 丟失修丟失修改是指事務(wù)1與事務(wù)2從數(shù)據(jù)庫(kù)中讀入同一數(shù)據(jù)并修改，事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)果，導(dǎo)致事務(wù)1的修改被丟失。 丟失修①②③A←A-④A←A- 不可重復(fù)不可重復(fù)讀是指事務(wù)1 數(shù)據(jù)后，事務(wù)2執(zhí)行更新操作，使事務(wù)1無(wú)法再現(xiàn) 三類(lèi)不可重復(fù)事務(wù) 某一數(shù)據(jù)后 事務(wù)2對(duì)其做了修改，當(dāng)事務(wù)1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值。 不可重復(fù)①求和②③求和(驗(yàn)算不對(duì) 讀“臟”數(shù)事務(wù)1修改某一數(shù)據(jù)，并將其寫(xiě)回磁盤(pán)事務(wù)2 同一數(shù)據(jù)后，事務(wù)1由于某種原因被撤消，這 務(wù)1已修改過(guò)的數(shù)據(jù)恢復(fù)原值，事務(wù)2讀到的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)不一致，是不正確的數(shù)據(jù)，又稱(chēng)為“臟數(shù)據(jù)。 3讀“臟”數(shù)①R(W(C)=200②③C恢復(fù)為R(并發(fā)控制的主要技術(shù) 第十一章并發(fā)11.1小 一、什么二、基 類(lèi)三、基本鎖的相容 一、什么 就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖加鎖后事務(wù)就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對(duì)象。是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技 二、基 類(lèi)基 類(lèi)排它鎖（Exclusivelock，簡(jiǎn)記為X鎖排它鎖又稱(chēng)為寫(xiě) 二、基 類(lèi)共享鎖（Sharelock，簡(jiǎn)記為S鎖共享鎖又稱(chēng)為讀 二、基 類(lèi)修改數(shù)據(jù)時(shí)一般申請(qǐng)讀數(shù)據(jù)時(shí)一般申請(qǐng) SX三、鎖的相容矩SX-SX-SX

YYYY-YY-YNYNNNYY YY使 機(jī)制解決丟失修改問(wèn)例沒(méi)有丟失修①Xlock②這時(shí)T2讀到的A已經(jīng)T1更新過(guò)的值③A←A-等等等等④獲得XlockA←A-⑤使 機(jī)制解決不可重復(fù)讀問(wèn)SlockB求和②UnlockAUnlock

XlockB等

可重事務(wù)T1在讀A，BA，B加S T1為驗(yàn)算再讀A，B 獲得 2Unlock2

出的B仍是100，求150，即可重復(fù)T1結(jié)束才釋放A，B上的S鎖T2才獲得對(duì)B的X 例

不讀“臟①XlockC②③UnlockC④⑤

SlockC獲得SlockCommitCUnlockC

T1釋放C上的X鎖后T2獲得上的S鎖，讀C=100T2讀“臟第十一章并發(fā)11.1小 活鎖和死 活死 活 鎖之后系統(tǒng)又批準(zhǔn)了T4的請(qǐng)求…T2有 活 如何避免活采用先來(lái)先服務(wù)當(dāng)多個(gè)事務(wù)請(qǐng) 同一數(shù)據(jù)對(duì)象按請(qǐng) 的先后次序?qū)@些事務(wù)排該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn) 死死Xlock.....Xlock.Xlock等.Xlock等等等..解決死鎖的方兩類(lèi)方預(yù)防死死鎖 與解 預(yù)防死鎖的一 順 一 一次法存在的問(wèn)題： 順 順序，所有事務(wù)都按這個(gè)順序?qū)?。?法存在的問(wèn)題 成本 死鎖 與解 檢測(cè)死鎖：優(yōu)點(diǎn)缺 等待事務(wù)等待圖是一個(gè)有向圖T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)U為邊的集合若1等待2，則1，2之間劃一條有向邊，從1指向2 等待事務(wù)等待圖(a)中，事務(wù)T1等待T2，T2等待T1圖(b)中，事務(wù)T1等待T2，T2等待T3，T3等待T4，T4又等T1，產(chǎn)生了死圖(b)中，事務(wù)T3可能還等待T2 等待 死鎖 與解除（續(xù)解除死–選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將 第十一章并發(fā)11.1小 并發(fā) 一、什么樣的并發(fā)操作調(diào)度是正確計(jì)算機(jī)系統(tǒng)對(duì)并發(fā)事務(wù)中并發(fā)操作的調(diào)度是隨機(jī)的，而不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果。將所有事務(wù)串行起來(lái)的調(diào)度策略一定是正確的調(diào)度策略。以不同的順序串行執(zhí)行事務(wù)也有可能會(huì)產(chǎn)生不同的結(jié)果，但由于不會(huì)將數(shù)據(jù)庫(kù)置于不一致?tīng)顟B(tài)，所以都可以認(rèn)為是正確的。 什么樣的并發(fā)操作調(diào)度是正確的（續(xù)（Serializable）的調(diào)度可串行性是并發(fā)事務(wù)正確性的 什么樣的并發(fā)操作調(diào)度是正確的（續(xù)例：現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作：事務(wù)1：讀；1；寫(xiě)回A；事務(wù)2：讀；1；寫(xiě)回B；假設(shè)A的初值為2，B的初值為2 什么樣的并發(fā)操作調(diào)度是正確的（續(xù)對(duì)這兩個(gè)事務(wù)的不同串行執(zhí)串行調(diào)度策略1：T1串行調(diào)度策略2：T2交錯(cuò)執(zhí)不可串行化可串行化的調(diào) 讀B；A=B+1；寫(xiě)回讀A；B=A+1；寫(xiě)回SlockBUnlockBXlockAUnlockSlockUnlockAXlockBUnlock 讀B；A=B+1；寫(xiě)回讀A；B=A+1；寫(xiě)回UnlockAXlockBUnlockSlockUnlockBXlockAUnlock 讀B；A=B+1；寫(xiě)回讀A；B=A+1；寫(xiě)回SlockBSlockBSlockUnlockUnlockXlockXlockUnlockUnlock讀B；A=B+1；寫(xiě)回讀A；B=A+1；寫(xiě)回SlockBUnlockSlockBUnlockBXlockAUnlockSlock等UnlockAXlockBUnlock以是正確的調(diào)度并發(fā) 二、如何保證并發(fā)操作的調(diào)度發(fā)控制機(jī)制必須提供一定的來(lái)保證調(diào)保證 方法： 第十一章并發(fā)11.1小 兩段鎖協(xié)在運(yùn)用鎖和鎖對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，需要約定一些規(guī)則： 協(xié)議（LockingProtocol）何時(shí)申請(qǐng)X鎖或S 協(xié)議(Two-PhaseLocking，簡(jiǎn)稱(chēng)2PL) 兩段鎖協(xié)兩段鎖協(xié)議的內(nèi) 兩段鎖協(xié)議（續(xù)“兩段”鎖的含義：事務(wù)分為第一階段是獲 ，也稱(chēng)為擴(kuò)展階段第二階段是釋 ，也稱(chēng)為收縮階段 兩段鎖協(xié)議（續(xù)例事務(wù)1 序列SlockA...SlockB...XlockC...UnlockB...UnlockAUnlock事務(wù)2 序列SlockA...UnlockA...SlockB...XlockC...UnlockCUnlock事務(wù)1遵守兩段鎖協(xié)議，而事務(wù) 兩段鎖協(xié)議 兩段鎖協(xié)議（續(xù)并發(fā)執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的所有并發(fā)調(diào)度策略都是可串行化的。所有遵守兩段鎖協(xié)議的事務(wù)，其并發(fā)執(zhí)行的結(jié)果一定是正確的事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件可串行化的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)議。 兩段鎖協(xié)議（續(xù)SlockXlockUnlockUnlock

SlockASlockAXlockBUnlockBUnlock(a)遵守兩段 兩段鎖協(xié)議（續(xù)兩段鎖協(xié)議與防止死鎖的一 一次 法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次 法遵守兩段鎖協(xié)議有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖 兩段鎖協(xié)議（續(xù)圖11.9遵守兩段鎖協(xié)議的事務(wù)發(fā)Slock等Xlock等 第十一章并發(fā)11.1小 的粒粒意向 粒一、什么 粒二、選 粒度的原 一、什么 粒X鎖和S的對(duì)象:對(duì)象的大小稱(chēng) 的粒例：在關(guān)系數(shù)據(jù)庫(kù)中 對(duì)象邏輯單元屬性值、屬性值集合、元組、關(guān)系、物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等 什么 粒度（續(xù) 對(duì)某個(gè)屬性 粒一、什么 粒二、選 粒度的原 二、選 粒度的原的粒度 大，小系統(tǒng) 的對(duì)象 少，多并發(fā)度 小，高系統(tǒng)開(kāi)銷(xiāo) 小，大選 粒度 選 粒度的原則（續(xù)一般情況需要處理多個(gè)關(guān)系的大量元組的用戶(hù)事務(wù)：以數(shù)據(jù)庫(kù)為 粒度； 的粒粒意向 多粒多粒度以樹(shù)形結(jié)構(gòu)來(lái)表示多 粒葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒 多粒 （續(xù)例：三級(jí)粒度樹(shù)。根結(jié)點(diǎn)為數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。數(shù)據(jù)關(guān)系

關(guān)系

元 元組 元 多粒 協(xié)允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后 顯 和隱顯 :直接加到數(shù)據(jù)對(duì)象上 :由于其 顯 和隱 的效果是一樣 對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢檢查方法效該數(shù)檢查方法效有無(wú)顯 與所 結(jié) 所有下級(jí)結(jié)看上面的顯 是否與本事務(wù)的隱（將加到下級(jí)結(jié)點(diǎn) 的粒粒意向 意向引進(jìn)意向鎖（intentionlock）目–提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的 什么 意向鎖(續(xù)例：對(duì)任一r加鎖，先對(duì)關(guān)系R加意向鎖,事務(wù)T要對(duì)關(guān)系R加X(jué)鎖,系統(tǒng)只要檢查根結(jié)點(diǎn)不需要搜索和檢查R中的每一個(gè)元組提高了檢查效 意向共享鎖(IntentShareLock，簡(jiǎn)稱(chēng)意向排它鎖(IntentExclusiveLock，簡(jiǎn)共享意向排它鎖(ShareIntentExclusiveLock，簡(jiǎn)稱(chēng)SIX鎖) IS鎖：如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加IS鎖，表例：要對(duì)某個(gè)元組加S鎖，則要首先對(duì)關(guān) 鎖） 意向鎖（續(xù)意向鎖的相容矩SX-SYNYNNYXNNNNNYYNYYYYNNYYNYNNYNNY-YYYYYY意向鎖（續(xù)select*frommoviewheretitle=‘KingKong’;構(gòu)成的事務(wù)T1從獲得整個(gè)關(guān)系上的IS鎖開(kāi)始 兩部為KingKong的影片），并在它們中的每一個(gè)上獲得 意向鎖（續(xù) 務(wù)T2開(kāi)始，updatemoviesetyear=1939wheretitle=‘GonewiththeWind’;T2需要該關(guān)系上的一個(gè)IX鎖，因?yàn)樗蛩銥槠渲幸绘i被授予。當(dāng)T2來(lái)到關(guān)于GonewiththeWind的元組，試圖在kingkong影片之一的元組中寫(xiě)入新值，它將必須 意向鎖（續(xù)King King Gonewiththe如果寫(xiě)意向與讀意向涉及共同的元素，則允許在較低的層次上解決 。 意向鎖（續(xù)意向鎖的相容矩SX-SYNYNNYXNNNNNYYNYYYYNNYYNYNNYNNY-YYYYYY意向鎖（續(xù)鎖的強(qiáng)一個(gè)事務(wù)在申 時(shí)以強(qiáng)鎖代替弱鎖是安的，反之則不

- 意向鎖（續(xù)具有意向鎖的多粒 方申 時(shí)應(yīng)該按自上而下的次序進(jìn)行 意向鎖（續(xù)例如：事務(wù)T1要對(duì)關(guān)系R1加S要首先對(duì)數(shù)據(jù)庫(kù)加IS 意向鎖（續(xù)具有意向鎖的多粒 方減少了加鎖 的開(kāi) 第十一章并發(fā)11.1小 小數(shù)據(jù)共享與數(shù)據(jù)一致性數(shù)據(jù)庫(kù)的并發(fā)控制以數(shù)據(jù)庫(kù)的并發(fā)控制通常使 機(jī)– 小結(jié)（續(xù)并發(fā)控制機(jī)制調(diào)度并發(fā)事務(wù)操作是否正確的判別準(zhǔn)則是可串行性并發(fā)操作的正確性則通常由兩段鎖協(xié)議證。兩段鎖協(xié)議是可串行化調(diào)度的充分條件不是必要條件對(duì)數(shù)據(jù)對(duì)象施 ，帶來(lái)問(wèn)題：活鎖和死 練、設(shè)有兩個(gè)事務(wù)1、T2，其并發(fā)操作如圖所示，下面評(píng)價(jià)正確的是（）A.B.C.D. 練2、設(shè)有兩個(gè)事務(wù)T1、T2，其并發(fā)操作如圖所示，下面評(píng)價(jià)正確的是（）A.B.C.D. 練3、設(shè)有兩個(gè)事務(wù)T1、T2，其并發(fā)操作如圖所示，下面評(píng)價(jià)正確的是（）A.B.C.D. 練4、設(shè)有兩個(gè)事務(wù)T1、T2，面評(píng)價(jià)正確的是（）（ 練5、解決并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性問(wèn)題普遍采用(B.恢復(fù)C.存取控制D．協(xié)6、若事務(wù)T對(duì)數(shù)據(jù)R已加X(jué)鎖，則其他對(duì)數(shù)據(jù)R()。A.可以加S鎖不能加x鎖B.不能加S鎖可以加X(jué)鎖C.可以加S鎖也可以加x鎖D.不能加任何鎖、不允許任何其他事務(wù)對(duì)這個(gè)鎖定目標(biāo)再加任何類(lèi)型鎖的鎖是（）A.共享鎖B.排它鎖C.共享鎖或排它鎖D.以上都不是8、數(shù)據(jù)庫(kù)中的機(jī)制是