第三章分布式系統(tǒng)的同步

第3章分布式系統(tǒng)的同步

時(shí)鐘同步互斥選舉算法原子事務(wù)

分布式系統(tǒng)中的死鎖3.1

時(shí)鐘同步分布式算法的性質(zhì)相關(guān)信息分散在多臺機(jī)器上進(jìn)程決策僅僅依賴于本地信息系統(tǒng)中單點(diǎn)故障應(yīng)避免沒有公用時(shí)鐘和其他精確的全局時(shí)間資源存在21442145214621472142214321442145進(jìn)行編譯的計(jì)算機(jī)進(jìn)行編譯的計(jì)算機(jī)創(chuàng)建output.o創(chuàng)建output.c根據(jù)本地時(shí)鐘的時(shí)間根據(jù)本地時(shí)鐘的時(shí)間時(shí)間當(dāng)每臺機(jī)器都有自己的時(shí)鐘，一個(gè)發(fā)生于另一個(gè)事件之后的事件可能會標(biāo)記一個(gè)比另一個(gè)事件更早的時(shí)間3.1

時(shí)鐘同步3.1.1邏輯時(shí)鐘

計(jì)算機(jī)計(jì)時(shí)方法

?

計(jì)算機(jī)上的計(jì)時(shí)器通常由一個(gè)精確的石英晶體制成，它以一定的頻率震蕩。

?

每次震蕩計(jì)數(shù)器減1，當(dāng)計(jì)數(shù)器減為0時(shí)，產(chǎn)生一次中斷（時(shí)鐘點(diǎn)）。

?

在多CPU系統(tǒng)中，不同計(jì)算機(jī)上的晶體以不同的頻率震蕩，導(dǎo)致時(shí)鐘不同步。（時(shí)鐘偏移）

問題：同步所有時(shí)鐘產(chǎn)生一個(gè)單一的、無二義的時(shí)間標(biāo)準(zhǔn)可能嗎？

——Lamport：時(shí)鐘同步是可能的！??！

?

如果兩個(gè)進(jìn)程無相互作用，它們的時(shí)鐘無需同步。?時(shí)鐘同步不需要絕對同步，不需所有進(jìn)程在時(shí)間上完全一致，而是它們在事件發(fā)生的順序上要完全一致。?只關(guān)心事件發(fā)生的順序，而不關(guān)心是否與真實(shí)時(shí)間接近。（邏輯時(shí)鐘）3.1

時(shí)鐘同步3.1.1邏輯時(shí)鐘

先發(fā)生關(guān)系

?

a發(fā)生在b之前，記為：a→b。存在兩種情況：

?

如果a和b是同一進(jìn)程中兩個(gè)事件，且a發(fā)生在b之前，則a→b為真；

?

如果a是一個(gè)進(jìn)程發(fā)送消息的事件，b為另一個(gè)進(jìn)程接收這一消息的事件，則a→b為真；?性質(zhì)：

?

先發(fā)生關(guān)系具有傳遞性：若a→b且b→c，則a→c。

并發(fā)事件

如果兩個(gè)事件x和y，出現(xiàn)在不同的進(jìn)程中，但并不交換消息，則x→y為假，y→x也為假。則事件x和y稱為并發(fā)事件。3.1

時(shí)鐘同步3.1.1邏輯時(shí)鐘

Lamport算法

06121824303642485460081624324048566472800102030405060708090100ABCD

對于對每一事件a，給它分配一個(gè)時(shí)間值C(a)。這些時(shí)間值具有下列性質(zhì)：若a→b，則c(a)<c(b)。此外，時(shí)鐘時(shí)間值C必須遞增，不能倒退。

例子：三個(gè)進(jìn)程，每個(gè)均有自己的時(shí)鐘，每個(gè)時(shí)鐘速率不同。進(jìn)程0進(jìn)程1進(jìn)程23.1

時(shí)鐘同步3.1.1邏輯時(shí)鐘Lamport算法

06121824303642487076081624324048616977850102030405060708090100ABCD

Lamport解決方案直接使用先發(fā)生關(guān)系，每條消息攜帶發(fā)送者的時(shí)鐘以指出其發(fā)送的時(shí)刻，當(dāng)消息到達(dá)時(shí)，接收者時(shí)鐘若比消息發(fā)送時(shí)鐘小，就立即將自己的時(shí)鐘調(diào)到比發(fā)送時(shí)間大1或更多的值。

Lamport解決方案：調(diào)整C到達(dá)的時(shí)間為５６-61，D到達(dá)的時(shí)間為５４-70進(jìn)程0進(jìn)程1進(jìn)程23.1

時(shí)鐘同步3.1.1邏輯時(shí)鐘

Lamport算法補(bǔ)充說明?在每兩個(gè)事件之間，時(shí)鐘必須至少滴答一下。如果一個(gè)進(jìn)程以相當(dāng)快的速度連續(xù)發(fā)送或接收兩條消息，它必須在這中間至少嘀嗒一下。

?附加條件：兩個(gè)事件不會精確的同時(shí)發(fā)生。如果進(jìn)程1和進(jìn)程2同時(shí)發(fā)生了2個(gè)事件，發(fā)生時(shí)刻都是40，則前者記為40.1，后者為40.2。

lamport算法遵循的規(guī)則：?若在同一進(jìn)程中a發(fā)生在b之前，則C（a）<C（b）;?若a和b分別代表發(fā)送消息和接收消息，則C（a）<C（b）；?對所有的a和b，C（a）≠C（b）。3.1

時(shí)鐘同步

3.1.2物理時(shí)鐘

物理時(shí)鐘：UTC（統(tǒng)一協(xié)調(diào)時(shí)間），它是所有現(xiàn)代人使用的時(shí)間。地球軌道在n天以后的中天點(diǎn)地球已經(jīng)旋轉(zhuǎn)了將近３６０度到銀河系的距離到銀河系的距離地球第n天到達(dá)中天地球第０天到達(dá)中天中天點(diǎn)：太陽到達(dá)一天的最高點(diǎn)3.1

時(shí)鐘同步

3.1.3時(shí)鐘同步算法dC/dt<1UTC，t時(shí)鐘時(shí)間C稍慢時(shí)鐘最佳時(shí)鐘稍快時(shí)鐘dC/dt=1dC/dt>11-ρ≤dC/dt≤1+ρ

若保證兩個(gè)時(shí)鐘之間的差不超過δ，時(shí)鐘至少在每δ/2ρ秒內(nèi)再同步一次。（ρ為最大漂移速度）圖3-5不是所有的時(shí)鐘都按正確的速率中斷3.1

時(shí)鐘同步

3.1.3時(shí)鐘同步算法Cristian’s算法發(fā)送機(jī)器

T0

時(shí)間T1I，中斷處理時(shí)間請求CUTC時(shí)間服務(wù)器T0和T1都是由相同時(shí)鐘測量的

適合于只有一臺機(jī)器上有WWV接收器

（時(shí)間服務(wù)器），其它所有機(jī)器與它同步的系統(tǒng)。

說明：每臺機(jī)器以小于或等于δ/2ρ秒的周期定期地向時(shí)間服務(wù)器發(fā)送消息詢問當(dāng)前的時(shí)間，時(shí)間服務(wù)器接到消息后就盡快回答含有當(dāng)前時(shí)間CUTC值的消息。3.1

時(shí)鐘同步

3.1.3時(shí)鐘同步算法Cristian’s算法

問題1：發(fā)送者如何根據(jù)時(shí)間服務(wù)器的返回值調(diào)整時(shí)間？由于時(shí)間不能倒退，因此一種方法是根據(jù)時(shí)鐘快慢，中斷服務(wù)程序調(diào)整（增大或減?。┟看沃袛嗨拥臅r(shí)間值。

問題2：如何處理從時(shí)間服務(wù)器發(fā)送的應(yīng)答到發(fā)送者存在的延遲？精確記錄從向時(shí)間服務(wù)器發(fā)送請求的起始時(shí)間于時(shí)間T0和接收到應(yīng)答的結(jié)束時(shí)間T1。

當(dāng)前服務(wù)器時(shí)間估計(jì)值=CUTC+（T1-T0）/2

如果考慮服務(wù)器中斷處理的時(shí)間I，那么傳輸?shù)臅r(shí)間間隔為T1-T0-I，單向傳輸時(shí)間為它的一半。3.1

時(shí)鐘同步3.1.3時(shí)鐘同步算法Berkeley算法

3:003:003:003:003:252:50+153:00+5-203:053:05-103:000+253:252:50

時(shí)間守護(hù)進(jìn)程（時(shí)間服務(wù)器）定期地詢問每臺機(jī)器的時(shí)間。然后基于這些回答計(jì)算出平均值并告訴所有的機(jī)器將它們的時(shí)鐘撥快或撥慢到一個(gè)新的值。（適合于沒有WWV接收器的系統(tǒng)）時(shí)間守護(hù)進(jìn)程詢問其它機(jī)器的時(shí)間值機(jī)器應(yīng)答時(shí)間守護(hù)進(jìn)程通知每個(gè)機(jī)器如何調(diào)整時(shí)間3.1

時(shí)鐘同步3.1.3時(shí)鐘同步算法平均值算法將時(shí)間分成固定長度的再同步間隔，第i次間隔開始于T0+iR，結(jié)束于T0+(i+1)R.T0是過去某一約定的時(shí)間，R是一個(gè)系統(tǒng)參數(shù)。在每次間隔開始處，每臺機(jī)器根據(jù)自己的時(shí)鐘廣播發(fā)送當(dāng)前的時(shí)間。

在機(jī)器廣播發(fā)送時(shí)間之后，它啟動本地計(jì)時(shí)器收集在S時(shí)間間隔中到達(dá)的其他廣播。當(dāng)所有廣播到達(dá)后，執(zhí)行一個(gè)算法，得到新的時(shí)間值。這個(gè)算法可以是求這些值得平均值，或者是去掉m個(gè)最大值和m個(gè)最小值，平均其余值。3.1

時(shí)鐘同步3.1.4使用時(shí)鐘同步至多一次消息傳遞

每臺機(jī)器上保存一個(gè)全局變量G，任何比G早的時(shí)間戳都能安全地從表中移走。

G=當(dāng)前時(shí)間-最大生存時(shí)間-最大時(shí)鐘偏移

G是所有老消息的消息數(shù)目的梗概。每隔一定時(shí)間△T，將當(dāng)前的時(shí)間寫入磁盤。當(dāng)服務(wù)器重啟時(shí)，從磁盤上重新裝載G，再加上△T?；跁r(shí)鐘的緩沖存儲器的一致性

3.2

互斥3.2.1集中式算法優(yōu)點(diǎn)：容易實(shí)現(xiàn)、需要交互的消息少（請求、允許、釋放）。缺點(diǎn)：單點(diǎn)故障、瓶頸、無法辨認(rèn)服務(wù)器崩潰。012C請求OK協(xié)調(diào)者空隊(duì)列012C請求無應(yīng)答協(xié)調(diào)者2OK012C釋放協(xié)調(diào)者算法思想：選一個(gè)進(jìn)程作為協(xié)調(diào)者，進(jìn)程若要進(jìn)入臨界區(qū)，它向協(xié)調(diào)者發(fā)送請求消息，協(xié)調(diào)者負(fù)責(zé)處理。圖3-8集中式算法3.2

互斥3.2.2分布式算法Ricart和Agrawale算法要求系統(tǒng)中所有的事件都是全序的。即對于任何事件組（如消息），哪個(gè)先發(fā)生，哪個(gè)后發(fā)生必須無歧異。算法如下：當(dāng)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)，它要建立一個(gè)包括它要進(jìn)入的臨界區(qū)的名字、處理機(jī)號和當(dāng)前時(shí)間的消息，然后將消息發(fā)給所有其他進(jìn)程。（也包括發(fā)送給它自身）當(dāng)一個(gè)進(jìn)程接收到另一個(gè)進(jìn)程請求消息時(shí)，它取決于接收方的狀態(tài)以及臨界區(qū)的命名。有三種情況要加以區(qū)別。①若接收者不在臨界區(qū)中，也不想進(jìn)入臨界區(qū)，它就向發(fā)送者發(fā)送OK消息。3.2

互斥3.2.2分布式算法Ricart和Agrawale算法②若接收者已經(jīng)在臨界區(qū)中，它就不必回答，而是負(fù)責(zé)對請求隊(duì)列排隊(duì)。③若接收者要進(jìn)入臨界區(qū)，但是還沒有進(jìn)入時(shí)，它要將發(fā)來的消息和它發(fā)送給其余進(jìn)程的時(shí)間戳對比，取小的那個(gè)。如果來得消息時(shí)間戳小，接收者發(fā)送OK消息。如果接收者本身的時(shí)間戳小，那么接收者負(fù)責(zé)排列請求隊(duì)列而不發(fā)送任何消息。在發(fā)送完允許進(jìn)入臨界區(qū)的請求后，進(jìn)程將不做任何事，僅等待所有的允許消息，一旦得到允許，它就進(jìn)入臨界區(qū)。從臨界區(qū)退出時(shí)，向隊(duì)列中所有進(jìn)程發(fā)送OK消息，并將它從隊(duì)列中刪除。3.2

互斥3.2.2分布式算法Ricart和Agrawale算法012888121212012OKOKOK012OK圖3-9(a)兩個(gè)進(jìn)程在同一時(shí)刻進(jìn)入同一個(gè)臨界區(qū)

(b)進(jìn)程0的時(shí)間戳小，所以它獲勝

(c)當(dāng)進(jìn)程0完成時(shí)，它發(fā)送消息OK，進(jìn)程2現(xiàn)在可進(jìn)入臨界區(qū)3.2

互斥3.2.2分布式算法Ricart和Agrawale算法每次進(jìn)入臨界區(qū)需要2(n-1)條消息，n為系統(tǒng)中進(jìn)程數(shù)。如何解決多點(diǎn)失效當(dāng)請求到達(dá)時(shí)，不管是許可還是拒絕，都要發(fā)送應(yīng)答。一旦請求或應(yīng)答丟失，發(fā)送者的等待時(shí)間到，它繼續(xù)發(fā)送直到得到應(yīng)答或者認(rèn)為目的進(jìn)程已經(jīng)崩潰為止。使用組通信原語算法改進(jìn)當(dāng)一個(gè)進(jìn)程從大多數(shù)進(jìn)程哪里獲得允許而并不需要所有進(jìn)程都允許時(shí)就可以進(jìn)入臨界區(qū)。3.2

互斥3.2.3令牌環(huán)算法0249716583進(jìn)程網(wǎng)絡(luò)2345678901令牌持有者可能進(jìn)入臨界區(qū)或?qū)⒘钆仆聜鬟f用軟件的方法構(gòu)造出一個(gè)邏輯環(huán)，環(huán)中每個(gè)進(jìn)程都有一個(gè)位置，每個(gè)進(jìn)程都知道誰在自己的下一個(gè)位置。優(yōu)點(diǎn)：消息比分布式算法少。缺點(diǎn)：令牌丟失、進(jìn)程崩潰。

圖3-10(a)網(wǎng)絡(luò)中一組未排序的進(jìn)程

(b)用軟件構(gòu)造進(jìn)程的邏輯環(huán)3.2

互斥3.2.4三種算法的比較算法每次進(jìn)出需要的消息進(jìn)入前的延遲（按消息次數(shù)）問題集中式32協(xié)調(diào)者崩潰分布式2(n-1)2(n-1)任何一個(gè)進(jìn)程崩潰令牌環(huán)1到無窮大0到n-1丟失令牌，進(jìn)程崩潰集中式、分布式和令牌環(huán)三種算法的性質(zhì)的比較：進(jìn)程進(jìn)入或退出臨界區(qū)需要的消息數(shù)目，每次進(jìn)入前的延遲以及一些與算法有關(guān)的問題。表3-1三種互斥算法比較3.3

選舉算法3.3.1欺負(fù)(bully)算法假設(shè)每個(gè)進(jìn)程有一個(gè)特殊的號碼，通常選舉算法總是找擁有最大號碼的進(jìn)程。欺負(fù)算法：當(dāng)一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再相應(yīng)請求時(shí)，它發(fā)起選舉。進(jìn)程P選舉過程如下：P向所有號碼比它大的進(jìn)程發(fā)送選舉(Election)消息若無人響應(yīng)，P獲勝成為協(xié)調(diào)者。若有號碼比它大的進(jìn)程響應(yīng)，響應(yīng)者接管，P的工作完成。由于最大的進(jìn)程總能取勝，因而將該算法命名為欺負(fù)算法。3.3

選舉算法3.3.1欺負(fù)(bully)算法42156037選舉選舉選舉42156037OKOK以前的協(xié)調(diào)者崩潰42156037選舉選舉選舉42156037OK42156037協(xié)調(diào)者協(xié)調(diào)者（a）（b）（c）（d）（e）3.3

選舉算法3.3.2環(huán)算法10765560565234223選舉過程

?

發(fā)起者沿環(huán)發(fā)送選舉消息，若某點(diǎn)失效則繞過。

?每次發(fā)送者都將自己的進(jìn)程號加入到消息中。

?最后，消息到達(dá)始發(fā)者手中，沿環(huán)發(fā)送協(xié)調(diào)者消息。3.4

原子事務(wù)3.4.1原子事務(wù)簡介兩個(gè)例子老式磁帶銀行轉(zhuǎn)帳

（1）提?。ń痤~，賬戶1）（2）存入（金額，賬戶2）計(jì)算機(jī)輸入磁帶今天的更新以前的庫存新的庫存輸出磁帶3.4

原子事務(wù)3.4.2事務(wù)模型穩(wěn)定存儲器不受洪水地震之類大災(zāi)難之外的任何其他錯(cuò)誤的影響，可以通過兩個(gè)磁盤實(shí)現(xiàn)。適合于需高度容錯(cuò)的應(yīng)用，例如事務(wù)。sahfwbtosahfwbtosa1hfwbtosahfwbtosahfwbtosafwbto錯(cuò)誤的校驗(yàn)和驅(qū)動器1驅(qū)動器2(a)(b)(c)3.4

原子事務(wù)3.4.2事務(wù)模型事務(wù)原語BEGIN_TRANSACTION:標(biāo)記一個(gè)事務(wù)的開始；END_TRANSACTION:結(jié)束事務(wù)并設(shè)法提交；ABORT_TRANSACTION;取消事務(wù)；恢復(fù)舊值；READ：從一個(gè)文件（或其他對象）讀取數(shù)據(jù)；WRITE：將數(shù)據(jù)寫入一個(gè)文件（或其他對象）。事務(wù)體在BEGIN_TRANSACTION和END_TRANSACTION之間的操作構(gòu)成了事務(wù)體。這些操作要么全部執(zhí)行，要么一個(gè)也不執(zhí)行。3.4

原子事務(wù)3.4.2事務(wù)模型事務(wù)原語例子（航空訂票系統(tǒng)）BEGIN_TRANSACTIONreserveA_BreserveB_CreserveC_DEND_TRANSACTIONBEGIN_TRANSACTIONreserveA_BreserveB_CC_DfullABORT_TRANSACTION(a)預(yù)定三個(gè)航班機(jī)票的事務(wù)(b)當(dāng)?shù)谌齻€(gè)航班的機(jī)票預(yù)定失敗后事務(wù)中止預(yù)定一張從A到D的機(jī)票：3.4

原子事務(wù)3.4.2事務(wù)模型事務(wù)的特性（ACID）原子性（Atomic）

對外部世界來說，事務(wù)的發(fā)生是不可分割的。確保了每個(gè)事務(wù)要么全部發(fā)生，要么全部發(fā)生。一致性（Consistent）

事務(wù)不會破壞系統(tǒng)的恒定。意味著如果系統(tǒng)擁有某種必須經(jīng)常保持的不變性，那么一旦事務(wù)開始之前保持有這樣的性質(zhì)，則事務(wù)結(jié)束后該性質(zhì)應(yīng)還該存在。3.4

原子事務(wù)3.4.2事務(wù)模型事務(wù)的特性（ACID）獨(dú)立性（Isolated）

并發(fā)的事務(wù)不會相互干擾。這個(gè)特性說明事務(wù)是獨(dú)立的或連續(xù)的。BEGIN_TRANSACTIONx=0;x=x+1;END_TRANSACTIONBEGIN_TRANSACTIONx=0;x=+2;END_TRANSACTIONBEGIN_TRANSACTIONx=0;x=x+3;END_TRANSACTION調(diào)度1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3合法調(diào)度2x=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不合法3.4

原子事務(wù)3.4.2事務(wù)模型事務(wù)的特性（ACID）持久性（Durable）

一旦一個(gè)事務(wù)提交，改變就是永遠(yuǎn)存在的。提交之后發(fā)生的任何錯(cuò)誤都不可能使結(jié)果取消或丟失。嵌套事務(wù)嵌套事務(wù)

事務(wù)可以包含子事務(wù)，通常稱作嵌套事務(wù)。頂層事務(wù)可以在不同的處理機(jī)上創(chuàng)建并行運(yùn)行子事務(wù)，以提高性能簡化編程。3.4

原子事務(wù)3.4.3實(shí)現(xiàn)私有工作空間在進(jìn)程開始一個(gè)事務(wù)時(shí)給它分配一個(gè)包含了所有需要訪問的文件的私有工作空間，在事務(wù)提交或中止前所有的讀寫操作都是在私有工作空間而不是在真正的文件系統(tǒng)中進(jìn)行的。問題：所有內(nèi)容拷貝到私有工作空間，代價(jià)難以承受。兩種優(yōu)化方法：

私有工作空間中只包含一個(gè)指向父輩工作區(qū)的指針。當(dāng)事務(wù)處于最頂層時(shí)，它的工作區(qū)是真正的文件系統(tǒng)。使用索引節(jié)點(diǎn)。索引是一個(gè)與判斷文件所在磁盤塊位置有關(guān)的數(shù)據(jù)塊。該方法不將全部文件拷入私有工作空間，而只是將其索引拷入。

3.4

原子事務(wù)3.4.3實(shí)現(xiàn)私有工作空間使用索引節(jié)點(diǎn)（優(yōu)化方法）

120空閑塊012磁盤一個(gè)有三個(gè)數(shù)據(jù)塊的文件的文件索引和磁盤數(shù)據(jù)塊（a）3.4

原子事務(wù)3.4.3實(shí)現(xiàn)私有工作空間使用索引節(jié)點(diǎn)（優(yōu)化方法）

1200’3’012一個(gè)事務(wù)修改第0塊和附加塊3后的情況123’0’私有工作空間起初的索引（b）3.4

原子事務(wù)3.4.3實(shí)現(xiàn)私有工作空間使用索引節(jié)點(diǎn)（優(yōu)化方法）

12０３1230（c）提交以后如果事務(wù)成功結(jié)束，私有索引將被自動移到父輩工作區(qū)中3.4

原子事務(wù)3.4.3實(shí)現(xiàn)寫前日志（計(jì)劃列表）文件真正被修改，但是在改動之前將一條記錄寫入穩(wěn)定存儲器的寫前日志中。日志工作例子：對事務(wù)中三條語句中的每一條，在執(zhí)行之前都要寫入一條日志，以記錄新值和舊值。

x=0;y=0;BEGIN_TRANSACTIONx=x+1;y=y+2;x=y*y;END_TRANSACTIONx=0/1x=0/1y=0/2x=0/1y=0/2x=1/4日志日志日志如果事務(wù)異常中止，可用日志備份初始狀態(tài)，回滾。3.4

原子事務(wù)3.4.3實(shí)現(xiàn)兩階段提交協(xié)議問題背景：在分布式系統(tǒng)中，提交操作可能需要在不同的機(jī)器上的多個(gè)進(jìn)程的協(xié)作。兩階段提交協(xié)議是一種分布式系統(tǒng)中實(shí)現(xiàn)原子性提交的協(xié)議。

將“準(zhǔn)備”寫入日志發(fā)送“準(zhǔn)備”消息將“就緒”寫入日志發(fā)送“就緒”消息

收集所有應(yīng)答寫日志記錄發(fā)送“提交”消息將提交寫入日志提交發(fā)送“完成”消息將“準(zhǔn)備”寫入日志發(fā)送“準(zhǔn)備”消息將“就緒”寫入日志發(fā)送“就緒”消息

收集所有應(yīng)答寫日志記錄發(fā)送“提交”消息將提交寫入日志提交發(fā)送“完成”消息階段1階段2協(xié)調(diào)者參與者3.4

原子事務(wù)3.4.4并發(fā)控制加鎖法兩階段加鎖法

進(jìn)程在增長階段先請求它需要的所有鎖，然后在收縮階段釋放它們。如圖所示：時(shí)間鎖的數(shù)目鎖點(diǎn)增長階段收縮階段3.4

原子事務(wù)3.4.4并發(fā)控制樂觀的并發(fā)控制思想

：“做自己想做的，有問題出現(xiàn)再說！”處理沖突

記錄下哪些文件被讀寫過，在提交時(shí)刻，檢測其它事務(wù)以判斷在本事務(wù)開始后，它的文件是否被其它事務(wù)修改過。如果被修改過，本事務(wù)將被終止；如果沒有修改過，本事務(wù)可以提交。

優(yōu)點(diǎn)：避免了死鎖，允許最大的并行度。

缺點(diǎn):有時(shí)可能會失效，這時(shí)所有的事務(wù)都必須退回重新運(yùn)行一遍。3.4

原子事務(wù)3.4.4并發(fā)控制時(shí)間戳在一個(gè)事務(wù)開始做BEGIN_TRANSACTION時(shí)給它分配一個(gè)時(shí)間戳（唯一）。系統(tǒng)中每個(gè)文件都有一個(gè)相關(guān)的讀取時(shí)間戳和寫入時(shí)間戳，以判斷哪個(gè)已提交的進(jìn)程最近一次讀取或?qū)懭脒^該文件。如果事務(wù)都很短小并且在時(shí)間間隔上比較大，那么當(dāng)一個(gè)進(jìn)程試圖訪問某個(gè)文件時(shí)，該文件的讀寫時(shí)間戳將低于當(dāng)前事務(wù)的時(shí)間戳。（正常情況）如果次序不正確，表明一個(gè)晚于當(dāng)前事務(wù)開始的事務(wù)試圖插入、訪問文件并提交。這意味著當(dāng)前事務(wù)開始過早，將其終止。3.4

原子事務(wù)3.4.4并發(fā)控制時(shí)間戳?xí)r間戳方法舉例：設(shè)有三個(gè)事務(wù)：α、β、γ。α

很早以前已開始運(yùn)行，并且要使用β和γ需要的所有文件，因此這些文件都將設(shè)成α的時(shí)間戳。β和γ同時(shí)開始，但β的時(shí)間戳小于γ。TRDTWRT(α)(α)(β)TRDTWRT(α)(β)(a)(b)當(dāng)γ未提交時(shí)β寫文件的情況試驗(yàn)T(β)(γ)TTWR(c)(d)退出(β)(γ)TRD當(dāng)γ既讀取又寫入文件并提交時(shí)，β寫文件的情況寫3.4

原子事務(wù)3.4.4并發(fā)控制時(shí)間戳?xí)r間戳方法舉例：退出TWRT(α)(β)TTENTTWRT(α)(β)(e)(f)沒有沖突OKT(β)(γ)T(g)(h)(β)(γ)TWR(γ)等待TTENT某個(gè)闖入者試圖進(jìn)入并寫文件γ修改了文件并提交γ正在修改文件讀3.5

分布式系統(tǒng)中的死鎖分布式系統(tǒng)處理死鎖問題的四種策略鴕鳥算法（忽略問題）檢測（允許死鎖發(fā)生，在檢測到后想辦法恢復(fù)）預(yù)防（靜態(tài)的使死鎖在結(jié)構(gòu)上是不可能發(fā)生的）避免（通過仔細(xì)的分配資源以避免死鎖）其中，鴕鳥算法在分布式系統(tǒng)中和在單處理機(jī)系統(tǒng)中一樣好用。死鎖檢測與恢復(fù)算法也很流行。死鎖預(yù)防可能實(shí)現(xiàn)。死鎖避免在分布式系統(tǒng)中從來不采用。3.5分布式系統(tǒng)中的死鎖3.5.1分布式死鎖檢測集中式死鎖檢測每臺機(jī)器的資源圖中只包含它自己的進(jìn)程和資源。協(xié)調(diào)者節(jié)點(diǎn)保存整個(gè)系統(tǒng)（所有資源圖的集合）的資源圖，當(dāng)協(xié)調(diào)者檢測到環(huán)路時(shí)，它中止一個(gè)進(jìn)程以解決死鎖。假死鎖

ABRS機(jī)器0CTS機(jī)器1ABRSCT協(xié)調(diào)者ABRSCT協(xié)調(diào)者圖3-223.5分布式系統(tǒng)中的死鎖3.5.1分布式死鎖檢測分布式死鎖檢測Chandy-Misra-Has算法：算法允許進(jìn)程一次請求多個(gè)資