數(shù)據(jù)庫原理第7章 V2.1

《數(shù)據(jù)庫原理及應(yīng)用》第7章并發(fā)控制電子科技大學(xué)計(jì)算機(jī)學(xué)院鄭莉華cd_zhenglh@163.com12一月2024ClicktoaddTitle1事務(wù)并發(fā)1ClicktoaddTitle2并發(fā)事務(wù)引起的問題2ClicktoaddTitle2可串行化3ClicktoaddTitle1基于鎖的并發(fā)控制協(xié)議4ClicktoaddTitle1*活鎖與死鎖5ClicktoaddTitle2*多粒度封鎖3

I/O與CPU等可以并行交叉運(yùn)行并發(fā)執(zhí)行的優(yōu)點(diǎn)改善系統(tǒng)的資源利用率減少短事務(wù)的等待時(shí)間調(diào)度(schedule)一個(gè)或多個(gè)事務(wù)的操作按時(shí)間排序的一個(gè)序列。一個(gè)事務(wù)的兩個(gè)操作在調(diào)度中出現(xiàn)的順序必須與其在事務(wù)內(nèi)定義的先后順序一致。ClicktoaddTitle1事務(wù)并發(fā)1ClicktoaddTitle2并發(fā)事務(wù)引起的問題2ClicktoaddTitle2可串行化3ClicktoaddTitle1基于鎖的并發(fā)控制協(xié)議4ClicktoaddTitle1*活鎖與死鎖5ClicktoaddTitle2*多粒度封鎖3

讀臟數(shù)據(jù)（dirtyread）臟數(shù)據(jù)(dirtydata)是對未提交事務(wù)所寫數(shù)據(jù)的統(tǒng)稱。若臟讀就造成了數(shù)據(jù)庫的不一致狀態(tài)，應(yīng)嚴(yán)格禁止。若臟讀帶來的影響足夠小，偶爾可讀一次臟數(shù)據(jù)，它可以提高并發(fā)性，減少事務(wù)的等待時(shí)間

不可重復(fù)讀(unrepeatableread)事務(wù)T1的兩次讀取數(shù)據(jù)之間，其它事務(wù)修改了它要讀取的數(shù)據(jù)，以致兩次讀到的值不同在事務(wù)串行執(zhí)行時(shí)，不會(huì)出現(xiàn)此現(xiàn)象

丟失更新(lostupdate)由兩個(gè)事務(wù)對同一數(shù)據(jù)并發(fā)地寫入引起ClicktoaddTitle1事務(wù)并發(fā)1ClicktoaddTitle2并發(fā)事務(wù)引起的問題2ClicktoaddTitle2可串行化3ClicktoaddTitle1基于鎖的并發(fā)控制協(xié)議4ClicktoaddTitle1*活鎖與死鎖5ClicktoaddTitle2*多粒度封鎖3

回顧：事務(wù)ACID特性中的隔離性？事務(wù)在運(yùn)行中不受其它事務(wù)干擾的方法：串行：每個(gè)事務(wù)依次順序執(zhí)行并行但控制：事務(wù)之間并發(fā)執(zhí)行，DBMS調(diào)整事務(wù)的調(diào)度，使其運(yùn)行結(jié)果與一次只執(zhí)行一個(gè)事務(wù)的結(jié)果相同

串行調(diào)度：不同事務(wù)的活動(dòng)在調(diào)度中是一個(gè)接一個(gè)執(zhí)行的，沒有交叉的運(yùn)行。兩個(gè)串行調(diào)度的結(jié)果不同。但只要保持了數(shù)據(jù)庫的一致性，最終的結(jié)果并不重要

可串行化調(diào)度調(diào)度是可串行化的：多個(gè)事務(wù)交叉調(diào)度的結(jié)果與某一個(gè)串行調(diào)度的結(jié)果相同DBMS認(rèn)為事務(wù)串行調(diào)度的結(jié)果保持了數(shù)據(jù)庫的一致性，都是正確的一個(gè)調(diào)度如果是可串行化的，系統(tǒng)認(rèn)為其調(diào)度是一個(gè)正確的調(diào)度，保持了數(shù)據(jù)庫的一致性并行調(diào)度與串行調(diào)度的結(jié)果相同，因此該調(diào)度是可串行的調(diào)度

DBMS需要事務(wù)調(diào)度管理如果將事務(wù)的并發(fā)執(zhí)行完全交給操作系統(tǒng)，則任何一種調(diào)度方式都有可能出現(xiàn)。有的調(diào)度能保持?jǐn)?shù)據(jù)庫的一致，有的調(diào)度卻會(huì)產(chǎn)生錯(cuò)誤的結(jié)果。DBMS必須對事務(wù)的運(yùn)行加以控制，確保交叉調(diào)度完畢后的結(jié)果與某一串行調(diào)度的結(jié)果相同，數(shù)據(jù)庫不會(huì)出現(xiàn)不一致的狀態(tài)。

丟失更新！兩個(gè)調(diào)度的結(jié)果不一致，是一個(gè)不可串行化的調(diào)度。

簡記符號WRITE簡寫為W，READ簡寫為R，WT(X)：事務(wù)T寫數(shù)據(jù)庫元素X，RT(X)：事務(wù)T讀數(shù)據(jù)庫元素X，S表示一個(gè)調(diào)度。調(diào)度(事務(wù)序列)表示：S=R1(A)R2(A)W1(A)W2(A)R2(B)R1(B)W2(B)W1(B)

指令沖突性讀相同數(shù)據(jù)：不沖突若事務(wù)Ti和Tj都是讀取數(shù)據(jù)A，則Ri(A)，Rj(A)指令不發(fā)生沖突。讀寫相同數(shù)據(jù)：沖突若事務(wù)Ti和Tj一個(gè)是讀數(shù)據(jù)，一個(gè)是寫數(shù)據(jù)，則事務(wù)的執(zhí)行順序是重要的。Ri(A)和Wj(A)指令是沖突的。寫相同數(shù)據(jù)：沖突若事務(wù)Ti和Tj都是寫數(shù)據(jù)A，則Wi（A）和Wj（A）指令也是沖突的。讀寫不同數(shù)據(jù)：不沖突示例

S=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）指令是不沖突。調(diào)度中兩個(gè)事務(wù)發(fā)生沖突，必須：對同一數(shù)據(jù)對象進(jìn)行操作兩個(gè)操作指令中有一個(gè)是寫操作W

沖突等價(jià)：若調(diào)度S中屬于不同事務(wù)的兩條操作指令是不沖突的，則可以交換兩條指令的執(zhí)行順序，得到一個(gè)新的調(diào)度S′。稱調(diào)度S與調(diào)度S′沖突等價(jià)的（conflictequivalent）。沖突可串行化：若一個(gè)調(diào)度沖突等價(jià)于一個(gè)串行調(diào)度，則該調(diào)度是沖突可串行化的。示例調(diào)度S=R1(A)W1(A)R2(A)W2(A)R1(B)W1(B)R2(B)W2(B)R1(B)與W2(A)指令不沖突，可以交換執(zhí)行順序；R1(B)與R2(A)指令不沖突，可以交換執(zhí)行順序；W1(B)與W2(A)指令不沖突，可以交換執(zhí)行順序；W1(B)與R2(A)指令不沖突，可以交換執(zhí)行順序。調(diào)度S’=R1(A)W1(A)R1(B)W1(B)R2(A)W2(A)R2(B)W2(B)調(diào)度S’是一個(gè)串行調(diào)度。調(diào)度S等價(jià)于串行調(diào)度S’，是沖突可串行化的。

沖突可串行是可串行性的充分條件調(diào)度運(yùn)行結(jié)果與串行調(diào)度T1→T2→T3的運(yùn)行結(jié)果是一致的，但調(diào)度不是沖突可串行的

視圖等價(jià)對同一事務(wù)集，如果兩個(gè)調(diào)度S1和S2在任何時(shí)候都保證每個(gè)事務(wù)讀取相同的值，寫入數(shù)據(jù)庫的最終狀態(tài)也是一樣的，則稱調(diào)度S1和S2視圖等價(jià)。調(diào)度S1和調(diào)度S2不是視圖等價(jià)的調(diào)度S1中T2事務(wù)讀取的A值是事務(wù)T1修改后的值，調(diào)度S2中T2事務(wù)讀取的A值是事務(wù)T1修改前的值。

示例調(diào)度S和調(diào)度S’是視圖等價(jià)的，因?yàn)閮蓚€(gè)調(diào)度中：事務(wù)T1讀取的都是數(shù)據(jù)庫的初始值事務(wù)T2讀取的數(shù)據(jù)都是事務(wù)T1修改后的值數(shù)據(jù)庫中藥品A、B的最終狀態(tài)都是由事務(wù)T2寫入的。

視圖可串行化如果某個(gè)調(diào)度視圖等價(jià)于一個(gè)串行調(diào)度，則稱這個(gè)調(diào)度是視圖可串行化的如果調(diào)度是沖突可串行化的，則該調(diào)度一定是視圖可串行化的。但反過來未必成立。舉例設(shè)調(diào)度S1=R1(A)W3(A)R2(B)W1(B)經(jīng)過非沖突調(diào)整，S2=R2(B)R1(A)W1(B)W3(A) 調(diào)度S1和調(diào)度S2是沖突等價(jià)的。又因?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是視圖可串行化的。

判定一個(gè)調(diào)度是否是沖突可串行化的，可以使用前驅(qū)圖（precedencegraph）若前驅(qū)圖中存在環(huán)，則表示調(diào)度S是不可串行化的。反之，若前驅(qū)圖中不存在環(huán)，表示調(diào)度S是沖突可串行化的，可用拓?fù)渑判虻玫秸{(diào)度S的一個(gè)等價(jià)的串行調(diào)度。前驅(qū)圖是一個(gè)有向圖G=（V，E）頂點(diǎn)代表調(diào)度S中的事務(wù)由Ti→Tj

的邊表示在調(diào)度S中Ti和Tj之間存在一對沖突指令，并且Ti中的指令先于Tj

中的指令執(zhí)行。

示例1S=R1(A)W1(A)R2(A)W2(A)R1(B)W1(B)R2(B)W2(B)沖突指令W1(A)在R2(A)前，W1(B)在R2(B)前，因此存在從T1到T2的有向邊。示例2 S=R1(A)R2(A)W1(A)W2(A)R2(B)R1(B)W2(B)W1(B)W1(A)在W2(A)之前，R1(B)在W2(B)之前，因此存在T1到T2的有向邊；R2(A)在W1(A)之前，W2(B)在W1(B)之前，因此存在T2到T1的有向邊。

數(shù)據(jù)庫系統(tǒng)要求所有的調(diào)度都是可恢復(fù)的可恢復(fù)條件：調(diào)度S中，事務(wù)Ti如果讀取了事務(wù)Tj修改過的數(shù)據(jù)，則事務(wù)Ti必須等事務(wù)Tj提交后才能提交。

事務(wù)在并行執(zhí)行過程中發(fā)生故障，還可能引起多個(gè)事務(wù)的級聯(lián)回滾?！纠杭壜?lián)讀臟】假定T2事務(wù)讀取A的值并修改；還有T3事務(wù)讀取T2修改后的值，并做了修改；依次類推。。。若事務(wù)T1發(fā)生故障時(shí)，后續(xù)的事務(wù)T2、T3、T4...都已提交，則事務(wù)T1的回滾導(dǎo)致級聯(lián)回滾，產(chǎn)生大量的撤銷工作。無級聯(lián)回滾的調(diào)度應(yīng)滿足：調(diào)度S中的每對事務(wù)Ti和Tj，事務(wù)Ti如果讀取了事務(wù)Tj修改過的數(shù)據(jù)，則事務(wù)Tj必須在Ti讀取前提交即調(diào)度禁止讀取臟數(shù)據(jù)。ClicktoaddTitle1事務(wù)并發(fā)1ClicktoaddTitle2并發(fā)事務(wù)引起的問題2ClicktoaddTitle2可串行化3ClicktoaddTitle1基于鎖的并發(fā)控制協(xié)議4ClicktoaddTitle1*活鎖與死鎖5ClicktoaddTitle2*多粒度封鎖3

封鎖指事務(wù)在對數(shù)據(jù)庫進(jìn)行讀、寫操作之前，必須先得到對操作對象的控制權(quán)力。先要對將執(zhí)行讀、寫操作的數(shù)據(jù)庫對象申請鎖，在獲得該數(shù)據(jù)庫對象的控制權(quán)力后，才能進(jìn)行相應(yīng)地讀、寫操作。封鎖是實(shí)現(xiàn)數(shù)據(jù)庫并發(fā)控制的重要手段。鎖管理器（lockmanager）事務(wù)執(zhí)行過程中鎖的申請和釋放由DBMS中的鎖管理器負(fù)責(zé)鎖管理器維護(hù)一張哈希表——鎖表對每個(gè)數(shù)據(jù)庫對象，如果其上有鎖，那么鎖表指明持有該鎖的事務(wù)。鎖表包含的信息包括：每個(gè)數(shù)據(jù)庫對象上已有的鎖的個(gè)數(shù)、鎖的類型以及一個(gè)指向申請鎖隊(duì)列的指針。

鎖的類型共享鎖（S鎖）：如果事務(wù)Ti申請到數(shù)據(jù)項(xiàng)Q的共享鎖，則Ti可以讀數(shù)據(jù)項(xiàng)Q，但不能寫Q。排它鎖（X鎖）：如果事務(wù)Ti申請到數(shù)據(jù)項(xiàng)Q的排它鎖，則Ti可以讀數(shù)據(jù)項(xiàng)Q，也可以寫Q。鎖的相容性

當(dāng)事務(wù)需要操作數(shù)據(jù)項(xiàng)時(shí)，它向鎖管理器發(fā)出鎖的申請：若申請的是一個(gè)共享鎖，且申請隊(duì)列為空，當(dāng)前數(shù)據(jù)項(xiàng)上也沒有排它鎖，則鎖管理器授予鎖，并修改數(shù)據(jù)項(xiàng)的鎖表。若申請的是一個(gè)排它鎖，當(dāng)前也沒有其它的事務(wù)擁有該數(shù)據(jù)項(xiàng)上的鎖，則鎖管理器授予鎖，并修改數(shù)據(jù)項(xiàng)的鎖表。否則，申請的鎖不能馬上授予，鎖申請加入申請隊(duì)列，申請鎖的事務(wù)掛起。

更新后立即釋放鎖，可能臟讀。事務(wù)的最后釋放鎖，避免臟讀和確?？纱行?。但降低并發(fā)度相互等待出現(xiàn)死鎖

兩段鎖協(xié)議（two-phaselockingprotocol，2PL）是指所有事務(wù)分兩個(gè)階段提出加鎖和解鎖申請:增長階段（growingphase)：在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，首先申請并獲得該數(shù)據(jù)的封鎖；收縮階段（shrinkingphase)：在釋放一個(gè)封鎖后，事務(wù)不再申請和獲得其它的任何封鎖。兩段鎖協(xié)議是保證沖突可串行化的充分條件，但該協(xié)議不保證不發(fā)生死鎖。

兩段鎖協(xié)議的級聯(lián)回滾現(xiàn)象每個(gè)事務(wù)都遵從兩段鎖協(xié)議；若T1事務(wù)在WRITE（B）時(shí)刻發(fā)生故障，將導(dǎo)致事務(wù)T2、T3級聯(lián)回滾。

嚴(yán)格兩階段鎖除要求滿足兩段鎖協(xié)議規(guī)定外，還要求事務(wù)的排它鎖必須在事務(wù)提交之后釋放。解決級聯(lián)回滾問題避免了臟讀和丟失修改的問題。強(qiáng)兩階段鎖除要求滿足兩段鎖協(xié)議規(guī)定外，還要求事務(wù)的所有鎖都必須在事務(wù)提交之后釋放。進(jìn)一步解決數(shù)據(jù)項(xiàng)不能重復(fù)讀的問題

兩階段鎖總結(jié)從兩段鎖協(xié)議到嚴(yán)格兩段鎖協(xié)議，再到強(qiáng)兩段鎖協(xié)議，事務(wù)持鎖的時(shí)間不斷增長。這不但保證事務(wù)的并發(fā)調(diào)度是沖突可串行化的，還不斷增強(qiáng)了數(shù)據(jù)庫的一致性保證。但帶來的另一方面的問題是并發(fā)度的降低，以及死鎖出現(xiàn)可能性的增加。目前，大多數(shù)的DBMS都采用嚴(yán)格兩段鎖協(xié)議或強(qiáng)兩段鎖協(xié)議。

鎖的升級及更新鎖鎖的升級有可能使得出現(xiàn)死鎖的概率加大更新鎖只允許事務(wù)讀取數(shù)據(jù)項(xiàng)而不能修改數(shù)據(jù)項(xiàng)系統(tǒng)允許更新鎖升級，而不允許共享鎖升級

更新鎖相容矩陣ClicktoaddTitle1事務(wù)并發(fā)1ClicktoaddTitle2并發(fā)事務(wù)引起的問題2ClicktoaddTitle2可串行化3ClicktoaddTitle1基于鎖的并發(fā)控制協(xié)議4ClicktoaddTitle1*活鎖與死鎖5ClicktoaddTitle2*多粒度封鎖3

活鎖或餓死解決活鎖方法：采用先來先服務(wù)的策略。

死鎖死鎖的兩種處理方式：一種是進(jìn)行死鎖的預(yù)防，不讓并發(fā)執(zhí)行的事務(wù)出現(xiàn)死鎖的狀況；一種是允許死鎖的發(fā)生，在死鎖出現(xiàn)后采取措施解決，為此系統(tǒng)中需增加死鎖的檢測及死鎖的解除算法

順序封鎖法將數(shù)據(jù)庫對象按某種規(guī)定的順序排列，要求事務(wù)實(shí)行封鎖也必須按照這個(gè)順序進(jìn)行。缺點(diǎn)：不好確定數(shù)據(jù)庫對象的封鎖順序。維護(hù)封鎖順序是件困難的事情且成本很高一次封鎖法要求事務(wù)在開始執(zhí)行前先申請到所需的所有封鎖，如果有一個(gè)封鎖沒有申請到，則事務(wù)中止。缺點(diǎn)：在事務(wù)開始前很難預(yù)先知道哪些數(shù)據(jù)項(xiàng)需要封鎖；一次將所有需要的封鎖申請到，可能有些封鎖只在事務(wù)運(yùn)行的后期才需要，這就大大降低了系統(tǒng)的并發(fā)度。

時(shí)間戳法根據(jù)事務(wù)啟動(dòng)時(shí)的時(shí)間戳設(shè)置事務(wù)的優(yōu)先級，越早開始運(yùn)行的事務(wù)優(yōu)先級越高。為預(yù)防死鎖，在事務(wù)Ti申請的封鎖與事務(wù)Tj已經(jīng)擁有的封鎖發(fā)生沖突時(shí)，鎖管理器可使用如下兩種不同的機(jī)制：Wait-die機(jī)制：若Ti優(yōu)先級較高，則Ti可以等待；否則中止事務(wù)Ti。Wound-wait機(jī)制：若Ti優(yōu)先級較高，則中止Tj；否則Ti等待。示例：假設(shè)事務(wù)T1、T2、T3的時(shí)間戳分別為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等待。

超時(shí)法：規(guī)定申請鎖事務(wù)等待的最長時(shí)間。若超過了規(guī)定時(shí)間，則系統(tǒng)判定出現(xiàn)死鎖，此時(shí)該事務(wù)本身回滾并重啟。實(shí)現(xiàn)簡單可能出現(xiàn)誤判等待多長時(shí)間合適難以把握等待圖法：當(dāng)且僅當(dāng)?shù)却龍D中出現(xiàn)環(huán)路時(shí)，表示系統(tǒng)中存在死鎖。

死鎖的解除選擇一個(gè)或多個(gè)事務(wù)撤銷，釋放這個(gè)或這些事務(wù)擁有的封鎖。撤銷事務(wù)的選擇。為解除死鎖必須回滾處于死鎖狀態(tài)的部分事務(wù)。撤銷事務(wù)的選擇原則是事務(wù)撤銷所需的系統(tǒng)代價(jià)最小。事務(wù)撤銷的程度。全部回滾選中事務(wù)，然后重新開始。部分回滾選中事務(wù)，需要系統(tǒng)維護(hù)更多的事務(wù)運(yùn)行狀態(tài)信息。