并發(fā)控制-課件

第十一章并發(fā)控制

1ppt課件主要內(nèi)容11.1并發(fā)控制概述11.2封鎖11.3活鎖和死鎖11.4并發(fā)調(diào)度的可串行性11.5兩段鎖協(xié)議11.6封鎖的粒度2ppt課件11.1并發(fā)控制概述多事務(wù)執(zhí)行方式(1)事務(wù)串行執(zhí)行(2)交叉并發(fā)方式(3)同時并發(fā)方式并發(fā)是指在單處理機(jī)上，利用分時方法實行多個事務(wù)同時做。事務(wù)并發(fā)執(zhí)行帶來的問題可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)的隔離性和一致性3ppt課件DBMS必須提供并發(fā)控制機(jī)制DBMS的并發(fā)控制子系統(tǒng)保證事務(wù)的隔離性保證事務(wù)的一致性對并發(fā)操作進(jìn)行正確調(diào)度4ppt課件并發(fā)操作帶來的問題1---丟失更新時間更新事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1R（A）

t2

R（A）t3A:=A-1

t4

A:=A-1t5W（A）

t6

99W（A）t7

99

圖在時間t7丟失了事務(wù)T1的更新5ppt課件時間更新事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1R（A）

t2

t3

t4

t5

COMMITt6

圖事務(wù)T1兩次讀取A的值，卻得到了不同的結(jié)果R（A）200R（A）A:=A*2W（A）并發(fā)操作帶來的問題2---不可重復(fù)讀問題6ppt課件并發(fā)操作帶來的問題3---讀臟數(shù)據(jù)時間更新事務(wù)T1數(shù)據(jù)庫中A的值讀事務(wù)T2t0

100

t1R（A）

t2A:=A-30

t3W（A）

t4

70R（A）t5ROLLBACK

t6

100

圖事務(wù)T2在時間t4讀了未提交的A值（70）

7ppt課件

并發(fā)控制就是用正確的方式調(diào)度并發(fā)操作，使一個用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性。8ppt課件11.2封鎖封鎖是實現(xiàn)并發(fā)控制的一個主要技術(shù)。鎖（Lock）是一個與數(shù)據(jù)項相關(guān)的變量，對可能應(yīng)用于該數(shù)據(jù)項上的操作而言，鎖描述了該數(shù)據(jù)項的狀態(tài)。兩種封鎖：

-排他型（Exclusive）封鎖（簡稱：X鎖）

-共享型（Share）封鎖（簡稱：S鎖）9ppt課件X鎖（排它鎖）排它鎖又稱為寫鎖若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對A加任何類型的鎖，直到T釋放A上的鎖。X鎖的操作XlockA：表示事務(wù)對數(shù)據(jù)A加X鎖，并讀數(shù)據(jù)AunlockA：表示事務(wù)要解除對數(shù)據(jù)A的X鎖10ppt課件X鎖PX協(xié)議:

使用X鎖的規(guī)則稱為PX協(xié)議。任何企圖更新記錄R的事務(wù)必須先執(zhí)行“XlockR”操作，以獲得對R的X鎖，才能讀或?qū)懹涗汻；如果未獲準(zhǔn)X鎖，那么這個事務(wù)進(jìn)入等待隊列，一直到獲準(zhǔn)X鎖，事務(wù)才能繼續(xù)做下去。

PXC協(xié)議

X鎖的解除操作應(yīng)該合并到事務(wù)的結(jié)束（COMMIT或ROLLBACK）操作中。引入此規(guī)則，PX協(xié)議成為PXC協(xié)議。11ppt課件S鎖（共享鎖）S鎖定義若事務(wù)T對數(shù)據(jù)對象A加上S鎖，則事務(wù)T可以讀A但不能修改A。其它事務(wù)只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖。操作SlockA

表示事務(wù)對數(shù)據(jù)A加S鎖，并讀數(shù)據(jù)。UnlockA

表示事務(wù)要解除對數(shù)據(jù)A的S鎖。允許并發(fā)的讀，又稱為‘讀鎖’12ppt課件封鎖的相容矩陣注：①N=NO，不相容的請求Y=YES，相容的請求②X、S、－：分別表示X鎖，S鎖，無鎖③如果兩個封鎖是不相容的，則后提出封鎖的事務(wù)要等待。XS—

X

S

—

NNY

NYY

YYY

T2T1

13ppt課件例：使用X鎖封鎖解決數(shù)據(jù)丟失時間更新事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1XlockA

t2

XlockAt3R（A）

waitt4A:=A-1

waitt5

waitt6W（A）

waitt7

COMMIT99waitt8UnlockA

waitt9

獲得XlockAt10

R（A）t11

A：=A-1t12

98W（A）14ppt課件11.3活鎖和死鎖

封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題。死鎖活鎖15ppt課件1.“活鎖”T2XlockAT3XlockAT4XlockAAA已被封鎖，不成功，等待A剛被釋放，成功時間點A剛被釋放，成功……T2永遠(yuǎn)等待活鎖！解決方法：先來先服務(wù)系統(tǒng)可能使某個事務(wù)永遠(yuǎn)處于等待狀態(tài)，得不到封鎖的機(jī)會，這種現(xiàn)象稱為“活鎖”。16ppt課件2.“死鎖”時間事務(wù)T1事務(wù)T2t0XlockA

t1

XlockBt2XlockB

t3waitXlockAt4waitwait出現(xiàn)了T1在等待T2，而T2又在等待T1的局面，T1和T2兩個事務(wù)永遠(yuǎn)不能結(jié)束，形成了死鎖。17ppt課件

解決死鎖的方法兩類方法1）預(yù)防死鎖2）死鎖的診斷與解除18ppt課件1）死鎖的預(yù)防預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件。預(yù)防死鎖的方法一次封鎖法順序封鎖法19ppt課件一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行一次封鎖法存在的問題擴(kuò)大封鎖范圍難于事先精確確定封鎖對象20ppt課件順序封鎖法順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務(wù)都按這個順序?qū)嵭蟹怄i。順序封鎖法存在的問題維護(hù)成本高難于實現(xiàn)21ppt課件2）死鎖的診斷與解除允許死鎖發(fā)生解除死鎖由DBMS的并發(fā)控制子系統(tǒng)定期檢測系統(tǒng)中是否存在死鎖一旦檢測到死鎖，就要設(shè)法解除22ppt課件“死鎖的診斷”若事務(wù)等待圖有環(huán)，則表示出現(xiàn)死鎖圖事務(wù)的有環(huán)依賴圖1）超時法2）等待圖法圖：結(jié)點表示正運行的事務(wù)。邊表示事務(wù)等待的情況。T1T223ppt課件“死鎖的解除”死鎖測試程序：選擇一個處理死鎖代價最小的事務(wù)，將其撤消，釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運行下去。24ppt課件11.4并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的25ppt課件事務(wù)的調(diào)度事務(wù)的執(zhí)行次序稱為“調(diào)度”串行調(diào)度如果多個事務(wù)依次執(zhí)行，則稱為事務(wù)的串行調(diào)度（SerialSchedule）并發(fā)調(diào)度如果利用分時的方法，同時處理多個事務(wù)，則稱為事務(wù)的并發(fā)調(diào)度（ConcurrentSchedule）26ppt課件一、什么樣的并發(fā)操作調(diào)度是正確的計算機(jī)系統(tǒng)對并行事務(wù)中并行操作的調(diào)度是的隨機(jī)的，而不同的調(diào)度可能會產(chǎn)生不同的結(jié)果。將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。以不同的順序串行執(zhí)行事務(wù)也有可能會產(chǎn)生不同的結(jié)果，但由于不會將數(shù)據(jù)庫置于不一致狀態(tài)，所以都可以認(rèn)為是正確的。幾個事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行這些事務(wù)時的結(jié)果相同。這種并行調(diào)度策略稱為可串行化（Serializable）的調(diào)度?？纱行允遣⑿惺聞?wù)正確性的唯一準(zhǔn)則27ppt課件例：現(xiàn)在有兩個事務(wù)，分別包含下列操作：事務(wù)1：讀B；A=B+1；寫回A；事務(wù)2：讀A；B=A+1；寫回B；假設(shè)A的初值為2，B的初值為2。對這兩個事務(wù)的不同調(diào)度策略串行執(zhí)行串行調(diào)度策略1串行調(diào)度策略2交錯執(zhí)行不可串行化的調(diào)度可串行化的調(diào)度28ppt課件串行調(diào)度策略，正確的調(diào)度SlockBY=B=2UnlockBXlockAA=Y+1寫回A(=3)UnlockA

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

T1T2

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

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

T1T229ppt課件并行調(diào)度策略T2SlockBY=B=2

UnlockB

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

UnlockA

SlockAX=A=2

UnlockA

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

UnlockBT1SlockBY=B=2UnlockBXlockA

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

SlockA

等待等待等待X=A=3UnlockAXlockBB=X+1寫回B(=4)UnlockBT1T2不可串行化的調(diào)度可串行化的調(diào)度30ppt課件二、如何保證并發(fā)操作的調(diào)度是正確的保證并發(fā)操作調(diào)度正確性的方法封鎖方法：兩段鎖（Two-PhaseLocking，簡稱2PL）協(xié)議時標(biāo)方法樂觀方法31ppt課件兩段封鎖協(xié)議是最常用的一種封鎖協(xié)議。封鎖協(xié)議在運用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)則，例如何時申請封鎖、持鎖時間、何時釋放封鎖等。我們稱這些規(guī)格為封鎖協(xié)議。32ppt課件11.5兩段鎖協(xié)議兩段鎖協(xié)議是指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖。內(nèi)容1.在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對該數(shù)據(jù)的封鎖2.在釋放一個封鎖之后，事務(wù)不再獲得任何其他封鎖。33ppt課件“兩段”鎖的含義事務(wù)分為兩個階段第一階段是獲得封鎖，也稱為擴(kuò)展階段；第二階段是釋放封鎖，也稱為收縮階段。例：事務(wù)1的封鎖序列：SlockA...SlockB...XlockC...UnlockB...UnlockA...UnlockC；事務(wù)2的封鎖序列：SlockA...UnlockA...SlockB...XlockC...UnlockC...UnlockB；事務(wù)1遵守兩段鎖協(xié)議，而事務(wù)2不遵守兩段協(xié)議。34ppt課件結(jié)論并行執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對這些事務(wù)的所有并行調(diào)度策略都是可串行化的。

所有遵守兩段鎖協(xié)議的事務(wù)，其并行執(zhí)行的結(jié)果一定是正確的事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件可串行化的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)議。35ppt課件圖遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖T1SlockB讀B=2

XlockA等待等待T2

SlockA讀A=2

XlockA等待36ppt課件11.6封鎖的粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則37ppt課件一、什么是封鎖粒度X鎖和S鎖都是加在某一個數(shù)據(jù)對象上的封鎖的對象:邏輯單元，物理單元

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