并發(fā)控制技術

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

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

XlockB等

可重事務T1在讀A，BA，B加S T1為驗算再讀A，B 獲得 2Unlock2

出的B仍是100，求150，即可重復T1結束才釋放A，B上的S鎖T2才獲得對B的X 例

不讀“臟①XlockC②③UnlockC④⑤

SlockC獲得SlockCommitCUnlockC

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

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

關系

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

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