分布式系統(tǒng)課件：chapter6

SynchronizationChapter6ClockSynchronization分布式系統(tǒng)進(jìn)程同步問題涉及到的以下方面：1）時間2）互斥/同步3)分布式事務(wù)4）死鎖ClockSynchronization時間問題:時間一致性

集中式系統(tǒng)中的時間vs分布式系統(tǒng)中的時間;與真實時鐘之間的關(guān)系

邏輯時鐘vs物理時鐘;ClockSynchronization在集中式系統(tǒng)中，可以通過一個物理時鐘確定兩個或兩個以上的事件的順序從而實現(xiàn)同步。例如：進(jìn)程A詢問時間，之后進(jìn)程B也詢問時間，B得到的時間值就應(yīng)該大于或等于A所得到的時間值，但一定不會小于A得到的時間值。在分布式系統(tǒng)中，因為每個結(jié)點都有自己的時鐘，獲得時間上的一致要復(fù)雜的多。ClockSynchronization例如UNIX的make程序：大程序可被分割成多個源文件，當(dāng)某個源文件發(fā)生變化，只需將該文件重新編譯即可，而不需要對所有的文件進(jìn)行重編譯。make檢查所有的源文件并找出源文件的時間大于目標(biāo)文件的時間那個文件，調(diào)用編譯器重新編譯它。假設(shè)多個文件在不同的機(jī)器上，由于沒有統(tǒng)一時間，就可能發(fā)生修改以后的時間小于原先編譯過的時間。ClockSynchronizationWheneachmachinehasitsownclock,aneventthatoccurredafteranothereventmayneverthelessbeassignedanearliertime.PhysicalClocks(1)實際時間的測量：1、平均太陽日太陽到達(dá)的最高點稱為中天(transitofthesun)，它在每天正午發(fā)生，兩次連續(xù)的中天之間的時間稱為太陽日(solarday)。每天24小時，每小時3600秒，所以太陽秒被精確地定義為1/86400個太陽日。PhysicalClocks(1)Computationofthemeansolarday.PhysicalClocks(2)2、原子時鐘

原子時鐘與地球的擺動和振動無關(guān)，它是通過銫133原子的躍遷計時，定義秒是銫133原子做9,192,631,770次躍遷所用的時間，該原子秒與平均太陽秒相等。目前世界上約有50個實驗室擁有銫133時鐘，每個實驗室都要定期地向巴黎的BIH報告它的時鐘時間，BIH將這些值平均起來計算出國際原子時間(InternationalAtomicTime)，簡稱為TAI。BIH（BureauInternationaldel‘Heure）：國際時間局，設(shè)于巴黎。1922年成立，1988年改組為國際地球自轉(zhuǎn)服務(wù)。PhysicalClocks(2)問題：86,400個TAI秒比一個平均太陽日少3微秒(因為地球自轉(zhuǎn)速度減慢，平均太陽日會越來越長)。BIH通過引入閏秒(leapsecond)解決了問題，當(dāng)用原子秒計時和用太陽秒計時的差距增到800微秒時，使用閏秒，如下圖所示。PhysicalClocks(2)TAIsecondsareofconstantlength,unlikesolarseconds.Leapsecondsareintroducedwhennecessarytokeepinphasewiththesun.PhysicalClocks(2)

這種糾正使在基于連續(xù)的TAI秒時間系統(tǒng)加值，但卻可以和太陽的運動保持一致，它稱作統(tǒng)一協(xié)調(diào)時間（UniversalCoordinatedTime，簡稱為UTC）。UTC是所有現(xiàn)代人使用的時間(Colorado的WWV短波發(fā)射站提供)，它基本上取代了老標(biāo)準(zhǔn)--格林威治天文時間。PhysicalClocks(2)

物理時間校準(zhǔn):

在分布式系統(tǒng)中，由于有多個主機(jī)存在，各主機(jī)的時鐘是有一定的差異的，雖然這個時鐘可以通過使用一個稱為UTC的接收器來校準(zhǔn)，但是，消息在網(wǎng)絡(luò)中的傳送是需要時間的。因此，當(dāng)一臺機(jī)器使用服務(wù)器所給的時間時，要給一個相應(yīng)的誤差估計。

PhysicalClocks(2)t

minΔ1 minΔ2

p發(fā)送mr s返回mt mt到達(dá)

mt中含有時間tClockSynchronizationAlgorithms假設(shè)每臺機(jī)器上都有一個每秒產(chǎn)生H次中斷的計時器。當(dāng)時間到時，中斷處理程序?qū)④洉r鐘加1，軟時鐘記錄從過去某一約定值開始的中斷次數(shù)(記為C)。當(dāng)UTC時間為t時，在機(jī)器P上的時間值是Cp(t)，最完美的情況是對所有的p和t，有Cp(t)=t，即:dC/dt理想值為1。ClockSynchronizationAlgorithmsTherelationbetweenclocktimeandUTCwhenclockstickatdifferentrates.Cristian'sAlgorithmGettingthecurrenttimefromatimeserver.Cristian'sAlgorithmt

minΔ1 minΔ2

p發(fā)送mr s返回mt mt到達(dá)

mt中含有時間t進(jìn)程p向時間服務(wù)器s申請系統(tǒng)時間（mr），mr至少用時min到達(dá)s，s在時刻t用mt傳回給p，至少用時min，Δ1、Δ2是網(wǎng)絡(luò)的其他因素占用的時間.則:Tround=min+Δ1+Δ2+min；一般地，p考慮用t+Tround/2作為當(dāng)前估計時刻（時鐘置為t+Tround/2），此結(jié)果的精度為±[(Δ1+Δ2)/2]。TheBerkeleyAlgorithm

在Cristian算法中，時間服務(wù)器是被動的；在BerkeleyUNIX中采取了完全相反的方法，這里的時間服務(wù)器（實際是時間守護(hù)進(jìn)程）是主動的，它定期地詢問每臺機(jī)器的時間。然后基于這些回答，計算出平均值并告訴所有的機(jī)器將它們的時鐘撥快或撥慢到一個新的值。

該方法適合于沒有WWV接收器的系統(tǒng)，時間守護(hù)進(jìn)程的時間必須由操作者定期地手工設(shè)置。

TheBerkeleyAlgorithmThetimedaemonasksalltheothermachinesfortheirclockvaluesThemachinesanswerThetimedaemontellseveryonehowtoadjusttheirclockAveragingAlgorithms非集中式時鐘同步算法:

將時間劃分為固定長度的再同步間隔:(T0+iR,T0+(i+1)R)在每次間隔開始處，每臺機(jī)器廣播當(dāng)前時鐘，并在時間間隔S內(nèi)接收到達(dá)的其他廣播，計算平均值作為當(dāng)前時間.LogicalClock邏輯時鐘：對多數(shù)應(yīng)用來說，所有機(jī)器在同一時間上達(dá)到一致就足夠了，而時間并不一定要與真實時間一樣。比如對make程序的運行，只要所有的機(jī)器都認(rèn)為當(dāng)前是10:00就可，而盡管當(dāng)前的實際時間是10:02。故對于某一類算法，重要的是內(nèi)部各時鐘的一致。為此，引入了邏輯時鐘（logicalclock）。LamportTimestampsLamport1978年提出了基于邏輯時鐘的時間戳算法，用于分布式系統(tǒng)。其思想是用因果關(guān)系來描述進(jìn)程事件發(fā)生的順序。1、事件定序關(guān)系Lamport提出了HB(Happen-Before)關(guān)系。對于事件e1、e2①

如果存在進(jìn)程p，p包含e1、e2,且e1在e2前發(fā)生，則e1e2；②

如果存在消息m，e1為Send(m)，e2為Receive(m)，則e1e2；③

如果e1e2&e2e3，則e1e3；④

如果e1e2，e2e1均不成立，則e1和e2可以并發(fā)：e1||e2；

LamportTimestamps2、一種邏輯時鐘的定義：設(shè)每個進(jìn)程p有一個邏輯時鐘計數(shù)Tp，則：①在進(jìn)程p的一個事件發(fā)生前，執(zhí)行Tp=Tp+1；②當(dāng)進(jìn)程p發(fā)送消息m時，在m上攜帶時鐘值：(m,Tp)；③當(dāng)進(jìn)程q接收消息(m,Tp)時，取Tq=max{Tq，Tp}+1LamportTimestamps3、邏輯時鐘排序與HB（HappenBefore）的關(guān)系①

如果pq，則Tp<Tq；②

如果Tp<Tq，則pq不一定成立；可能有p||q。

LamportTimestamps4、邏輯時鐘與事件的全排序按照進(jìn)程的邏輯時鐘定義，在一個系統(tǒng)中，不同的事件可能擁有相同的邏輯時間。為了獲得全排序，需要將“進(jìn)程”這一因素加進(jìn)去。這樣，可以用序?qū)Γ═p，pa）來進(jìn)行定序。其中Tp為時間的邏輯時鐘值，pa為進(jìn)程p的優(yōu)先級，稱之為時間戳。在需要排序時，當(dāng)邏輯時鐘值相同時，就比較它們的優(yōu)先級，優(yōu)先級高者優(yōu)先。LamportTimestamps例如：有三個進(jìn)程0、1、2。各進(jìn)程運行在不同的機(jī)器上，每個機(jī)器都有自己的時鐘，以各自不同的速率工作（圖a）,通過Lamport的邏輯時鐘算法矯正(圖b)。

LamportTimestampsThreeprocesses,eachwithitsownclock.Theclocksrunatdifferentrates.Lamport'salgorithmcorrectstheclocks.60544842363024181260807264564840322416801009080706050403020100ABCD(a)76704842363024181260857769614840322416801009080706050403020100ABCD(b)

012012LamportTimestamps如果將進(jìn)程本身的因素考慮進(jìn)去，就可以實現(xiàn)對系統(tǒng)中的所有事件進(jìn)行“定序”（全排序）。定義系統(tǒng)范圍內(nèi)的前于關(guān)系“=>”：a(inPi)=>b(inPj)當(dāng)且僅當(dāng)：Ti<Tj

或者

Ti=Tj并且Pi優(yōu)先級高于Pj。Example:Totally-OrderedMulticastingUpdatingareplicateddatabaseandleavingitinaninconsistentstate.例如：一個銀行在兩個地方存有數(shù)據(jù)備份，如果一個地方存款，同時，另一個地方加利息，會出現(xiàn)不一致。用邏輯時鐘可以避免這一問題。向量時鐘標(biāo)量時鐘無法識別時鐘的推進(jìn)是局部事件引起,還是包文交換引起的。因此引入向量時鐘:每個進(jìn)程Pi和一個時間向量LCi[1,2,...,n]相關(guān)聯(lián),其中:(1)向量元素LCi[i]描述進(jìn)程Pi自身的邏輯時鐘進(jìn)展情況.(2)向量元素LCi[j]表示進(jìn)程Pi所知道的關(guān)于進(jìn)程Pj的邏輯時鐘進(jìn)展情況.(3)向量LCi[1,2,...,n]組成進(jìn)程Pi對于邏輯全局時間的局部視圖.向量時鐘每個進(jìn)程Pi向量時鐘修改規(guī)則如下:(1)當(dāng)發(fā)生一個事件之前,Pi更新LCi[i]:

LCi[i]:=LCi[i]+d(d>0)；(2)每個報文帶有發(fā)送時的時鐘向量,當(dāng)收到一個帶時間戳的報文(m,LCj,j)時,Pi更新LCi:

LCi[k]:=max(LCi[k],LCj[k])1<=k<=n；

LCi[i]:=LCi[i]+d(d>0)；向量時鐘使用向量邏輯時鐘方法確定的各事件的邏輯時間(可以知道時間前進(jìn)的原因)進(jìn)程P進(jìn)程R進(jìn)程Qp1(1,0,0)p2(2,1,0)p3(3,1,0)p4(4,5,0)q1(0,1,0)q2(1,2,0)q3(1,3,0)q4(1,4,0)q5(1,5,0)q6(1,6,0)q7(1,7,2)r1(0,0,1)r3(1,4,3)r2(0,0,2)r4(1,4,4)分布式互斥臨界區(qū)互斥問題——臨界資源的互斥使用

一、基本假設(shè)①在分布式系統(tǒng)中，每個進(jìn)程是平等的。它們都擁有申請和“審批”資源的權(quán)利；②系統(tǒng)有n個結(jié)點，結(jié)點和進(jìn)程一一對應(yīng)；③進(jìn)程按照發(fā)送者發(fā)送消息的順序接收消息；④每條消息在有限時間內(nèi)是可送達(dá)的；⑤每個進(jìn)程可以給其它任意進(jìn)程發(fā)消息。MutualExclusion:

ACentralizedAlgorithmProcess1asksthecoordinatorforpermissiontoenteracriticalregion.PermissionisgrantedProcess2thenaskspermissiontoenterthesamecriticalregion.Thecoordinatordoesnotreply.Whenprocess1exitsthecriticalregion,ittellsthecoordinator,whenthenrepliesto2分布式互斥二、集中式算法——每一個資源有一個協(xié)調(diào)者進(jìn)程管理。1、等待新消息2、如果是Release消息，則查看Request隊列是否為空。a)如果該隊列空，則轉(zhuǎn)1繼續(xù)等待下一個請求；b)如果不空，則從該Request隊列中取下一個請求，并給其發(fā)送者發(fā)Reply消息。轉(zhuǎn)1等待下一個請求；3、如果是Request消息，則查看臨界資源是否有效。a)如果有效，則給發(fā)送此Request的進(jìn)程發(fā)Reply消息，轉(zhuǎn)1繼續(xù)等待下一個請求；b)如果無效，則將此Request掛到相應(yīng)隊列中；轉(zhuǎn)1等待下一個請求；4、進(jìn)行出錯處理，然后轉(zhuǎn)1。討論：①每完成一次臨界區(qū)操作，要發(fā)Request、Reply、Release三個消息；②當(dāng)協(xié)調(diào)者進(jìn)程故障時，需要安排新進(jìn)程代替它：選一個進(jìn)程；通知其它進(jìn)程；建立相應(yīng)隊列；恢復(fù)工作。

分布式互斥ADistributedAlgorithmTwoprocesses(0and2)wanttoenterthesamecriticalregionatthesamemoment.Process0hasthelowesttimestamp,soitwins.Whenprocess0isdone,itsendsanOKalso,so2cannowenterthecriticalregion.三、Lamport算法（分布式算法）

基本思想：要想獲得某一資源的使用權(quán)，必須征得所有結(jié)點同意；沖突時，按“定序”進(jìn)行處理。主要數(shù)據(jù)結(jié)構(gòu)：每個進(jìn)程擁有一個全局請求隊列。分布式互斥1.當(dāng)進(jìn)程p要進(jìn)入臨界區(qū)時，向系統(tǒng)中所有進(jìn)程發(fā)送Request(Tp,p)，并將此請求放入自己的請求隊列；2.當(dāng)進(jìn)程q接到此消息，將其放入自己的請求隊列，并返回一個帶有時間戳的Reply(Tq)；[Tq>=Tp+1];3.當(dāng)Request(Tp,p)按“定序”規(guī)則排在p的隊列首位時，p進(jìn)入臨界區(qū)，否則p等待；4.當(dāng)p退出臨界區(qū)時，從自己的隊列中去掉Request(Tp,p)，并向其它進(jìn)程發(fā)出Release；5.當(dāng)q接到Release后，將相應(yīng)的Request(Tp,p)從自己的隊列中刪除。然后看自己是否正在等待此臨界區(qū)：a)如果是，則轉(zhuǎn)3；b)如果不是，不做任何進(jìn)一步的工作。算法討論：①每完成一次臨界區(qū)操作，要發(fā)Request、Reply、Release消息各n-1個；②時間戳及全排序保證了不會死鎖。

分布式互斥四、Lamport算法的改進(jìn)（Ricart,Agrawala1981）①Request消息。由于是分布式管理，p必須讓系統(tǒng)中的其它n-1個進(jìn)程知道它的需求。因此這n-1個消息時必須的；②Reply消息。a)

如果進(jìn)程q未在臨界區(qū)內(nèi)，且現(xiàn)在也不打算進(jìn)入臨界區(qū)，則同意p的進(jìn)入請求，向p發(fā)Reply；b)如果進(jìn)程q在臨界區(qū)內(nèi)，則不向p發(fā)Reply，并將此Request掛入請求隊列；c)

如果進(jìn)程q正打算進(jìn)入臨界區(qū)，則看Tp<Tq是否成立，

i.

如果成立，同意p的進(jìn)入請求，向p發(fā)Reply；

ii.如果不成立，則將此Request掛入相應(yīng)隊列，此時不發(fā)Reply；③按照發(fā)Reply消息的原則，當(dāng)未發(fā)Reply的進(jìn)程使用完臨界區(qū)后，再向原來發(fā)Request的進(jìn)程發(fā)送Release消息。該算法所發(fā)送的Reply和Release消息的總數(shù)為n-1。這樣一來，只用2(n-1)條消息就可以完成一次對臨界區(qū)的操作。分布式互斥分布式互斥Ricart改進(jìn)算法的狀態(tài)轉(zhuǎn)換圖討論：①新來者問題——參與此活動的進(jìn)程都需要知道彼此的名字，當(dāng)一進(jìn)程新參與時，要完成相應(yīng)的工作；②故障問題——某參與者故障時，會使算法失效，這可用監(jiān)測方法解決。分布式互斥ATokeRingAlgorithmAnunorderedgroupofprocessesonanetwork.Alogicalringconstructedinsoftware.ATokeRingAlgorithm五、令牌傳遞算法

1.基于環(huán)結(jié)構(gòu)的令牌傳遞算法a)被動等待（LeLam，1977）

i.

p接到左邊傳來的令牌，如果自己想進(jìn)入1）則握著令牌并進(jìn)入臨界區(qū)；2）完成臨界區(qū)操作3）退出臨界區(qū)；

ii.

將令牌右傳；ATokeRingAlgorithm2.基于非環(huán)結(jié)構(gòu)的令牌傳遞算法[K.M.Chandy1982]設(shè)系統(tǒng)有n個進(jìn)程，則它有一個n維令牌向量，每一個進(jìn)程對應(yīng)一個分量，該分量表示相應(yīng)的進(jìn)程已獲得服務(wù)時的Request的最大次數(shù)。每個進(jìn)程維持一個請求隊列。ATokeRingAlgorithm算法：①p為第m次進(jìn)入臨界區(qū)，向所有參與者進(jìn)程發(fā)出Request(p,m)后進(jìn)入等待狀態(tài)；②在獲得令牌后：a)

將對應(yīng)的令牌向量中的對應(yīng)元素置為m；b)進(jìn)入臨界區(qū)工作；c)退出臨界區(qū)時，查看請求隊列?若隊列空，則執(zhí)行自己的工作，直到收到某個請求；若隊列非空，則取一個請求Request(q,h)，如果h比q對應(yīng)的令牌向量中的元素小（見a)），表明此請求已經(jīng)被執(zhí)行，將其刪除，并取下一個Request；否則將令牌傳給q；ATokeRingAlgorithm討論：①令牌傳送是直接的；②令牌不用時，不需要循環(huán)不斷地傳送；只在得到申請時才向申請者發(fā)送；③需要解決令牌丟失問題；④需要進(jìn)行隊列的維護(hù)和令牌向量的協(xié)調(diào)工作。ComparisonAcomparisonofthreemutualexclusionalgorithms.AlgorithmMessagesperentry/exitDelaybeforeentry(inmessagetimes)ProblemsCentralized32CoordinatorcrashDistributed2(n–1)2(n–1)CrashofanyprocessTokenring1to0ton–1Losttoken,processcrashComparison

Messagesperentry/exit:集中式算法:它在進(jìn)程進(jìn)入和退出臨界區(qū)時，只用了3條消息，即請求進(jìn)入，同意進(jìn)入和退出時釋放。

分布式算法:需要N-1條請求消息，及另外的N-1條允許消息，總共有2(N-1)條消息。

令牌算法:如果每個進(jìn)程總是想進(jìn)入一個臨界區(qū)，則令牌的每次傳遞將導(dǎo)致一次進(jìn)出臨界區(qū)。平均每一次進(jìn)入臨界區(qū)入口都有一條消息。在其它極限情況下，令牌也許將幾小時幾小時地沿環(huán)傳遞而沒有進(jìn)程想使用它，在這種情況下，每一次進(jìn)入臨界區(qū)入出口消息數(shù)是無界的。ComparisonDelaybeforeentry(inmessagetimes)進(jìn)程需要進(jìn)入臨界區(qū)到它能進(jìn)入臨界區(qū)的延遲:集中式算法:進(jìn)入臨界區(qū)只需要處理2條消息的時間.分布式算法:需要2(N-1)條消息.令牌環(huán)算法:時間從0（剛接收到令牌）到N-1（釋放令牌）變化。ARingAlgorithm選舉算法Bully算法環(huán)算法選擇算法許多分布式算法需要一個進(jìn)程充當(dāng)協(xié)調(diào)者、發(fā)起者、排序者，或者其它角色。而系統(tǒng)運行中是會發(fā)生故障的，當(dāng)發(fā)生故障時，必須立即選擇另一個副本恢復(fù)運行，既選擇算法，假定：①

進(jìn)程與結(jié)點機(jī)一一對應(yīng)；②進(jìn)程p具有唯一優(yōu)先級，并用p表示；③系統(tǒng)中具有最高優(yōu)先級者為協(xié)調(diào)進(jìn)程；④每個進(jìn)程知道系統(tǒng)中當(dāng)前的各個進(jìn)程及其優(yōu)先級。選擇算法選舉算法的目的是在選舉開始后，確保在所有進(jìn)程都同意的基礎(chǔ)上選出協(xié)調(diào)者;選舉算法總是找擁有最大號碼的進(jìn)程，將它指定為協(xié)調(diào)者，各算法在選舉時有不同的方法;TheBullyAlgorithm(1)ThebullyelectionalgorithmProcess4holdsanelectionProcess5and6respond,telling4tostopNow5and6eachholdanelectionTheBullyAlgorithm(2)Process6tells5tostopProcess6winsandtellseveryoneBully算法描述1.當(dāng)進(jìn)程p需要進(jìn)入臨界區(qū)時，向協(xié)調(diào)者發(fā)一個請求消息，如果在T時間內(nèi)得到回復(fù)，則進(jìn)入臨界區(qū)工作；否則，開始競爭協(xié)調(diào)者；2.p向所有的優(yōu)先級較高的進(jìn)程發(fā)送消息：“要當(dāng)協(xié)調(diào)者”。

i.如果在規(guī)定時間T內(nèi)沒接到回復(fù)，p則啟動一個協(xié)調(diào)者副本，并發(fā)

出“p為當(dāng)前的協(xié)調(diào)者”消息給其它進(jìn)程；

ii.如果在規(guī)定時間T內(nèi)收到回復(fù)（反對者），則再等一個時間T′。如果在T′內(nèi)沒有收到消息，則認(rèn)為剛才的回復(fù)者故障，p重新開始執(zhí)行競爭協(xié)調(diào)者算法；如果在T′收到消息“q是新的協(xié)調(diào)者”，則p記下q，并向q申請進(jìn)入臨界區(qū)；3.如果p接到一個比它優(yōu)先級低的進(jìn)程競爭協(xié)調(diào)者的消息，則給對方一個適當(dāng)?shù)幕貜?fù)；自己開始執(zhí)行競爭者算法。4.當(dāng)一個高優(yōu)先級的進(jìn)程因故障排除恢復(fù)運行時，它重新執(zhí)行競爭者算法，以剝奪較低優(yōu)先級進(jìn)程的協(xié)調(diào)者資格，自己重新行使此權(quán)利。二、基于環(huán)結(jié)構(gòu)的算法基本思想:假設(shè)所有的進(jìn)程是按物理或邏輯排序的，每個進(jìn)程都知道誰是它的后繼者。當(dāng)任何一個進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時，它就構(gòu)造一個包含它自身進(jìn)程號的選舉消息發(fā)送給它的后繼者。如果后繼者失效，消息將繞過后繼者到達(dá)下一個后繼者，或者再下一個，直到找到一個運行進(jìn)程。每次發(fā)送者都將自己的進(jìn)程號加入到消息表中。ARingAlgorithmARingAlgorithm基于環(huán)結(jié)構(gòu)的算法(假定：單向右傳，建立活躍表)。如果p發(fā)現(xiàn)協(xié)調(diào)者故障，則向右鄰發(fā)送elec(p)消息，并建立一個活躍表，在表中填上自己的優(yōu)先級；如果p收到左鄰發(fā)來的elec(q)消息，則：如果p未見到其它elec消息，則建立活躍表，并在表中填上p和q；然后依次向右鄰發(fā)elec(q)、elec(p)；如果已經(jīng)見過其它elec消息（此時已有活躍表），則判定此elec是否是自己最初發(fā)出的，如果不是，則將其放入自己的活躍表中，并將其右傳；如果它最初是自己發(fā)出的，則p的活躍表中已有所有進(jìn)程的優(yōu)先級，此時從中選最高者為協(xié)調(diào)者。ARingAlgorithmElectionalgorithmusingaring.進(jìn)程2、5同時發(fā)現(xiàn)前任協(xié)調(diào)者進(jìn)程7失效，它們各自建立一個選舉消息沿環(huán)發(fā)送。ARingAlgorithm最終，兩條消息都將沿環(huán)運動，進(jìn)程2和5分別將它們轉(zhuǎn)化成協(xié)調(diào)者消息，消息中有完全一樣的成員，相互順序也相同，當(dāng)兩條消息再繞環(huán)一周時，都被去掉;分布式的同步不同結(jié)點上的進(jìn)程的同步點：基于消息的發(fā)送與接收。

P1P2………………..send(P2)receive(P1)……………….TheTransactionModel商業(yè)模型最初的模型來源于社會的貿(mào)易。比如,對任何一個交易,從協(xié)商到簽定合同成交。其實，大到企業(yè)之間的交易，小到一般的購物等。都經(jīng)歷了從協(xié)商到簽約過程，簽約前可以更改或中止，簽約后必須執(zhí)行。TheTransactionModel(1)磁帶系統(tǒng)模型：早期計算機(jī)系統(tǒng)中對事務(wù)的使用（約60年代）。在硬盤和在線數(shù)據(jù)庫出現(xiàn)之前，所有的文件都保存在磁帶上。一個帶有自動盤點系統(tǒng)的超級市場，每天關(guān)門后，計算機(jī)對兩盤作為輸入的磁帶進(jìn)行處理。第一盤磁帶存有當(dāng)天早晨開門以前的所有庫存，第二盤存有當(dāng)天的更新列表：已銷售給客戶的產(chǎn)品和供應(yīng)商交付的產(chǎn)品。計算機(jī)從兩盤磁帶上讀取數(shù)據(jù)，并生成新的主庫存磁帶。TheTransactionModel(1)Updatingamastertapeisfaulttolerant.對任何原因引起的運行錯誤，所有的磁帶都可以倒卷（rewound），其工作可以毫無損失地重新開始。老式的磁帶系統(tǒng)具有了要么全有要么全無的特性--原子事務(wù)。TheTransactionModel(1)在線更新數(shù)據(jù)庫模型：銀行應(yīng)用的例子：客戶通過帶有調(diào)制解調(diào)器的PC機(jī)連接到銀行，想將一個賬戶下的錢取出再存入另一賬戶。操作通過下面兩步執(zhí)行：提?。ń痤~，賬戶1）存入（金額，賬戶2）如果電話線在第一步之后第二步之前中斷，那么第一個賬戶已被取出而第二個賬戶卻沒有存入。錢就消失在了未知的空間中。TheTransactionModel(1)必須將這兩個操作組成作為一個原子事務(wù)：要么兩個都執(zhí)行，要么一個也不執(zhí)行。關(guān)鍵是事務(wù)執(zhí)行失敗后能返回到最初狀態(tài)。我們真正需要的是像使用磁帶時那樣的對數(shù)據(jù)庫倒卷的方法。這種能力是原子事務(wù)必須提供的。TheTransactionModel(1)假設(shè)1：系統(tǒng)由一些相互獨立的進(jìn)程組成，每個進(jìn)程都會隨機(jī)出錯；假設(shè)2：通信錯誤已經(jīng)被底層軟件透明地處理；假設(shè)3：穩(wěn)定的存儲器；TheTransactionModel(2)Examplesofprimitivesfortransactions.PrimitiveDescriptionBEGIN_TRANSACTIONMakethestartofatransactionEND_TRANSACTIONTerminatethetransactionandtrytocommitABORT_TRANSACTIONKillthetransactionandrestoretheoldvaluesREADReaddatafromafile,atable,orotherwiseWRITEWritedatatoafile,atable,orotherwise1、事務(wù)原語：使用事務(wù)編程需要由操作系統(tǒng)提供或者由語言運行系統(tǒng)提供特殊的原語，例如：TheTransactionModel(2)2、事務(wù)體由BEGIN_TRANSACTION和END_TRANSACTION括起來的程序段；事務(wù)體中的操作要么全部執(zhí)行，要么一個也不執(zhí)行。這些操作可能是系統(tǒng)調(diào)用、庫過程、或者是某種語言中用括號括起來的語句。TheTransactionModel(3)TransactiontoreservethreeflightscommitsTransactionabortswhenthirdflightisunavailableBEGIN_TRANSACTION

reserveWP->JFK;

reserveJFK->Nairobi;

reserveNairobi->Malindi;

END_TRANSACTION(a)BEGIN_TRANSACTION

reserveWP->JFK;

reserveJFK->Nairobi;

reserveNairobi->Malindifull=>

ABORT_TRANSACTION(b)從紐約WhitePlains到肯尼亞的Malindi經(jīng)過3個航班：TheTransactionModel(3)3、事務(wù)的特性（ACID）原子性（Atomic）：對外部世界來說，事務(wù)的發(fā)生是不可分割的；一致性（Consistent）：事務(wù)不會破壞系統(tǒng)的恒定；獨立性（Isolated）：并發(fā)的事務(wù)不會互相干擾；持久性（Durable）：一旦一個事務(wù)提交，改變就是永遠(yuǎn)存在的。ClassificationofTransactionsFlattransactionsNestedtransactionsDistributedtransactionsClassificationofTransactionsNestedtransactions

事務(wù)可以包含子事務(wù)，這通常稱作嵌套事務(wù)，比如：預(yù)定3個不同航班的事務(wù)可以在邏輯上分成3個子事務(wù)，他們可以獨立管理和運行。ClassificationofTransactionsDistributedtransactions

單層事務(wù)需要處理分布在多臺機(jī)器上的數(shù)據(jù)的情況。例如：預(yù)定從紐約到Nairobi航班座位的子事務(wù)涉及分布在兩個城市的2個數(shù)據(jù)庫。DistributedTransactionsAnestedtransactionAdistributedtransaction事務(wù)實現(xiàn):

1.PrivateWorkspace

2.WriteaheadLogPrivateWorkspaceThefileindexanddiskblocksforathree-blockfileThesituationafteratransactionhasmodifiedblock0andappendedblock3AftercommittingWriteaheadLog寫前日志是另一個實現(xiàn)事務(wù)的常用方法，有時也稱為計劃列表（intentionslist）。使用該方法時，文件被真正修改，但是在改動任何塊之前，將一條記錄寫入穩(wěn)定存儲器的寫前日志中，以判斷是哪一個事務(wù)在進(jìn)行修改操作，哪一個文件的哪一塊被改動了，舊值和新值分別是什么。只有當(dāng)日志成功寫入之后才可以進(jìn)行文件的修改。WriteaheadLoga)Atransactionb)–d)Thelogbeforeeachstatementisexecutedx=0;y=0;BEGIN_TRANSACTION;x=x+1;y=y+2x=y*y;END_TRANSACTION;(a)Log[x=0/1](b)Log[x=0/1][y=0/2](c)Log[x=0/1][y=0/2][x=1/4](d)WriteaheadLog三個記錄依次寫入日志：如果事務(wù)執(zhí)行成功且被提交，那么它的提交記錄也將被寫入日志，但數(shù)據(jù)不需要變動，因為它們已經(jīng)被更新了。使用日志進(jìn)行系統(tǒng)恢復(fù)（1）日志作為事務(wù)向前（處理事務(wù)）和向后（撤銷事務(wù)）的依據(jù)；若事務(wù)異常中止，可用日志來備份初始狀態(tài)；從日志的末尾開始向回讀取每條記錄，再將記錄中描述的改動復(fù)原，該操作稱之為滾回；日志也可用來進(jìn)行系統(tǒng)崩潰后的恢復(fù)（2）假設(shè)執(zhí)行事務(wù)的進(jìn)程在寫入上例最后一條記錄后及改變x之前崩潰；在機(jī)器重啟動后，日志可以用來檢查在系統(tǒng)崩潰時刻是否有事務(wù)正在處理中；當(dāng)讀到最后一條記錄顯示x的當(dāng)前值是1，那么說明崩潰顯然是在更新之前發(fā)生的，所以x的值應(yīng)被改為4；相反，如果在系統(tǒng)恢復(fù)時x的值是4，那么同樣也清楚的說明崩潰是在更新后發(fā)生的，因此不需要進(jìn)行任何變動。BEGIN_TRANSACTION;x=x+1;y=y+2x=y*y;END_TRANSACTION;Log[x=0/1][y=0/2][x=1/4]寫完后系統(tǒng)崩潰事務(wù)提交事務(wù)提交操作必須是原子的，即瞬時和不可再分的。在分布式系統(tǒng)中，提交操作可能需要不同機(jī)器上的多個進(jìn)程的協(xié)作，這些進(jìn)程中的每一個都有一些被事務(wù)改動過的變量、文件、數(shù)據(jù)庫或者其他對象。two-phasecommitprotocol基本思想（Gray，1978）：選一個進(jìn)程作為協(xié)調(diào)者。一般是執(zhí)行事務(wù)的進(jìn)程。提交協(xié)議開始時，協(xié)調(diào)者先寫入一條日志表明它要開始提交協(xié)議，然后向每個下屬進(jìn)程發(fā)送一條消息，通知它們?yōu)樘峤蛔骱脺?zhǔn)備。當(dāng)下屬收到消息后，它先進(jìn)行檢查以確認(rèn)是否為提交作好了準(zhǔn)備，然后將它的決定發(fā)回給協(xié)調(diào)者。當(dāng)協(xié)調(diào)者收到了所有的響應(yīng)后，它就知道是否可以提交或中止。如果所有的進(jìn)程都準(zhǔn)備提交，那么事務(wù)就可以提交了。如果一個或幾個進(jìn)程不能提交（或沒有響應(yīng)），事務(wù)就中止。無論哪種情況，協(xié)調(diào)者都要寫一條日志記錄，并通知下屬下一步的決定。正是因為寫入的日志才使得事務(wù)真正被提交，且無論發(fā)生什么它都會繼續(xù)下去。two-phasecommitprotocol崩潰和恢復(fù)日志在穩(wěn)定存儲器上，所以這個協(xié)議在（多個）崩潰面前仍然是有彈性的：如果協(xié)調(diào)者在寫入初始化日志后崩潰，恢復(fù)時只需要從停止的地方開始繼續(xù)工作就可以了；若需要，還可以重發(fā)初始化消息；如果在響應(yīng)第一條消息之前某個下屬崩潰了，那么協(xié)調(diào)者在放棄之前將會給它不斷地發(fā)送消息；如果協(xié)調(diào)者后來崩潰了，那么它就可以從日志中看出自己所處的位置，并能決定該作些什么。ConcurrencyControl當(dāng)多個事務(wù)在不同的進(jìn)程（在不同的處理機(jī)上）中同時執(zhí)行時，需要一些機(jī)制以保證它們互不干擾。這種機(jī)制稱為并發(fā)控制算法。ConcurrencyControl(1)Generalorganizationofmanagersforhandlingtransactions.ConcurrencyControl(2)Generalorganizationofmanagersforhandlingdistributedtransactions.ConcurrencyControl定義：多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行執(zhí)行它們時的結(jié)果相同。稱這種調(diào)度策略為可串行化（Serializable）的調(diào)度。

可串行性（Serializability）是并發(fā)事務(wù)正確性的準(zhǔn)則。按這個準(zhǔn)則規(guī)定，一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度。Serializabilitya)–c)ThreetransactionsT1,T2,andT3d)PossibleschedulesBEGIN_TRANSACTION

x=0;

x=x+1;

END_TRANSACTION

(a)BEGIN_TRANSACTION

x=0;

x=x+2;

END_TRANSACTION

(b)BEGIN_TRANSACTION

x=0;

x=x+3;

END_TRANSACTION

(c)Schedule1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3LegalSchedule2x=0;x=0;x=x+1;x=x+2;x=0;x=x+3;LegalSchedule3x=0;x=0;x=x+1;x=0;x=x+2;x=x+3;Illegal(d)ConcurrencyControl三種并發(fā)控制算法：1）加鎖法；2）樂觀的并發(fā)控制；3）時間戳；1、加鎖法加鎖方法實現(xiàn)并發(fā)操作調(diào)度的可串行性，保證了調(diào)度正確性：作為一個事務(wù)的一部分，當(dāng)一個進(jìn)程需要讀或?qū)懸粋€文件（或其他對象）時，它首先將這個文件加鎖；對文件加鎖可以防止其他進(jìn)程對文件的訪問，保證了一個事務(wù)的生存期內(nèi)文件不會被改變；鎖一般由事務(wù)系統(tǒng)請求和釋放，不需要編程人員的操作；加鎖法實現(xiàn)用一個集中式的加鎖管理者來實現(xiàn);每臺機(jī)器上有一個本地加鎖管理者管理本地文件。

兩種情況下，加鎖管理者都擁有一個鎖定的文件列表，所有欲對已加鎖文件進(jìn)行的加鎖嘗試都將被拒絕。讀鎖和寫鎖上述方案限制過于嚴(yán)格，可以通過區(qū)分讀鎖和寫鎖來加以改進(jìn)：如果在一個文件上設(shè)置了讀鎖，那么在它上面設(shè)置其他的讀鎖也是允許的；讀鎖用來確保文件不會被改寫（也即排斥所有的寫入者），但不禁止其他讀取文件的事務(wù)；當(dāng)一個文件被設(shè)置寫鎖時，其他任何類型的鎖都被禁止。

讀鎖共享，寫鎖互斥。鎖的粒度加鎖單位的大小稱為鎖的粒度。例如：整個文件、記錄、頁面，或整個數(shù)據(jù)庫；粒度越合適，加鎖就可以越精確，也就能實現(xiàn)更大的并發(fā)度；例如，允許兩個進(jìn)程同時對某個文件的開頭和末尾進(jìn)行操作；鎖分得越細(xì)致，就需要更多的鎖，開銷也就越大，也容易導(dǎo)致死鎖；Two-PhaseLocking(1)兩段鎖（Two-PhaseLocking，簡稱2PL）協(xié)議是保證并發(fā)調(diào)度可串行性的封鎖協(xié)議，它提供了一種可以串行調(diào)度的算法。在兩階段加鎖法中，進(jìn)程在增長階段先請求它需要的所有鎖，然后在收縮階段釋放它們。Two-PhaseLocking(1)遵守三個規(guī)則:當(dāng)調(diào)度管理器收到來自事務(wù)管理器的oper(T,x)操作時,檢測該操作是否與已經(jīng)允許鎖定的另一個進(jìn)程沖突？如果是,oper(T,x)被延遲；否則，它就允許對數(shù)據(jù)項x加鎖,并將oper(T,x)傳遞給數(shù)據(jù)管理器；直到數(shù)據(jù)管理器通知它已經(jīng)完成了對鎖定數(shù)據(jù)項x的操作,調(diào)度管理器才會釋放數(shù)據(jù)項x的鎖；一旦調(diào)度管理器為事務(wù)T釋放了鎖，那么無論事務(wù)T請求為哪個數(shù)據(jù)項加鎖,調(diào)度管理器都不會允許T加另外一把鎖。T獲取另外一把鎖的任何企圖都是一個程序錯誤,都會中止事務(wù)T.Two-PhaseLocking(1)可以證明（Eswaran等，1976）如果所有的事務(wù)都使用兩階段加鎖法，那么通過交錯事務(wù)進(jìn)行的所有調(diào)度都是串行的。在緊偶合系統(tǒng)中兩階段加鎖法被廣泛使用。Two-PhaseLocking(1)嚴(yán)格的兩階段加鎖法：收縮階段是在事務(wù)結(jié)束運行之后要么提交，要么中止時出現(xiàn)。Stricttwo-phaselocking.Two-PhaseLocking(1)該策略有2個優(yōu)點：一個事務(wù)總是讀由另一個已提交的事務(wù)寫入的值，不會因為一個事務(wù)的計算是基于它本不應(yīng)該看到的文件而中止它；所有鎖的請求與釋放都可以由系統(tǒng)來處理而無須事務(wù)關(guān)心：只要訪問一個文件就可以請求一個鎖，當(dāng)事務(wù)結(jié)束時就可以釋放一個鎖。該策略消除了瀑布型中止：不得不撤銷一個已經(jīng)提交的事務(wù)，因為它看到了不該看到的文件。死鎖加鎖，即使兩階段加鎖，也可能會導(dǎo)致死鎖。例如：若兩個進(jìn)程都試圖以相反的順序請求同一對鎖，那么就會發(fā)生死鎖。解決方法：采用諸如以某種規(guī)范順序請求所有的鎖之類的一般方法來防止保持-等待循環(huán)的出現(xiàn)。通過對一張精確描述哪個進(jìn)程可以擁有哪個鎖，它還想請求哪個鎖的圖進(jìn)行死鎖掃描，以檢查是否有環(huán)路出現(xiàn)，也可以防止死鎖。如果事先知道一個鎖的擁有時間不會超過T秒時，也可以采用一個超時方案：如果某個擁有者連續(xù)擁有同一個鎖超過了T秒，那么一定是出現(xiàn)了死鎖。2、樂觀的并發(fā)控制處理同時運行多個事務(wù)的第二種方法是樂觀并發(fā)控制法（KungandRobinson，1981）。思想：盡管放心去做你想做的，不用在意其他人正在做什么。如果有問題出現(xiàn)，那么以后再考慮吧。在實際情況中，沖突相對來說非常少，所以這個策略大部分時間都可以正常工作。樂觀的并發(fā)控制沖突的處理：記錄下有哪些文件曾經(jīng)被讀寫過；在提交時刻，檢測其他的事務(wù)以判斷在本事務(wù)開始后它的文件是否被其他事務(wù)修改過？如果被修改過，那么本事務(wù)將被中止；如果沒有修改過，那么本事務(wù)就可以提交了。樂觀的并發(fā)控制最適合于基于私有工作空間的情況：每個事務(wù)都獨立地修改各自的文件，不會涉及其他的事務(wù)；在結(jié)束的時候，新的文件要么被提交要么被釋放。優(yōu)點：避免了死鎖，而且允許最大的并行度（進(jìn)程不需要去等待一個鎖）；缺點：有時可能會失效，這時所有事務(wù)都必須退回重新運行；在重負(fù)載的情況下，算法失效的可能性將會直線上升，這使得樂觀并發(fā)控制算法成了一個很糟糕的選擇。3、時間戳在一個事務(wù)開始做BEGIN_TRANSACTION的時候給它分配一個時間戳（Reed，1983）；Lamport算法可以確保時間戳的惟一性；系統(tǒng)中的每個文件（對象）都擁有一個讀取時間戳和寫入時間戳，以判斷哪個已提交的進(jìn)程最近一次讀取或?qū)懭脒^該文件。事務(wù)的時間標(biāo)記：ts(T)數(shù)據(jù)的時間標(biāo)記：讀時間標(biāo)記tr寫時間標(biāo)記tw時間戳（cont’d）

事務(wù)T讀數(shù)據(jù)

read(D);ifts(T)≥twthen/*符合時間標(biāo)記協(xié)議，read(D)即為讀取值*/tr:=max(ts(T),tr);else/*已有比T年輕的事務(wù)寫入D，違反時間標(biāo)記協(xié)議，T卷回*/rollbackTandrestartitwithanewts(T);時間戳（cont’d）事務(wù)T寫數(shù)據(jù)Difts(T)