分布式系統(tǒng)與WEB服務(wù)(3)

1、南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 第五章第五章 分布式系統(tǒng)文件共享分布式系統(tǒng)文件共享 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5.1 5.1 共享文件的語(yǔ)義共享文件的語(yǔ)義 兩個(gè)以上的用戶共享同一個(gè)文件時(shí)，會(huì)產(chǎn)生多種情況，兩個(gè)以上的用戶共享同一個(gè)文件時(shí)，會(huì)產(chǎn)生多種情況， 從而產(chǎn)生不同的語(yǔ)義故文件服務(wù)時(shí)必須精確定義服務(wù)的讀從而產(chǎn)生不同的語(yǔ)義故文件服務(wù)時(shí)必須精確定義服務(wù)的讀 寫(xiě)語(yǔ)義。寫(xiě)語(yǔ)義。 一一.UNIX.UNIX語(yǔ)義語(yǔ)義( (時(shí)間順序時(shí)間順序) ) 對(duì)于單處理機(jī)而言，在對(duì)于單處理機(jī)而言，在UNIXU

2、NIX系統(tǒng)中，其讀操作的語(yǔ)義是，系統(tǒng)中，其讀操作的語(yǔ)義是， 讀取的結(jié)果是它前面最近一次寫(xiě)操作形成的結(jié)果。寫(xiě)操作的讀取的結(jié)果是它前面最近一次寫(xiě)操作形成的結(jié)果。寫(xiě)操作的 語(yǔ)義是，若先后連續(xù)有兩個(gè)寫(xiě)操作，則文件結(jié)果決定于后面語(yǔ)義是，若先后連續(xù)有兩個(gè)寫(xiě)操作，則文件結(jié)果決定于后面 的寫(xiě)操作。因此，的寫(xiě)操作。因此，最后形成的語(yǔ)義是嚴(yán)格意義下的時(shí)間序操最后形成的語(yǔ)義是嚴(yán)格意義下的時(shí)間序操 作。作。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 在對(duì)分布式文件系統(tǒng)中的文件進(jìn)行讀操作時(shí)，能看到在對(duì)分布式文件系統(tǒng)中的文件進(jìn)行讀操作時(shí)，能看到 以前所有對(duì)該文件執(zhí)行寫(xiě)操作的效果

3、。特別是，客戶對(duì)于以前所有對(duì)該文件執(zhí)行寫(xiě)操作的效果。特別是，客戶對(duì)于 已打開(kāi)文件的寫(xiě)操作可立即為其它打開(kāi)此文件的客戶所見(jiàn)。已打開(kāi)文件的寫(xiě)操作可立即為其它打開(kāi)此文件的客戶所見(jiàn)。 客戶可共享文件當(dāng)前位置的指針。這樣，一個(gè)客戶將指針客戶可共享文件當(dāng)前位置的指針。這樣，一個(gè)客戶將指針 向前推進(jìn)時(shí)將影響所有共享客戶的視圖。向前推進(jìn)時(shí)將影響所有共享客戶的視圖。 此種語(yǔ)義的特點(diǎn)是易于理解和實(shí)現(xiàn)。此種語(yǔ)義的特點(diǎn)是易于理解和實(shí)現(xiàn)。 二二. 會(huì)話語(yǔ)義會(huì)話語(yǔ)義 對(duì)于打開(kāi)文件的寫(xiě)操作可以立即為本地客戶所見(jiàn)，遠(yuǎn)程的對(duì)于打開(kāi)文件的寫(xiě)操作可以立即為本地客戶所見(jiàn)，遠(yuǎn)程的 客戶也同時(shí)打開(kāi)該文件，但卻不可見(jiàn)。客戶也同時(shí)打開(kāi)該文件

4、，但卻不可見(jiàn)。一旦文件關(guān)閉，對(duì)一旦文件關(guān)閉，對(duì) 此文件所作的修改僅為后面進(jìn)行的操作所見(jiàn)，該文件已經(jīng)此文件所作的修改僅為后面進(jìn)行的操作所見(jiàn)，該文件已經(jīng) 打開(kāi)的各副本不表現(xiàn)這些修改打開(kāi)的各副本不表現(xiàn)這些修改. . 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 三三. . 不可改變文件語(yǔ)義不可改變文件語(yǔ)義 一但文件為共享文件，則所有用戶均不能再修改它。這里的一但文件為共享文件，則所有用戶均不能再修改它。這里的 不可改變有兩個(gè)含義：一是其名字不可再變；二是其內(nèi)容不可不可改變有兩個(gè)含義：一是其名字不可再變；二是其內(nèi)容不可 改變。這樣，不可改變的文件的名字代表該文件

5、的固定內(nèi)容，改變。這樣，不可改變的文件的名字代表該文件的固定內(nèi)容， 而不再是信息存儲(chǔ)機(jī)制。而不再是信息存儲(chǔ)機(jī)制。這一語(yǔ)義非常簡(jiǎn)單，易于實(shí)現(xiàn)，但應(yīng)這一語(yǔ)義非常簡(jiǎn)單，易于實(shí)現(xiàn)，但應(yīng) 用起來(lái)，很不靈活用起來(lái)，很不靈活 四四. 事務(wù)語(yǔ)義事務(wù)語(yǔ)義 用戶若要訪問(wèn)一個(gè)文件或了組文件，用戶若要訪問(wèn)一個(gè)文件或了組文件，首先要執(zhí)行一個(gè)啟動(dòng)事首先要執(zhí)行一個(gè)啟動(dòng)事 務(wù)的操作務(wù)的操作,表示下面的操作必須獨(dú)立執(zhí)行，然后對(duì)文件進(jìn)行讀表示下面的操作必須獨(dú)立執(zhí)行，然后對(duì)文件進(jìn)行讀 寫(xiě)操作，當(dāng)工作完成后，再執(zhí)行一個(gè)結(jié)束事務(wù)的操作。寫(xiě)操作，當(dāng)工作完成后，再執(zhí)行一個(gè)結(jié)束事務(wù)的操作。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布

6、式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 其關(guān)鍵特性是其關(guān)鍵特性是, ,保證事務(wù)期間的所有文件操作按序執(zhí)保證事務(wù)期間的所有文件操作按序執(zhí) 行，而不受其它用戶的干擾，也就是說(shuō)，在事務(wù)內(nèi)部嚴(yán)行，而不受其它用戶的干擾，也就是說(shuō)，在事務(wù)內(nèi)部嚴(yán) 格具有格具有UNIXUNIX語(yǔ)義、顯然，語(yǔ)義、顯然，事務(wù)語(yǔ)義是一種比較實(shí)用的文事務(wù)語(yǔ)義是一種比較實(shí)用的文 件語(yǔ)義。件語(yǔ)義。事務(wù)的完成要求一個(gè)客戶機(jī)與一個(gè)或幾個(gè)服務(wù)事務(wù)的完成要求一個(gè)客戶機(jī)與一個(gè)或幾個(gè)服務(wù) 器進(jìn)行協(xié)作。器進(jìn)行協(xié)作。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5 52 2 原子事務(wù)原子事務(wù) 在分布式系統(tǒng)中，在分布

7、式系統(tǒng)中，原子事物又簡(jiǎn)稱(chēng)事物，原子事物又簡(jiǎn)稱(chēng)事物，事務(wù)實(shí)際上就事務(wù)實(shí)際上就 是一組邏輯上連續(xù)執(zhí)行的操作，其具有動(dòng)態(tài)性，有三種狀態(tài)：是一組邏輯上連續(xù)執(zhí)行的操作，其具有動(dòng)態(tài)性，有三種狀態(tài)： 提交提交 事務(wù)中的文件數(shù)據(jù)項(xiàng)的修改永久保存事務(wù)中的文件數(shù)據(jù)項(xiàng)的修改永久保存 中止中止 由于同其他事務(wù)沖突或硬件故障導(dǎo)致事務(wù)中止由于同其他事務(wù)沖突或硬件故障導(dǎo)致事務(wù)中止 臨時(shí)臨時(shí) 事務(wù)執(zhí)行中的存在的臨時(shí)狀態(tài)事務(wù)執(zhí)行中的存在的臨時(shí)狀態(tài) 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5.2.1 5.2.1 事務(wù)的特性事務(wù)的特性 事務(wù)具有以下四個(gè)特性事務(wù)具有以下四個(gè)特性, ,簡(jiǎn)稱(chēng)

8、簡(jiǎn)稱(chēng)ACIDACID特性特性 原子性原子性(Atomic):(Atomic):即事務(wù)的作用要么完整，要么沒(méi)有。即事務(wù)的作用要么完整，要么沒(méi)有。 一致性一致性( (Consistent)Consistent)：事務(wù)處理不影響系統(tǒng)中的不變性：意：事務(wù)處理不影響系統(tǒng)中的不變性：意 思是，當(dāng)系統(tǒng)具有某種不變特性需要保持時(shí)，在事務(wù)執(zhí)行前后思是，當(dāng)系統(tǒng)具有某種不變特性需要保持時(shí)，在事務(wù)執(zhí)行前后 該不變性一定要保持。例如，銀行業(yè)務(wù)系統(tǒng)中有一個(gè)關(guān)鍵的不該不變性一定要保持。例如，銀行業(yè)務(wù)系統(tǒng)中有一個(gè)關(guān)鍵的不 變特性是變特性是“金錢(qián)不滅金錢(qián)不滅”，經(jīng)過(guò)內(nèi)部任何轉(zhuǎn)帳之后，銀行的總錢(qián)，經(jīng)過(guò)內(nèi)部任何轉(zhuǎn)帳之后，銀行的總錢(qián)

9、 數(shù)是不變的。數(shù)是不變的。 孤立性孤立性(Isolated)(Isolated)：并發(fā)的事務(wù)不會(huì)相互影響，多個(gè)事務(wù)處：并發(fā)的事務(wù)不會(huì)相互影響，多個(gè)事務(wù)處 理可并發(fā)執(zhí)行，其結(jié)果和各事務(wù)處理串行執(zhí)行結(jié)果一樣，也叫理可并發(fā)執(zhí)行，其結(jié)果和各事務(wù)處理串行執(zhí)行結(jié)果一樣，也叫 串行等價(jià)性。串行等價(jià)性。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 三個(gè)事務(wù)三個(gè)事務(wù)A A、B B、C C被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行被三個(gè)獨(dú)立的進(jìn)程同時(shí)執(zhí)行, ,若順序執(zhí)行其結(jié)果為若順序執(zhí)行其結(jié)果為1 1、2 2或或 3 3 BEGIN_TRANSACTION A BEGIN_TRANSACT

10、ION B BEGIN_TRANSACTION C BEGIN_TRANSACTION A BEGIN_TRANSACTION B BEGIN_TRANSACTION C X=0; X=0; X=0; X=0; X=0; X=0; X=X+1; X=X+2; X=X+3; X=X+1; X=X+2; X=X+3; END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION END_TRANSACTION 時(shí)間時(shí)間 調(diào)度1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3;合法 調(diào)度2x=

11、0; x=0;x=x+1; x=x+2;x=0;x=x+3;合法 調(diào)度3x=0; x=0;x=x+1; x=0;x=x+2; x=x+3;不合法 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 持久性持久性(Durable)(Durable)：如果事務(wù)處理成功完成、則結(jié)果將永不：如果事務(wù)處理成功完成、則結(jié)果將永不 消失，除非發(fā)生硬故障。消失，除非發(fā)生硬故障。 5.2.2 5.2.2 事務(wù)需求事務(wù)需求 銀行基本業(yè)務(wù)服務(wù) 服務(wù)過(guò)程解釋 存款存款( (賬號(hào)，數(shù)額賬號(hào)，數(shù)額) )將指定數(shù)額數(shù)額的款項(xiàng)存入給定賬號(hào)賬號(hào) 取款取款( (賬號(hào)，數(shù)額賬號(hào)，數(shù)額) )從給定賬

12、號(hào)賬號(hào)取出指定數(shù)額數(shù)額的款項(xiàng) 平衡平衡( (賬號(hào)賬號(hào)) )返回給定賬號(hào)賬號(hào)的當(dāng)前平衡 總平衡總平衡()()返回該客戶所有賬號(hào)的總平衡 開(kāi)始事務(wù)處理開(kāi)始事務(wù)處理( (標(biāo)號(hào)標(biāo)號(hào)) )開(kāi)始指定標(biāo)號(hào)標(biāo)號(hào)的事務(wù)處理 結(jié)束事務(wù)處理結(jié)束事務(wù)處理( (標(biāo)號(hào)標(biāo)號(hào)) )結(jié)束指定標(biāo)號(hào)標(biāo)號(hào)的事務(wù)處理 流產(chǎn)事務(wù)處理流產(chǎn)事務(wù)處理( (標(biāo)號(hào)標(biāo)號(hào)) )迫使指定標(biāo)號(hào)標(biāo)號(hào)的事務(wù)處理流產(chǎn) 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 銀行服務(wù)的例子 開(kāi)始事務(wù)處理開(kāi)始事務(wù)處理(T) (T) ； K K：取款：取款(A(A，100) 100) ； K K：存款：存款(B(B，100) 100)

13、； K K：取款：取款(C(C，200) 200) ； K K：存款：存款(B(B，200) 200) ； 結(jié)束事務(wù)處理結(jié)束事務(wù)處理(T)(T) 我們將用T、U、V代表事務(wù)處理標(biāo)號(hào)，用K、M、N代表不同 的銀行分行，用A、B、C代表客戶的分行賬號(hào)，一個(gè)客戶發(fā) 出的一系列服務(wù)過(guò)程調(diào)用就可以合并為一次事務(wù)處理。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5 53 3 并發(fā)控制并發(fā)控制 并發(fā)控制的主要目標(biāo)是滿足事務(wù)處理的一致性并發(fā)控制的主要目標(biāo)是滿足事務(wù)處理的一致性( (串行等串行等 價(jià)性價(jià)性),),最早的方法最早的方法: : A. A.某一時(shí)刻只允許執(zhí)行

14、一個(gè)事務(wù)某一時(shí)刻只允許執(zhí)行一個(gè)事務(wù) B B 在啟動(dòng)多個(gè)事物操作之前先檢查是否滿足一致性在啟動(dòng)多個(gè)事物操作之前先檢查是否滿足一致性 缺點(diǎn)缺點(diǎn): : 解決的不好解決的不好. .為彌補(bǔ)不足為彌補(bǔ)不足. .提出提出下面三種方法下面三種方法. . 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5.3.15.3.1 加鎖加鎖 當(dāng)某一事務(wù)訪問(wèn)一共享數(shù)據(jù)項(xiàng)時(shí)，由服務(wù)器對(duì)該數(shù)據(jù)項(xiàng)加當(dāng)某一事務(wù)訪問(wèn)一共享數(shù)據(jù)項(xiàng)時(shí)，由服務(wù)器對(duì)該數(shù)據(jù)項(xiàng)加 鎖，當(dāng)完成訪問(wèn)時(shí)，再由服務(wù)器開(kāi)鎖，以便于其它事務(wù)訪問(wèn)。鎖，當(dāng)完成訪問(wèn)時(shí)，再由服務(wù)器開(kāi)鎖，以便于其它事務(wù)訪問(wèn)。 在上鎖期間，只有鎖定該數(shù)據(jù)項(xiàng)的事

15、務(wù)才能對(duì)其訪問(wèn)，這樣在上鎖期間，只有鎖定該數(shù)據(jù)項(xiàng)的事務(wù)才能對(duì)其訪問(wèn)，這樣 就保證了在某一時(shí)刻訪問(wèn)數(shù)據(jù)進(jìn)程的唯一性和確定性。就保證了在某一時(shí)刻訪問(wèn)數(shù)據(jù)進(jìn)程的唯一性和確定性。 一一. .基本原理基本原理 一個(gè)鎖可由三都分組成：一個(gè)鎖可由三都分組成： 一個(gè)二值邏輯變量，用以指示上鎖開(kāi)鎖；一個(gè)二值邏輯變量，用以指示上鎖開(kāi)鎖； 一個(gè)類(lèi)似于信號(hào)燈的條件變量；一個(gè)類(lèi)似于信號(hào)燈的條件變量； 訪問(wèn)該鎖的宿主事務(wù)標(biāo)識(shí)符訪問(wèn)該鎖的宿主事務(wù)標(biāo)識(shí)符 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 實(shí)現(xiàn)上鎖機(jī)制時(shí)，需要注意鎖的粒度。粒度是指被加鎖實(shí)現(xiàn)上鎖機(jī)制時(shí)，需要注意鎖的粒度。粒度

16、是指被加鎖 的數(shù)據(jù)項(xiàng)的大小，粒度越細(xì)，則并行度越高，反之，并行度的數(shù)據(jù)項(xiàng)的大小，粒度越細(xì)，則并行度越高，反之，并行度 越低。對(duì)整個(gè)文件加鎖是一種極端情況，這時(shí)候，事務(wù)串行越低。對(duì)整個(gè)文件加鎖是一種極端情況，這時(shí)候，事務(wù)串行 執(zhí)行。執(zhí)行。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項(xiàng)上。在下面的討論中，上鎖一般施加于文件中的數(shù)據(jù)項(xiàng)上。 鎖定機(jī)制是分兩個(gè)階段進(jìn)行的。鎖定機(jī)制是分兩個(gè)階段進(jìn)行的。一個(gè)事務(wù)在工作過(guò)程中，一個(gè)事務(wù)在工作過(guò)程中， 可分為可分為“生長(zhǎng)生長(zhǎng)”和和“消亡消亡”兩個(gè)階段。生長(zhǎng)階段需要上鎖，兩個(gè)階段。生長(zhǎng)階段需要上鎖， 消亡階段需要開(kāi)鎖，這就是兩階段鎖定機(jī)制。消亡階段需要開(kāi)鎖，這就是兩

17、階段鎖定機(jī)制。在生長(zhǎng)階段，在生長(zhǎng)階段， 事務(wù)處于臨時(shí)狀態(tài)，其臨時(shí)數(shù)據(jù)不為其它事務(wù)所見(jiàn)。在消亡事務(wù)處于臨時(shí)狀態(tài)，其臨時(shí)數(shù)據(jù)不為其它事務(wù)所見(jiàn)。在消亡 階段，臨時(shí)數(shù)據(jù)要變成永久數(shù)據(jù)，為了保持事務(wù)的特性，必階段，臨時(shí)數(shù)據(jù)要變成永久數(shù)據(jù)，為了保持事務(wù)的特性，必 須在事務(wù)關(guān)閉的最后，才能開(kāi)鎖。須在事務(wù)關(guān)閉的最后，才能開(kāi)鎖。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 二、幾種加鎖方案二、幾種加鎖方案 1 1最簡(jiǎn)單的加鎖方法最簡(jiǎn)單的加鎖方法 在這種方案中，文件服務(wù)器對(duì)客戶事務(wù)訪問(wèn)的每一個(gè)數(shù)在這種方案中，文件服務(wù)器對(duì)客戶事務(wù)訪問(wèn)的每一個(gè)數(shù) 據(jù)項(xiàng)加鎖，而在事務(wù)完成據(jù)項(xiàng)加

18、鎖，而在事務(wù)完成( (或中止或中止) )時(shí)打開(kāi)所有的鎖，當(dāng)另一時(shí)打開(kāi)所有的鎖，當(dāng)另一 事務(wù)試圖訪問(wèn)已上鎖的數(shù)據(jù)項(xiàng)時(shí)，它必須等待到開(kāi)鎖為止。事務(wù)試圖訪問(wèn)已上鎖的數(shù)據(jù)項(xiàng)時(shí)，它必須等待到開(kāi)鎖為止。 2. 2. 讀寫(xiě)鎖方案讀寫(xiě)鎖方案 由于簡(jiǎn)單鎖定機(jī)制不必要地將所有訪問(wèn)到的數(shù)據(jù)項(xiàng)鎖定，由于簡(jiǎn)單鎖定機(jī)制不必要地將所有訪問(wèn)到的數(shù)據(jù)項(xiàng)鎖定， 從而降低了事務(wù)的并發(fā)性。從而降低了事務(wù)的并發(fā)性。特別是當(dāng)事務(wù)中均是讀操作時(shí)，特別是當(dāng)事務(wù)中均是讀操作時(shí)， 便沒(méi)有必要上鎖便沒(méi)有必要上鎖。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 基于這種分析，基于這種分析，提出了讀寫(xiě)鎖方案，即

19、允許多個(gè)事務(wù)提出了讀寫(xiě)鎖方案，即允許多個(gè)事務(wù) 并發(fā)讀同一數(shù)據(jù)項(xiàng)，只允許一個(gè)事務(wù)寫(xiě)一個(gè)數(shù)據(jù)項(xiàng)。也稱(chēng)為并發(fā)讀同一數(shù)據(jù)項(xiàng)，只允許一個(gè)事務(wù)寫(xiě)一個(gè)數(shù)據(jù)項(xiàng)。也稱(chēng)為 “多讀單寫(xiě)多讀單寫(xiě)” 方法方法。在這種方法中，對(duì)于讀操作，還不。在這種方法中，對(duì)于讀操作，還不 能放棄上鎖，因?yàn)椴簧湘i，可能會(huì)有其它事務(wù)修改它，造成能放棄上鎖，因?yàn)椴簧湘i，可能會(huì)有其它事務(wù)修改它，造成 不一致。為此，不一致。為此，要采用兩種不同的鎖，即讀鎖和寫(xiě)鎖要采用兩種不同的鎖，即讀鎖和寫(xiě)鎖 對(duì)于對(duì)于 訪問(wèn)的所有數(shù)據(jù)項(xiàng)均可上讀鎖，只對(duì)寫(xiě)操作訪問(wèn)的數(shù)據(jù)項(xiàng)上訪問(wèn)的所有數(shù)據(jù)項(xiàng)均可上讀鎖，只對(duì)寫(xiě)操作訪問(wèn)的數(shù)據(jù)項(xiàng)上 寫(xiě)鎖。上寫(xiě)鎖的數(shù)據(jù)項(xiàng)不能被其它事務(wù)所

20、訪問(wèn)，上讀鎖的數(shù)寫(xiě)鎖。上寫(xiě)鎖的數(shù)據(jù)項(xiàng)不能被其它事務(wù)所訪問(wèn)，上讀鎖的數(shù) 據(jù)項(xiàng)只能為其它事務(wù)讀，但不能寫(xiě)據(jù)項(xiàng)只能為其它事務(wù)讀，但不能寫(xiě)。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 上鎖和開(kāi)鎖的基本規(guī)則如示上鎖和開(kāi)鎖的基本規(guī)則如示: : 1 1當(dāng)客戶在事務(wù)中訪問(wèn)數(shù)據(jù)項(xiàng)時(shí)，有如下情況當(dāng)客戶在事務(wù)中訪問(wèn)數(shù)據(jù)項(xiàng)時(shí)，有如下情況： 如果數(shù)據(jù)項(xiàng)還未上鎖，服務(wù)器將其鎖定，并讓客戶防問(wèn)如果數(shù)據(jù)項(xiàng)還未上鎖，服務(wù)器將其鎖定，并讓客戶防問(wèn) 該數(shù)據(jù)項(xiàng)；該數(shù)據(jù)項(xiàng)； 如果數(shù)據(jù)項(xiàng)已被其它事務(wù)上鎖，客戶必須等待該鎖打開(kāi)：如果數(shù)據(jù)項(xiàng)已被其它事務(wù)上鎖，客戶必須等待該鎖打開(kāi)： 如果服務(wù)器已經(jīng)鎖

21、定了本事務(wù)中的一個(gè)數(shù)據(jù)項(xiàng)，客戶可如果服務(wù)器已經(jīng)鎖定了本事務(wù)中的一個(gè)數(shù)據(jù)項(xiàng)，客戶可 以繼續(xù)防問(wèn)。以繼續(xù)防問(wèn)。 如果事務(wù)想要寫(xiě)自己已上有讀鎖的數(shù)據(jù)項(xiàng)，應(yīng)當(dāng)將讀鎖如果事務(wù)想要寫(xiě)自己已上有讀鎖的數(shù)據(jù)項(xiàng)，應(yīng)當(dāng)將讀鎖 改為寫(xiě)鎖。改為寫(xiě)鎖。 2.2.當(dāng)事務(wù)提交或中止時(shí)，服務(wù)器打開(kāi)它為該事務(wù)鎖定的所有數(shù)當(dāng)事務(wù)提交或中止時(shí)，服務(wù)器打開(kāi)它為該事務(wù)鎖定的所有數(shù) 據(jù)項(xiàng)。據(jù)項(xiàng)。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 3. 3.讀寫(xiě)鎖的死鎖問(wèn)題讀寫(xiě)鎖的死鎖問(wèn)題 以上兩種方法都在一定程度上提高了并發(fā)性，但與此同以上兩種方法都在一定程度上提高了并發(fā)性，但與此同 時(shí)也會(huì)帶來(lái)另一個(gè)

22、問(wèn)題時(shí)也會(huì)帶來(lái)另一個(gè)問(wèn)題死鎖。死鎖。所謂死鎖就是一組事務(wù)中所謂死鎖就是一組事務(wù)中 的每個(gè)操作都處于上鎖且又等待開(kāi)鎖的狀態(tài)的每個(gè)操作都處于上鎖且又等待開(kāi)鎖的狀態(tài)，例如以下兩個(gè)，例如以下兩個(gè) 事務(wù)事務(wù)U U和和T T，在時(shí)間順序上依次采取如下動(dòng)作，結(jié)果將導(dǎo)致死，在時(shí)間順序上依次采取如下動(dòng)作，結(jié)果將導(dǎo)致死 鎖。鎖。 T T等待事務(wù)等待事務(wù)U U釋放讀鎖釋放讀鎖b b，而它本身又對(duì)其加讀鎖引起事務(wù)，而它本身又對(duì)其加讀鎖引起事務(wù) U U對(duì)其解鎖的等待，由此，便導(dǎo)致了對(duì)其解鎖的等待，由此，便導(dǎo)致了互相牽制。互相牽制。 解決方法有如下解決方法有如下4 4種種 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分

23、布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 在事務(wù)開(kāi)始執(zhí)行前便對(duì)其所要訪問(wèn)的數(shù)據(jù)加鎖在事務(wù)開(kāi)始執(zhí)行前便對(duì)其所要訪問(wèn)的數(shù)據(jù)加鎖，這雖能預(yù)，這雖能預(yù) 防死鎖，但卻降低了資源共享率。防死鎖，但卻降低了資源共享率。 給資源規(guī)定一個(gè)序號(hào)給資源規(guī)定一個(gè)序號(hào)，申請(qǐng)資源時(shí)必須按序號(hào)單調(diào)遞增或，申請(qǐng)資源時(shí)必須按序號(hào)單調(diào)遞增或 遞減的方向申請(qǐng)，這種方法也降低了并行性。遞減的方向申請(qǐng)，這種方法也降低了并行性。 通過(guò)資源申請(qǐng)占有圖來(lái)檢測(cè)有無(wú)死鎖，一旦發(fā)現(xiàn)死鎖便由通過(guò)資源申請(qǐng)占有圖來(lái)檢測(cè)有無(wú)死鎖，一旦發(fā)現(xiàn)死鎖便由 服務(wù)器中止一個(gè)事務(wù)來(lái)打破循環(huán)占有等待服務(wù)器中止一個(gè)事務(wù)來(lái)打破循環(huán)占有等待，解決死鎖。，解決死鎖。 “時(shí)限時(shí)限”控

24、制，是文件系統(tǒng)中較常用的方法，即給控制，是文件系統(tǒng)中較常用的方法，即給每個(gè)鎖每個(gè)鎖 規(guī)定一個(gè)時(shí)間段。在此時(shí)段內(nèi)，該鎖是穩(wěn)定的，若超出此時(shí)限規(guī)定一個(gè)時(shí)間段。在此時(shí)段內(nèi)，該鎖是穩(wěn)定的，若超出此時(shí)限 后，該鎖便變成易損鎖，后，該鎖便變成易損鎖，若此時(shí)沒(méi)有別的事務(wù)對(duì)上鎖數(shù)據(jù)項(xiàng)競(jìng)?cè)舸藭r(shí)沒(méi)有別的事務(wù)對(duì)上鎖數(shù)據(jù)項(xiàng)競(jìng) 爭(zhēng)，則該鎖繼續(xù)保持；否則的話，便打破此鎖，與此同時(shí)，原爭(zhēng)，則該鎖繼續(xù)保持；否則的話，便打破此鎖，與此同時(shí)，原 上鎖事務(wù)中止。這種方法也有兩個(gè)不足，第一是增加了系統(tǒng)開(kāi)上鎖事務(wù)中止。這種方法也有兩個(gè)不足，第一是增加了系統(tǒng)開(kāi) 銷(xiāo)；第二是銷(xiāo)；第二是“時(shí)限時(shí)限”的取值問(wèn)題的取值問(wèn)題 南京理工大學(xué)計(jì)算機(jī)學(xué)院

25、南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 4 4意向?qū)戞i意向?qū)戞i 讀寫(xiě)鎖中讀鎖的存在阻止了其它事務(wù)對(duì)其進(jìn)行寫(xiě)操作，讀寫(xiě)鎖中讀鎖的存在阻止了其它事務(wù)對(duì)其進(jìn)行寫(xiě)操作， 在一定程度上降低了并發(fā)性。然而在一定程度上降低了并發(fā)性。然而事務(wù)的執(zhí)行要經(jīng)過(guò)兩個(gè)事務(wù)的執(zhí)行要經(jīng)過(guò)兩個(gè) 階段，在臨時(shí)階段，寫(xiě)操作實(shí)際上只是將改寫(xiě)的內(nèi)容寫(xiě)到階段，在臨時(shí)階段，寫(xiě)操作實(shí)際上只是將改寫(xiě)的內(nèi)容寫(xiě)到 一個(gè)臨時(shí)緩沖區(qū)中，并未改寫(xiě)實(shí)際的數(shù)據(jù)項(xiàng)。只有在提交一個(gè)臨時(shí)緩沖區(qū)中，并未改寫(xiě)實(shí)際的數(shù)據(jù)項(xiàng)。只有在提交 階段才寫(xiě)回?cái)?shù)據(jù)項(xiàng)，基于此原理可把讀寫(xiě)鎖改成意向?qū)戨A段才寫(xiě)回?cái)?shù)據(jù)項(xiàng)，基于此原理可把讀寫(xiě)鎖改成意向?qū)?鎖和提交鎖

26、來(lái)提高并發(fā)性鎖和提交鎖來(lái)提高并發(fā)性. . 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5.3.2 5.3.2 樂(lè)觀的并發(fā)控制方法樂(lè)觀的并發(fā)控制方法 一一. .問(wèn)題的提出問(wèn)題的提出 使用鎖機(jī)制處理并發(fā)控制時(shí)存在一些缺陷：使用鎖機(jī)制處理并發(fā)控制時(shí)存在一些缺陷： 分布式系統(tǒng)中的鎖機(jī)制是一種額外的開(kāi)銷(xiāo)。分布式系統(tǒng)中的鎖機(jī)制是一種額外的開(kāi)銷(xiāo)。例如，在只例如，在只 有讀操作的事務(wù)中，鎖可以保證所讀的數(shù)據(jù)項(xiàng)不被別的事務(wù)有讀操作的事務(wù)中，鎖可以保證所讀的數(shù)據(jù)項(xiàng)不被別的事務(wù) 修改，但這種鎖只有在最壞的情況下才有必要。又例如，兩修改，但這種鎖只有在最壞的情況下才有必要。又

27、例如，兩 個(gè)客戶進(jìn)程并發(fā)地對(duì)個(gè)客戶進(jìn)程并發(fā)地對(duì)n n個(gè)數(shù)據(jù)項(xiàng)進(jìn)行增值運(yùn)算，若它們同時(shí)啟個(gè)數(shù)據(jù)項(xiàng)進(jìn)行增值運(yùn)算，若它們同時(shí)啟 動(dòng)，執(zhí)行時(shí)間量也相同，以互不相關(guān)的序列訪問(wèn)數(shù)據(jù)項(xiàng)，并動(dòng)，執(zhí)行時(shí)間量也相同，以互不相關(guān)的序列訪問(wèn)數(shù)據(jù)項(xiàng)，并 且各自使用一個(gè)事務(wù)來(lái)訪問(wèn)和增值數(shù)據(jù)項(xiàng)，則這兩個(gè)程序試且各自使用一個(gè)事務(wù)來(lái)訪問(wèn)和增值數(shù)據(jù)項(xiàng)，則這兩個(gè)程序試 圖同時(shí)訪問(wèn)同一數(shù)據(jù)項(xiàng)的機(jī)會(huì)僅有圖同時(shí)訪問(wèn)同一數(shù)據(jù)項(xiàng)的機(jī)會(huì)僅有1 1n n，也即每，也即每n n個(gè)事務(wù)中實(shí)個(gè)事務(wù)中實(shí) 際有用的鎖只有一次。際有用的鎖只有一次。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 使用鎖機(jī)制會(huì)導(dǎo)致死鎖，

28、并且沒(méi)有令人滿意的死鎖使用鎖機(jī)制會(huì)導(dǎo)致死鎖，并且沒(méi)有令人滿意的死鎖 解決算法解決算法。在鎖機(jī)制中，只有在一個(gè)事務(wù)終止時(shí)才釋放它。在鎖機(jī)制中，只有在一個(gè)事務(wù)終止時(shí)才釋放它 的所有鎖，這明顯有損于并發(fā)性。正是基于以上原因，有的所有鎖，這明顯有損于并發(fā)性。正是基于以上原因，有 人提出另一種算法人提出另一種算法樂(lè)觀的并發(fā)控制方法樂(lè)觀的并發(fā)控制方法。之所以稱(chēng)其。之所以稱(chēng)其 為為“樂(lè)觀樂(lè)觀”，是基于這樣一種假設(shè)，是基于這樣一種假設(shè)，兩個(gè)客戶的事務(wù)同時(shí)兩個(gè)客戶的事務(wù)同時(shí) 訪問(wèn)某一數(shù)據(jù)的可能性很小訪問(wèn)某一數(shù)據(jù)的可能性很小, , 因此兩個(gè)事務(wù)可以執(zhí)行下去，因此兩個(gè)事務(wù)可以執(zhí)行下去， 直至發(fā)出直至發(fā)出C1oseT

29、ransactionC1oseTransaction請(qǐng)求。當(dāng)產(chǎn)生沖突時(shí)，一般要請(qǐng)求。當(dāng)產(chǎn)生沖突時(shí)，一般要 中止一些事務(wù)，并由客戶重新啟動(dòng)。這樣，每個(gè)事務(wù)便分中止一些事務(wù)，并由客戶重新啟動(dòng)。這樣，每個(gè)事務(wù)便分 為以下三個(gè)階段：為以下三個(gè)階段： 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 1.1.讀階段：讀階段：在這一階段中，每個(gè)事務(wù)有一個(gè)待更新數(shù)據(jù)的臨在這一階段中，每個(gè)事務(wù)有一個(gè)待更新數(shù)據(jù)的臨 時(shí)版本時(shí)版本。讀請(qǐng)求可以立即執(zhí)行讀請(qǐng)求可以立即執(zhí)行，如果有臨時(shí)版本存在，則要，如果有臨時(shí)版本存在，則要 訪問(wèn)最近提交的數(shù)據(jù)值。訪問(wèn)最近提交的數(shù)據(jù)值。而寫(xiě)請(qǐng)求以一種

30、其它事務(wù)不可見(jiàn)的而寫(xiě)請(qǐng)求以一種其它事務(wù)不可見(jiàn)的 形式緩存起來(lái)，形式緩存起來(lái)，若有幾個(gè)并發(fā)事務(wù)，可能會(huì)同時(shí)存在同一數(shù)若有幾個(gè)并發(fā)事務(wù)，可能會(huì)同時(shí)存在同一數(shù) 據(jù)項(xiàng)的幾個(gè)不同的臨時(shí)值。另外，據(jù)項(xiàng)的幾個(gè)不同的臨時(shí)值。另外，針對(duì)于每一個(gè)事務(wù)需要設(shè)針對(duì)于每一個(gè)事務(wù)需要設(shè) 置兩個(gè)集合：讀集合和寫(xiě)集合，讀集合列出事務(wù)所讀的數(shù)據(jù)置兩個(gè)集合：讀集合和寫(xiě)集合，讀集合列出事務(wù)所讀的數(shù)據(jù) 項(xiàng)的集合，而寫(xiě)集合則列出事務(wù)創(chuàng)建、修改、刪除的數(shù)據(jù)項(xiàng)項(xiàng)的集合，而寫(xiě)集合則列出事務(wù)創(chuàng)建、修改、刪除的數(shù)據(jù)項(xiàng) 集合。集合。 2.2.確認(rèn)階段：確認(rèn)階段：當(dāng)服務(wù)器收到當(dāng)服務(wù)器收到CloseTransactionCloseTransactio

31、n請(qǐng)求之后，請(qǐng)求之后， 進(jìn)入這個(gè)階段進(jìn)入這個(gè)階段，在該階段中，在該階段中，對(duì)該事務(wù)進(jìn)行確認(rèn)是否可以將對(duì)該事務(wù)進(jìn)行確認(rèn)是否可以將 該事務(wù)的寫(xiě)操作結(jié)果永久保存下來(lái)。該事務(wù)的寫(xiě)操作結(jié)果永久保存下來(lái)。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 如果事務(wù)確認(rèn)成功，則進(jìn)入寫(xiě)階段如果事務(wù)確認(rèn)成功，則進(jìn)入寫(xiě)階段( (寫(xiě)操作結(jié)果記錄到相寫(xiě)操作結(jié)果記錄到相 關(guān)文件中，事務(wù)成功完成，關(guān)文件中，事務(wù)成功完成，發(fā)出發(fā)出commit);commit);否則，要解決沖突，否則，要解決沖突， 需要中止某些事務(wù)。需要中止某些事務(wù)。確認(rèn)階段是建立在一致性基礎(chǔ)上的確認(rèn)階段是建立在一致性基

32、礎(chǔ)上的，即，即 如果事務(wù)執(zhí)行的結(jié)果等價(jià)于各個(gè)事務(wù)順序執(zhí)行的結(jié)果，則該如果事務(wù)執(zhí)行的結(jié)果等價(jià)于各個(gè)事務(wù)順序執(zhí)行的結(jié)果，則該 事務(wù)視為確認(rèn)成功。事務(wù)視為確認(rèn)成功。 3.3.寫(xiě)階段：寫(xiě)階段：如果一個(gè)事務(wù)確認(rèn)成功，則臨時(shí)版本記錄的如果一個(gè)事務(wù)確認(rèn)成功，則臨時(shí)版本記錄的 所有修改均可以變?yōu)橛谰眯孕薷摹Ｋ行薷木梢宰優(yōu)橛谰眯孕薷?。只讀事務(wù)可以在確認(rèn)通過(guò)只讀事務(wù)可以在確認(rèn)通過(guò) 后立即提交。寫(xiě)事務(wù)在臨時(shí)版本中的數(shù)據(jù)變?yōu)橛谰脭?shù)據(jù)之后后立即提交。寫(xiě)事務(wù)在臨時(shí)版本中的數(shù)據(jù)變?yōu)橛谰脭?shù)據(jù)之后 立即提交。立即提交。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 二、二、事務(wù)的確認(rèn)

33、事務(wù)的確認(rèn) 確認(rèn)是利用讀寫(xiě)沖突規(guī)則來(lái)保證一組重疊事務(wù)確認(rèn)是利用讀寫(xiě)沖突規(guī)則來(lái)保證一組重疊事務(wù)( (即當(dāng)前事務(wù)即當(dāng)前事務(wù) 還未提交便已開(kāi)始的事務(wù)還未提交便已開(kāi)始的事務(wù)) )的調(diào)度符合一致性的調(diào)度符合一致性, , 當(dāng)一個(gè)事務(wù)完當(dāng)一個(gè)事務(wù)完 成第一階段工作后成第一階段工作后, ,為其指定一個(gè)事務(wù)號(hào)，若該事務(wù)確認(rèn)成功為其指定一個(gè)事務(wù)號(hào)，若該事務(wù)確認(rèn)成功 完成完成, ,則事務(wù)號(hào)被保留下來(lái)：否則，若事務(wù)未被確認(rèn)，或事務(wù)則事務(wù)號(hào)被保留下來(lái)：否則，若事務(wù)未被確認(rèn)，或事務(wù) 是只讀事務(wù)，則釋放該事務(wù)號(hào)是只讀事務(wù)，則釋放該事務(wù)號(hào) 確認(rèn)工作主要基于兩個(gè)事務(wù)操作的沖突來(lái)完成的確認(rèn)工作主要基于兩個(gè)事務(wù)操作的沖突來(lái)完成的

34、對(duì)于對(duì)于 兩個(gè)重疊事務(wù)兩個(gè)重疊事務(wù)TiTi和和TJTJ，必須滿足下列規(guī)則必須滿足下列規(guī)則。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 確認(rèn)方法有兩種，確認(rèn)方法有兩種，一種叫做向后確認(rèn)一種叫做向后確認(rèn)(Backward (Backward Validation)Validation)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查已經(jīng)進(jìn)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查已經(jīng)進(jìn) 入 確 認(rèn) 階 段 的 事 務(wù) 。入 確 認(rèn) 階 段 的 事 務(wù) 。 一 種 叫 做 向 前 確 認(rèn)一 種 叫 做 向 前 確 認(rèn) ( ( F o r w a r d F o r w a r

35、d Validation)Validation)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查后續(xù)進(jìn)，以正在執(zhí)行確認(rèn)的事務(wù)為基準(zhǔn)，檢查后續(xù)進(jìn) 人確認(rèn)階段的事務(wù)人確認(rèn)階段的事務(wù). . 三三. . 餓死現(xiàn)象餓死現(xiàn)象 事務(wù)中止后事務(wù)中止后, , 通常由客戶程序重新啟動(dòng)通常由客戶程序重新啟動(dòng), , 但有可能該事但有可能該事 務(wù)仍然無(wú)法通過(guò)確認(rèn)務(wù)仍然無(wú)法通過(guò)確認(rèn), , 于是其又被中止于是其又被中止, , 重啟重啟, , 再中止再中止. . 如此如此, , 該事務(wù)則被剝奪了提交能力該事務(wù)則被剝奪了提交能力 此現(xiàn)象即為餓死此現(xiàn)象即為餓死 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服

36、務(wù) 5.3.3 5.3.3 時(shí)間戳?xí)r間戳 要利用時(shí)間戳完成并發(fā)控制，要利用時(shí)間戳完成并發(fā)控制，需要對(duì)每個(gè)事務(wù)的操作進(jìn)行需要對(duì)每個(gè)事務(wù)的操作進(jìn)行 有效性檢查，若檢查未能通過(guò)有效性檢查，若檢查未能通過(guò), ,則該事務(wù)立即中止并重新啟動(dòng)則該事務(wù)立即中止并重新啟動(dòng) 基本的時(shí)間規(guī)則基本的時(shí)間規(guī)則: : 事務(wù)對(duì)數(shù)據(jù)項(xiàng)的寫(xiě)請(qǐng)求，僅當(dāng)該數(shù)據(jù)項(xiàng)最近由前一個(gè)事事務(wù)對(duì)數(shù)據(jù)項(xiàng)的寫(xiě)請(qǐng)求，僅當(dāng)該數(shù)據(jù)項(xiàng)最近由前一個(gè)事 務(wù)務(wù)( (有沖突有沖突) )讀和寫(xiě)，才能有效。讀和寫(xiě)，才能有效。 事務(wù)對(duì)數(shù)據(jù)項(xiàng)的讀請(qǐng)求，僅當(dāng)該數(shù)據(jù)項(xiàng)剛剛由前一個(gè)事事務(wù)對(duì)數(shù)據(jù)項(xiàng)的讀請(qǐng)求，僅當(dāng)該數(shù)據(jù)項(xiàng)剛剛由前一個(gè)事 務(wù)務(wù)( (有沖突有沖突) )寫(xiě)，才能有效。寫(xiě)，

37、才能有效。 該規(guī)則允許并發(fā)事務(wù)共享臨時(shí)數(shù)據(jù)項(xiàng)，從而確保每個(gè)數(shù)據(jù)該規(guī)則允許并發(fā)事務(wù)共享臨時(shí)數(shù)據(jù)項(xiàng)，從而確保每個(gè)數(shù)據(jù) 項(xiàng)的臨時(shí)值按時(shí)間戳順序提交項(xiàng)的臨時(shí)值按時(shí)間戳順序提交. . 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5 54 4 恢復(fù)恢復(fù) 事務(wù)的原子性要求事務(wù)要么提供完整的運(yùn)行結(jié)果，要么么作事務(wù)的原子性要求事務(wù)要么提供完整的運(yùn)行結(jié)果，要么么作 用都沒(méi)有，即持久性和失效原子性。這兩個(gè)需要并不是獨(dú)立的，用都沒(méi)有，即持久性和失效原子性。這兩個(gè)需要并不是獨(dú)立的， 可以由服務(wù)器上的獨(dú)立機(jī)制來(lái)管理，我們稱(chēng)這個(gè)機(jī)制叫做恢復(fù)管可以由服務(wù)器上的獨(dú)立機(jī)制來(lái)管理，我們稱(chēng)這

38、個(gè)機(jī)制叫做恢復(fù)管 理器。理器。 恢復(fù)管理器的主要任務(wù)是；恢復(fù)管理器的主要任務(wù)是； 將提交事務(wù)的數(shù)據(jù)保存到永久性存儲(chǔ)介質(zhì)將提交事務(wù)的數(shù)據(jù)保存到永久性存儲(chǔ)介質(zhì)( (恢復(fù)文件恢復(fù)文件) )上；上； 故障重啟后，恢復(fù)服務(wù)器的數(shù)據(jù)；故障重啟后，恢復(fù)服務(wù)器的數(shù)據(jù)； 組織恢復(fù)文件，改進(jìn)恢復(fù)性能；組織恢復(fù)文件，改進(jìn)恢復(fù)性能； 回收恢復(fù)文件涉及到的空間?；厥栈謴?fù)文件涉及到的空間。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5 55 5 事務(wù)服務(wù)中的文件版本事務(wù)服務(wù)中的文件版本 5.5.15.5.1 文件版本的實(shí)現(xiàn)文件版本的實(shí)現(xiàn) 通過(guò)在每個(gè)文件的索引表中擴(kuò)充一項(xiàng)通過(guò)在每

39、個(gè)文件的索引表中擴(kuò)充一項(xiàng), ,即版本號(hào)即版本號(hào), ,通過(guò)對(duì)通過(guò)對(duì) 影子頁(yè)的操作影子頁(yè)的操作, ,到事務(wù)提交時(shí)到事務(wù)提交時(shí), ,若無(wú)版本沖突若無(wú)版本沖突, ,則合并臨時(shí)版則合并臨時(shí)版 本與當(dāng)前版本得到最新版本本與當(dāng)前版本得到最新版本. .若有沖突則放棄臨時(shí)版本若有沖突則放棄臨時(shí)版本. . 5.5.2 5.5.2 意向表的實(shí)現(xiàn)意向表的實(shí)現(xiàn) 也可通過(guò)對(duì)影子頁(yè)的操作實(shí)現(xiàn)意向表也可通過(guò)對(duì)影子頁(yè)的操作實(shí)現(xiàn)意向表, , 意向表記錄意向表記錄: :操作類(lèi)型、事務(wù)標(biāo)識(shí)符、文件標(biāo)識(shí)符、頁(yè)號(hào)、操作類(lèi)型、事務(wù)標(biāo)識(shí)符、文件標(biāo)識(shí)符、頁(yè)號(hào)、 影子頁(yè)面的指針影子頁(yè)面的指針 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式

40、系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 文件版本方法文件版本方法 解決兩類(lèi)問(wèn)題解決兩類(lèi)問(wèn)題: :版本沖突和串行沖突版本沖突和串行沖突 版本沖突版本沖突: :并發(fā)事務(wù)訪問(wèn)同一個(gè)文件的不同數(shù)據(jù)段并發(fā)事務(wù)訪問(wèn)同一個(gè)文件的不同數(shù)據(jù)段, ,從而產(chǎn)從而產(chǎn) 生不同的版本生不同的版本, ,但無(wú)一版本包含所有的修改但無(wú)一版本包含所有的修改. . 串行沖突串行沖突: :并發(fā)事務(wù)訪問(wèn)同一數(shù)據(jù)段并發(fā)事務(wù)訪問(wèn)同一數(shù)據(jù)段, ,從而有多個(gè)寫(xiě)操作從而有多個(gè)寫(xiě)操作, , 導(dǎo)致數(shù)據(jù)項(xiàng)決定于最后的版本導(dǎo)致數(shù)據(jù)項(xiàng)決定于最后的版本. . 版本沖突解決如圖版本沖突解決如圖: : 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式

41、系統(tǒng)與WEB服務(wù)服務(wù) 老版本老版本老版本老版本 當(dāng)前版本當(dāng)前版本合并最新版本合并最新版本 事務(wù)事務(wù)T的臨時(shí)版的臨時(shí)版 本本 事務(wù)事務(wù)U的臨時(shí)版的臨時(shí)版 本本 版本的合并版本的合并 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 老版本老版本老版本老版本 上一個(gè)版本上一個(gè)版本當(dāng)前版本當(dāng)前版本 事務(wù)事務(wù)T的臨時(shí)版的臨時(shí)版 本本 事務(wù)事務(wù)U的臨時(shí)版的臨時(shí)版 本本 串行沖突的解決串行沖突的解決 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 意向表方法意向表方法 意向表實(shí)際上是一個(gè)事務(wù)操作的日志記錄意向表實(shí)際上是一個(gè)事務(wù)操作的

42、日志記錄, ,是兩階段提交是兩階段提交 的機(jī)制的機(jī)制. .即即: :第一階段第一階段, ,事務(wù)處于臨時(shí)狀態(tài)事務(wù)處于臨時(shí)狀態(tài), ,第二階段第二階段, ,事務(wù)進(jìn)入事務(wù)進(jìn)入 提交階段提交階段. .如圖如圖 DATADATA為服務(wù)器為待修改的數(shù)據(jù)的臨時(shí)拷貝為服務(wù)器為待修改的數(shù)據(jù)的臨時(shí)拷貝. .意向操作只是意向操作只是 記錄到意向表并不是真的對(duì)文件操作記錄到意向表并不是真的對(duì)文件操作, ,一個(gè)意向只有給出足夠一個(gè)意向只有給出足夠 的信息的信息, ,才能到第二階段執(zhí)行才能到第二階段執(zhí)行. . 本事務(wù)的視圖本事務(wù)的視圖 DATA1DATA1DATA2DATA2 其它事務(wù)的視圖其它事務(wù)的視圖 南京理工大學(xué)計(jì)算

43、機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 第六章第六章 分布事務(wù)與文件備份分布事務(wù)與文件備份 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 6 61 1 合作服務(wù)器合作服務(wù)器 合作服務(wù)器是由多個(gè)物理服務(wù)器合作完成一個(gè)邏輯服合作服務(wù)器是由多個(gè)物理服務(wù)器合作完成一個(gè)邏輯服 務(wù)器的功能務(wù)器的功能, ,各個(gè)服務(wù)器由網(wǎng)絡(luò)互連各個(gè)服務(wù)器由網(wǎng)絡(luò)互連, ,每個(gè)服務(wù)器可具備不每個(gè)服務(wù)器可具備不 同性能同性能, ,可位于不同地點(diǎn)可位于不同地點(diǎn), , 并持有整個(gè)合作服務(wù)器中所有文并持有整個(gè)合作服務(wù)器中所有文 件的一部分件的一部分 南京理工大學(xué)計(jì)算機(jī)

44、學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 6 62 2 分布事務(wù)分布事務(wù) 分布事務(wù)是指一個(gè)事務(wù)將涉及到多個(gè)服務(wù)器的操作分布事務(wù)是指一個(gè)事務(wù)將涉及到多個(gè)服務(wù)器的操作, , 即即 該事務(wù)是由合作服務(wù)器完成的該事務(wù)是由合作服務(wù)器完成的, , 構(gòu)造分布事務(wù)的方法有簡(jiǎn)構(gòu)造分布事務(wù)的方法有簡(jiǎn) 單分布事務(wù)和嵌套分布事務(wù)兩種單分布事務(wù)和嵌套分布事務(wù)兩種 簡(jiǎn)單分布事務(wù)簡(jiǎn)單分布事務(wù): :客戶機(jī)可以多次訪問(wèn)不同的服務(wù)器客戶機(jī)可以多次訪問(wèn)不同的服務(wù)器, ,服務(wù)服務(wù) 器僅響應(yīng)客戶機(jī)的請(qǐng)求器僅響應(yīng)客戶機(jī)的請(qǐng)求, ,不引發(fā)其它服務(wù)器的操作不引發(fā)其它服務(wù)器的操作 嵌套分布事務(wù)嵌套分布事務(wù): :一個(gè)服

45、務(wù)器上的操作可能引發(fā)其它服務(wù)一個(gè)服務(wù)器上的操作可能引發(fā)其它服務(wù) 器操作器操作 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 客戶機(jī) 服務(wù)器1 服務(wù)器2 服務(wù)器3 在分布事務(wù)中在分布事務(wù)中, ,多個(gè)服務(wù)器需要相互通信和合作多個(gè)服務(wù)器需要相互通信和合作, ,各自完各自完 成部分工作成部分工作, ,最終是事務(wù)提交完成最終是事務(wù)提交完成. .在分布事務(wù)處理中在分布事務(wù)處理中, ,第一個(gè)第一個(gè) 響應(yīng)客戶機(jī)請(qǐng)求的服務(wù)器為該事務(wù)的協(xié)調(diào)服務(wù)器響應(yīng)客戶機(jī)請(qǐng)求的服務(wù)器為該事務(wù)的協(xié)調(diào)服務(wù)器, ,負(fù)責(zé)中止、負(fù)責(zé)中止、 提交該事務(wù)，其后加入的服務(wù)器為工作服務(wù)器。提交該事務(wù)，其后加

46、入的服務(wù)器為工作服務(wù)器。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) T S 1 T22 T21 T12 T11 T2 T1 T S 3 S 2 S 2 S 6 S 5 S 4 S 1 S 3 (a)分布式平面事務(wù)處理 (b)分布式嵌套事務(wù)處理 S 7 S 0 事務(wù)處理分類(lèi) 其中方框代表事務(wù)處理，圓形代表執(zhí)行操作的服務(wù)器 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式事務(wù)處理 n分布式事務(wù)處理的關(guān)鍵在于服務(wù)及數(shù)據(jù)的分布，即 一個(gè)事務(wù)處理所需的服務(wù)與數(shù)據(jù)可能分散在不同的 服務(wù)器上，因此，事務(wù)處理過(guò)程就必須在多

47、臺(tái)服務(wù) 器上執(zhí)行。 n分布式事務(wù)處理的調(diào)度與同步 -多臺(tái)服務(wù)器聯(lián)合執(zhí)行一個(gè)事務(wù)處理時(shí)需要彼此協(xié) 調(diào)，才能做到整個(gè)事務(wù)處理的成功提交 -常用的方法是由一個(gè)協(xié)調(diào)者(coordinator)通過(guò) 服務(wù)器之間的通信來(lái)實(shí)現(xiàn)最終提交 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式事務(wù)處理例子 開(kāi)始事務(wù)處理(T) ； K：取款(A，100) ； M：存款(B，100) ； N：取款(D，200) ； M：存款(C，200) ； 結(jié)束事務(wù)處理(T) 某客戶要在K、M、N三個(gè)銀行分行的A、B、C、D四個(gè)賬號(hào)上執(zhí)行轉(zhuǎn)帳業(yè) 務(wù)，即從K分行的A賬號(hào)取出100元，存入M分行

48、的B賬號(hào)去，然后從N分 行的D賬號(hào)取出200元并存入到M分行的C賬號(hào)。假定這三個(gè)分行的數(shù)據(jù) 庫(kù)分別位于三臺(tái)服務(wù)器上，其中S1管理K分行的A賬號(hào) ，S2管理M分行的 B、C兩個(gè)賬號(hào)，S3管理N分行的D賬號(hào) 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式銀行事務(wù)處理 T S 1 S 3 S 2 (1.1) 開(kāi)始事務(wù)處理(T) ； (1.2) K：取款(A，100) ； (1.3) 結(jié)束事務(wù)處理(T) ； (2.1) 加入服務(wù)器(T，S1) ； (2.2) M：存款(B，100) ； (2.3) M：存款(C，200) ； (3.1) 加入服務(wù)器(T，S

49、1) ； (3.2) N：取款(D，200) ； K分行 M分行 N分行 協(xié)調(diào)者協(xié)調(diào)者 參與者參與者 參與者參與者 由于每個(gè)服務(wù)器可能同時(shí)執(zhí)行不同的分布式事務(wù)處理，因此 在整個(gè)系統(tǒng)中事務(wù)處理標(biāo)號(hào)必須是唯一的。首先啟動(dòng)分布式 事務(wù)處理的那臺(tái)服務(wù)器是整個(gè)事務(wù)處理的協(xié)調(diào)者服務(wù)器 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 6 63 3 分布事務(wù)的提交協(xié)議分布事務(wù)的提交協(xié)議 最簡(jiǎn)單的方法最簡(jiǎn)單的方法: : 1 1一階段原子提交協(xié)議一階段原子提交協(xié)議: : 即由協(xié)調(diào)服務(wù)器不斷查詢所有工作服務(wù)器即由協(xié)調(diào)服務(wù)器不斷查詢所有工作服務(wù)器, ,直到所有工直到所有工 作服務(wù)

50、器都回答提交成功作服務(wù)器都回答提交成功, ,完成整個(gè)事務(wù)提交完成整個(gè)事務(wù)提交 2 2兩階段提交協(xié)議兩階段提交協(xié)議(2PC(2PC協(xié)議協(xié)議) )，可以保證分布事務(wù)的原子，可以保證分布事務(wù)的原子 性，在此協(xié)議中，任何服務(wù)器都可以隨時(shí)中止自己的子事性，在此協(xié)議中，任何服務(wù)器都可以隨時(shí)中止自己的子事 務(wù)而不影響客戶機(jī)事務(wù)的正常提交或中止。務(wù)而不影響客戶機(jī)事務(wù)的正常提交或中止。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 協(xié)調(diào)服務(wù)器分為兩階段工作協(xié)調(diào)服務(wù)器分為兩階段工作(2PC)(2PC)： 第一階段第一階段 投票階段投票階段 A A協(xié)調(diào)服務(wù)器向每個(gè)工作服務(wù)期發(fā)

51、出提交請(qǐng)求協(xié)調(diào)服務(wù)器向每個(gè)工作服務(wù)期發(fā)出提交請(qǐng)求 B B工作服務(wù)器收到請(qǐng)求后工作服務(wù)器收到請(qǐng)求后, ,回答回答YESYES或或NO,NO,如回答有如回答有NO,NO,則終止則終止 第二階段第二階段 完成階段完成階段 C C協(xié)調(diào)服務(wù)器查看搜集的票數(shù)協(xié)調(diào)服務(wù)器查看搜集的票數(shù), ,若無(wú)反對(duì)票若無(wú)反對(duì)票, ,協(xié)調(diào)服務(wù)器則提協(xié)調(diào)服務(wù)器則提 交該事務(wù)并通知所有工作服務(wù)器交該事務(wù)并通知所有工作服務(wù)器, ,否則否則, ,若有反對(duì)票協(xié)調(diào)服務(wù)若有反對(duì)票協(xié)調(diào)服務(wù) 器則終止事務(wù)器則終止事務(wù), ,并向所有回答并向所有回答YESYES的工作服務(wù)器發(fā)出終止請(qǐng)求的工作服務(wù)器發(fā)出終止請(qǐng)求 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算

52、機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 3 3 嵌套事務(wù)的兩階段提交協(xié)議嵌套事務(wù)的兩階段提交協(xié)議 嵌套事務(wù)的兩階段提交協(xié)議的執(zhí)行過(guò)程的第一階段與非嵌套事務(wù)的兩階段提交協(xié)議的執(zhí)行過(guò)程的第一階段與非 嵌套事務(wù)不同，當(dāng)工作服務(wù)器接到提交：嵌套事務(wù)不同，當(dāng)工作服務(wù)器接到提交： 1)1)如果工作服務(wù)器具有暫時(shí)提交且是頂層事務(wù)的子事務(wù)如果工作服務(wù)器具有暫時(shí)提交且是頂層事務(wù)的子事務(wù) A.A.檢查它有沒(méi)有前輩事務(wù)處于中止事務(wù)表中，準(zhǔn)備提交檢查它有沒(méi)有前輩事務(wù)處于中止事務(wù)表中，準(zhǔn)備提交 B B 中止具有中止前輩事務(wù)的事務(wù)中止具有中止前輩事務(wù)的事務(wù) C C 向協(xié)調(diào)服務(wù)器投票向協(xié)調(diào)服務(wù)器投票YESYES 南

53、京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 2)2)如果工作服務(wù)器沒(méi)有處于暫時(shí)提交狀態(tài)的、且是頂層如果工作服務(wù)器沒(méi)有處于暫時(shí)提交狀態(tài)的、且是頂層 事務(wù)的子事務(wù)，它肯定已經(jīng)失敗，應(yīng)向協(xié)調(diào)服務(wù)器投票事務(wù)的子事務(wù)，它肯定已經(jīng)失敗，應(yīng)向協(xié)調(diào)服務(wù)器投票NONO 注意注意: : A.A.子事務(wù)的標(biāo)識(shí)符可以通過(guò)擴(kuò)充其父事務(wù)的標(biāo)識(shí)符子事務(wù)的標(biāo)識(shí)符可以通過(guò)擴(kuò)充其父事務(wù)的標(biāo)識(shí)符; ; B. B.子事務(wù)的提交決定于其父事務(wù)的提交子事務(wù)的提交決定于其父事務(wù)的提交, ,但父事務(wù)的提但父事務(wù)的提 交并不決定于其子事務(wù)的提交交并不決定于其子事務(wù)的提交 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大

54、學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 6 64 4 分布事務(wù)中的并發(fā)控制分布事務(wù)中的并發(fā)控制 當(dāng)多個(gè)事務(wù)處理訪問(wèn)同一個(gè)數(shù)據(jù)時(shí)，順序等價(jià)性要求必須把每一個(gè)事當(dāng)多個(gè)事務(wù)處理訪問(wèn)同一個(gè)數(shù)據(jù)時(shí)，順序等價(jià)性要求必須把每一個(gè)事 務(wù)處理對(duì)該數(shù)據(jù)的完整務(wù)處理對(duì)該數(shù)據(jù)的完整( (讀讀/ /寫(xiě)寫(xiě)) )訪問(wèn)一一排序，嚴(yán)格禁止任何沖突訪問(wèn)一一排序，嚴(yán)格禁止任何沖突 開(kāi)始事務(wù)處理(T) ： K：取款(A， 40) ； K：存入(B， 40) ； 結(jié)束事務(wù)處理(T) ； 開(kāi)始事務(wù)處理(U) ： K：取款(C， 30) K：存款(B， 30) 結(jié)束事務(wù)處理(U) ； 分解操作分解操作平衡平衡分解操作分解操作

55、平衡平衡 A平衡 A讀出()(A) 100元 A寫(xiě)入(A平衡 40)(A) 60元 C平衡 C讀出()(C) 300元 C寫(xiě)入(C平衡 30)(C) 270元 B平衡 B讀出()(B) 200元 B寫(xiě)入(B平衡 + 40)(B) 240元 B平衡 B讀出()(B) 240元 B寫(xiě)入(B平衡 + 30)(B) 270元 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 1. 1. 分布事務(wù)中的鎖分布事務(wù)中的鎖 每個(gè)服務(wù)器都要提供鎖管理機(jī)制，本地的鎖管理機(jī)制可每個(gè)服務(wù)器都要提供鎖管理機(jī)制，本地的鎖管理機(jī)制可 以決定是否接受事務(wù)的請(qǐng)求操作。以決定是否接受事務(wù)的請(qǐng)求

56、操作。 利用互斥鎖進(jìn)行事務(wù)處理并發(fā)控制 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 開(kāi)始事務(wù)處理(T) ： K：取款(A， 40) ； K：存款(B， 40) ； 結(jié)束事務(wù)處理(T) ； 分解操作分解操作互斥鎖互斥鎖分解操作分解操作互斥鎖互斥鎖 開(kāi)始事務(wù)處理(T) 開(kāi)始事務(wù)處理(U) A平衡 A讀出()鎖定AC平衡 C讀出()鎖定C A寫(xiě)入(A平衡 40) C寫(xiě)入(C平衡 30) B平衡 B讀出()鎖定B B平衡 B讀出()等待B的鎖 B寫(xiě)入(B平衡 + 40) 結(jié)束事務(wù)處理(T)釋放A，B 鎖定B B寫(xiě)入(B平衡 + 30) 結(jié)束事務(wù)處理(U)釋放B

57、，C 開(kāi)始事務(wù)處理(U) ： K：取款(C， 30) K：存款(B， 30) 結(jié)束事務(wù)處理(U) ； 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式死鎖分布式死鎖 n在各種涉及互斥的算法中，只要算法采用互斥鎖，就有在各種涉及互斥的算法中，只要算法采用互斥鎖，就有 可能發(fā)生可能發(fā)生“死鎖死鎖” 現(xiàn)象?，F(xiàn)象。 n死鎖的典型特征是一組事務(wù)處理形成了一條循環(huán)等待鏈 n死鎖處理： -置之不理 （鴕鳥(niǎo)算法（鴕鳥(niǎo)算法） 由程序員對(duì)其負(fù)責(zé) -預(yù)防（靜態(tài)的使死鎖在結(jié)構(gòu)上不可能）（靜態(tài)的使死鎖在結(jié)構(gòu)上不可能） 不存在運(yùn)行系統(tǒng)支持 -避免 （合理的分配資源）（合理的分配

58、資源） 運(yùn)行系統(tǒng)支持 -檢測(cè)恢復(fù)（允許死鎖發(fā)生，檢測(cè)到后恢復(fù)）（允許死鎖發(fā)生，檢測(cè)到后恢復(fù)） 不同的算法 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) T UV W W U T V (a) 簡(jiǎn)單循環(huán)鏈簡(jiǎn)單循環(huán)鏈(b) 復(fù)雜循環(huán)鏈復(fù)雜循環(huán)鏈 n互斥 n持有并等待(a) TUVWT n不容搶占(b) VWTV n循環(huán)鏈 VWV 死鎖 - 循環(huán)等待鏈 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式事務(wù)處理的死鎖例子 事務(wù)處理U事務(wù)處理V事務(wù)處理W 存款(D，100)鎖定D S3 存款(B，300)鎖定B S2 存款

59、(A，200)鎖定A S1 存款(C，500)鎖定C S3 取款(B，200)等待B S2 取款(C，100)等待C S3 取款(A，300)等待A S1 死鎖 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 死鎖檢測(cè)死鎖檢測(cè) n死鎖是一種穩(wěn)定的狀態(tài) n盡管無(wú)法從局部狀態(tài)檢測(cè)分布式事務(wù)處理 的死鎖，但死鎖依舊是環(huán)形等待鏈。 n死鎖檢測(cè)算法： -中央式 周期性地收集等待狀態(tài) -分布式 推出等待狀態(tài) -提示式 構(gòu)造檢測(cè)體系 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 2. 2. 分布事務(wù)中的時(shí)間戳分布事務(wù)中的時(shí)間戳 利

60、用時(shí)間戳進(jìn)行讀寫(xiě)協(xié)作利用時(shí)間戳進(jìn)行讀寫(xiě)協(xié)作 3. 3. 分布事務(wù)中的樂(lè)觀并發(fā)控制分布事務(wù)中的樂(lè)觀并發(fā)控制 分布事務(wù)通過(guò)一組獨(dú)立的服務(wù)器進(jìn)行確定，每個(gè)服務(wù)器分布事務(wù)通過(guò)一組獨(dú)立的服務(wù)器進(jìn)行確定，每個(gè)服務(wù)器 都要確認(rèn)事務(wù)訪問(wèn)的是自己的數(shù)據(jù)項(xiàng)，所有確認(rèn)均通過(guò)兩階都要確認(rèn)事務(wù)訪問(wèn)的是自己的數(shù)據(jù)項(xiàng)，所有確認(rèn)均通過(guò)兩階 段進(jìn)行。段進(jìn)行。 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院 分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) n讀階段讀階段 在讀階段，該事務(wù)處理所訪問(wèn)的數(shù)據(jù)都有一套暫時(shí)版本，這套版 本不對(duì)外，只由擁有者使用。采用暫時(shí)版本可以使事務(wù)處理流產(chǎn)而不會(huì)影 響到長(zhǎng)存數(shù)據(jù)。當(dāng)執(zhí)行一個(gè)讀操作時(shí)，如果數(shù)據(jù)的暫