數(shù)據(jù)庫(kù)原理第11章

數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第十一章

并發(fā)控制1xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)2xuyuezhu@

(1)事務(wù)串行執(zhí)行每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn)多事務(wù)執(zhí)行方式3xuyuezhu@(2)交叉并發(fā)方式（interleavedconcurrency）事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運(yùn)行是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率4xuyuezhu@(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ā)方式，但受制于硬件環(huán)境更復(fù)雜的并發(fā)方式機(jī)制5xuyuezhu@事務(wù)并發(fā)執(zhí)行帶來的問題可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞事務(wù)的隔離性和數(shù)據(jù)庫(kù)的一致性DBMS必須提供并發(fā)控制機(jī)制并發(fā)控制機(jī)制是衡量一個(gè)DBMS性能的重要標(biāo)志之一6xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)7xuyuezhu@11.1并發(fā)控制概述并發(fā)控制機(jī)制的任務(wù)對(duì)并發(fā)操作進(jìn)行正確調(diào)度保證事務(wù)的隔離性保證數(shù)據(jù)庫(kù)的一致性8xuyuezhu@T1的修改被T2覆蓋了！

讀A=16

A←A-3寫回A=13①讀A=16

②

③A←A-1

寫回A=15

④事務(wù)T2事務(wù)T1數(shù)據(jù)不一致實(shí)例：飛機(jī)訂票系統(tǒng)9xuyuezhu@并發(fā)操作帶來的數(shù)據(jù)不一致性丟失修改（lostupdate）不可重復(fù)讀（non-repeatableread）讀“臟”數(shù)據(jù)（dirtyread）10xuyuezhu@圖11.1三種數(shù)據(jù)不一致性T1T2①讀A=16

②

③A←A-1

寫回A=15

④

讀A=16

A←A-1寫回A=15(a)丟失修改11xuyuezhu@1.丟失修改丟失修改是指事務(wù)1與事務(wù)2從數(shù)據(jù)庫(kù)中讀入同一數(shù)據(jù)并修改事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)果，導(dǎo)致事務(wù)1的修改被丟失。12xuyuezhu@圖11.1三種數(shù)據(jù)不一致性(續(xù))

讀B=100B←B*2寫回B=200

①

讀A=50

讀B=100

求和=150②

③讀A=50

讀B=200

求和=250(驗(yàn)算不對(duì))T2T1(b)不可重復(fù)讀13xuyuezhu@2.不可重復(fù)讀不可重復(fù)讀是指事務(wù)1讀取數(shù)據(jù)后，事務(wù)2執(zhí)行更新操作，使事務(wù)1無法再現(xiàn)前一次讀取結(jié)果。14xuyuezhu@三類不可重復(fù)讀事務(wù)1讀取某一數(shù)據(jù)后：1。事務(wù)2對(duì)其做了修改，當(dāng)事務(wù)1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值。2.事務(wù)2刪除了其中部分記錄，當(dāng)事務(wù)1再次讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄神密地消失了。3.事務(wù)2插入了一些記錄，當(dāng)事務(wù)1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄.

后兩種不可重復(fù)讀有時(shí)也稱為幻影現(xiàn)象（phantomrow）15xuyuezhu@圖11.1三種數(shù)據(jù)不一致性(續(xù))

讀C=200

①讀C=100C←C*2

寫回C②

③ROLLBACKC恢復(fù)為100T2T1(c)讀“臟”數(shù)據(jù)16xuyuezhu@3.讀“臟”數(shù)據(jù)事務(wù)1修改某一數(shù)據(jù)，并將其寫回磁盤事務(wù)2讀取同一數(shù)據(jù)后事務(wù)1由于某種原因被撤消，這時(shí)事務(wù)1已修改過的數(shù)據(jù)恢復(fù)原值事務(wù)2讀到的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)不一致，是不正確的數(shù)據(jù)，又稱為“臟”數(shù)據(jù)。17xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)18xuyuezhu@11.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣19xuyuezhu@一、什么是封鎖封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖加鎖后事務(wù)T就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)T釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對(duì)象。封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)20xuyuezhu@11.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣21xuyuezhu@二、基本封鎖類型DBMS通常提供了多種類型的封鎖。一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制是由封鎖的類型決定的?；痉怄i類型排它鎖（eXclusivelock，簡(jiǎn)記為X鎖）共享鎖（Sharelock，簡(jiǎn)記為S鎖）22xuyuezhu@

排它鎖

排它鎖又稱為寫鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類型的鎖，直到T釋放A上的鎖23xuyuezhu@共享鎖共享鎖又稱為讀鎖若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則其它事務(wù)只能再對(duì)A加S鎖，而不能加X鎖，直到T釋放A上的S鎖24xuyuezhu@11.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣25xuyuezhu@三、鎖的相容矩陣Y=Yes，相容的請(qǐng)求N=No，不相容的請(qǐng)求

T1T2XS-XNNYSNYY-YYY26xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)27xuyuezhu@11.3封鎖協(xié)議在運(yùn)用X鎖和S鎖對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，需要約定一些規(guī)則：封鎖協(xié)議（LockingProtocol）何時(shí)申請(qǐng)X鎖或S鎖持鎖時(shí)間、何時(shí)釋放不同的封鎖協(xié)議，在不同的程度上為并發(fā)操作的正確調(diào)度提供一定的保證常用的封鎖協(xié)議：三級(jí)封鎖協(xié)議28xuyuezhu@1級(jí)封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)R之前必須先對(duì)其加X鎖，直到事務(wù)結(jié)束才釋放正常結(jié)束（COMMIT）非正常結(jié)束（ROLLBACK）1級(jí)封鎖協(xié)議可防止丟失修改在1級(jí)封鎖協(xié)議中，如果是讀數(shù)據(jù)，不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。29xuyuezhu@1級(jí)封鎖協(xié)議T1T2①

XlockA

獲得②

讀A=16

③A←A-1

寫回A=15CommitUnlockA④

⑤

XlockA等待等待等待等待獲得XlockA讀A=15A←A-1寫回A=14CommitUnlockA

沒有丟失修改30xuyuezhu@1級(jí)封鎖協(xié)議

讀A=15①

XlockA

獲得②

讀A=16

A←A-1

寫回A=15③

④RollbackUnlockA

T2T1讀“臟”數(shù)據(jù)31xuyuezhu@1級(jí)封鎖協(xié)議

XlockB

獲得

讀B=100B←B*2

寫回B=200CommitUnlockB①讀A=50

讀B=100

求和=150②③讀A=50

讀B=200

求和=250(驗(yàn)算不對(duì))T2T1不可重復(fù)讀32xuyuezhu@

2級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)R前必須先加S鎖，讀完后即可釋放S鎖2級(jí)封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)。在2級(jí)封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀。33xuyuezhu@2級(jí)封鎖協(xié)議不可重復(fù)讀①

SclockA

獲得讀A=50UnlockA②SclockB

獲得讀B=100UnlockB③求和=150

XlockB等待等待獲得XlockB讀B=100B←B*2寫回B=200CommitUnlockBT2T1④SclockA

獲得讀A=50UnlockA

SclockB

獲得讀B=200UnlockB

求和=250(驗(yàn)算不對(duì))

T2T1(續(xù))34xuyuezhu@

3級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放3級(jí)封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復(fù)讀。35xuyuezhu@3級(jí)封鎖協(xié)議T1T2①

SlockA

讀A=50

SlockB

讀B=100

求和=150②

③讀A=50

讀B=100

求和=150CommitUnlockAUnlockB④

⑤

XlockB等待等待等待等待等待等待等待等待獲得XlockB讀B=100B←B*2寫回B=200CommitUnlockB

可重復(fù)讀36xuyuezhu@3級(jí)封鎖協(xié)議T1T2①

XlockC

讀C=100C←C*2

寫回C=200②

③ROLLBACK(C恢復(fù)為100)UnlockC④

⑤

SlockC等待等待等待等待獲得SlockC讀C=100CommitCUnlockC不讀“臟”數(shù)據(jù)37xuyuezhu@4．封鎖協(xié)議小結(jié)三級(jí)協(xié)議的主要區(qū)別什么操作需要申請(qǐng)封鎖何時(shí)釋放鎖（即持鎖時(shí)間）38xuyuezhu@封鎖協(xié)議小結(jié)(續(xù))39xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)40xuyuezhu@11.4活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題死鎖活鎖41xuyuezhu@11.4.1活鎖42xuyuezhu@如何避免活鎖采用先來先服務(wù)的策略：當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì)該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖。43xuyuezhu@11.4.2死鎖

T1T2

Xlock

R1...XlockR2等待等待等待...XlockR2..Xlock

R1等待等待.44xuyuezhu@

解決死鎖的方法

兩類方法1.預(yù)防死鎖2.死鎖的診斷與解除45xuyuezhu@1.死鎖的預(yù)防產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件46xuyuezhu@死鎖的預(yù)防（續(xù)）預(yù)防死鎖的方法一次封鎖法順序封鎖法47xuyuezhu@2.死鎖的診斷與解除允許死鎖發(fā)生解除死鎖由DBMS的并發(fā)控制子系統(tǒng)定期檢測(cè)系統(tǒng)中是否存在死鎖一旦檢測(cè)到死鎖，就要設(shè)法解除48xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)49xuyuezhu@11.5并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的50xuyuezhu@一、什么樣的并發(fā)操作調(diào)度是正確的計(jì)算機(jī)系統(tǒng)對(duì)并行事務(wù)中并行操作的調(diào)度是的隨機(jī)的，而不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果。將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。如果一個(gè)事務(wù)運(yùn)行過程中沒有其他事務(wù)在同時(shí)運(yùn)行，也就是說它沒有受到其他事務(wù)的干擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正常的或者預(yù)想的51xuyuezhu@什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）以不同的順序串行執(zhí)行事務(wù)也有可能會(huì)產(chǎn)生不同的結(jié)果，但由于不會(huì)將數(shù)據(jù)庫(kù)置于不一致狀態(tài)，所以都可以認(rèn)為是正確的。幾個(gè)事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同。這種并行調(diào)度策略稱為可串行化（Serializable）的調(diào)度。52xuyuezhu@什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）可串行性是并行事務(wù)正確性的唯一準(zhǔn)則例：現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作：事務(wù)1：讀B；A=B+1；寫回A；

事務(wù)2：讀A；B=A+1；寫回B；

假設(shè)A的初值為2，B的初值為2。53xuyuezhu@結(jié)果：A=3；B=4A=4；B=354xuyuezhu@11.5并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的55xuyuezhu@二、如何保證并發(fā)操作的調(diào)度是正確的為了保證并行操作的正確性，DBMS的并行控制機(jī)制必須提供一定的手段來保證調(diào)度是可串行化的。從理論上講，在某一事務(wù)執(zhí)行時(shí)禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡(jiǎn)單的調(diào)度策略，但這種方法實(shí)際上是不可行的，因?yàn)樗褂脩舨荒艹浞止蚕頂?shù)據(jù)庫(kù)資源。56xuyuezhu@如何保證并發(fā)操作的調(diào)度是正確的（續(xù)）保證并發(fā)操作調(diào)度正確性的方法封鎖方法：兩段鎖（Two-PhaseLocking，簡(jiǎn)稱2PL）協(xié)議時(shí)標(biāo)方法樂觀方法57xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)58xuyuezhu@11.6兩段鎖協(xié)議兩段鎖協(xié)議的內(nèi)容1.在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖2.在釋放一個(gè)封鎖之后，事務(wù)不再獲得任何其他封鎖。59xuyuezhu@第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)60xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖61xuyuezhu@11.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則62xuyuezhu@一、什么是封鎖粒度X鎖和S鎖都是加在某一個(gè)數(shù)據(jù)對(duì)象上的封鎖的對(duì)象:邏輯單元，物理單元例：在關(guān)系數(shù)據(jù)庫(kù)中，封鎖對(duì)象：邏輯單元:屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等63xuyuezhu@11.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則64xuyuezhu@二、選擇封鎖粒度的原則封鎖的粒度越大系統(tǒng)被封鎖的對(duì)象少并發(fā)度小系統(tǒng)開銷小選擇封鎖粒度：考慮封鎖機(jī)構(gòu)和并發(fā)度兩個(gè)因素對(duì)系統(tǒng)開銷與并發(fā)度進(jìn)行權(quán)衡小多高大65xuyuezhu@選擇封鎖粒度的原則（續(xù)）需要處理多個(gè)關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫(kù)為封鎖單位；需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元；只處理少量元組的用戶事務(wù)：以元組為封鎖單位66xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖67xuyuezhu@11.7.2多粒度封鎖多粒度樹以樹形結(jié)構(gòu)來表示多級(jí)封鎖粒度根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度

68xuyuezhu@11.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖69xuyuezhu@11.7.3意向鎖引進(jìn)意向鎖（intentionlock）目的提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率70xuyuezhu@什么是意向鎖對(duì)任一結(jié)點(diǎn)加基本鎖，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖71xuyuezhu@常用意向鎖意向共享鎖(IntentShareLock，簡(jiǎn)稱IS鎖)意向排它鎖(IntentExclusiveLock，簡(jiǎn)稱IX鎖)共享意向排它鎖(ShareIntentExclusiveLock，簡(jiǎn)稱SIX鎖)72xuyuezhu@意向鎖（續(xù)）意向鎖的相容矩陣

T1T2SXISIXSIX-

SYNYNNY