【正文】 顯然有： a→b→c→d ； 然而，如果 P2在事件 b之前發(fā)生過某事件 f，例如，打印輸出，盡管可以確定： f→b ， f→c ， f→d 但 a和 f間的先后關(guān)系無法確定。 分布式進程同步 (2) ? 算法應(yīng)滿足：資源分配的互斥性 、 不產(chǎn)生餓死現(xiàn)象 、 且各資源管理者處于平等地位而無主控者 。參數(shù) S取下列值： S=0 若 Sr=0且所有回聲消息中所附參數(shù)均為 0 S=min(Sr1+1,… ,Sre+1,Sr) 否則 若 S值被選為 Sre+1，回聲消息中所附結(jié)點編號就是附有資源參數(shù) Sre的回聲中所附的結(jié)點編號。 ?接成功消息或失敗消息后，若接消息者非申請者，則將消息轉(zhuǎn)發(fā)給它的上鄰結(jié)點，否則搜索就此結(jié)束。 ?資源使用完畢后，向分配資源的資源管理者歸還資源。為保證文件副本的一致性，當一份副本正被修改時，其他各副本應(yīng)禁止使用。 第三種方法： 名字服務(wù)器尋址法 。 如何實現(xiàn) ” 單計算機系統(tǒng)映像 ” ？ 實現(xiàn)分布式系統(tǒng)的技術(shù)稱透明性： ?位臵透明性 ?遷移透明性 ?復制透明性 ?并發(fā)透明性 ?并行透明性 分布式操作系統(tǒng)基本功能 1進程通信 。 ?系統(tǒng)中的資源為所有用戶共享 ?系統(tǒng)中的若干機器可互相協(xié)作完成同一個任務(wù) ?系統(tǒng)中的一個結(jié)點出錯不影響其它結(jié)點運行 ， 具有較好的容錯性和健壯性 。 第二種方法： 廣播尋址法 。 分布式資源管理 (3) 完全分布管理 ?假如一個文件有若干副本，分別受管于不同的文件管理。 ?接到申請消息后，將申請者的名字登記入冊，并在可以分配資源時發(fā)消息通知申請者。 分布式資源管理 (9) 由近及遠算法 (3) ?如果既沒有未被搜索的下鄰結(jié)點，又沒有后結(jié)點，則說明全部結(jié)點己被搜索過，這時它將向上鄰結(jié)點發(fā)一個失敗消息。 分布式資源管理 (13) 回聲算法 (3) ?當一個結(jié)點接到它的所有下鄰結(jié)點發(fā)來的回聲消息后，就向它的上鄰結(jié)點發(fā)一回聲消息，消息中附上參數(shù) S及與之對應(yīng)的結(jié)點編號。 必須設(shè)計一個算法 ， 各資源管理者按此算法共同協(xié)商資源的分配 。 事件排序 (3) 定義事件的 “ 先發(fā)生 ” 關(guān)系后， ?同一進程中兩個事件的先后關(guān)系可以被明確確定， ?不同進程中發(fā)生的事件間的先后關(guān)系，有一部分可以被確定，而另一部分則不能確定。 ?事件排序規(guī)則：對來自站點 i的消息 x和來自站點 j的消息 y，說事件 x先發(fā)生于事件 y，如果： (1)Ti Tj 或 (2)如果 Ti = Tj 并且 i j 事件排序 (12) Lamport算法校正時鐘 0 6 12 18 24 30 36 42 48 54 60 0 8 16 24 32 40 48 56 64 72 80 0 10 20 30 40 50 60 70 80 90 100 D A B C P0 P1 P2 (a) 0 6 12 18 24 30 36 42 48 70 76 0 8 16 24 32 40 48 61 69 77 85 0 10 20 30 40 50 60 70 80 90 100 D A B C P0 P1 P2 (b) (a)三個進程 ， 各有自己的時鐘 (b)Lamport算法校正時鐘 事件排序 (13) 時間戳算法的操作例子 P1 時間 P2 P3 0 1 4 5 2 3 6 0 1 6 7 0 4 2 5 6 (a, 1, 1) (b, 5, 1) (j, 5, 3) (x,3,2) 事件排序 (14) 時間戳算法的操作另一個例子 P1 時間 P2 P3 0 1 1 2 2 0 0 2 3 (a, 1, 1) (q, 1, 4) 3 P4 0 2 分布式同步算法 (1) (1)Lamport算法 (1) ? 分布式系統(tǒng)由 N個結(jié)點組成，每個結(jié)點建立數(shù)據(jù)結(jié)構(gòu) (一個數(shù)組，也叫隊列 )，用來記錄該結(jié)點最近收到的消息和該結(jié)點自己產(chǎn)生的消息。 此條件表明其他進程要么不訪問資源 ， 要么要求訪問但其時間戳較晚 。 分布式同步算法 (12) (5) 請求互斥等待請求互斥計算激活其他進程發(fā)送r e q u e s t 給所有進程收到所有回答離開臨界區(qū)互斥請求對等待請求進程返回r e p l y分布式同步算法 (13) (3) 令牌環(huán)算法 (1) ?令牌實現(xiàn)進程互斥的過程：令牌在初始化后 ， 被邏輯環(huán)中任意一個進程獲得 ， 這樣令牌開始繞環(huán)移動 ， 它從進程 K傳遞給它的下家進程 K+1， 可按點到點方式進行傳遞 。 分布式死鎖檢測與預防 (7) 分布式死鎖檢測 (3) 防止網(wǎng)絡(luò)中出現(xiàn)死鎖 ， 可以采取破壞產(chǎn)生死鎖的四個必要條件之一的方法來實現(xiàn) 。 網(wǎng)絡(luò)文件系統(tǒng) NFS(5) NFS的實現(xiàn) NFS實現(xiàn)分成三層， ?頂層是系統(tǒng)調(diào)用層，處理open、 read、 close等調(diào)用 ?第二層虛擬文件系統(tǒng)（ VFS） ?第三層本地操作系統(tǒng) 網(wǎng)絡(luò)文件系統(tǒng) NFS(6) NFS的使用 (1)安裝（ Mount） (2)打開（ Open） (3)讀 /寫（ Read/Write） (1) 1． 數(shù)據(jù)遷移 2． 計算遷移 3． 進程遷移 進程遷移 (2) 下列原因需要引入進程遷移 : (1)負載均衡。