1、數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論an introduction to database system第七章第七章 并發(fā)控制并發(fā)控制第七章第七章 并發(fā)控制并發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié) 并發(fā)控制概述并發(fā)控制概述多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行n每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行n不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn)并發(fā)控制并發(fā)控制(2)交叉并發(fā)方式（interleaved concurrency）n事務(wù)的并行執(zhí)

2、行是這些并行事務(wù)的并行操作輪流交叉運(yùn)行n是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率并發(fā)控制并發(fā)控制(3)同時(shí)并發(fā)方式（simultaneous concurrency）n多處理機(jī)系統(tǒng)中，每個(gè)處理機(jī)可以運(yùn)行一個(gè)事務(wù)，多個(gè)處理機(jī)可以同時(shí)運(yùn)行多個(gè)事務(wù)，實(shí)現(xiàn)多個(gè)事務(wù)真正的并行運(yùn)行n最理想的并發(fā)方式，但受制于硬件環(huán)境n更復(fù)雜的并發(fā)方式機(jī)制事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)題事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)題n可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞事務(wù)的隔離性和數(shù)據(jù)庫(kù)的一致性ndbms必須提供并發(fā)控制機(jī)制n并發(fā)控制機(jī)制是衡量一個(gè)dbms性能的重要標(biāo)志之一7.1 7.1 并發(fā)控制概述并發(fā)控制概述n并發(fā)控制機(jī)制的

3、任務(wù)n對(duì)并發(fā)操作進(jìn)行正確調(diào)度n保證事務(wù)的隔離性n保證數(shù)據(jù)庫(kù)的一致性t1的修改被的修改被t2覆蓋了！覆蓋了！ 讀a=16 aa-3寫(xiě)回a=13 讀a=16 aa-1 寫(xiě)回a=15 事務(wù) t2事務(wù) t1數(shù)據(jù)不一致實(shí)例：飛機(jī)訂票系統(tǒng)數(shù)據(jù)不一致實(shí)例：飛機(jī)訂票系統(tǒng)并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性n丟失修改（lost update）n不可重復(fù)讀（non-repeatable read）n讀“臟”數(shù)據(jù)（dirty read）1. 丟失修改丟失修改丟失修改是指事務(wù)1與事務(wù)2從數(shù)據(jù)庫(kù)中讀入同一數(shù)據(jù)并修改事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)果，導(dǎo)致事務(wù)1的修改被丟失。2. 不可重復(fù)讀不可重復(fù)讀

4、不可重復(fù)讀是指事務(wù)1讀取數(shù)據(jù)后，事務(wù)2執(zhí)行更新操作，使事務(wù)1無(wú)法再現(xiàn)前一次讀取結(jié)果。三類(lèi)三類(lèi)不可重復(fù)讀不可重復(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í)也稱(chēng)為幻影現(xiàn)象（phantom row）3. 讀讀“臟臟”數(shù)據(jù)數(shù)據(jù)事務(wù)1修改某一數(shù)據(jù)，并將其寫(xiě)回磁盤(pán)事務(wù)2讀取同一數(shù)據(jù)后事務(wù)1由于某種原因被撤消，這時(shí)事務(wù)1已修改過(guò)的數(shù)據(jù)恢復(fù)原值事務(wù)2讀到的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)不

5、一致，是不正確的數(shù)據(jù)，又稱(chēng)為“臟”數(shù)據(jù)。圖圖7.1 三種數(shù)據(jù)不一致性三種數(shù)據(jù)不一致性 t1t2 讀a=16 aa-1 寫(xiě)回a=15 讀a=16 aa-1寫(xiě)回a=15(a) 丟失修改丟失修改圖圖7.1 三種數(shù)據(jù)不一致性三種數(shù)據(jù)不一致性(續(xù)續(xù)) 讀b=100 bb*2寫(xiě)回b=200 讀a=50 讀b=100 求和=150 讀a=50 讀b=200 求和=250 (驗(yàn)算不對(duì)) t2t1(b) 不可重復(fù)讀不可重復(fù)讀圖圖7.1 三種數(shù)據(jù)不一致性三種數(shù)據(jù)不一致性(續(xù)續(xù)) 讀c=200 讀c=100 cc*2 寫(xiě)回c rollback c恢復(fù)為100t2t1(c) 讀讀“臟臟”數(shù)據(jù)數(shù)據(jù)第七章第七章 并發(fā)控制

6、并發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.2 封鎖封鎖一、什么是封鎖二、基本封鎖類(lèi)型三、基本鎖的相容矩陣一、什么是封鎖一、什么是封鎖n封鎖就是事務(wù)t在對(duì)某個(gè)數(shù)據(jù)對(duì)象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖n加鎖后事務(wù)t就對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)t釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對(duì)象。n封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)7.2 封鎖封鎖一、什么是封鎖二、基本封鎖類(lèi)型三、基本鎖的相容矩陣二、基本封鎖類(lèi)型二、基本封鎖類(lèi)型ndb

7、ms通常提供了多種類(lèi)型的封鎖。一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制是由封鎖的類(lèi)型決定的。n基本封鎖類(lèi)型n排它鎖（exclusive lock，簡(jiǎn)記為x鎖）n共享鎖（share lock，簡(jiǎn)記為s鎖）排它鎖排它鎖n排它鎖又稱(chēng)為寫(xiě)鎖n若事務(wù)t對(duì)數(shù)據(jù)對(duì)象a加上x(chóng)鎖，則只允許t讀取和修改a，其它任何事務(wù)都不能再對(duì)a加任何類(lèi)型的鎖，直到t釋放a上的鎖共享鎖共享鎖n共享鎖又稱(chēng)為讀鎖n若事務(wù)t對(duì)數(shù)據(jù)對(duì)象a加上s鎖，則其它事務(wù)只能再對(duì)a加s鎖，而不能加x鎖，直到t釋放a上的s鎖7.2 封鎖封鎖一、什么是封鎖二、基本封鎖類(lèi)型三、基本鎖的相容矩陣三、鎖的相容矩陣三、鎖的相容矩陣y=yes，相容的請(qǐng)求，

8、相容的請(qǐng)求n=no，不相容的請(qǐng)求，不相容的請(qǐng)求 t1 t2xs-xnnysnyy-yyy第七章第七章 并發(fā)控制并發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.3 封鎖協(xié)議封鎖協(xié)議n在運(yùn)用x鎖和s鎖對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，需要約定一些規(guī)則：封鎖協(xié)議（locking protocol） n何時(shí)申請(qǐng)x鎖或s鎖n持鎖時(shí)間、何時(shí)釋放n 不同的封鎖協(xié)議，在不同的程度上為并發(fā)操 作的正確調(diào)度提供一定的保證n常用的封鎖協(xié)議：三級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議n事務(wù)t在修改數(shù)據(jù)r之前必

9、須先對(duì)其加x鎖，直到事務(wù)結(jié)束才釋放n正常結(jié)束（commit）n非正常結(jié)束（rollback）n1級(jí)封鎖協(xié)議可防止丟失修改n在1級(jí)封鎖協(xié)議中，如果是讀數(shù)據(jù)，不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。1級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議t1t2 xlock a 獲得 讀a=16 aa-1 寫(xiě)回a=15 commit unlock a xlock a等待等待等待等待獲得xlock a讀a=15aa-1寫(xiě)回a=14commitunlock a 沒(méi)有丟失修改沒(méi)有丟失修改 1級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議 讀a=15 xlock a 獲得 讀a=16 aa-1 寫(xiě)回a=15 rollbackunlock a t2t1

10、讀讀“臟臟”數(shù)據(jù)數(shù)據(jù)1級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議 xlock b 獲得 讀b=100 bb*2 寫(xiě)回b=200 commit unlock b讀a=50 讀b=100 求和=150讀a=50 讀b=200 求和=250 (驗(yàn)算不對(duì)) t2t1不可重復(fù)讀不可重復(fù)讀 2級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議n1級(jí)封鎖協(xié)議+事務(wù)t在讀取數(shù)據(jù)r前必須先加s鎖，讀完后即可釋放s鎖n2級(jí)封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)。n在2級(jí)封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放s鎖，所以它不能保證可重復(fù)讀。2級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議不可重復(fù)讀不可重復(fù)讀 sclock a 獲得 讀a=50 unlock a sclock b 獲得 讀b=100

11、 unlock b 求和=150 xlock b等待等待獲得xlock b讀b=100bb*2寫(xiě)回b=200commitunlock bt2t1sclock a 獲得 讀a=50 unlock a sclock b 獲得 讀b=200 unlock b 求和=250 (驗(yàn)算不對(duì)) t2t1 (續(xù)) 3級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議n1級(jí)封鎖協(xié)議 + 事務(wù)t在讀取數(shù)據(jù)r之前必須先對(duì)其加s鎖，直到事務(wù)結(jié)束才釋放n3級(jí)封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復(fù)讀。3級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議t1t2 slock a 讀a=50 slock b 讀b=100 求和=150 讀a=50 讀b=100 求和=150 co

12、mmit unlock a unlock b xlock b等待等待等待 等待等待等待等待等待獲得xlock b讀b=100bb*2寫(xiě)回b=200commitunlock b 可重復(fù)讀可重復(fù)讀 3級(jí)封鎖協(xié)議級(jí)封鎖協(xié)議t1t2 xlock c 讀c= 100 cc*2 寫(xiě)回c=200 rollback (c恢復(fù)為100) unlock c slock c等待等待等待等待獲得slock c讀c=100commit cunlock c不讀不讀“臟臟”數(shù)據(jù)數(shù)據(jù) 4封鎖協(xié)議小結(jié)封鎖協(xié)議小結(jié)n三級(jí)協(xié)議的主要區(qū)別n什么操作需要申請(qǐng)封鎖n何時(shí)釋放鎖（即持鎖時(shí)間）封鎖協(xié)議小結(jié)封鎖協(xié)議小結(jié)第七章第七章 并發(fā)控制并

13、發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.4 活鎖和死鎖活鎖和死鎖n封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)題，但也帶來(lái)一些新的問(wèn)題n死鎖n活鎖7.4.1 活鎖活鎖如何避免活鎖如何避免活鎖采用先來(lái)先服務(wù)的策略：當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)n按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì)n該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖。7.4.2 死鎖死鎖t1 t2 xlock r1.xlock r2等待等待等待等待等待等待.xlock r2.xlock

14、 r1等待等待等待等待.解決死鎖的方法解決死鎖的方法兩類(lèi)方法1. 預(yù)防死鎖2. 死鎖的診斷與解除1. 死鎖的預(yù)防死鎖的預(yù)防n產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。n預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件死鎖的預(yù)防死鎖的預(yù)防預(yù)防死鎖的方法n 一次封鎖法n 順序封鎖法（1）一次封鎖法）一次封鎖法n要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行n一次封鎖法存在的問(wèn)題：降低并發(fā)度n 擴(kuò)大封鎖范圍n將以后要用到的全部數(shù)據(jù)加鎖，勢(shì)必?cái)U(kuò)大了封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度一次封鎖法一次封鎖法n難于事先精確確定

15、封鎖對(duì)象n數(shù)據(jù)庫(kù)中數(shù)據(jù)是不斷變化的，原來(lái)不要求封鎖的數(shù)據(jù)，在執(zhí)行過(guò)程中可能會(huì)變成封鎖對(duì)象，所以很難事先精確地確定每個(gè)事務(wù)所要封鎖的數(shù)據(jù)對(duì)象n解決方法：將事務(wù)在執(zhí)行過(guò)程中可能要封鎖的數(shù)據(jù)對(duì)象全部加鎖，這就進(jìn)一步降低了并發(fā)度。（2）順序封鎖法）順序封鎖法n順序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。n順序封鎖法存在的問(wèn)題n 維護(hù)成本高n數(shù)據(jù)庫(kù)系統(tǒng)中可封鎖的數(shù)據(jù)對(duì)象極其眾多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護(hù)這樣極多而且變化的資源的封鎖順序非常困難，成本很高順序封鎖法順序封鎖法n難于實(shí)現(xiàn)n事務(wù)的封鎖請(qǐng)求可以隨著事務(wù)的執(zhí)行而動(dòng)態(tài)地決定，很難事先確定每一個(gè)事務(wù)

16、要封鎖哪些對(duì)象，因此也就很難按規(guī)定的順序去施加封鎖。 例：規(guī)定數(shù)據(jù)對(duì)象的封鎖順序?yàn)閍,b,c,d,e。事務(wù)t3起初要求封鎖數(shù)據(jù)對(duì)象b,c,e，但當(dāng)它封鎖了b,c后，才發(fā)現(xiàn)還需要封鎖a，這樣就破壞了封鎖順序.死鎖的預(yù)防死鎖的預(yù)防n結(jié)論n在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫(kù)的特點(diǎn)ndbms在解決死鎖的問(wèn)題上更普遍采用的是診斷并解除死鎖的方法2. 死鎖的診斷與解除死鎖的診斷與解除n允許死鎖發(fā)生n解除死鎖n由dbms的并發(fā)控制子系統(tǒng)定期檢測(cè)系統(tǒng)中是否存在死鎖n一旦檢測(cè)到死鎖，就要設(shè)法解除檢測(cè)死鎖：檢測(cè)死鎖：超時(shí)法超時(shí)法n如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖n優(yōu)點(diǎn)：實(shí)

17、現(xiàn)簡(jiǎn)單n缺點(diǎn)n有可能誤判死鎖n時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)等待圖法等待圖法n用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況n事務(wù)等待圖是一個(gè)有向圖g=(t，u)nt為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)nu為邊的集合，每條邊表示事務(wù)等待的情況n若t1等待t2，則t1，t2之間劃一條有向邊，從t1指向t2n并發(fā)控制子系統(tǒng)周期性地（比如每隔1 min）檢測(cè)事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。死鎖的診斷與解除死鎖的診斷與解除n解除死鎖n選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消，釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去。第七章第七章 并發(fā)控制并發(fā)控制7.1 并發(fā)控制

18、概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.5 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的7.5 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的一、什么樣的并發(fā)操作調(diào)度是正確的一、什么樣的并發(fā)操作調(diào)度是正確的n計(jì)算機(jī)系統(tǒng)對(duì)并行事務(wù)中并行操作的調(diào)度是的隨機(jī)的，而不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果。n將所有事務(wù)串行起來(lái)的調(diào)度策略一定是正確的調(diào)度策略。n如果一個(gè)事務(wù)運(yùn)行過(guò)程中沒(méi)

19、有其他事務(wù)在同時(shí)運(yùn)行，也就是說(shuō)它沒(méi)有受到其他事務(wù)的干擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正常的或者預(yù)想的什么樣的并發(fā)操作調(diào)度是正確的什么樣的并發(fā)操作調(diào)度是正確的n以不同的順序串行執(zhí)行事務(wù)也有可能會(huì)產(chǎn)生不同的結(jié)果，但由于不會(huì)將數(shù)據(jù)庫(kù)置于不一致?tīng)顟B(tài)，所以都可以認(rèn)為是正確的。n 幾個(gè)事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同。這種并行調(diào)度策略稱(chēng)為可串行化（serializable）的調(diào)度。什么樣的并發(fā)操作調(diào)度是正確的什么樣的并發(fā)操作調(diào)度是正確的n可串行性是并行事務(wù)正確性的唯一準(zhǔn)則例：現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作： 事務(wù)1：讀b；a=b+1；寫(xiě)回a； 事務(wù)2：讀a

20、；b=a+1；寫(xiě)回b； 假設(shè)a的初值為2，b的初值為2。什么樣的并發(fā)操作調(diào)度是正確的什么樣的并發(fā)操作調(diào)度是正確的n對(duì)這兩個(gè)事務(wù)的不同調(diào)度策略n串行執(zhí)行n串行調(diào)度策略1n串行調(diào)度策略2n交錯(cuò)執(zhí)行n不可串行化的調(diào)度n可串行化的調(diào)度(a) 串行調(diào)度策略，正確的調(diào)度串行調(diào)度策略，正確的調(diào)度slock by=b=2unlock bxlock aa=y+1寫(xiě)回寫(xiě)回a(=3)unlock a slock ax=a=3unlock axlock bb=x+1寫(xiě)回寫(xiě)回b(=4)unlock b t1t2(b) 串行調(diào)度策略，正確的調(diào)度串行調(diào)度策略，正確的調(diào)度 slock by=b=3unlock bxlock

21、aa=y+1寫(xiě)回寫(xiě)回a(=4)unlock a slocka x=a=2unlock axlock bb=x+1寫(xiě)回寫(xiě)回b(=3)unlock b t1t2(c) 不可串行化的調(diào)度不可串行化的調(diào)度slock by=b=2 unlock b xlock aa=y+1寫(xiě)回寫(xiě)回a(=3) unlock a slock ax=a=2 unlock a xlock bb=x+1寫(xiě)回寫(xiě)回b(=3) unlock b t1t2(c) 不可串行化的調(diào)度不可串行化的調(diào)度n由于其執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同，所以是錯(cuò)誤的調(diào)度。(d) 可串行化的調(diào)度可串行化的調(diào)度slock by=b=2unlock bxl

22、ock a a=y+1寫(xiě)回寫(xiě)回a(=3)unlock a slock a 等待等待 等待等待 等待等待x=a=3unlock axlock bb=x+1寫(xiě)回寫(xiě)回b(=4)unlock b t1t2(d) 可串行化的調(diào)度可串行化的調(diào)度n由于其執(zhí)行結(jié)果與串行調(diào)度（a）的執(zhí)行結(jié)果相同，所以是正確的調(diào)度。7.5 并發(fā)調(diào)度的可串行性并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的n為了保證并行操作的正確性，dbms的并行控制機(jī)制必須提供一定的手段來(lái)保證調(diào)度是可串行化的。n從理論上講，在某一事務(wù)執(zhí)行時(shí)禁

23、止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡(jiǎn)單的調(diào)度策略，但這種方法實(shí)際上是不可行的，因?yàn)樗褂脩舨荒艹浞止蚕頂?shù)據(jù)庫(kù)資源。如何保證并發(fā)操作的調(diào)度是正確的如何保證并發(fā)操作的調(diào)度是正確的n保證并發(fā)操作調(diào)度正確性的方法n封鎖方法：兩段鎖（two-phase locking，簡(jiǎn)稱(chēng)2pl）協(xié)議n時(shí)標(biāo)方法n樂(lè)觀方法第七章第七章 并發(fā)控制并發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.6 兩段鎖協(xié)議兩段鎖協(xié)議n兩段鎖協(xié)議的內(nèi)容1. 在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫(xiě)操作之前，

24、事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖2. 在釋放一個(gè)封鎖之后，事務(wù)不再獲得任何其他封鎖。兩段鎖協(xié)議兩段鎖協(xié)議n“兩段”鎖的含義n事務(wù)分為兩個(gè)階段n 第一階段是獲得封鎖，也稱(chēng)為擴(kuò)展階段；n 第二階段是釋放封鎖，也稱(chēng)為收縮階段。兩段鎖協(xié)議兩段鎖協(xié)議例：事務(wù)1的封鎖序列：slock a . slock b . xlock c . unlock b . unlock a . unlock c；事務(wù)2的封鎖序列：slock a . unlock a . slock b . xlock c . unlock c . unlock b；事務(wù)1遵守兩段鎖協(xié)議，而事務(wù)2不遵守兩段協(xié)議。兩段鎖協(xié)議兩段鎖協(xié)議n并行執(zhí)行的所

25、有事務(wù)均遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的所有并行調(diào)度策略都是可串行化的。所有遵守兩段鎖協(xié)議的事務(wù)，其并行執(zhí)行的結(jié)果一定是正確的n事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件n可串行化的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)議。兩段鎖協(xié)議兩段鎖協(xié)議t1slock b讀b=2y=bxlock a a=y+1寫(xiě)回a=3unlock bunlock a t2 slock a 等待等待 等待等待 等待等待 等待等待 等待等待slock a讀讀a=3y=a xlock bb=y+1寫(xiě)回寫(xiě)回b=4unlock bunlock a t1slock b讀讀b=2y=bunlock bxlock a

26、 a=y+1寫(xiě)回寫(xiě)回a=3unlock a t2 slock a等待等待等待等待等待等待等待等待slock a讀讀a=3x=aunlock axlock bb=x+1寫(xiě)回寫(xiě)回b=4unlock b (a) 遵守兩段鎖協(xié)議遵守兩段鎖協(xié)議 (b) 不遵守兩段鎖協(xié)議不遵守兩段鎖協(xié)議 t1slock b讀讀b=2y=bunlock bxlock aa=y+1寫(xiě)回寫(xiě)回a=3unlock at2 slock a讀讀a=2x=aunlock axlock b等待等待xlock bb=x+1寫(xiě)回寫(xiě)回b=3unlock b (c) 不遵守兩段鎖協(xié)議不遵守兩段鎖協(xié)議 兩段鎖協(xié)議兩段鎖協(xié)議n兩段鎖協(xié)議與防止死鎖的一

27、次封鎖法n一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議n但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖兩段鎖協(xié)議兩段鎖協(xié)議圖8.7 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖t1slock b讀讀b=2 xlock a等待等待等待等待t2 slock a讀讀a=2 xlock a等待等待兩段鎖協(xié)議兩段鎖協(xié)議n兩段鎖協(xié)議與三級(jí)封鎖協(xié)議n兩類(lèi)不同目的的協(xié)議n兩段鎖協(xié)議n保證并發(fā)調(diào)度的正確性n三級(jí)封鎖協(xié)議n在不同程度上保證數(shù)據(jù)一致性n遵守第三級(jí)封鎖協(xié)議必然遵守兩段協(xié)議第七章第七章 并發(fā)控制并發(fā)控制7.

28、1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.7 封鎖的粒度封鎖的粒度7.7.1 封鎖粒度7.7.2 多粒度封鎖7.7.3 意向鎖7.7.1 封鎖粒度封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則一、什么是封鎖粒度一、什么是封鎖粒度nx鎖和s鎖都是加在某一個(gè)數(shù)據(jù)對(duì)象上的n封鎖的對(duì)象:邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫(kù)中，封鎖對(duì)象：n邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等n物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等什么是封鎖粒度什么是

29、封鎖粒度n封鎖對(duì)象可以很大也可以很小 例： 對(duì)整個(gè)數(shù)據(jù)庫(kù)加鎖 對(duì)某個(gè)屬性值加鎖n封鎖對(duì)象的大小稱(chēng)為封鎖的粒度(granularity)n多粒度封鎖(multiple granularity locking)n在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇7.7.1 封鎖粒度封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則二、選擇封鎖粒度的原則二、選擇封鎖粒度的原則n封鎖的粒度越 大，小，n系統(tǒng)被封鎖的對(duì)象 少，多，n并發(fā)度 小，高，n系統(tǒng)開(kāi)銷(xiāo) 小，大，n選擇封鎖粒度：考慮封鎖機(jī)構(gòu)和并發(fā)度兩個(gè)因素對(duì)系統(tǒng)開(kāi)銷(xiāo)與并發(fā)度進(jìn)行權(quán)衡選擇封鎖粒度的原則選擇封鎖粒度的原則n需要處理多個(gè)關(guān)系的大量元組的用戶事

30、務(wù)：以數(shù)據(jù)庫(kù)為封鎖單位；n需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元；n只處理少量元組的用戶事務(wù)：以元組為封鎖單位7.7 封鎖的粒度封鎖的粒度7.7.1 封鎖粒度7.7.2 多粒度封鎖7.7.3 意向鎖7.7.2 多粒度封鎖多粒度封鎖n多粒度樹(shù)n以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度n根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度n葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度 多粒度封鎖多粒度封鎖例：三級(jí)粒度樹(shù)。根結(jié)點(diǎn)為數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)關(guān)系關(guān)系rn關(guān)系關(guān)系r1元組元組元組元組元組元組元組元組多粒度多粒度封鎖協(xié)議封鎖協(xié)議n 允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖n對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)

31、結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類(lèi)型的鎖n在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：顯式封鎖和隱式封鎖顯式封鎖和隱式封鎖顯式封鎖和隱式封鎖n顯式封鎖: 直接加到數(shù)據(jù)對(duì)象上的封鎖n隱式封鎖: 由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖n顯式封鎖和隱式封鎖的效果是一樣的對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢查的內(nèi)容對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢查的內(nèi)容n 該數(shù)據(jù)對(duì)象n有無(wú)顯式封鎖與之沖突n 所有上級(jí)結(jié)點(diǎn)n檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式封鎖沖突：(由上級(jí)結(jié)點(diǎn)封鎖造成的）n所有下級(jí)結(jié)點(diǎn)n看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級(jí)結(jié)點(diǎn)的封鎖）沖突。7.7 封鎖的粒度封鎖的粒度7.7.1 封鎖粒度7

32、.7.2 多粒度封鎖7.7.3 意向鎖7.7.3 意向鎖意向鎖n引進(jìn)意向鎖（intention lock）目的n提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率什么是意向鎖什么是意向鎖n對(duì)任一結(jié)點(diǎn)加基本鎖，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖n如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖意向鎖意向鎖例：對(duì)任一元組 r 加鎖，先關(guān)系r加意向鎖n 事務(wù)t要對(duì)關(guān)系r加x鎖, 系統(tǒng)只要檢查根結(jié)點(diǎn)數(shù)據(jù)庫(kù)和關(guān)系r是否已加了不相容的鎖，n不需要搜索和檢查r中的每一個(gè)元組是否加了x鎖常用意向鎖常用意向鎖n意向共享鎖(intent share lock，簡(jiǎn)稱(chēng)is鎖)n意向排它鎖(intent exclusive lo

33、ck，簡(jiǎn)稱(chēng)ix鎖)n共享意向排它鎖(share intent exclusive lock，簡(jiǎn)稱(chēng)six鎖)意向鎖意向鎖nis鎖n如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加is鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加s鎖。 例：要對(duì)某個(gè)元組加s鎖，則要首先對(duì)關(guān)系和數(shù)據(jù)庫(kù)加is鎖意向鎖意向鎖nix鎖n如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加ix鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加x鎖。 例：要對(duì)某個(gè)元組加x鎖，則要首先對(duì)關(guān)系和數(shù)據(jù)庫(kù)加ix鎖。意向鎖意向鎖nsix鎖n如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加six鎖，表示對(duì)它加s鎖，再加ix鎖，即six = s + ix。 例：對(duì)某個(gè)表加six鎖，則表示該事務(wù)要讀整個(gè)表（所以要對(duì)該表加s鎖），同時(shí)會(huì)更新個(gè)別元組（所以要對(duì)該

34、表加ix鎖）。意向鎖意向鎖意向鎖的相容矩陣 t1 t2 s x is ix six - s y n y n n y x n n n n n y is y n y y y y ix n n y y n y six n n y n n y - y y y y y y 意向鎖意向鎖n鎖的強(qiáng)度n鎖的強(qiáng)度是指它對(duì)其他鎖的排斥程度n一個(gè)事務(wù)在申請(qǐng)封鎖時(shí)以強(qiáng)鎖代替弱鎖是安全的，反之則不然sixxsix -is意向鎖意向鎖n具有意向鎖的多粒度封鎖方法n申請(qǐng)封鎖時(shí)應(yīng)該按自上而下的次序進(jìn)行；n釋放封鎖時(shí)則應(yīng)該按自下而上的次序進(jìn)行 例：事務(wù)t要對(duì)一個(gè)數(shù)據(jù)對(duì)象加鎖，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖第七章第七章 并發(fā)控制并發(fā)控制7.1 并發(fā)控制概述7.2 封鎖7.3 封鎖協(xié)議7.4 活鎖和死鎖7.5 并發(fā)調(diào)度的可串行性7.6 兩段鎖協(xié)議7.7 封鎖的粒度7.8 oracle的并發(fā)控制7.9 小結(jié)7.8 oracle的并發(fā)控制的并發(fā)控制noracl