分布式計(jì)算機(jī)系統(tǒng)ppt課件計(jì)算機(jī)操作系統(tǒng)湯小丹梁

1、第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 第第9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng)9.2 分布式系統(tǒng)的設(shè)計(jì)分布式系統(tǒng)的設(shè)計(jì) 9.3 分布式系統(tǒng)中的通信問題分布式系統(tǒng)中的通信問題 9.4 消息傳遞消息傳遞 9.5 遠(yuǎn)程過程調(diào)用遠(yuǎn)程過程調(diào)用 9.6 進(jìn)程遷移進(jìn)程遷移 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.7 分布式操作系統(tǒng)中的進(jìn)程同步分布式操作系統(tǒng)中的進(jìn)程同步 9.8 分布式操作系統(tǒng)中的進(jìn)程互斥分布式操作系統(tǒng)中的進(jìn)程互斥9.9 分布式系統(tǒng)的資源管理分布式系統(tǒng)的資源管理9.10 死鎖處理死鎖處理 習(xí)題習(xí)題第第9 9章章 分布式計(jì)算

2、機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1.1 概述 網(wǎng)絡(luò)技術(shù)的發(fā)展使一些計(jì)算機(jī)系統(tǒng)從集中式走向分布式，那么什么是分布式系統(tǒng)呢?分布式計(jì)算機(jī)系統(tǒng)(Distributed Computer Systems)是由多個(gè)分散的計(jì)算機(jī)經(jīng)互連網(wǎng)絡(luò)連接而成的計(jì)算機(jī)系統(tǒng)。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 分布式計(jì)算機(jī)系統(tǒng)是多機(jī)系統(tǒng)的一種新形式，它強(qiáng)調(diào)資源、任務(wù)、功能和控制的全面分布。就資源分布而言，既包括處理機(jī)、I/O設(shè)備、通信接口、后援存儲器等物理設(shè)備資源，也包括進(jìn)程、文件、目錄、表、數(shù)據(jù)庫等邏輯資源。它們分布于物理上分散的若干場點(diǎn)中，而各場點(diǎn)經(jīng)互連網(wǎng)絡(luò)溝通，

3、彼此通信，構(gòu)成統(tǒng)一的計(jì)算機(jī)系統(tǒng)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 網(wǎng)絡(luò)操作系統(tǒng)是為計(jì)算機(jī)網(wǎng)絡(luò)配置的操作系統(tǒng)，網(wǎng)絡(luò)中的每臺計(jì)算機(jī)配置各自的操作系統(tǒng)，通過網(wǎng)絡(luò)操作系統(tǒng)把它們有機(jī)地聯(lián)系起來。因此，它除了具有一般操作系統(tǒng)所具備的存儲管理、處理機(jī)管理、設(shè)備管理、信息管理和作業(yè)管理等功能外，還應(yīng)具有以下網(wǎng)絡(luò)管理功能： (1) 高效可靠的網(wǎng)絡(luò)通信能力。 (2) 多種網(wǎng)絡(luò)服務(wù)功能，包括遠(yuǎn)程作業(yè)錄入、分時(shí)系統(tǒng)服務(wù)和文件傳輸服務(wù)等。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (1) 進(jìn)程通信不能借助公共存儲器，因而常采用信息傳遞方式。 (2) 系統(tǒng)中的資源分布于多個(gè)場點(diǎn)，因而進(jìn)程調(diào)度、資源分

4、配及系統(tǒng)管理等必須滿足分布處理要求，并采用保證一致性的分散式管理方式和具有強(qiáng)健性的分布式算法。 (3) 不失時(shí)機(jī)地協(xié)調(diào)各場點(diǎn)的負(fù)載，使其達(dá)到基本平衡，以充分發(fā)揮各場點(diǎn)的作用。 (4) 故障檢測與恢復(fù)及系統(tǒng)重構(gòu)和可靠性等問題的處理和實(shí)現(xiàn)都比較復(fù)雜。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1.2 分布式系統(tǒng)的特征 由分布式系統(tǒng)的定義可知，分布式系統(tǒng)是由多臺計(jì)算機(jī)組成的系統(tǒng)。更確切地說，分布式系統(tǒng)是具有以下特點(diǎn)的多計(jì)算機(jī)系統(tǒng)。 (1) 分布性：組成系統(tǒng)的部件在物理上是分散的，這些部件包括處理機(jī)、數(shù)據(jù)、算法和操作系統(tǒng)。 (2) 自治性：系統(tǒng)所有的軟硬件資源都是高度自治的，它們能夠獨(dú)立執(zhí)行

5、任務(wù)、提供或拒絕提供服務(wù)。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (3) 透明性：系統(tǒng)的分布性、操作和實(shí)現(xiàn)對用戶完全透明，用戶只需提出所需服務(wù)，而不必要指明由哪一臺設(shè)備在什么位置用什么方法來提供這些服務(wù)。 (4) 共享性：系統(tǒng)中的資源為系統(tǒng)中所有用戶所共享，在某臺計(jì)算機(jī)終端上的用戶，不僅可以使用位于該機(jī)上的資源，而且還可以使用位于它機(jī)上的資源。 (5) 協(xié)同性：系統(tǒng)中的若干臺計(jì)算機(jī)可以相互協(xié)作來完成一個(gè)共同任務(wù)，或者說，一個(gè)程序可以分布在幾臺計(jì)算機(jī)上并行運(yùn)行。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 分布式系統(tǒng)應(yīng)具備以下三種基本功能： (1) 通信。系統(tǒng)提供某種通信機(jī)制，使

6、得運(yùn)行在不同計(jì)算機(jī)上的用戶程序可以利用網(wǎng)絡(luò)來交換信息。 (2) 資源共享。系統(tǒng)提供訪問它機(jī)資源的功能，使得在某機(jī)或其終端上的用戶或用戶程序可以訪問位于它機(jī)的資源。 (3) 協(xié)同工作。系統(tǒng)提供某種程序設(shè)計(jì)語言，使得用戶可以用它編寫能夠分布在若干臺計(jì)算機(jī)上并行執(zhí)行的應(yīng)用程序，同時(shí)系統(tǒng)提供這些應(yīng)用程序(進(jìn)程)之間的協(xié)調(diào)和通信。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1.3 分布式系統(tǒng)的結(jié)構(gòu) 分布式系統(tǒng)中的場點(diǎn)可用不同的方式將它們從物理上連接起來，每種方式都有其優(yōu)缺點(diǎn)，下面簡單討論幾種常用的連接方式并按以下標(biāo)準(zhǔn)來比較它們的性能。 基本開銷：連接系統(tǒng)中的各個(gè)場點(diǎn)需要多少花費(fèi)? 通信開銷：從

7、場點(diǎn)Ai發(fā)送信息到場點(diǎn)Aj需要多少時(shí)間？(i，j=1，2，3，n) 可靠性：若系統(tǒng)中某場點(diǎn)或通信線路出現(xiàn)故障，余下的場點(diǎn)是否仍能彼此通信?第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 1全互連結(jié)構(gòu) 在一個(gè)全互連結(jié)構(gòu)中，每個(gè)場點(diǎn)都直接與系統(tǒng)中所有其他的場點(diǎn)相連，如圖9.1所示。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) A2A1A4A5A3圖9.1 全互連結(jié)構(gòu)第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2部分互連結(jié)構(gòu) 在一個(gè)部分互連結(jié)構(gòu)中，有些場點(diǎn)間存在直接通信鏈路，但有些則沒有，如圖9.2所示。因此這種構(gòu)形的基本開銷比全互連結(jié)構(gòu)要低，但場點(diǎn)間的消息傳遞可能經(jīng)由若干中間的場點(diǎn)，

8、以致延緩了通信速度。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 圖9.2 部分互連結(jié)構(gòu)發(fā)消息A1A4A2A3A5第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 3層次結(jié)構(gòu) 層次結(jié)構(gòu)中的各場點(diǎn)組織呈樹形結(jié)構(gòu)，如圖9.3所示。其中，每一場點(diǎn)(根除外)有一個(gè)惟一的父節(jié)點(diǎn)和若干個(gè)(或0個(gè))子節(jié)點(diǎn)。這種結(jié)構(gòu)的基本開銷一般小于部分互連結(jié)構(gòu)。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 圖9.3 層次結(jié)構(gòu)A3A4A2A5A1A6第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 4星形結(jié)構(gòu) 在星形結(jié)構(gòu)中，系統(tǒng)中的場點(diǎn)之一與系統(tǒng)中所有其余場點(diǎn)相連，其他的場點(diǎn)之間彼此不直接相連，如圖9.4所示。

9、第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 圖9.4 星形結(jié)構(gòu)A5A4A1A3A2A6第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 5環(huán)形結(jié)構(gòu) 在環(huán)形結(jié)構(gòu)中，每個(gè)場點(diǎn)物理上恰好與另外兩個(gè)場點(diǎn)相連，如圖9.5(a)所示。 在雙向環(huán)形結(jié)構(gòu)中，其中兩條通信鏈路故障就可能導(dǎo)致分割整個(gè)系統(tǒng)。在單向環(huán)形結(jié)構(gòu)中，單個(gè)場點(diǎn)或單條通信鏈路故障，就可能分割整個(gè)系統(tǒng)。一種補(bǔ)救的辦法是通過提供雙通信鏈路來擴(kuò)充這種結(jié)構(gòu)，但這顯然會增加基本開銷，如圖9.5(b)所示。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) A8A7A6A5A4A3A2A1(a)(b)A8A7A6A5A4A3A2A1圖9.5 環(huán)形結(jié)構(gòu)

10、(a) 單通信鏈路；(b) 雙通信鏈路 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 6多存取總線結(jié)構(gòu) 在多存取總線結(jié)構(gòu)(簡稱總線結(jié)構(gòu))中，有一條共享的通信鏈路(即總線)。系統(tǒng)中所有的場點(diǎn)都直接與這條通信鏈路相連，它可以組織成直線狀(見圖9.6(a)，也可以組織成環(huán)形(見圖9.6(b)，其中的場點(diǎn)可以經(jīng)由這條總線彼此直接進(jìn)行通信。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) AnA1A2A3A4A5A6AnA3A2A1(a)(b)圖9.6 總線結(jié)構(gòu)(a) 線形總線；(b) 環(huán)形總線第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 7立方體結(jié)構(gòu) 立方體結(jié)構(gòu)又稱n維立方體分布式網(wǎng)絡(luò)結(jié)構(gòu)。

11、這種結(jié)構(gòu)把2nN個(gè)計(jì)算機(jī)互連起來，各計(jì)算機(jī)分別位于該立方體的角頂。立方體的每條邊把兩個(gè)場點(diǎn)連接起來，而每個(gè)場點(diǎn)則有n個(gè)全雙向通路把它和n個(gè)其他計(jì)算機(jī)相連。例如，n3和n4時(shí)立方體互連結(jié)構(gòu)分別如圖9.7(a)、(b)所示，其中，n為立方體的維數(shù)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (a)(b)圖9.7 立方體結(jié)構(gòu)(a) n=3, N=8；(b) n=4, N=16第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.1.4 分布式系統(tǒng)的設(shè)計(jì)方法 傳統(tǒng)上，分布式操作系統(tǒng)是按面向進(jìn)程的方法設(shè)計(jì)的，近年來提出了面向?qū)ο蟮姆植际讲僮飨到y(tǒng)的設(shè)計(jì)方法，它與面向進(jìn)程的分布式操作系統(tǒng)的設(shè)計(jì)方法的主

12、要區(qū)別是：前者將操作系統(tǒng)視為對象的集合，而且有關(guān)用戶(進(jìn)程)對象和系統(tǒng)狀態(tài)的同步及控制是通過權(quán)限(Capability)的管理和分配完成的；而后者則把操作系統(tǒng)看作是進(jìn)程的集合，有關(guān)用戶進(jìn)程和系統(tǒng)狀態(tài)的同步及控制是通過消息傳遞實(shí)現(xiàn)的。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.2 分布式系統(tǒng)的設(shè)計(jì)分布式系統(tǒng)的設(shè)計(jì) 1透明性(Transparency) 分布式系統(tǒng)的透明性具體表現(xiàn)在： (1) 位置透明性。在一個(gè)分布式系統(tǒng)中，用戶不必知道硬件或軟件資源的具體位置。資源的名字不能用資源的位置編碼。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (2) 遷移(Migration)透明性。遷

13、移透明性是指資源可以隨意從一個(gè)計(jì)算機(jī)(節(jié)點(diǎn))遷移到另一個(gè)計(jì)算機(jī)上，而無需改變資源的名字。 (3) 復(fù)制(Replication)透明性。復(fù)制透明性是指用戶不知道系統(tǒng)擁有多少副本。 (4) 并發(fā)(Concurrency)透明性。 (5) 并行(Parallelism)透明性。用戶所看到的一個(gè)分布式系統(tǒng)是一個(gè)單機(jī)形式。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2靈活性(Flexibility) 分布式系統(tǒng)設(shè)計(jì)的第二個(gè)關(guān)鍵問題是靈活性。靈活性涉及到分布式操作系統(tǒng)的結(jié)構(gòu)。分布式操作系統(tǒng)結(jié)構(gòu)有兩種不同的形式：一種是單內(nèi)核(Monolithic Kernel)，另一種是微內(nèi)核(Micro Ker

14、nel)，如圖9.8所示。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 用戶程序包括文件、目錄 和進(jìn)程管理網(wǎng)絡(luò)微內(nèi)核文件服務(wù)器微內(nèi)核目錄服務(wù)器微內(nèi)核進(jìn)程服務(wù)器微內(nèi)核用戶程序單內(nèi)核圖9.8 分布式操作系統(tǒng)結(jié)構(gòu)(a) 單內(nèi)核；(b) 微內(nèi)核第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 微內(nèi)核結(jié)構(gòu)更加靈活，是一種新的結(jié)構(gòu)，僅僅提供以下四種服務(wù)： (1) 進(jìn)程間通信機(jī)制； (2) 某些內(nèi)存管理； (3) 有限的低級進(jìn)程管理和調(diào)度； (4) 低級的輸入輸出。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 3可靠性(Reliability) 最初分布式系統(tǒng)的設(shè)計(jì)原因之一是它比集中式系統(tǒng)可靠性更高

15、，即一臺機(jī)器壞了，其他機(jī)器能夠接替它的工作。換句話說，在理論上系統(tǒng)可靠性是所有部件可靠性的布爾“或”。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 4性能(Performance) 性能是設(shè)計(jì)任何一個(gè)系統(tǒng)都需要重視的問題。一個(gè)分布式系統(tǒng)的透明性再好，靈活性再強(qiáng)，可靠性再高，而它的性能很差，速度很慢，也就失去了建立分布式系統(tǒng)的意義。如何衡量分布式系統(tǒng)性能的好壞是一個(gè)有待進(jìn)一步研究的問題。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 5可擴(kuò)展性(Expansibility) 在建立一個(gè)分布式系統(tǒng)之前，分布式系統(tǒng)的規(guī)模也是必須考慮的問題，即所設(shè)計(jì)的系統(tǒng)應(yīng)是可擴(kuò)展的，應(yīng)避免潛在的瓶頸：集中

16、式部件、集中式表格和集中式算法。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.3 分布式系統(tǒng)中的通信問題分布式系統(tǒng)中的通信問題在分布式系統(tǒng)中的通信應(yīng)注意以下幾個(gè)方面的問題： 發(fā)送策略：如何通過通信網(wǎng)發(fā)送消息? 連接策略：如何去連接彼此希望通信的進(jìn)程? 爭奪處理：由于通信網(wǎng)是共享資源，應(yīng)注意解決在利用它的過程中哪些有沖突的要求和沖突現(xiàn)象。 保密：如何保住消息內(nèi)容的秘密? 通信機(jī)制：研究分布式操作系統(tǒng)中的基本通信機(jī)制。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.3.1 發(fā)送策略 當(dāng)場點(diǎn)A1上的一進(jìn)程希望同場點(diǎn)A2上的另一進(jìn)程進(jìn)行通信時(shí)，如何發(fā)送消息呢? 若從A1到A2之間只有一條

17、物理信道(好像在一個(gè)星形結(jié)構(gòu)或?qū)哟谓Y(jié)構(gòu)中)，那么，該消息只能經(jīng)由這條信道發(fā)送。若從A1到A2存在多條物理通路，那么，發(fā)送該消息就有選擇性了。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (1) 固定發(fā)送：從A到B的信道事先已規(guī)定好且不得更改，除非硬件方面的故障影響到它的通信能力。通常是選擇(物理上長度)最短的信道，以減少通信開銷。 (2) 虛擬線路：從A到B的信道在一段時(shí)間內(nèi)是固定的，在不同時(shí)期，從A向B發(fā)送的信息可能經(jīng)由不同的信道發(fā)送。 (3) 動(dòng)態(tài)發(fā)送：用于從A到B發(fā)送信息的信道僅當(dāng)該消息發(fā)送之時(shí)才被確定。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.3.2 連接策略 1線路

18、轉(zhuǎn)換 假設(shè)兩個(gè)進(jìn)程之間需要通信，那么在它們通信期間應(yīng)建立一永久性的物理通信鏈路，在這段時(shí)間其他進(jìn)程不能使用這條鏈路。這種方案與電話系統(tǒng)類似，一旦一通話線路已對兩方開放(如甲方給乙方打電話)，其他的人就不可能使用這條信道，除非甲、乙兩方的通話結(jié)束(如一方已掛上聽筒)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2消息轉(zhuǎn)換 假設(shè)兩個(gè)進(jìn)程之間需要通信，那么確定一臨時(shí)通信鏈路供其消息傳遞期間使用。物理通信鏈路則根據(jù)需要在用戶間動(dòng)態(tài)地進(jìn)行分配，而且只允許使用較短的一段時(shí)間。每條消息由一個(gè)數(shù)據(jù)塊再附加一些系統(tǒng)信息(如發(fā)送地、接收地、錯(cuò)誤校正碼等)組成，這些系統(tǒng)信息輔助通信網(wǎng)絡(luò)正確地將消息傳遞到目的地

19、。這種方案與郵局系統(tǒng)類似，每封信可看作是包含發(fā)送地和接收地的一條消息，而且來自不同用戶的信件(消息)可在相同通信線路上傳遞。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 3消息包轉(zhuǎn)換 消息一般是可變長度的。為了簡化系統(tǒng)的設(shè)計(jì)，常常把消息設(shè)計(jì)成定長的形式，并把這種定長的形式稱為消息包(Packet)。一條邏輯消息可能不得不劃分成若干消息包，每個(gè)消息包都可以經(jīng)由網(wǎng)絡(luò)中不同的路徑單獨(dú)發(fā)送到其目的地，當(dāng)這些消息包都到達(dá)其目的地后，還得拼裝起來組成一條完整的消息。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.3.3 爭奪處理 1沖突檢測 一個(gè)場點(diǎn)要在某條通信線路上傳遞消息之前，必須進(jìn)行監(jiān)測以

20、確定當(dāng)前在該通信線路上是否正在傳遞另外的消息。若該通信線路空閑，則這個(gè)場點(diǎn)可以開始發(fā)送，否則它必須等待(同時(shí)繼續(xù)監(jiān)測)，直到這條線路空閑。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2令牌傳遞(Token Passing) 令牌是一個(gè)特殊的消息類型，它不停地在系統(tǒng)(通常在一個(gè)環(huán)形結(jié)構(gòu))中循環(huán)。希望傳遞消息的場點(diǎn)必須等待令牌到達(dá)。當(dāng)令牌到達(dá)后，該場點(diǎn)就從環(huán)中取走令牌并開始傳遞它的消息。 3消息槽(Slot) 若干定長的消息槽連續(xù)不斷地在系統(tǒng)(通常是一個(gè)環(huán)形結(jié)構(gòu))中循環(huán)。每個(gè)消息槽可以容納一定長的消息和有關(guān)的控制信息(如發(fā)送處、接收處、消息槽滿/空等)。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分

21、布式計(jì)算機(jī)系統(tǒng) 9.3.4 保密 系統(tǒng)必須提供適當(dāng)?shù)拇胧┳層脩舯Ｗo(hù)他們的信息(數(shù)據(jù))。編碼是保護(hù)信息的常用方法之一。信息在發(fā)送之前先予以編碼，當(dāng)信息到達(dá)目的地后就進(jìn)行譯碼。問題在于如何研制一個(gè)不可能(或很難)破譯的編碼系統(tǒng)。對此，有許多解決辦法，常用的一種就是提供一個(gè)通用的編碼算法E和一個(gè)通用的譯碼算法D，并對每次應(yīng)用提供一個(gè)密鑰。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 令Ek和Dk分別表示具有密鑰k的那個(gè)特定應(yīng)用的編碼和譯碼算法，那么，對于任何消息m，該編碼系統(tǒng)必須滿足下面的特性： (1) Dk(Ek(m)=m； (2) Dk和Ek都能有效地計(jì)算； (3) 該系統(tǒng)的保密性只依賴于

22、密鑰k的保密性而不依賴于算法E和D的保密性。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 基于上述思想的編碼方案已由Rivest，Shamir和Adleman(1978)設(shè)計(jì)出來了。這個(gè)方案簡稱RSA算法，曾被認(rèn)為是不可破譯的。其中的公共鑰是對偶(e，n)，私鑰是對偶(d，n)。這里e，d，n都是正整數(shù)。每條消息用0n-1之間的一個(gè)整數(shù)表示(較長的消息可分成若干較短的消息，它們每一個(gè)都可用這樣的一個(gè)整數(shù)表示)。函數(shù)E和D定義為 E(m)me mod nC D(C)Cd mod n第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 這里的主要問題是選擇編碼和鑰。整數(shù)n可用下式計(jì)算：npq 其中

23、，p和q是隨機(jī)選取的兩個(gè)較大的素?cái)?shù)(例如，它們是由100位或更多位數(shù)字組成的)；d是隨機(jī)選取的一個(gè)與(p-1)(q-1)互質(zhì)的較大整數(shù)，即d滿足GCDd, (p-1)(q-1)1 而e滿足 ed mod (p-1)(q-1)1第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.4 消消 息息 傳傳 遞遞 9.4.1 異步型 在這類通信機(jī)制中，發(fā)送消息的進(jìn)程不等待接收者的回復(fù)，即允許發(fā)送方任意超前于接收方，因而它具有下面的特征： (1) 接收方收到的消息與發(fā)送方目前的狀態(tài)是無關(guān)的。換言之，接收消息中反映的發(fā)送狀態(tài)一般不是發(fā)送方的當(dāng)前狀態(tài)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (2)

24、 由于通信機(jī)制與同步機(jī)制幾乎被截然分開，因此，系統(tǒng)應(yīng)具有“無限”的緩沖空間來容納任意超前發(fā)出而尚未處理的消息，以此來解決消息發(fā)送速度和消息處理速度之間的差異。 (3) 能比較充分地利用系統(tǒng)的潛在能力，但實(shí)現(xiàn)時(shí)需解決許多實(shí)際的控制問題。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.4.2 同步型 同步型與異步型消息傳遞正好相反，總是要求發(fā)送方等待接收方的回復(fù)，然后發(fā)送方與接收方同步繼續(xù)向下執(zhí)行。其主要特征如下： (1) 消息的發(fā)送方和接收方在完成信息交換后彼此知道對方的狀態(tài)。 (2) 同步機(jī)制和通信機(jī)制合二為一，一般無需大的緩沖區(qū)。 (3) 實(shí)現(xiàn)容易，但效率較低。第第9 9章章 分布式計(jì)

25、算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.4.3 組通信 1組通信的用途 如果一個(gè)進(jìn)程想和另一組進(jìn)程進(jìn)行通信，單個(gè)的消息交換并非最好的模式。比如，一個(gè)服務(wù)是由多個(gè)計(jì)算機(jī)上的多個(gè)進(jìn)程完成的時(shí)候，就會出現(xiàn)一個(gè)進(jìn)程和一組進(jìn)程間的通信。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 如果需要設(shè)計(jì)一個(gè)具有如下特征的分布式系統(tǒng)，則組播消息是一個(gè)非常有用的方式。 (1) 以重復(fù)服務(wù)為基礎(chǔ)的容錯(cuò)性。每當(dāng)一個(gè)客戶發(fā)出一個(gè)請求消息時(shí)，它實(shí)際上是將這條消息發(fā)送給一組服務(wù)器。 (2) 定位分布式服務(wù)中的對象。組播消息可以用來在一個(gè)分布式服務(wù)中尋找一個(gè)對象，例如在分布式文件服務(wù)中尋找一個(gè)文件。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)

26、分布式計(jì)算機(jī)系統(tǒng) (3) 通過保留數(shù)據(jù)的副本來提高性能。分布式系統(tǒng)可以使用數(shù)據(jù)的副本來提高服務(wù)的性能，有時(shí)候副本就保存在用戶的本地機(jī)之中。 (4) 多重刷新。對一個(gè)組的組播可在發(fā)生某些事件時(shí)通知該組中的進(jìn)程。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2組通信的特性 1) 原子性(Atomicity) 在上面提到的第(1)種“將這條消息發(fā)送給一組服務(wù)器”的情況中，每個(gè)服務(wù)器都收到所有的請求，因此每個(gè)服務(wù)器執(zhí)行的操作都是相同的，并且在任一時(shí)刻每個(gè)服務(wù)器的狀態(tài)都是一樣的。要實(shí)現(xiàn)這樣的目標(biāo)，必須使用原子組播。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 所謂原子組播(Aatomic Mu

27、lticast)，就是指任何一條以原子組播方式發(fā)送的消息，要么被接收的服務(wù)器組中的所有成員全部收到，要么其中的成員一個(gè)也收不到。這里我們規(guī)定，失效的進(jìn)程不可能是任一個(gè)服務(wù)器組中的成員。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2) 定序(Ordering) 原子組播和可靠組播在進(jìn)程對之間都提供FIFO式的定序。在FIFO式的定序中，從任一個(gè)客戶發(fā)送到某個(gè)服務(wù)器的次序也就是它們發(fā)出時(shí)的次序，我們可以在消息中加上一個(gè)序列號來實(shí)現(xiàn)這一目的。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) BBAAP1時(shí)間P2P3P4圖9.9 無定序限制的組播第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng)

28、9.5 遠(yuǎn)程過程調(diào)用遠(yuǎn)程過程調(diào)用 9.5.1 概述 在單處理機(jī)系統(tǒng)中，不同進(jìn)程之間可以通過過程(函數(shù))調(diào)用方式實(shí)現(xiàn)進(jìn)程通信。在調(diào)用時(shí)，調(diào)用進(jìn)程必須給出被調(diào)用的過程名，傳送所需參數(shù)和提供返回參數(shù)的緩沖區(qū)。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.5.2 基本RPC操作 在分布式操作系統(tǒng)中，為實(shí)現(xiàn)進(jìn)程間的通信，通常要設(shè)計(jì)一些通信原語(如前述的send、receive)。這些原語是按照通信協(xié)議所規(guī)定的規(guī)則實(shí)現(xiàn)的，這些通信原語就構(gòu)成了分布式系統(tǒng)基本的通信機(jī)制。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 為了解RPC是如何工作的，首先要了解清楚傳統(tǒng)的(即單機(jī)上)過程調(diào)用是如何工作的

29、?？紤]這樣一個(gè)過程調(diào)用： count=read(fd，buf，nbytes); 這里fd是一個(gè)整數(shù)，buf是一個(gè)字符型數(shù)組，nbytes也是一個(gè)整數(shù)。若主程序調(diào)用該過程，調(diào)用前堆棧的情況如圖9.10(a)所示。調(diào)用開始時(shí)，調(diào)用者按序?qū)?shù)壓入堆棧，后進(jìn)入的先彈出，如圖9.10(b)所示。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 主程序局部變量nbytesSPSP00buffd返回地址read的局部變量主程序局部變量SP主程序局部變量(a)(b)(c)圖9.10 基本的RPC操作(a) 調(diào)用之前的棧狀態(tài)；(b) 過程執(zhí)行中的棧；(c) 返回到調(diào)用者之后的棧第第9 9章章 分布式計(jì)算機(jī)系

30、統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 客戶存根調(diào)用調(diào)用客戶機(jī)返回返回參數(shù)打包內(nèi)核內(nèi)核網(wǎng)上傳送的消息橢圓代表進(jìn)程，陰影部分表示存根服務(wù)器存根參數(shù)拆包結(jié)果打包服務(wù)器結(jié)果拆包圖9.11 RPC調(diào)用和消息第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) RPC的主要步驟是：(1) 客戶過程以普通方式調(diào)用相應(yīng)的客戶代理。(2) 客戶代理建立消息并激活內(nèi)核陷阱。(3) 內(nèi)核將消息發(fā)送到遠(yuǎn)程內(nèi)核。(4) 遠(yuǎn)程內(nèi)核將消息送到服務(wù)器代理。(5) 服務(wù)器代理取出消息中的參數(shù)后調(diào)用服務(wù)器的過程。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (6) 服務(wù)器完成工作后將結(jié)果返回至服務(wù)器代理。(7) 服務(wù)器代理將結(jié)果打包并激活內(nèi)核陷阱

31、。(8) 遠(yuǎn)程內(nèi)核將消息發(fā)送至客戶內(nèi)核。(9) 客戶內(nèi)核將消息交給客戶代理。(10) 客戶代理從消息中取出結(jié)果返回給客戶。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.5.3 兩種通信方式的比較 遠(yuǎn)程過程調(diào)用在廣泛的應(yīng)用中，也暴露了一些缺點(diǎn)，不能滿足某些方面的要求，主要有： (1) 遠(yuǎn)程過程調(diào)用的參數(shù)在系統(tǒng)內(nèi)不同機(jī)種之間通用的能力有所不足。 (2) 缺乏在一次調(diào)用過程中多次接收、返回的能力。 (3) 遠(yuǎn)程過程調(diào)用缺乏傳送大量數(shù)據(jù)的能力。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.6 進(jìn)進(jìn) 程程 遷遷 移移 9.6.1 數(shù)據(jù)和計(jì)算的遷移 1數(shù)據(jù)遷移(Data Migratio

32、n) 假如系統(tǒng)A中的用戶希望去訪問系統(tǒng)B中的數(shù)據(jù)，比如一份文件，可采取以下兩種方法來實(shí)現(xiàn)數(shù)據(jù)的傳送。 第一種方法是將系統(tǒng)B中的整個(gè)文件送到系統(tǒng)A。 第二種方法是把文件中用戶當(dāng)前需要的那一部分從系統(tǒng)B傳送到A。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2計(jì)算遷移(Computation Migration) 在某些情況下，傳送計(jì)算要比傳送數(shù)據(jù)更有效。例如，有一個(gè)作業(yè)，它需訪問多個(gè)駐留在不同系統(tǒng)中的大型文件，以獲得這些文件的摘要。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.6.2 引入進(jìn)程遷移的原因 1負(fù)荷均衡(Load Balancing) 在分布式系統(tǒng)中，各個(gè)系統(tǒng)中的負(fù)荷

33、，經(jīng)常會是不均勻的。此時(shí)，可通過進(jìn)程遷移的方法來均衡各個(gè)系統(tǒng)的負(fù)荷，即將重負(fù)荷系統(tǒng)中的進(jìn)程遷移到輕負(fù)荷系統(tǒng)中去，以改善系統(tǒng)的性能。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2通信性能 對于那些分布在不同系統(tǒng)中，而彼此交互性又非常強(qiáng)的一些進(jìn)程，應(yīng)將它們遷移到同一系統(tǒng)中，以減少由于它們之間頻繁地交互而加大的通信費(fèi)用。 3加速計(jì)算 對于一個(gè)大型作業(yè)，如果始終運(yùn)行在一臺處理機(jī)上，可能會花費(fèi)較多的時(shí)間，使作業(yè)的周轉(zhuǎn)時(shí)間很長；但如果能為該作業(yè)建立多個(gè)進(jìn)程，并將這些進(jìn)程遷移到多個(gè)處理機(jī)上，使它們并行執(zhí)行，就會大大加速該作業(yè)的完成，從而縮短作業(yè)的周轉(zhuǎn)時(shí)間。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)

34、系統(tǒng) 4需要特殊資源 當(dāng)某進(jìn)程必須在具有某種特殊功能的處理機(jī)上運(yùn)行才能完成其任務(wù)時(shí)，就需要將該進(jìn)程遷移到該處理機(jī)上去運(yùn)行。 5提高可利用性 在分布式系統(tǒng)中，如果某個(gè)系統(tǒng)發(fā)生了故障，而在該系統(tǒng)中的進(jìn)程又希望能繼續(xù)運(yùn)行下去，則分布式OS便可將這些進(jìn)程遷移到其他系統(tǒng)中去運(yùn)行。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.6.3 進(jìn)程遷移機(jī)制 為了實(shí)現(xiàn)進(jìn)程遷移，在分布式系統(tǒng)中必須建立相應(yīng)的進(jìn)程遷移機(jī)制。該機(jī)制應(yīng)該解決以下幾個(gè)問題： (1) 由誰來發(fā)動(dòng)進(jìn)程遷移？ (2) 應(yīng)遷移進(jìn)程的哪些部分？ (3) 如何進(jìn)行進(jìn)程遷移？ (4) 對尚未完成的報(bào)文和消息應(yīng)如何處理？第第9 9章章 分布式計(jì)算機(jī)系

35、統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 1進(jìn)程遷移的啟動(dòng) 由誰來啟動(dòng)進(jìn)程遷移，取決于在設(shè)計(jì)進(jìn)程遷移機(jī)制時(shí)所要達(dá)到的目標(biāo)。如果其目標(biāo)是為了均衡負(fù)荷，則在進(jìn)程遷移機(jī)制中，應(yīng)為各個(gè)系統(tǒng)配置系統(tǒng)負(fù)荷監(jiān)視模塊，并指定其中之一為主控模塊。主控模塊定時(shí)地與各系統(tǒng)中的監(jiān)視模塊交互有關(guān)系統(tǒng)負(fù)荷情況的信息。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2進(jìn)程遷移前后 在進(jìn)程進(jìn)行遷移時(shí)，應(yīng)將源系統(tǒng)中的已遷移的進(jìn)程撤消，在目標(biāo)系統(tǒng)中建立一個(gè)相同的新進(jìn)程，此時(shí)是所謂的進(jìn)程遷移而不是進(jìn)程復(fù)制。在進(jìn)程遷移時(shí)，所遷移的是進(jìn)程實(shí)體或稱進(jìn)程映像(Process Image)。通常它都包含進(jìn)程控制塊、程序、數(shù)據(jù)和棧。此外，被遷移的進(jìn)程與其他進(jìn)程

36、之間的鏈應(yīng)做適當(dāng)修改。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 3如何進(jìn)行遷移 (1) 傳送整個(gè)地址空間。它是指一次性地將程序、數(shù)據(jù)等全部從源系統(tǒng)傳送到目標(biāo)系統(tǒng)。 (2) 僅傳送在內(nèi)存中的那部分地址空間。在程序運(yùn)行時(shí)若還需要附加的部分，則可通過請求方式予以傳送。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 4對未完成報(bào)文的處理 在一個(gè)進(jìn)程由源系統(tǒng)向目標(biāo)系統(tǒng)遷移期間，可能會有其他進(jìn)程繼續(xù)向源系統(tǒng)中已遷移的進(jìn)程發(fā)來報(bào)文和信號，我們把這些報(bào)文和信號稱為未完成報(bào)文和信號。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.6.4 遷移的協(xié)商 為了實(shí)現(xiàn)這種遷移協(xié)商(Negotiatio

37、n of Migration)，在Charlatte系統(tǒng)中設(shè)置了一進(jìn)程遷移機(jī)構(gòu)。它由若干個(gè)Starter來決定應(yīng)將哪些進(jìn)程遷移到目標(biāo)系統(tǒng)中去；同時(shí)，這些Starter還負(fù)責(zé)作業(yè)調(diào)度和內(nèi)存分配，并使這三項(xiàng)任務(wù)協(xié)調(diào)起來。每一個(gè)Starter進(jìn)程可以管理一組機(jī)器(系統(tǒng))，每當(dāng)要進(jìn)行進(jìn)程遷移時(shí)，都需有兩個(gè)Starter進(jìn)程參與決定。圖9.12是進(jìn)程遷移的協(xié)商示意。進(jìn)程遷移是按照下述步驟進(jìn)行協(xié)商的。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) KJSK JD(3)Starter進(jìn)程Starter進(jìn)程P(2)(1)(5)(6)(4)(7)圖9.12 進(jìn)程遷移的協(xié)商示意圖 第第9 9章章 分布式計(jì)算機(jī)系

38、統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (1) 當(dāng)Starter已決定將系統(tǒng)S中的進(jìn)程P遷移到指定的系統(tǒng)D時(shí)，便發(fā)送一個(gè)要求傳送進(jìn)程的報(bào)文給系統(tǒng)D的Starter。 (2) 系統(tǒng)D的Starter若準(zhǔn)備接受該進(jìn)程，便返回一同意接收的報(bào)文。 (3) 由系統(tǒng)S的Starter向系統(tǒng)S的內(nèi)核通知這個(gè)決定。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (4) 當(dāng)系統(tǒng)S的內(nèi)核接到通知后，先向D發(fā)送一份含有被遷移進(jìn)程P有關(guān)信息的報(bào)文。 (5) 在D接收到該報(bào)文后，如果本系統(tǒng)的現(xiàn)有資源尚不能滿足P的運(yùn)行需要，便拒絕進(jìn)程P的遷移；否則，由D向本系統(tǒng)的Starter轉(zhuǎn)發(fā)報(bào)文F。 (6) 由系統(tǒng)D的Starter利用遷入調(diào)用(

39、Migration Call)通知D：決定遷入進(jìn)程P。 (7) D準(zhǔn)備好進(jìn)程P所需要的資源，然后向S發(fā)送同意接收的報(bào)文。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.7 分布式操作系統(tǒng)中的進(jìn)程同步分布式操作系統(tǒng)中的進(jìn)程同步 1事件排序 在分布式操作系統(tǒng)中，為了實(shí)現(xiàn)進(jìn)程的同步，首先要對系統(tǒng)中發(fā)生的事件進(jìn)行排序，還要有良好的分布式同步算法。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 須遵循規(guī)則： 第一，根據(jù)事件發(fā)生的先后，賦予每個(gè)事件惟一的邏輯時(shí)鐘值。 第二，若事件a是進(jìn)程i發(fā)送的一條消息m，消息m中應(yīng)包含一個(gè)時(shí)間郵戳T(m)=Ci(a)；當(dāng)接收進(jìn)程j在收到消息時(shí)，如果其邏輯時(shí)鐘Cj

40、 Ci(a)，則應(yīng)當(dāng)重置Cj大于或等于Ci(a)(通常置Cj= Ci(a) +1)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 其次，看同步算法。在所有的同步算法中，都包含以下四項(xiàng)假設(shè)： (1) 每個(gè)分布式系統(tǒng)具有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有惟一的編號，可以從1到N。每個(gè)節(jié)點(diǎn)中僅有一個(gè)進(jìn)程提出訪問共享資源的請求。 (2) 按序傳送信息，即發(fā)送進(jìn)程按序發(fā)送消息，接收進(jìn)程也按相同順序接收消息。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (3) 每個(gè)消息能在有限的時(shí)間內(nèi)被正確地傳送到目標(biāo)進(jìn)程。 (4) 在處理機(jī)間能實(shí)現(xiàn)直接通信，即每個(gè)進(jìn)程能把消息直接發(fā)送到指定的進(jìn)程，不需要通過中轉(zhuǎn)處理機(jī)。第第9

41、 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2Lamport算法 在Lamport算法中，利用事件排序方法，對要求訪問臨界資源的全部事件進(jìn)行排序，并按照先來先服務(wù)原則，對事件進(jìn)行處理。該方法規(guī)定，每個(gè)進(jìn)程Pi在發(fā)送請求消息Request時(shí)，應(yīng)為它打上時(shí)間郵戳(Ti，i)(其中Ti是進(jìn)程Pi的邏輯時(shí)鐘值)；而在每一進(jìn)程中都保持一個(gè)請求隊(duì)列，隊(duì)列中包含了按邏輯時(shí)鐘排序的請求信息。Lamport算法用下述五個(gè)規(guī)則定義：第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 第一，當(dāng)進(jìn)程Pi請求訪問某個(gè)資源時(shí)，該進(jìn)程把請求信息掛在自己的請求隊(duì)列中，也送一Request(Ti，i)消息給所有其他進(jìn)程。 第二，

42、當(dāng)進(jìn)程Pj收到Request(Ti，i)消息時(shí)，形成一個(gè)打上郵戳的Reply(Tj，j)消息，將它放在自己的請求隊(duì)列中。應(yīng)該說明，若進(jìn)程Pj在收到Request(Tj，j)前也已提出過對同一資源的訪問請求，那么其郵戳?xí)r間應(yīng)比(Ti，i)小。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 第三，若滿足以下兩個(gè)條件，則允許進(jìn)程Pi訪問該資源： (1) Pi自身請求訪問該資源的消息已處于請求隊(duì)列的最前面。 (2) Pi已接收到從所有其他進(jìn)程發(fā)來的響應(yīng)消息，這些響應(yīng)消息上郵戳的時(shí)間晚于(Ti，i)。此條件表明，所有其他進(jìn)程或者都不訪問該資源，或者要求訪問，但時(shí)間較晚。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)

43、分布式計(jì)算機(jī)系統(tǒng) 第四，為了釋放該資源，Pi從自己的請求隊(duì)列中消去請求信息，且發(fā)送一打上時(shí)間郵戳的Release消息給其他所有進(jìn)程。 第五，當(dāng)進(jìn)程Pj收到進(jìn)程Pi的Release消息后，從自己的隊(duì)列中消去Pi的Request消息。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.8 分布式操作系統(tǒng)中的進(jìn)程互斥分布式操作系統(tǒng)中的進(jìn)程互斥 實(shí)現(xiàn)分布式互斥的幾點(diǎn)要求如下： (1) 安全性：在某一時(shí)刻至多只有一個(gè)進(jìn)程在臨界區(qū)內(nèi)執(zhí)行。 (2) 可用性：請求進(jìn)入臨界段的進(jìn)程終將準(zhǔn)入(只要在臨界區(qū)執(zhí)行的進(jìn)程最終離開臨界區(qū))。 (3) 定序：按關(guān)系排定的次序進(jìn)入臨界區(qū)。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布

44、式計(jì)算機(jī)系統(tǒng) 已經(jīng)提出了許多實(shí)現(xiàn)分布式系統(tǒng)中互斥的算法(Lamport 1978；Thomas 1979；Gifford 1979；Ricart and Agrawala 1981；Maekawa l985，等等)。盡管它們的要求和目的各不相同，但這些分布式算法都有如下的基本假定： (1) 一個(gè)分布式系統(tǒng)由n個(gè)場點(diǎn)組成，它們從1到n惟一地編號，每個(gè)場點(diǎn)含有一個(gè)進(jìn)程，而且進(jìn)程和場點(diǎn)間存在一一對應(yīng)的關(guān)系。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) (2) Pipeline特性成立，即從一個(gè)進(jìn)程發(fā)送給另一個(gè)進(jìn)程的消息是按它們發(fā)送的次序接收的。 (3) 每條消息在有窮的時(shí)間間隔內(nèi)都能正確地傳送到

45、它的目的地。 (4) 系統(tǒng)是全互連的，因而每個(gè)進(jìn)程都可直接給其他的進(jìn)程發(fā)送消息。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 1集中式算法 用于解決分布式互斥問題的集中式算法中，通常選定某個(gè)進(jìn)程負(fù)責(zé)協(xié)調(diào)進(jìn)入臨界區(qū)的工作，每個(gè)希望進(jìn)入臨界區(qū)(引用互斥)的進(jìn)程都得給協(xié)調(diào)者進(jìn)程發(fā)送一Request消息，僅當(dāng)此進(jìn)程接收到協(xié)調(diào)者的Reply消息時(shí)，它才可以進(jìn)入它的臨界區(qū)。當(dāng)它退出臨界區(qū)時(shí)，此進(jìn)程發(fā)送一Release消息給協(xié)調(diào)者進(jìn)程，然后繼續(xù)它的執(zhí)行。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2Ricart and Agrawla 算法 Lamport發(fā)表的時(shí)鐘同步算法中給出了第一個(gè)互斥算法。

46、Ricart和Agrawala 1981年改進(jìn)了Lamport算法，而且可以為分布式算法提供時(shí)間戳。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) Ricart and Agrawala算法的描述如下： (1) 當(dāng)進(jìn)程Pi要求訪問某個(gè)資源時(shí)，它發(fā)送一個(gè)Request(Ti，i)消息給所有其他進(jìn)程。 (2) 當(dāng)進(jìn)程Pj收到Request(Ti，i)消息后，執(zhí)行如下操作： 若進(jìn)程Pj正處在臨界區(qū)中，則推遲向進(jìn)程Pi發(fā)出Reply響應(yīng)； 若進(jìn)程Pj當(dāng)前并不要求訪問臨界資源，則立即返回一個(gè)有時(shí)間戳的Reply消息；第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 若進(jìn)程Pj也要求訪問臨界資源，而在消

47、息Request(Ti，i)中的郵戳?xí)r間早于(Tj，i)，同樣立即返回一個(gè)有時(shí)間戳的Reply消息，否則Pj保留Pi發(fā)來的消息Request(Ti，i)并推遲發(fā)出Reply響應(yīng)。 (3) 當(dāng)進(jìn)程Pi收到所有其他進(jìn)程發(fā)來的響應(yīng)時(shí)，便可訪問該資源。 (4) 當(dāng)進(jìn)程釋放該資源后，僅向所有推遲發(fā)來Reply消息的進(jìn)程發(fā)送Reply消息。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 該算法能夠獲得較好的性能：能夠?qū)崿F(xiàn)諸進(jìn)程對共享資源的互斥訪問；能夠保證不發(fā)生死鎖，因?yàn)樵谶M(jìn)程-資源圖中沒有環(huán)路；不會出現(xiàn)饑餓現(xiàn)象，因?yàn)閷蚕碣Y源的訪問是按照郵戳?xí)r間排序的，即按照FCFS原則服務(wù)的；每次對共享資源訪問時(shí)

48、，只要求發(fā)2(N-1)個(gè)消息。圖9.13說明了進(jìn)程在訪問共享資源時(shí)的狀態(tài)轉(zhuǎn)換。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 互斥請求從臨界區(qū)退出已收到所有的Reply消息給每個(gè)其他進(jìn)程發(fā)送一條Request消息將Reply消息回復(fù)給正等待進(jìn)入臨界區(qū)的進(jìn)程請求互斥等待計(jì)算激活其他進(jìn)程臨界區(qū)圖9.13 進(jìn)程在訪問共享資源時(shí)的狀態(tài)轉(zhuǎn)換圖第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 3令牌傳送法 1) 令牌傳送法的基本原理 為了實(shí)現(xiàn)進(jìn)程互斥，在系統(tǒng)中設(shè)置了象征存取權(quán)利的令牌(Token)。令牌本身是一種特定格式的報(bào)文，通常只有一個(gè)字節(jié)長，它不斷地在由進(jìn)程所組成的邏輯環(huán)(Logical Ring

49、)中循環(huán)。環(huán)中的每一個(gè)進(jìn)程都有惟一的前趨者(Predecessor)和惟一的后繼者(Successor)。這樣的邏輯結(jié)構(gòu)并不意味任何特定的物理拓?fù)?。第? 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 2) 令牌傳送法的性能及基本要求 利用令牌傳送法實(shí)現(xiàn)進(jìn)程互斥所需的消息數(shù)目是不定的。因?yàn)椴还苁欠裼羞M(jìn)程要求進(jìn)入其臨界區(qū)，令牌總是在邏輯環(huán)中循環(huán)。當(dāng)邏輯環(huán)中所有進(jìn)程都要求進(jìn)入其臨界區(qū)時(shí)，平均每個(gè)進(jìn)程訪問臨界資源只需一個(gè)消息。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 使用令牌傳送法時(shí)，必須滿足下述兩點(diǎn)要求： (1) 邏輯環(huán)應(yīng)能夠及時(shí)發(fā)現(xiàn)環(huán)路中某進(jìn)程失效或退出以及通信鏈路的故障。一旦發(fā)現(xiàn)了這種進(jìn)

50、程或故障，便應(yīng)立即撤消該進(jìn)程，并重構(gòu)邏輯環(huán)。 (2) 必須能保證邏輯環(huán)中在任何時(shí)候都有個(gè)令牌在循環(huán)。一旦發(fā)現(xiàn)令牌丟失，應(yīng)立即選定一個(gè)進(jìn)程來產(chǎn)生新令牌。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.9 分布式系統(tǒng)的資源管理分布式系統(tǒng)的資源管理 資源的調(diào)度和管理是操作系統(tǒng)的一項(xiàng)主要功能。單機(jī)操作系統(tǒng)通常采用一類資源由一個(gè)管理者來管理的集中式管理方法。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 分布式管理方式又可分為集中分布式管理和完全分布式(也稱分散)管理兩種方式。采用集中分布式管理，一類資源由多個(gè)管理者來管，但每個(gè)具體資源只存在一個(gè)管理者對其負(fù)責(zé)。 第第9 9章章 分布式計(jì)算機(jī)系

51、統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 分布管理方式與集中管理方式的主要區(qū)別是對同類資源采用多個(gè)管理者還是一個(gè)管理者。 集中分布管理方式讓資源管理者對他所管理的資源擁有全部控制權(quán)，而完全分布管理方式只允許資源管理者對資源擁有部分控制權(quán)。采用集中式管理時(shí)，一類資源只有一個(gè)管理者，他控制這類全部資源。 第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 9.10 死死 鎖鎖 處處 理理 分布式系統(tǒng)中的死鎖問題與單機(jī)系統(tǒng)類似，只是更為復(fù)雜，原因是所有與死鎖有關(guān)的信息都分布在多臺機(jī)器上。有些人把分布式死鎖分為兩類：通信死鎖與資源死鎖。實(shí)際上也沒有這個(gè)必要，因?yàn)榕c通信死鎖有關(guān)的信道、緩沖區(qū)等也是資源，所以完全可以將其歸并到資源死鎖中。第第9 9章章 分布式計(jì)算機(jī)系統(tǒng)分布式計(jì)算機(jī)系統(tǒng) 對死鎖問題的處理通常采取如下的策略：(1) 鴕鳥算法(不考慮死鎖問題)。(2) 死鎖檢測(允許死鎖發(fā)生，檢測井恢復(fù))。(3) 死鎖預(yù)防(靜態(tài)地使死鎖在結(jié)構(gòu)上不可能發(fā)生)。(4) 死鎖避免(通過精心分配資源，避免死鎖)。第第9 9章章