分布式系統(tǒng)之7、同步1

1、同步(1)物理時(shí)鐘同步邏輯時(shí)鐘同步選舉算法互斥內(nèi)容一、物理時(shí)鐘同步1、基本概念一致的系統(tǒng)時(shí)間是分布式同步的基礎(chǔ)事件的順序關(guān)系問(wèn)題的解決基礎(chǔ)兩個(gè)層面的時(shí)鐘同步絕對(duì)同步（物理同步）物理時(shí)鐘相對(duì)同步（邏輯同步）邏輯時(shí)鐘物理時(shí)鐘計(jì)算機(jī)系統(tǒng)的絕對(duì)時(shí)間UTC：一種國(guó)際統(tǒng)一的科學(xué)物理時(shí)間，稱為統(tǒng)一協(xié)調(diào)時(shí)間?；靖拍顣r(shí)鐘精確度設(shè)UTC時(shí)間為t，機(jī)器的時(shí)間為C，則機(jī)器時(shí)鐘的精確度可以用一個(gè)常數(shù)來(lái)表達(dá)：1- dC/dt 1+一般來(lái)說(shuō)， 由生產(chǎn)廠商規(guī)定，稱為最大偏移率。同步間隔最壞的情況下，兩個(gè)計(jì)算機(jī)的時(shí)鐘以相反的方向偏離UTC時(shí)間，則要保證兩個(gè)時(shí)鐘誤差不超過(guò)，就必須至少/(2)秒鐘重新同步一次。時(shí)鐘速率不正確時(shí)，

2、機(jī)器時(shí)間與UTC之間的關(guān)系基本思想系統(tǒng)中有唯一一臺(tái)時(shí)間服務(wù)器接收UTC時(shí)間，其他機(jī)器則必須與時(shí)間服務(wù)器同步。每臺(tái)機(jī)器以不大于/(2)秒的周期定期向時(shí)間服務(wù)器發(fā)送消息詢問(wèn)當(dāng)前時(shí)間時(shí)間服務(wù)器收到后發(fā)送消息告知當(dāng)前時(shí)間CUTC發(fā)送者收到服務(wù)器消息后將時(shí)鐘調(diào)整為CUTC2、Cristian時(shí)鐘同步算法Cristian算法：從服務(wù)器得到當(dāng)前時(shí)間問(wèn)題時(shí)間回調(diào)將導(dǎo)致嚴(yán)重后果逐步調(diào)整時(shí)鐘：即正常一個(gè)時(shí)鐘中斷將時(shí)鐘加10毫秒，而需要慢下來(lái)時(shí)則一個(gè)中斷加9毫秒，需要快時(shí)加11。傳輸延遲的問(wèn)題測(cè)量估算法Cristian時(shí)鐘同步算法思想主動(dòng)式服務(wù)與Cristian算法中的被動(dòng)式時(shí)間服務(wù)器相反過(guò)程服務(wù)器主動(dòng)定期詢問(wèn)每臺(tái)

3、機(jī)器的時(shí)間服務(wù)器基于客戶的回答，告知它們撥快或者撥慢3、Berkeley時(shí)鐘同步算法Berkeley時(shí)鐘同步算法Cristian算法和Berkeley算法集中式的算法。平均值算法非集中式算法將時(shí)間劃分為固定長(zhǎng)度的再同步間隔R第i次同步開(kāi)始于T0+iR，結(jié)束于T0+(i+1)R每次同步間隔開(kāi)始，每臺(tái)機(jī)器廣播自己的時(shí)間對(duì)于某一具體的機(jī)器，當(dāng)所有的同步廣播都到達(dá)后，它根據(jù)所有的時(shí)間執(zhí)行某一平均算法得一新值，再根據(jù)新值調(diào)整時(shí)鐘。思考：各機(jī)器計(jì)算的新值一樣嗎？4、平均值算法二、邏輯時(shí)鐘同步1、基本概念許多應(yīng)用中，并不嚴(yán)格需要所有機(jī)器都與UTC時(shí)間保持一致，而只需要所有機(jī)器時(shí)間相同就夠了，即系統(tǒng)保持一個(gè)內(nèi)

4、部一致的時(shí)鐘。這種時(shí)鐘稱為邏輯時(shí)鐘。更進(jìn)一步，很多問(wèn)題中根本就不需要時(shí)間嚴(yán)格一致，而只是需要多個(gè)事件的發(fā)生順序一致就可以?；靖拍顑蓚€(gè)概念：先發(fā)生關(guān)系ab事件a先發(fā)生，然后b才發(fā)生如果a和b是同一個(gè)進(jìn)程的兩個(gè)事件，如果a在b之前發(fā)生，則ab為真如果a是一個(gè)進(jìn)程發(fā)送消息的事件，b是另一個(gè)進(jìn)程的接收消息事件，則ab為真并發(fā)事件如果x和y事件發(fā)生在兩個(gè)互不交換消息的進(jìn)程中，xy不真，yx也不真邏輯同步問(wèn)題若干分布式進(jìn)程協(xié)同工作對(duì)于任一事件a，為它分配一個(gè)所有進(jìn)程都認(rèn)可的時(shí)間值C(a)如果ab，則C(a) C(b) 時(shí)鐘值C必須保證始終前進(jìn)，不能倒退，所以校正時(shí)間的操作是加上一個(gè)正值，而不是減去一個(gè)正

5、值2、 Lamport時(shí)間戳Lamport時(shí)間戳Lamport算法直接遵循先發(fā)生關(guān)系所有消息都必須攜帶發(fā)送者時(shí)鐘的時(shí)間當(dāng)接受者發(fā)現(xiàn)自己時(shí)鐘比發(fā)送者的時(shí)鐘早時(shí)，接受者將它的時(shí)鐘調(diào)到一個(gè)比發(fā)送時(shí)間大1的值同一進(jìn)程的每?jī)蓚€(gè)事件之間，必須至少滴答（即一個(gè)時(shí)鐘中斷）一次Lamport時(shí)間戳提供了一種對(duì)系統(tǒng)中所有事件完全排序的方法000612182430364248546000081624324048566472800010203040506070809010000612182430364248707600081624324048616977850010203040506070809010Lamport算

6、法校正三個(gè)進(jìn)程的不同時(shí)鐘三、選舉算法1、基本概念為什么要進(jìn)行選舉？許多分布式算法中需要一個(gè)進(jìn)程來(lái)充當(dāng)協(xié)調(diào)者、發(fā)起者或者其他特殊角色兩種基本選舉算法欺負(fù)算法環(huán)算法2、欺負(fù)算法基本思想比大小最大者獲勝當(dāng)選欺負(fù)算法過(guò)程當(dāng)任何一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請(qǐng)求時(shí)，它就發(fā)起一次選舉P向所有編號(hào)比它大的進(jìn)程發(fā)送一個(gè)ELECTION消息。如果無(wú)人響應(yīng)，P獲勝，成為協(xié)調(diào)者。如果有編號(hào)比它大的進(jìn)程響應(yīng)，則由響應(yīng)者接管選舉工作。P的工作完成。最后選舉獲勝者向所有進(jìn)程發(fā)送選舉獲勝的消息，聲明它成為協(xié)調(diào)者。欺負(fù)選舉算法3、環(huán)算法基本過(guò)程所有進(jìn)程按照物理或者邏輯的順序組成一個(gè)邏輯的環(huán)當(dāng)任何一個(gè)進(jìn)程注意到協(xié)調(diào)者不工作時(shí)，它就

7、自己構(gòu)造一個(gè)帶有它自己進(jìn)程號(hào)的ELECTION消息，發(fā)給它的后繼者如果后繼者崩潰了，則跳過(guò)發(fā)給下一個(gè)接收者將自己的進(jìn)程號(hào)加入消息中，繼續(xù)傳遞消息。最后消息返回到選舉發(fā)起者，它計(jì)算出協(xié)調(diào)者之后發(fā)送COORDINATOR消息宣布協(xié)調(diào)者消息環(huán)系統(tǒng)環(huán)一周后被刪除環(huán)選舉算法四、互斥基本概念分布式互斥解決分布式共享資源并發(fā)訪問(wèn)問(wèn)題比單機(jī)系統(tǒng)互斥復(fù)雜算法集中式互斥算法分布式互斥算法令牌環(huán)算法1、集中式算法最簡(jiǎn)單的一種互斥算法基本過(guò)程：選舉一個(gè)協(xié)調(diào)者任何一個(gè)進(jìn)程要進(jìn)入臨界區(qū)，向協(xié)調(diào)者發(fā)送申請(qǐng)消息協(xié)調(diào)者根據(jù)臨界區(qū)的使用情況同意或者拒絕申請(qǐng)者的請(qǐng)求協(xié)調(diào)者拒絕申請(qǐng)者的方式可以發(fā)送拒絕消息或者不應(yīng)答，但都將請(qǐng)求放入隊(duì)

8、列中集中式互斥算法優(yōu)點(diǎn)：保證了互斥的實(shí)現(xiàn)公平先來(lái)先服務(wù)沒(méi)有進(jìn)程會(huì)處于永遠(yuǎn)等待狀態(tài)，不會(huì)出現(xiàn)餓死易于實(shí)現(xiàn)缺點(diǎn)：協(xié)調(diào)者是一個(gè)單故障點(diǎn)，如果協(xié)調(diào)者崩潰，則整個(gè)系統(tǒng)癱瘓協(xié)調(diào)者可能成為性能的瓶頸集中式算法2、分布式互斥算法基本過(guò)程：當(dāng)一個(gè)進(jìn)程想進(jìn)入臨界區(qū)時(shí)，它構(gòu)造一個(gè)含有目標(biāo)臨界區(qū)名字、本進(jìn)程號(hào)和當(dāng)前時(shí)間的消息，發(fā)給所有進(jìn)程。一個(gè)進(jìn)程收到另一個(gè)進(jìn)程的請(qǐng)求消息時(shí)，根據(jù)自己與目標(biāo)臨界區(qū)的狀態(tài)關(guān)系反應(yīng)：若接受者不在也不想進(jìn)入臨界區(qū)，發(fā)送OK消息接受者已經(jīng)在臨界區(qū)則不應(yīng)答，只是把請(qǐng)求放入隊(duì)列接受者亦欲進(jìn)入臨界區(qū)，則將收到的請(qǐng)求時(shí)間戳與它發(fā)送的請(qǐng)求時(shí)間戳比較，早的獲勝進(jìn)入。發(fā)送者一直等待至其他所有進(jìn)程返回OK消息，之后進(jìn)入臨界區(qū)，使用完畢向隊(duì)列中的進(jìn)程發(fā)送OK消息，刪除自己的任務(wù)。分布式互斥算法優(yōu)點(diǎn)：實(shí)現(xiàn)了分布式互斥不會(huì)發(fā)生死鎖或餓死不存在單個(gè)故障點(diǎn)缺點(diǎn)：反而有n個(gè)故障點(diǎn)，實(shí)際上比集中式算法差了n倍需要自己維護(hù)組成員清單，處理進(jìn)入、離開(kāi)組和崩潰進(jìn)程的能力比較差總之，實(shí)際上比集中式算法更慢，更復(fù)雜，花費(fèi)更高，而且更脆弱。意義：說(shuō)明分布式算法至少可以實(shí)現(xiàn)。分布式互斥算法3、令牌