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

1、An Introduction to Database System 中國人民大學信息學院 陳紅 數(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 小結An Introduction to Database System11.5 兩段鎖協(xié)議封鎖協(xié)議 運用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)則 何時申請封鎖持鎖時間何時釋放封

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

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

4、ction to Database System兩段鎖協(xié)議（續(xù)）事務T1事務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é)議的，因此一定是一個可串行化調(diào)度。如何驗證？ An Introduction to Database System兩段鎖協(xié)議

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

6、議（續(xù)）例 遵守兩段鎖協(xié)議的事務發(fā)生死鎖T1Slock BR(B)=2Xlock A等待等待T2Slock AR(A)=2Xlock A等待遵守兩段鎖協(xié)議的事務可能發(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 小結An Introduction to Database System封鎖粒度封鎖對象的大小稱為封鎖粒度(Granularity) 封鎖的對象:邏輯單元，物理單元 例：在關系數(shù)據(jù)庫中，封鎖對象：邏輯單元:

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

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

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

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

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

12、意向鎖，則說明該結點的下層結點正在被加鎖對任一結點加基本鎖，必須先對它的上層結點加意向鎖例如，對任一元組加鎖時，必須先對它所在的數(shù)據(jù)庫和關系加意向鎖 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鎖如果對一個數(shù)據(jù)對象加IS鎖，表示它的后裔結點擬（意向）加S鎖。 例如：事

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

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