第8章-事務(wù)并發(fā)控制

xshxie@第2部分關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)第8章事務(wù)并發(fā)控制高級(jí)數(shù)據(jù)庫(kù)系統(tǒng)及其應(yīng)用第8章事務(wù)并發(fā)控制事務(wù)并發(fā)執(zhí)行管理概述8.1基于封鎖的并發(fā)控制8.2死鎖及其處理8.3擴(kuò)展封鎖處理技術(shù)8.4基于優(yōu)化的并發(fā)控制8.5SQL-92的事務(wù)支持8.68.1事務(wù)并發(fā)執(zhí)行管理概述8.1.1事務(wù)的概念與基本特性8.1.2調(diào)度的基本概念8.1.3事務(wù)的并發(fā)執(zhí)行8.1.4優(yōu)先圖8.1.5視可串行化DB事務(wù)DBMS內(nèi)核會(huì)自動(dòng)將來(lái)自一條或多條SQL語(yǔ)句的用戶讀寫DB請(qǐng)求，劃分為若干個(gè)事務(wù)。每個(gè)事務(wù)有自己的局部?jī)?nèi)存，由一系列讀/寫DB數(shù)據(jù)元素的動(dòng)作構(gòu)成。DB(數(shù)據(jù))元素或稱為DB對(duì)象，泛指DB關(guān)系表、數(shù)據(jù)頁(yè)或元組等，具體要視具體場(chǎng)合或上下文而定。讀一個(gè)DB元素X通常是先將X從磁盤頁(yè)帶到DB緩沖區(qū)，然后再?gòu)?fù)制到事務(wù)局部?jī)?nèi)存的相應(yīng)變量t中。寫一個(gè)DB元素X總是先修改局部?jī)?nèi)存中的變量t，再將t復(fù)制到DB緩沖區(qū)，必要時(shí)候再將X從DB緩沖區(qū)刷新到磁盤。

這里共涉及到三個(gè)地址空間：磁盤空間、DB緩沖區(qū)(虛存空間)和事務(wù)局部主存空間。8.1.1事務(wù)的基本概念與特性事務(wù)定義：是DBMS中一個(gè)可執(zhí)行的、具有一定偏序的動(dòng)作序列。動(dòng)作(actions)：指‘讀/寫’DB數(shù)據(jù)元素，或指定事務(wù)結(jié)束行為的動(dòng)作，如commit(提交)、abort(中止)等。對(duì)指定的事務(wù)T，以上所列的幾個(gè)動(dòng)作可簡(jiǎn)記為RT(X),WT(X),COMMITT,ABORTT。實(shí)際DB事務(wù)中也可能含有一些不影響并發(fā)的、事務(wù)管理一般不顯式列出的其它動(dòng)作，如讀寫OS文件、內(nèi)部賦值計(jì)算等。所謂的偏序，是指事務(wù)中有些關(guān)鍵動(dòng)作順序很重要，但也有些動(dòng)作的前后相對(duì)順序并不重要。事務(wù)的四個(gè)基本特性原子性(atomic)事務(wù)的執(zhí)行具有原子性。要么成功，所有事務(wù)動(dòng)作都被正常執(zhí)行；要么失敗，任何一個(gè)事務(wù)動(dòng)作都未被執(zhí)行。如果執(zhí)行中間出錯(cuò)或被中止，則之前已執(zhí)行過(guò)的那些動(dòng)作必須全部撤銷，事務(wù)回滾(rollback)。一致性(consistency)當(dāng)事務(wù)獨(dú)立執(zhí)行時(shí)，必須能保持DB狀態(tài)的一致性。孤立性(isolation)盡管DBMS內(nèi)核通常以并發(fā)形式管理事務(wù)，但對(duì)用戶而言，仍是以事務(wù)被‘孤立’執(zhí)行，來(lái)理解其執(zhí)行效果。持久性(durability)當(dāng)事務(wù)被成功執(zhí)行后，它對(duì)DB數(shù)據(jù)造成的影響應(yīng)是持久性的；即使是發(fā)生系統(tǒng)突然崩潰時(shí)，也應(yīng)如此。8.1.2調(diào)度的基本概念

調(diào)度(Scheduling)定義指對(duì)一組可能來(lái)自多個(gè)不同事務(wù)動(dòng)作流的一種偏序序列安排完全調(diào)度（completeschedule）調(diào)度所包含的所有事務(wù)都有提交或中止動(dòng)作。串行調(diào)度（seriesschedule）調(diào)度中，來(lái)自不同事務(wù)的動(dòng)作沒(méi)有交替。8.1.2調(diào)度的基本概念例8.1一個(gè)包含了兩個(gè)事務(wù)T1、T2的調(diào)度。這兩個(gè)事務(wù)都沒(méi)有Commit或Abort動(dòng)作；列表中，從上到下的逐行排序，隱含了動(dòng)作執(zhí)行時(shí)間的先后。8.1.3事務(wù)的并發(fā)執(zhí)行

交替執(zhí)行不同事務(wù)的動(dòng)作，是DBMS并發(fā)響應(yīng)多用戶請(qǐng)求，提高系統(tǒng)性能的必然要求。但并不是所有的交替都是允許的。兩個(gè)一致性事務(wù)，當(dāng)它們交替執(zhí)行時(shí)，可能導(dǎo)致DB狀態(tài)出現(xiàn)不一致。

交替執(zhí)行可能導(dǎo)致異常的幾種典型情況

讀未提交數(shù)據(jù)（WR沖突）不可重復(fù)的讀（WR沖突）重寫未提交的數(shù)據(jù)（WW沖突）調(diào)度中包含中止事務(wù)可恢復(fù)調(diào)度與可串行調(diào)度可恢復(fù)調(diào)度如果一個(gè)調(diào)度S只包含滿足以下規(guī)定的事務(wù)Ti，則稱調(diào)度S是可恢復(fù)的。令事務(wù)Ti可能讀取DB元素集{X}，而{Tj|j≠i}是至少改變了元素集合{X}中一個(gè)元素的所有事務(wù)集合，則事務(wù)Ti必須在{Tj|j≠i}中所有事務(wù)都提交之后才能提交?？纱谢{(diào)度當(dāng)一個(gè)包含一組提交事務(wù)的調(diào)度執(zhí)行時(shí)，如果對(duì)任何一致性DB造成的影響，與某個(gè)包含同組事務(wù)的串行調(diào)度相同。沖突等價(jià)與沖突可串行化沖突定義稱兩個(gè)動(dòng)作是沖突的或不可交換的，如果它們屬于同一事務(wù)，或當(dāng)它們都對(duì)同一DB元素操作且其中至少有一個(gè)是寫操作。稱兩個(gè)調(diào)度S1和S2沖突等價(jià)，如果滿足：（1）在S1與S2中，都包含了同一組事務(wù)，以及屬于這組事務(wù)的相同動(dòng)作集；（2）S1中任意兩個(gè)提交事務(wù)的每個(gè)沖突動(dòng)作對(duì)的先后順序，與S2中發(fā)生的情況相同。沖突可串行化稱調(diào)度S是沖突可串行化的，如果S與某個(gè)串行調(diào)度的沖突等價(jià)。

8.1.5視可串行化(viewserializability)視等價(jià)定義：令兩調(diào)度S1和S2包含同樣的事務(wù)集，如果滿足以下三個(gè)條件，則稱它們視等價(jià)。若在S1中事務(wù)Ti讀元素A的初值，則在S2中事務(wù)Ti也必須讀元素A的初值；若在S1中事務(wù)Ti讀被事務(wù)Tj寫過(guò)的元素A值，則在S2中事務(wù)Ti也必須讀被事務(wù)Tj寫過(guò)的元素A值；若S1中由某事務(wù)Ti執(zhí)行了對(duì)DB元素A的最后寫操作，則在S2中，Ti也須是對(duì)A執(zhí)行最后寫操作的事務(wù)。如果一個(gè)調(diào)度視等價(jià)于某串行調(diào)度，則稱該調(diào)度是視可串行化的。視可串行化是一種比沖突可串行化弱的可串行化條件。例8.2給定調(diào)度S:R1(A),W2(A),COMMIT(T2),W1(A),COMMIT(T1),W3(A),COMMIT(T3)試分析它的可串行性。它等價(jià)于串行調(diào)度T1,T2,T3（兩調(diào)度中，T1讀到的A值相同，且A值最終值都由T3寫)，因而是可串行調(diào)度；但這個(gè)調(diào)度顯然不是沖突可串行化的，它與串行調(diào)度T1,T2,T3在沖突上不等價(jià)。本例中，調(diào)度S雖不滿足沖突可串行化，但卻是一個(gè)視可串行化的調(diào)度。

嚴(yán)格調(diào)度、可恢復(fù)調(diào)度與可避免嚴(yán)格中止調(diào)度嚴(yán)格調(diào)度對(duì)調(diào)度中的任意事務(wù)T，要求T所寫的值，在T提交或中止之前，不會(huì)被S中其它事務(wù)讀或重寫?？苫謴?fù)調(diào)度對(duì)調(diào)度中的任意事務(wù)T，如果讀取了某個(gè)元素集{X}，則T必須等到調(diào)度中修改了元素集{X}的所有其它事務(wù)提交之后才能提交?？杀苊饧?jí)聯(lián)中止avoids-cascading-aborts事務(wù)只讀已提交數(shù)據(jù)（無(wú)臟讀）。這種事務(wù)不僅是可恢復(fù)的，且中止該事務(wù)不會(huì)級(jí)聯(lián)中止其它事務(wù)。8.1.4優(yōu)先圖(precedencegraph)

調(diào)度S優(yōu)先圖構(gòu)成：S中的每個(gè)事務(wù)對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn)。若Ti動(dòng)作A先于Tj的動(dòng)作B，且動(dòng)作A與B存在沖突，則有一條從Ti對(duì)應(yīng)節(jié)點(diǎn)到Tj對(duì)應(yīng)節(jié)點(diǎn)的弧。定理8.1一個(gè)調(diào)度S是沖突可串行化的，當(dāng)且僅當(dāng)它的優(yōu)先圖是無(wú)環(huán)的。

8.2基于封鎖的并發(fā)控制8.2.1嚴(yán)格兩階段封鎖協(xié)議8.2.2一般兩階段封鎖協(xié)議8.2.3封鎖管理8.2基于封鎖的并發(fā)控制

通常，DBMS必須能確保：只允許可串行化和可恢復(fù)的調(diào)度，在撤銷事務(wù)時(shí),不會(huì)導(dǎo)致其它已提交事務(wù)動(dòng)作效果丟失。DBMS常用基于‘封鎖協(xié)議’調(diào)度來(lái)達(dá)到這一目標(biāo)。封鎖協(xié)議：指每個(gè)事務(wù)都必須遵循的一組規(guī)則。調(diào)度的一致性在基于封鎖的調(diào)度器中，事務(wù)只有先獲得某DB元素的鎖且還沒(méi)釋放，才可訪問(wèn)該元素；訪問(wèn)結(jié)束后，事務(wù)必須釋放該元素的鎖。調(diào)度的合法性調(diào)度中的所有事務(wù)，都嚴(yán)格按封鎖協(xié)議來(lái)獲得DB元素鎖8.2.1嚴(yán)格兩階段封鎖協(xié)議(Strict-2PL)嚴(yán)格-2PL:指包含以下兩條規(guī)則的基本封鎖協(xié)議有兩種元素鎖：如果一個(gè)事務(wù)T準(zhǔn)備讀一個(gè)元素，必須先獲得該元素的共享鎖；如果準(zhǔn)備修改一個(gè)元素，則必須先獲得該元素的排它鎖。事務(wù)所持有的所有鎖只有在它完成時(shí)，才允許釋放。如果一個(gè)調(diào)度S的所有事務(wù)都遵循這兩個(gè)規(guī)則，則稱S是嚴(yán)格-2PL調(diào)度。由DBMS調(diào)度負(fù)責(zé)自動(dòng)往事務(wù)動(dòng)作流中，插入獲得鎖和釋放鎖的請(qǐng)求。一個(gè)請(qǐng)求鎖的事務(wù)將被阻塞掛起（延遲），直到系統(tǒng)同意授予所請(qǐng)求的鎖為止。

一個(gè)演示嚴(yán)格-2PL協(xié)議起作用的示例

8.2.2一般兩階段封鎖協(xié)議(2PL)

一般2PL是嚴(yán)格-2PL協(xié)議的一種變體，它放松了嚴(yán)格2PL的第二條規(guī)則：允許事務(wù)在結(jié)束(提交或中止)之前釋放鎖。2PL(規(guī)則1)：與嚴(yán)格-2PL相同。2PL(規(guī)則2)：當(dāng)一個(gè)事務(wù)已經(jīng)釋放了一個(gè)鎖之后，就不能再請(qǐng)求額外的鎖。通常把釋放第一個(gè)鎖之前的階段稱為“增長(zhǎng)階段(Growingphase)”，把之后的階段稱為“萎縮(Shrinkingphase)”階段。定理：由若干一致的兩階段封鎖事務(wù)構(gòu)成的任意合法調(diào)度S，肯定是沖突等價(jià)的可串行調(diào)度。strict-2PL與一般2PL對(duì)比嚴(yán)格調(diào)度（定義）一個(gè)調(diào)度S被稱為嚴(yán)格的，如果被一個(gè)S中事務(wù)T寫的值在它提交或中止之前，不被S中其它事務(wù)讀或重寫。嚴(yán)格調(diào)度是可恢復(fù)的，且可避免級(jí)聯(lián)中止。嚴(yán)格-2PL增強(qiáng)了2PL，能保證每個(gè)允許的調(diào)度都是嚴(yán)格的，且是沖突可串行化的。這是因?yàn)楫?dāng)一個(gè)事務(wù)在嚴(yán)格-2PL下寫一個(gè)元素時(shí)，它將持有排它鎖直到提交或中止－－不會(huì)有其它事務(wù)能‘看見(jiàn)’或修改這個(gè)元素的值。

8.2.3封鎖管理

封鎖管理器工作的基本數(shù)據(jù)結(jié)構(gòu)；封鎖管理基本算法8.3死鎖及其處理8.3.1預(yù)防死鎖8.3.2死鎖檢索8.3.3基于封鎖的并發(fā)控制性能8.3死鎖及其處理

死鎖(Deadlock)定義：在一組事務(wù)中，如果每一個(gè)都在等待其它事務(wù)占有的資源(持有的鎖)，使得每個(gè)事務(wù)都無(wú)法向前推進(jìn)。死鎖是所有事務(wù)都被無(wú)限長(zhǎng)延遲的極端阻塞情況即使是兩階段封鎖事務(wù)，也可能發(fā)生死鎖。處理死鎖的兩種基本方法：預(yù)防法(DeadlockPrevention)檢測(cè)法(DeadlockDetection)8.3.1預(yù)防死鎖根據(jù)事務(wù)啟動(dòng)的先后賦予事務(wù)不同的時(shí)間戳，規(guī)定小時(shí)間戳(更早或較老)事務(wù)，具有較高的優(yōu)先權(quán)。如果一個(gè)事務(wù)Ti請(qǐng)求一個(gè)鎖，而事務(wù)Tj持有這個(gè)鎖，則封鎖管理器可使用下面的兩種策略之一來(lái)預(yù)防死鎖發(fā)生：等待-死亡(Wait-die)如果事務(wù)Ti有較高優(yōu)先級(jí)，則允許它等待；否則中止Ti（自死亡）；傷害-等待(Wound-wait)如果Ti有較高的優(yōu)先級(jí)，則會(huì)中止(傷害)Tj；否則Ti等待；附加策略：“被中止而重新啟動(dòng)事務(wù)，總保持原有的時(shí)間戳”，能保證每個(gè)事務(wù)最終總會(huì)變?yōu)樽銐蚶希蔀榫哂懈邇?yōu)先權(quán)的事務(wù)。8.3.2基于等待圖的死鎖檢測(cè)

等待圖的拓?fù)浣Y(jié)構(gòu)：每個(gè)活躍事務(wù)對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn)；如果事務(wù)Ti正等待事務(wù)Tj所持有的某個(gè)鎖，則有一條從Ti對(duì)應(yīng)節(jié)點(diǎn)指向Tj對(duì)應(yīng)節(jié)點(diǎn)的邊。它可清晰表達(dá)事務(wù)等待其它事務(wù)持有鎖的情況。封鎖管理器通過(guò)維護(hù)等待圖來(lái)檢測(cè)死鎖循環(huán)。一個(gè)會(huì)導(dǎo)致死鎖的調(diào)度及其等待圖(圖8.7)

8.3.3基于封鎖的并發(fā)控制性能

基于封鎖的并發(fā)控制機(jī)制，主要使用“阻塞(blocking)”和“中止(aborting)”兩種機(jī)制來(lái)解決并發(fā)事務(wù)間的動(dòng)作沖突。兩種處理機(jī)制都有性能懲罰因素被阻塞事務(wù)可能因持有某些鎖，而導(dǎo)致更多的事務(wù)阻塞等待；中止和重啟動(dòng)則會(huì)浪費(fèi)事務(wù)已完成的工作。DBMS中，要設(shè)計(jì)一個(gè)良好的、基于封鎖的并發(fā)控制機(jī)制，必須在以下幾個(gè)方面作出選擇：是使用死鎖預(yù)防還是死鎖-檢測(cè)機(jī)制？如果使用死鎖-檢測(cè)機(jī)制，則多長(zhǎng)時(shí)間間隔檢測(cè)一次？檢測(cè)到了一個(gè)死鎖，應(yīng)中止等待環(huán)中的那個(gè)事務(wù)？檢測(cè)方法與預(yù)防方法比較

實(shí)現(xiàn)難易程度預(yù)防法實(shí)現(xiàn)通常比檢測(cè)法更容易。特別是當(dāng)DB為分布式時(shí)，構(gòu)造等待圖必須通過(guò)各個(gè)節(jié)點(diǎn)上的鎖表集合來(lái)構(gòu)造。在死鎖發(fā)生不頻繁的場(chǎng)合，基于檢測(cè)死鎖方案通常效果更好、更為實(shí)用。等待圖能使由于死鎖而必須中止事務(wù)的次數(shù)最少。除非真的存在死鎖，否則系統(tǒng)決不會(huì)中止事務(wù)。而預(yù)防法常會(huì)在并不存在死鎖的情況下中止事務(wù)。然而，在封鎖競(jìng)爭(zhēng)程度很大的場(chǎng)合，死鎖的生命期會(huì)變得很長(zhǎng)，這時(shí)基于預(yù)防的方案效果可能會(huì)更好些。

保守-2PL(Conservative2PL)事務(wù)必須獲得它可能需要的所有鎖后，才能開(kāi)始執(zhí)行，否則只能阻塞等待。該協(xié)議除了能保證沖突可串行化外，還能確保不發(fā)生死鎖。任何一個(gè)已經(jīng)持有某些鎖的事務(wù)，不會(huì)發(fā)生等待其它事務(wù)持有鎖而被阻塞。作為性能代價(jià)，保守-2PL要求事務(wù)更早獲得所有鎖。相比于其它協(xié)議，如果系統(tǒng)封鎖競(jìng)爭(zhēng)不強(qiáng)，則事務(wù)持有鎖的平均時(shí)間會(huì)較長(zhǎng)。但在系統(tǒng)封鎖競(jìng)爭(zhēng)很強(qiáng)烈時(shí)，事務(wù)持有鎖的平均時(shí)間反而會(huì)減少，且持有鎖的事務(wù)從不會(huì)被阻塞。8.4擴(kuò)展封鎖處理技術(shù)8.4.1動(dòng)態(tài)數(shù)據(jù)庫(kù)與幻象問(wèn)題8.4.2B+樹(shù)的并發(fā)控制8.4.3多粒度封鎖8.4擴(kuò)展封鎖處理技術(shù)針對(duì)元素集大小可變擴(kuò)展討論：著名的幻象(phantom)問(wèn)題針對(duì)元素間非獨(dú)立擴(kuò)展1針對(duì)元素間非獨(dú)立擴(kuò)展2討論：具有嵌套包含關(guān)系元素組的多粒度封鎖問(wèn)題前面已介紹的各種封鎖協(xié)議，都是將DB抽象為一組相互獨(dú)立的、DB元素固定的集合。本節(jié)我們將放寬這個(gè)限制，并討論相關(guān)擴(kuò)展處理方法。方法:通過(guò)進(jìn)一步細(xì)化封鎖協(xié)議,以獲得更好性能討論：樹(shù)形結(jié)構(gòu)對(duì)象的封鎖問(wèn)題8.4.1動(dòng)態(tài)數(shù)據(jù)庫(kù)與幻象問(wèn)題實(shí)例分析：事務(wù)T1掃描Sailors關(guān)系，檢索職級(jí)rating=1和2的最大年齡水手。T2插入一個(gè)rating=1,age=96的新元組討論不同的動(dòng)作執(zhí)行順序?qū)Y(jié)果的影響如果事務(wù)封鎖了一組DB元素后，其它事務(wù)還能導(dǎo)致組元素增加(enlarging)，則沖突可串行化并不能真正保證可串行化。處理幻象問(wèn)題的方法封鎖整個(gè)關(guān)系文件如果沒(méi)有索引且文件所有頁(yè)必須被掃描，則必須封鎖整個(gè)關(guān)系文件。采用謂詞封鎖技術(shù)如果有特定字段上的稠密索引，則直接封鎖指定鍵值范圍的索引項(xiàng)。索引封鎖實(shí)際上是謂詞封鎖中的一種特殊情形。謂詞封鎖是一種代價(jià)相對(duì)昂貴的封鎖方法，實(shí)際系統(tǒng)中并不常用。

8.4.2B+樹(shù)的并發(fā)控制

將B樹(shù)索引當(dāng)作一般文件，以頁(yè)為單位，采用2PL協(xié)議進(jìn)行并發(fā)控制管理，將會(huì)導(dǎo)致很強(qiáng)的封鎖競(jìng)爭(zhēng)。因?yàn)槿魏卧L問(wèn)B+樹(shù)的事務(wù)都要經(jīng)根節(jié)點(diǎn)現(xiàn)已有一些更有效的封鎖協(xié)議，如樹(shù)協(xié)議，能充分利用B+樹(shù)的層次結(jié)構(gòu)特征，在確?？纱谢涂苫謴?fù)性的同時(shí)，有效提高系統(tǒng)的并發(fā)性能。針對(duì)B+樹(shù)結(jié)構(gòu)特點(diǎn)的兩點(diǎn)觀察

樹(shù)的內(nèi)層只是用來(lái)幫助搜索，只有葉節(jié)點(diǎn)上才存儲(chǔ)的數(shù)據(jù)記錄或記錄指針；對(duì)搜索操作：必須獲得沿路徑（從根至葉）的各節(jié)點(diǎn)共享鎖；此外，B+樹(shù)搜索從不需要回溯。以上觀察說(shuō)明“一旦達(dá)到并封鎖了某節(jié)點(diǎn)的子節(jié)點(diǎn)，則該節(jié)點(diǎn)上的鎖即可釋放”。

對(duì)于插入：如果因葉節(jié)點(diǎn)修改分裂，可能傳播到的上層節(jié)點(diǎn)，必須以排它模式封鎖。一個(gè)用來(lái)分析樹(shù)封鎖方式的3階B+樹(shù)搜索38*，事務(wù)Ti需經(jīng)歷的動(dòng)作序列：獲得A的S鎖,讀A,確定下層節(jié)點(diǎn)B；獲B的S鎖,釋A的S鎖；獲C的S鎖，釋B的S鎖；獲D的S鎖，釋C的S鎖。

為了迫使操作同一葉節(jié)點(diǎn)的其它后來(lái)事務(wù)不超越Ti，Ti必至少維持搜索路徑上一個(gè)節(jié)點(diǎn)的鎖。例如，比Ti更晚的事務(wù)Tj要?jiǎng)h38*,也須穿越從ABCD這條路徑，且須等待Ti先完成（Tj始終無(wú)法逾越Ti）。插入45*的動(dòng)作序列：1)獲A的S鎖，獲B的S鎖；釋A的S鎖,獲C上的S鎖(這時(shí),不能馬上釋B鎖，因?yàn)镃是滿的)；2)獲E的X鎖，釋放C的鎖，并釋B的鎖(因E未滿)；3)在E上插入45*，釋放E的X鎖。

再分析插入25*:事務(wù)最終會(huì)獲得F上的S鎖，H上的X鎖。不幸的是，H是滿的，插入新項(xiàng)后須分裂。分裂H，需修改F；但現(xiàn)在F上只持有S鎖，？圖8.8樹(shù)協(xié)議（一種2PL變體規(guī)則）

讀模式訪問(wèn)某樹(shù)節(jié)點(diǎn)，必須先獲得該節(jié)點(diǎn)的S鎖（共享鎖）；讀/寫模式訪問(wèn)某節(jié)點(diǎn)，必須先獲得該節(jié)點(diǎn)的X鎖（排它鎖）；但沒(méi)有兩階段封鎖限制。對(duì)于樹(shù)中的一個(gè)節(jié)點(diǎn)，事務(wù)只有在其上持有鎖時(shí)，才能獲得其后續(xù)子節(jié)點(diǎn)的鎖。事務(wù)的第1個(gè)鎖可以在樹(shù)的任何節(jié)點(diǎn)上。節(jié)點(diǎn)可在任何時(shí)候解鎖，無(wú)兩階段封鎖限制。事務(wù)不能對(duì)一個(gè)已經(jīng)解鎖的節(jié)點(diǎn)重新上鎖，即使它在其父節(jié)點(diǎn)上仍持有鎖。樹(shù)協(xié)議起作用的原因分析

調(diào)度S中事務(wù)Ti和Tj封鎖一個(gè)共同的結(jié)點(diǎn)，而Ti先封鎖該結(jié)點(diǎn)，則稱Ti先于Tj（簡(jiǎn)記為Ti<Tj）。對(duì)任意兩個(gè)事務(wù)Ti和Tj，如果Ti先于Tj封鎖根，那么Ti在Tj前封鎖兩者都共同封鎖的結(jié)點(diǎn)(相當(dāng)于強(qiáng)制一個(gè)串行調(diào)度)。本質(zhì)上看，可認(rèn)為樹(shù)協(xié)議在調(diào)度涉及的事務(wù)上強(qiáng)制實(shí)現(xiàn)一個(gè)串行順序；可以證明：滿足樹(shù)協(xié)議的調(diào)度優(yōu)先圖總是無(wú)環(huán)的。

8.4.3多粒度封鎖

不同DB元素，可能有不同粒度，且相互間可能還存在包含性的層次結(jié)構(gòu)。對(duì)某節(jié)點(diǎn)的鎖，隱含了對(duì)該節(jié)點(diǎn)所有子節(jié)點(diǎn)的鎖。多粒度封鎖時(shí)，需要考慮的一些特別因素當(dāng)一個(gè)事務(wù)已獲得某層次節(jié)點(diǎn)鎖時(shí)，必須能防止該節(jié)點(diǎn)的上層大粒度元素不會(huì)被其它事務(wù)以某種有沖突的方式封鎖。盡可能將較嚴(yán)格的封鎖（X鎖）局限在較小粒度元素上，這樣會(huì)更有利于提高系統(tǒng)的并發(fā)性能。如果必須封鎖較大粒度元素（會(huì)隱含封鎖下層所有子元素），應(yīng)盡可能使用寬松的模式進(jìn)行封鎖。多粒度封鎖正是基于以上考慮而提出的一種封鎖協(xié)議。多粒度封鎖協(xié)議除了S鎖、X鎖外，多粒度封鎖還引入了用在上層大粒度元素上、起一種警示作用的意向鎖：意向共享鎖（IS,intentionsharedlock)意向排它鎖（IX,Intentionexclusivelock）。在包含它的上層大粒度元素上放置意向鎖，可以防止其它事務(wù)以有沖突方式封鎖上層大粒度元素。IS與IX之間沒(méi)有沖突，一個(gè)節(jié)點(diǎn)可以同時(shí)具有IS和IX鎖。IS只與X鎖沖突；IX則與S、X沖突。8.5基于優(yōu)化的并發(fā)控制8.5.1基于有效確認(rèn)的并發(fā)控制8.5.2基于時(shí)間戳的并發(fā)控制8.5.3三種并發(fā)機(jī)制比較基于封鎖的并發(fā)控制封鎖協(xié)議采用了一種悲觀保守的（pessimistic）方法來(lái)解決事務(wù)間沖突----使用中止或延遲事務(wù)封鎖請(qǐng)求的方式來(lái)解決沖突。.基于封鎖的并發(fā)控制采用了一種樂(lè)觀式(optimistic)假設(shè)性前提：認(rèn)為絕大部分事務(wù)相互之間并不會(huì)有沖突。在此基本前提下，采用“先放任事務(wù)執(zhí)行，出現(xiàn)問(wèn)題后再處理”的思想.8.5.1基于有效確認(rèn)的并發(fā)控制

有效確認(rèn)是一種基于優(yōu)化的并發(fā)控制，允許事務(wù)不經(jīng)過(guò)封鎖直接訪問(wèn)數(shù)據(jù)，并在“適當(dāng)?shù)臅r(shí)候”檢查事務(wù)是否以可串行化的方式運(yùn)轉(zhuǎn)。這個(gè)“適當(dāng)時(shí)候”主要指事務(wù)開(kāi)始寫DB對(duì)象之前的、一個(gè)稱被為“有效確認(rèn)”的、很短的瞬間階段。基于有效確認(rèn)的調(diào)度器數(shù)據(jù)結(jié)構(gòu)－－五個(gè)集合對(duì)每個(gè)事務(wù)：維護(hù)其讀對(duì)象集RS(Ti)、寫元素集WT(Ti)三個(gè)全局事務(wù)集:1)處于讀階段的事務(wù)集START；2)處于寫階段(已確認(rèn)但寫尚未完成)的事務(wù)集VAL；3)三個(gè)階段都已完成的事務(wù)集FIN；有效確認(rèn)規(guī)則

一個(gè)事務(wù)能否有效確認(rèn)主要取決于：事務(wù)基于時(shí)間戳的先后順序是否能等價(jià)于無(wú)沖突的串行順序。對(duì)于事務(wù)對(duì)集(Tj,Ti)Ti是在Tj確認(rèn)之前一個(gè)已確認(rèn)但仍活躍事務(wù)如果滿足以下兩個(gè)條件之一，則認(rèn)為Tj能被有效確認(rèn)。

(1)在Tj準(zhǔn)備確認(rèn)時(shí)，Ti所有三個(gè)階段已經(jīng)完成，且RT(Tj)∩WT(Ti)=?；(2)在Tj準(zhǔn)備確認(rèn)時(shí)，Ti已有效確認(rèn)但尚未完成。這時(shí)要求:RT(Tj)∩WT(Ti)=?∧WT(Tj)∩WT(Ti)=?。應(yīng)用舉例----例8.4

圖8.11中給出了四個(gè)事務(wù)T、U、V、W試圖執(zhí)行并確認(rèn)的時(shí)間點(diǎn)，每個(gè)事務(wù)的讀寫集已在圖中標(biāo)明。試分析它們是否能有效確認(rèn)。8.5.2基于時(shí)間戳的并發(fā)控制

在樂(lè)觀式的并發(fā)控制中，事務(wù)被施加了一個(gè)基于時(shí)間戳的順序，且要檢查所有沖突動(dòng)作是否能遵循該順序?；跁r(shí)間戳的并發(fā)控制，本質(zhì)上也是一種樂(lè)觀式的并發(fā)控制機(jī)制。基于時(shí)間戳并發(fā)控制器的數(shù)據(jù)結(jié)構(gòu)時(shí)間戳及其產(chǎn)生方法需要標(biāo)記時(shí)間戳的事件和動(dòng)作:對(duì)每個(gè)事務(wù)Ti，應(yīng)維護(hù)一個(gè)啟動(dòng)時(shí)的時(shí)間戳TS(Ti)。對(duì)每個(gè)DB對(duì)象O，應(yīng)維護(hù)：一個(gè)最近被讀的時(shí)間戳RT(O)；一個(gè)最近被寫的時(shí)間戳WT(O)；一個(gè)最近被寫的提交位C(O)。若最近寫事務(wù)提交，則C(O)=true；否則C(O)=false?；跁r(shí)間戳的并發(fā)控制原理

事務(wù)被施加了一個(gè)基于時(shí)間戳的順序，要求并發(fā)控制器檢查事務(wù)對(duì)每個(gè)DB對(duì)象的讀寫請(qǐng)求，看是否能遵循基于時(shí)間戳的串行順序。以上這個(gè)原則性要求，可具體表達(dá)為：對(duì)任兩事務(wù)Ti和Tj，若Ti先于Tj,即TS(Ti)<TS(Tj)，則必須確保在執(zhí)行期間，當(dāng)事務(wù)Ti的動(dòng)作ai與Tj的動(dòng)作aj沖突時(shí)，總有ai先于aj。如果有某個(gè)動(dòng)作違反了這個(gè)串行順序原則，則相關(guān)事務(wù)就必須被中止撤銷。違反了這個(gè)串行原則的幾種典型情況(圖8.12)

基于時(shí)間戳的算法應(yīng)用舉例

多版本時(shí)間戳并發(fā)控制

基本目標(biāo)：希望事務(wù)只讀DB元素時(shí)不需要等待。基本做法：是維護(hù)最近被修改對(duì)象的多個(gè)版本(每個(gè)版本都帶有一個(gè)寫時(shí)間戳)，當(dāng)讀事務(wù)T到來(lái)時(shí)，讓它讀TS(T)之前的最近版本。單版本時(shí)，會(huì)因“過(guò)晚讀”而回滾的讀事務(wù)，在多版本下，總能讀到適合它的版本值（符合“串行要求”），從而避免回滾。如果DB元素是頁(yè)，這種方法特別有用，因?yàn)檫@時(shí)所需做的只是讓緩沖區(qū)管理器保留一些對(duì)當(dāng)前活躍事務(wù)可能有用的頁(yè)。多版本時(shí)間戳并發(fā)控制

相比于單版本，多版本時(shí)間戳調(diào)度器，需要在以下幾個(gè)方面進(jìn)行增強(qiáng)管理：當(dāng)新的寫請(qǐng)求WT(X)合法時(shí)，DB對(duì)象的一個(gè)新版本被創(chuàng)建，其寫時(shí)間為t=TS(T)；寫時(shí)間與對(duì)象的版本有關(guān)，且永遠(yuǎn)不改變。當(dāng)新的讀請(qǐng)求RT(X)到來(lái)時(shí)，調(diào)度器找到不違反“過(guò)晚讀”的最新對(duì)象版本。當(dāng)某版本的寫時(shí)間t小于任何活躍事務(wù)的啟動(dòng)時(shí)間時(shí)，就可以刪除比t更早的所有其它版本。

三種并發(fā)機(jī)制比較

不推遲事務(wù)執(zhí)行的性能比較

封鎖法一般只推遲事務(wù)沒(méi)有回滾事務(wù)；但為處理死鎖，偶爾也會(huì)有回滾事務(wù)的情況。優(yōu)化法不推遲事務(wù)，但會(huì)導(dǎo)致事務(wù)回滾?；貪L是更嚴(yán)重的推遲形式，會(huì)造成較大的資源和已完成工作浪費(fèi)。在高沖突的競(jìng)用情況下，優(yōu)化方法的回滾會(huì)很頻繁，這時(shí)封鎖法往往性能更優(yōu)。當(dāng)