第十一章并發(fā)控制教學(xué)內(nèi)容

第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)1并發(fā)控制（續(xù)）多事務(wù)執(zhí)行方式(1)事務(wù)串行執(zhí)行每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)共享資源的特點(diǎn)2并發(fā)控制（續(xù)）多事務(wù)執(zhí)行方式(2)交叉并發(fā)方式（interleavedconcurrency）事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運(yùn)行是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率3并發(fā)控制（續(xù)）多事務(wù)執(zhí)行方式(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)境4第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)611.1并發(fā)控制概述并發(fā)控制機(jī)制的任務(wù)對(duì)并發(fā)操作進(jìn)行正確調(diào)度，以保證事務(wù)的隔離性，進(jìn)而保證數(shù)據(jù)庫(kù)的一致性7并發(fā)控制概述（續(xù)）什么是數(shù)據(jù)的不一致性例：飛機(jī)訂票系統(tǒng)中的一個(gè)活動(dòng)序列：1）甲售票員讀出某航班的機(jī)票余額A，設(shè)A=162）乙售票員讀出同一航班的機(jī)票余額A，也為163）甲售票點(diǎn)賣出一張機(jī)票，修改機(jī)票余額A←A-1，所以A=15，把A寫(xiě)回?cái)?shù)據(jù)庫(kù)4）乙售票點(diǎn)也賣出一張機(jī)票，修改機(jī)票余額A←A-1，所以A=15，把A寫(xiě)回?cái)?shù)據(jù)庫(kù)結(jié)果：賣出兩張機(jī)票，但數(shù)據(jù)庫(kù)中機(jī)票余額只減少1。

這種情況稱為數(shù)據(jù)庫(kù)的不一致性。8并發(fā)控制概述（續(xù)）產(chǎn)生原因由甲乙兩個(gè)售票員并發(fā)操作引起在并發(fā)操作情況下，對(duì)甲、乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。因?yàn)榈?步中乙事務(wù)修改A并寫(xiě)回后覆蓋了甲事務(wù)的修改9并發(fā)控制概述（續(xù)）并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性丟失修改（lostupdate）不可重復(fù)讀（non-repeatableread）讀“臟”數(shù)據(jù)（dirtyread）101.丟失修改事務(wù)1與事務(wù)2從數(shù)據(jù)庫(kù)中讀入同一數(shù)據(jù)并修改事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)果導(dǎo)致事務(wù)1的修改被丟失。112.不可重復(fù)讀事務(wù)1讀取數(shù)據(jù)之后，事務(wù)2執(zhí)行更新操作從而使事務(wù)1無(wú)法再現(xiàn)前一次讀取結(jié)果。12不可重復(fù)讀（續(xù)）三類不可重復(fù)讀1.讀-更新事務(wù)1讀取某一數(shù)據(jù)事務(wù)2對(duì)其做了修改當(dāng)事務(wù)1再次讀該數(shù)據(jù)時(shí)，得到與前一次不同的值。13不可重復(fù)讀（續(xù)）三類不可重復(fù)讀2.讀-刪除事務(wù)1按一定條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)記錄事務(wù)2刪除了其中部分記錄當(dāng)事務(wù)1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄神密地消失了。14不可重復(fù)讀（續(xù)）三類不可重復(fù)讀(續(xù))3.讀-插入事務(wù)1按一定條件從數(shù)據(jù)庫(kù)中讀取某些數(shù)據(jù)記錄事務(wù)2插入了一些記錄當(dāng)事務(wù)1再次按相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄。后兩種不可重復(fù)讀有時(shí)也稱為幻行現(xiàn)象153.讀“臟”數(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ù)不一致，是不正確的數(shù)據(jù)，又稱為“臟”數(shù)據(jù)。16圖11.1三種數(shù)據(jù)不一致性T1T2①讀A=16

②

③A←A-1寫(xiě)回A=15

④

讀A=16

A←A-1寫(xiě)回A=15(a)丟失修改17圖11.1三種數(shù)據(jù)不一致性(續(xù))

讀B=100B←B*2寫(xiě)回B=200

①

讀A=50讀B=100求和=150②

③讀A=50讀B=200求和=250(驗(yàn)算不對(duì))T2T1(b)不可重復(fù)讀18圖11.1三種數(shù)據(jù)不一致性(續(xù))

讀C=200

①讀C=100C←C*2寫(xiě)回C②

③ROLLBACKC恢復(fù)為100T2T1(c)讀“臟”數(shù)據(jù)19第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)2011.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣2111.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣22一、什么是封鎖封鎖就是事務(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ù)2311.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣24二、基本封鎖類型DBMS通常提供了多種類型的封鎖。一個(gè)事務(wù)對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制是由封鎖的類型決定的?；痉怄i類型排它鎖（eXclusivelock，簡(jiǎn)記為X鎖）共享鎖（Sharelock，簡(jiǎn)記為S鎖）25基本封鎖類型（續(xù)）排它鎖排它鎖又稱為寫(xiě)鎖。若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對(duì)A加任何類型的鎖，直到T釋放A上的鎖。26基本封鎖類型（續(xù)）共享鎖共享鎖又稱為讀鎖。若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則其它事務(wù)只能再對(duì)A加S鎖，而不能加X(jué)鎖，直到T釋放A上的S鎖。2711.2封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣28三、基本鎖的相容矩陣Y=Yes，相容的請(qǐng)求N=No，不相容的請(qǐng)求

T1T2XS-XNNYSNYY-YYY29第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)3011.3封鎖協(xié)議什么是封鎖協(xié)議在運(yùn)用X鎖和S鎖對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)，需要約定一些規(guī)則，這些規(guī)則為封鎖協(xié)議（LockingProtocol）。何時(shí)申請(qǐng)X鎖或S鎖持鎖時(shí)間何時(shí)釋放對(duì)封鎖方式規(guī)定不同的規(guī)則，就形成了各種不同的封鎖協(xié)議，它們分別在不同的程度上為并發(fā)操作的正確調(diào)度提供一定的保證。31封鎖協(xié)議（續(xù)）常用的保持?jǐn)?shù)據(jù)一致性的封鎖協(xié)議三級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議2級(jí)封鎖協(xié)議3級(jí)封鎖協(xié)議321.1級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)R之前必須先對(duì)其加X(jué)鎖，直到事務(wù)結(jié)束才釋放。正常結(jié)束（COMMIT）非正常結(jié)束（ROLLBACK）1級(jí)封鎖協(xié)議可防止丟失修改，并保證事務(wù)T是可恢復(fù)的。在1級(jí)封鎖協(xié)議中，如果僅僅是讀數(shù)據(jù)不對(duì)其進(jìn)行修改，是不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。332.2級(jí)封鎖協(xié)議2級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，讀完后即可釋放S鎖。2級(jí)封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)。在2級(jí)封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀。343.3級(jí)封鎖協(xié)議3級(jí)封鎖協(xié)議1級(jí)封鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放。3級(jí)封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復(fù)讀。35圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例T1T2①

XlockA獲得②

讀A=16

③A←A-1寫(xiě)回A=15CommitUnlockA④

⑤

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

(a)沒(méi)有丟失修改36圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例

讀A=15①

XlockA獲得②

讀A=16

A←A-1寫(xiě)回A=15③

④RollbackUnlockA

T2T1(a.1)讀“臟”數(shù)據(jù)37圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例

XlockB獲得

讀B=100B←B*2寫(xiě)回B=200CommitUnlockB①讀A=50讀B=100求和=150②③讀A=50讀B=200求和=250(驗(yàn)算不對(duì))T2T1(a.2)不可重復(fù)讀38圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例T1T2①

SlockA讀A=50SlockB讀B=100求和=150②

③讀A=50讀B=100求和=150CommitUnlockAUnlockB④

⑤

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

(b)可重復(fù)讀39圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例T1T2①

XlockC讀C=100C←C*2寫(xiě)回C=200②

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

⑤

SlockC等待等待等待等待獲得SlockC讀C=100CommitCUnlockC(c)不讀“臟”數(shù)據(jù)40圖11.3用封鎖機(jī)制解決三種數(shù)據(jù)不一致性示例(c.1)不可重復(fù)讀①

SclockA獲得讀A=50UnlockA②SclockB獲得讀B=100UnlockB③求和=150

XlockB等待等待獲得XlockB讀B=100B←B*2寫(xiě)回B=200CommitUnlockBT2T1④SclockA獲得讀A=50UnlockASclockB獲得讀B=200UnlockB求和=250(驗(yàn)算不對(duì))

T2T1(續(xù))414．封鎖協(xié)議小結(jié)三級(jí)協(xié)議的主要區(qū)別什么操作需要申請(qǐng)封鎖以及何時(shí)釋放鎖（即持鎖時(shí)間）42封鎖協(xié)議小結(jié)(續(xù))43第11章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)4411.4活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)題，但也帶來(lái)一些新的問(wèn)題死鎖活鎖4511.4活鎖和死鎖11.4.1活鎖11.4.2死鎖4611.4活鎖和死鎖11.4.1活鎖11.4.2死鎖4711.4.1活鎖一、什么是活鎖48活鎖(續(xù))二、如何避免活鎖采用先來(lái)先服務(wù)的策略當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)，封鎖子系統(tǒng)按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì)該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第一個(gè)事務(wù)獲得鎖。4911.4活鎖和死鎖11.4.1活鎖11.4.2死鎖5011.4.2死鎖一、什么是死鎖 T1T2

XlockR1...XlockR2等待等待等待...XlockR2..XlockR1等待等待.51死鎖（續(xù)）二、如何解決死鎖解決死鎖的兩類方法1.死鎖的預(yù)防2.死鎖的診斷與解除52死鎖（續(xù)）二、如何解決死鎖解決死鎖的兩類方法1.死鎖的預(yù)防2.死鎖的診斷與解除531.死鎖的預(yù)防預(yù)防死鎖為何能解決死鎖產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從而出現(xiàn)死等待。預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件。54死鎖的預(yù)防（續(xù)）預(yù)防死鎖的方法一次封鎖法順序封鎖法55（1）一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行。一次封鎖法存在的問(wèn)題：降低并發(fā)度擴(kuò)大封鎖范圍一次就將以后要用到的全部數(shù)據(jù)加鎖，勢(shì)必?cái)U(kuò)大了封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度。56一次封鎖法（續(xù)）難于事先精確確定封鎖對(duì)象數(shù)據(jù)庫(kù)中數(shù)據(jù)是不斷變化的，原來(lái)不要求封鎖的數(shù)據(jù)，在執(zhí)行過(guò)程中可能會(huì)變成封鎖對(duì)象，所以很難事先精確地確定每個(gè)事務(wù)所要封鎖的數(shù)據(jù)對(duì)象解決方法：將事務(wù)在執(zhí)行過(guò)程中可能要封鎖的數(shù)據(jù)對(duì)象全部加鎖，這就進(jìn)一步降低了并發(fā)度。57（2）順序封鎖法順序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。順序封鎖法存在的問(wèn)題維護(hù)成本高數(shù)據(jù)庫(kù)系統(tǒng)中可封鎖的數(shù)據(jù)對(duì)象極其眾多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護(hù)這樣極多而且變化的資源的封鎖順序非常困難，成本很高。58順序封鎖法（續(xù)）難于實(shí)現(xiàn)事務(wù)的封鎖請(qǐng)求可以隨著事務(wù)的執(zhí)行而動(dòng)態(tài)地決定，很難事先確定每一個(gè)事務(wù)要封鎖哪些對(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，這樣就破壞了封鎖順序.59死鎖的預(yù)防（續(xù)）結(jié)論在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫(kù)的特點(diǎn)DBMS在解決死鎖的問(wèn)題上更普遍采用的是診斷并解除死鎖的方法60死鎖（續(xù)）二、如何解決死鎖解決死鎖的兩類方法1.死鎖的預(yù)防2.死鎖的診斷與解除612.死鎖的診斷與解除方法由DBMS的并發(fā)控制子系統(tǒng)定期檢測(cè)系統(tǒng)中是否存在死鎖，一旦檢測(cè)到死鎖，就要設(shè)法解除。62死鎖的診斷與解除（續(xù)）檢測(cè)死鎖

超時(shí)法如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖。優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)有可能誤判死鎖時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)63死鎖的診斷與解除（續(xù)）

等待圖法用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況事務(wù)等待圖是一個(gè)有向圖G=(T，U)T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)U為邊的集合，每條邊表示事務(wù)等待的情況若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2并發(fā)控制子系統(tǒng)周期性地（比如每隔1min）檢測(cè)事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。64死鎖的診斷與解除（續(xù)）解除死鎖選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消，釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去。65第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)6611.5并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的6711.5并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的68一、什么樣的并發(fā)操作調(diào)度是正確的計(jì)算機(jī)系統(tǒng)對(duì)并行事務(wù)中并行操作的調(diào)度是的隨機(jī)的，而不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果。將所有事務(wù)串行起來(lái)的調(diào)度策略一定是正確的調(diào)度策略。如果一個(gè)事務(wù)運(yùn)行過(guò)程中沒(méi)有其他事務(wù)在同時(shí)運(yùn)行，也就是說(shuō)它沒(méi)有受到其他事務(wù)的干擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正常的或者預(yù)想的69什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）以不同的順序串行執(zhí)行事務(wù)也有可能會(huì)產(chǎn)生不同的結(jié)果，但由于不會(huì)將數(shù)據(jù)庫(kù)置于不一致?tīng)顟B(tài)，所以都可以認(rèn)為是正確的。幾個(gè)事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同。這種并行調(diào)度策略稱為可串行化（Serializable）的調(diào)度。70什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）可串行性是并行事務(wù)正確性的唯一準(zhǔn)則例：現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作：事務(wù)1：讀B；A=B+1；寫(xiě)回A；事務(wù)2：讀A；B=A+1；寫(xiě)回B；假設(shè)A的初值為2，B的初值為2。71什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）對(duì)這兩個(gè)事務(wù)的不同調(diào)度策略串行執(zhí)行串行調(diào)度策略1串行調(diào)度策略2交錯(cuò)執(zhí)行不可串行化的調(diào)度可串行化的調(diào)度72(a)串行調(diào)度策略，正確的調(diào)度SlockBY=B=2UnlockBXlockAA=Y+1寫(xiě)回A(=3)UnlockA

SlockAX=A=3UnlockAXlockBB=X+1寫(xiě)回B(=4)UnlockB

T1T273(b)串行調(diào)度策略，正確的調(diào)度

SlockBY=B=3UnlockBXlockAA=Y+1寫(xiě)回A(=4)UnlockA

SlockAX=A=2UnlockAXlockBB=X+1寫(xiě)回B(=3)UnlockB

T1T274(c)不可串行化的調(diào)度SlockBY=B=2

UnlockB

XlockAA=Y+1寫(xiě)回A(=3)

UnlockA

SlockAX=A=2

UnlockA

XlockBB=X+1寫(xiě)回B(=3)

UnlockBT1T275(c)不可串行化的調(diào)度(續(xù))由于其執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同，所以是錯(cuò)誤的調(diào)度。76(d)可串行化的調(diào)度SlockBY=B=2UnlockBXlockA

A=Y+1寫(xiě)回A(=3)UnlockA

SlockA等待等待等待X=A=3UnlockAXlockBB=X+1寫(xiě)回B(=4)UnlockBT1T277(d)可串行化的調(diào)度（續(xù)）由于其執(zhí)行結(jié)果與串行調(diào)度（a）的執(zhí)行結(jié)果相同，所以是正確的調(diào)度。7811.5并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的79二、如何保證并發(fā)操作的調(diào)度是正確的為了保證并行操作的正確性，DBMS的并行控制機(jī)制必須提供一定的手段來(lái)保證調(diào)度是可串行化的。從理論上講，在某一事務(wù)執(zhí)行時(shí)禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡(jiǎn)單的調(diào)度策略，但這種方法實(shí)際上是不可行的，因?yàn)樗褂脩舨荒艹浞止蚕頂?shù)據(jù)庫(kù)資源。80如何保證并發(fā)操作的調(diào)度是正確的（續(xù)）保證并發(fā)操作調(diào)度正確性的方法封鎖方法：兩段鎖（Two-PhaseLocking，簡(jiǎn)稱2PL）協(xié)議時(shí)標(biāo)方法樂(lè)觀方法81第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)8211.6兩段鎖協(xié)議可串行性是并行調(diào)度正確性的唯一準(zhǔn)則，兩段鎖（2PL）協(xié)議就是為保證并行調(diào)度可串行性而提供的封鎖協(xié)議。兩段鎖協(xié)議的內(nèi)容1.在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫(xiě)操作之前，事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖2.在釋放一個(gè)封鎖之后，事務(wù)不再獲得任何其他封鎖。83兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義事務(wù)分為兩個(gè)階段

第一階段是獲得封鎖，也稱為擴(kuò)展階段；第二階段是釋放封鎖，也稱為收縮階段。84兩段鎖協(xié)議（續(xù)）例：事務(wù)1的封鎖序列：SlockA...SlockB...XlockC...UnlockB...UnlockA...UnlockC；事務(wù)2的封鎖序列：SlockA...UnlockA...SlockB...XlockC...UnlockC...UnlockB；事務(wù)1遵守兩段鎖協(xié)議，而事務(wù)2不遵守兩段協(xié)議。85兩段鎖協(xié)議（續(xù)）并行執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的所有并行調(diào)度策略都是可串行化的。

所有遵守兩段鎖協(xié)議的事務(wù)，其并行執(zhí)行的結(jié)果一定是正確的。事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。即可串行化的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)議。86兩段鎖協(xié)議（續(xù)）T1SlockB讀B=2Y=BXlockA

A=Y+1寫(xiě)回A=3UnlockBUnlockA

T2

SlockA等待等待等待等待等待SlockA讀A=3Y=AXlockBB=Y+1寫(xiě)回B=4UnlockBUnlockA

T1SlockB讀B=2Y=BUnlockBXlockA

A=Y+1寫(xiě)回A=3UnlockA

T2

SlockA等待等待等待等待SlockA讀A=3X=AUnlockAXlockBB=X+1寫(xiě)回B=4UnlockB

(a)遵守兩段鎖協(xié)議

(b)不遵守兩段鎖協(xié)議T1SlockB讀B=2Y=BUnlockBXlockAA=Y+1寫(xiě)回A=3UnlockAT2

SlockA讀A=2X=AUnlockAXlockB等待XlockBB=X+1寫(xiě)回B=3UnlockB

(c)不遵守兩段鎖協(xié)議87兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議與防止死鎖的一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖88兩段鎖協(xié)議（續(xù)）圖11.7遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖T1SlockB讀B=2

XlockA等待等待T2

SlockA讀A=2

XlockB等待89兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議與三級(jí)封鎖協(xié)議兩類不同目的的協(xié)議兩段鎖協(xié)議保證并發(fā)調(diào)度的正確性三級(jí)封鎖協(xié)議在不同程度上保證數(shù)據(jù)一致性遵守第三級(jí)封鎖協(xié)議必然遵守兩段協(xié)議90第十一章并發(fā)控制11.1并發(fā)控制概述11.2封鎖11.3封鎖協(xié)議11.4活鎖和死鎖11.5并發(fā)調(diào)度的可串行性11.6兩段鎖協(xié)議11.7封鎖的粒度11.8小結(jié)9111.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖9211.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖9311.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則9411.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則95一、什么是封鎖粒度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è)）、塊等96什么是封鎖粒度（續(xù)）封鎖對(duì)象可以很大也可以很小例：對(duì)整個(gè)數(shù)據(jù)庫(kù)加鎖對(duì)某個(gè)屬性值加鎖封鎖對(duì)象的大小稱為封鎖的粒度(Granularity)多粒度封鎖(multiplegranularitylocking)在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇9711.7.1封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則98二、選擇封鎖粒度的原則封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開(kāi)銷密切相關(guān)。封鎖的粒度越大，系統(tǒng)中能夠被封鎖的對(duì)象就越少，并發(fā)度也就越小，但同時(shí)系統(tǒng)開(kāi)銷也越??；封鎖的粒度越小，并發(fā)度越高，但系統(tǒng)開(kāi)銷也就越大。選擇封鎖粒度時(shí)必須同時(shí)考慮封鎖機(jī)構(gòu)和并發(fā)度兩個(gè)因素，對(duì)系統(tǒng)開(kāi)銷與并發(fā)度進(jìn)行權(quán)衡，以求得最優(yōu)的效果。99選擇封鎖粒度的原則（續(xù)）一般原則需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元；需要處理多個(gè)關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫(kù)為封鎖單位；只處理少量元組的用戶事務(wù)：以元組為封鎖單位10011.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖10111.7.2多粒度封鎖多粒度樹(shù)以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度

102多粒度封鎖（續(xù)）例：三級(jí)粒度樹(shù)。根結(jié)點(diǎn)為數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。數(shù)據(jù)庫(kù)關(guān)系Rn關(guān)系R1元組元組元組元組………………103多粒度封鎖（續(xù)）多粒度封鎖的封鎖協(xié)議允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的鎖在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖，顯式封鎖和隱式封鎖104多粒度封鎖（續(xù)）顯式封鎖和隱式封鎖顯式封鎖:直接加到數(shù)據(jù)對(duì)象上的封鎖隱式封鎖:由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖顯式封鎖和隱式封鎖的效果是一樣的105多粒度封鎖（續(xù)）對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢查的內(nèi)容1.該數(shù)據(jù)對(duì)象有無(wú)顯式封鎖與之沖突2.所有上級(jí)結(jié)點(diǎn)檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式封鎖沖突3.所有下級(jí)結(jié)點(diǎn)看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級(jí)結(jié)點(diǎn)的封鎖）沖突。10611.7封鎖的粒度11.7.1封鎖粒度11.7.2多粒度封鎖11.7.3意向鎖10711.7.3意向鎖引進(jìn)意向鎖（intentionlock）目的提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率108意向鎖(續(xù))什么是意向鎖對(duì)任一結(jié)點(diǎn)加基本鎖，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖109意向鎖(續(xù))例：對(duì)任一元組r加鎖時(shí)，必須先對(duì)它所在的關(guān)系R加意向鎖

事務(wù)T要對(duì)關(guān)系R加X(jué)鎖,系統(tǒng)只要檢查根結(jié)點(diǎn)數(shù)據(jù)庫(kù)和關(guān)系R是否已加了不相容的鎖，而不再需要搜索和檢查R中的每一個(gè)元組是否加了X鎖110意向鎖（續(xù)）常用意向鎖意向共享鎖(IntentShareLock，簡(jiǎn)稱IS鎖)意向排它鎖(IntentExclusiveLock，簡(jiǎn)稱IX鎖)共享意向排它鎖(ShareIntentExclusiveLock，簡(jiǎn)稱SIX鎖)111意向鎖（續(xù)）IS鎖如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加IS鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加S鎖。

例：要對(duì)某個(gè)元組加S鎖，則要首先對(duì)關(guān)系和