1、An Introduction to Database System 中國(guó)人民大學(xué)信息學(xué)院 陳紅 數(shù)據(jù)庫(kù)系統(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í)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請(qǐng)封鎖持鎖時(shí)間何時(shí)釋放封

2、鎖等兩段封鎖協(xié)議(Two-Phase Locking，簡(jiǎn)稱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è)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖 在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖 在釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和獲得任何其他封鎖An Introduction to Database System兩段鎖協(xié)議（續(xù)）“兩段”鎖的含義事務(wù)分為兩個(gè)階段 第一階段是獲得封

3、鎖，也稱為擴(kuò)展階段事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是不能再申請(qǐ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é)議，則對(duì)這些事務(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封鎖粒度封鎖對(duì)象的大小稱為封鎖粒度(Granularity) 封鎖的對(duì)象:邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫(kù)中，封鎖對(duì)象：邏輯單元:

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

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

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

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

11、 An Introduction to Database System顯式封鎖和隱式封鎖（續(xù)）對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢查 該數(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)的封鎖）沖突An Introduction to Database System11.6.2 意向鎖引進(jìn)意向鎖（intention lock）目的提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率An Introduction to Database System意向鎖(續(xù))如果對(duì)一個(gè)結(jié)點(diǎn)加

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

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

14、oduction to Database System意向鎖（續(xù)）意向鎖的相容矩陣An Introduction to Database System意向鎖（續(xù)）鎖的強(qiáng)度鎖的強(qiáng)度是指它對(duì)其他鎖的排斥程度一個(gè)事務(wù)在申請(qǐng)封鎖時(shí)以強(qiáng)鎖代替弱鎖是安全的，反之則不然An Introduction to Database System意向鎖（續(xù)）具有意向鎖的多粒度封鎖方法申請(qǐng)封鎖時(shí)應(yīng)該按自上而下的次序進(jìn)行釋放封鎖時(shí)則應(yīng)該按自下而上的次序進(jìn)行 例如：事務(wù)T1要對(duì)關(guān)系R1加S鎖要首先對(duì)數(shù)據(jù)庫(kù)加IS鎖檢查數(shù)據(jù)庫(kù)和R1是否已加了不相容的鎖(X或IX)不再需要搜索和檢查R1中的元組是否加了不相容的鎖(X鎖) An Introduction to Database System意向鎖（續(xù)）具有意向鎖的多粒度封鎖方法提高了系統(tǒng)的并發(fā)度減少了加鎖和解鎖的開(kāi)銷在實(shí)際的數(shù)據(jù)庫(kù)管理系統(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 封鎖的粒度