西華師范大學(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ù)庫

共享資源的特點(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í)行帶來的問題

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

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

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

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

重要標(biāo)志之一

8.1并發(fā)控制概述

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

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

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

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

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

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

①讀A=16

②

讀A=16

③A—A-1

寫回A=15

④

A<—A-3

寫回A=13

T1的修改被T2覆蓋了!

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

?丟失修改(lostupdate)

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

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

1.丟失修改

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

入同一數(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無法再現(xiàn)前一次讀

取結(jié)果。

4

三類不可重復(fù)讀

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

lo事務(wù)2對其做了修改，當(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)象(phantom

row)

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ù)庫中的數(shù)據(jù)不一致，

是不正確的數(shù)據(jù)，又稱為“臟”數(shù)據(jù)。0

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

T2

①讀A=16

②

讀A=16

③A-A-1

寫回A=15

④

A—A-1

寫回A=15

(a)丟失修改

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

TiT2

①讀A=50

讀B=100

求和=150

②

讀B=100

B—B*2

寫回B=200

③讀A=50

讀B=200

求和=250

（驗(yàn)算不對）

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

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

TiT2

①讀C=100

C—C*2

寫回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封鎖

、什么是封鎖

、基本封鎖類型

、基本鎖的相容矩陣

一、什么是封鎖

?封鎖就是事務(wù)T在對某個(gè)數(shù)據(jù)對象（例如表、

記錄等）操作之前，先向系統(tǒng)發(fā)出請求，對其

加鎖

?加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的控制,

在事務(wù)T釋放它的鎖之前，其它的事務(wù)不能更

新此數(shù)據(jù)對象。

?封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)

8.2封鎖

、什么是封鎖

、基本封鎖類型

、基本鎖的相容矩陣

二、基本封鎖類型

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

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

是由封鎖的類型決定的。

?基本封鎖類型

-排它鎖（exclusivelock,簡記為X鎖）

-共享鎖（Sharelock,簡記為S鎖）

排它鎖

?排它鎖又稱為寫鎖

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

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

再對A加任何類型的鎖，直到T釋放A上

的鎖

共享鎖

?共享鎖又稱為讀鎖

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

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

直到T釋放A上的S鎖

8.2封鎖

、什么是封鎖

、基本封鎖類型

、基本鎖的相容矩陣

工鎖的相容矩陣

Y=Yes,相容的請求

N=No,不相容的請求

第八章并發(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鎖對數(shù)據(jù)對象加鎖時(shí)，需要約定

一些規(guī)則：封鎖協(xié)議(LockingProtocol)

-何時(shí)申請X鎖或S鎖

-持鎖時(shí)間、何時(shí)釋放

?不同的封鎖協(xié)議，在不同的程度上為并發(fā)操

作的正確調(diào)度提供一定的保證

?常用的封鎖協(xié)議：三級封鎖協(xié)議

1級封鎖協(xié)議

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

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

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

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

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

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

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

數(shù)據(jù)。

1級封鎖協(xié)議

TiT2

①XlockA

獲得

②讀A=16

XlockA

③A-A-1

等待沒有丟失修改

寫回A=15

等待

Commit

等待

UnlockA

等待

④

獲得XlockA

讀A=15

A-A-l

⑤

寫回A=14

Commit

UnlockA

1級封鎖協(xié)議

T?

①XlockA

獲得

②讀A=16

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

寫回A=15

③

讀A=15

(4)Rollback

UnlockA

1級封鎖協(xié)議

T2

①讀A=50

讀B=100

求和=150

②

XlockB

獲得不可重復(fù)讀

讀B=100

B—B*2

寫回B=200

Commit

UnlockB

③讀A=50

讀B=200

求和=250

（驗(yàn)算不對）

2級封鎖協(xié)議

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

力口S鎖，讀完后即可釋放S鎖

?2級封鎖協(xié)議可以防止丟失修改和讀“臟”

數(shù)據(jù)。

?在2級封鎖協(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)算不對）

B—B*2

寫回B=200

Commit

UnlockB

不可重復(fù)讀

3級封鎖協(xié)議

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

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

?3級封鎖協(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

⑤寫回B=200

Commit

UnlockB

3級封鎖協(xié)議

TiT2

①XlockC

讀C=100

C—C*2

寫回C=200

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

SlockC

等待

③ROLLBACK等待

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

UnlockC等待

④獲得SlockC

讀C=100

⑤CommitC

UnlockC

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

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

-什么操作需要申請封鎖

-何時(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ù)可以有效地解決并行操作的一致性問

題，但也帶來一些新的問題

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

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

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

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

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

待。

8.4.1活鎖

lockR

lockR

等待LockR

UnlockLockR

■

等待LockR等待

等待等待

■

Unlock蟒

LockR

等待

如何避免活鎖

采用先來先服務(wù)的策略：

當(dāng)多個(gè)事務(wù)請求封鎖同一數(shù)據(jù)對象時(shí)

?按請求封鎖的先后次序?qū)@些事務(wù)排隊(duì)

?該數(shù)據(jù)對象上的鎖一旦釋放，首先批準(zhǔn)

申請隊(duì)列中第一個(gè)事務(wù)獲得鎖。

8.4.2死鎖

XlockR1

XlockR2

XlockR2

等待XlockR1

等待等待

等待等待

解決死鎖的方法

兩類方法

1.預(yù)防死鎖

2.死鎖的診斷與解除

1.死鎖的預(yù)防

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

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

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

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

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

條件

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

預(yù)防死鎖的方法

?一次封鎖法

?順序封鎖法

(1)一次封鎖法

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

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

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

-擴(kuò)大封鎖范圍

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

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

一次封鎖法（續(xù)）

?難于事先精確確定封鎖對象

-數(shù)據(jù)庫中數(shù)據(jù)是不斷變化的，原來不要求封

鎖的數(shù)據(jù)，在執(zhí)行過程中可能會變成封鎖對

象，所以很難事先精確地確定每個(gè)事務(wù)所要

封鎖的數(shù)據(jù)對象

-解決方法：將事務(wù)在執(zhí)行過程中可能要封鎖

的數(shù)據(jù)對象全部加鎖，這就進(jìn)一步降低了并

發(fā)度。

(2)順序封鎖法

?順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個(gè)封鎖順

序，所有事務(wù)都按這個(gè)順序?qū)嵭蟹怄i。

?順序封鎖法存在的問題

-維護(hù)成本高

-數(shù)據(jù)庫系統(tǒng)中可封鎖的數(shù)據(jù)對象極其眾多，

并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變

化，要維護(hù)這樣極多而且變化的資源的封鎖

順序非常困難，成本很高

順序封鎖法（續(xù)）

-難于實(shí)現(xiàn)

-事務(wù)的封鎖請求可以隨著事務(wù)的執(zhí)行而動態(tài)地

決定，很難事先確定每一個(gè)事務(wù)要封鎖哪些對

象，因此也就很難按規(guī)定的順序去施加封鎖。

例：規(guī)定數(shù)據(jù)對象的封鎖順序?yàn)锳,B,C,D,E。事務(wù)T3起

初要求封鎖數(shù)據(jù)對象B,C,E,但當(dāng)它封鎖了B,C后，才

發(fā)現(xiàn)還需要封鎖A,這樣就破壞了封鎖順序.

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

,結(jié)論

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

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

-DBMS在解決死鎖的問題上更普遍采用的是

診斷并解除死鎖的方法

2.死鎖的診斷與解除

?允許死鎖發(fā)生

?解除死鎖

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

是否存在死鎖

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

檢測死鎖：超時(shí)法

?如果一個(gè)事務(wù)的等待時(shí)間超過了規(guī)

定的時(shí)限，就認(rèn)為發(fā)生了死鎖

?優(yōu)點(diǎn)：實(shí)現(xiàn)簡單

?缺點(diǎn)

-有可能誤判死鎖

-時(shí)限若設(shè)置得太長，死鎖發(fā)生后

不能及時(shí)發(fā)現(xiàn)

等待圖法

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

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

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

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

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

向

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

測事務(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)對并行事務(wù)中并行操作的調(diào)度是的

隨機(jī)的，而不同的調(diào)度可能會產(chǎn)生不同的結(jié)果。

?將所有事務(wù)串行起來的調(diào)度策略一定是正確的

調(diào)度策略。

-如果一個(gè)事務(wù)運(yùn)行過程中沒有其他事務(wù)在同

時(shí)運(yùn)行，也就是說它沒有受到其他事務(wù)的干

擾，那么就可以認(rèn)為該事務(wù)的運(yùn)行結(jié)果是正

常的或者預(yù)想的

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

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

同的結(jié)果，但由于不會將數(shù)據(jù)庫置于不一致狀

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

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

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

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

的調(diào)度。

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

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

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

?串行執(zhí)行

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

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

?交錯執(zhí)行

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

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

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

%

T2

SlockB

Y=B=2

UnlockB

XlockA

A=Y+1

寫回A(=3)

UnlockA

SlockA

X=A=3

UnlockA

XlockB

B=X+1

寫回B(=4)

UnlockB

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

*T2

SlockA

X=A=2

UnlockA

XlockB

B=X+1

寫回B(=3)

UnlockB

SlockB

Y=B=3

UnlockB

XlockA

A=Y+1

寫回A(=4)

UnlockA

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

%

T2

SlockB

Y=B=2

SlockA

X=A=2

UnlockB

UnlockA

XlockA

A=Y+1

寫回A(=3)

XlockB

B=X+1

寫回B(=3)

UnlockA

UnlockB

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

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

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

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

%

T2

SlockB

Y=B=2

UnlockB

XlockA

SlockA

A=Y+1等待

寫回A(=3)等待

UnlockA等待

X=A=3

UnlockA

XlockB

B=X+1

寫回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)度，這也

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

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

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

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

-封鎖方法：兩段鎖（Two-PhaseLocking,簡

稱2PL）協(xié)議

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

-樂觀方法

第八章并發(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.在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，

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

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

任何其他封鎖。

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

?“兩段”鎖的含義

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

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

.第二階段是釋放封鎖，也稱為收縮階段。

兩段鎖協(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ù)，對它們的所有并行

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

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

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

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

的調(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

寫回A=3

等

等待寫回A=3待UnlockB等待

UnlockB等待UnlockAXlockB

UnlockASlockASlockAB=X+1

讀A=3讀A=3寫回B=3

Y=AX=AUnlockB

XlockBUnlockA

B=Y+1XlockBXlockA?

寫回B=4B=X+1A=Y+1I

UnlockB寫回B=4寫回A=3?

UnlockAUnlockBUnlockA,

(a)遵守兩盤鎖協(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é)議與三級封鎖協(xié)議

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

?兩段鎖協(xié)議

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

?三級封鎖協(xié)議

-在不同程度上保證數(shù)據(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ù)對象上的

?封鎖的對象:邏輯單元，物理單元

例：在關(guān)系數(shù)據(jù)庫中，封鎖對象：

-邏輯單元:屬性值、屬性值集合、元組、關(guān)系、索

引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫等

-物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等

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

?封鎖對象可以很大也可以很小

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

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

?封鎖對象的大小稱為封鎖的粒度(Granularity)

?多粒度封鎖(multiplegranularitylocking)

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

的事務(wù)選擇

8.7.1封鎖粒度

＞什么是封鎖粒度

八選擇封鎖粒度的原則

一選擇封鎖粒度的原則

?封鎖的粒度越大，小，

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

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

?系統(tǒng)開銷小，大，

?選擇封鎖粒度：

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

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

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

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

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

單元；

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

位

8.7封鎖的粒度

8.7.1封鎖粒度

8.7.2多粒度封鎖

8.7.3意向鎖

8.7.2多粒度封鎖

?多粒度樹

-以樹形結(jié)構(gòu)來表示多級封鎖粒度

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

-葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度

多粒度封鎖（續(xù)）

例：三級粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫的子

結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。

數(shù)據(jù)庫

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

元/，、&元’…\^組

多粒度封鎖協(xié)議

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

鎖

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

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

?在多粒度封鎖中一個(gè)數(shù)據(jù)對象可能以兩

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

顯式封鎖和隱式封鎖

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

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

據(jù)對象加上了鎖

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

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

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

-有無顯式封鎖與之沖突

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

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

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

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

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

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

8.7封鎖的粒度

8.7.1封鎖粒度

8.7.2多粒度封鎖

8.7.3意向鎖

8.7.3意向鎖

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

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

什么是意向鎖

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

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

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

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

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

口

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

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

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