分布式操作系統(tǒng)2(3)

1、發(fā)送和接收原語發(fā)送和接收原語 RPC是一個(gè)比send和 receive更常使用的通訊機(jī)制，它很難與組通信相融合。給一個(gè)組發(fā)送一條消息不能作為一個(gè)過程調(diào)用。因?yàn)樵赗PC中，客戶發(fā)送一條消息到服務(wù)器，之后返回一個(gè)結(jié)果，但在組通信中，對一條請求可能會有N個(gè)應(yīng)答，如何能處理這N個(gè)應(yīng)答呢?因此，一個(gè)常用的方法就是采用單向通信模型send和 receive的顯式調(diào)用，而不采用基于RPC的雙向通信模型請求/應(yīng)答(request/reply)。應(yīng)答的消息本身是獨(dú)立的消息，與先前的請求不相關(guān)。有時(shí)也需要得到與請求相關(guān)的應(yīng)答，以此來接近RPC的通信的方式。在這種情況下，在發(fā)送一條消息后，而要啟動(dòng)一個(gè)進(jìn)程重復(fù)調(diào)用g

2、etreply來收集所有應(yīng)答，每調(diào)用一次getreply可收到一個(gè)應(yīng)答。有些系統(tǒng)引入新的庫例程，group-send,group-receive。 原子性原子性 一條消息發(fā)送給一個(gè)組后，不是該組所有成員都正確收到，就是均未收到，不允許出現(xiàn)組內(nèi)有些成員收到而有些成員收不到的情況。具有要么全有要么全無的傳遞叫做原子性或原子廣播通信。原子性可使分布式系統(tǒng)編程容易得多。當(dāng)一進(jìn)程發(fā)送消息給組時(shí)，不必?fù)?dān)心如果組成員沒有收到消息該怎么辦。 實(shí)現(xiàn)原子廣播通信并起來那么簡單。因?yàn)榻邮粘瑫r(shí)是經(jīng)?？赡艹霈F(xiàn)的。確保每一臺機(jī)器都能收到每一條消息，唯一的辦法是要求所有機(jī)器收到消息時(shí)發(fā)回一個(gè)確認(rèn)消息。許多分布式系統(tǒng)以容錯(cuò)為

3、目標(biāo)，對這些系統(tǒng)來說，在出現(xiàn)機(jī)器故障時(shí)仍能保持原子性是很重要的。 有一種簡單的算法證明原子廣播通信至少是可能的。發(fā)送者以發(fā)送一條消息給所有組成員開始。設(shè)置一時(shí)鐘并在必要的時(shí)候重發(fā)消息。當(dāng)一個(gè)進(jìn)程接收到一條消息時(shí)，如果它還沒有看到這一特殊的消息，它就將該消息轉(zhuǎn)發(fā)給組內(nèi)其他成員。如果進(jìn)程已經(jīng)看到了這個(gè)特殊消息，就不必做這一步了，并且將該消息丟棄。這樣，不管有多少個(gè)機(jī)器崩潰或有多少個(gè)信包被丟失，最終所有幸存的進(jìn)程都將收到該消息。以后我們將討論實(shí)現(xiàn)原子性的更有效的算法。消息的順序消息的順序 要使組通信易于理解和使用:首先是原子廣播通信，確保了一條消息要么被所有的組內(nèi)成員收到，要么沒有一個(gè)成員能收到。第

4、二涉及到消息的發(fā)送順序。 進(jìn)程0、1、3、4屬于同一個(gè)進(jìn)程組。進(jìn)程0與4同時(shí)想給該組發(fā)送一條消息。 如（B）圖，進(jìn)程4與0的兩條消息以不同的順序到達(dá)了進(jìn)程1和3。如果進(jìn)程0和4都想去改變數(shù)據(jù)庫中的同一記錄的值，那么進(jìn)程1和進(jìn)程3執(zhí)行的最終結(jié)果是不相同的。系統(tǒng)必須很好地定義消息傳遞順序的語義。 最好的保證就是立即發(fā)送所有消息并讓它們保持發(fā)送的順序。如果進(jìn)程0發(fā)送A消息，稍后進(jìn)程4發(fā)送B消息，系統(tǒng)應(yīng)先將消息A發(fā)送給組內(nèi)各成員，然后冉將消息B發(fā)送給組內(nèi)各成員，這樣所有接收者都可以同樣的順序收到消息。這種將消息精確地按發(fā)送順序傳遞到目的地的方法稱為全局時(shí)間順序。一致時(shí)間順序是指若有兩條消息A和B，以很

5、小的時(shí)間間隔發(fā)送，系統(tǒng)保證組內(nèi)成員按同樣的順序收到了各條消息，但這個(gè)順序可能并不是發(fā)送消息的順序。 組的重疊組的重疊 一個(gè)進(jìn)程能夠同時(shí)成為多個(gè)組的成員。然而，這導(dǎo)致了新的不合理性。下圖中有組1和組2兩個(gè)組。進(jìn)程A、B、C是組1的成員，進(jìn)程B、C、D是組2的成員。 現(xiàn)A與D同時(shí)向它們所在的進(jìn)程組發(fā)送消息，組內(nèi)采用全局時(shí)間順序，A與D采用單點(diǎn)傳送的方法。B先收到下A的消息后收到D的消息，而C則相反。盡管在組內(nèi)都采用全局時(shí)間順序，但在組間還需要協(xié)調(diào)。 一些系統(tǒng)支持重疊組中的精確定義的時(shí)間順序，有些系統(tǒng)不支持。在不同的組間實(shí)現(xiàn)一致的時(shí)間順序是很困難的，有時(shí)不值得去做 ?？蓽y量性可測量性 如果進(jìn)程組內(nèi)只

6、有幾個(gè)成員，將工作良好。但如果組內(nèi)有數(shù)十個(gè)、數(shù)百個(gè)以至成干上萬個(gè)成員，或進(jìn)程組時(shí)會怎樣?或者，整個(gè)系統(tǒng)不限于一個(gè)局域網(wǎng)，而是有網(wǎng)關(guān)連接的際網(wǎng)，那么這些算法能實(shí)現(xiàn)并有效嗎? 網(wǎng)關(guān)的出現(xiàn)會影響我們實(shí)現(xiàn)中的許多特性，首先，多點(diǎn)廣播更復(fù)雜，如圖所示網(wǎng)絡(luò)，它由四個(gè)LAN與四個(gè)網(wǎng)關(guān)構(gòu)成。 在LAN2有一機(jī)器發(fā)出了一個(gè)多點(diǎn)廣播的消息，當(dāng)多點(diǎn)廣播的信包到達(dá)網(wǎng)關(guān)G1和G3時(shí)，若網(wǎng)關(guān)丟棄這個(gè)信包，則其他三個(gè)子網(wǎng)就無法看到該消息。若G1與G3將消息轉(zhuǎn)發(fā)，那么消息到達(dá)了LANl與LAN4，然后分別通過G2與G4都到達(dá)LAN3，這樣LAN3會收到兩次這樣的信包。由于四個(gè)子網(wǎng)構(gòu)成一回路，且又采用了多點(diǎn)廣播，經(jīng)過G4的消息

7、發(fā)往了G2到達(dá)LANl，經(jīng)過了G2的消息發(fā)往了G4到達(dá)LAN4，最終部會回到LAN2。這需要更復(fù)雜的算法通過跟蹤信包在網(wǎng)上的傳送路徑來避免信包被成倍地多點(diǎn)廣播。 另一個(gè)問題是一個(gè)內(nèi)部網(wǎng)上的組通信利用LAN上某一瞬間只能傳送一個(gè)信包的事實(shí)。實(shí)際上，信包在網(wǎng)上按絕對全局時(shí)間順序發(fā)送是很重要的。但是在帶有網(wǎng)關(guān)的多個(gè)子網(wǎng)構(gòu)成的網(wǎng)上，同時(shí)刻傳送兩個(gè)信包，就破壞了絕對企全局時(shí)間順序要求的某一時(shí)刻只有一個(gè)信包在網(wǎng)上傳遞的性質(zhì)。 在在ISISISIS中的組通信中的組通信ISIS是組合軟件調(diào)用系統(tǒng)，它并不是完全意義上的操作是組合軟件調(diào)用系統(tǒng)，它并不是完全意義上的操作系統(tǒng)，而是運(yùn)行在系統(tǒng)，而是運(yùn)行在UNIX或其他

8、操作系統(tǒng)上的一組程序?；蚱渌僮飨到y(tǒng)上的一組程序。 在ISIS中的關(guān)鍵思想是同步，它的主要通信原語是不同形式的原子廣播。同步系統(tǒng)是指一個(gè)每個(gè)事件都嚴(yán)格按序發(fā)生，并且每個(gè)事件的完成不需要時(shí)間。如圖(a) 松散同步系統(tǒng)中圖2-34(b)每個(gè)事件占用有限的一段時(shí)間，但所有的事件會以同樣的順序在所有成員那里出現(xiàn)，與一致時(shí)間順序是相同的。還可以采用一些更松散的語義，以提高性能。圖2-34(c)中給出了一個(gè)虛擬同步系統(tǒng)。在這個(gè)系統(tǒng)中放寬了對順序的限制但是在仔細(xì)選擇的環(huán)境下，還是可以同步的。 在分布式系統(tǒng)中,如果第一個(gè)事件可能會影響第二個(gè)事件的性質(zhì)和行為則這兩個(gè)事件是因果關(guān)系。如果兩個(gè)事件間存在影響,那么就

9、讓它存在。無關(guān)的兩個(gè)互不影響的事件稱為并發(fā)。我們所說的虛擬同步就是,若兩條消息是因果相關(guān)的,那么所有接收進(jìn)程必須以同樣的順序接收它們,若兩條消息是并發(fā)的,那么就不必以同樣的順序接收。系統(tǒng)可以隨意地將這些消息以不同的順序傳遞給不同的進(jìn)程。 ISISISIS中的通信原語中的通信原語 ISIS中定義了三種通信原語ABCAST,CBCAST,GBCAST。ABCAST提供松散同步通信,用于向組成員傳送數(shù)據(jù)。CBCAST提供虛擬同步通信,也用于向組成員傳送數(shù)據(jù)。GBCAST與ABCAST類似,用于管理組內(nèi)成員而不傳送普通數(shù)據(jù)。 通常ABCAST使用兩階段提交協(xié)議。其工作情況如下:發(fā)送者A分配一時(shí)間戳(僅

10、是一個(gè)序號)，將它放在一消息中，發(fā)送給組內(nèi)各成員。各成員將自己的時(shí)間戳返回給A，該時(shí)間戳應(yīng)大于該成員以前所收發(fā)的任何時(shí)間戳。當(dāng)A收到所有時(shí)間戳后，A選擇最大的一個(gè)，并將提交消息發(fā)給各成員。提交消息按時(shí)間戳大小提交給各應(yīng)用程序。這協(xié)議保證了所有消息將按同樣的順序投遞給各過程。 ABCAST復(fù)雜且昂貴，設(shè)計(jì)者提出了CBCAST，它僅僅保證了所有因果相關(guān)的消息能按序發(fā)送到目的地。其工作情況:如果一個(gè)組有n個(gè)成員，每個(gè)成員進(jìn)程保存一個(gè)n維向量，向量的每一維對應(yīng)一個(gè)成員。第i維的值就是從進(jìn)程i發(fā)過來的最后一次消息的序號。這向量由運(yùn)行系統(tǒng)來控制（初始化為0 ）。進(jìn)程有消息要發(fā)送時(shí)，它在自己保存的向量中屬于

11、自己的位置上加 l，然后將該向量放在消息中。如圖2-35的頂部。 決定對到來的消息是接收還是推遲的算法描述如下:Vi是發(fā)送方向量中的第i位。Li是接受方向量的第i位。假設(shè)消息由j 發(fā)送。接收的第一個(gè)條件是Vj= Lj十1，表明這是j進(jìn)程發(fā)送來的下一條消息Vj ，以前的消息均已收到?jīng)]何遺漏。第二個(gè)條件:對所有的ij 有Vi= Li .（ j 一定， i 為變量）表明接受方己有所有發(fā)送方收到的消息。如果到來的消息通過這兩個(gè)條件，那么運(yùn)行系統(tǒng)可將消息送給本機(jī)上的用戶進(jìn)程。否則該消息必須等待。 圖2-36，進(jìn)程0向其他五個(gè)成員發(fā)送消息，消息包含向量(4，6，8，2，1，5)。進(jìn)程l的除0以外的其他位與

12、0進(jìn)程的相同，表明進(jìn)程0收到的那些消息進(jìn)程l也收到了。而進(jìn)程l剛發(fā)送一條消息，進(jìn)程0未收到，但這并不影響進(jìn)程l接收消息。此外，進(jìn)程1上的對應(yīng)0的那位剛好比進(jìn)程0的相應(yīng)位小1，這樣進(jìn)程l接收進(jìn)程0來的消息4。進(jìn)程2的向量表明尚未收到進(jìn)程1發(fā)來的消息6，進(jìn)程2還不能接收進(jìn)程0發(fā)來的消息。進(jìn)程3看上去也收到了發(fā)送者收到的其他消息，進(jìn)程3甚至收到進(jìn)程1的消息7，只是還沒有收到來自進(jìn)程0的消息，因而，進(jìn)程3可以接收進(jìn)程0來的消息4。由于進(jìn)程4向量對應(yīng)的進(jìn)程0的位置上的值是2，這就說明進(jìn)程4丟失了進(jìn)程0發(fā)來的消息3，因而進(jìn)程4就不能接收進(jìn)程0發(fā)來的消息4。在進(jìn)程5中，該向量在0進(jìn)程的位置上剛好比進(jìn)程0少1，而且它比進(jìn)程0先收到了來自進(jìn)程1的消息，因而，它可以接收進(jìn)程0來的消息4。小結(jié)小結(jié) 分布式系統(tǒng)中提出和實(shí)現(xiàn)了通信的不同方法。對于相對傳送速度較慢的廣域分布式系統(tǒng)來說，使用TCP/IP面向連接的分層協(xié)議，克服物理線路傳輸數(shù)據(jù)的不可靠性。對局域的分布式系統(tǒng)，很少使用分層協(xié)議，而是采用較簡單的模式。這種模式能取得更高的性能。在這種消息傳遞系統(tǒng)中，關(guān)于通信原語，我們討論了阻塞與非陽塞、有緩沖區(qū)與無緩沖區(qū)、可靠與不可靠等等。在RPC進(jìn)程通信模式中，機(jī)器上運(yùn)行的客戶進(jìn)程調(diào)用在另臺機(jī)器上的過程。運(yùn)行系統(tǒng)嵌入在存根的過程庫中，用來收集