第7章并發(fā)控制

1、DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 數(shù)據(jù)庫系統(tǒng)與應(yīng)用數(shù)據(jù)庫系統(tǒng)與應(yīng)用_第7章 并發(fā)控制 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院鄭莉華鄭莉華 cd_DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l7.1 事務(wù)的并發(fā)執(zhí)行 l7.2 并發(fā)執(zhí)行可能引起的問題 l7.3 可串行化 l7.4 基于鎖的并發(fā)控制協(xié)議 l7.5 活鎖與死鎖 l7.6 多粒度封鎖 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.1 事務(wù)的并發(fā)執(zhí)行l(wèi)并發(fā)執(zhí)行優(yōu)點(diǎn)改善系統(tǒng)的資源利用率

2、 減少短事務(wù)的等待時間 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 調(diào)度調(diào)度(schedule)(schedule)一個或多個事務(wù)的操作按時間排序的一個序列一個事務(wù)的兩個操作在調(diào)度中出現(xiàn)的順序必須與其在事務(wù)內(nèi)定義的先后順序一致7.1 事務(wù)的并發(fā)執(zhí)行DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.2 并發(fā)執(zhí)行可能引起的問題 臟數(shù)據(jù)(dirty data) 是對未提交事務(wù)所寫數(shù)據(jù)的統(tǒng)稱 若臟讀造成了數(shù)據(jù)庫的不一致狀態(tài)，應(yīng)嚴(yán)格禁止 若臟讀帶來的影響足夠小，偶爾可讀一次臟數(shù)據(jù)，它可以提高并發(fā)性，減少事務(wù)的等待時

3、間 讀臟數(shù)據(jù)（讀臟數(shù)據(jù)（dirty readdirty read）DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 不可重復(fù)讀不可重復(fù)讀(unrepeatable read) (unrepeatable read) 事務(wù)T1的兩次讀取數(shù)據(jù)之間，其它事務(wù)修改了它要讀取的數(shù)據(jù)，以致兩次讀到的值不同 在事務(wù)串行執(zhí)行時，不會出現(xiàn)此現(xiàn)象 7.2 并發(fā)執(zhí)行可能引起的問題 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 丟失更新丟失更新(lost update) (lost update) 由兩個事務(wù)對同一數(shù)據(jù)并發(fā)地寫入引起

4、7.2 并發(fā)執(zhí)行可能引起的問題 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.3 可串行化l回顧：事務(wù)ACID特性中的隔離性l事務(wù)在運(yùn)行中不受其它事務(wù)干擾的方法：每個事務(wù)依次順序執(zhí)行 事務(wù)之間并發(fā)執(zhí)行，DBMS調(diào)整事務(wù)的調(diào)度，使其運(yùn)行結(jié)果與一次只執(zhí)行一個事務(wù)的結(jié)果相同DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.3.1 7.3.1 串行調(diào)度串行調(diào)度 l串行調(diào)度：不同事務(wù)的活動在調(diào)度中是一個接一個執(zhí)行的，沒有交叉的運(yùn)行。7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)

5、算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 兩個串行調(diào)度的結(jié)果不同。但只要保持了數(shù)據(jù)庫的一致性，最終的結(jié)果并不重要 【例7-1】 ：串行調(diào)度4 串行調(diào)度57.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.3.2 7.3.2 可串行化調(diào)度可串行化調(diào)度 l調(diào)度是可串行化的：多個事務(wù)交叉調(diào)度的結(jié)果與某一個串行調(diào)度的結(jié)果相同lDBMS認(rèn)為事務(wù)串行調(diào)度的結(jié)果保持了數(shù)據(jù)庫的一致性，都是正確的 l一個調(diào)度如果是可串行化的，系統(tǒng)認(rèn)為其調(diào)度是一個正確的調(diào)度，保持了數(shù)據(jù)庫的一致性 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)

6、據(jù)庫數(shù)據(jù)庫 【例7-2】：例7-1中事務(wù)的另外一種調(diào)度方式:調(diào)度6 它的結(jié)果和書中串行調(diào)度4的結(jié)果相同，因此該調(diào)度是可串行的調(diào)度 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-2】：例7-1中事務(wù)的另外一種調(diào)度方式：調(diào)度7 調(diào)度7最終的結(jié)果與串行調(diào)度4、串行調(diào)度5中的任何一個結(jié)果都不一致，是一個不可串行化的調(diào)度。7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l如果將事務(wù)的并發(fā)執(zhí)行完全交給操作系統(tǒng)，則任何一種調(diào)度方式都有可能出現(xiàn)。有的調(diào)度能保持?jǐn)?shù)據(jù)庫的一致，有的調(diào)度卻會

7、產(chǎn)生錯誤的結(jié)果。因此:DBMS必須對事務(wù)的運(yùn)行加以控制，確保交叉調(diào)度完畢后的結(jié)果與某一串行調(diào)度的結(jié)果相同，數(shù)據(jù)庫不會出現(xiàn)不一致的狀態(tài)。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 設(shè)WRITE簡寫為W，READ簡寫為R，WT(X)、RT(X)分別表示事務(wù)T寫和讀數(shù)據(jù)庫元素X，S表示一個調(diào)度。這樣，圖7.8的調(diào)度7可表示為： S=R1（A）R2（A）W1（A）W2（A）R2（B）R1（B）W2（B）W1(B) 7.3 可串行化沖突可串行化沖突可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)

8、庫 考慮一個調(diào)度S，涉及事務(wù)Ti 和Tj （i j）,事務(wù)Ti的操作對象元素為A，事務(wù)Tj的操作對象元素為B。若AB，很明顯，事務(wù)Ti 和Tj 是對不同的數(shù)據(jù)庫元素進(jìn)行操作，不論它們的執(zhí)行動作是讀還是寫，執(zhí)行的先后順序都不會影響數(shù)據(jù)庫中的最終結(jié)果。若A=B，則事務(wù)的執(zhí)行順序就很重要。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l若事務(wù)Ti 和Tj都是讀取數(shù)據(jù)R1（A），R2（A），則Ri（A），Rj（A）指令不發(fā)生沖突l若事務(wù)Ti 和Tj一個是讀數(shù)據(jù)，一個是寫數(shù)據(jù)，則事務(wù)的執(zhí)行順序是重要的。Ri（A）和Wj（A）指令是沖突的l若事

9、務(wù)Ti 和Tj都是寫數(shù)據(jù)W1（A），W2（A），則Wi（A）和Wj（A）指令也是沖突的7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 調(diào)度S中兩個事務(wù)的操作要發(fā)生沖突，必須：對同一數(shù)據(jù)對象進(jìn)行操作兩個操作指令中有一個是寫操作W 例如：圖7.8的調(diào)度7S=R1（A）R2（A）W1（A）W2（A）R2（B）R1（B）W2（B）W1(B)T2事務(wù)的READ（A）與T1事務(wù)的WRITE（A）是沖突指令，但T1事務(wù)的READ（A）與T2事務(wù)的READ（A）指令是不沖突。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)

10、科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l沖突等價：若調(diào)度S中屬于不同事務(wù)的兩條操作指令是不沖突的，則可以交換兩條指令的執(zhí)行順序，得到一個新的調(diào)度S。稱調(diào)度S與調(diào)度S沖突等價的（conflict equivalent）。l沖突可串行化：若一個調(diào)度沖突等價于一個串行調(diào)度，則該調(diào)度是沖突可串行化的。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 考慮前面的調(diào)度6：S= R1（A）W1（A）R2（A）W2（A）R1（B）W1（B）R2（B）W2（B）調(diào)度中的R1（B）與W2（A）指令不沖突，可以交換執(zhí)行順序；R1（B）與R2（A）指令不沖突，可以交換

11、執(zhí)行順序；W1（B）與W2（A）指令不沖突，可以交換執(zhí)行順序；W1（B）與R2（A）指令不沖突，可以交換執(zhí)行順序。在四個交換之后，得到新的調(diào)度S：S= R1（A）W1（A）R1（B）W1（B）R2（A）W2（A）R2（B）W2（B）調(diào)度S是一個串行調(diào)度，即前面的調(diào)度4。因此，調(diào)度6等價于串行調(diào)度4，是沖突可串行化的。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l沖突可串行是可串行性的充分條件 調(diào)度運(yùn)行結(jié)果與串行調(diào)度T1T2T3的運(yùn)行結(jié)果是一致的，但調(diào)度不是沖突可串行的 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科

12、技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.3 可串行化視圖可串行化視圖可串行化l視圖等價：對同一事務(wù)集，如果兩個調(diào)度S1和S2在任何時候都保證每個事務(wù)讀取相同的值，寫入數(shù)據(jù)庫的最終狀態(tài)也是一樣的，則稱調(diào)度S1和S2視圖等價。DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 調(diào)度4和調(diào)度5不是視圖等價的，因?yàn)檎{(diào)度4中T2事務(wù)讀取的A值是事務(wù)T1修改后的值，而調(diào)度5中T2事務(wù)讀取的A值是事務(wù)T1修改前的值。 調(diào)度4 調(diào)度57.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 調(diào)度4和調(diào)度6是視圖等價的

13、，因?yàn)閮蓚€調(diào)度中，事務(wù)T1讀取的都是數(shù)據(jù)庫的初始值，事務(wù)T2讀取的數(shù)據(jù)都是事務(wù)T1修改后的值，數(shù)據(jù)庫中藥品A、B的最終狀態(tài)都是由事務(wù)T2寫入的。 7.3 可串行化 調(diào)度4 調(diào)度6DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l視圖可串行化：如果某個調(diào)度視圖等價于一個串行調(diào)度，則稱這個調(diào)度是視圖可串行化的 l如果調(diào)度是沖突可串行化的，則該調(diào)度一定是視圖可串行化的。但反過來未必成立。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-3】：設(shè)調(diào)度S1為事務(wù)T1、T2、T3的一個可能調(diào)度：S1

14、=R1（A）W3（A）R2（B）W1（B）經(jīng)過非沖突指令順序的調(diào)整，得到調(diào)度S2：S2=R2（B）R1（A）W1（B）W3（A）調(diào)度S1和調(diào)度S2是沖突等價的。又因?yàn)檎{(diào)度S2為一串行調(diào)度，因此調(diào)度S1是沖突可串行化的。對于調(diào)度S1和S2，事務(wù)T1讀取的A、事務(wù)T2讀取的B都是數(shù)據(jù)庫的初始值；數(shù)據(jù)庫最終的A、B值都是由事務(wù)T3和T1寫入的。因此，調(diào)度S1和S2是視圖可串行化的。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-4】：設(shè)調(diào)度S為事務(wù)T1、T2、T3的一個可能調(diào)度：S=R1（A）W2（A）W1（A）W3（A）該調(diào)度與串

15、行調(diào)度T1T2T3是視圖等價的，因?yàn)樵趦蓚€調(diào)度中讀取的A都是數(shù)據(jù)庫的初始值，數(shù)據(jù)庫中A的最終值都是T3寫入的。調(diào)度S視圖可串行化。但調(diào)度S明顯不是沖突可串行化的，每對連續(xù)指令都是沖突的。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l判定一個調(diào)度是否是沖突可串行化的，可以使用前驅(qū)圖（precedence graph）l在構(gòu)造的前驅(qū)圖中若存在環(huán)，則表示調(diào)度S是不可串行化的。反之，若前驅(qū)圖中不存在環(huán)，表示調(diào)度S是沖突可串行化的，可用拓?fù)渑判虻玫秸{(diào)度S 的一個等價的串行調(diào)度。 7.3 可串行化可串行化判定可串行化判定DataBaseUES

16、TC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 前驅(qū)圖是一個有向圖G=（V，E）。頂點(diǎn)代表調(diào)度S 中的事務(wù)，由TiTj 的邊表示在調(diào)度S中Ti 和Tj之間存在一對沖突指令，并且Ti中的指令先于Tj 中的指令執(zhí)行?！纠?-5】：考慮前面的調(diào)度6：S= R1（A）W1（A）R2（A）W2（A）R1（B）W1（B）R2（B）W2（B）在S中，沖突指令W1（A）在R2（A）前，W1（B）在R2（B）前，因此存在從T1到T2的有向邊。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-6】：考慮前面的調(diào)度7：S=R1（A

17、）R2（A）W1（A）W2（A）R2（B）R1（B）W2（B）W1(B)在S中，沖突指令W1（A）在W2（A）之前，R1（B）在W2（B）之前，因此存在T1到T2的有向邊；此外， R2（A）在W1（A）之前，W2（B）在W1(B)之前，因此存在T2到T1的有向邊。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.3.3 7.3.3 可恢復(fù)性可恢復(fù)性 一個無法恢復(fù)的調(diào)度是不允許的。數(shù)據(jù)庫系統(tǒng)要求所有的調(diào)度都是可恢復(fù)的 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 調(diào)度是可恢復(fù)

18、的需滿足：l調(diào)度S中，事務(wù)Ti如果讀取了事務(wù)Tj修改過的數(shù)據(jù)，則事務(wù)Ti必須等事務(wù)Tj提交后才能提交 。7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-7】： 調(diào)度S1是可恢復(fù)的，可串行的：S1=R1（A）W1（A）R2（A）W1（B）W2（B）C1 C2 調(diào)度S2是可恢復(fù)的，但不是可串行的：S2=R1（A）W1（A）R2（A）W2（B）W1（B）C1 C2 調(diào)度S3：是不可恢復(fù)的，但是可串行的 S3=R1（A）W1（A）R2（A）W1（B）W2（B）C2 C1 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大

19、學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l 事務(wù)在并行執(zhí)行過程中發(fā)生故障，還可能引起多個事務(wù)的級聯(lián)回滾 。例：在前面的臟讀例子中，假定T2事務(wù)讀取A 的值并修改，另外還有T3事務(wù)讀取T2修改后的值，并做了修改，依次類推，有多個事務(wù)都對A做了修改。若事務(wù)T1發(fā)生故障時，后續(xù)的事務(wù)T2、T3、T4.都已提交，則事務(wù)T1的回滾導(dǎo)致級聯(lián)回滾，產(chǎn)生大量的撤銷工作。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 無級聯(lián)回滾的調(diào)度應(yīng)滿足：l調(diào)度S中的每對事務(wù)Ti和Tj，事務(wù)Ti如果讀取了事務(wù)Tj修改過的數(shù)據(jù)，則事務(wù)Tj必須在Ti讀取前提交即調(diào)度禁止

20、讀取臟數(shù)據(jù)。 7.3 可串行化DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.4 基于鎖的并發(fā)控制協(xié)議 l事務(wù)執(zhí)行過程中鎖的申請和釋放由DBMS中的鎖管理器（lock manager）負(fù)責(zé) l鎖表包含的信息包括：每個數(shù)據(jù)庫對象上已有的鎖的個數(shù)、鎖的類型以及一個指向申請鎖隊(duì)列的指針 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.4.1 7.4.1 封鎖封鎖l共享鎖（S鎖）：如果事務(wù)Ti申請到數(shù)據(jù)項(xiàng)Q 的共享鎖，則Ti可以讀數(shù)據(jù)項(xiàng)Q，但不能寫Q。l排它鎖（X鎖）：如果事務(wù)Ti申請到數(shù)據(jù)項(xiàng)Q 的排它鎖，則T

21、i可以讀數(shù)據(jù)項(xiàng)Q，也可以寫Q。 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 鎖的相容矩陣鎖的相容矩陣 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 當(dāng)事務(wù)需要數(shù)據(jù)項(xiàng)上的一個鎖時，它向鎖管理器發(fā)出鎖的申請：l若申請的是一個共享鎖，且申請隊(duì)列為空，當(dāng)前數(shù)據(jù)項(xiàng)上也沒有排它鎖，則鎖管理器授予鎖，并修改數(shù)據(jù)項(xiàng)的鎖表。l若申請的是一個排它鎖，當(dāng)前也沒有其它的事務(wù)擁有該數(shù)據(jù)項(xiàng)上的鎖，則鎖管理器授予鎖，并修改數(shù)據(jù)項(xiàng)的鎖表。l否則，申請的鎖不能馬上授予，鎖申請加入

22、申請隊(duì)列，申請鎖的事務(wù)掛起。 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 【例7-8】：調(diào)度9 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 圖（a）中 ，該封鎖在更新后立即釋放，有可能引起其它事務(wù)的臟讀 圖（b）中 ，事務(wù)將鎖的釋放都放到事務(wù)的最后，這樣可以有效避免（a）中可能出現(xiàn)的臟讀情況，并保證了事務(wù)執(zhí)行的可串行性 。但該封鎖方式在一定程度上降低了并發(fā)度，可能會出現(xiàn)一種稱之為死鎖的狀況，如圖（c）所示7.4 基于鎖的并發(fā)控制協(xié)議 DataB

23、aseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l 如果不使用封鎖，或者光對并發(fā)執(zhí)行的事務(wù)加鎖，對鎖的申請和釋放時間卻不加控制，就不能保證事務(wù)執(zhí)行的可串行性，數(shù)據(jù)庫的一致狀態(tài)仍有可能被破壞 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.4.2 7.4.2 兩段鎖協(xié)議（兩段鎖協(xié)議（2PL2PL）保證可串行性的一個協(xié)議是兩段鎖協(xié)議（two-phase locking protocol）。所謂兩段鎖協(xié)議是指所有事務(wù)分兩個階段提出加鎖和解鎖申請l增長階段（growing phase)：在對任何

24、數(shù)據(jù)進(jìn)行讀、寫操作之前，首先申請并獲得該數(shù)據(jù)的封鎖；l收縮階段（shrinking phase)：在釋放一個封鎖后，事務(wù)不再申請和獲得其它的任何封鎖。 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l兩段鎖協(xié)議是保證沖突可串行化的充分條件，但該協(xié)議不保證不發(fā)生死鎖。 例：例7-8調(diào)度9中的（b）:滿足兩段鎖協(xié)議的，該調(diào)度是一個沖突可串行化的調(diào)度;例7-8調(diào)度9中的（c）:也滿足遵守兩段鎖協(xié)議的，但該調(diào)度發(fā)生了死鎖。例7-8調(diào)度9中的（a）:并沒有遵守兩段鎖協(xié)議，但該調(diào)度是沖突可串行化的。 7.4 基于鎖的并發(fā)控制協(xié)議 D

25、ataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 圖中每個事務(wù)都遵從兩段鎖協(xié)議，若T1事務(wù)在WRITE（B）時刻發(fā)生故障，將導(dǎo)致事務(wù)T2、T3級聯(lián)回滾。 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l為避免級聯(lián)回滾，可使用嚴(yán)格兩段鎖協(xié)議（strict two-phase locking protocol） l嚴(yán)格兩段鎖協(xié)議：除要求滿足兩段鎖協(xié)議規(guī)定外，還要求事務(wù)的排它鎖必須在事務(wù)提交之后釋放 避免了臟讀和丟失修改的問題。l強(qiáng)兩段鎖協(xié)議（rigorous two-phase lock

26、ing protocol)：兩段鎖協(xié)議的另一個變化，除要求滿足兩段鎖協(xié)議規(guī)定外，還要求事務(wù)的所有鎖都必須在事務(wù)提交之后釋放。進(jìn)一步解決數(shù)據(jù)項(xiàng)不能重復(fù)讀的問題 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l從兩段鎖協(xié)議到嚴(yán)格兩段鎖協(xié)議，再到強(qiáng)兩段鎖協(xié)議，事務(wù)持鎖的時間不斷增長。這不但保證事務(wù)的并發(fā)調(diào)度是沖突可串行化的，還不斷增強(qiáng)了數(shù)據(jù)庫的一致性保證。但帶來的另一方面的問題是并發(fā)度的降低，以及死鎖出現(xiàn)可能性的增加 l目前，大多數(shù)的DBMS都采用嚴(yán)格兩段鎖協(xié)議或強(qiáng)兩段鎖協(xié)議 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUE

27、STC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.4.3 7.4.3 鎖的升級及更新鎖鎖的升級及更新鎖 【例7-9】 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l鎖的升級有可能使得出現(xiàn)死鎖的概率加大 l更新鎖只允許事務(wù)讀取數(shù)據(jù)項(xiàng)而不能修改數(shù)據(jù)項(xiàng)l系統(tǒng)允許更新鎖升級，而不允許共享鎖升級 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 鎖的相容矩陣鎖的相容矩陣 7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技

28、大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 有了更新鎖后，【例7-9】調(diào)度10只須將T1事務(wù)中的SLOCK（A）、SLOCK（B）變?yōu)閁LOCK（A）、ULOCK（B）,兩個事務(wù)仍然可以如調(diào)度10一樣并發(fā)執(zhí)行。而上訴提到的死鎖現(xiàn)象根本不可能再出現(xiàn) 。7.4 基于鎖的并發(fā)控制協(xié)議 DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.5.1 7.5.1 活鎖活鎖 解決活鎖的方法：采用先來先服務(wù)的策略 7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.5.2 7.5.2 死鎖的形成死鎖的

29、形成 針對死鎖，DBMS可以有兩種處理方式：一種是進(jìn)行死鎖的預(yù)防，不讓并發(fā)執(zhí)行的事務(wù)出現(xiàn)死鎖的狀況；一種是允許死鎖的發(fā)生，在死鎖出現(xiàn)后采取措施解決，為此系統(tǒng)中需增加死鎖的檢測及死鎖的解除算法 7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.5.3 7.5.3 死鎖的預(yù)防死鎖的預(yù)防 l順序封鎖法 將數(shù)據(jù)庫對象按某種規(guī)定的順序排列，要求事務(wù)實(shí)行封鎖也必須按照這個順序進(jìn)行。 缺點(diǎn)：不好確定數(shù)據(jù)庫對象的封鎖順序。維護(hù)封鎖順序是件困難的事情且成本很高7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué)

30、 數(shù)據(jù)庫數(shù)據(jù)庫 l一次封鎖法 要求事務(wù)在開始執(zhí)行前先申請到所需的所有封鎖，如果有一個封鎖沒有申請到，則事務(wù)中止。 缺點(diǎn)：在事務(wù)開始前很難預(yù)先知道哪些數(shù)據(jù)項(xiàng)需要封鎖；一次將所有需要的封鎖申請到，可能有些封鎖只在事務(wù)運(yùn)行的后期才需要，這就大大降低了系統(tǒng)的并發(fā)度。7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l用時間戳的死鎖預(yù)防根據(jù)事務(wù)啟動時的時間戳設(shè)置事務(wù)的優(yōu)先級，越早開始運(yùn)行的事務(wù)優(yōu)先級越高。為預(yù)防死鎖，在事務(wù)Ti申請的封鎖與事務(wù)Tj已經(jīng)擁有的封鎖發(fā)生沖突時，鎖管理器可使用如下兩種不同的機(jī)制：Wait-die機(jī)制：若Ti優(yōu)先級較高，則

31、Ti可以等待；否則中止事務(wù)Ti。Wound-wait機(jī)制：若Ti優(yōu)先級較高，則中止Tj；否則Ti等待。 7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 例：假設(shè)事務(wù)T1、T2、T3的時間戳分別為5，10，20。在Wait-die機(jī)制下，若T1申請的封鎖被T2擁有，則T1等待；若T3申請的封鎖被T2擁有，則T3中止運(yùn)行做回滾操作。在Wound-wait機(jī)制下，若T1申請的封鎖被T2擁有，則中止事務(wù)T2的運(yùn)行；若T3申請的封鎖被T2擁有，則T3等待。 7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)

32、科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l若一個事務(wù)被中止回滾，當(dāng)該事務(wù)再重新啟動時應(yīng)保持原有的時間戳 。lWait-die機(jī)制不是一種搶占機(jī)制，越老的事務(wù)可能等待的時間越長，而年青的事務(wù)與年老事務(wù)發(fā)生沖突被中止，重新啟動后仍可能與年老事務(wù)再次發(fā)生封鎖沖突，于是可能出現(xiàn)年青的事務(wù)反復(fù)被中止的情況。l在Wound-wait機(jī)制中不會出現(xiàn)反復(fù)中止的情況。7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.5.4 7.5.4 死鎖的檢測及處理死鎖的檢測及處理 l死鎖的檢測方法包括超時法和等待圖法超時法規(guī)定申請鎖的事務(wù)等待的最長時間。若超過了規(guī)定時間，則系統(tǒng)判定

33、出現(xiàn)死鎖，此時該事務(wù)本身回滾并重啟。實(shí)現(xiàn)簡單可能出現(xiàn)誤判等待多長時間合適難以把握 7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 l等待圖法檢測：當(dāng)且僅當(dāng)?shù)却龍D中出現(xiàn)環(huán)路時，表示系統(tǒng)中存在死鎖。7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 死鎖的解除選擇一個或多個事務(wù)撤銷，釋放這個或這些事務(wù)擁有的封鎖。7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 解除死鎖的過程中要解決的問題主要包括：撤銷事務(wù)的選擇。為解除死鎖必

34、須回滾處于死鎖狀態(tài)的部分事務(wù)。撤銷事務(wù)的選擇原則是事務(wù)撤銷所需的系統(tǒng)代價最小。系統(tǒng)花費(fèi)代價的計(jì)算與很多因素相關(guān)，比如事務(wù)已經(jīng)運(yùn)行了多久，還需多長時間才能結(jié)束；事務(wù)已經(jīng)使用了哪些數(shù)據(jù)項(xiàng)，還將使用多少數(shù)據(jù)項(xiàng)；回滾該事務(wù)會牽涉多少其它的事務(wù)等。事務(wù)撤銷的程度。事務(wù)撤銷是全部回滾還是只需部分回滾。最簡單的是全部回滾選中事務(wù)，然后重新開始。部分回滾的實(shí)現(xiàn)需要系統(tǒng)維護(hù)更多的事務(wù)運(yùn)行狀態(tài)信息。7.5 活鎖與死鎖DataBaseUESTC 電子科技大學(xué)電子科技大學(xué) 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué) 數(shù)據(jù)庫數(shù)據(jù)庫 7.6 多粒度封鎖 l封鎖對象的大小稱為封鎖粒度（granularity) 它可以是數(shù)據(jù)庫的邏輯單位，如：屬性、元組、關(guān)系、索引、整個數(shù)據(jù)庫等；也可以是數(shù)據(jù)庫的物理單位，如頁、塊等 封鎖粒度與系統(tǒng)的并發(fā)度及資源的消耗是息息相關(guān)的。若封鎖粒度小，則系統(tǒng)的并發(fā)度高，需要更多的系統(tǒng)資源；若封鎖粒度大，則系統(tǒng)的并發(fā)度低，資源消耗小 不同的事務(wù)在運(yùn)行過程中可