【正文】 場點上的文件可通過把該場點名加在相應文件的路徑名之首來進行訪問。這種方案 容易實現(xiàn) ，用戶也比較 容易掌握 。 ? 若一文件有多個副本且位于不同的場點上，它們就會有不同的名字，那么對它們的任何更改都容易導致 不一致性。一般說來，這是分布式系統(tǒng)的設計者所不希望的。 ? 這也可以說是 性能對靈活性 的問題。這使得可對系統(tǒng)中的遠程或本地資源 (對象 )進行一致的存取。 ? 移動文件要注意改名，后續(xù)操作也要注意名字問題 ? 多副本情況一致性的維護問題 ? 透明性的問題 26 三、唯一標識符和字符串名 ? UID ? 系統(tǒng)中的每一對象給定一個唯一的標識符 (UID)，即在系統(tǒng)中，它唯一地指稱該對象。特別，當一對象從一場點遷移到另一場點時其 UID 仍保持不變。 ? UID 也可作為一種權(quán)限使用 ，此時，與其相關的對象是受保護的，它既不能由用戶改變，也不應被用戶忘卻。 ? 此外，它還可含有一些 隨機生成的位 ，使得它難以猜測，從而起到保密作用。 28 三、唯一標識符和字符串名（續(xù)） 總結(jié) ? 在大多數(shù)系統(tǒng)中，字符串名主要供用戶使用，而 UID僅供操作系統(tǒng)使用。 ? 操作系統(tǒng)提供了從字符串名到 UID 的映射。名字服務器管理著包含有“名字及其物理地址”的對照表，系統(tǒng)中的所有服務程序都由名字服務器來尋址和定位。 ? 為了引用一個服務程序， client 將代表某個服務程序名字的一個 ASCII串 發(fā)送給名字服務器，名字服務器收到這一信息后，就查看該串是否在其管理的表中。 ? 在 CDCS中， 名字服務器本身的地址是固定的 ，系統(tǒng)提供了向名字服務器管理的表中添加或從中刪除信息的命令。 31 （續(xù)） ? 設計名字服務器一般有中央方式、復制方式和分劃方式三種途徑 。但由于 性能及可靠性 方面的原因，這種方式不常采用。 32 （續(xù)） ? 分劃方式 意指： ? 若系統(tǒng)由若干子系統(tǒng) (子網(wǎng) )組成，則對于每個子系統(tǒng)，用一個名字服務器管理本子系統(tǒng)上的所有服務程序及本子系統(tǒng)與其他子系統(tǒng)相互請求的服務信息； ? 或者若系統(tǒng)的名字空間可根據(jù)某種方式來分劃，則對于每個經(jīng)這樣分劃后的實體，用單獨的或復制式的名字服務器管理； ? 或者將名字空間組織成層次結(jié)構(gòu)來管理。 ? 與此緊密相關的是進程之間如何協(xié)作及如何彼此同步。 34 DOS中的同步（續(xù)） ? 在單 CPU系統(tǒng)中，臨界區(qū)、互斥和其它同步問題經(jīng)常使用信號量、管程等方法來解決，這些方法在分布式系統(tǒng)中并不十分適用，因為它們依賴于共享存儲器的存在。 ? 如果它們在 同一臺機器 上運行，能夠共享內(nèi)核中的信號量，并通過執(zhí)行系統(tǒng)調(diào)用訪問它。 ? 甚至看似 簡單的問題 ，比如判斷事件 A在事件 B之前還是之后發(fā)生的問題也需要認真考慮。 ? 在 DOS中的分布式算法 有如下性質(zhì)： ? 相關信息分散在多臺機器中； ? 進程決策僅僅依賴于本地信息； ? 系統(tǒng)中單點故障應該避免； ? 沒有公用時鐘或其它精確的全局時間資源存在。 ? 比如，資源分配（以一種無死鎖的的方式分配） 向單一的管理進程 發(fā)送所有 I/O請求，由它來檢查它們，根據(jù)表中的信息準予或拒絕請求是不實際的。 37 時鐘同步 ? 進一步而言，一個單點故障會造成系統(tǒng)不可靠。 ? 上述的最后一點是十分關鍵的，在 集中式系統(tǒng)中時間的概念很清楚 ，當進程想知道時間時，它使用系統(tǒng)調(diào)用，由內(nèi)核提供。 ? 在 分布式系統(tǒng)中，獲得時間上的一致是并不容易 。 ? Make程序所使用的方法： ? 當編程者修改完所有的源文件，他啟動 make程序，看一下源文件和目標文件最后一次修改的時間，如果源文件 2151，而相應的目標文件 2150， make就知道 。相反，若 2144，而 2145，就不必再重編譯了。 39 一個簡單的例子：在缺少全局時間時的 UNIX下的make程序 DOS中很難獲得時間上的一致（續(xù)） ? 在沒有統(tǒng)一時間的分布式系統(tǒng)中：假設 2144，緊隨其后 ，但是由于它所在機器上的時鐘略慢，造成 2143，如圖 224所示。 40 一、問題提出 ? 所有的計算機都有一個計時電路（計時器），通常是由一個精確的 石英晶體 制成，當其在張力限度內(nèi)時，石英晶體以一定的頻率振蕩。 每次振蕩時使計數(shù)器減 1，當計數(shù)器減為 0時，產(chǎn)生一次中斷，計數(shù)器重新從保持寄存器中裝入起始值，通過這種方法可以編程使得一個計時器每秒能產(chǎn)生 60次中斷或以其它希望的頻率產(chǎn)生中斷成為可能， 每次中斷稱作一個時鐘點 （ clock tick）。 41 一、問題提出（續(xù)） ? 在 單機單時鐘中，如果時鐘被瞬間關閉其問題不會太大 ，因為這臺機器上所有進程使用同一時鐘，它們?nèi)詫?nèi)在地保持一致。 42 一、問題提出（續(xù)） ? 多 CPU系統(tǒng)中 ，每個 CPU將擁有自己的時鐘， 情況發(fā)生變化 。 ? 實際上，當系統(tǒng)有 N臺計算機時，所有 N個晶體將以略微不同的速度振蕩，導致（軟）時鐘逐漸不同步，當同時讀這些時鐘時，也會得到不同的值。 ? 一個程序期望與文件、目標文件、進程或消息相聯(lián)系的時間應是正確的，且與產(chǎn)生它們的機器（即使用哪個時鐘）無關。 ? 解決： Lamport（ 1978）闡明了時鐘同步是可能的，并且描述了實現(xiàn)的算法，他還繼續(xù)對這個問題進行了一些研究（ Lamport 1990）。 如果兩個進程無相互作用，它們的時鐘無須同步，因為即使缺少同步也覺察不出來，不會產(chǎn)生什么問題。 ? 在上述 make程序的例子中，計時目的在于說明 ，而并不是它們各自產(chǎn)生的絕對時間。 46 二、邏輯時鐘與事件定序 （續(xù)） ? Lamport 為同步邏輯時鐘定義了 “先發(fā)生”關系 ：表達式A→B 讀做“ A在 B之前發(fā)生”，意思是所有進程認為先發(fā)生事件 A，接著發(fā)生事件 B，這種關系有如下兩種情況： ? 如果 A和 B是在同一進程中的兩個事件，且 A發(fā)生在 B之前，則 A→B 為真。 ? 先發(fā)生是一個傳遞關系，即，若 A→B 且 B→C 則 A→C 。則事件 X和 Y稱為 并發(fā)事件 ，即它們之間不存在誰先誰后的問題。設 A、 B為任意兩個事件，當且僅當在圖中不存在從 A到 B或從 B到 A的一條路徑時，事件 A 與事件 B 是并發(fā)的。 ? 并發(fā)事件是： q0和 p2， r0和 q3， r0和 p3， q3和 p3。既然這兩個事件沒有一個影響另一個，因此哪一個先發(fā)生并不重要。 ? 若 a和 b是同一進程中的兩個事件，且 a→b ，則C(a)C(b) ? 同理，若 a是一個進程發(fā)送消息的事件， b為另一個進程接收消息的事件，那么 C(a)C(b)。 校正時間的操作是給時間加上一個正值，而不是減一個正數(shù)。進程 0的時鐘滴答（ tick）了 6下時，進程 1的時鐘滴答了 8下，進程 2的時鐘滴答了 10下。依次類推， 消息 B從進程 1到進程 2需要滴答 16下這也是可能的。同理， 消息D從進程 1到進程 0是在 64時刻離開，54時刻到達，這是絕對不可能出現(xiàn)的，必須防止這種情況的出現(xiàn)。 ? 在圖 b中， C現(xiàn)在到達的時間是61。 51 三、時間戳 — Lamport算法怎么給事件分配時間 （續(xù)） ? 為適應全局統(tǒng)一時間的需要，只需對此作一點 補充 即可，即在 每兩個事件之間，時鐘必須至少滴答一下，如果一個進程以相當快的速度連續(xù)發(fā)送或接收兩條消息，它必須在這中間至少滴答一下。這樣，如果在進程 1和進程 2中同時發(fā)生了 2個事件，發(fā)生時刻都是 40，則前者記為 ，后者記為。 53 四、時鐘同步算法 ? 所有算法都有相同的 系統(tǒng)基礎模型： ? 每臺機器上假設都有一個每秒產(chǎn)生 H次中斷的計時器。我們把這個時鐘值記為 C。 ? UTC：世界協(xié)調(diào)時間 (Universal Time Coordinated)。兩者的區(qū)別為時區(qū)不同， UTC就是 0時區(qū)的時間，地方時為本地時間。 ? 實際上，用現(xiàn)代計時時鐘芯片可以獲得相關的延遲是 105，意味著一臺機器每小時可以獲得 215,998～ 216,002范圍的滴答，若存在某一常數(shù) ρ，便有： ?? ???? 11 dtdC55 四、時鐘同步算法（續(xù)） ? 計時器可以在它規(guī)定的范圍內(nèi)工作，制造商標明的常數(shù) ρ是最大漂移速度 。 56 四、時鐘同步算法（續(xù)） ? 若兩個時鐘相對于 UTC時間以相反方向漂移，在它們同步后的 Δt時間內(nèi)，它們可能的差值為2ρΔt，若操作系統(tǒng)的設計者要保證每兩個時鐘之間的相差不超過 δ，時鐘必須至少在每 δ/(2ρ)秒內(nèi)再同步一次（用軟件方法），不同算法實現(xiàn)再同步的方法不同。 ? 把擁有 WWV接受器的那臺機器稱作 時間服務器 ，算法是基于 Cristian(1989)和以前的一些工作。 58 （續(xù)） ? 當發(fā)送者得到回答后，就將它的時鐘設為 CUTC，但是這種算法有兩個問題： ? 第一個重要的問題是時間決不能倒退 ，若發(fā)送者的時鐘快， CUTC將會比發(fā)送者的時間值 C小，若把發(fā)送者的時間值直接改成 CUTC會導致嚴重的錯誤，比如在時鐘變化后，編譯產(chǎn)生的目標文件的時間早于時鐘變化前源文件的修改時間。同樣時鐘要加快時，每次中斷服務程序?qū)r鐘加 11毫秒， 而不是立即把時間調(diào)到所需要的值 。 ? Cristian的處理方法是 試圖測量這個延遲值。在沒有其它任何信息時，消息傳送時間的最佳估計值是（ T1T0） /2，當應答消息到達時， 消息中的時間值再加上此值就得到了當前時間服務器的時間估計值 ，如果理論上知道了最小的傳送時間，那么與時間估算相關的其它性質(zhì)也能推算出來。 ? 系統(tǒng)中確實存在著從 A到 B的消息和從 B到 A的消息傳輸路徑不同，因此就有不同的傳輸時間，但我們目前先不考慮這種情況。對剩余的測量值取平均值會得到較好的估算值，也就是說， 最快返回的消息是最精確的，因為消息遇到阻塞最少，所以它最能代表純粹的傳輸時間。然后基于這些回答，計算出平均值并告訴所有的機器將它們的時鐘撥快或撥慢到一個新的值。 62 （續(xù)） ? (a),時間守護進程在 3:00把它的時間告訴其它機器，并且詢問它們各自的時間 ? (b)，各機器將它們各自的時間與時間守護進程時間的差值告訴時間守護進程， ? (c)守護進程計算出它們的平均值，通知各機器如何調(diào)整各自的時間。存在一些非集中式算法，如： ? 一種分布式時鐘同步算法： ? 它是 將時間劃分成固定長度的再同步間隔 ，第 i次間隔開始于 T0+iR，而結(jié)束于 T0+(i+1)R，這里的 T0是過去某一約定的時間， R是一個系統(tǒng)參數(shù)。 64 （續(xù)） ? 在機器廣播發(fā)送時間之后，它啟動本地計時器收集在 S時間間隔中到達的其它廣播 ，當所有廣播到達后，執(zhí)行一個算法，得到新的時間值。去掉兩端值可認為是一種對 m個錯誤時鐘發(fā)出毫無意義的時間值的一種自我保護。 ? 時間源自身固有的不精確性以及信號傳送的不定性，最好的操作系統(tǒng)能做的也只是建立一個UTC時間范圍 。 66 （續(xù)） ? 為達到一致，每個具有 UTC源的處理機定期在每一 UTC精確分的開始處廣播其時間范圍， 但 ? 沒有處理機會同時獲得時間包， ? 傳輸和接收延遲依賴于纜線的距離和包必須經(jīng)過的網(wǎng)關數(shù)，它對于每一對 UTC源和處理機之間都不相同。 ? 更進一步，如一臺處理機忙于處理以前的包，它可能在相當長的幾微秒內(nèi)不去理會到來的時間包，從而導致了時間的不確定性。如果有，這些 UTC范圍一定是錯誤的，棄而不用。 68 （續(xù)） 69 ? 涉及多個進程的系統(tǒng)使用臨界區(qū)容易編程 ? 當一個進程必須讀或修改某些共享數(shù)據(jù)結(jié)構(gòu)時，它首先進入臨界區(qū)獲得 互斥鎖 ，保證沒有其它的進程能同時使用該共享數(shù)據(jù)結(jié)構(gòu)。 ? 幾個例子：在分布式系統(tǒng)中臨界區(qū)和互斥是如何實現(xiàn)的。無論什么時候進程要進入臨界區(qū)，它將向協(xié)調(diào)者發(fā)送請求消息，說明它想進入哪個臨界區(qū)并希望獲得允許。當應答到達時，請求者就可以進入臨界區(qū)。而在圖 230中，協(xié)調(diào)者 回避應答 ，這樣就阻塞了進程 2，使它等待應答。 兩種方法都會把進程 2放入等待隊列，等待臨界區(qū)的釋放。如果該進程仍然阻塞（即，這是第一條發(fā)給它的允許進入消息）它去除阻塞且進入臨界區(qū)；如果明確發(fā)送一消息拒絕它進入臨界區(qū)，此進程應該不時地查詢輸入的消息，或者接著將它阻塞等待許可響應。 73 一、集中式算法 （續(xù)） ? 優(yōu)點： ? 算法保證了互斥的實現(xiàn)，協(xié)調(diào)者僅能讓某一進程在某一時刻進入臨界區(qū)。 ? 容易實現(xiàn)，每用一次臨界區(qū)只需 3條消息（請求，允許，釋放），它不僅能管理臨界區(qū)，也可用于更普遍的資源分配。 ? 此外，大系統(tǒng)中單協(xié)調(diào)者會成為執(zhí)行的瓶頸。 也就是說，對任何事件組如消息，哪個先發(fā)生必須無歧異。概念上講也包括發(fā)送給它自身。 75 二、分布式算法 （續(xù)） ? 當一個進程接收另一個進程請求消息時，根據(jù)接收方的狀態(tài)以及臨界區(qū)的名字。