【文章內容簡介】 時間（續(xù)） ? 使用這種方法，分布式系統(tǒng)中將時間分配給所有事件的方法 遵照如下規(guī)則 ： ? 若在同一進程中 a發(fā)生在 b之前，則 C(a)C(b)； ? 若 a和 b分別代表發(fā)送消息和接收消息，則C(a)C(b)； ? 對所有事件 a和 b， C(a)≠C(b) ? 這個算法給我們提供了對系統(tǒng)中所有的事件進行排序的一種方法，許多其它的分布式算法也需要這種排序以避免混亂。 53 四、時鐘同步算法 ? 所有算法都有相同的 系統(tǒng)基礎模型： ? 每臺機器上假設都有一個每秒產生 H次中斷的計時器。當時間到時，中斷處理程序將軟時鐘加 1，軟時鐘記錄從過去某一約定值開始的中斷次數(shù)。我們把這個時鐘值記為 C。 ? 更特殊的，當 UTC時間為 t時，在機器 p上的時間值是Cp(t)， ? 最 完美的情況 是對所有的 p和 t，有 Cp(t)=t，換言之，dC/dt理想值為 1。 ? UTC：世界協(xié)調時間 (Universal Time Coordinated)。 GPS 系統(tǒng)中有兩種時間區(qū)分，一為 UTC，另一為 LT（地方時）。兩者的區(qū)別為時區(qū)不同， UTC就是 0時區(qū)的時間，地方時為本地時間。 54 四、時鐘同步算法（續(xù)） ? 真正計時器并不是每秒精確的中斷 H次，理論上當 H=60時，計時器每小時應該產生 216,000個滴答。 ? 實際上，用現(xiàn)代計時時鐘芯片可以獲得相關的延遲是 105，意味著一臺機器每小時可以獲得 215,998～ 216,002范圍的滴答，若存在某一常數(shù) ρ，便有： ?? ???? 11 dtdC55 四、時鐘同步算法（續(xù)） ? 計時器可以在它規(guī)定的范圍內工作，制造商標明的常數(shù) ρ是最大漂移速度 。稍慢的、精確的、稍快的時鐘如圖 227所示。 56 四、時鐘同步算法（續(xù)） ? 若兩個時鐘相對于 UTC時間以相反方向漂移，在它們同步后的 Δt時間內，它們可能的差值為2ρΔt，若操作系統(tǒng)的設計者要保證每兩個時鐘之間的相差不超過 δ，時鐘必須至少在每 δ/(2ρ)秒內再同步一次（用軟件方法），不同算法實現(xiàn)再同步的方法不同。 57 ? 非常適合于 只有一臺機器上有 WWV接收器 ，其它所有機器與它同步的系統(tǒng)。 ? 把擁有 WWV接受器的那臺機器稱作 時間服務器 ，算法是基于 Cristian(1989)和以前的一些工作。 ? 每臺機器以小于或等于δ/(2ρ)秒的周期定期地向時間服務器發(fā)送消息詢問當前的時間，時間服務器接到消息后就盡快回答含有當前時間 CUTC值的消息，如圖 228所示。 58 （續(xù)） ? 當發(fā)送者得到回答后，就將它的時鐘設為 CUTC，但是這種算法有兩個問題： ? 第一個重要的問題是時間決不能倒退 ，若發(fā)送者的時鐘快， CUTC將會比發(fā)送者的時間值 C小，若把發(fā)送者的時間值直接改成 CUTC會導致嚴重的錯誤，比如在時鐘變化后，編譯產生的目標文件的時間早于時鐘變化前源文件的修改時間。 ? 這種 變化必須逐步進行 ，一種方法是假設將計時器設置為每秒產生 100次中斷，通常，每次中斷將時間加 10毫秒，當時鐘需要慢下來時，中斷服務程序每次僅加 9毫秒，直到調整好為止。同樣時鐘要加快時，每次中斷服務程序將時鐘加 11毫秒， 而不是立即把時間調到所需要的值 。 59 （續(xù)） ? 另一個小問題是從時間服務器端發(fā)送的應答到發(fā)送者要花費時間 ，這種延遲可能較大，而且隨著網絡負荷的改變而改變。 ? Cristian的處理方法是 試圖測量這個延遲值。 ? 最簡單的方法：發(fā)送者精確地記錄從向時間服務器發(fā)送請求到接收到應答的時間間隔，假設起始時間是 T0與結束時間 T1，他們都是通過同一個時鐘來測量的，就算發(fā)送者的時鐘與 UTC有一定的差值，它所測得的時間間隔還是較精確的。在沒有其它任何信息時，消息傳送時間的最佳估計值是（ T1T0） /2，當應答消息到達時， 消息中的時間值再加上此值就得到了當前時間服務器的時間估計值 ，如果理論上知道了最小的傳送時間，那么與時間估算相關的其它性質也能推算出來。 60 （續(xù)） ? 如果知道時間服務器 中斷處理的時間和處理消息的時間 ，這樣的估算還能進一步改進，設中斷處理的時間是 I，那么傳輸時間間隔為 T1T0I，所以估算單向傳輸時間為它的一半。 ? 系統(tǒng)中確實存在著從 A到 B的消息和從 B到 A的消息傳輸路徑不同，因此就有不同的傳輸時間，但我們目前先不考慮這種情況。 ? 為了提高精確度， Cristian建議不要只做一次測量，而做一系列測量，測量中 T1T0超出一定范圍就認為是網絡阻塞，為不可信值。對剩余的測量值取平均值會得到較好的估算值，也就是說， 最快返回的消息是最精確的，因為消息遇到阻塞最少，所以它最能代表純粹的傳輸時間。 61 ? 在 Berkeley UNIX中采取了完全相反的方法，這里的時間服務器 （實際是時間守護進程）是 主動 的，它定期地詢問每臺機器的時間。然后基于這些回答，計算出平均值并告訴所有的機器將它們的時鐘撥快或撥慢到一個新的值。這種方法 適合于沒有 WWV接收器的系統(tǒng) ，時間守護進程的時間必須由操作者 定期地手工設置 ，這種方法如圖 229所示。 62 （續(xù)） ? (a),時間守護進程在 3:00把它的時間告訴其它機器，并且詢問它們各自的時間 ? (b)，各機器將它們各自的時間與時間守護進程時間的差值告訴時間守護進程， ? (c)守護進程計算出它們的平均值，通知各機器如何調整各自的時間。 63 ? 上述兩種方法都高度集中的，有不足之處。存在一些非集中式算法，如： ? 一種分布式時鐘同步算法： ? 它是 將時間劃分成固定長度的再同步間隔 ，第 i次間隔開始于 T0+iR，而結束于 T0+(i+1)R，這里的 T0是過去某一約定的時間， R是一個系統(tǒng)參數(shù)。 ? 在每次間隔的開始處，每臺機器根據自己的時鐘廣播發(fā)送當前的時間，由于在不同機器上的時鐘不可能完全同速工作，這種廣播就不會完全同時發(fā)生。 64 （續(xù)） ? 在機器廣播發(fā)送時間之后，它啟動本地計時器收集在 S時間間隔中到達的其它廣播 ，當所有廣播到達后，執(zhí)行一個算法，得到新的時間值。 ? 僅將這些值取平均值； —— 最簡單 ? 先除去 m個最大值和 m個最小值，平均其余值。去掉兩端值可認為是一種對 m個錯誤時鐘發(fā)出毫無意義的時間值的一種自我保護。 ? 給每條消息值加上一個從源到目的地的傳送時間估計值，這種估計值可參考網絡的拓撲結構或計算試探消息的響應時間而得出 65 ? 對 使用 UTC進行同步又要求特別精確的系統(tǒng) 來說，可給系統(tǒng)安裝如 WWV， GEOS或其它 UTC源的 多接收器 來實現(xiàn)的。 ? 時間源自身固有的不精確性以及信號傳送的不定性，最好的操作系統(tǒng)能做的也只是建立一個UTC時間范圍 。 ? 一般來說，不同的時間源會產生不同的時間范圍，這種范圍需要機器和它們達成一致。 66 （續(xù)） ? 為達到一致，每個具有 UTC源的處理機定期在每一 UTC精確分的開始處廣播其時間范圍， 但 ? 沒有處理機會同時獲得時間包， ? 傳輸和接收延遲依賴于纜線的距離和包必須經過的網關數(shù)，它對于每一對 UTC源和處理機之間都不相同。 ? 其它因素，如多臺機器要同時在以太網上傳輸而發(fā)生的碰撞。 ? 更進一步，如一臺處理機忙于處理以前的包，它可能在相當長的幾微秒內不去理會到來的時間包，從而導致了時間的不確定性。 67 （續(xù)） ? 解決 ： Open Software Foundation（開放軟件組織）的分布式計算環(huán)境的處理方法 ? 某個接收器接收到所有時間源的 UTC時間范圍后， ? 首先檢查是否有與其他范圍不相交的 UTC范圍。如果有，這些 UTC范圍一定是錯誤的，棄而不用。剩余的時間范圍都是準確的 UTC時間所在的范圍； ? 因此接著就求出這些范圍相交的部分； ? 最后將相交部分的中點作為準確的 UTC時間，并將內部時鐘設置為該值。 68 （續(xù)） 69 ? 涉及多個進程的系統(tǒng)使用臨界區(qū)容易編程 ? 當一個進程必須讀或修改某些共享數(shù)據結構時，它首先進入臨界區(qū)獲得 互斥鎖 ，保證沒有其它的進程能同時使用該共享數(shù)據結構。 ? 在單處理機系統(tǒng)中，使用信號量、管程和一些近似的結構來保護臨界區(qū)。 ? 幾個例子：在分布式系統(tǒng)中臨界區(qū)和互斥是如何實現(xiàn)的。 70 一、集中式算法 ? 在分布式系統(tǒng)中獲得互斥的最直接方法是 仿照單處理機系統(tǒng) 的方法， 選一個進程為協(xié)調者 （比如在最大網絡地址機器上運行的進程）。無論什么時候進程要進入臨界區(qū)，它將向協(xié)調者發(fā)送請求消息，說明它想進入哪個臨界區(qū)并希望獲得允許。如果當前該臨界區(qū)內沒有其它任何進程，協(xié)調者就發(fā)送允許進入消息，如圖 230(a)所示。當應答到達時，請求者就可以進入臨界區(qū)。 71 一、集中式算法 （續(xù)） ? 現(xiàn)在假設有另一個進程，如圖 230(b)所示，請求進入同一個臨界區(qū)，協(xié)調者知道該臨界區(qū)已有一個進程，所以不能同意該請求，最好的辦法是發(fā)出拒絕允許應答。而在圖 230中，協(xié)調者 回避應答 ，這樣就阻塞了進程 2，使它等待應答。另一方面，協(xié)調者還可以發(fā)送“ 拒絕請 求”應答。 兩種方法都會把進程 2放入等待隊列，等待臨界區(qū)的釋放。 72 一、集中式算法 （續(xù)） ? 當進程 1從臨界區(qū)退出時，它向協(xié)調者發(fā)送釋放互斥消息訪問，如圖 230(c)所示，協(xié)調者從推遲請求隊列中取出最前面的進程，向它 發(fā)送允許進入消息 。如果該進程仍然阻塞（即，這是第一條發(fā)給它的允許進入消息）它去除阻塞且進入臨界區(qū)；如果明確發(fā)送一消息拒絕它進入臨界區(qū)，此進程應該不時地查詢輸入的消息，或者接著將它阻塞等待許可響應。不管怎么樣， 當它發(fā)現(xiàn)允許進入時，它就可以進入臨界區(qū) 。 73 一、集中式算法 （續(xù)） ? 優(yōu)點： ? 算法保證了互斥的實現(xiàn)，協(xié)調者僅能讓某一進程在某一時刻進入臨界區(qū)。 ? 也很 公平 ，因為允許請求的順序同它們接收的順序一致，沒有進程永遠等待（ 沒有饑餓 ）。 ? 容易實現(xiàn)，每用一次臨界區(qū)只需 3條消息（請求，允許，釋放），它不僅能管理臨界區(qū)，也可用于更普遍的資源分配。 ? 缺點： ? 協(xié)調者是一個單點故障，如它崩潰，整個系統(tǒng)將癱瘓，如果進程在請求之后被阻塞，以上這兩種情況都沒有消息返回，請求者不能從“拒絕請求”中辨認出協(xié)調者已崩潰。 ? 此外，大系統(tǒng)中單協(xié)調者會成為執(zhí)行的瓶頸。 74 二、分布式算法 ? 分布式互斥算法 ，第一次出現(xiàn)的是在 1978年 Lamport關于時鐘同步的論文中，后來 Ricart 和 Agrawale對它作了進一步的改進， ? 算法前提： Ricart 和 Agrawale算法 要求系統(tǒng)中所有事件都是全序的 。 也就是說，對任何事件組如消息，哪個先發(fā)生必須無歧異。 ? 算法： ? 當一個進程想進入臨界區(qū)時，它要 建立 一個包括它要進入的臨界區(qū)的名字、處理機號和當前時間的 消息 ， ? 然后將消息發(fā)送給所有其它進程。概念上講也包括發(fā)送給它自身。發(fā)送的消息假設是可靠的，即每條消息都應該被確認， 如可能應使用可靠的組通信 ，避免使用單個的消息通信。 75 二、分布式算法 （續(xù)） ? 當一個進程接收另一個進程請求消息時，根據接收方的狀態(tài)以及臨界區(qū)的名字。有三種情況要加以區(qū)別： 1. 若接收者不在臨界區(qū)中，也不想進入臨界區(qū)，它就向發(fā)送者發(fā)送 OK消息。 2. 若接收者已經在臨界區(qū)中，它就不必回答，而是負責對請求隊列排隊。 3. 若接收者要進入臨界區(qū)，但是還沒有進入時，它要將發(fā)來的消息和它發(fā)送給其余進程的時間戳對比，取小的那個，如果來的消息的時戳小，接收者發(fā)送OK消息，如果接收者本身的時間戳更小，那么接收者負責排列請求隊列而不發(fā)送任何消息。 76 二、分布式算法 （續(xù)） ? 在發(fā)送完允許進入臨界區(qū)的請求后，進程將不做任何事，僅 等待所有的允許消息 ，一旦得到允許，它就進入臨界區(qū)，它從臨界區(qū)退出時，向隊列中的所有的進程發(fā)送 OK消息，并把它從隊列中刪除。 77 二、分布式算法 （續(xù)） ? 分析： 如果沒有沖突，則正常工作。但是，假設兩個進程要同時試圖進入一個臨界區(qū)，如圖231(a)所示 78 二、分布式算法 （續(xù)） ? 進程 0發(fā)出時戳為 8的請求，而同時進程 2發(fā)出時間戳為 12的請求。進程 1不想進入臨界區(qū)，所以它向 2個發(fā)送者發(fā)回OK。進程 0和 2同時發(fā)現(xiàn)沖突，比較時間戳，進程 2發(fā)現(xiàn)自己的大，它只好同意進程 0進入臨界區(qū)，向 0發(fā)送 OK，進程 0就把進程 2的請求排在隊列中，為以后處理用，自己進入臨界區(qū)，如圖 231(b)所示。 79 二、分布式算法 （續(xù)） ? 當進程 0結束退出