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

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

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

3、收器n接收di = c(tnow ti)d =di+crd = r 時(shí)鐘誤差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)星、接收器的時(shí)鐘精度；n信號(hào)傳播速度4rr424243rr323232rr222221rr12121d)zz()()(d)zz()()(d)zz()()(d)zz()()(rrrrrrrryyxxyyxxyyxxyyxx9時(shí)鐘同步算法如何與現(xiàn)實(shí)時(shí)鐘同步如何使不同機(jī)器之間相互同步n設(shè)進(jìn)程P的機(jī)器時(shí)鐘值Cp(t),nt 為UTC時(shí)間n最大偏移率（）n精確時(shí)

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

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

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

7、a)表示事件a的時(shí)鐘值。性質(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算法時(shí)時(shí)間間慢慢快快慢慢快快三個(gè)進(jìn)程，各有自己的局部時(shí)鐘，它們速率不同通過(guò)Lamport算法，校正時(shí)鐘19Lamport算法Pi在執(zhí)行一個(gè)事件之前，Pi執(zhí)行CiCi+1Pi在發(fā)送消息m給Pj時(shí)，時(shí)間戳ts(m) CiPj接受到消息m后，CjmaxCj，ts(m)20舉例：全序多播（1）n 問(wèn)題：兩個(gè)進(jìn)程分別對(duì)同一個(gè)復(fù)制數(shù)據(jù)庫(kù)進(jìn)行更新時(shí)，造成不一致?tīng)顟B(tài)n 原因：全局次序不一致。u1u2; u2u1NoI

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

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

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

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

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