西華師范大學(xué)計(jì)算機(jī)學(xué)院第八章并發(fā)控制

第八章并發(fā)控制

西華師范大學(xué)計(jì)算機(jī)學(xué)院

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

并發(fā)控制概述

多事務(wù)執(zhí)行方式

⑴事務(wù)串行執(zhí)行

-每個(gè)時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其他事

務(wù)必須等到這個(gè)事務(wù)結(jié)束以后方能運(yùn)

行

-不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫(kù)

共享資源的特點(diǎn)

并發(fā)控制(續(xù))

(2)交叉并發(fā)方式(interleavedconcurrency)

-事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作

輪流交叉運(yùn)行

-是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處

理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率

并發(fā)控制(續(xù))

⑶同時(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ī)制

事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)題

?可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞

事務(wù)的隔離性和數(shù)據(jù)庫(kù)的一致性

?DBMS必須提供并發(fā)控制機(jī)制

?并發(fā)控制機(jī)制是衡量一個(gè)DBMS性能的

重要標(biāo)志之一

8.1并發(fā)控制概述

?并發(fā)控制機(jī)制的任務(wù)

-對(duì)并發(fā)操作進(jìn)行正確調(diào)度

-保證事務(wù)的隔離性

-保證數(shù)據(jù)庫(kù)的一致性

數(shù)據(jù)不一致實(shí)例：飛機(jī)訂票系統(tǒng)

事務(wù)T1事務(wù)T,

①讀A=16

②

讀A=16

③A—A-1

寫(xiě)回A=15

④

A<—A-3

寫(xiě)回A=13

T1的修改被T2覆蓋了!

并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性

?丟失修改(lostupdate)

?不可重復(fù)讀(non-repeatableread)

?讀“臟”數(shù)據(jù)(dirtyread)

1.丟失修改

丟失修改是指事務(wù)1與事務(wù)2從數(shù)據(jù)庫(kù)中讀

入同一數(shù)據(jù)并修改

事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)果,

導(dǎo)致事務(wù)1的修改被丟失。

4

2.不可重復(fù)讀

不可重復(fù)讀是指事務(wù)1讀取數(shù)據(jù)后，事務(wù)2

執(zhí)行更新操作，使事務(wù)1無(wú)法再現(xiàn)前一次讀

取結(jié)果。

4

三類(lèi)不可重復(fù)讀

事務(wù)1讀取某一數(shù)據(jù)后：

lo事務(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ù)

事務(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ù)，又稱(chēng)為“臟”數(shù)據(jù)。0

圖8.1三種數(shù)據(jù)不一致性

T2

①讀A=16

②

讀A=16

③A-A-1

寫(xiě)回A=15

④

A—A-1

寫(xiě)回A=15

(a)丟失修改

圖8.1三種數(shù)據(jù)不一致性（續(xù)）

TiT2

①讀A=50

讀B=100

求和=150

②

讀B=100

B—B*2

寫(xiě)回B=200

③讀A=50

讀B=200

求和=250

（驗(yàn)算不對(duì)）

（b）不可重復(fù)讀

圖8.1三種數(shù)據(jù)不一致性（續(xù)）

TiT2

①讀C=100

C—C*2

寫(xiě)回c

②

讀C=200

(3)ROLLBACK

C恢復(fù)為100

（C）讀“臟”數(shù)據(jù)wr

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.2封鎖

、什么是封鎖

、基本封鎖類(lèi)型

、基本鎖的相容矩陣

一、什么是封鎖

?封鎖就是事務(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ù)

8.2封鎖

、什么是封鎖

、基本封鎖類(lèi)型

、基本鎖的相容矩陣

二、基本封鎖類(lèi)型

?DBMS通常提供了多種類(lèi)型的封鎖。一個(gè)事務(wù)

對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖后究竟擁有什么樣的控制

是由封鎖的類(lèi)型決定的。

?基本封鎖類(lèi)型

-排它鎖（exclusivelock,簡(jiǎn)記為X鎖）

-共享鎖（Sharelock,簡(jiǎn)記為S鎖）

排它鎖

?排它鎖又稱(chēng)為寫(xiě)鎖

?若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允

許T讀取和修改A,其它任何事務(wù)都不能

再對(duì)A加任何類(lèi)型的鎖，直到T釋放A上

的鎖

共享鎖

?共享鎖又稱(chēng)為讀鎖

?若事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則其它

事務(wù)只能再對(duì)A加S鎖，而不能加X(jué)鎖，

直到T釋放A上的S鎖

8.2封鎖

、什么是封鎖

、基本封鎖類(lèi)型

、基本鎖的相容矩陣

工鎖的相容矩陣

Y=Yes,相容的請(qǐng)求

N=No,不相容的請(qǐng)求

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.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é)議

1級(jí)封鎖協(xié)議

?事務(wù)T在修改數(shù)據(jù)R之前必須先對(duì)其加X(jué)

鎖，直到事務(wù)結(jié)束才釋放

?正常結(jié)束(COMMIT)

?非正常結(jié)束(ROLLBACK)

?1級(jí)封鎖協(xié)議可防止丟失修改

?在1級(jí)封鎖協(xié)議中，如果是讀數(shù)據(jù)，不需要加

鎖的，所以它不能保證可重復(fù)讀和不讀“臟”

數(shù)據(jù)。

1級(jí)封鎖協(xié)議

TiT2

①XlockA

獲得

②讀A=16

XlockA

③A-A-1

等待沒(méi)有丟失修改

寫(xiě)回A=15

等待

Commit

等待

UnlockA

等待

④

獲得XlockA

讀A=15

A-A-l

⑤

寫(xiě)回A=14

Commit

UnlockA

1級(jí)封鎖協(xié)議

T?

①XlockA

獲得

②讀A=16

A-A-1讀“臟”數(shù)據(jù)

寫(xiě)回A=15

③

讀A=15

(4)Rollback

UnlockA

1級(jí)封鎖協(xié)議

T2

①讀A=50

讀B=100

求和=150

②

XlockB

獲得不可重復(fù)讀

讀B=100

B—B*2

寫(xiě)回B=200

Commit

UnlockB

③讀A=50

讀B=200

求和=250

（驗(yàn)算不對(duì)）

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ù)讀。

IK、\、，

。知封4uH\1\J

T（丹

TiT2T2

①SlockA④SlockA

獲得獲得

讀A=50讀A=50

UnlockAUnlockA

②SlockBSlockB

獲得XlockB獲得

讀B=100等待讀B=200

UnlockB等待UnlockB

③求和=150獲得XlockB求和=250

讀B=100（驗(yàn)算不對(duì)）

B—B*2

寫(xiě)回B=200

Commit

UnlockB

不可重復(fù)讀

3級(jí)封鎖協(xié)議

?1級(jí)封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)R之前

必須先對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放

?3級(jí)封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不

可重復(fù)讀。

T2"

1

①SlockA

讀A=50

SlockB

讀B=100

求和=150

②XlockB

等待

等待

③讀A=50等待可重復(fù)讀

讀B=100等待

求和=150等待

Commit等待

UnlockA等待

UnlockB等待

④獲得XlockB

讀B=100

B—B*2

⑤寫(xiě)回B=200

Commit

UnlockB

3級(jí)封鎖協(xié)議

TiT2

①XlockC

讀C=100

C—C*2

寫(xiě)回C=200

②不讀“臟”數(shù)據(jù)

SlockC

等待

③ROLLBACK等待

（C恢復(fù)為100）等待

UnlockC等待

④獲得SlockC

讀C=100

⑤CommitC

UnlockC

4.封鎖協(xié)議小結(jié)

?三級(jí)協(xié)議的主要區(qū)別

-什么操作需要申請(qǐng)封鎖

-何時(shí)釋放鎖（即持鎖時(shí)間）

封鎖協(xié)議小結(jié)（續(xù)）

X領(lǐng)S頃Ttt保證

嬲事猴捌愉事猴不丟失硬肥W

束轍硼硼束戳微姓雄

1躺翎成JJ

2跚撼44J

3麴鼬雙77777

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.4活鎖和死鎖

?封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)

題，但也帶來(lái)一些新的問(wèn)題

-死鎖：指多個(gè)事務(wù)循環(huán)等待其他事務(wù)釋放鎖而陷入

停滯狀態(tài)，不借助外力干預(yù)則無(wú)法解開(kāi)的狀態(tài)。

-活鎖：當(dāng)多個(gè)事務(wù)請(qǐng)求對(duì)一個(gè)數(shù)據(jù)對(duì)象進(jìn)行封鎖時(shí),

由于加鎖請(qǐng)求選擇策略的問(wèn)題，其中一個(gè)較早事務(wù)

的封鎖請(qǐng)求一直沒(méi)有得到滿(mǎn)足，導(dǎo)致該事務(wù)永遠(yuǎn)等

待。

8.4.1活鎖

lockR

lockR

等待LockR

UnlockLockR

■

等待LockR等待

等待等待

■

Unlock蟒

LockR

等待

如何避免活鎖

采用先來(lái)先服務(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ù)獲得鎖。

8.4.2死鎖

XlockR1

XlockR2

XlockR2

等待XlockR1

等待等待

等待等待

解決死鎖的方法

兩類(lèi)方法

1.預(yù)防死鎖

2.死鎖的診斷與解除

1.死鎖的預(yù)防

?產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已

封鎖了一些數(shù)據(jù)對(duì)象，然后又都請(qǐng)求對(duì)

已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖，從

而出現(xiàn)死等待。

?預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的

條件

死鎖的預(yù)防（續(xù)）

預(yù)防死鎖的方法

?一次封鎖法

?順序封鎖法

(1)一次封鎖法

?要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全

部加鎖，否則就不能繼續(xù)執(zhí)行

?一次封鎖法存在的問(wèn)題：降低并發(fā)度

-擴(kuò)大封鎖范圍

-將以后要用到的全部數(shù)據(jù)加鎖，勢(shì)必?cái)U(kuò)大了

封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度

一次封鎖法（續(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ā)度。

(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ù)這樣極多而且變化的資源的封鎖

順序非常困難，成本很高

順序封鎖法（續(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,這樣就破壞了封鎖順序.

死鎖的預(yù)防（續(xù)）

,結(jié)論

-在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并

不很適合數(shù)據(jù)庫(kù)的特點(diǎn)

-DBMS在解決死鎖的問(wèn)題上更普遍采用的是

診斷并解除死鎖的方法

2.死鎖的診斷與解除

?允許死鎖發(fā)生

?解除死鎖

-由DBMS的并發(fā)控制子系統(tǒng)定期檢測(cè)系統(tǒng)中

是否存在死鎖

-一旦檢測(cè)到死鎖，就要設(shè)法解除

檢測(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)

等待圖法

?用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況

-事務(wù)等待圖是一個(gè)有向圖G=(T,U)

-T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)

-。為邊的集合，每條邊表示事務(wù)等待的情況

-若T1等待丁2，貝門(mén)1，之間劃一條有向邊，從T1指

向

?并發(fā)控制子系統(tǒng)周期性地(比如每隔1min)檢

測(cè)事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表

示系統(tǒng)中出現(xiàn)了死鎖。

死鎖的診斷與解除（續(xù)）

?解除死鎖

-選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，

將其撤消，釋放此事務(wù)持有的所有的

鎖，使其它事務(wù)能繼續(xù)運(yùn)行下去。

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.5并發(fā)調(diào)度的可串行性

、什么樣的并發(fā)操作調(diào)度是正確的

、如何保證并發(fā)操作的調(diào)度是正確的

一、什么樣的并發(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ù)想的

什么樣的并發(fā)操作調(diào)度是正確的(續(xù))

?以不同的順序串行執(zhí)行事務(wù)也有可能會(huì)產(chǎn)生不

同的結(jié)果，但由于不會(huì)將數(shù)據(jù)庫(kù)置于不一致?tīng)?/p>

態(tài)，所以都可以認(rèn)為是正確的。

?幾個(gè)事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)

果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同。

這種并行調(diào)度策略稱(chēng)為可串行化(Serializable)

的調(diào)度。

什么樣的并發(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。

什么樣的并發(fā)操作調(diào)度是正確的（續(xù)）

-對(duì)這兩個(gè)事務(wù)的不同調(diào)度策略

?串行執(zhí)行

-串行調(diào)度策略1

-串行調(diào)度策略2

?交錯(cuò)執(zhí)行

-不可串行化的調(diào)度

-可串行化的調(diào)度

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

%

T2

SlockB

Y=B=2

UnlockB

XlockA

A=Y+1

寫(xiě)回A(=3)

UnlockA

SlockA

X=A=3

UnlockA

XlockB

B=X+1

寫(xiě)回B(=4)

UnlockB

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

*T2

SlockA

X=A=2

UnlockA

XlockB

B=X+1

寫(xiě)回B(=3)

UnlockB

SlockB

Y=B=3

UnlockB

XlockA

A=Y+1

寫(xiě)回A(=4)

UnlockA

(c)不可串行化的調(diào)度

%

T2

SlockB

Y=B=2

SlockA

X=A=2

UnlockB

UnlockA

XlockA

A=Y+1

寫(xiě)回A(=3)

XlockB

B=X+1

寫(xiě)回B(=3)

UnlockA

UnlockB

(c)不可串行化的調(diào)度(續(xù))

-由于其執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同,

所以是錯(cuò)誤的調(diào)度。

(d)可串行化的調(diào)度

%

T2

SlockB

Y=B=2

UnlockB

XlockA

SlockA

A=Y+1等待

寫(xiě)回A(=3)等待

UnlockA等待

X=A=3

UnlockA

XlockB

B=X+1

寫(xiě)回B(=4)

UnlockB

（d）可串行化的調(diào)度（續(xù)）

?由于其執(zhí)行結(jié)果與串行調(diào)度（a）的執(zhí)行

結(jié)果相同，所以是正確的調(diào)度。

8.5并發(fā)調(diào)度的可串行性

、什么樣的并發(fā)操作調(diào)度是正確的

、如何保證并發(fā)操作的調(diào)度是正確的

、如何保證并發(fā)操作的調(diào)度是正確的

?為保證并行操作的正確性，DBMS的并行控制

機(jī)制必須提供手段保證調(diào)度是可串行化的。

?從理論上講，在某一事務(wù)執(zhí)行時(shí)禁止其他事務(wù)

執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也

是最簡(jiǎn)單的調(diào)度策略，但它使用戶(hù)不能充分共

享數(shù)據(jù)庫(kù)資源，不可行。

如何保證并發(fā)操作的調(diào)度是正確的（續(xù)）

?保證并發(fā)操作調(diào)度正確性的方法

-封鎖方法：兩段鎖（Two-PhaseLocking,簡(jiǎn)

稱(chēng)2PL）協(xié)議

-時(shí)標(biāo)方法

-樂(lè)觀方法

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.6兩段鎖協(xié)議

?兩段鎖協(xié)議的內(nèi)容

1.在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫(xiě)操作之前，

事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖

2.在釋放一個(gè)封鎖之后，事務(wù)不再獲得

任何其他封鎖。

兩段鎖協(xié)議（續(xù)）

?“兩段”鎖的含義

-事務(wù)分為兩個(gè)階段

.第一階段是獲得封鎖，也稱(chēng)為擴(kuò)展階段;

.第二階段是釋放封鎖，也稱(chēng)為收縮階段。

兩段鎖協(xié)議（續(xù)）

例：

事務(wù)1的封鎖序列：

SlockA...SlockB...XlockC...UnlockB...UnlockA...Unlock

C；

事務(wù)2的封鎖序列：

SlockA...UnlockA...SlockB...XlockC...UnlockC...Unlock

B；

事務(wù)1遵守兩段鎖協(xié)議，而事務(wù)2不遵守兩段協(xié)議。

兩段鎖協(xié)議（續(xù)）

?所有遵守兩段鎖協(xié)議的事務(wù)，對(duì)它們的所有并行

調(diào)度策略都是可串行化的，即

其并行執(zhí)行的結(jié)果一定是正確的

?注意：事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充

分條件，而不是必要條件，也就是說(shuō)，可串行化

的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)

議。

兩段鎖協(xié)議(續(xù))

SlockBSlockB

讀B=2讀B=2SlockA

Y=BY=B讀A=2

XlockAUnlockBX=A

SlockAXlockAUnlockA

等待

S等1

OC待1SlockB

等待

等

待讀

A=Y+1B=2

等

等待A=Y+1待Y=BXlockB

寫(xiě)回A=3

等

等待寫(xiě)回A=3待UnlockB等待

UnlockB等待UnlockAXlockB

UnlockASlockASlockAB=X+1

讀A=3讀A=3寫(xiě)回B=3

Y=AX=AUnlockB

XlockBUnlockA

B=Y+1XlockBXlockA?

寫(xiě)回B=4B=X+1A=Y+1I

UnlockB寫(xiě)回B=4寫(xiě)回A=3?

UnlockAUnlockBUnlockA,

(a)遵守兩盤(pán)鎖協(xié)議(b)不遵守愉段鎖協(xié)議(c)不遵守祐段鎖協(xié)議

兩段鎖協(xié)議（續(xù)）

?兩段鎖協(xié)議與防止死鎖的一次封鎖法

-一次封鎖法要求每個(gè)事務(wù)必須一次將所有要

使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行,

因此一次封鎖法遵守兩段鎖協(xié)議

-但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所

有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖

協(xié)議的事務(wù)可能發(fā)生死鎖

兩段鎖協(xié)議（續(xù)）

圖8.7遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖

T

L2

SlockB

讀B=2

SlockA

讀A=2

XlockA

等待XlockA

等待等待

兩段鎖協(xié)議（續(xù)）

?兩段鎖協(xié)議與三級(jí)封鎖協(xié)議

-兩類(lèi)不同目的的協(xié)議

?兩段鎖協(xié)議

-保證并發(fā)調(diào)度的正確性

?三級(jí)封鎖協(xié)議

-在不同程度上保證數(shù)據(jù)一致性

-遵守第三級(jí)封鎖協(xié)議必然遵守兩段協(xié)議

第八章并發(fā)控制

8.1并發(fā)控制概述

8.2封鎖

8.3封鎖協(xié)議

8.4活鎖和死鎖

8.5并發(fā)調(diào)度的可串行性

8.6兩段鎖協(xié)議

8.7封鎖的粒度

8.8小結(jié)

8.7封鎖的粒度

8.7.1封鎖粒度

8.7.2多粒度封鎖

8.7.3意向鎖

8.7.1封鎖粒度

、什么是封鎖粒度

、選擇封鎖粒度的原則

一、什么是封鎖粒度

?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è)）、物理記錄等

什么是封鎖粒度(續(xù))

?封鎖對(duì)象可以很大也可以很小

例：對(duì)整個(gè)數(shù)據(jù)庫(kù)加鎖

對(duì)某個(gè)屬性值加鎖

?封鎖對(duì)象的大小稱(chēng)為封鎖的粒度(Granularity)

?多粒度封鎖(multiplegranularitylocking)

-在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同

的事務(wù)選擇

8.7.1封鎖粒度

＞什么是封鎖粒度

八選擇封鎖粒度的原則

一選擇封鎖粒度的原則

?封鎖的粒度越大，小，

?系統(tǒng)被封鎖的對(duì)象少，多,

?并發(fā)度小，高，

?系統(tǒng)開(kāi)銷(xiāo)小，大，

?選擇封鎖粒度：

考慮封鎖開(kāi)銷(xiāo)和并發(fā)度兩個(gè)因素進(jìn)行權(quán)衡

選擇封鎖粒度的原則（續(xù)）

?需要處理多個(gè)關(guān)系的大量元組的用戶(hù)事務(wù)：以

數(shù)據(jù)庫(kù)為封鎖單位；

?需要處理大量元組的用戶(hù)事務(wù)：以關(guān)系為封鎖

單元；

?只處理少量元組的用戶(hù)事務(wù)：以元組為封鎖單

位

8.7封鎖的粒度

8.7.1封鎖粒度

8.7.2多粒度封鎖

8.7.3意向鎖

8.7.2多粒度封鎖

?多粒度樹(shù)

-以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度

-根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度

-葉結(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ù)庫(kù)

關(guān)系Ri……關(guān)系R〃

元/，、&元’…\^組

多粒度封鎖協(xié)議

?允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加

鎖

?對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有

后裔結(jié)點(diǎn)也被加以同樣類(lèi)型的鎖

?在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以?xún)?/p>

種方式封鎖：顯式封鎖和隱式封鎖

顯式封鎖和隱式封鎖

?顯式封鎖:直接加到數(shù)據(jù)對(duì)象上的封鎖

?隱式封鎖：由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)

據(jù)對(duì)象加上了鎖

?顯式封鎖和隱式封鎖的效果是一樣的

對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)檢查的內(nèi)容

■該數(shù)據(jù)對(duì)象

-有無(wú)顯式封鎖與之沖突

?所有上級(jí)結(jié)點(diǎn)

-檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式

封鎖沖突：（由上級(jí)結(jié)點(diǎn)封鎖造成的）

?所有下級(jí)結(jié)點(diǎn)

-看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到

下級(jí)結(jié)點(diǎn)的封鎖）沖突。

8.7封鎖的粒度

8.7.1封鎖粒度

8.7.2多粒度封鎖

8.7.3意向鎖

8.7.3意向鎖

?引進(jìn)意向鎖(intentionlock)目的

_提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率

什么是意向鎖

?對(duì)任一結(jié)點(diǎn)加基本鎖，必須先對(duì)它的上

層結(jié)點(diǎn)加意向鎖

?如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)

點(diǎn)的下層結(jié)點(diǎn)正在被加鎖

例：對(duì)任一元組r加鎖，先關(guān)系R加意向鎖

口

?事務(wù)T要對(duì)關(guān)系R加X(jué)鎖，系統(tǒng)只要檢查根結(jié)點(diǎn)

數(shù)據(jù)庫(kù)和關(guān)系R是否已加了不相容的鎖，

?不需要搜索和檢查R中的每一個(gè)元組是否加了