第6章 高級操作系統(tǒng)同步化

1、第第6章章 同步化 2主要內(nèi)容6.1 物理時鐘同步6.2 邏輯時鐘同步6.3 互斥控制6.4 選舉算法36.1物理時鐘同步n分布式協(xié)同處理n基于時間的同步n分布式算法的特點相關(guān)信息散布在多個場地上每個進(jìn)程只能基于本地信息做決定應(yīng)避免因單點失敗造成整個系統(tǒng)的失敗不存在公共時鐘或精確的全局時間4時鐘同步問題n例：makefile誤差時間時間#腳本命令output.o ： cc C output.c5遙遠(yuǎn)的星系遙遠(yuǎn)的星系在n天后的日中天，地球旋轉(zhuǎn)不到360物理時鐘與現(xiàn)實時鐘n日中天（transit of the sun）：太陽升到一天的最高點n太陽日：連續(xù)的兩次日中天的時間n太陽年：地球圍繞太陽旋轉(zhuǎn)

2、360（一周）。n太陽秒：solar-day/24*3600=solar-day/86400n平均太陽秒：n solar-days/n*86400n如，格林威治時間第0個日中天第n個日中天6現(xiàn)實時鐘nTAI秒：國際原子時間n銫133原子鐘：9,192,631,770次躍遷/1秒n巴黎BIH統(tǒng)計50個實驗室原子鐘后的平均值nUTC秒：世界時間n在UTC秒中加入閏秒（TAI秒長度恒定，但比太陽秒長度少）n時間服務(wù)：n美國WWV電臺(NIST)、GEOS衛(wèi)星1020為了與TAI保持同步，在UTC中引入閏秒7例：時間的應(yīng)用-GPS全球定位系統(tǒng)nGPS衛(wèi)星n使用4個原子時鐘n周期地廣播定位消息n即，n接

3、收器n接收di = c(tnow ti)d =di+crd = r 時鐘誤差22)()(ririyyxx(1)(2)(3)8例：GPS全球定位系統(tǒng)n求解方程組（擴(kuò)展到3維，需4顆衛(wèi)星）n可求出（xr,yr,zr）,以及rn誤差因素n衛(wèi)星的位置n衛(wèi)星、接收器的時鐘精度；n信號傳播速度4rr424243rr323232rr222221rr12121d)zz()()(d)zz()()(d)zz()()(d)zz()()(rrrrrrrryyxxyyxxyyxxyyxx9時鐘同步算法如何與現(xiàn)實時鐘同步如何使不同機(jī)器之間相互同步n設(shè)進(jìn)程P的機(jī)器時鐘值Cp(t),nt 為UTC時間n最大偏移率（）n精確時

4、鐘： dC/dt =1n快時鐘： dC/dt 1n慢時鐘： dC/dt 110時鐘同步算法時鐘校正n設(shè)兩個時鐘都存在誤差率，允許兩者之間誤差；n由于最大可能誤差2t ，則t /2n需每隔/(2)校準(zhǔn)時間，進(jìn)行校正n校準(zhǔn)原則：單調(diào)遞增n假設(shè)：每秒產(chǎn)生100次中斷，每次中斷將時間加10毫秒n若調(diào)慢時鐘，中斷服務(wù)程序每次只加9毫秒；n若加快時鐘，則加11毫秒。11網(wǎng)絡(luò)時間協(xié)議nChristian算法n時間服務(wù)器，可接受WWV的UTC時間n每隔/(2)，客戶機(jī)向服務(wù)器詢問時間n服務(wù)器返回CUTCn客戶機(jī)校正自己時間=CUTC+傳播時間n傳播時間=(T1-T0-I)/2nT0:請求時間，T1:到達(dá)時間n

5、I:中斷處理時間n假定雙向路徑相同n優(yōu)化處理n設(shè)定傳播閾值,超出閾值，認(rèn)定無效12網(wǎng)絡(luò)時間協(xié)議n時間服務(wù)請求過程參數(shù)n假定雙向路徑相同nT1:A請求時間， T2:B接收時間nT3:B發(fā)送時間， T4:A接收時間n傳輸延時 = dTreqdTresn時間偏差nT1=T2 - dTreq + nT4=T3+dTres+ n平均延時=(dTreq+dTres)/2 n=T4-T3-dTres=T4 -T3 - =時間服務(wù)器客戶2)TT()TT(2)TT()TT(341234122)TT()TT(342113Berkeley 算法 主動式方法n時間監(jiān)控器定期查詢其他機(jī)器時間n計算出平均值n通知其他機(jī)器

6、調(diào)整時間14無線網(wǎng)絡(luò)中的時鐘同步q 參考廣播同步協(xié)議（RBS）普通的網(wǎng)絡(luò)延時關(guān)鍵路徑RBS的網(wǎng)絡(luò)延時關(guān)鍵路徑15無線網(wǎng)絡(luò)中的時鐘同步q 參考廣播同步協(xié)議（RBS）q 一個節(jié)點廣播一個消息m后，其他節(jié)點p記錄接收時間Tp,mMTTqpMkkqkp1,)(,偏差166.2 邏輯時鐘同步n計時器：石英晶體+計數(shù)器n時鐘偏差（clock skew）n物理時鐘：真實時間n邏輯時鐘：相對時間n“之前”關(guān)系: n事件a在b之前出現(xiàn)，則abna為發(fā)送消息m，b為接收m，則abn具有傳遞性：ab, bc,則acn并發(fā)事件（concurrent）n兩個事件相互對立。既不ab，不 b a17Lamport算法nC(

7、a)表示事件a的時鐘值。性質(zhì)：nif ab;則C(a)C(b)na,b C(a) C(b)nC是遞增的n校正算法nab，nif C(b)C(a), 則C(b) = C(a) +118Lamport算法時時間間慢慢快快慢慢快快三個進(jìn)程，各有自己的局部時鐘，它們速率不同通過Lamport算法，校正時鐘19Lamport算法Pi在執(zhí)行一個事件之前，Pi執(zhí)行CiCi+1Pi在發(fā)送消息m給Pj時，時間戳ts(m) CiPj接受到消息m后，CjmaxCj，ts(m)20舉例：全序多播（1）n 問題：兩個進(jìn)程分別對同一個復(fù)制數(shù)據(jù)庫進(jìn)行更新時，造成不一致狀態(tài)n 原因：全局次序不一致。u1u2; u2u1NoI

8、mage21舉例：全序多播（2）n解決方案：全序多播n發(fā)送進(jìn)程多播發(fā)送消息m時，給m帶上當(dāng)前時間戳tsn當(dāng)接收進(jìn)程收到消息m后，存放其局部隊列q，按時間戳排序n接收進(jìn)程向所有進(jìn)程多播發(fā)送應(yīng)答n當(dāng)消息m被所有進(jìn)程應(yīng)答，且排在隊列q隊首后，方可處理n定理：各個進(jìn)程的局部隊列的值最終都相同22舉例：全序多播（3）n舉例q1q2u1u2(1)u1u2u1u2(2）u1u2a11u1u2a22(3)q1q2u1u2a11a22u1u2a11a22(4)u1u2a11a22a12u1u2a11a22a21(5)q1q2u1u2a11a22a12a21u1u2a11a22a12a21(6)a11, a22本

9、地消息a12,a21遠(yuǎn)地消息23向量時鐘n因果性(causality):n如果事件a，b存在因果關(guān)系。a為因，b為果，則C(a)C(b)nVector Clockn如果VC(a)n/2個協(xié)作者中獲得多數(shù)投票。n通信量：3mk個消息，k表示可能需要進(jìn)行多次嘗試。n優(yōu)點：當(dāng)某個協(xié)作者崩潰時，能快速恢復(fù)n缺點：重置會導(dǎo)致協(xié)作者忘記它前面已授權(quán)某進(jìn)程訪問資源的許可，在其恢復(fù)后，可能錯誤地把該許可又賦給另外一個進(jìn)程。31分布式算法（Ricart-Agrawala算法）n在一個進(jìn)程P打算進(jìn)入臨界區(qū)R之前，向所有其他進(jìn)程廣播消息 n當(dāng)一個進(jìn)程P收到消息后，做如下決定：若P不在臨界區(qū)R中，也不想進(jìn)入R，它就向

10、P發(fā)送OK；若P已經(jīng)在臨界區(qū)R中，則不回答，并將P放入請求隊列；若P也同時要進(jìn)入臨界區(qū)R，但是還沒有進(jìn)入時，則將發(fā)來的消息和它發(fā)送給其余進(jìn)程的時間戳對比。如果P時間戳小，則向P發(fā)送OK;否則，不回答，并將P放入請求隊列；n當(dāng)P收到所有的OK消息后，進(jìn)入R。否則，等待。n當(dāng)P退出R時，如果存在等待隊列，則取出一個請求者，向其發(fā)送OK消息。32分布式算法舉例舉例： 共有0，1，2三個進(jìn)程。進(jìn)程0，2申請進(jìn)入臨界區(qū)02002233分布式算法評價n缺點：n點失敗n點瓶頸2（n-1)個消息n改進(jìn)方案：n超時重發(fā)n組通信n簡單多數(shù)同意（1/2）34令牌環(huán)算法構(gòu)造一個邏輯環(huán)，得到令牌才可進(jìn)入臨界區(qū)問題：令牌

11、丟失檢測35三種互斥算法的比較算法每次進(jìn)出需要的消息進(jìn)入前的延遲（按消息次數(shù)）存在問題集中式32協(xié)調(diào)者崩潰分布式2（n-1）2（n-1）任何一個進(jìn)程崩潰令牌環(huán)1到0到n-1丟失令牌，進(jìn)程崩潰366.4 選舉算法n作用：n在分布式進(jìn)程之間做出統(tǒng)一的的決定n例如：確定協(xié)調(diào)者n前提：n每個進(jìn)程具有唯一的號碼，如IP地址n每個進(jìn)程知道其它進(jìn)程的號碼n選舉標(biāo)準(zhǔn)：n確定具有最大號碼的進(jìn)程37霸道（Bully）算法v將進(jìn)程進(jìn)行排序nP向高的進(jìn)程發(fā)E消息n如果沒有響應(yīng)，P選舉獲勝n如果有進(jìn)程Q響應(yīng),則P結(jié)束，Q接管選舉并繼續(xù)下去。45656465638環(huán)算法n所有進(jìn)程按邏輯或物理次序排序，形成一個環(huán)n當(dāng)一個進(jìn)

12、程P發(fā)現(xiàn)協(xié)調(diào)者C失效后，向后續(xù)進(jìn)程發(fā)送E消息n每個進(jìn)程繼續(xù)向后傳遞E消息，直到返回P1.P再將新確定的協(xié)調(diào)者C傳給所有進(jìn)程5239無線網(wǎng)絡(luò)系統(tǒng)的選舉算法n例：選舉一個協(xié)調(diào)者，它具有最大的能力n1、發(fā)起者，提出選舉40無線網(wǎng)絡(luò)系統(tǒng)的選舉算法n2、向鄰居節(jié)點擴(kuò)展，形成一個生成樹（spanning tree）41無線網(wǎng)絡(luò)系統(tǒng)的選舉算法n3、沿生成樹向父節(jié)點返回i，cmax，cmax為最大值n4、發(fā)起者，向其余節(jié)點發(fā)布協(xié)調(diào)者42大型系統(tǒng)的選舉n大型系統(tǒng)中需要選舉多個節(jié)點n如p2p系統(tǒng)中的超級節(jié)點n對如何選擇超級節(jié)點（superpeer）的要求:u普通節(jié)點對超級節(jié)點的訪問延遲要小u超級節(jié)點應(yīng)均勻地分布在覆蓋網(wǎng)絡(luò)中u相對于覆蓋網(wǎng)絡(luò)中的節(jié)點數(shù)量，應(yīng)有一定數(shù)量的預(yù)先定義好的超級節(jié)點u每個超級節(jié)點所服務(wù)的普通節(jié)點個數(shù)不能超過規(guī)定