事務(wù)管理的學(xué)習(xí)課件

事務(wù)管理的學(xué)習(xí)課件第1頁/共72頁1.單純以后備副本為基礎(chǔ)的恢復(fù)技術(shù)2.以后備副本和運(yùn)行記錄為基礎(chǔ)的恢復(fù)3.基于多副本的恢復(fù)技術(shù)恢復(fù)技術(shù)大致可以分為下列三種第2頁/共72頁1.單純以后備副本為基礎(chǔ)的恢復(fù)技術(shù)從文件系統(tǒng)繼承而來，周期性的把磁盤上的數(shù)據(jù)庫轉(zhuǎn)儲(chǔ)（dump）到脫機(jī)存放的磁帶上。失效取后備副本取后備副本取后備副本更新丟失更新丟失取后備副本取后備副本IDIDIDID取后備副本ID失效增量轉(zhuǎn)儲(chǔ)（ID）第3頁/共72頁單純以后備副本為基礎(chǔ)的恢復(fù)技術(shù)：優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，不增加數(shù)據(jù)庫正常運(yùn)行時(shí)的開銷。缺點(diǎn)：不能恢復(fù)到數(shù)據(jù)庫的最近一致的狀態(tài)。多用于文件系統(tǒng)以及小型的不重要的數(shù)據(jù)庫系統(tǒng)。第4頁/共72頁2.以后備副本和運(yùn)行記錄為基礎(chǔ)的恢復(fù)

運(yùn)行記錄（log或journal）由系統(tǒng)維護(hù)，一般包括下列內(nèi)容：（1）前像（BeforeImage,BI）當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更新前的映像（image）稱為該事務(wù)的前像（BI），前像以物理塊為單位；有了前像可以使數(shù)據(jù)庫恢復(fù)到更新前狀態(tài)，對(duì)應(yīng)操作undo(撤銷)。第5頁/共72頁（2）后像(AfterImage,AI)當(dāng)數(shù)據(jù)庫被一個(gè)事務(wù)更新時(shí)，所涉及的物理塊更新后的映像（image）稱為該事務(wù)的后像（AI），后像也以物理塊為單位；有了后像，即便更新的數(shù)據(jù)丟失了，仍然可以使數(shù)據(jù)庫恢復(fù)到更新后的狀態(tài)，相當(dāng)于重做一次更新，對(duì)應(yīng)操作redo(重做)。第6頁/共72頁問題：前像(BI)、后像(AI)和事務(wù)操作的關(guān)系？

修改——有前像有后像插入——沒前像有后像刪除——有前像沒后像第7頁/共72頁（3）事務(wù)狀態(tài)

記錄每個(gè)事務(wù)的狀態(tài)，以便在恢復(fù)時(shí)作不同的處理（COMMIT和NOTCOMMIT）。事務(wù)失敗事務(wù)開始活動(dòng)狀態(tài)操作結(jié)束事務(wù)提交回卷事務(wù)結(jié)束第8頁/共72頁

提交(Commit)——成功執(zhí)行(doall)。

回卷(Rollback或Abort)——消除事務(wù)對(duì)數(shù)據(jù)庫的影響(donothing)。

對(duì)恢復(fù)而言，至少要區(qū)分一個(gè)事務(wù)是否提交！

第9頁/共72頁實(shí)現(xiàn)方法最近后備副本運(yùn)行記錄失效最近后備副本運(yùn)行記錄基于后備副本與運(yùn)行記錄的恢復(fù)如上圖所示，當(dāng)數(shù)據(jù)庫失效時(shí)，取出最近后備副本，然后根據(jù)運(yùn)行記錄，對(duì)未提交的事務(wù)用前像卷回——向后恢復(fù)(backwardrecovery)；對(duì)已提交的事務(wù)，必要時(shí)用后像重做——向前恢復(fù)(forwardrecovery)。第10頁/共72頁這種恢復(fù)技術(shù)，需保持運(yùn)行記錄，這將會(huì)影響數(shù)據(jù)庫的正常工作速度，但可以使數(shù)據(jù)庫恢復(fù)到最近一致狀態(tài)。大多數(shù)商品化DBMS采用這種恢復(fù)技術(shù)。第11頁/共72頁3.基于多副本的恢復(fù)技術(shù)如果系統(tǒng)中有多個(gè)DB副本，且這些副本具有獨(dú)立的失效模式(independentfailuremode)，則可利用這些副本互為備份，用于恢復(fù)。此技術(shù)在分布式數(shù)據(jù)庫系統(tǒng)中應(yīng)用的較多。近年來，由于硬件價(jià)格的下降，也采用鏡像磁盤(mirroreddisks)技術(shù)。第12頁/共72頁寫數(shù)據(jù)時(shí)，兩個(gè)磁盤都寫入同樣的內(nèi)容。當(dāng)一個(gè)磁盤的數(shù)據(jù)丟失時(shí)，可以用另一個(gè)磁盤的數(shù)據(jù)來恢復(fù)。（兩盤同時(shí)故障的概率可以假設(shè)為零！）磁盤1磁盤2控制器1控制器2CPU1CPU2鏡像磁盤系統(tǒng)下面主要討論第二種恢復(fù)技術(shù)。第13頁/共72頁7.2運(yùn)行記錄的結(jié)構(gòu)

運(yùn)行記錄的存儲(chǔ)要避免與數(shù)據(jù)庫“全軍覆沒”。運(yùn)行記錄(log)一般不能和數(shù)據(jù)庫放在同一磁盤上，以免兩者皆失。（假設(shè)log和DBMS同時(shí)失效的概率為零；一般假設(shè)log不會(huì)損壞，若運(yùn)行中DBMS測(cè)得log損壞，則采取強(qiáng)制措施，例如拒絕新事務(wù)，完成已提交事務(wù)，停止運(yùn)行，修復(fù)log）。第14頁/共72頁運(yùn)行記錄的結(jié)構(gòu)因DBMS而異Log基本內(nèi)容

1.活動(dòng)事務(wù)表（activetransactionlist---ATL）記錄所有正在執(zhí)行，尚未提交的事務(wù)的標(biāo)識(shí)符(transactionidentifier---TID)。2.提交事務(wù)表（committedtransactionlist---CTL）記錄所有已提交事務(wù)的標(biāo)識(shí)符。第15頁/共72頁注意：提交時(shí)，先將要提交事務(wù)的TID加入CTL，再從ATL中刪除相應(yīng)的TID。否則，一旦發(fā)生故障，該事務(wù)的狀態(tài)將丟失！

問題：某事務(wù)需要提交時(shí)，該按照什么順序?qū)TL和CTL進(jìn)行更新？第16頁/共72頁3.前像文件可以看成一個(gè)堆文件。每個(gè)物理塊有個(gè)塊標(biāo)識(shí)符BID（blockidentifier）。BID由TID、關(guān)系名和邏輯塊號(hào)組成。邏輯塊號(hào)在關(guān)系中是唯一的。如果一個(gè)事務(wù)需要卷回，可以在前像文件中找出該事務(wù)的所有前像塊，按照邏輯塊號(hào)寫入到關(guān)系的對(duì)應(yīng)塊，從而消除該事務(wù)對(duì)數(shù)據(jù)庫的影響。undo滿足冪等性:undo(undo(undo…undo(x)))=undo(x)因此，undo失敗可以再undo!第17頁/共72頁4.后像文件結(jié)構(gòu)與前像文件相仿，不過記的是后像。在恢復(fù)時(shí)，可按提交事務(wù)表中的事務(wù)次序，按邏輯塊號(hào)，寫入其后像。這相當(dāng)于按提交的次序重做各個(gè)事務(wù)。redo滿足冪等性:redo(redo(redo…redo(x)))=redo(x)問題：undo操作需要按照事務(wù)的次序嗎？為什么？第18頁/共72頁取后備復(fù)本后，之前的運(yùn)行記錄就失去了價(jià)值，對(duì)恢復(fù)來說，只要保留最近后備復(fù)本以后的運(yùn)行記錄。但運(yùn)行記錄仍可能很大。可采用下列措施減小運(yùn)行記錄規(guī)模。1.不保留已提交事務(wù)的前像2.有選擇性的保留后像3.合并后像（對(duì)給定邏輯塊號(hào)的物理塊，如多次更新，可只保留最近的后像）如何判斷該做undo還是redo呢？下一節(jié)，將解決這個(gè)問題。第19頁/共72頁7.3更新事務(wù)的執(zhí)行與恢復(fù)1提交規(guī)則（CommitRule）

后像必須在事務(wù)提交前，寫入非易失性存儲(chǔ)器（DB或log）。

更新事務(wù)執(zhí)行時(shí)，應(yīng)遵守下兩條規(guī)則：2先記后寫規(guī)則（LogAheadRule）

如果后像在事務(wù)提交前寫入數(shù)據(jù)庫，則必須把前像先寫入log。在執(zhí)行一個(gè)更新事務(wù)時(shí)，按后像寫入DB的時(shí)間，有三種可能的方案。即后像不能僅留在內(nèi)存中！第20頁/共72頁三種更新策略a)后像在事務(wù)提交前完全寫入DB TID→activelist B.I→Log (按LogAhead

Rule) A.I→DB ┇ TID→commitlist deleteTIDfromactivelist第21頁/共72頁在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？Restart時(shí)，對(duì)每個(gè)TID，查兩個(gè)list：CommitlistActivelist

undo

deleteTIDfromactivelist

nothingtodo第22頁/共72頁b)后像在事務(wù)提交后寫入數(shù)據(jù)庫 TID→activelist A.I→Log (按commit

rule) ┇ TID→commitlist A.I→DB deleteTIDfromactivelist第23頁/共72頁在這種情況下，如果出現(xiàn)故障，如何恢復(fù)Restart時(shí)，對(duì)每個(gè)TID，查兩個(gè)list：CommitlistActivelist

deleteTIDfromactivelist

redo,deleteTIDfromactivelist

nothingtodo第24頁/共72頁c)后像在事務(wù)提交前后寫入數(shù)據(jù)庫 TID→activelist A.I,B.I→Log (按2rules) A.I→DB (partiallydone) ┇ TID→commitlist A.I→DB (completed) deleteTIDfromactivelist第25頁/共72頁在這種情況下，如果出現(xiàn)故障，如何恢復(fù)？Restart時(shí)，對(duì)每個(gè)TID，查兩個(gè)list：CommitlistActivelist

undo

redo,deleteTIDfromactivelist

nothingtodo思考：方案3均勻的將寫入DB的I/O操作分散在事務(wù)提交前后，有什么優(yōu)點(diǎn)？有利于磁盤均衡負(fù)載第26頁/共72頁

7.5消息的處理一個(gè)事務(wù)常常要給用戶發(fā)送有影響的消息(message)，不是指需要用戶輸入的指示消息。例如：“付款2000元”以及“立即執(zhí)行下一步處理”等。

發(fā)送消息也是事務(wù)執(zhí)行結(jié)果的一部分，應(yīng)該遵循“要么不做，要么全做”的原則。但是，消息往往難以用“undo”操作來消除其影響。因此，在事務(wù)結(jié)束前，消息不能發(fā)出，只有等事務(wù)結(jié)束后才能發(fā)出。帶來什么問題？第27頁/共72頁消息發(fā)送委托消息管理（messagemanager--MM）子系統(tǒng)執(zhí)行。事務(wù)執(zhí)行時(shí)，將需要發(fā)送的消息轉(zhuǎn)給MM,MM為每個(gè)事務(wù)建立一個(gè)消息隊(duì)列。MMTi消息1消息2第28頁/共72頁當(dāng)事務(wù)正常結(jié)束時(shí)（包括提交和回卷），事務(wù)通知MM發(fā)送消息；當(dāng)事務(wù)因故障被撤銷時(shí)，MM將把該事務(wù)的消息丟棄。為了保證消息能可靠的發(fā)送給有關(guān)用戶，MM采用“發(fā)送-確認(rèn)”方式傳遞。MM對(duì)事務(wù)委托發(fā)送的消息，在事務(wù)正常結(jié)束前，允許事務(wù)增加和刪除；一旦事務(wù)結(jié)束，MM就把消息存于不易失存儲(chǔ)器中。MM終端消息（MSG）確認(rèn)（ACK）第29頁/共72頁7.6失效的類型及恢復(fù)的對(duì)策一種恢復(fù)方法通常只對(duì)某些類型的失效有用。通常的失效可以分為以下三類：

1.事務(wù)失效(transactionfailure)

事務(wù)應(yīng)不可預(yù)知的原因而夭折。例如：數(shù)據(jù)庫中沒有要訪問的數(shù)據(jù)、輸入數(shù)據(jù)類型不對(duì)、除數(shù)為零等。事務(wù)失效時(shí)DB未被破壞，系統(tǒng)控制在手。且事務(wù)失效一定發(fā)生在事務(wù)提交前。第30頁/共72頁恢復(fù)措施：MM丟棄該事務(wù)的消息隊(duì)列；如果需要，進(jìn)行undo操作；從ATL刪除該事務(wù)的TID，釋放該事務(wù)所占資源。

2.系統(tǒng)失效(systemfailure)

系統(tǒng)(包括OS和DBMS)崩潰，需要重新啟動(dòng)(restart)，DB未被破壞，但系統(tǒng)失去控制。例如：掉電、除數(shù)據(jù)庫存儲(chǔ)介質(zhì)以外的軟、硬件故障等。第31頁/共72頁恢復(fù)措施：

重新啟動(dòng)OS和DBMS；恢復(fù)DB致一致狀態(tài)（對(duì)未提交的事務(wù)進(jìn)行undo操作對(duì)已提交的事務(wù)進(jìn)行redo操作）。只有當(dāng)數(shù)據(jù)庫恢復(fù)到一致狀態(tài)后，才允許用戶訪問數(shù)據(jù)庫。系統(tǒng)中，活動(dòng)事務(wù)表(ATL)的長度是有限的；由于累積效應(yīng)，提交事務(wù)表（CTL）可能很長。思考：系統(tǒng)失效時(shí)，要做undo和redo操作；然而ATL長度有限，CTL可能較長。這將導(dǎo)致什么結(jié)果？由于事務(wù)可以在提交前和提交后將數(shù)據(jù)的后像分別寫入數(shù)據(jù)庫，因而對(duì)CTL中的事務(wù)只能全部做redo，很費(fèi)時(shí)（可能CTL中的很多事務(wù)已經(jīng)完成將后像寫入數(shù)據(jù)庫，但鑒別代價(jià)很大）。第32頁/共72頁為了減少恢復(fù)時(shí)大量redo操作的工作量，在運(yùn)行過程中，DBMS每隔一定時(shí)間在運(yùn)行記錄中設(shè)置一個(gè)檢查點(diǎn)(checkpoint—CP)，在檢查點(diǎn)，DBMS強(qiáng)制寫入所有已提交事務(wù)的后像。最近后備副本失效運(yùn)行記錄最近后備副本CPCPCPCPCP運(yùn)行記錄失效顯然，在最近檢查點(diǎn)以前提交的事務(wù)，恢復(fù)時(shí)，不用redo。第33頁/共72頁取CP過程一般如下：暫停事務(wù)的執(zhí)行；寫入上一個(gè)CP以后所提交事務(wù)的后像；在log的CTL中記下檢查點(diǎn)；恢復(fù)事務(wù)的執(zhí)行。取CP很影響系統(tǒng)的正常運(yùn)行，而只有在發(fā)生系統(tǒng)失效時(shí)，才有其減少redo工作量的效益。第34頁/共72頁

3.介質(zhì)失效(mediafailure)

磁盤發(fā)生故障，DB被破壞。

修復(fù)系統(tǒng)，必要時(shí)更新磁盤；如果系統(tǒng)（OS和DBMS）崩潰，重新啟動(dòng)系統(tǒng)；加載最近后備副本；用log中的后像重做取最近后備副本后提交的所有事務(wù)?；謴?fù)措施：第35頁/共72頁第36頁/共72頁7.7并發(fā)控制7.7.1數(shù)據(jù)庫系統(tǒng)中的并發(fā)

1.串行訪問(serialaccess)——事務(wù)順序執(zhí)行。DBMST3T2T1時(shí)間T1T2T3第37頁/共72頁2.并發(fā)訪問(concurrentaccess)——DBMS可同時(shí)接納多個(gè)事務(wù)，事務(wù)可在時(shí)間上重疊執(zhí)行。DBMST1T2T3時(shí)間T1T2T3第38頁/共72頁

交叉并發(fā)（interleavedconcurrency）——單CPU系統(tǒng)，各個(gè)事務(wù)交叉使用CPU。

同時(shí)并發(fā)（simultaneousconcurrency）——多CPU系統(tǒng)，多個(gè)事務(wù)在CPU中同時(shí)運(yùn)行。7.7.2并發(fā)的目的

1.提高系統(tǒng)資源利用率；2.改善短事務(wù)響應(yīng)時(shí)間。例如，兩個(gè)事務(wù)T1和T2，T1長，先交付；T2短，稍后交付，如果串行執(zhí)行，則T2必須等T1，響應(yīng)時(shí)間很長。第39頁/共72頁丟失7.7.3并發(fā)引起的問題

事務(wù)若不加控制的并發(fā)執(zhí)行，會(huì)產(chǎn)生什么問題？1.丟失更新（lostupdate）T1Read(x)x:=x+1Write(x)T2Read(x)x:=2*xWrite(x)時(shí)間T1T2Read(x)Read(x)x:=x+1Write(x)x:=2*xWrite(x)問題：為什么會(huì)發(fā)生丟失更新？由兩個(gè)事務(wù)對(duì)同一數(shù)據(jù)并發(fā)寫入引起，稱為“寫-寫沖突”(write-writeconflict)第40頁/共72頁臟數(shù)據(jù)2.讀臟數(shù)據(jù)（dirtyread）T1write(t)rollbackT2read(t[x])read(t[y])時(shí)間T1T2read(t[x])write(t)read(t[y])rollback問題：為什么會(huì)發(fā)生讀臟數(shù)據(jù)？由于一個(gè)事務(wù)讀取另一個(gè)更新事務(wù)尚未提交的數(shù)據(jù)引起，稱為“讀-寫沖突”(read-writeconflict)第41頁/共72頁X已改變3.讀值不可復(fù)現(xiàn)（unrepeatableread)T1read(x)read(x)T2Write(x)時(shí)間T1T2Read(x)Write(x)Read(x)問題：為什么會(huì)發(fā)生讀值不可重現(xiàn)？由兩個(gè)事務(wù)對(duì)同一數(shù)據(jù)并發(fā)讀寫引起，問題出在“寫”操作上第42頁/共72頁事務(wù)并發(fā)執(zhí)行時(shí)可能會(huì)有兩種沖突：寫－寫、讀－寫；

寫－寫沖突在任何情況下都應(yīng)避免，讀－寫沖突一般情況下應(yīng)避免，但某些應(yīng)用場(chǎng)合可以容忍。第43頁/共72頁7.7.4并發(fā)控制的正確性準(zhǔn)則

思考：多個(gè)事務(wù)并發(fā)執(zhí)行，結(jié)果怎么估計(jì)？假設(shè)數(shù)據(jù)庫系統(tǒng)中，某一時(shí)刻并發(fā)執(zhí)行的事務(wù)集為{T1,T2,…Tn}，調(diào)度(Schedule)S是對(duì)n個(gè)事務(wù)所有操作的順序的一個(gè)安排。在S中，不同事物的操作可以交叉，但必須保持各個(gè)事務(wù)的操作的原有次序。（注意：操作是調(diào)度的基本單位！）設(shè)Write簡(jiǎn)寫為W，Read為R，R和W用其所屬事務(wù)號(hào)為下標(biāo)，上圖的調(diào)度可表示為：

S=…R1(x)…W2(x)…R1(x)…第44頁/共72頁對(duì)同一事務(wù)集,可能有很多種調(diào)度。如果其中兩個(gè)調(diào)度S1和S2，在數(shù)據(jù)庫的任何初始狀態(tài)下，所有讀出的數(shù)據(jù)都一樣，留給數(shù)據(jù)庫的最終狀態(tài)也一樣，則稱S1和S2是等價(jià)的，又稱為目標(biāo)等價(jià)(viewequivalence)?！卣Z義，難以判斷！還有一種更實(shí)用的等價(jià)定義，稱為沖突等價(jià)(conflictequivalence)?！菀讓?shí)現(xiàn)！沖突操作有讀-寫沖突和寫-寫沖突兩種，可表示為：Ri(x)和Wj(x)Wi(x)和Wj(x)(ij)第45頁/共72頁沖突操作的執(zhí)行次序會(huì)影響執(zhí)行結(jié)果，不沖突操作的次序可以互換，不致影響執(zhí)行結(jié)果。

凡是通過調(diào)換S中不沖突操作得到的新的調(diào)度，稱為S的沖突等價(jià)調(diào)度。如果兩個(gè)調(diào)度是沖突等價(jià)的，一定是目標(biāo)等價(jià)的；反之未必！第46頁/共72頁

若調(diào)度S在數(shù)據(jù)庫中產(chǎn)生的效果，與這組事務(wù)的某個(gè)串行執(zhí)行序列的結(jié)果相同，則稱這個(gè)調(diào)度S是可串行化的（serializable）。例如，對(duì)事務(wù)集{T1,T2,T3}的一個(gè)調(diào)度：

S=R2(x)W3(x)R1(y)W2(y)S’=R1(y)R2(x)W2(y)W3(x)S’是串行調(diào)度，故S是沖突可串行化的，也是目標(biāo)可串行化的！第47頁/共72頁沖突可串行化的調(diào)度一定是目標(biāo)可串行化的嗎？目標(biāo)可串行化的調(diào)度一定是沖突可串行化的嗎？目標(biāo)可串行化的調(diào)度未必是沖突可串行化！例如，調(diào)度S=R1(x)W2(x)W1(x)W3(x)無沖突等價(jià)調(diào)度，但卻可以找到一個(gè)調(diào)度S’：S’=R1(x)W1(x)W2(x)W3(x)與S目標(biāo)等價(jià)。第48頁/共72頁目標(biāo)可串行化沖突可串行化多個(gè)事務(wù)串行執(zhí)行后，DB仍保持一致狀態(tài)?？纱谢{(diào)度與事務(wù)的某個(gè)串行執(zhí)行等價(jià)。當(dāng)然也保持?jǐn)?shù)據(jù)庫的一致狀態(tài)，因此，在一般的DBMS中，都是以可串行化作為并發(fā)控制的正確性準(zhǔn)則！第49頁/共72頁可串行化——并發(fā)控制的正確性準(zhǔn)則問題：不同的調(diào)度→不同的等價(jià)串行序列→不同的執(zhí)行結(jié)果？(n!)第50頁/共72頁關(guān)于目標(biāo)等價(jià)與沖突等價(jià)調(diào)度：是系統(tǒng)對(duì)n個(gè)并發(fā)事務(wù)的所有操作的順序的一個(gè)安排。目標(biāo)等價(jià)：兩個(gè)調(diào)度s1和s2，如果在同樣的初始條件下執(zhí)行，對(duì)數(shù)據(jù)庫產(chǎn)生的效果完全相同，則稱s1和s2是目標(biāo)等價(jià)的。沖突操作：R-W、W-W。沖突操作的執(zhí)行順序會(huì)影響執(zhí)行效果。不沖突操作：①R-R②雖有寫操作，但作用對(duì)象不同，如Ri(x)和Wj(y)。沖突等價(jià)：凡是通過調(diào)換s中的不沖突操作所得的新調(diào)度，稱為s的沖突等價(jià)調(diào)度。第51頁/共72頁性質(zhì)：如兩調(diào)度是沖突等價(jià)的，則一定是目標(biāo)等價(jià)的；反之未必正確。串行化也分為目標(biāo)可串行化和沖突可串行化。例1：對(duì)事務(wù)集{T1,T2,T3}的一個(gè)調(diào)度s

s=R2(x)W3(x)R1(y)W2(y)→R1(y)R2(x)W2(y)W3(x)=s’因?yàn)閟’是串行調(diào)度，所以s是沖突可串行化的。例2：s=R1(x)W2(x)W1(x)W3(x)無沖突等價(jià)調(diào)度，但卻可以找到一個(gè)調(diào)度s’ s’=R1(x)W1(x)W2(x)W3(x) 與s目標(biāo)等價(jià)。 第52頁/共72頁目標(biāo)可串行化的測(cè)試算法是NP難度的，沖突可串行化覆蓋了絕大部分可串行化的調(diào)度實(shí)例，所以今后如無特別說明，可串行化均指沖突可串行化。前趨圖有向圖G=<V,E>V——頂點(diǎn)的集合，包含所有參與調(diào)度的事務(wù)。E——邊的集合，通過分析沖突操作來決定。如果下列條件之一成立，可在E中加邊Ti→Tj：Ri(x)在Wj(x)之前

Wi(x)在Rj(x)之前Wi(x)在Wj(x)之前最后，看構(gòu)造好的前趨圖中是否有環(huán)路，如果有，則該調(diào)度不可串行化；否則，可串行化。第53頁/共72頁可串行化時(shí)，決定等價(jià)串行調(diào)度序列的算法：由于無環(huán)路，必有入度為0的頂點(diǎn)。將它們及其有關(guān)的邊從圖中移去并將這些頂點(diǎn)存入一個(gè)隊(duì)列。對(duì)剩下的圖作同樣處理，不過移出的頂點(diǎn)要隊(duì)列中已有頂點(diǎn)之后。重復(fù)1，2直至所有頂點(diǎn)移入隊(duì)列為止。 例對(duì){T1,T2,T3,T4}的一個(gè)調(diào)度s S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 它是否可串行化？如可串行化找出其等價(jià)的串行執(zhí)行序列。第54頁/共72頁S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)并發(fā)控制的任務(wù)就是對(duì)并發(fā)執(zhí)行的事務(wù)加以控制，使之按某種可串行化的調(diào)度序列來執(zhí)行。T1T2T3T4T2T3T4隊(duì)列:T1T2T4隊(duì)列:T1,T3T4隊(duì)列:T1,T3,T2等價(jià)串行序列：T1→T3→T2→T4空第55頁/共72頁7.8加鎖協(xié)議—LockProtocol封鎖法是最基本的并發(fā)控制方法之一，它可以有多種實(shí)現(xiàn)方式。Xlocks：Onlyonetypeoflock,forbothreadandwrite相容矩陣： NL－nolock X－Xlock Y－相容 N－不相容待加已有NLXNLYYXYNX_lockRUpdateR┇X_unlockREOTTAX_lockRwaitX_lockRReadR┇TB第56頁/共72頁防止連鎖卷回現(xiàn)象的發(fā)生（多米諾骨牌）事務(wù)結(jié)束(EOT)第57頁/共72頁*TwoPhaseLockingDef1:Inatransaction,ifalllocksprecedeallunlocks,thenthetransactioniscalledtwophasetransaction.Thisrestrictioniscalledtwophaselockingprotocol.Def2:Inatransaction,ifitfirstacquiresalockontheobjectbeforeoperatingonit,itiscalledwell-formed.T1LockALockBLockC┇UnlockAUnlockBUnlockCT2LockALockBUnlockAUnlockBLockC┇UnlockC2PLnot2PLGrowingphaseShrinkingphaseTheorem:IfSisanyscheduleofwell-formedand2PLtransactions,thenSisserializable. (王書p151證明)第58頁/共72頁結(jié)論：Well-formed+2PL:serializableWell-formed+2PL+unlockupdateatEOT:serializableandrecoverable.(不會(huì)有多米諾現(xiàn)象)Well-formed+2PL+holdingalllockstoEOT:stricttwophaselockingtransaction.第59頁/共72頁(S,X)鎖Slock——ifreadaccessisintended.Xlock——ifupdateaccessisintended.待加已有NLSXNLYYYSYYNXYNN1.使用(S,X)鎖要防止活鎖現(xiàn)象發(fā)生2.規(guī)定“先生請(qǐng)，先服務(wù)”第60頁/共72頁(S,U,X)鎖U鎖——updatelock.ForanupdateaccessthetransactionfirstacquiresaU-lockandthenpromoteittoX-lock.目的：減少排他時(shí)間，提高并發(fā)度，減少死鎖。

待加

已有NLSUXNLYYYYSYYYNUYYNNXYNNNX (S,X) (S,U,X)concurrency第61頁/共72頁7.9死鎖的檢測(cè)處理和防止死鎖：循環(huán)等待，誰也無法得到全部資源。活鎖：雖然其它事務(wù)都在有限長的時(shí)間內(nèi)釋放了資源，但某事務(wù)就是無法得到想要的資源。X_lockR1┇X_lockR2waitTAX_lockR2┇X_lockR1waitTBRT1:S-lockT2:S-lock┇T:x-lock活鎖較簡(jiǎn)單，只需稍加修改調(diào)度策略，如FIFO死鎖：(1)防(不允許發(fā)生)；(2)治(允許，能消除)第62頁/共72頁死鎖的檢測(cè)超時(shí)法:某事務(wù)等待時(shí)間超過某個(gè)定值，便認(rèn)為發(fā)生了死鎖，該事務(wù)被終止。等待圖法G=<V,E> V—

事務(wù)集{Ti|TiisatransactioninDBS(i=1,2,…n)} E－{<Ti,Tj>|TiwaitsforTj(i≠j)}若圖中有環(huán)路則說明已經(jīng)發(fā)生死鎖。何時(shí)檢測(cè)?一旦某個(gè)事務(wù)等待.周期性進(jìn)行第63頁/共72頁死鎖的處理如何處理死鎖?選出犧牲事務(wù)(最年輕、卷回代價(jià)最小…)終止?fàn)奚聞?wù)釋放它所有的鎖及資源該事務(wù)等待一段時(shí)間重啟動(dòng)該事務(wù)(系統(tǒng)進(jìn)行or用戶進(jìn)行)第64頁/共72頁死鎖的防止一次性申請(qǐng)所有鎖將數(shù)據(jù)對(duì)象編號(hào)，按序號(hào)加鎖一旦沖突，便終止相關(guān)事務(wù)卷回重執(zhí)第65頁/共72頁每個(gè)事務(wù)有唯