11.5.1兩段鎖協(xié)議和封鎖的粒度

1、An Introduction to Database System 中國人民大學(xué)信息學(xué)院 陳紅 數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第十一章 并發(fā)控制An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System11.5 兩段鎖協(xié)議封鎖協(xié)議 運(yùn)用封鎖方法時(shí)，對數(shù)據(jù)對象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請封鎖持鎖時(shí)間何時(shí)釋放封

2、鎖等兩段封鎖協(xié)議(Two-Phase Locking，簡稱2PL)是最常用的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可串行化調(diào)度DBMS普遍采用兩段鎖協(xié)議的方法實(shí)現(xiàn)并發(fā)調(diào)度的可串行性，從而保證調(diào)度的正確性 An Introduction to Database System兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議 指所有事務(wù)必須分兩個(gè)階段對數(shù)據(jù)項(xiàng)加鎖和解鎖 在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對該數(shù)據(jù)的封鎖 在釋放一個(gè)封鎖之后，事務(wù)不再申請和獲得任何其他封鎖An Introduction to Database System兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義事務(wù)分為兩個(gè)階段 第一階段是獲得封

3、鎖，也稱為擴(kuò)展階段事務(wù)可以申請獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請任何鎖 An Introduction to Database System兩段鎖協(xié)議（續(xù)）例事務(wù)Ti遵守兩段鎖協(xié)議，其封鎖序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock C；| 擴(kuò)展階段 | 收縮階段 |事務(wù)Tj不遵守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B；An Introdu

4、ction to Database System兩段鎖協(xié)議（續(xù)）事務(wù)T1事務(wù)T2Slock(A)R(A)=260Slock(C)R(C)=300Xlock(A)W(A)=160Xlock( C )W(C)=250Slock(A)Slock(B)等待R(B)=1000等待Xlock(B)等待W(B)=1100 等待Unlock(A)等待R(A)=160Xlock(A)Unlock(B)W(A)=210Unlock( C )遵守兩段鎖協(xié)議的可串行化調(diào)度左圖的調(diào)度是遵守兩段鎖協(xié)議的，因此一定是一個(gè)可串行化調(diào)度。如何驗(yàn)證？ An Introduction to Database System兩段鎖協(xié)議

5、（續(xù)）事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的若并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都符合兩段鎖協(xié)議 An Introduction to Database System兩段鎖協(xié)議（續(xù)）兩段鎖協(xié)議與防止死鎖的一次封鎖法一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖An Introduction to Database System兩段鎖協(xié)

6、議（續(xù)）例 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖T1Slock BR(B)=2Xlock A等待等待T2Slock AR(A)=2Xlock A等待遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖 An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度11.7 小結(jié)An Introduction to Database System封鎖粒度封鎖對象的大小稱為封鎖粒度(Granularity) 封鎖的對象:邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫中，封鎖對象：邏輯單元:

7、 屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫等物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等An Introduction to Database System選擇封鎖粒度原則封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開銷密切相關(guān)。封鎖的粒度越大，數(shù)據(jù)庫所能夠封鎖的數(shù)據(jù)單元就越少，并發(fā)度就越小，系統(tǒng)開銷也越??；封鎖的粒度越小，并發(fā)度較高，但系統(tǒng)開銷也就越大An Introduction to Database System選擇封鎖粒度的原則（續(xù)）例若封鎖粒度是數(shù)據(jù)頁，事務(wù)T1需要修改元組L1，則T1必須對包含L1的整個(gè)數(shù)據(jù)頁A加鎖。如果T1對A加鎖后事務(wù)T2要修改A中元組L2，則T2被迫

8、等待，直到T1釋放A。如果封鎖粒度是元組，則T1和T2可以同時(shí)對L1和L2加鎖，不需要互相等待，提高了系統(tǒng)的并行度。又如，事務(wù)T需要讀取整個(gè)表，若封鎖粒度是元組，T必須對表中的每一個(gè)元組加鎖，開銷極大 An Introduction to Database System選擇封鎖粒度的原則（續(xù)）多粒度封鎖(Multiple Granularity Locking) 在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇選擇封鎖粒度 同時(shí)考慮封鎖開銷和并發(fā)度兩個(gè)因素, 適當(dāng)選擇封鎖粒度需要處理多個(gè)關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫為封鎖單位需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元只處理少量元組的用戶

9、事務(wù)：以元組為封鎖單位An Introduction to Database System11.6.1 多粒度封鎖多粒度樹以樹形結(jié)構(gòu)來表示多級封鎖粒度根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度 An Introduction to Database System多粒度封鎖（續(xù)）例：三級粒度樹。根結(jié)點(diǎn)為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)點(diǎn)為關(guān)系，關(guān)系的子結(jié)點(diǎn)為元組。數(shù)據(jù)庫關(guān)系Rn關(guān)系R1元組元組元組元組 三級粒度樹An Introduction to Database System多粒度封鎖協(xié)議允許多粒度樹中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖對一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的

10、鎖在多粒度封鎖中一個(gè)數(shù)據(jù)對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖An Introduction to Database System顯式封鎖和隱式封鎖顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖隱式封鎖:是該數(shù)據(jù)對象沒有獨(dú)立加鎖，是由于其上級結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對象加上了鎖顯式封鎖和隱式封鎖的效果是一樣的An Introduction to Database System顯式封鎖和隱式封鎖（續(xù)）系統(tǒng)檢查封鎖沖突時(shí)要檢查顯式封鎖還要檢查隱式封鎖例如事務(wù)T要對關(guān)系R1加X鎖系統(tǒng)必須搜索其上級結(jié)點(diǎn)數(shù)據(jù)庫、關(guān)系R1還要搜索R1的下級結(jié)點(diǎn)，即R1中的每一個(gè)元組如果其中某一個(gè)數(shù)據(jù)對象已經(jīng)加了不相容鎖，則T必須等待

11、 An Introduction to Database System顯式封鎖和隱式封鎖（續(xù)）對某個(gè)數(shù)據(jù)對象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對象有無顯式封鎖與之沖突 所有上級結(jié)點(diǎn)檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對象上的隱式封鎖沖突：(由上級結(jié)點(diǎn)已加的封鎖造成的）所有下級結(jié)點(diǎn)看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加到下級結(jié)點(diǎn)的封鎖）沖突An Introduction to Database System11.6.2 意向鎖引進(jìn)意向鎖（intention lock）目的提高對某個(gè)數(shù)據(jù)對象加鎖時(shí)系統(tǒng)的檢查效率An Introduction to Database System意向鎖(續(xù))如果對一個(gè)結(jié)點(diǎn)加

12、意向鎖，則說明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖對任一結(jié)點(diǎn)加基本鎖，必須先對它的上層結(jié)點(diǎn)加意向鎖例如，對任一元組加鎖時(shí)，必須先對它所在的數(shù)據(jù)庫和關(guān)系加意向鎖 An Introduction to Database System常用意向鎖意向共享鎖(Intent Share Lock，簡稱IS鎖)意向排它鎖(Intent Exclusive Lock，簡稱IX鎖)共享意向排它鎖(Share Intent Exclusive Lock，簡稱SIX鎖)An Introduction to Database System意向鎖（續(xù)）IS鎖如果對一個(gè)數(shù)據(jù)對象加IS鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加S鎖。 例如：事

13、務(wù)T1要對R1中某個(gè)元組加S鎖，則要首先對關(guān)系R1和數(shù)據(jù)庫加IS鎖 An Introduction to Database System意向鎖（續(xù)）IX鎖如果對一個(gè)數(shù)據(jù)對象加IX鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加X鎖。 例如：事務(wù)T1要對R1中某個(gè)元組加X鎖，則要首先對關(guān) 系R1和數(shù)據(jù)庫加IX鎖 An Introduction to Database System意向鎖（續(xù)）SIX鎖如果對一個(gè)數(shù)據(jù)對象加SIX鎖，表示對它加S鎖，再加IX鎖，即SIX = S + IX。 例：對某個(gè)表加SIX鎖，則表示該事務(wù)要讀整個(gè)表（所以要對該表加S鎖），同時(shí)會(huì)更新個(gè)別元組（所以要對該表加IX鎖）。An Intr

14、oduction to Database System意向鎖（續(xù)）意向鎖的相容矩陣An Introduction to Database System意向鎖（續(xù)）鎖的強(qiáng)度鎖的強(qiáng)度是指它對其他鎖的排斥程度一個(gè)事務(wù)在申請封鎖時(shí)以強(qiáng)鎖代替弱鎖是安全的，反之則不然An Introduction to Database System意向鎖（續(xù)）具有意向鎖的多粒度封鎖方法申請封鎖時(shí)應(yīng)該按自上而下的次序進(jìn)行釋放封鎖時(shí)則應(yīng)該按自下而上的次序進(jìn)行 例如：事務(wù)T1要對關(guān)系R1加S鎖要首先對數(shù)據(jù)庫加IS鎖檢查數(shù)據(jù)庫和R1是否已加了不相容的鎖(X或IX)不再需要搜索和檢查R1中的元組是否加了不相容的鎖(X鎖) An Introduction to Database System意向鎖（續(xù)）具有意向鎖的多粒度封鎖方法提高了系統(tǒng)的并發(fā)度減少了加鎖和解鎖的開銷在實(shí)際的數(shù)據(jù)庫管理系統(tǒng)產(chǎn)品中得到廣泛應(yīng)用 An Introduction to Database System第十一章 并發(fā)控制11.1 并發(fā)控制概述11.2 封鎖11.3 活鎖和死鎖11.4 并發(fā)調(diào)度的可串行性11.5 兩段鎖協(xié)議11.6 封鎖的粒度