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

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

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

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

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

時鐘同步3.1.1邏輯時鐘

計算機計時方法

?

計算機上的計時器通常由一個精確的石英晶體制成，它以一定的頻率震蕩。

?

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

?

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

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

——Lamport：時鐘同步是可能的?。。?/p>

?

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

時鐘同步3.1.1邏輯時鐘

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

?

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

?

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

?

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

?

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

并發(fā)事件

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

時鐘同步3.1.1邏輯時鐘

Lamport算法

06121824303642485460081624324048566472800102030405060708090100ABCD

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

例子：三個進程，每個均有自己的時鐘，每個時鐘速率不同。進程0進程1進程23.1

時鐘同步3.1.1邏輯時鐘Lamport算法

06121824303642487076081624324048616977850102030405060708090100ABCD

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

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

時鐘同步3.1.1邏輯時鐘

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

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

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

時鐘同步

3.1.2物理時鐘

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

時鐘同步

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

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

時鐘同步

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

T0

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

適合于只有一臺機器上有WWV接收器

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

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

時鐘同步

3.1.3時鐘同步算法Cristian’s算法

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

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

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

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

時鐘同步3.1.3時鐘同步算法Berkeley算法

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

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

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

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

時鐘同步3.1.4使用時鐘同步至多一次消息傳遞

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

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

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

3.2

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

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

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

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

(b)進程0的時間戳小，所以它獲勝

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

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

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

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

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

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

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

選舉算法3.3.1欺負(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ā)送選舉消息，若某點失效則繞過。

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

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

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

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

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

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

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

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

對外部世界來說，事務(wù)的發(fā)生是不可分割的。確保了每個事務(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）獨立性（Isolated）

并發(fā)的事務(wù)不會相互干擾。這個特性說明事務(wù)是獨立的或連續(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）

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

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

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

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

3.4

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

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

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

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

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

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

原子事務(wù)3.4.3實現(xiàn)寫前日志（計劃列表）文件真正被修改，但是在改動之前將一條記錄寫入穩(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實現(xiàn)兩階段提交協(xié)議問題背景：在分布式系統(tǒng)中，提交操作可能需要在不同的機器上的多個進程的協(xié)作。兩階段提交協(xié)議是一種分布式系統(tǒng)中實現(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ā)控制加鎖法兩階段加鎖法

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

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

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

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

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

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

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

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

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

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

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

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