清華大學數(shù)據(jù)庫access課件 第11章：并發(fā)控制

1、2021-12-281第第1111章并發(fā)控制章并發(fā)控制事務最基本的特性之一就是隔離性。當DBMS中有多個事務并發(fā)執(zhí)行時，事務的隔離性就不一定能保持。DBMS必須對并發(fā)事務之間的相互作用加以控制，這種控制是通過來實現(xiàn)的。所謂的并發(fā)控制機制本質上就是并發(fā)控制協(xié)議，這些協(xié)議是一組規(guī)則，用來決定沖突的事務是回滾重啟還是等待執(zhí)行。本章要討論的所有協(xié)議都本章要討論的所有協(xié)議都能保證調度是可串行化的能保證調度是可串行化的！封鎖協(xié)議封鎖協(xié)議有效性檢查協(xié)議有效性檢查協(xié)議死鎖處理死鎖處理樹形協(xié)議樹形協(xié)議多粒度機制多粒度機制插入與刪除插入與刪除時間戳排序協(xié)議時間戳排序協(xié)議多版本機制多版本機制本章總結本章總結2021

2、-12-28211.111.1封鎖協(xié)議封鎖協(xié)議加鎖的理由保證調度可串行化的方法之一是對數(shù)據(jù)項的訪問以互斥的方式進行： 當一個事務訪問某個數(shù)據(jù)項時，其他任何事務都不能修改該數(shù)據(jù)項。實現(xiàn)這個要求的最常用的方法就是： 只有當一個事務目前在一個數(shù)據(jù)項上持有某種鎖時，DBMS才允許該事務訪問這個數(shù)據(jù)項； 否則，就2021-12-28311.111.1封鎖協(xié)議封鎖協(xié)議給數(shù)據(jù)項加鎖的類型 共享鎖： 如果事務T獲得了數(shù)據(jù)項Q上的共享鎖(記為S)，則T可讀Q但不能寫Q。 排他鎖： 如果事務T獲得了數(shù)據(jù)項Q上的排他鎖(記為X)，則T既可讀Q又可寫Q。根據(jù)操作要求事務給數(shù)據(jù)項申請適當?shù)逆i 該請求是發(fā)送給DBMS的并

3、發(fā)控制管理器的； 只有在并發(fā)控制管理器授予事務所需要的鎖之后，事務才能繼續(xù)其操作。2021-12-28411.111.1封鎖協(xié)議封鎖協(xié)議一個數(shù)據(jù)項上到底能加有多少個鎖？鎖和鎖之間的關系是什么？ 令A與B代表任意類型的鎖，已知如下條件： 事務Ti正請求對數(shù)據(jù)項Q加A類型鎖； 而另一個事務Tj當前在數(shù)據(jù)項Q上持有B類型鎖。 結論： 盡管數(shù)據(jù)項Q上已加有B類型鎖，但如果事務Ti可以立即獲得數(shù)據(jù)項Q上的A類型鎖，則稱A類型鎖與B類型鎖相容。鎖相容矩陣 只有其值為TRUE的兩類鎖才相容。2021-12-28511.111.1封鎖協(xié)議封鎖協(xié)議基本的封鎖協(xié)議 加鎖： 要訪問一個數(shù)據(jù)項，事務T必須首先申請給該

4、數(shù)據(jù)項加鎖：如果該數(shù)據(jù)項已經(jīng)被另一事務加上了不相容類型的鎖，則在所有不相容類型的鎖被釋放之前，并發(fā)控制管理器不會授予事務T申請的鎖；因此T必須等待，直到所有不相容類型的鎖被釋放。 解鎖： 只要事務T還在訪問某數(shù)據(jù)項，它就必須擁有該數(shù)據(jù)項上的鎖； 除此之外，事務T可以隨時釋放隨時釋放先前它加在某個數(shù)據(jù)項上的鎖。2021-12-28611.111.1封鎖協(xié)議封鎖協(xié)議加鎖與解鎖的表達假設Q代表數(shù)據(jù)項加鎖指令： lock-S(Q)：申請Q上的共享鎖； lock-X(Q)：申請Q上的排他鎖。解鎖指令： unlock(Q)：釋放Q上的所有鎖。2021-12-28711.111.1封鎖協(xié)議封鎖協(xié)議帶鎖的調度

5、 事務T1申請鎖 并發(fā)控制管理器檢查是否可以授予鎖？ 如果可以，grant-X(A,T1)指令將授予鎖 如果不可以，則事務T1就必須等待！2021-12-28811.111.1封鎖協(xié)議封鎖協(xié)議基本封鎖協(xié)議的問題 從前面的例子可以看出，即使在調度中采用了基本的封鎖協(xié)議，也還有可能導致數(shù)據(jù)庫不一致。因此基本的封鎖協(xié)議也有缺陷： 解鎖問題： 在事務中過早地釋放數(shù)據(jù)項上的鎖，有可能導致數(shù)據(jù)庫的不一致。 死鎖問題： 所有的事務因為持有鎖和申請鎖而導致大家都處于等待狀態(tài)，無法繼續(xù)執(zhí)行； 餓死問題： 一個事務總是不能在某個數(shù)據(jù)項上加上鎖，因此該事務也就永遠不能取得進展。2021-12-28911.111.1

6、封鎖協(xié)議封鎖協(xié)議解鎖與死鎖問題 如果對數(shù)據(jù)項進行讀寫之后立即解鎖，容易造成數(shù)據(jù)庫的不一致，那么是否把解鎖的時機往后推到事務的末尾就萬事大吉了呢？ 解鎖的時機不僅影響事務的并發(fā)度，同時還有可能造成調度的死鎖！ 死鎖比造成數(shù)據(jù)庫不一致要好，因為死鎖可以通過DBMS回滾某事務加以解決；而2021-12-281011.111.1封鎖協(xié)議封鎖協(xié)議餓死問題 鎖的授予：事務申請對某數(shù)據(jù)項加某種類型的鎖；沒有其他事務在該數(shù)據(jù)項上持有與該事務所申請的鎖不相容的鎖；此時，并發(fā)控制管理器才可以授予鎖。當事務Ti申請對數(shù)據(jù)項Q加M型鎖時，授權加鎖的條件是：不存在其他事務在數(shù)據(jù)項Q上持有與M型鎖沖突的鎖；不存在其他事務

7、等待對數(shù)據(jù)項Q加鎖且先于Ti申請加鎖。2021-12-2811兩階段封鎖協(xié)議 為了解決事務的解鎖問題，該協(xié)議要求每個事務分兩個階段提出加鎖和解鎖申請： 增長階段：事務可以獲得鎖，但不能釋放鎖。 縮減階段：事務可以釋放鎖，但不能獲得鎖。 對于一個事務而言：11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-281211.111.1封鎖協(xié)議封鎖協(xié)議兩階段封鎖協(xié)議 餓死問題： DBMS中并發(fā)控制管理器授權加鎖的兩個條件。 解鎖問題： 兩階段封鎖協(xié)議指出了事務釋放鎖的時機，使得解鎖指令不必非得出現(xiàn)在事務的末尾，增加了事務之間的并發(fā)度。 死鎖問題： 在調度中可能還會有死鎖發(fā)生，真正的原因是什么呢？2021-

8、12-2813封鎖點 對任何一個事務而言，在調度中獲得其最后一個鎖的時刻，稱為該事務的封鎖點。思考題 調度中多個事務可根據(jù)它們的封鎖點進行排序，該順序就是事務的一個可串行化次序？11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-2814加強的兩階段封鎖協(xié)議 問題的提出： 在兩階段封鎖協(xié)議下，還有一個問題就是在發(fā)生故障的情況下調度中事務的級聯(lián)回滾可能發(fā)生。 舉例： 如右圖所示11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-2815加強的兩階段封鎖協(xié)議 嚴格兩階段封鎖協(xié)議： 除了要求封鎖是兩階段之外，還要求事務持有的所有排他鎖必須在事務提交之后方可釋放； 這個要求保證未提交事務所寫的任何數(shù)據(jù)在該事務

9、提交之前均以排他方式加鎖，防止其他事務讀取這些數(shù)據(jù)。 強兩階段封鎖協(xié)議： 該協(xié)議要求事務提交之前不得釋放任何鎖，它旨在讓沖突的事務盡可能地串行執(zhí)行； 這樣調度中的事務可以按其提交的順序串行化； 事務提交的順序與前面講的封鎖點順序一致嗎？11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-2816鎖的轉換 問題的提出： 如果事務一開始就申請排他鎖并獲得該鎖，那么其他事務只能在該事務提交之后才有可能獲得鎖而繼續(xù)執(zhí)行； 也就是說，加強的兩階段封鎖協(xié)議雖然保證了調度不會發(fā)生級聯(lián)回滾，但卻降低了事務之間的并發(fā)度。 舉例： 事務T12必須對數(shù)據(jù)項a1加排他鎖，結果導致11.111.1封鎖協(xié)議封鎖協(xié)議2021-

10、12-2817鎖的轉換 問題的解決： 事實上，只是在T12寫a1的時候才需要對a1加排他鎖； 因此，一開始T12只要對a1加共享鎖就可以，只是在需要時再將其變?yōu)榕潘i，這樣T12和T13就可以真正地實現(xiàn)并發(fā)執(zhí)行。 鎖的升降級： upgrade表示將共享鎖升級為排他鎖，只能發(fā)生在 downgrade表示將排他鎖降級為共享鎖，只能發(fā)生在11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-2818商用DBMS中封鎖協(xié)議的實現(xiàn) 在實際的商用DBMS中，根據(jù)加強的封鎖協(xié)議實現(xiàn)的并發(fā)控制機制很簡單且被廣泛采用； 這樣的機制能保證并發(fā)控制管理器自動為事務產(chǎn)生加鎖、解鎖指令： 當事務T進行read(Q)操作時，系

11、統(tǒng)產(chǎn)生lock-S(Q)指令，后接read(Q)指令； 當事務T進行write(Q)操作時，系統(tǒng)檢查T是否已在Q上持有共享鎖：若有，則系統(tǒng)發(fā)出upgrade(Q)指令，后接write(Q)指令；否則系統(tǒng)發(fā)出lock-X(Q)指令，后接write(Q)指令； 事務提交或回滾后，該事務持有的鎖都被釋放。11.111.1封鎖協(xié)議封鎖協(xié)議2021-12-2819事務沖突 封鎖協(xié)議要求事務在操作數(shù)據(jù)前，必須向并發(fā)控制管理器申請鎖： 如果事務沒有立刻申請到相關的鎖，就說明系統(tǒng)中有沖突的事務，它必須等待。 系統(tǒng)中并發(fā)的事務之間存在哪些沖突？這些沖突會造成哪些問題(數(shù)據(jù)庫不一致)？ 寫讀沖突：讀未提交的數(shù)據(jù)，

12、即臟讀； 讀寫沖突：不可重復讀； 寫寫沖突：重寫未提交的數(shù)據(jù)，即丟失修改； 幻影：相同的條件，前后兩次查詢的結果不同。11.211.2并發(fā)調度中的事務沖突并發(fā)調度中的事務沖突2021-12-2820寫讀沖突 讀未提交的數(shù)據(jù)，即臟讀： 事務Tj讀取了已經(jīng)被另一個事務Ti修改，但最終卻沒有提交的數(shù)據(jù)項Q。11.211.2并發(fā)調度中的事務沖突并發(fā)調度中的事務沖突2021-12-2821讀寫沖突 不可重復的讀： 當事務Tj讀數(shù)據(jù)對象Q并仍在運行時，事務Ti修改了Q的值。如果Tj再次讀Q的值11.211.2并發(fā)調度中的事務沖突并發(fā)調度中的事務沖突2021-12-2822寫寫沖突 重寫未提交的數(shù)據(jù)，即丟失

13、修改： 事務Ti和Tj讀入同一數(shù)據(jù)并進行修改，Tj重復寫入Q值，并且Ti先于Tj提交。這樣Tj提交的結果就破壞了Ti提交的結果，導致Ti的修改丟失。11.211.2并發(fā)調度中的事務沖突并發(fā)調度中的事務沖突2021-12-2823幻影事務Tj按一定條件讀取了某些數(shù)據(jù)后，事務Ti又插入(刪除)了一些滿足條件的數(shù)據(jù)。當Tj再次按相同的條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多(少)了一些記錄。11.211.2并發(fā)調度中的事務沖突并發(fā)調度中的事務沖突僅保證它所訪問的數(shù)據(jù)不被其他事務修改是不夠的沒有阻止其他事務插入新的滿足條件的數(shù)據(jù)2021-12-2824調度中沖突事務的解決方案： 封鎖協(xié)議： 等待執(zhí)行； 沖突可串行化順序

14、：事務封鎖點的順序；按事務提交的順序；每一對沖突事務的可串行化次序是由執(zhí)行時第一個兩者都申請但互相沖突的鎖決定的。 時間戳排序協(xié)議： 回滾重啟； 沖突可串行化順序：事先選定好了事務的串行順序，即事務進入DBMS的先后順序。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議三個順序的一致性？2021-12-2825時間戳 基本概念： 對于系統(tǒng)中的每個事務T，把一個唯一固定的時間標志和事務T聯(lián)系起來，這個時間標志就是事務的時間戳 時間戳是在事務T開始執(zhí)行前由DBMS的并發(fā)控制管理器賦予事務的，記為TS(T)。 時間戳的大小(先后)之分： 如果事務Ti先于事務Tj進入系統(tǒng)，那么： TS(Ti) TS(Tj

15、) 實現(xiàn)方式： 使用系統(tǒng)時鐘或邏輯計數(shù)器11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2826時間戳的特征 事務的時間戳決定了調度中事務的可串行化順序： 若TS(Ti)TS(Tj)，則DBMS保證所產(chǎn)生的調度等價于Ti出現(xiàn)在Tj之前的某個串行調度。 每個數(shù)據(jù)項Q需要和以下兩個重要的時間戳相關聯(lián)： W-TS(Q)：當前已成功執(zhí)行write(Q)的所有事務的最大時間戳 R-TS(Q)：當前已成功執(zhí)行read(Q)的所有事務的最大時間戳 隨著讀寫指令的成功執(zhí)行，它們隨時被更新。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2827協(xié)議內容 時間戳排序協(xié)議保證并發(fā)調度中任何

16、有沖突的read和write操作按時間戳順序執(zhí)行。 假設事務Ti發(fā)出read(Q)操作： 若TS(Ti)W-TS(Q)，則Ti需要讀入的Q值已被覆蓋。因此，read操作被拒絕，Ti回滾；(寫讀沖突) 若TS(Ti)W-TS(Q)，則執(zhí)行read操作，而R-TS(Q)的值被設為R-TS(Q)與TS(Ti)中的較大者。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2828協(xié)議內容 時間戳排序協(xié)議保證并發(fā)調度中任何有沖突的read和write操作按時間戳順序執(zhí)行。 假設事務Ti發(fā)出write(Q)操作： 若TS(Ti)R-TS(Q)，則Ti產(chǎn)生的Q值是先前所需要的值，但系統(tǒng)已假定該值不

17、會被產(chǎn)生。因此，write操作被拒絕，Ti回滾；(讀寫沖突)11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2829協(xié)議內容 假設事務Ti發(fā)出write(Q)操作： 若TS(Ti)W-TS(Q)，則Ti想寫入的Q值已經(jīng)丟失。因此，write操作被拒絕，Ti回滾；(寫寫沖突) 其他情況下執(zhí)行write(Q)操作，并將W-TS(Q)的值設為TS(Ti)。 事務Ti被并發(fā)控制機制回滾之后，被賦予新的時新的時間戳間戳并重新啟動，進入系統(tǒng)。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2830調度舉例 在時間戳排序協(xié)議下： 假設事務在第一條指令執(zhí)行前的那一刻被賦予時間戳； 對事

18、務要訪問的任何數(shù)據(jù)項來說，假設它們的W-TS和R-TS的初始值都為0(最小)。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2831Thomas(托馬斯)寫規(guī)則 對時間戳排序協(xié)議中事務間“寫/寫”沖突規(guī)則的重大修改； 首先從一個例子開始： 如圖所示，TS(T3)TS(T4)，假設T3的read(Q)和T4的write(Q)都成功執(zhí)行，則W-TS(Q)=TS(T4)； 當T3試圖執(zhí)行write(Q)時，由于TS(T3)W-TS(Q)，即TS(T4)，該操作被拒絕且事務T3回滾。 雖然按照時間戳排序協(xié) 議的要求T3應該回滾， 但實際上沒有必要。T3 的write(Q)操作可以 忽略，

19、為什么？11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2832Thomas(托馬斯)寫規(guī)則 T4已寫T3要寫的Q永遠不會被任何事務讀到： 滿足TS(Ti)W-TS(Q)=TS(T4)的任何事務Ti試圖進行read(Q)操作時均被回滾； 滿足TS(Tj)W-TS(Q)=TS(T4)的任何事務Tj必須讀入由T4而不是T3寫入的Q值。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議結論：T3的write(Q)已經(jīng)過時，可以忽略！即使執(zhí)行T3的write(Q)，W-TS(Q)的值仍然是TS(T4)！2021-12-2833Thomas(托馬斯)寫規(guī)則 當事務Ti發(fā)出write(Q)操作時：

20、若TS(Ti)R-TS(Q)，規(guī)則同前面：Ti回滾； 若TS(Ti)W-TS(Q)，則Ti試圖要寫入的Q值已經(jīng)過時。因此該write(Q)操作可被忽略； 其他情況下執(zhí)行write(Q)操作，并將W-TS(Q)的值設為TS(Ti)。11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2834小結 時間戳排序協(xié)議保證： 滿足該協(xié)議的任何調度沖突可串行化，為什么？ 滿足該協(xié)議的任何調度無死鎖，為什么？ 但該協(xié)議不保證： 所產(chǎn)生的調度都是可恢復的：11.311.3時間戳排序協(xié)議時間戳排序協(xié)議2021-12-2835并發(fā)事務的隔離等級 事務的隔離等級控制事務可暴露給其他并發(fā)執(zhí)行事務的程度； 通過

21、選擇隔離等級，事務以把未提交的數(shù)據(jù)更新暴露給其他事務為代價，獲得更高程度的并發(fā)度； 一般商用DBMS的隔離等級分為以下四種： 讀未提交(Read Uncommitted) 讀已提交(Read Committed) 可重復讀(Repeatable Read) 可串行化(Serializable)11.411.4事務的隔離等級事務的隔離等級2021-12-2836讀未提交： 允許事務可以讀取未提交的數(shù)據(jù)； 設置事務的隔離等級為“讀未提交”，使得事務不必等待任何鎖，也不必對所讀的數(shù)據(jù)加共享鎖； 讀未提交雖然提高了事務之間的并發(fā)度，但是以犧牲數(shù)據(jù)庫的一致性為代價： 讀臟數(shù)據(jù) 不能重復讀 幻影 set

22、trans isolation READ UNCOMMITTED11.411.4事務的隔離等級事務的隔離等級2021-12-2837讀已提交 只允許事務讀取已提交的數(shù)據(jù)，但不要求可重復讀； 這是一般商用DBMS的缺省隔離等級，保證事務不會讀取其他未提交事務所修改的數(shù)據(jù)； 讀已提交要求在所訪問的數(shù)據(jù)上至少加共享鎖，共享鎖不會防止其他事務讀取數(shù)據(jù)，但會防止其他事務修改數(shù)據(jù)。這里的共享鎖不必保持到事務結束； 讀已提交可能造成的數(shù)據(jù)庫不一致性現(xiàn)象： 不能重復讀和幻影11.411.4事務的隔離等級事務的隔離等級2021-12-2838可重復讀 只允許事務讀取已提交的數(shù)據(jù)，并要求一個事務在對同一數(shù)據(jù)的兩次

23、讀取之間，其他事務不能對這些數(shù)據(jù)進行更新； 為保證可重復讀，事務必須保持它的共享鎖到事務結束(注意：排他鎖總是保持到事務結束)。這樣，其他事物就不能修改可重復讀事務正在訪問的數(shù)據(jù)； 可重復讀會極大地降低事務之間的并發(fā)度，同時也會造成數(shù)據(jù)庫的不一致性現(xiàn)象： 幻影11.411.4事務的隔離等級事務的隔離等級2021-12-2839可串行化 并發(fā)調度的執(zhí)行結果等價于一個串行調度； 在可重復讀的基礎上，進一步要求一個事務的兩次相同的查詢之間，其他事務不能插入滿足查詢條件的數(shù)據(jù)，避免發(fā)生幻影現(xiàn)象； 同可重復讀一樣，事務必須保持它的共享鎖到事務結束。同時，事務不但要封鎖現(xiàn)有的數(shù)據(jù)，還要封鎖不存在的數(shù)據(jù)；

24、加強的兩階段封鎖協(xié)議和時間戳排序協(xié)議都能保證它們所產(chǎn)生的并發(fā)調度是沖突可串行化的。11.411.4事務的隔離等級事務的隔離等級2021-12-2840死鎖的定義 如果存在一個事務集，該集合中的每個事務都在等待集合中的另外一個事務，我們就說系統(tǒng)處于死鎖狀態(tài)。例如： 在集合T0,T1,Tn中，若T0在等待被T1鎖住的數(shù)據(jù)項；T1在等待被T2鎖住的數(shù)據(jù)項；Tn-1在等待被Tn鎖住的數(shù)據(jù)項；而Tn在等待被T0鎖住的數(shù)據(jù)項，則系統(tǒng)死鎖。11.511.5死鎖處理死鎖處理2021-12-2841死鎖的解決 解決死鎖問題主要有以下兩種策略： 死鎖預防：預先防止死鎖發(fā)生，保證系統(tǒng)永不進入死鎖狀態(tài)。 死鎖檢測與恢

25、復：允許系統(tǒng)進入死鎖狀態(tài)，但要周期性地檢測系統(tǒng)有無死鎖。如果有，則把系統(tǒng)從死鎖中恢復過來。 兩種策略都會引起事務回滾： 如果系統(tǒng)進入死鎖狀態(tài)的概率相對較高，則通常采用死鎖預防策略； 否則死鎖檢測與恢復策略會更有效。 基于鎖超時的機制： 申請鎖的事務至多等待給定的時間。若11.511.5死鎖處理死鎖處理2021-12-2842死鎖預防 預防死鎖的最有效的方法就是采用資源搶占與事務回滾技術： 在這種方法里，首先賦予每個事務一個唯一的時間戳，系統(tǒng)利用時間戳來決定事務應當是等待，還是回滾重啟； 但調度的并發(fā)控制仍然使用封鎖機制； 若一個事務回滾，則該事務重啟時保持原有的時間戳。 利用時間戳的兩種死鎖預

26、防機制如下： 等待-死亡(wait-die)機制 受傷-等待(wound-wait)機制11.511.5死鎖處理死鎖處理2021-12-2843等待-死亡機制 這種機制基于非搶占技術； 當事務Ti申請的數(shù)據(jù)項當前被Tj持有，僅當TS(Ti)TS(Tj)時，允許Ti等待。否則，Ti搶占Tj持有的數(shù)據(jù)項，而Tj回滾。例如： 若事務Ti、Tj、Tk的時間戳分別為5、10、15：如果Ti申請的數(shù)據(jù)項當前被Tj持有，則Ti將從Tj搶占數(shù)據(jù)項，Tj回滾；如果Tk申請的數(shù)據(jù)項當前被Tj持有，則Tk將等待。11.511.5死鎖處理死鎖處理2021-12-2845等待-死亡與受傷-等待的區(qū)別 等待區(qū)別： 在等待

27、-死亡機制中，較老的事務必須等待 在受傷-等待機制中，較老的事務從不等待 回滾區(qū)別： 在等待-死亡機制中：同一事務可能回滾多次！ 在受傷-等待機制中：相關事務只需回滾一次？11.511.5死鎖處理死鎖處理2021-12-2846死鎖檢測與恢復 死鎖檢測與恢復機制的工作方式如下： 檢查系統(tǒng)狀態(tài)的算法周期性地被激活(實際上它應當是系統(tǒng)中的一個進程或線程)，判斷系統(tǒng)中有無死鎖； 如果發(fā)生死鎖，則系統(tǒng)要進行恢復。 這種機制的基本要求如下： 維護當前已分配給事務的數(shù)據(jù)項的有關信息以及任何尚未解決的數(shù)據(jù)項請求信息； 提供一個使用這些信息判斷系統(tǒng)是否進入死鎖狀態(tài)的算法； 提供解除死鎖的策略。11.511.5

28、死鎖處理死鎖處理2021-12-2847死鎖檢測與恢復 死鎖檢測： 死鎖用稱為等待圖的有向圖來描述； 該圖由兩部分G=(V, E)組成，其中V是頂點集，E是邊集：頂點集由調度中的所有事務組成；如果事務Ti在等待Tj釋放所需數(shù)據(jù)項，則存在從Ti到Tj的一條有向邊TiTj。 死鎖檢測算法就是要檢查等待圖中是否存在有向環(huán)，圖論中有相應的深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法來完成此任務：這和前面介紹過的判斷調度沖突可串行化的優(yōu)先圖類似。11.511.5死鎖處理死鎖處理2021-12-2848死鎖檢測與恢復死鎖恢復： 常用方法是回滾一個或多個事務； 在選擇要回滾的事務時要考慮以下情況：選擇使回滾代價最小的

29、事務作為犧牲者；決定回滾多遠：徹底回滾，即中止該事務爾后重啟；部分回滾，只回滾到可以解除死鎖為止。避免餓死：避免同一事務總是作為回滾代價最小的事務而被選中；常用的方法就是在代價因素中包含回滾次數(shù)11.511.5死鎖處理死鎖處理該事務已計算了多久？已使用了多少數(shù)據(jù)項？完成還需多少數(shù)據(jù)項？回滾將牽涉多少其他事務？2021-12-2849概述 前面講的read和write操作只能處理數(shù)據(jù)庫中已經(jīng)存在的數(shù)據(jù)； 實際上，事務不僅要訪問數(shù)據(jù)庫中已經(jīng)存在的數(shù)據(jù)項，而且還要創(chuàng)建新的數(shù)據(jù)項、刪除舊的數(shù)據(jù)項： delete(Q)：從數(shù)據(jù)庫中刪除數(shù)據(jù)項Q； insert(Q)：插入一個新的數(shù)據(jù)項Q到數(shù)據(jù)庫并賦予Q一

30、個初值。 事務T在Q被刪除后執(zhí)行read(Q)或在Q被插入前執(zhí)行read(Q)都將產(chǎn)生邏輯錯誤！11.611.6插入與刪除插入與刪除2021-12-2850刪除 首先要弄清楚調度中刪除操作和哪些數(shù)據(jù)操作沖突？ 假設調度S中兩個連續(xù)的操作Im和In分別屬于事務Ti和Tj，其中Im=delete(Q)： 若In=read(Q)：ImIn，則沖突； 若In=write(Q)：ImIn，則沖突； 若In=delete(Q)：則沖突； 若In=insert(Q)：則沖突。分兩種情況：ImIn，在Im與In之前，Q已經(jīng)存在。11.611.6插入與刪除插入與刪除2021-12-2851刪除并發(fā)控制機制中刪除操作的處理： 如果使用兩階段封鎖協(xié)議，則在一數(shù)據(jù)項被刪除之前，