第二章 分布式通信機制

1、高高 級級 操操 作作 系系 統(tǒng)統(tǒng)1第二章第二章 分布式通信機制分布式通信機制高高 級級 操操 作作 系系 統(tǒng)統(tǒng)2 本章討論分布式系統(tǒng)中的通信問題。在考慮這一本章討論分布式系統(tǒng)中的通信問題。在考慮這一問題時，應(yīng)注意以下幾個方面：問題時，應(yīng)注意以下幾個方面： 發(fā)送策略發(fā)送策略：如何通過通信網(wǎng)發(fā)送消息？：如何通過通信網(wǎng)發(fā)送消息？ 連接策略連接策略：如何去連接彼此希望通信的進程？：如何去連接彼此希望通信的進程？ 爭奪處理爭奪處理：由于通信網(wǎng)是共享資源，應(yīng)注意解決：由于通信網(wǎng)是共享資源，應(yīng)注意解決在利用它的過程中那些有沖突的要求和沖突現(xiàn)象。在利用它的過程中那些有沖突的要求和沖突現(xiàn)象。 保密保密：如何保

2、住消息內(nèi)容的秘密？：如何保住消息內(nèi)容的秘密？ 通信機制通信機制：研究分布式操作系統(tǒng)中的基本通信機：研究分布式操作系統(tǒng)中的基本通信機制。制。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)32.1.1 發(fā)送策略發(fā)送策略 當(dāng)場點當(dāng)場點A上的一個進程希望同場點上的一個進程希望同場點B上的另一個進程進上的另一個進程進行通信時，如何發(fā)送消息？行通信時，如何發(fā)送消息？ 常用的幾種發(fā)送策略是：常用的幾種發(fā)送策略是： 固定發(fā)送固定發(fā)送:從從A到到B的信道事先已規(guī)定好并且不得更改，的信道事先已規(guī)定好并且不得更改，除非硬件的故障影響到它的通信能力。通常選擇物理上長除非硬件的故障影響到它的通信能力。通常選擇物理上長度最短的信道，

3、以減少通信開銷度最短的信道，以減少通信開銷。 虛擬線路虛擬線路:從從A到到B的信道在一段時期內(nèi)是固定的，在的信道在一段時期內(nèi)是固定的，在不同時期，從不同時期，從A向向B發(fā)送的消息可能經(jīng)由不同的信道發(fā)送。發(fā)送的消息可能經(jīng)由不同的信道發(fā)送。 動態(tài)發(fā)送動態(tài)發(fā)送:用于從用于從A到到B發(fā)送消息的信道僅當(dāng)該消息發(fā)發(fā)送消息的信道僅當(dāng)該消息發(fā)送時才確定。由于這種選擇是自動進行的，單一的消息可送時才確定。由于這種選擇是自動進行的，單一的消息可能分給不同的信道。能分給不同的信道。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)4上述幾種方案各有利弊。固定發(fā)送不適用于通信負載的上述幾種方案各有利弊。固定發(fā)送不適用于通信負載的改變

4、。即如果已在場點改變。即如果已在場點A和和B之間確立了一條信道，那之間確立了一條信道，那么消息只能經(jīng)由這條信道傳送，即使這條信道已經(jīng)超載，么消息只能經(jīng)由這條信道傳送，即使這條信道已經(jīng)超載，而其它信道還處于尚未滿載的狀態(tài)?？梢岳锰摂M線路而其它信道還處于尚未滿載的狀態(tài)?？梢岳锰摂M線路策略進行改善或通過動態(tài)發(fā)送策略來加以完全地解決。策略進行改善或通過動態(tài)發(fā)送策略來加以完全地解決。固定發(fā)送和虛擬線路策略可以確保按消息的發(fā)送次序從固定發(fā)送和虛擬線路策略可以確保按消息的發(fā)送次序從A向向B發(fā)送消息。采用動態(tài)發(fā)送策略，消息的到達次序發(fā)送消息。采用動態(tài)發(fā)送策略，消息的到達次序不一定和消息的發(fā)送次序相一致。這

5、可以通過給每條消不一定和消息的發(fā)送次序相一致。這可以通過給每條消息賦以一個順序號來解決。息賦以一個順序號來解決。 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)52.1.2 連接策略連接策略 有許多不同的方法來連接一對彼此希望通信的場點（或有許多不同的方法來連接一對彼此希望通信的場點（或進程）。最常用的方法有線路轉(zhuǎn)換、消息轉(zhuǎn)換和消息包轉(zhuǎn)進程）。最常用的方法有線路轉(zhuǎn)換、消息轉(zhuǎn)換和消息包轉(zhuǎn)換。換。 線路轉(zhuǎn)換線路轉(zhuǎn)換（circulate switch）：如果兩個進程希望通）：如果兩個進程希望通信，那么就在它們之間設(shè)立一條永久性的物理通信鏈路。信，那么就在它們之間設(shè)立一條永久性的物理通信鏈路。這條通信鏈路供其消息

6、轉(zhuǎn)移期間使用，在這段期間其它進這條通信鏈路供其消息轉(zhuǎn)移期間使用，在這段期間其它進程不能使用這條鏈路。這種方案與電話系統(tǒng)類似，一旦一程不能使用這條鏈路。這種方案與電話系統(tǒng)類似，一旦一條通話線路已對通話雙方開通（例如甲方給乙方打電話），條通話線路已對通話雙方開通（例如甲方給乙方打電話），其它人就不能使用這條信道，除非甲乙兩方已明顯地結(jié)束其它人就不能使用這條信道，除非甲乙兩方已明顯地結(jié)束其通話（例如一方已掛起話筒）。其通話（例如一方已掛起話筒）。 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)6n 消息轉(zhuǎn)換消息轉(zhuǎn)換（message switch）：如果兩個進程希）：如果兩個進程希望通信，那么就確定一個臨時的通信

7、鏈路供其消息轉(zhuǎn)移期望通信，那么就確定一個臨時的通信鏈路供其消息轉(zhuǎn)移期間使用。物理通信鏈路則根據(jù)需要在用戶間動態(tài)進行分配，間使用。物理通信鏈路則根據(jù)需要在用戶間動態(tài)進行分配，而且只允許使用較短的一段時間。每條消息由一個數(shù)據(jù)再而且只允許使用較短的一段時間。每條消息由一個數(shù)據(jù)再加上某些系統(tǒng)信息（如發(fā)送處，接收處和錯誤校正碼等）加上某些系統(tǒng)信息（如發(fā)送處，接收處和錯誤校正碼等）組成，這些系統(tǒng)信息將輔助通信網(wǎng)絡(luò)正確地將消息轉(zhuǎn)移到組成，這些系統(tǒng)信息將輔助通信網(wǎng)絡(luò)正確地將消息轉(zhuǎn)移到目的地。這種方案與郵局系統(tǒng)類似，每封信可看作是包含目的地。這種方案與郵局系統(tǒng)類似，每封信可看作是包含發(fā)送處和接收處的一條消息，而

8、且來自不同用戶的信件發(fā)送處和接收處的一條消息，而且來自不同用戶的信件（消息）可在相同通信線路上轉(zhuǎn)移。（消息）可在相同通信線路上轉(zhuǎn)移。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)7 消息包轉(zhuǎn)換消息包轉(zhuǎn)換（packet switch）：消息一般是可變長度的。）：消息一般是可變長度的。為了簡化系統(tǒng)的設(shè)計。常常把消息設(shè)計成定長的形式，并把這為了簡化系統(tǒng)的設(shè)計。常常把消息設(shè)計成定長的形式，并把這種定長的形式稱為消息包（種定長的形式稱為消息包（packet）。一條邏輯消息可能不得）。一條邏輯消息可能不得不劃分成若干消息包，每個消息包都可以經(jīng)由網(wǎng)絡(luò)中不同的路不劃分成若干消息包，每個消息包都可以經(jīng)由網(wǎng)絡(luò)中不同的路徑單獨

9、地發(fā)送到其目的地，當(dāng)這些消息包都到達其目的地后，徑單獨地發(fā)送到其目的地，當(dāng)這些消息包都到達其目的地后，還得拼裝起來組成一條完整的消息。還得拼裝起來組成一條完整的消息。 線路轉(zhuǎn)換需要安裝時間但傳送每條消息的開銷較少；消息線路轉(zhuǎn)換需要安裝時間但傳送每條消息的開銷較少；消息轉(zhuǎn)換和消息包轉(zhuǎn)換需要較少的安裝時間，但轉(zhuǎn)移每條消息的開轉(zhuǎn)換和消息包轉(zhuǎn)換需要較少的安裝時間，但轉(zhuǎn)移每條消息的開銷較大。此外，在采用消息包轉(zhuǎn)換方法時，每條消息可能得先銷較大。此外，在采用消息包轉(zhuǎn)換方法時，每條消息可能得先“化整為零化整為零”，然后再，然后再“集零為整集零為整”。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)82.1.3 爭奪處理爭

10、奪處理 由于一條通信鏈路往往連結(jié)多個場點，而這由于一條通信鏈路往往連結(jié)多個場點，而這些場點有可能希望同時在這條通信鏈路上轉(zhuǎn)移信些場點有可能希望同時在這條通信鏈路上轉(zhuǎn)移信息，從而發(fā)生爭奪現(xiàn)象。這種情況在環(huán)結(jié)構(gòu)或多息，從而發(fā)生爭奪現(xiàn)象。這種情況在環(huán)結(jié)構(gòu)或多存取總線結(jié)構(gòu)中表現(xiàn)得尤為突出。解決爭奪現(xiàn)象存取總線結(jié)構(gòu)中表現(xiàn)得尤為突出。解決爭奪現(xiàn)象的技術(shù)，常用的有的技術(shù)，常用的有沖突檢測沖突檢測，令牌轉(zhuǎn)移令牌轉(zhuǎn)移和和消息槽消息槽。 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)9 沖突檢測沖突檢測：一個場點要在某條通信線路上轉(zhuǎn)移消：一個場點要在某條通信線路上轉(zhuǎn)移消息之前，它必須進行監(jiān)測以確定當(dāng)前在該通信線路上是息之前，

11、它必須進行監(jiān)測以確定當(dāng)前在該通信線路上是否正在轉(zhuǎn)移另外的消息。若該通信線路空閑，則這個場否正在轉(zhuǎn)移另外的消息。若該通信線路空閑，則這個場點可以開始發(fā)送，否則它必須等待（同時繼續(xù)監(jiān)測），點可以開始發(fā)送，否則它必須等待（同時繼續(xù)監(jiān)測），直到這條線路空閑。直到這條線路空閑。 采用這種途徑的主要問題是，當(dāng)系統(tǒng)非常忙時，可采用這種途徑的主要問題是，當(dāng)系統(tǒng)非常忙時，可能發(fā)生許多沖突現(xiàn)象，因此整個系統(tǒng)的性能由于沖突檢能發(fā)生許多沖突現(xiàn)象，因此整個系統(tǒng)的性能由于沖突檢測方面的工作而受到衰減。這種方法已成功地用在以太測方面的工作而受到衰減。這種方法已成功地用在以太網(wǎng)系統(tǒng)。網(wǎng)系統(tǒng)。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)

12、10 令牌轉(zhuǎn)移令牌轉(zhuǎn)移（Token Passing）：令牌是一個特殊的）：令牌是一個特殊的消息類型，它不斷地在系統(tǒng)（通常在一個環(huán)結(jié)構(gòu)）中循消息類型，它不斷地在系統(tǒng)（通常在一個環(huán)結(jié)構(gòu)）中循環(huán)。希望轉(zhuǎn)移消息的場點必須等待直至令牌到達。當(dāng)令環(huán)。希望轉(zhuǎn)移消息的場點必須等待直至令牌到達。當(dāng)令牌到達后，該場點就從環(huán)中取走令牌并開始轉(zhuǎn)移它的消牌到達后，該場點就從環(huán)中取走令牌并開始轉(zhuǎn)移它的消息，當(dāng)它完成了相應(yīng)的消息轉(zhuǎn)移后再重新發(fā)送令牌，這息，當(dāng)它完成了相應(yīng)的消息轉(zhuǎn)移后再重新發(fā)送令牌，這就給另一個場點提供了占有令牌的機會，一旦占有，就就給另一個場點提供了占有令牌的機會，一旦占有，就可開始它的消息轉(zhuǎn)移。如果令牌丟

13、失。那么系統(tǒng)應(yīng)能發(fā)可開始它的消息轉(zhuǎn)移。如果令牌丟失。那么系統(tǒng)應(yīng)能發(fā)現(xiàn)這種情況并產(chǎn)生一個新令牌。該方法已由現(xiàn)這種情況并產(chǎn)生一個新令牌。該方法已由Primenet系系統(tǒng)所采用。統(tǒng)所采用。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)11 消息槽消息槽(slot)：若干定長的消息槽連續(xù)不斷地：若干定長的消息槽連續(xù)不斷地在系統(tǒng)（通常是一個環(huán)結(jié)構(gòu)）中循環(huán)。每個消息槽在系統(tǒng)（通常是一個環(huán)結(jié)構(gòu)）中循環(huán)。每個消息槽可以容納一定長的消息和有關(guān)的控制信息（如像發(fā)可以容納一定長的消息和有關(guān)的控制信息（如像發(fā)送處，接收處，消息槽滿送處，接收處，消息槽滿 / 空等）。希望轉(zhuǎn)移消息空等）。希望轉(zhuǎn)移消息的場點必須等待直到一個空消息槽到

14、達，然后，該的場點必須等待直到一個空消息槽到達，然后，該場點將它的消息插入這個空消息槽并附上適當(dāng)?shù)目貓鳇c將它的消息插入這個空消息槽并附上適當(dāng)?shù)目刂菩畔?，此消息在網(wǎng)絡(luò)中繼續(xù)流動，當(dāng)它到達某個制信息，此消息在網(wǎng)絡(luò)中繼續(xù)流動，當(dāng)它到達某個特定的場點時，該場點就查看此消息槽的控制信息，特定的場點時，該場點就查看此消息槽的控制信息，以確認此消息槽是否包含了發(fā)送給它的消息；若沒以確認此消息槽是否包含了發(fā)送給它的消息；若沒有，它就放過此消息槽，否則，它取走消息糟中的有，它就放過此消息槽，否則，它取走消息糟中的消息，重新設(shè)置控制信息以指明該消息槽為空。消息，重新設(shè)置控制信息以指明該消息槽為空。高高 級級 操操

15、 作作 系系 統(tǒng)統(tǒng)122.1.4 保密問題保密問題 編碼編碼是保護信息的常用方法之一。信息在發(fā)送之前先予是保護信息的常用方法之一。信息在發(fā)送之前先予以編碼，當(dāng)信息到達其目的地后就進行譯碼。以編碼，當(dāng)信息到達其目的地后就進行譯碼。 編碼技術(shù)，最常用的一種就是提供一個通用的編碼算法編碼技術(shù)，最常用的一種就是提供一個通用的編碼算法E，一個通用的譯碼算法一個通用的譯碼算法D，并對每次應(yīng)用提供一個保密鍵，并對每次應(yīng)用提供一個保密鍵（key），令），令Ek和和Dk分別表示具有保密鍵分別表示具有保密鍵k的那個特定應(yīng)用的的那個特定應(yīng)用的編碼和譯碼算法，那么，對于任何消息編碼和譯碼算法，那么，對于任何消息m，該

16、編碼系統(tǒng)必須滿，該編碼系統(tǒng)必須滿足下面的特性：足下面的特性： Dk(Ek(m) = m； Ek和和Dk都能有效地計算；都能有效地計算； 該系統(tǒng)的保密性只依賴于鍵該系統(tǒng)的保密性只依賴于鍵k的保密性而不依賴于算法的保密性而不依賴于算法E和和D的保密性。的保密性。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)13 一個稱之為一個稱之為“數(shù)據(jù)編碼標準數(shù)據(jù)編碼標準”（Data Encryption Standard)的編碼系統(tǒng)已由美國國家標準局所采用。不過，該的編碼系統(tǒng)已由美國國家標準局所采用。不過，該方案還存在方案還存在“鍵分布鍵分布”問題，即，開始通信之前，保密鍵必問題，即，開始通信之前，保密鍵必須秘密地轉(zhuǎn)移給

17、發(fā)送者和接收者，但在一個通信網(wǎng)絡(luò)環(huán)境中須秘密地轉(zhuǎn)移給發(fā)送者和接收者，但在一個通信網(wǎng)絡(luò)環(huán)境中很難有效地完成這一點。解決此問題的辦法之一是利用一個很難有效地完成這一點。解決此問題的辦法之一是利用一個“公共鍵公共鍵”（public key）編碼方案。每個用戶有一個公共鍵）編碼方案。每個用戶有一個公共鍵和一個私有鍵，兩個彼此知道他們的公共鍵的用戶才可以相和一個私有鍵，兩個彼此知道他們的公共鍵的用戶才可以相互通信?；ネㄐ?。 基于上述思想的編碼方案已設(shè)計出來了。這個方案曾被基于上述思想的編碼方案已設(shè)計出來了。這個方案曾被認為是差不多不可破譯的。其中的公共編碼鍵是一對偶認為是差不多不可破譯的。其中的公共編碼

18、鍵是一對偶(e, n)，私有鍵是對偶私有鍵是對偶(d, n),這里這里e, d, n都是正整數(shù)。每條消息用都是正整數(shù)。每條消息用0n-1之間的一個整數(shù)表示（較長的消息可分成若干較短的消息，之間的一個整數(shù)表示（較長的消息可分成若干較短的消息，它們每一個都可用這樣的一個整數(shù)表示），函數(shù)它們每一個都可用這樣的一個整數(shù)表示），函數(shù)E和和D定義為：定義為：高高 級級 操操 作作 系系 統(tǒng)統(tǒng)14E(m) = me mod n = C D(C) = Cd mod n 這里的主要問題是選擇編碼和譯碼鍵。整數(shù)這里的主要問題是選擇編碼和譯碼鍵。整數(shù)n可用下式計可用下式計算算n = p q 其中其中p和和q是隨機選

19、取的兩個較大的素數(shù)（例如，它們是是隨機選取的兩個較大的素數(shù)（例如，它們是由由100位或更多位數(shù)字組成），位或更多位數(shù)字組成），d是隨機選取的一個與是隨機選取的一個與(p - 1) (q - 1)互質(zhì)的較大整數(shù)，即互質(zhì)的較大整數(shù)，即d滿足滿足GCD(d, (p - 1) (q - 1) = 1 而而e則應(yīng)滿足則應(yīng)滿足e d mod (p - 1) (q - 1) = 1 應(yīng)指出的是，雖然應(yīng)指出的是，雖然n可能是大家知道的，但可能是大家知道的，但p和和q卻很難為卻很難為他人所知。因為，對這里的他人所知。因為，對這里的n進行因式分解是比鉸困難的。因進行因式分解是比鉸困難的。因此，此，d和和e也是不易

20、試探出來的。也是不易試探出來的。 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)15例如，令例如，令p = 5和和q = 7，那么，那么n = 35，(p - 1) (q - 1) 24。由于由于11與與24互質(zhì)，所以可選取互質(zhì)，所以可選取d = 11。因為。因為11 11 mod 2412l mod 24 = 1，因此，因此，e = 11。假定，給定。假定，給定m3，那么，那么C = me mod n = 311 mod 35 = 12而而Cd mod n = 1211 mod 35 = 3 =m因此，如果我們利用因此，如果我們利用e對進行編碼，那么，我們就能用對對進行編碼，那么，我們就能用對它進行譯碼

21、。它進行譯碼。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)162.2 消息傳遞消息傳遞2.2.1 消息傳遞原語消息傳遞原語 在分布式系統(tǒng)中，進程相互通信是通過彼此交換消在分布式系統(tǒng)中，進程相互通信是通過彼此交換消息進行的。一個消息是從一進程發(fā)往另一些進程的信息息進行的。一個消息是從一進程發(fā)往另一些進程的信息單位。源進程通過執(zhí)行單位。源進程通過執(zhí)行send操作發(fā)送消息，宿進程則通操作發(fā)送消息，宿進程則通過執(zhí)行過執(zhí)行receive操作來獲取消息；如果必要，在其獲取消操作來獲取消息；如果必要，在其獲取消息后再通過執(zhí)行息后再通過執(zhí)行reply操作給發(fā)送者一個回復(fù)。因此，分操作給發(fā)送者一個回復(fù)。因此，分布式操作系

22、統(tǒng)通常提供布式操作系統(tǒng)通常提供send、receive和和reply等基本通信等基本通信原語來實現(xiàn)進程間的通信和同步。原語來實現(xiàn)進程間的通信和同步。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)17 消息轉(zhuǎn)移原語分為兩類：同步型和異步型。消息轉(zhuǎn)移原語分為兩類：同步型和異步型。 1.異步型異步型：在這類通信機制中，轉(zhuǎn)移消息的進程不等待：在這類通信機制中，轉(zhuǎn)移消息的進程不等待接收者的回復(fù)，又稱接收者的回復(fù)，又稱“不等不等”轉(zhuǎn)移（轉(zhuǎn)移（send no Wait)，即允許，即允許發(fā)送方可任意超前于接收方，因而具有下面的特征：發(fā)送方可任意超前于接收方，因而具有下面的特征： 接收方收到的消息與發(fā)送方目前的狀態(tài)是無關(guān)的

23、；接收方收到的消息與發(fā)送方目前的狀態(tài)是無關(guān)的； 由于通信機制與同步機制幾乎被截然分開，因此，系由于通信機制與同步機制幾乎被截然分開，因此，系統(tǒng)應(yīng)具有統(tǒng)應(yīng)具有“無限無限”的緩沖空間來容納任意超前發(fā)出而尚未處的緩沖空間來容納任意超前發(fā)出而尚未處理的消息，以此來解決消息發(fā)送速度和消息處理速度之間的理的消息，以此來解決消息發(fā)送速度和消息處理速度之間的差異；差異； 能比較充分地利用系統(tǒng)的潛在能力，但實現(xiàn)時須解決能比較充分地利用系統(tǒng)的潛在能力，但實現(xiàn)時須解決許多實際的控制問題。許多實際的控制問題。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)18圖圖2.2 同步消息傳遞和異步消息傳遞同步消息傳遞和異步消息傳遞高高 級

24、級 操操 作作 系系 統(tǒng)統(tǒng)19 2.同步型同步型：它與異步型消息轉(zhuǎn)移正好相反，總是要求發(fā)：它與異步型消息轉(zhuǎn)移正好相反，總是要求發(fā)送方等待接收方的回復(fù)，然后，發(fā)送方與接入方同步繼送方等待接收方的回復(fù)，然后，發(fā)送方與接入方同步繼續(xù)向下執(zhí)行，其主要特征是：續(xù)向下執(zhí)行，其主要特征是： 消息的發(fā)送方和接收方在完成信息交換后彼此知道消息的發(fā)送方和接收方在完成信息交換后彼此知道對方的狀態(tài)；對方的狀態(tài)； 同步機制和通信機制合二為一，一般無需大的緩沖同步機制和通信機制合二為一，一般無需大的緩沖區(qū)；區(qū)； 實現(xiàn)容易，但效率較低。實現(xiàn)容易，但效率較低。同步型消息轉(zhuǎn)移和異步型消息轉(zhuǎn)移示意圖，見圖同步型消息轉(zhuǎn)移和異步型消

25、息轉(zhuǎn)移示意圖，見圖2.2。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)20 消息本身要占用存貯空間，并常常存放在系統(tǒng)的消息本身要占用存貯空間，并常常存放在系統(tǒng)的緩沖區(qū)中。當(dāng)使們異步消息轉(zhuǎn)移機制時，系統(tǒng)中的每緩沖區(qū)中。當(dāng)使們異步消息轉(zhuǎn)移機制時，系統(tǒng)中的每個進程在某一時刻可能有多個尚未處理的消息。由于個進程在某一時刻可能有多個尚未處理的消息。由于消息緩沖區(qū)是一個有窮的資源，因此，當(dāng)使用異步消消息緩沖區(qū)是一個有窮的資源，因此，當(dāng)使用異步消息傳遞方式傳遞消息時，可能會發(fā)生消息緩沖區(qū)溢出息傳遞方式傳遞消息時，可能會發(fā)生消息緩沖區(qū)溢出的情況。因此，異步消息傳遞需要特定的消息緩沖區(qū)的情況。因此，異步消息傳遞需要特定的

26、消息緩沖區(qū)管理算法來處理這方面的問題。但在采用同步消息傳管理算法來處理這方面的問題。但在采用同步消息傳遞方式時，系統(tǒng)中的每個進程決不可能存在一個以上遞方式時，系統(tǒng)中的每個進程決不可能存在一個以上尚未處理的消息，因此，其消息緩沖區(qū)的管理算法比尚未處理的消息，因此，其消息緩沖區(qū)的管理算法比較簡單。較簡單。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)212.2.2 同步消息傳遞方式的應(yīng)用同步消息傳遞方式的應(yīng)用 同步消息轉(zhuǎn)移方式特別適合于同步消息轉(zhuǎn)移方式特別適合于client / server模型。一個模型。一個client通過向一個通過向一個server發(fā)送一個消息來請求該發(fā)送一個消息來請求該server為它

27、服務(wù)，為它服務(wù)，然后這個然后這個client就掛起，直至對應(yīng)的就掛起，直至對應(yīng)的server發(fā)來回復(fù)消息（即告發(fā)來回復(fù)消息（即告之所請求的服務(wù)已經(jīng)完成）。之所請求的服務(wù)已經(jīng)完成）。server可以寫成一個無窮循環(huán)程可以寫成一個無窮循環(huán)程序，它等待接收請求，然后處理相應(yīng)的請求，最后發(fā)回復(fù)消息。序，它等待接收請求，然后處理相應(yīng)的請求，最后發(fā)回復(fù)消息。client們在等待所請求的服跟務(wù)完成時就阻塞自己。僅當(dāng)沒有消們在等待所請求的服跟務(wù)完成時就阻塞自己。僅當(dāng)沒有消息給息給server，即沒有供它做的事情時，該，即沒有供它做的事情時，該server就阻塞，見圖就阻塞，見圖2.3，其中，其中c1ient們

28、向們向time-server發(fā)送一請求給出時間的消息：發(fā)送一請求給出時間的消息：send(time-server，gettime.time)。time-server循環(huán)等待請求讀循環(huán)等待請求讀時鐘的消息，然后執(zhí)行時鐘的消息，然后執(zhí)行“讀時鐘讀時鐘”工作，并在處理下一請求消工作，并在處理下一請求消息之前發(fā)出回復(fù)，即息之前發(fā)出回復(fù)，即time-server和和client可分別編寫成如下的程可分別編寫成如下的程序段：序段：高高 級級 操操 作作 系系 統(tǒng)統(tǒng)22timeserver:while true doreceive(request);readclock(time);reply(time);e

29、nd;client：send(timeserver, gettime, time);圖圖2.3 使用消息轉(zhuǎn)移方式的使用消息轉(zhuǎn)移方式的client / server模型模型高高 級級 操操 作作 系系 統(tǒng)統(tǒng)23 一般，一般，server可以設(shè)計成依次重復(fù)執(zhí)行下述步驟的程序段：可以設(shè)計成依次重復(fù)執(zhí)行下述步驟的程序段： 等待接收來自等待接收來自clients發(fā)送的發(fā)送的“請求服務(wù)請求服務(wù)”的消息；的消息； 接收接收clients發(fā)來的發(fā)來的“請求服務(wù)請求服務(wù)”的消息；的消息； 處理處理clients發(fā)來的發(fā)來的“請求服務(wù)請求服務(wù)”的消息；的消息； 向向clients發(fā)送發(fā)送“服務(wù)已完成服務(wù)已完成”的

30、回復(fù)消息。的回復(fù)消息。 僅當(dāng)沒有僅當(dāng)沒有“請求服務(wù)請求服務(wù)”的消息到達時，的消息到達時，server就阻塞自己。就阻塞自己。clients在等待在等待server的回復(fù)消息時就阻塞它們自己，從而實現(xiàn)了的回復(fù)消息時就阻塞它們自己，從而實現(xiàn)了clients與與server的同步。的同步。 在設(shè)計在設(shè)計server進程時，通常要求：進程時，通常要求： server必須能調(diào)度和回復(fù)多個并發(fā)的請求消息；必須能調(diào)度和回復(fù)多個并發(fā)的請求消息； server處理請求消息和發(fā)送回復(fù)消息的次序與接收該請?zhí)幚碚埱笙⒑桶l(fā)送回復(fù)消息的次序與接收該請求消息的次序無關(guān)；求消息的次序無關(guān)； 在在server給給client

31、發(fā)送回復(fù)消息時，決不應(yīng)阻塞；發(fā)送回復(fù)消息時，決不應(yīng)阻塞； 某個相關(guān)的某個相關(guān)的client故障，不應(yīng)影響故障，不應(yīng)影響server的操作。的操作。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)24 同步原語有一種與信息交換不同的特性。當(dāng)一個進程同步原語有一種與信息交換不同的特性。當(dāng)一個進程引用了一個掛起的原語時，它就阻塞自己直至此原語執(zhí)行引用了一個掛起的原語時，它就阻塞自己直至此原語執(zhí)行完畢。同步原語的這種完畢。同步原語的這種”阻塞阻塞”特性，類似于單處理機中特性，類似于單處理機中所使用的信號量，可用于同步目的。圖所使用的信號量，可用于同步目的。圖2.4(a)展示了兩個進展示了兩個進程使用信號量進行同步例

32、子，其中，當(dāng)程使用信號量進行同步例子，其中，當(dāng)P1在信號量在信號量sem上上等待時，它就彼阻塞直至等待時，它就彼阻塞直至P2喚醒它。一個進程等待另一進喚醒它。一個進程等待另一進程的類似效果也可利用同步程的類似效果也可利用同步send / receive原語實現(xiàn)，見圖原語實現(xiàn)，見圖2.4(b)。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)25圖圖2.4 同步同步高高 級級 操操 作作 系系 統(tǒng)統(tǒng)26 還有不少其它形式的還有不少其它形式的send / receive原語。例如，原語。例如，“選擇選擇性接收性接收”（selective receive）和）和”條件發(fā)送條件發(fā)送”（conditional sen

33、d）。一個）。一個selective receive操作允許其用戶選擇一個進程操作允許其用戶選擇一個進程或一組進程去接收發(fā)送來的消息。當(dāng)執(zhí)行或一組進程去接收發(fā)送來的消息。當(dāng)執(zhí)行conditional send操操作時，如果相關(guān)的接收者不是處于阻塞狀態(tài)正等待接收消息，作時，如果相關(guān)的接收者不是處于阻塞狀態(tài)正等待接收消息，那么它將立即完成而不發(fā)送消息。實際上，大多數(shù)異步那么它將立即完成而不發(fā)送消息。實際上，大多數(shù)異步send操作后緊隨著一個操作后緊隨著一個receive操作?；谶@個原因，許多分布式操作?；谶@個原因，許多分布式操作系統(tǒng)只提供同步消息傳遞原語。操作系統(tǒng)只提供同步消息傳遞原語。 高高

34、 級級 操操 作作 系系 統(tǒng)統(tǒng)272.3 遠程過程調(diào)用遠程過程調(diào)用 遠程過程調(diào)用遠程過程調(diào)用（Remote Procedure Call）就是把）就是把過程調(diào)用的概念加以擴允后引入分布式環(huán)境中的一種過程調(diào)用的概念加以擴允后引入分布式環(huán)境中的一種形式。遠程過程調(diào)用的形式和行為與傳統(tǒng)的過程調(diào)用形式。遠程過程調(diào)用的形式和行為與傳統(tǒng)的過程調(diào)用的形式和行為類似，主要差別在于被調(diào)用的過程實際的形式和行為類似，主要差別在于被調(diào)用的過程實際運行在一個與調(diào)用者所在場點不同的場點上，見圖運行在一個與調(diào)用者所在場點不同的場點上，見圖2.6。因此，需要設(shè)計相應(yīng)的軟件來實現(xiàn)兩者之間的連接和因此，需要設(shè)計相應(yīng)的軟件來實現(xiàn)

35、兩者之間的連接和信息溝通。信息溝通。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)28圖圖2.5 消息轉(zhuǎn)移與過程調(diào)用的類似性消息轉(zhuǎn)移與過程調(diào)用的類似性圖圖2.6 遠程過程調(diào)用示意圖遠程過程調(diào)用示意圖高高 級級 操操 作作 系系 統(tǒng)統(tǒng)292.3.1 RPC機制的結(jié)構(gòu)及實現(xiàn)機制的結(jié)構(gòu)及實現(xiàn)1.RPC機制的結(jié)構(gòu)機制的結(jié)構(gòu)由下列成份組成：由下列成份組成：stub：client和和server 各一個；各一個；控制部分：為追蹤控制部分：為追蹤RPC的調(diào)用狀態(tài)所設(shè)；的調(diào)用狀態(tài)所設(shè)；傳送部分：確定如何將信息從一個場點傳送到另一個傳送部分：確定如何將信息從一個場點傳送到另一個場點。場點。實現(xiàn)實現(xiàn)RPC的一般過程可概括如圖

36、的一般過程可概括如圖2.7所示：所示：圖圖2.7 實現(xiàn)實現(xiàn)RPC的一般過程的一般過程高高 級級 操操 作作 系系 統(tǒng)統(tǒng)30nclients stub與一個與一個client連接，它對于該連接，它對于該client就像一個就像一個“server”。在調(diào)用時，它截取。在調(diào)用時，它截取client的遠程過程調(diào)用命令后，利用通信網(wǎng)絡(luò)向的遠程過程調(diào)用命令后，利用通信網(wǎng)絡(luò)向server發(fā)送發(fā)送“請求服務(wù)請求服務(wù)”的信息。在返回時，的信息。在返回時，它獲取返回消息，并帶返回結(jié)果返回到它獲取返回消息，并帶返回結(jié)果返回到client，然后然后client繼續(xù)執(zhí)行。繼續(xù)執(zhí)行。 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)3

37、1nServers stub與一個與一個server連接，它對于該連接，它對于該server就像一個就像一個“client”。在調(diào)用時，它收到遠程調(diào)用請。在調(diào)用時，它收到遠程調(diào)用請求后，產(chǎn)生一個本地調(diào)用，去執(zhí)行被請求的遠程過求后，產(chǎn)生一個本地調(diào)用，去執(zhí)行被請求的遠程過程。在返回時，它截取遠程過程的返回結(jié)果，并形程。在返回時，它截取遠程過程的返回結(jié)果，并形成返回消息發(fā)送出去。成返回消息發(fā)送出去。nstub包含了一組包含了一組RPC機制的操作原話，這些原語構(gòu)機制的操作原話，這些原語構(gòu)成了成了RPC調(diào)用的實現(xiàn)細節(jié)，它可獨立于調(diào)用的實現(xiàn)細節(jié)，它可獨立于client和和server編程，在編譯時再連接起

38、來編程，在編譯時再連接起來 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)32nRPC的實現(xiàn)要考慮兩個方面的問題。第一，當(dāng)進行遠程過的實現(xiàn)要考慮兩個方面的問題。第一，當(dāng)進行遠程過程調(diào)用時，調(diào)用場點必須能定位出被調(diào)用的過程實際上運程調(diào)用時，調(diào)用場點必須能定位出被調(diào)用的過程實際上運行在哪個場點上；第二，相關(guān)的兩個場點必須能協(xié)同合作行在哪個場點上；第二，相關(guān)的兩個場點必須能協(xié)同合作交換信息。所有這些對用戶都是透明的，這些的工作是依交換信息。所有這些對用戶都是透明的，這些的工作是依次進行的。下面介紹一種實現(xiàn)次進行的。下面介紹一種實現(xiàn)RPC的方法其實現(xiàn)思想已的方法其實現(xiàn)思想已概括在圖概括在圖2.8中。中。高高 級級

39、 操操 作作 系系 統(tǒng)統(tǒng)33圖圖2.8 RPC的實現(xiàn)概況的實現(xiàn)概況高高 級級 操操 作作 系系 統(tǒng)統(tǒng)34 每個遠程過程由若干成分組成：每個遠程過程由若干成分組成：l調(diào)用者（調(diào)用者（caller）或用戶（）或用戶（user）l調(diào)用代碼段調(diào)用代碼段l以及被調(diào)用者（以及被調(diào)用者（callee）或）或serverl被調(diào)用代碼段。這些都可用常規(guī)的程序設(shè)計語言編寫，被調(diào)用代碼段。這些都可用常規(guī)的程序設(shè)計語言編寫， 不需要利用特別的設(shè)施，就象它們在同一場點上執(zhí)行不需要利用特別的設(shè)施，就象它們在同一場點上執(zhí)行一一 樣。樣。l與調(diào)用者相關(guān)的與調(diào)用者相關(guān)的stubl與被調(diào)用者相關(guān)的與被調(diào)用者相關(guān)的stublRPC

40、 runtime子程序，可在系統(tǒng)中所有場點上運行。子程序，可在系統(tǒng)中所有場點上運行。2. RPC的實現(xiàn)的實現(xiàn)高高 級級 操操 作作 系系 統(tǒng)統(tǒng)35nstub程序的功能是把這種過程調(diào)用中所帶的參數(shù)組程序的功能是把這種過程調(diào)用中所帶的參數(shù)組裝和拆卸成消息形式，并進行相應(yīng)的類型檢查，然裝和拆卸成消息形式，并進行相應(yīng)的類型檢查，然后把這些消息轉(zhuǎn)移給后把這些消息轉(zhuǎn)移給RPC runtime子程序，后者再子程序，后者再把它們發(fā)送到系統(tǒng)中的其它場點。把它們發(fā)送到系統(tǒng)中的其它場點。n程序設(shè)計者定義了過程并寫好了過程體，而系統(tǒng)生程序設(shè)計者定義了過程并寫好了過程體，而系統(tǒng)生成了對應(yīng)的成了對應(yīng)的stub。實現(xiàn)一個遠

41、程過程調(diào)用的主要工。實現(xiàn)一個遠程過程調(diào)用的主要工作環(huán)節(jié)如下。作環(huán)節(jié)如下。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)36n調(diào)用者用通常方式調(diào)用對應(yīng)調(diào)用者用通常方式調(diào)用對應(yīng)stub中的一個過程；中的一個過程；n這個這個stub過程把有關(guān)的參數(shù)組裝成一個消息包過程把有關(guān)的參數(shù)組裝成一個消息包或一組消息包，以形成一條消息。運行此過程的或一組消息包，以形成一條消息。運行此過程的那個場點的那個場點的“地址地址”和那個場點上指稱此過程的和那個場點上指稱此過程的“標識符標識符”都應(yīng)包含在這條消息中；都應(yīng)包含在這條消息中；n將這條消息發(fā)送給對應(yīng)的將這條消息發(fā)送給對應(yīng)的RPC runtme子程序，子程序，該子程序再把它發(fā)

42、送給指定的場點。該子程序再把它發(fā)送給指定的場點。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)37n在接收此消息時，遠程在接收此消息時，遠程runtime子程序引用與被子程序引用與被調(diào)用者對應(yīng)的調(diào)用者對應(yīng)的stub中的一個子程序，并讓它來處中的一個子程序，并讓它來處理這條消息；理這條消息；n被調(diào)用者對應(yīng)的被調(diào)用者對應(yīng)的stub中的這個子程序拆卸有關(guān)中的這個子程序拆卸有關(guān)的參數(shù)并用通常的過程調(diào)用方式調(diào)用所需的過程。的參數(shù)并用通常的過程調(diào)用方式調(diào)用所需的過程。n返回調(diào)用結(jié)果，整個遠程過程調(diào)用以與調(diào)用者對返回調(diào)用結(jié)果，整個遠程過程調(diào)用以與調(diào)用者對應(yīng)的應(yīng)的stub程序執(zhí)行程序執(zhí)行“return”語句返回到用戶而終

43、語句返回到用戶而終止。止。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)38 在上面的述中，我們回避了一個重要的問題，即與在上面的述中，我們回避了一個重要的問題，即與用戶對應(yīng)的用戶對應(yīng)的stub如何知道實際運行遠程過程的場點之地如何知道實際運行遠程過程的場點之地址呢？址呢？一些解決這一向題的方法：一些解決這一向題的方法：n 當(dāng)系統(tǒng)生成與調(diào)用者對應(yīng)的當(dāng)系統(tǒng)生成與調(diào)用者對應(yīng)的stub時，可把該遠程時，可把該遠程場地的地址也一同并入其中，不過這種做法不太靈活。場地的地址也一同并入其中，不過這種做法不太靈活。n 在進行調(diào)用之前，與調(diào)用者對應(yīng)的在進行調(diào)用之前，與調(diào)用者對應(yīng)的stub向系統(tǒng)中向系統(tǒng)中的其它場點進行廣播

44、，請求有關(guān)的場點通報其地址，這的其它場點進行廣播，請求有關(guān)的場點通報其地址，這必然引起一系列的消息轉(zhuǎn)移。特別，當(dāng)這種廣播是在若必然引起一系列的消息轉(zhuǎn)移。特別，當(dāng)這種廣播是在若干網(wǎng)絡(luò)之間進行時，其轉(zhuǎn)移速度是很慢的。干網(wǎng)絡(luò)之間進行時，其轉(zhuǎn)移速度是很慢的。n 由系統(tǒng)管理一個表，其表項的內(nèi)容為由系統(tǒng)管理一個表，其表項的內(nèi)容為n 場點地址；場點地址；n 該場點上將運行的遠程過程的名字。該場點上將運行的遠程過程的名字。n 高高 級級 操操 作作 系系 統(tǒng)統(tǒng)392.3.2 RPC執(zhí)行時各部分之間的關(guān)系執(zhí)行時各部分之間的關(guān)系 RPC執(zhí)行時，各部分的關(guān)系如圖執(zhí)行時，各部分的關(guān)系如圖2.9所示。其中，所示。其中，

45、傳輸部分是傳輸部分是RPC的最低層，其主要功能為：的最低層，其主要功能為：n 提供對網(wǎng)絡(luò)傳輸層協(xié)議的選擇；提供對網(wǎng)絡(luò)傳輸層協(xié)議的選擇；n 建立建立 / 釋放邏輯信道，發(fā)送釋放邏輯信道，發(fā)送 / 接收消息等；接收消息等；n 管理管理RPC中的消息緩沖區(qū)。中的消息緩沖區(qū)。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)40圖2.9 RPC執(zhí)行時各部分的關(guān)系圖高高 級級 操操 作作 系系 統(tǒng)統(tǒng)41 控制部分的主要功能是：控制部分的主要功能是： 確定確定RPC中消息的方向（發(fā)送或接收）；中消息的方向（發(fā)送或接收）； 當(dāng)當(dāng)client的的stub開始一次開始一次RPC調(diào)用或者調(diào)用或者server向向server的的s

46、tub返回調(diào)用結(jié)果時，該部分負責(zé)控制傳輸部分進行發(fā)返回調(diào)用結(jié)果時，該部分負責(zé)控制傳輸部分進行發(fā)送。送。 場點間會合與進程同步；場點間會合與進程同步；場點間會合是指為使兩個場點間進程同步，它們必須同場點間會合是指為使兩個場點間進程同步，它們必須同意意“會合（會合（rendezvous）”，即早到達的進程要等待晚到，即早到達的進程要等待晚到達的進程。會話進程通過場點間會合建立一致的起點，達的進程。會話進程通過場點間會合建立一致的起點，并以該起點作為進程同步點進行對話。并以該起點作為進程同步點進行對話。 若干狀態(tài)信息的處理。若干狀態(tài)信息的處理。由上可知，由于由上可知，由于client的的stub的作

47、用，使得的作用，使得client可用常規(guī)可用常規(guī)過程調(diào)用方式去調(diào)用遠程過程；由于過程調(diào)用方式去調(diào)用遠程過程；由于server的的stub的作用，的作用，使得使得server程序可以獨立于調(diào)用者來編程，因而比較靈活。程序可以獨立于調(diào)用者來編程，因而比較靈活。高高 級級 操操 作作 系系 統(tǒng)統(tǒng)42n 本地調(diào)用和遠程過程調(diào)用之間存在許多不同之處。如本地調(diào)用和遠程過程調(diào)用之間存在許多不同之處。如果遠程調(diào)用是在兩種異型機器間進行，這就存在數(shù)據(jù)表示果遠程調(diào)用是在兩種異型機器間進行，這就存在數(shù)據(jù)表示問題，例如，這兩類機器的字長可能不同。解決這一向題問題，例如，這兩類機器的字長可能不同。解決這一向題的方法之一

48、是它在轉(zhuǎn)移數(shù)據(jù)之前，讓的方法之一是它在轉(zhuǎn)移數(shù)據(jù)之前，讓RPC機制將有關(guān)的數(shù)機制將有關(guān)的數(shù)據(jù)轉(zhuǎn)換成一種統(tǒng)一的格式，接收場點在接收數(shù)據(jù)時，再把據(jù)轉(zhuǎn)換成一種統(tǒng)一的格式，接收場點在接收數(shù)據(jù)時，再把它們轉(zhuǎn)換成本地所允許的數(shù)據(jù)格式。第二個問題是如何解它們轉(zhuǎn)換成本地所允許的數(shù)據(jù)格式。第二個問題是如何解釋指針，更確切他說，一個指針到底訪問的是什么，在不釋指針，更確切他說，一個指針到底訪問的是什么，在不具有共享地址空間的情況下，具有共享地址空間的情況下，RPC不可能允許在網(wǎng)絡(luò)范圍不可能允許在網(wǎng)絡(luò)范圍內(nèi)轉(zhuǎn)移指針。因此，在內(nèi)轉(zhuǎn)移指針。因此，在RPC中是不可能用中是不可能用“reference方式方式”傳遞參數(shù)的。傳遞參數(shù)的。n 2.3.3 RPC的語義的語義高高 級級 操操 作作 系系 統(tǒng)統(tǒng)43n 更嚴重的問題是調(diào)用者和被調(diào)用者都可能在調(diào)更嚴重的問題是調(diào)用者和被調(diào)用者都可能在調(diào)用期間發(fā)生故障，而且經(jīng)常是被調(diào)用者故障，留下用期間發(fā)生故障，而