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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、個(gè)初值。 事務(wù)T在Q被刪除后執(zhí)行read(Q)或在Q被插入前執(zhí)行read(Q)都將產(chǎn)生邏輯錯(cuò)誤！11.611.6插入與刪除插入與刪除2021-12-2850刪除 首先要弄清楚調(diào)度中刪除操作和哪些數(shù)據(jù)操作沖突？ 假設(shè)調(diào)度S中兩個(gè)連續(xù)的操作Im和In分別屬于事務(wù)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ā)控制機(jī)制中刪除操作的處理： 如果使用兩階段封鎖協(xié)議，則在一數(shù)據(jù)項(xiàng)被刪除之前，