《高級操作系統(tǒng)》配套教學(xué)課件

高級操作系統(tǒng)1課程主要內(nèi)容介紹2分布式計(jì)算機(jī)系統(tǒng)分布式通信機(jī)制分布式協(xié)同處理分布式資源管理分布式進(jìn)程與處理機(jī)任務(wù)分配與負(fù)載平衡分布式文件系統(tǒng)命名服務(wù)分布式事務(wù)處理故障恢復(fù)與容錯(cuò)分布式共享內(nèi)存3

教學(xué)要求

要求學(xué)生掌握上述主要內(nèi)容中的基本概念，了解相關(guān)的一些典型算法，并就分布式操作系統(tǒng)中的設(shè)計(jì)模型、實(shí)現(xiàn)方法及有待進(jìn)一步解決和探索的問題加以關(guān)注，寫出相關(guān)論文。1.1分布式系統(tǒng)概述1.2分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)1.3分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)1.4分布式系統(tǒng)的拓?fù)浣Y(jié)構(gòu)1.5分布式資源管理1.6分布式操作系統(tǒng)4第一章分布式計(jì)算機(jī)系統(tǒng)1.1分布式系統(tǒng)概述

計(jì)算機(jī)技術(shù)發(fā)展迅猛。從1945年現(xiàn)代計(jì)算機(jī)時(shí)代開始直到1985年，計(jì)算機(jī)一直是龐大昂貴的設(shè)備。即便是小型計(jì)算機(jī)也要花數(shù)萬美元。這使得大多數(shù)機(jī)構(gòu)通常只有為數(shù)不多的幾臺機(jī)器，并且由于它們之間缺少互連的手段，這些機(jī)器都是各自獨(dú)立地工作。

51.1分布式系統(tǒng)概述

然而，從80年代開始，兩項(xiàng)技術(shù)進(jìn)步改變了這種局面。第一項(xiàng)是功能日益強(qiáng)大的微型計(jì)算機(jī)的發(fā)展。第二項(xiàng)進(jìn)步是高速局域網(wǎng)的出現(xiàn)。局域間能將數(shù)十臺機(jī)器、甚至數(shù)百臺機(jī)器連接在一起，數(shù)據(jù)在機(jī)器之間傳輸只需要幾u(yù)s的時(shí)間。大量的數(shù)據(jù)能以超過10Mbps的速率傳輸。61.1分布式系統(tǒng)概述

分布式計(jì)算機(jī)系統(tǒng)是由多個(gè)分散的計(jì)算機(jī)經(jīng)互連網(wǎng)絡(luò)連接而成的計(jì)算機(jī)系統(tǒng)。其中各個(gè)資源單位（物理的或邏輯的）既相互協(xié)同又高度自治，能在全系統(tǒng)范圍內(nèi)實(shí)現(xiàn)資源管理，動態(tài)地進(jìn)行任務(wù)分配或功能分配，并且能夠并行地運(yùn)行分布式程序。71.1分布式系統(tǒng)概述8分布式計(jì)算機(jī)系統(tǒng)示意圖1.1分布式系統(tǒng)概述

分布式操作系統(tǒng)（DistributedOperatingSystem，縮寫為DOS）是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。它在這種多機(jī)環(huán)境下，負(fù)責(zé)控制和管理以協(xié)同方式工作的多種系統(tǒng)（的物理和邏輯）資源，進(jìn)程的同步和執(zhí)行，處理機(jī)間的通信、調(diào)度等控制事務(wù)，自動實(shí)行全系統(tǒng)范圍內(nèi)的任務(wù)分配和負(fù)載平衡并具有高度并行性的一種高級軟件系統(tǒng)。91.2分布式系統(tǒng)的優(yōu)缺點(diǎn)(1)分布式系統(tǒng)相對于集中式系統(tǒng)的優(yōu)點(diǎn)優(yōu)點(diǎn)說明經(jīng)濟(jì)性微處理器能提供比大型機(jī)更好的性能價(jià)格比速度分布系統(tǒng)能提供比大型機(jī)更強(qiáng)的計(jì)算能力固有的分布性在一些應(yīng)用包含物理上分散的機(jī)器可靠性當(dāng)某臺機(jī)器崩潰時(shí)、整個(gè)系統(tǒng)仍能正常工作可擴(kuò)展性計(jì)算能力逐步增加10表1分布式系統(tǒng)相對于集中式系統(tǒng)的優(yōu)點(diǎn)1.2分布式系統(tǒng)的優(yōu)缺點(diǎn)(2)分布式系統(tǒng)相對于獨(dú)立PC機(jī)的優(yōu)點(diǎn)優(yōu)點(diǎn)說明數(shù)據(jù)共享允許許多用戶共享同一個(gè)數(shù)據(jù)庫外設(shè)共享允許用戶共享昂貴的外設(shè)，如彩色打印機(jī)通信使得人與人間的通信更加方便，例如通過電子郵件靈活性將工作負(fù)載更有效地分派到合適的機(jī)器上11表2分布式系統(tǒng)相對于PC機(jī)的優(yōu)點(diǎn)的優(yōu)點(diǎn)1.2分布式系統(tǒng)的優(yōu)缺點(diǎn)(3)分布式系統(tǒng)的缺點(diǎn)缺點(diǎn)說明軟件目前很少有分布式系統(tǒng)的軟件網(wǎng)絡(luò)網(wǎng)絡(luò)可能飽和，或讓系統(tǒng)遇到其他麻煩安全方便的數(shù)據(jù)共享意味著機(jī)密數(shù)據(jù)容易被竊取12表3分布式系統(tǒng)的缺點(diǎn)1.3分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)

分布式計(jì)算機(jī)系統(tǒng)具有如下明顯的主要特點(diǎn)：⑴結(jié)構(gòu)模塊性：分布式計(jì)算機(jī)系統(tǒng)的資源單位形成相對獨(dú)立的模塊，它們經(jīng)互連網(wǎng)絡(luò)連接成一個(gè)單一系統(tǒng)。模塊在一定范圍內(nèi)的增減或替換不影響系統(tǒng)的整體性。⑵資源分散性（distributed）：系統(tǒng)資源分布于物理上分散的若干場點(diǎn)中。在對用戶透明基礎(chǔ)上實(shí)現(xiàn)資源共享，使單個(gè)用戶的可用資源成倍地增長。

131.3分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)14⑶協(xié)同自治性（autonomous）：系統(tǒng)資源的操作是高度自治的，既不存在全系統(tǒng)的主/從控制關(guān)系，又能利用處理局部化的原則以減少各場點(diǎn)間的通信量。⑷工作并行性（parallesm）：分布式計(jì)算機(jī)系統(tǒng)中分散的資源單位可以相互協(xié)作，一起解決同一個(gè)問題。在分布式操作系統(tǒng)控制下，實(shí)現(xiàn)按任務(wù)資源重復(fù)或按功能時(shí)間重疊等不同形式的并行性。15

⑸系統(tǒng)透明性（transparency）：系統(tǒng)對于用戶是透明的。用戶可以像單機(jī)系統(tǒng)一樣使用分布式計(jì)算機(jī)系統(tǒng)。⑹整體強(qiáng)健性（robustness）：系統(tǒng)中的資源的冗余和自治控制方式使系統(tǒng)具有動態(tài)重構(gòu)能力，即使系統(tǒng)受到局部性破壞也能繼續(xù)工作。所以具有可靠性和容錯(cuò)性。1.3分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)1.3分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)⑺靈活的可擴(kuò)充性：以模塊作為系統(tǒng)擴(kuò)充或資源更新的增加單位，不必像集中式系統(tǒng)那樣替換整個(gè)系統(tǒng)或更改系統(tǒng)中的很大部分。系統(tǒng)的配置容易改變，以適應(yīng)不同應(yīng)用對象的各種需求。⑻良好的實(shí)時(shí)性：計(jì)算機(jī)資源更加靠近用戶，特別是使分散的用戶能得到計(jì)算機(jī)的快速響應(yīng)和直接服務(wù)，從而把大型機(jī)的強(qiáng)功能、高速度與微型機(jī)的使用方便性、靈活性結(jié)合了起來。161.3分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)分布式計(jì)算機(jī)系統(tǒng)是近年來計(jì)算機(jī)科學(xué)技術(shù)領(lǐng)域中倍受青睞、發(fā)展迅速的一個(gè)方向。一些專家亦斷言：將來任何一個(gè)有效的計(jì)算機(jī)系統(tǒng)，都將是一個(gè)分布式系統(tǒng)。17181.4分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)

分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)可用處理機(jī)之間的耦合度為主要標(biāo)志來加以描述。耦合度是系統(tǒng)模塊之間互連的緊密程度，它是數(shù)據(jù)傳輸率、響應(yīng)時(shí)間、并行處理能力等性能指標(biāo)的綜合反映，主要取決于所選用的互連拓?fù)浣Y(jié)構(gòu)和通信鏈路的類型。1.4分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)運(yùn)程計(jì)算機(jī)網(wǎng)絡(luò)采用串行數(shù)據(jù)傳輸，且受復(fù)雜的通信協(xié)議制約，故其耦合度最低，屬于松散耦合系統(tǒng)（looselycouple）。具有共享內(nèi)存的多處理機(jī)系統(tǒng)有著很高的并行處理速度，固其耦合度最高，屬于緊密耦合系統(tǒng)（looselycouple）。191.4分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)按地理環(huán)境衡量耦合度，分布式計(jì)算機(jī)系統(tǒng)可以分為機(jī)體內(nèi)系統(tǒng)、建筑物內(nèi)系統(tǒng)、建筑物間系統(tǒng)和不同地理范圍的區(qū)域系統(tǒng)等，它們的耦合度依次由高到低。2021按應(yīng)用領(lǐng)域的性質(zhì)決定耦合度，可以分成三類。一種是面向計(jì)算任務(wù)的分布并行計(jì)算機(jī)系統(tǒng)和分布式多用戶計(jì)算機(jī)系統(tǒng)，它們要求盡可能高的耦合度，以便發(fā)展成為能分擔(dān)大型計(jì)算機(jī)和分時(shí)計(jì)算機(jī)系統(tǒng)所完成的工作。第二種是面向管理信息的分布式數(shù)據(jù)處理系統(tǒng)，耦合度可以適當(dāng)降低。第三種是面向過程控制的分布式計(jì)算機(jī)控制系統(tǒng)。耦合度要求適中，當(dāng)然對于某些實(shí)時(shí)應(yīng)用，其耦合度的要求可能很高。分布式計(jì)算機(jī)系統(tǒng)可看作是并行處理系統(tǒng)的一種常見形式和特例。1.4分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)221.5分布式系統(tǒng)的拓?fù)浣Y(jié)構(gòu)

分布式系統(tǒng)中的場點(diǎn)可用不同的方式將它們從物理上連結(jié)起來，每種方式都有優(yōu)缺點(diǎn)。下面簡單討論幾種常用的連結(jié)方式并按以下標(biāo)準(zhǔn)來比較它們的性能：⑴基本開銷：連結(jié)系統(tǒng)中的各個(gè)場點(diǎn)要多少花費(fèi)？⑵通信開銷：從場點(diǎn)A發(fā)送消息到場點(diǎn)B需要多少時(shí)間？⑶可靠性：若系統(tǒng)中的場點(diǎn)或通信鏈路故障，余下的場點(diǎn)是否仍能彼此通信？一個(gè)系統(tǒng)稱之為分割的（partition），如果它已被分劃成兩個(gè)或多個(gè)子系統(tǒng)，且不同子系統(tǒng)中的場點(diǎn)已不再能彼此通信。231.全互連結(jié)構(gòu)

在一個(gè)全互連結(jié)構(gòu)中，每個(gè)場點(diǎn)都直接與系統(tǒng)中所有其它的場點(diǎn)相連（圖1.2），這種構(gòu)形的基本開銷很高，場點(diǎn)間的消息轉(zhuǎn)移非常快，此外，這種結(jié)構(gòu)是很可靠的，因?yàn)橹挥性谙喈?dāng)多的通信鍵路故障的情況下，才可能分割該系統(tǒng)。圖1.2全互連拓?fù)浣Y(jié)構(gòu)242.部分互連結(jié)構(gòu)

在一個(gè)部分互連結(jié)構(gòu)中，有些場點(diǎn)間存在直接通信鏈路，但有些則沒有，如圖1.3所示。因此這種構(gòu)形的基本開銷比全互連結(jié)構(gòu)要低，但場點(diǎn)間的消息轉(zhuǎn)移可能經(jīng)由若干中間的場點(diǎn)，以致延緩了通信速度。例如，在圖1.3中，從場點(diǎn)⑤④.發(fā)送一消息到場點(diǎn)③必須經(jīng)由場點(diǎn)①和②。圖1.3部分互連拓?fù)浣Y(jié)構(gòu)25

此外，部分互連系統(tǒng)也不如全互連系統(tǒng)可靠，因?yàn)槠渲械囊粋€(gè)通信鍵路故障就可能分割該系統(tǒng)。例如，在圖1.3中，若從場點(diǎn)①到場點(diǎn)②的通信鏈路故障，則該系統(tǒng)便分割成兩個(gè)子系統(tǒng)，一個(gè)包括①，④，⑤；一個(gè)包括②和③，而且這兩個(gè)子系統(tǒng)中的場點(diǎn)彼此不再能通信。為了減少這種情況發(fā)生，通常讓每個(gè)場點(diǎn)要少與另外兩個(gè)場點(diǎn)連給。例如，如果我們在圖1.3中增加一條從場點(diǎn)③到場點(diǎn)⑤的通信鍵路，那么任何單條通信鏈路故障都不可能導(dǎo)致對該系統(tǒng)的分割。263.層次結(jié)構(gòu)

層次結(jié)構(gòu)中的各場點(diǎn)組織成樹形結(jié)構(gòu)。如圖1.4所示，其中，這種構(gòu)形的基本開銷一般小于部分互連結(jié)構(gòu)。在這種環(huán)境中，父子之間可直接通信，孩子之間只能經(jīng)由它們的共同父親進(jìn)行通信，若父場點(diǎn)故障，那么，它的孩子們彼此就不能相互通信，也不能與其它進(jìn)程通信。一般而言，除葉結(jié)點(diǎn)外，任何中間結(jié)點(diǎn)故障都可能將這種結(jié)構(gòu)分割成若干不相交的子樹。圖1.4層次結(jié)構(gòu)27

4.星形結(jié)構(gòu)

在星形結(jié)構(gòu)中，系統(tǒng)中的場點(diǎn)之一與系統(tǒng)中所有其余場點(diǎn)相連，其它的場點(diǎn)之間彼此不直接相連，見圖1.5。這種構(gòu)形的基本開銷是場點(diǎn)個(gè)數(shù)的線性函數(shù)，其通信速度看起來也不會很慢，但這種通信速度卻是難以預(yù)測的，因?yàn)橹醒雸鳇c(diǎn)可能變成瓶頸，雖然轉(zhuǎn)移消息所需轉(zhuǎn)接的次數(shù)不多，但轉(zhuǎn)移消息所花的時(shí)間可能不少。在一些星形結(jié)構(gòu)系統(tǒng)中，中央場點(diǎn)完全擔(dān)負(fù)著消息轉(zhuǎn)接的任務(wù)。如果中央場點(diǎn)故障，那么該系統(tǒng)就完全地被分割了。圖1.5星形結(jié)構(gòu)285.環(huán)形結(jié)構(gòu)

在環(huán)形結(jié)構(gòu)中，每個(gè)場點(diǎn)物理上恰好與另外兩個(gè)場點(diǎn)相連，見圖1.6。這樣的環(huán)形結(jié)構(gòu)可以是單向的，也可以是雙向的。這種結(jié)構(gòu)的基本開銷不會很高，但通信代價(jià)可能較高，因?yàn)閺囊粋€(gè)場點(diǎn)向另一場點(diǎn)轉(zhuǎn)移消息需沿環(huán)按預(yù)定方向轉(zhuǎn)移直至到達(dá)目的地。在單向環(huán)結(jié)構(gòu)中，這最多可能需要n-1次轉(zhuǎn)接，在雙向環(huán)結(jié)構(gòu)中，則最多可能需要n/2次轉(zhuǎn)接，其中n是網(wǎng)絡(luò)中場點(diǎn)的個(gè)數(shù)。29圖1.6環(huán)形結(jié)構(gòu)

在雙向環(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)，但這顯然會增加基本開銷，如圖1.6(b)所示。306.多存取總線結(jié)構(gòu)

在多存取總線結(jié)構(gòu)（簡稱總線結(jié)構(gòu)）中，它可以組織成直線狀，見圖1.7(a)，也可以組織成環(huán)狀，如圖1.7(b)所示，其中的場點(diǎn)可以經(jīng)由這條總線彼此直接進(jìn)行通信。這類結(jié)構(gòu)的基本開銷是場點(diǎn)個(gè)數(shù)的線性函數(shù)，通信代價(jià)也很低，除非這條總線變成了瓶頸。這類結(jié)構(gòu)類似于帶有一個(gè)中央場點(diǎn)的星形結(jié)構(gòu)，其中某個(gè)場點(diǎn)故障不會影響其它場點(diǎn)間的通信，但是，若這條總線故障，那么該結(jié)構(gòu)就完全地被分割了。31圖1.7多存取總線結(jié)構(gòu)

327.環(huán)-星形結(jié)構(gòu)

環(huán)-星形結(jié)構(gòu)由環(huán)、星型結(jié)構(gòu)疊加而成，其優(yōu)缺點(diǎn)介于星形和環(huán)形結(jié)構(gòu)之間，見圖1.8。圖1.8環(huán)-星形結(jié)構(gòu)338.有規(guī)則結(jié)構(gòu)

有規(guī)則結(jié)構(gòu)（見圖1.9）中的每個(gè)場點(diǎn)都與它相鄰的上、下、左、右場點(diǎn)相連，因而具有高性能、高速度、和高可靠性。不過，這種結(jié)構(gòu)比較復(fù)雜，且一般要求各場點(diǎn)是完全一致的，構(gòu)造這種系統(tǒng)的費(fèi)用也較高。圖1.9有規(guī)則結(jié)構(gòu)349.不規(guī)則結(jié)構(gòu)

不規(guī)則結(jié)構(gòu)中的各場點(diǎn)間的連接關(guān)系無一定規(guī)則可依，其優(yōu)點(diǎn)是：可隨意增加不同類型的結(jié)點(diǎn)，各結(jié)點(diǎn)互連起來也較方便，還可提供任意冗余和重組能力；其缺點(diǎn)是運(yùn)行時(shí)需要較復(fù)雜的路徑選擇算法（見圖1.10）。圖1.10不規(guī)則結(jié)構(gòu)3510.立方體互連結(jié)構(gòu)

立方體互連結(jié)構(gòu)又稱n維立方體分布式網(wǎng)絡(luò)結(jié)構(gòu)。這種結(jié)構(gòu)把2n＝N個(gè)計(jì)算機(jī)互連起來，各計(jì)算機(jī)分別位于該立方體的角頂。立方體的每條邊把兩個(gè)場點(diǎn)連接起來，而每個(gè)場點(diǎn)則有n個(gè)全雙向通路把它和n個(gè)其它計(jì)算機(jī)相連。例如，n=3，n=4時(shí)立方體互連結(jié)構(gòu)如圖1.11所示，其中，n為立方體的維數(shù)。此外，還有交叉開關(guān)網(wǎng)、樹形網(wǎng)、網(wǎng)狀網(wǎng)、立方體網(wǎng)和超立方體等。36圖1.11立方體互連結(jié)構(gòu)1.6分布式系統(tǒng)的資源管理資源管理有四種方式：（1）全集中管理方式（2）分擔(dān)管理方式（3）輪流管理方式（4）全分散管理方式采取哪種資源管理方式，必須根據(jù)總體要求和資源性質(zhì)決定。37381.7分布式操作系統(tǒng)1.多機(jī)操作系統(tǒng)的基本結(jié)構(gòu)

多機(jī)操作系統(tǒng)有以下三種基本結(jié)構(gòu)：主從式獨(dú)立式分布式⑴主從式在多機(jī)系統(tǒng)上最早設(shè)計(jì)的多機(jī)操作系統(tǒng)都采用主從式，這是比較容易實(shí)現(xiàn)的一種形式。在具體設(shè)計(jì)和實(shí)現(xiàn)時(shí)，可在具備多道程序設(shè)計(jì)的操作系統(tǒng)基礎(chǔ)上加以擴(kuò)充而成。但是，它在管理和利用全系統(tǒng)資源方面的效率較低。其主要特點(diǎn)為：39

①管理程序始終由同一個(gè)處理機(jī)（稱為主機(jī)master）執(zhí)行，從而減化了控制信息的管理問題。若從機(jī)需要使用管理程序提供的服務(wù)，則應(yīng)先向主機(jī)提出申請并等待現(xiàn)行程序中斷后，由管理程序根據(jù)一定策略來決定是否滿足這一申請并提供相應(yīng)的控制。管理程序及其所用子程序不得重入，因?yàn)槭褂盟鼈兊闹挥幸慌_處理機(jī)。②若主機(jī)不能以足夠快的速度執(zhí)行調(diào)度程序和收、發(fā)信息，以使從機(jī)保持充分地忙碌狀態(tài)，那么從機(jī)的空閑時(shí)間就會增多，從而影響了整個(gè)系統(tǒng)的效率。③這種操作系統(tǒng)主要用于工作負(fù)載能精確給定的一些應(yīng)用場合，或由于從機(jī)能力小于主機(jī)能力的非對稱系統(tǒng)。④當(dāng)主機(jī)故障時(shí)，影響整個(gè)系統(tǒng)，此時(shí)需外來干預(yù)；整個(gè)系統(tǒng)的靈活性也較差。40

⑵獨(dú)立式獨(dú)立式操作系統(tǒng)的主要特點(diǎn)是：①系統(tǒng)中的每臺處理機(jī)的管理程序僅為自身的需要服務(wù)。某些程序所使用的子程序必須是再入式或復(fù)制品，以便為每臺處理機(jī)提供各自單獨(dú)的副本。②各臺處理機(jī)借助公用信息相互聯(lián)系。整個(gè)系統(tǒng)除了公用信息外，處理機(jī)的管理程序還可管理和使用各自的專用信息，因此，其信息的存取控制比主從式復(fù)雜。③系統(tǒng)中的每臺處理機(jī)各自都有一套顯示設(shè)備、I/O設(shè)備、文件、目錄等。41

⑶分布式①可由多臺處理機(jī)同時(shí)執(zhí)行管理、控制和服務(wù)程序，但“主處理機(jī)”是浮動的，可由一臺切換為另－臺。由于多臺處理機(jī)可同時(shí)執(zhí)行同一管理、控制和服務(wù)程序，因此，這些程序必須是再入式的。②在這種操作系統(tǒng)的管理和控制下，整個(gè)系統(tǒng)中的所有資源單元均可獲較好的負(fù)載平衡。③當(dāng)服務(wù)請求發(fā)生沖突時(shí)，可根據(jù)固定的優(yōu)先級或動態(tài)控制策略確定的優(yōu)先級予以解決。④當(dāng)系統(tǒng)中出現(xiàn)局部故障時(shí)，可通過自動重構(gòu)，適度降級（gracefuldegradation）使用，或通過錯(cuò)誤恢復(fù)手段使系統(tǒng)繼續(xù)運(yùn)行，因而系統(tǒng)有較好的可用性和可靠性。422.設(shè)計(jì)分布式操作系統(tǒng)時(shí)應(yīng)考慮的問題

(1)靈活性

(2)可靠性

(3)性能

(4)可申縮性43

⑵分布式操作系統(tǒng)的結(jié)構(gòu)本身也應(yīng)是分布式的，系統(tǒng)中的各場點(diǎn)都可包含該操作系統(tǒng)或其中的一部分。一般把分布式操作系統(tǒng)劃分成若干不相交的并行模塊，并將它們分別指派給系統(tǒng)中的各場點(diǎn)，且每個(gè)場點(diǎn)都有一個(gè)局部操作系統(tǒng)的內(nèi)核模塊的副本。在系統(tǒng)運(yùn)行時(shí)，各場點(diǎn)間的邏輯關(guān)系是完全平等的。分布式操作系統(tǒng)的模塊可以全部并行地在各場點(diǎn)上運(yùn)行，而控制流和數(shù)據(jù)流的移動則在各場點(diǎn)上的局部操作系統(tǒng)的內(nèi)核模塊的合作協(xié)調(diào)下進(jìn)行。⑶分布式操作系統(tǒng)可劃分為高層和局部，劃分的原則是：①屬于本機(jī)獨(dú)立運(yùn)行的基本管理功能劃歸為本場點(diǎn)（本機(jī)）局部操作系統(tǒng)。②本場點(diǎn)（本機(jī)）與其它場點(diǎn)（它機(jī)）之間的通信、同步、消息轉(zhuǎn)移等管理功能也劃歸為本場點(diǎn)局部操作系統(tǒng)。44

③各場點(diǎn)間協(xié)調(diào)合作完成的功能，如任務(wù)分配、負(fù)載平衡、死鎖處理、錯(cuò)誤處理與系統(tǒng)重構(gòu)等及其它公共事務(wù)劃歸為高層操作系統(tǒng)。這種劃分使各場點(diǎn)在運(yùn)行中既有自治性，又能使系統(tǒng)中各場點(diǎn)協(xié)調(diào)一致地進(jìn)行合作。④分布式操作系統(tǒng)的基本調(diào)度單位已不再是單機(jī)操作系統(tǒng)的進(jìn)程，而是一種任務(wù)隊(duì)列，這種隊(duì)列是由位于多個(gè)場點(diǎn)上的并發(fā)進(jìn)程所組成的任何隊(duì)列。同一任務(wù)隊(duì)列中的諸并發(fā)進(jìn)程可分布在不同的場點(diǎn)上并行地執(zhí)行；同一場點(diǎn)上也可執(zhí)行多個(gè)不同的任務(wù)隊(duì)列中的并發(fā)進(jìn)程。⑤在分布式系統(tǒng)中，需要提供一個(gè)支持資源共享的環(huán)境，把任務(wù)分解并分配到相應(yīng)的場點(diǎn)。若整個(gè)系統(tǒng)由不同類型的處理機(jī)組成，由于每個(gè)處理機(jī)的處理能力及硬設(shè)備配置等方面都可能各具特點(diǎn)。因此，操作系統(tǒng)應(yīng)該根據(jù)這些特點(diǎn)給處理機(jī)分配任務(wù)。45若系統(tǒng)由同類型的處理機(jī)組成，則在任何給定的時(shí)刻，任務(wù)都可分配給任何一個(gè)處理機(jī)，并可隨時(shí)進(jìn)行任務(wù)的遷移，以平衡系統(tǒng)的負(fù)載。顯然，這要求分布式操作系統(tǒng)有任務(wù)或進(jìn)程間通信及運(yùn)程任務(wù)控制的能力。⑥分布式操作系統(tǒng)的構(gòu)成與分布式計(jì)算機(jī)系統(tǒng)的耦合方式緊密相關(guān)。在緊密耦合的分布式系統(tǒng)中，各處理機(jī)共享存儲器和時(shí)鐘，通信是經(jīng)由共享存儲器進(jìn)行的，系統(tǒng)資源的耦合程度很高，因而需要專門的各種軟件和硬件機(jī)制來解決沖突和競爭等問題。在松散耦合的分布式系統(tǒng)中，各處理機(jī)無共享存儲器和時(shí)鐘，而都配有自己的本地資源，它們彼此之間經(jīng)由各種通信線路進(jìn)行通信。因此，分布式操作系統(tǒng)必須解決的主要問題是處理機(jī)以及進(jìn)程之間的通信和同步。所以，多機(jī)系統(tǒng)的耦合方式不同，相應(yīng)的分布式操作系統(tǒng)所要解決的主要問題也不同。⑦分布式操作系統(tǒng)必須具有探測任一處理機(jī)停機(jī)或發(fā)生故障的能力，并且要包含適當(dāng)?shù)奶幚泶胧?，如自動重?gòu)，、降級使用和錯(cuò)誤恢復(fù)等。463.構(gòu)造分布式操作系統(tǒng)的途徑

對于如何構(gòu)造分布式操作系統(tǒng)，可歸納為下面幾個(gè)主要觀點(diǎn)：⑴從頭開始因?yàn)榉植际讲僮飨到y(tǒng)不同于現(xiàn)有的單機(jī)、集中式和網(wǎng)絡(luò)操作系統(tǒng)，因此，不少學(xué)者主張完全從頭開始構(gòu)造一個(gè)分布式操作系統(tǒng)，即在裸機(jī)上重頭開始。這種途徑的最吸引人之處是給予設(shè)計(jì)者以完全的自由度。但不足之處在于其中所涉及到的所有系統(tǒng)軟件和應(yīng)用軟件幾乎全都要重新編寫。

⑵修改、擴(kuò)充式對現(xiàn)有的操作系統(tǒng)進(jìn)行修改和擴(kuò)充，使之具有分布處理和通信的功能。這種途徑通過盡量保持與現(xiàn)有操作系統(tǒng)的相容性而使重新編寫新軟件的工作量減到最少。而且存在一個(gè)與開發(fā)期間的新版本進(jìn)行比較的原有工作版本，這就給我們提供了測試和比較新版本性能的基礎(chǔ)。這種途徑的不利之處是開發(fā)期間的某些決策由于要考慮到如何與原有操作系統(tǒng)相容而不得不采取折衷方案。4748

⑶層次式在現(xiàn)有操作系統(tǒng)和用戶之間增加一個(gè)層次以提供分布處理和通信功能。這類系統(tǒng)有點(diǎn)類似網(wǎng)絡(luò)操作系統(tǒng)，它具有前述兩種途徑的優(yōu)點(diǎn)且不必改動現(xiàn)有的操作家統(tǒng),其不足之處在于所有對底層操作系統(tǒng)的引用由于必須經(jīng)由中間層而使系統(tǒng)性能受到了衰減，此外，還有不少局限性。利用這三種途徑構(gòu)造分布式操作系統(tǒng)的示意圖，見圖1.15。49圖1.15構(gòu)造分布式操作系統(tǒng)的三種途徑504.分布式操作系統(tǒng)的結(jié)構(gòu)模型

分布式操作系統(tǒng)的結(jié)構(gòu)是指其整體邏輯結(jié)構(gòu)，主要有以下幾種：⑴分布式操作系統(tǒng)內(nèi)核：各場點(diǎn)上都配有一個(gè)分布式操作系統(tǒng)內(nèi)核，它僅提供存儲管理、輔存管理、進(jìn)程管理、進(jìn)程間的同步與通信等核心管理功能及相應(yīng)的操作原語。例如，Accent和V核就屬于這種結(jié)構(gòu)模型。⑵集成式：集成式（integratedmodel）意指每個(gè)場點(diǎn)上運(yùn)行著一個(gè)比較完整或集成的高度可組合的標(biāo)準(zhǔn)化的操作系統(tǒng)模塊集，該集包含相應(yīng)場點(diǎn)上所需要的幾乎所有的服務(wù)功能，決大多數(shù)工作都是在本場點(diǎn)上完成的。每個(gè)場點(diǎn)也可訪問遠(yuǎn)程資源，即當(dāng)必要時(shí)才發(fā)生場點(diǎn)間的交叉訪問。LOCUS等就是這種模型的例子。51

⑶客戶/服務(wù)器（client/server）模型：在這種模型中，系統(tǒng)中的場點(diǎn)分為客戶和服務(wù)器兩大類。分布式操作系統(tǒng)的所有服務(wù)程序及相應(yīng)的共享信息都分散地駐留在一些特定的場點(diǎn)上，并加以實(shí)現(xiàn)。而客戶場點(diǎn)僅包含足以訪問相應(yīng)服務(wù)器場點(diǎn)上服務(wù)程序及相應(yīng)的共享信息的接口軟件，參見。這種模型常常分為兩種形式：服務(wù)池模型和資源池模型。對于前者，系統(tǒng)中的所有服務(wù)功能都是由服務(wù)池按服務(wù)類提供的，如文件服務(wù)類、命名服務(wù)類、終端服務(wù)類和通信服務(wù)類等。對于后者，系統(tǒng)管理著一個(gè)可重用的資源池，如處理機(jī)、外設(shè)、文件、服務(wù)程序和數(shù)據(jù)等，其中的資源可動態(tài)地分配給申請者，用完后再收回到資源池中供再次使用。52

⑷中央式：系統(tǒng)在硬件結(jié)構(gòu)上有一個(gè)中央場點(diǎn)和若干衛(wèi)星場點(diǎn)。中央場點(diǎn)運(yùn)行一個(gè)中央控制程序，由它處理所有對分布式操作系統(tǒng)的調(diào)用。每個(gè)衛(wèi)星場點(diǎn)上運(yùn)行的進(jìn)程彼此不能直接通信，它們只能借助中央控制程序進(jìn)行交往。⑸分散式：分散式模型意指將分布式操作系統(tǒng)的功能分散到各個(gè)場點(diǎn)，以構(gòu)成單個(gè)場點(diǎn)上的局部操作系統(tǒng)，使得每個(gè)場點(diǎn)上的局部操作系統(tǒng)僅擔(dān)負(fù)整個(gè)系統(tǒng)的部分管理功能。由各場點(diǎn)上的局部操作系統(tǒng)的核模塊和核外部分采用協(xié)商、合作的方式來實(shí)現(xiàn)對全系統(tǒng)的管理That’sall532.1概述2.2消息傳遞2.3遠(yuǎn)程過程調(diào)用54第二章分布式通信機(jī)制552.1概述

本章討論分布式系統(tǒng)中的通信問題。在考慮這一問題時(shí)，應(yīng)注意以下幾個(gè)方面：

發(fā)送策略：如何通過通信網(wǎng)發(fā)送消息？

連接策略：如何去連接彼此希望通信的進(jìn)程？

爭奪處理：由于通信網(wǎng)是共享資源，應(yīng)注意解決在利用它的過程中那些有沖突的要求和沖突現(xiàn)象。

保密：如何保住消息內(nèi)容的秘密？

通信機(jī)制：研究分布式操作系統(tǒng)中的基本通信機(jī)制。562.1.1發(fā)送策略

當(dāng)場點(diǎn)A上的一個(gè)進(jìn)程希望同場點(diǎn)B上的另一個(gè)進(jìn)程進(jìn)行通信時(shí)，如何發(fā)送消息？常用的幾種發(fā)送策略是：

⑴固定發(fā)送:從A到B的信道事先已規(guī)定好并且不得更改，除非硬件的故障影響到它的通信能力。通常選擇物理上長度最短的信道，以減少通信開銷。⑵虛擬線路:從A到B的信道在一段時(shí)期內(nèi)是固定的，在不同時(shí)期，從A向B發(fā)送的消息可能經(jīng)由不同的信道發(fā)送。⑶動態(tài)發(fā)送:用于從A到B發(fā)送消息的信道僅當(dāng)該消息發(fā)送時(shí)才確定。由于這種選擇是自動進(jìn)行的，單一的消息可能分給不同的信道。57上述幾種方案各有利弊。固定發(fā)送不適用于通信負(fù)載的改變。即如果已在場點(diǎn)A和B之間確立了一條信道，那么消息只能經(jīng)由這條信道傳送，即使這條信道已經(jīng)超載，而其它信道還處于尚未滿載的狀態(tài)。可以利用虛擬線路策略進(jìn)行改善或通過動態(tài)發(fā)送策略來加以完全地解決。固定發(fā)送和虛擬線路策略可以確保按消息的發(fā)送次序從A向B發(fā)送消息。采用動態(tài)發(fā)送策略，消息的到達(dá)次序不一定和消息的發(fā)送次序相一致。這可以通過給每條消息賦以一個(gè)順序號來解決。582.1.2連接策略

有許多不同的方法來連接一對彼此希望通信的場點(diǎn)（或進(jìn)程）。最常用的方法有線路轉(zhuǎn)換、消息轉(zhuǎn)換和消息包轉(zhuǎn)換。

⑴線路轉(zhuǎn)換（circulateswitch）：如果兩個(gè)進(jìn)程希望通信，那么就在它們之間設(shè)立一條永久性的物理通信鏈路。這條通信鏈路供其消息轉(zhuǎn)移期間使用，在這段期間其它進(jìn)程不能使用這條鏈路。這種方案與電話系統(tǒng)類似，一旦一條通話線路已對通話雙方開通（例如甲方給乙方打電話），其它人就不能使用這條信道，除非甲乙兩方已明顯地結(jié)束其通話（例如一方已掛起話筒）。

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

⑶消息包轉(zhuǎn)換（packetswitch）：消息一般是可變長度的。為了簡化系統(tǒng)的設(shè)計(jì)。常常把消息設(shè)計(jì)成定長的形式，并把這種定長的形式稱為消息包（packet）。一條邏輯消息可能不得不劃分成若干消息包，每個(gè)消息包都可以經(jīng)由網(wǎng)絡(luò)中不同的路徑單獨(dú)地發(fā)送到其目的地，當(dāng)這些消息包都到達(dá)其目的地后，還得拼裝起來組成一條完整的消息。線路轉(zhuǎn)換需要安裝時(shí)間但傳送每條消息的開銷較少；消息轉(zhuǎn)換和消息包轉(zhuǎn)換需要較少的安裝時(shí)間，但轉(zhuǎn)移每條消息的開銷較大。此外，在采用消息包轉(zhuǎn)換方法時(shí)，每條消息可能得先“化整為零”，然后再“集零為整”。612.1.3爭奪處理

由于一條通信鏈路往往連結(jié)多個(gè)場點(diǎn)，而這些場點(diǎn)有可能希望同時(shí)在這條通信鏈路上轉(zhuǎn)移信息，從而發(fā)生爭奪現(xiàn)象。這種情況在環(huán)結(jié)構(gòu)或多存取總線結(jié)構(gòu)中表現(xiàn)得尤為突出。解決爭奪現(xiàn)象的技術(shù)，常用的有沖突檢測，令牌轉(zhuǎn)移和消息槽。

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

⑵令牌轉(zhuǎn)移（TokenPassing）：令牌是一個(gè)特殊的消息類型，它不斷地在系統(tǒng)（通常在一個(gè)環(huán)結(jié)構(gòu)）中循環(huán)。希望轉(zhuǎn)移消息的場點(diǎn)必須等待直至令牌到達(dá)。當(dāng)令牌到達(dá)后，該場點(diǎn)就從環(huán)中取走令牌并開始轉(zhuǎn)移它的消息，當(dāng)它完成了相應(yīng)的消息轉(zhuǎn)移后再重新發(fā)送令牌，這就給另一個(gè)場點(diǎn)提供了占有令牌的機(jī)會，一旦占有，就可開始它的消息轉(zhuǎn)移。如果令牌丟失。那么系統(tǒng)應(yīng)能發(fā)現(xiàn)這種情況并產(chǎn)生一個(gè)新令牌。該方法已由Primenet系統(tǒng)所采用。64

⑶消息槽(slot)：若干定長的消息槽連續(xù)不斷地在系統(tǒng)（通常是一個(gè)環(huán)結(jié)構(gòu)）中循環(huán)。每個(gè)消息槽可以容納一定長的消息和有關(guān)的控制信息（如像發(fā)送處，接收處，消息槽滿/空等）。希望轉(zhuǎn)移消息的場點(diǎn)必須等待直到一個(gè)空消息槽到達(dá)，然后，該場點(diǎn)將它的消息插入這個(gè)空消息槽并附上適當(dāng)?shù)目刂菩畔?，此消息在網(wǎng)絡(luò)中繼續(xù)流動，當(dāng)它到達(dá)某個(gè)特定的場點(diǎn)時(shí)，該場點(diǎn)就查看此消息槽的控制信息，以確認(rèn)此消息槽是否包含了發(fā)送給它的消息；若沒有，它就放過此消息槽，否則，它取走消息糟中的消息，重新設(shè)置控制信息以指明該消息槽為空。652.1.4保密問題

編碼是保護(hù)信息的常用方法之一。信息在發(fā)送之前先予以編碼，當(dāng)信息到達(dá)其目的地后就進(jìn)行譯碼。編碼技術(shù)，最常用的一種就是提供一個(gè)通用的編碼算法E，一個(gè)通用的譯碼算法D，并對每次應(yīng)用提供一個(gè)保密鍵（key），令Ek和Dk分別表示具有保密鍵k的那個(gè)特定應(yīng)用的編碼和譯碼算法，那么，對于任何消息m，該編碼系統(tǒng)必須滿足下面的特性：⑴Dk(Ek(m))=m；⑵Ek和Dk都能有效地計(jì)算；⑶該系統(tǒng)的保密性只依賴于鍵k的保密性而不依賴于算法E和D的保密性。66

一個(gè)稱之為“數(shù)據(jù)編碼標(biāo)準(zhǔn)”（DataEncryptionStandard)的編碼系統(tǒng)已由美國國家標(biāo)準(zhǔn)局所采用。不過，該方案還存在“鍵分布”問題，即，開始通信之前，保密鍵必須秘密地轉(zhuǎn)移給發(fā)送者和接收者，但在一個(gè)通信網(wǎng)絡(luò)環(huán)境中很難有效地完成這一點(diǎn)。解決此問題的辦法之一是利用一個(gè)“公共鍵”（publickey）編碼方案。每個(gè)用戶有一個(gè)公共鍵和一個(gè)私有鍵，兩個(gè)彼此知道他們的公共鍵的用戶才可以相互通信?；谏鲜鏊枷氲木幋a方案已設(shè)計(jì)出來了。這個(gè)方案曾被認(rèn)為是差不多不可破譯的。其中的公共編碼鍵是一對偶(e,n)，私有鍵是對偶(d,n),這里e,d,n都是正整數(shù)。每條消息用0～n-1之間的一個(gè)整數(shù)表示（較長的消息可分成若干較短的消息，它們每一個(gè)都可用這樣的一個(gè)整數(shù)表示），函數(shù)E和D定義為：67E(m)=memodn=CD(C)=Cdmodn

這里的主要問題是選擇編碼和譯碼鍵。整數(shù)n可用下式計(jì)算n=pq

其中p和q是隨機(jī)選取的兩個(gè)較大的素?cái)?shù)（例如，它們是由100位或更多位數(shù)字組成），d是隨機(jī)選取的一個(gè)與(p-1)(q-1)互質(zhì)的較大整數(shù)，即d滿足GCD(d,(p-1)(q-1))=1

而e則應(yīng)滿足edmod(p-1)(q-1)=1

應(yīng)指出的是，雖然n可能是大家知道的，但p和q卻很難為他人所知。因?yàn)椋瑢@里的n進(jìn)行因式分解是比鉸困難的。因此，d和e也是不易試探出來的。

68例如，令p=5和q=7，那么n=35，(p-1)(q-1)＝24。由于11與24互質(zhì)，所以可選取d=11。因?yàn)?111mod24＝12lmod24=1，因此，e=11。假定，給定m＝3，那么C=memodn=311mod35=12而Cdmodn=1211mod35=3=m因此，如果我們利用e對ｍ進(jìn)行編碼，那么，我們就能用ｄ對它進(jìn)行譯碼。692.2消息傳遞2.2.1消息傳遞原語

在分布式系統(tǒng)中，進(jìn)程相互通信是通過彼此交換消息進(jìn)行的。一個(gè)消息是從一進(jìn)程發(fā)往另一些進(jìn)程的信息單位。源進(jìn)程通過執(zhí)行send操作發(fā)送消息，宿進(jìn)程則通過執(zhí)行receive操作來獲取消息；如果必要，在其獲取消息后再通過執(zhí)行reply操作給發(fā)送者一個(gè)回復(fù)。因此，分布式操作系統(tǒng)通常提供send、receive和reply等基本通信原語來實(shí)現(xiàn)進(jìn)程間的通信和同步。70

消息轉(zhuǎn)移原語分為兩類：同步型和異步型。

1.異步型：在這類通信機(jī)制中，轉(zhuǎn)移消息的進(jìn)程不等待接收者的回復(fù)，又稱“不等”轉(zhuǎn)移（sendnoWait)，即允許發(fā)送方可任意超前于接收方，因而具有下面的特征：①接收方收到的消息與發(fā)送方目前的狀態(tài)是無關(guān)的；②由于通信機(jī)制與同步機(jī)制幾乎被截然分開，因此，系統(tǒng)應(yīng)具有“無限”的緩沖空間來容納任意超前發(fā)出而尚未處理的消息，以此來解決消息發(fā)送速度和消息處理速度之間的差異；③能比較充分地利用系統(tǒng)的潛在能力，但實(shí)現(xiàn)時(shí)須解決許多實(shí)際的控制問題。71圖2.2同步消息傳遞和異步消息傳遞72

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

消息本身要占用存貯空間，并常常存放在系統(tǒng)的緩沖區(qū)中。當(dāng)使們異步消息轉(zhuǎn)移機(jī)制時(shí)，系統(tǒng)中的每個(gè)進(jìn)程在某一時(shí)刻可能有多個(gè)尚未處理的消息。由于消息緩沖區(qū)是一個(gè)有窮的資源，因此，當(dāng)使用異步消息傳遞方式傳遞消息時(shí)，可能會發(fā)生消息緩沖區(qū)溢出的情況。因此，異步消息傳遞需要特定的消息緩沖區(qū)管理算法來處理這方面的問題。但在采用同步消息傳遞方式時(shí)，系統(tǒng)中的每個(gè)進(jìn)程決不可能存在一個(gè)以上尚未處理的消息，因此，其消息緩沖區(qū)的管理算法比較簡單。742.2.2同步消息傳遞方式的應(yīng)用

同步消息轉(zhuǎn)移方式特別適合于client/server模型。一個(gè)client通過向一個(gè)server發(fā)送一個(gè)消息來請求該server為它服務(wù)，然后這個(gè)client就掛起，直至對應(yīng)的server發(fā)來回復(fù)消息（即告之所請求的服務(wù)已經(jīng)完成）。server可以寫成一個(gè)無窮循環(huán)程序，它等待接收請求，然后處理相應(yīng)的請求，最后發(fā)回復(fù)消息。client們在等待所請求的服跟務(wù)完成時(shí)就阻塞自己。僅當(dāng)沒有消息給server，即沒有供它做的事情時(shí)，該server就阻塞，見圖2.3，其中c1ient們向time-server發(fā)送一請求給出時(shí)間的消息：send(time-server，gettime.time)。time-server循環(huán)等待請求讀時(shí)鐘的消息，然后執(zhí)行“讀時(shí)鐘”工作，并在處理下一請求消息之前發(fā)出回復(fù)，即time-server和client可分別編寫成如下的程序段：75timeserver:

whiletruedo receive(request); readclock(time); reply(time);end;client：send(timeserver,gettime,time);圖2.3使用消息轉(zhuǎn)移方式的client/server模型76

一般，server可以設(shè)計(jì)成依次重復(fù)執(zhí)行下述步驟的程序段：⑴等待接收來自clients發(fā)送的“請求服務(wù)”的消息；⑵接收clients發(fā)來的“請求服務(wù)”的消息；⑶處理clients發(fā)來的“請求服務(wù)”的消息；⑷向clients發(fā)送“服務(wù)已完成”的回復(fù)消息。僅當(dāng)沒有“請求服務(wù)”的消息到達(dá)時(shí)，server就阻塞自己。clients在等待server的回復(fù)消息時(shí)就阻塞它們自己，從而實(shí)現(xiàn)了clients與server的同步。在設(shè)計(jì)server進(jìn)程時(shí)，通常要求：⑴server必須能調(diào)度和回復(fù)多個(gè)并發(fā)的請求消息；⑵server處理請求消息和發(fā)送回復(fù)消息的次序與接收該請求消息的次序無關(guān)；⑶在server給client發(fā)送回復(fù)消息時(shí)，決不應(yīng)阻塞；⑷某個(gè)相關(guān)的client故障，不應(yīng)影響server的操作。77

同步原語有一種與信息交換不同的特性。當(dāng)一個(gè)進(jìn)程引用了一個(gè)掛起的原語時(shí)，它就阻塞自己直至此原語執(zhí)行完畢。同步原語的這種”阻塞”特性，類似于單處理機(jī)中所使用的信號量，可用于同步目的。圖2.4(a)展示了兩個(gè)進(jìn)程使用信號量進(jìn)行同步例子，其中，當(dāng)P1在信號量sem上等待時(shí)，它就彼阻塞直至P2喚醒它。一個(gè)進(jìn)程等待另一進(jìn)程的類似效果也可利用同步send/receive原語實(shí)現(xiàn)，見圖2.4(b)。78圖2.4同步79

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

802.3遠(yuǎn)程過程調(diào)用

遠(yuǎn)程過程調(diào)用（RemoteProcedureCall）就是把過程調(diào)用的概念加以擴(kuò)允后引入分布式環(huán)境中的一種形式。遠(yuǎn)程過程調(diào)用的形式和行為與傳統(tǒng)的過程調(diào)用的形式和行為類似，主要差別在于被調(diào)用的過程實(shí)際運(yùn)行在一個(gè)與調(diào)用者所在場點(diǎn)不同的場點(diǎn)上，見圖2.6。因此，需要設(shè)計(jì)相應(yīng)的軟件來實(shí)現(xiàn)兩者之間的連接和信息溝通。81圖2.5消息轉(zhuǎn)移與過程調(diào)用的類似性圖2.6遠(yuǎn)程過程調(diào)用示意圖822.3.1RPC機(jī)制的結(jié)構(gòu)及實(shí)現(xiàn)1.RPC機(jī)制的結(jié)構(gòu)由下列成份組成：⑴stub：client和server各一個(gè)；⑵控制部分：為追蹤RPC的調(diào)用狀態(tài)所設(shè)；⑶傳送部分：確定如何將信息從一個(gè)場點(diǎn)傳送到另一個(gè)場點(diǎn)。實(shí)現(xiàn)RPC的一般過程可概括如圖2.7所示：圖2.7實(shí)現(xiàn)RPC的一般過程83client’sstub與一個(gè)client連接，它對于該client就像一個(gè)“server”。在調(diào)用時(shí)，它截取client的遠(yuǎn)程過程調(diào)用命令后，利用通信網(wǎng)絡(luò)向server發(fā)送“請求服務(wù)”的信息。在返回時(shí)，它獲取返回消息，并帶返回結(jié)果返回到client，然后client繼續(xù)執(zhí)行。

Server’sstub與一個(gè)server連接，它對于該server就像一個(gè)“client”。在調(diào)用時(shí)，它收到遠(yuǎn)程調(diào)用請求后，產(chǎn)生一個(gè)本地調(diào)用，去執(zhí)行被請求的遠(yuǎn)程過程。在返回時(shí)，它截取遠(yuǎn)程過程的返回結(jié)果，并形成返回消息發(fā)送出去。stub包含了一組RPC機(jī)制的操作原話，這些原語構(gòu)成了RPC調(diào)用的實(shí)現(xiàn)細(xì)節(jié)，它可獨(dú)立于client和server編程，在編譯時(shí)再連接起來84RPC的實(shí)現(xiàn)要考慮兩個(gè)方面的問題。第一，當(dāng)進(jìn)行遠(yuǎn)程過程調(diào)用時(shí)，調(diào)用場點(diǎn)必須能定位出被調(diào)用的過程實(shí)際上運(yùn)行在哪個(gè)場點(diǎn)上；第二，相關(guān)的兩個(gè)場點(diǎn)必須能協(xié)同合作交換信息。所有這些對用戶都是透明的，這些的工作是依次進(jìn)行的。下面介紹一種實(shí)現(xiàn)RPC的方法．其實(shí)現(xiàn)思想已概括在圖2.8中。8586圖2.8RPC的實(shí)現(xiàn)概況87

每個(gè)遠(yuǎn)程過程由若干成分組成：調(diào)用者（caller）或用戶（user）調(diào)用代碼段以及被調(diào)用者（callee）或server被調(diào)用代碼段。這些都可用常規(guī)的程序設(shè)計(jì)語言編寫，不需要利用特別的設(shè)施，就象它們在同一場點(diǎn)上執(zhí)行一樣。與調(diào)用者相關(guān)的stub與被調(diào)用者相關(guān)的stubRPCruntime子程序，可在系統(tǒng)中所有場點(diǎn)上運(yùn)行。2.

RPC的實(shí)現(xiàn)stub程序的功能是把這種過程調(diào)用中所帶的參數(shù)組裝和拆卸成消息形式，并進(jìn)行相應(yīng)的類型檢查，然后把這些消息轉(zhuǎn)移給RPCruntime子程序，后者再把它們發(fā)送到系統(tǒng)中的其它場點(diǎn)。程序設(shè)計(jì)者定義了過程并寫好了過程體，而系統(tǒng)生成了對應(yīng)的stub。實(shí)現(xiàn)一個(gè)遠(yuǎn)程過程調(diào)用的主要工作環(huán)節(jié)如下。88⑴調(diào)用者用通常方式調(diào)用對應(yīng)stub中的一個(gè)過程；⑵這個(gè)stub過程把有關(guān)的參數(shù)組裝成一個(gè)消息包或一組消息包，以形成一條消息。運(yùn)行此過程的那個(gè)場點(diǎn)的“地址”和那個(gè)場點(diǎn)上指稱此過程的“標(biāo)識符”都應(yīng)包含在這條消息中；⑶將這條消息發(fā)送給對應(yīng)的RPCruntme子程序，該子程序再把它發(fā)送給指定的場點(diǎn)。89⑷在接收此消息時(shí)，遠(yuǎn)程runtime子程序引用與被調(diào)用者對應(yīng)的stub中的一個(gè)子程序，并讓它來處理這條消息；⑸被調(diào)用者對應(yīng)的stub中的這個(gè)子程序拆卸有關(guān)的參數(shù)并用通常的過程調(diào)用方式調(diào)用所需的過程。⑹返回調(diào)用結(jié)果，整個(gè)遠(yuǎn)程過程調(diào)用以與調(diào)用者對應(yīng)的stub程序執(zhí)行“return”語句返回到用戶而終止。90

在上面的述中，我們回避了一個(gè)重要的問題，即與用戶對應(yīng)的stub如何知道實(shí)際運(yùn)行遠(yuǎn)程過程的場點(diǎn)之地址呢？一些解決這一向題的方法：⑴當(dāng)系統(tǒng)生成與調(diào)用者對應(yīng)的stub時(shí)，可把該遠(yuǎn)程場地的地址也一同并入其中，不過這種做法不太靈活。⑵在進(jìn)行調(diào)用之前，與調(diào)用者對應(yīng)的stub向系統(tǒng)中的其它場點(diǎn)進(jìn)行廣播，請求有關(guān)的場點(diǎn)通報(bào)其地址，這必然引起一系列的消息轉(zhuǎn)移。特別，當(dāng)這種廣播是在若干網(wǎng)絡(luò)之間進(jìn)行時(shí)，其轉(zhuǎn)移速度是很慢的。⑶由系統(tǒng)管理一個(gè)表，其表項(xiàng)的內(nèi)容為①場點(diǎn)地址；②該場點(diǎn)上將運(yùn)行的遠(yuǎn)程過程的名字。

912.3.2RPC執(zhí)行時(shí)各部分之間的關(guān)系

RPC執(zhí)行時(shí)，各部分的關(guān)系如圖2.9所示。其中，傳輸部分是RPC的最低層，其主要功能為：⑴提供對網(wǎng)絡(luò)傳輸層協(xié)議的選擇；⑵建立/釋放邏輯信道，發(fā)送/接收消息等；⑶管理RPC中的消息緩沖區(qū)。9293圖2.9RPC執(zhí)行時(shí)各部分的關(guān)系圖94

控制部分的主要功能是：⑴確定RPC中消息的方向（發(fā)送或接收）；當(dāng)client的stub開始一次RPC調(diào)用或者server向server的stub返回調(diào)用結(jié)果時(shí)，該部分負(fù)責(zé)控制傳輸部分進(jìn)行發(fā)送。⑵場點(diǎn)間會合與進(jìn)程同步；場點(diǎn)間會合是指為使兩個(gè)場點(diǎn)間進(jìn)程同步，它們必須同意“會合（rendezvous）”，即早到達(dá)的進(jìn)程要等待晚到達(dá)的進(jìn)程。會話進(jìn)程通過場點(diǎn)間會合建立一致的起點(diǎn)，并以該起點(diǎn)作為進(jìn)程同步點(diǎn)進(jìn)行對話。⑶若干狀態(tài)信息的處理。由上可知，由于client的stub的作用，使得client可用常規(guī)過程調(diào)用方式去調(diào)用遠(yuǎn)程過程；由于server的stub的作用，使得server程序可以獨(dú)立于調(diào)用者來編程，因而比較靈活。

本地調(diào)用和遠(yuǎn)程過程調(diào)用之間存在許多不同之處。如果遠(yuǎn)程調(diào)用是在兩種異型機(jī)器間進(jìn)行，這就存在數(shù)據(jù)表示問題，例如，這兩類機(jī)器的字長可能不同。解決這一向題的方法之一是它在轉(zhuǎn)移數(shù)據(jù)之前，讓RPC機(jī)制將有關(guān)的數(shù)據(jù)轉(zhuǎn)換成一種統(tǒng)一的格式，接收場點(diǎn)在接收數(shù)據(jù)時(shí)，再把它們轉(zhuǎn)換成本地所允許的數(shù)據(jù)格式。第二個(gè)問題是如何解釋指針，更確切他說，一個(gè)指針到底訪問的是什么，在不具有共享地址空間的情況下，RPC不可能允許在網(wǎng)絡(luò)范圍內(nèi)轉(zhuǎn)移指針。因此，在RPC中是不可能用“reference方式”傳遞參數(shù)的。

952.3.3RPC的語義

更嚴(yán)重的問題是調(diào)用者和被調(diào)用者都可能在調(diào)用期間發(fā)生故障，而且經(jīng)常是被調(diào)用者故障，留下調(diào)用者掛起。如果發(fā)生這種情況，調(diào)用者可能不得不夭折，這在本地調(diào)用中是決不會出現(xiàn)的。96

一個(gè)遠(yuǎn)程過程調(diào)用故障之后，調(diào)用者很難得知在故障發(fā)生前，該過程調(diào)用已經(jīng)進(jìn)行到了哪一步。這通常有三種可能：⑴在被調(diào)用者接收到調(diào)用它的命令之前，它發(fā)生了故障。⑵在執(zhí)行其過程體時(shí)，被調(diào)用者發(fā)生了故障；⑶被調(diào)用者正確地完成了其過程體的執(zhí)行，但在把結(jié)果返回給調(diào)用者之前發(fā)生了故障。此外，還有調(diào)用者在發(fā)出調(diào)用命令之后并在獲得調(diào)用結(jié)果之前發(fā)生了故障。

97

由于調(diào)用者無法知道到底出現(xiàn)哪種情況，因此，系統(tǒng)必須提供一些基本的保護(hù)機(jī)制來確保RPC正確效果。不過，這個(gè)問題由于通信方面也可能出錯(cuò)以及系統(tǒng)試圖進(jìn)行錯(cuò)誤矯正而混雜在一起，使得一個(gè)遠(yuǎn)程過程在成功地完成其執(zhí)行之前，實(shí)際上可能引用了若干次。不同的RPC實(shí)現(xiàn)方案定義的這種效果或RPC語義是有差別的，幾種常用的定義RPC語義的規(guī)則是：98

⑴1ast-of-many對執(zhí)行一個(gè)遠(yuǎn)程過程調(diào)用而言，被調(diào)用的過程可能執(zhí)行若干次，但規(guī)定其最后一次執(zhí)行的結(jié)果作為返回結(jié)果；⑵at-most-once若調(diào)用者收到了回復(fù)消息，則被調(diào)用的過程正確地完成了它的一次（僅僅一次）執(zhí)行。如果調(diào)用者沒收到回復(fù)消息，或者，如果調(diào)用者在獲得回復(fù)消息之前發(fā)生故障，那么，這時(shí)的調(diào)用效果就看作是根本就沒有執(zhí)行相應(yīng)的過程。

99

⑶at-1east-once在場點(diǎn)正常情況下，則遠(yuǎn)程過程至少執(zhí)行一次，且回復(fù)消息可能返回一次或多次。在場點(diǎn)故障時(shí)，就不能保證遠(yuǎn)程過程是否已被執(zhí)行或曾返回任何回復(fù)消息。⑷exactly-once若server正常，則遠(yuǎn)程過程將恰好執(zhí)行一次，并返回一個(gè)調(diào)用結(jié)果。同send/receive通信原語有許多變種一樣，RPC也有一些不同的形式。例如可以允許異步遠(yuǎn)程過程調(diào)用，因此，調(diào)用者和被調(diào)用者可以并行執(zhí)行，調(diào)用者負(fù)責(zé)在稍后某一時(shí)刻執(zhí)行一個(gè)所謂的會合（rendezvous）來獲取調(diào)用結(jié)果。100101Thanks!第3章分布式協(xié)同處理

3.1時(shí)間定序與時(shí)戳3.2分布式互斥算法3.3選擇算法

3.1時(shí)間定序與時(shí)戳3.1.1分布式算法的基本特征

在集中式方案中，一個(gè)場點(diǎn)被指定為中央控制場點(diǎn)，由它來控制對共享資源的存取。每當(dāng)一個(gè)場點(diǎn)希望存取一共享對象時(shí)，它就向該中央場點(diǎn)發(fā)一請求消息。當(dāng)所指共享對象可供某場點(diǎn)使用時(shí)，控制場點(diǎn)就回送一個(gè)“可以訪問”的消息給它。這種方案的弱點(diǎn)是中央控制場點(diǎn)可能變成瓶頸，而且一旦它故障，整個(gè)系統(tǒng)就崩潰了。可見，一個(gè)集中式算法具有兩個(gè)明顯的特點(diǎn)：⑴只有一個(gè)中央控制場點(diǎn)在進(jìn)行決策；⑵所有必要的信息都集中在該中央控制場點(diǎn)上。

與之相反，一個(gè)分布式算法的基本特征是：⑴所有的場點(diǎn)都有差不多同等數(shù)量的信息；⑵所有的場點(diǎn)都是根據(jù)本地信息來進(jìn)行決策的；⑶所有的場點(diǎn)對最終的決策都負(fù)有同等的責(zé)任；⑷所有的場點(diǎn)在影響最終決策時(shí)都付出了同等的努力；⑸算法具有強(qiáng)健性，系統(tǒng)的局部故障不影響算法的有效性。實(shí)際上，不管分布的程度和方式如何，對所有的分布式算法都有如下兩種基本的假定。

假定1每個(gè)場點(diǎn)只是整個(gè)系統(tǒng)的一部分，且決策都是根據(jù)本地信息進(jìn)行的；

假定2不存在全系統(tǒng)范圍內(nèi)的公共時(shí)鐘。

假定2是一個(gè)主要的制約，因?yàn)槟艽_定出事件發(fā)生的先后次序是極其重要的，它是計(jì)算系統(tǒng)中的一個(gè)基本概念。例如，在進(jìn)行資源分配時(shí)，通常規(guī)定僅當(dāng)某資源已經(jīng)釋放之后才可再次使用它。在分布式系統(tǒng)中，由于沒有公共時(shí)鐘，所以直接說某事件在另一事件之前或之后發(fā)生是不嚴(yán)格的。為了確定設(shè)計(jì)分布式算法的牢固基礎(chǔ)，我們必須尋求一種在全分布式系統(tǒng)范圍內(nèi)進(jìn)行事件定序的方法。3.1.2分布式系統(tǒng)中的事件定序方法

由于沒有公共的時(shí)鐘如何定序分布式系統(tǒng)中的事件呢？因?yàn)檫M(jìn)程本身具有順序性，所以在單個(gè)進(jìn)程中的事件是按時(shí)間完全定序的。此外，根據(jù)因果法則我們可以假定”發(fā)送”一個(gè)消息的事件發(fā)生在“接收”同一消息的事件之前。以上兩點(diǎn)自然給系統(tǒng)中的事件提供了一個(gè)偏序，稱之為HappenedBefore關(guān)系（筒稱HB），并用“”表示，其定義如下：

⑴ab①若a和b是同一進(jìn)程中的兩個(gè)事件，且a在b前發(fā)生；或者，②若a是一進(jìn)程中發(fā)送消息的事件，且b是另一進(jìn)程中接收同一消息的事件。

⑵該關(guān)系是轉(zhuǎn)移的，即若ab且bc，則有ac。

⑶該關(guān)系是非自反的。

⑷若兩個(gè)不同的事件之間不存在這種關(guān)系，即(ab)且(ba)，則a和b稱為并發(fā)事件。因而，它們可以并發(fā)執(zhí)行。例如，圖中某些事件的HB關(guān)系是：

p1q2 r0q4 q3r1 p1q4（因?yàn)閜1q2且q2q4）圖中的某些并發(fā)事件是：

q0和p2 r0和q3 r0和p3 q3和p3圖3.1三個(gè)并發(fā)進(jìn)程的相對時(shí)間并發(fā)和HB關(guān)系可用圖示加以說明，如圖3.1所示，

因此，引進(jìn)一個(gè)系統(tǒng)的邏輯時(shí)鐘，用它的值來反映這個(gè)關(guān)系，從而實(shí)現(xiàn)整個(gè)系統(tǒng)中的事件定序?，F(xiàn)假定，對每個(gè)進(jìn)程pi，有一個(gè)與其相關(guān)的邏輯時(shí)鐘Ci，賦給進(jìn)程pi中事件a的邏輯時(shí)鐘之值即Ci(a)。這種邏輯時(shí)鐘可用一個(gè)計(jì)數(shù)器實(shí)現(xiàn)。若用C表示系統(tǒng)的邏輯時(shí)鐘，則為使系統(tǒng)的邏輯時(shí)鐘C能正確的計(jì)值，下面的條件應(yīng)成立：時(shí)鐘（clock）條件：對系統(tǒng)中的任何事件a和b，若ab，則C(a)<C(b)。若下面兩個(gè)條件滿足，則時(shí)鐘條件成立：

條件1：對于進(jìn)程pi中的兩個(gè)事件a和b，若ab則有Ci(a)<Ci(b)；

條件2：若a是進(jìn)程pi發(fā)送消息的事件，b是進(jìn)程pj接收同一消息的事件，則有Ci(a)<Cj(b)

若按下面方法實(shí)現(xiàn)這種邏輯時(shí)鐘，則上述兩條件可以滿足：⑴進(jìn)程pi在其任何兩個(gè)相繼的事件之間使Ci增值；⑵若事件a表示進(jìn)程pi中發(fā)送消息m的事件，則發(fā)送消息m的事件就附有時(shí)間戳Tm＝Ci(a)；⑶若事件b是進(jìn)程pj(ij)中接收消息m的事件，pj就置Cj(b)之值為Cj(b)=max(Cj,Tm)+1

我們稱進(jìn)程pi中的事件a先于進(jìn)程pj中的事件b（以ab表示）當(dāng)且僅當(dāng)⑴Ci(a)<Cj(b)；或⑵Ci(a)=Cj(b)，且pipj，其中關(guān)系“”是進(jìn)程的一個(gè)任意偏序。實(shí)現(xiàn)關(guān)系“”的一個(gè)簡單方法是給系統(tǒng)中每個(gè)進(jìn)程賦以一個(gè)唯一的進(jìn)程號，且規(guī)定：若i<j，則pipj?？梢宰C明下列結(jié)果：⑴若ab，則一定不成立ba。⑵若ab，則ab。⑶若ab，bc則ac。分布式互斥的幾點(diǎn)要求：（1）安全性：在某一時(shí)刻至多只有一個(gè)進(jìn)程在臨界段內(nèi)執(zhí)行。（2）可用性：請求進(jìn)入臨界段的進(jìn)程終將準(zhǔn)入。（3）定序：按關(guān)系“”排定的次序進(jìn)入臨界段。3.2分布式互斥算法3.2.1分布式互斥算法的基本假定分布式算法有如下的基本假定：⑴一個(gè)分布式系統(tǒng)由n個(gè)場點(diǎn)組成，它們從1到n唯一地編號，每個(gè)場點(diǎn)含有一個(gè)進(jìn)程，而且進(jìn)程和場點(diǎn)間存在一一對應(yīng)的關(guān)系。⑵流水線（pipeline）特性成立，即從一個(gè)進(jìn)程發(fā)送給另一進(jìn)程的消息是按它們發(fā)送的次序接收的。⑶每條消息在有窮時(shí)間間隔內(nèi)都能正確地轉(zhuǎn)移到它的目的地。⑷系統(tǒng)是全互連的，因而每個(gè)進(jìn)程都可直接給其它的進(jìn)程發(fā)送消息。3.2.2集中式算法

分布式系統(tǒng)中實(shí)現(xiàn)互斥最直接的方法就是模擬單處理器系統(tǒng)的互斥方法。選擇一個(gè)進(jìn)程作為協(xié)調(diào)者（即運(yùn)行在最高網(wǎng)址的機(jī)器上的某個(gè)進(jìn)程）。某個(gè)進(jìn)程要進(jìn)入臨界區(qū)時(shí)，向協(xié)調(diào)者發(fā)請求信息，指出它要進(jìn)入臨界區(qū)，然后等待協(xié)調(diào)者的許可。如果當(dāng)前沒有其他進(jìn)程在該臨界區(qū)中，協(xié)調(diào)者就返回一個(gè)許可消息，請求信息的進(jìn)程接收到許可響應(yīng)后，就進(jìn)入臨界區(qū)，否則就要等待。如下圖所示集中式算法3.2.3分布式算法(Lamport算法)

第一個(gè)分布式方法是由Lamport[1978]提出的。算法的工作過程如下。進(jìn)程要進(jìn)入臨界區(qū)時(shí)，建立一個(gè)包含臨界區(qū)名，進(jìn)程號和當(dāng)前時(shí)間的消息。然后將該消息發(fā)送給其他所有進(jìn)程，概念上說也包括發(fā)送消息的進(jìn)程本身。每個(gè)進(jìn)程管理一個(gè)請求隊(duì)列。發(fā)送進(jìn)入臨界區(qū)的請求消息后，進(jìn)程就坐等其他進(jìn)程的許可消息。一但它得到所有進(jìn)程的許可，就可以進(jìn)入臨界區(qū)了。進(jìn)程退出臨界區(qū)時(shí)，向在該進(jìn)程的隊(duì)列中的所有進(jìn)程發(fā)送OK消息，并從隊(duì)列中刪除這些進(jìn)程。某進(jìn)程接收到其他進(jìn)程發(fā)送的請求消息后。所采取的動作由它和消息中所包含臨界區(qū)名決定。共分以下三種情況：

1）如果接收者不在臨界區(qū)內(nèi)，而且它不想進(jìn)人臨界區(qū)，就返回一個(gè)OK消息給發(fā)送者。

2）如果接收者在臨界區(qū)內(nèi)，就不做任何響應(yīng)，只是將請求送入等待隊(duì)列。

3）如果接收者要進(jìn)入臨界區(qū)。但還沒有進(jìn)入，它就比較接收到的消息中的時(shí)間戳與它自己發(fā)送給其他進(jìn)程的請求消息中的時(shí)間戳。時(shí)間戳小的請求獲勝。如果當(dāng)前接收到的消息中的時(shí)間戳小，就發(fā)送一個(gè)OK消息。否則，如果該進(jìn)程自己發(fā)送的消息中的時(shí)間戳小，就不做任何響應(yīng)，只將接收到的請求放入隊(duì)列中。分布式算法改進(jìn)的Lamport算法

設(shè)R是某分布式系統(tǒng)中所有進(jìn)程的集合，R={P1，P2，……Pn}，Ti是Pi進(jìn)程的邏輯時(shí)間戳。一個(gè)進(jìn)程要進(jìn)入臨界區(qū)需要執(zhí)行以下的算法步驟：申請臨界區(qū)

當(dāng)Pi進(jìn)程要進(jìn)入臨界區(qū)時(shí)，向R中的每一個(gè)進(jìn)程發(fā)送消息REQ(Ti，Pi)；當(dāng)Pj接收到來自Pi的請求消息時(shí)，可以根據(jù)臨界區(qū)的使用情況及進(jìn)程自己的狀態(tài)，做出三種處理：第一種情況，若接收者Pj不在臨界區(qū)中，也不想進(jìn)入臨界區(qū)，Pj向Pi發(fā)送REPLY應(yīng)答消息。第二種情況，若接收者Pj已在臨界區(qū)中，則不應(yīng)答并暫存Pi的請求消息，對請求隊(duì)列排隊(duì)。第三種情況，若接收者Pj也向R中的其他進(jìn)程發(fā)送了進(jìn)入臨界區(qū)的請求，但還沒有進(jìn)入臨界區(qū)時(shí)，Pj將接收到的消息與自己發(fā)送的消息的時(shí)間戳進(jìn)行比較，如果接收到的Pi時(shí)間戳小，進(jìn)程Pj向Pi發(fā)送REPLY應(yīng)答消息；否則，接收者Pj的時(shí)間戳小，則不應(yīng)答任何請求消息，只負(fù)責(zé)暫存請求消息和對請求隊(duì)列的排隊(duì)。進(jìn)入臨界區(qū)

當(dāng)Pi進(jìn)程接收到R進(jìn)程集合中所有的應(yīng)答消息REPLY后，Pi進(jìn)程進(jìn)入臨界區(qū)。退出臨界區(qū)

當(dāng)Pi進(jìn)程退出臨界區(qū)時(shí)，向排隊(duì)等候進(jìn)入臨界區(qū)的所有進(jìn)程發(fā)送REPLY消息。3.2.4令牌環(huán)算法

這里有一個(gè)總線網(wǎng)絡(luò)如圖所示，（如，以太網(wǎng)），其中的進(jìn)程沒有內(nèi)定的次序。軟件中構(gòu)造一個(gè)邏輯環(huán)每個(gè)進(jìn)程在環(huán)上被給定一個(gè)位置，

初始化環(huán)時(shí)，給進(jìn)程0一個(gè)令牌（token）。令牌在環(huán)上循環(huán)傳播。令牌從進(jìn)程k到進(jìn)程k＋1（對環(huán)的大小取模）由點(diǎn)到點(diǎn)的消息完成。進(jìn)程從它的相鄰結(jié)點(diǎn)獲得令牌后，檢查自己是否要進(jìn)入臨界區(qū)，如果是，就進(jìn)入臨界區(qū)，完成所需要工作后退出臨界區(qū)。退出之后，該進(jìn)程就將令牌在環(huán)上向后傳遞。這里不允許某個(gè)進(jìn)程利用同一個(gè)令牌進(jìn)人第二個(gè)臨界區(qū)。

如果進(jìn)程得到令牌時(shí)不要進(jìn)入臨界區(qū)，它就將令牌直接傳送給環(huán)上的下一個(gè)結(jié)點(diǎn)。因此，所有的進(jìn)程都不需進(jìn)入臨界區(qū)時(shí)，令牌就在環(huán)上高速循環(huán)傳送。該算法的正確性是顯而易見的。任何時(shí)刻都只有一個(gè)進(jìn)程得到令牌，因此只有一個(gè)進(jìn)程可以進(jìn)入臨界區(qū)。三種算法的比較三種互斥算法的比較算法進(jìn)入/退出臨界區(qū)所需的消息數(shù)等待進(jìn)入延遲（消息時(shí)間）問題集中式32協(xié)調(diào)著崩潰分布式3（n-1）2（n-1）任何進(jìn)程崩潰令牌環(huán)1～∞0～n-1令牌丟失，進(jìn)程崩潰3.3選舉算法許多分布式算法中都要一個(gè)進(jìn)程充當(dāng)協(xié)調(diào)者。假定每個(gè)進(jìn)程都有一個(gè)唯一的進(jìn)程號，通常選舉算法都指定具有最高進(jìn)程號的進(jìn)程作為協(xié)調(diào)者。

選舉算法的目的就是：保證在選舉執(zhí)行后，所有進(jìn)程都認(rèn)可某個(gè)進(jìn)程成為了新的協(xié)調(diào)者。3.3.1Bully算法

當(dāng)某個(gè)進(jìn)程注意到協(xié)調(diào)者無法響應(yīng)進(jìn)程的請求時(shí)，該進(jìn)程就初始啟動一個(gè)選舉過程。進(jìn)程P執(zhí)行的選舉過程如下：

l）P向所有進(jìn)程號比它高的進(jìn)程發(fā)ELECTION消息。

2)如果得不到其他進(jìn)程的響應(yīng)，進(jìn)程P獲勝，成為協(xié)凋者。

3)如果有一個(gè)進(jìn)程號更高的進(jìn)程響應(yīng)，該進(jìn)程就接管選舉過程。進(jìn)程P的任務(wù)完成。

bully選舉算法

3.3.2環(huán)算法

另外一個(gè)選舉算法利用了環(huán)，但與前不同的是，這里沒有用到令牌。假定對所有進(jìn)程進(jìn)行了物理或邏輯排序，因此每個(gè)進(jìn)程都知道它的后繼進(jìn)程是哪個(gè)進(jìn)程。任何一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者不再起作用時(shí)，就創(chuàng)建一條包含該進(jìn)程號的ELECTION消息．并將該消息發(fā)送給其后繼進(jìn)程。如果后繼進(jìn)程已經(jīng)中止，就跳過它發(fā)送給下一個(gè)進(jìn)程，依此類推．直到找到一個(gè)正在運(yùn)行的進(jìn)程為止。每個(gè)進(jìn)程接收到ELECTION消息后，就將自己的進(jìn)程號加入消息中的進(jìn)程表。最后ELECTION消息會回到創(chuàng)建它的那個(gè)進(jìn)程。進(jìn)程接收到的ELECTION消息中已經(jīng)包含該進(jìn)程的進(jìn)程號時(shí)，就可以斷定這條消息是由它自己創(chuàng)建的。這時(shí)，將消息類型改為COORDINATOR，再次在環(huán)上循環(huán)發(fā)送。這次是將新的協(xié)調(diào)者（進(jìn)程表中進(jìn)程號最大的進(jìn)程）和環(huán)上現(xiàn)有的成員通知給其他進(jìn)程，COORDINATOR消息在環(huán)上循環(huán)一周后，從環(huán)上移去該消息，各進(jìn)程恢復(fù)其原有操作。環(huán)選舉算法That'sAll!第四章分布式資源管理1354.1資源共享4.2資源管理策略4.3分布式系統(tǒng)中的死鎖處理1364.1資源共享實(shí)現(xiàn)資源共享的三種方法。4.1.1數(shù)據(jù)遷移數(shù)據(jù)遷移的兩種方法：

第一種方法是將整個(gè)文件轉(zhuǎn)移給場點(diǎn)A，爾后，所有對該文件的存取都是局部的了。當(dāng)用戶不再需要訪問該文件時(shí)，它的副本（如果它被修改過）被回送給場點(diǎn)B。對一個(gè)文件的任何微小的修改，都得將這整個(gè)文件傳送回去。137

另一種方法是只將該文件中實(shí)際需要的部分轉(zhuǎn)移給A。一旦用戶不再使用該文件，該文件的任何已作過修改時(shí)部分必須回送給場點(diǎn)B。顯然，如果只訪問一個(gè)較大文件的一小部分，那么采用后一種方法較好；否則采用第一種方法較合適。不過，僅僅從一個(gè)場點(diǎn)向另一個(gè)場點(diǎn)轉(zhuǎn)移數(shù)據(jù)是不夠的，系統(tǒng)還得執(zhí)行各種數(shù)據(jù)轉(zhuǎn)換（如果兩個(gè)場點(diǎn)不是直接兼容的話）。例如，如果它們使用了不同的字符代碼表示。138

4.1.2計(jì)算遷移

在某些情形中，轉(zhuǎn)移計(jì)算比轉(zhuǎn)移數(shù)據(jù)更有效。例如，考慮這樣一個(gè)作業(yè)，它需要存取位于不同場點(diǎn)上的若干較大的文件，以獲得它們的概況。一種比較有效的辦法是在它們駐留的場點(diǎn)上各自存取這些文件，然后分別回送所需要的值給初啟該計(jì)算的那個(gè)場點(diǎn)。計(jì)算的實(shí)現(xiàn)方式：可用一個(gè)遠(yuǎn)程過程調(diào)用來初啟。進(jìn)程p引用場點(diǎn)A上預(yù)定義的一個(gè)過程，該過程執(zhí)行完后給p回送所需要的結(jié)果。139

通過消息傳遞的方式。進(jìn)程p可以發(fā)送一條消息給場點(diǎn)A，操作系統(tǒng)在場點(diǎn)A創(chuàng)建一個(gè)新進(jìn)程q，q的功能是執(zhí)行由該消息所指定的任務(wù)，當(dāng)q完成其執(zhí)行后，它又通過消息系統(tǒng)給p回送所需要的結(jié)果。這兩種方案都可用來存取駐留在各個(gè)場點(diǎn)上的若干文件。1404.1.3作業(yè)遷移當(dāng)一個(gè)作業(yè)提交給系統(tǒng)后，系統(tǒng)可以在一特定的場點(diǎn)上執(zhí)行這整個(gè)作業(yè)，或在不同的場點(diǎn)上執(zhí)行它的某一部分利用這種方案的主要原因是：⑴負(fù)載均衡：作業(yè)（或子作業(yè)）可以分散到系統(tǒng)中以均衡系統(tǒng)的工作負(fù)載。⑵計(jì)算速度的提高：如果單個(gè)作業(yè)可以分解成若干子作業(yè)，這些子作業(yè)可以在不同的場點(diǎn)并發(fā)地執(zhí)行，那么，整個(gè)作業(yè)的周轉(zhuǎn)時(shí)間將會減少。

⑶硬件特性：該作業(yè)可能有這祥一些特性，即它比較適合于在某些特殊的處理機(jī)上執(zhí)行。例如，矩陣轉(zhuǎn)換就比較適合于在陣列機(jī)上執(zhí)行。⑷軟件特性：該作業(yè)可能需要特定場點(diǎn)上的軟件或不能移動的軟件，或者移動該作業(yè)比較劃算。顯示遷移隱式遷移1411424.2資源管理管理策略

分布式系統(tǒng)對于資源管理有兩種基本的觀點(diǎn)：單個(gè)資源管理單個(gè)資源與多個(gè)管理機(jī)構(gòu)相互關(guān)系的角度進(jìn)行分析。多個(gè)資源管理多個(gè)資源與多個(gè)管理機(jī)構(gòu)相互關(guān)系的角度進(jìn)行分析。前者是后者的基礎(chǔ)，后者是前者的提高。143

⑴單個(gè)資源管理，有四種資源管理方式：集中管理方式：只有一個(gè)管理者對該資源的各種活動統(tǒng)一進(jìn)行管理，其它管理者對該資源均不具有管理職能和責(zé)任。該方式也稱為專制（autocratic）管理方式。功能分布管理方式：多個(gè)管理者按照不同的資源活動分擔(dān)管理職能和責(zé)任，且每種活動只由一個(gè)管理者管理。該方式也稱為分擔(dān)管理方式或分割（partitioned)管理方式。144浮動管理方式：多個(gè)管理者均可同等地?fù)?dān)負(fù)管理職能和責(zé)任，但在一段時(shí)間內(nèi)，只有一個(gè)管理者行使職權(quán)，“任期”滿后再由另一管理者接替，如此輪流下去。該方式也稱輪流（successive）管理方式。分散管理方式：多個(gè)管理者采取協(xié)商一致的原則對資源活動進(jìn)行全面管理，其中各個(gè)管理者的地位和功能是完全平等的。該方式也稱民主(democratic）管理方式。

145⑵從多個(gè)資源管理，可分為如下四種管理方式：

集中：每一類資源只屬一個(gè)管理者管理。它控制該類全部資源。

分管（集中分布式）：每一類資源由多個(gè)管理者管理，但每一資源只屬一個(gè)管理者管理。

合管（完全分布式）：不僅每一類資源存在多個(gè)管理者管理，而且該類中每個(gè)資源屬于全部管理者共同管理。

部分管理：每一類資源由多個(gè)管理者管理，每一資源屬于若干管理者管理。如圖4.1所示。其中圓圈表示管理者，三角形表示資源。146圖4.1資源管理方式147

分布式管理方式和集中式管理方式的主要區(qū)別是對同類資源是采用多個(gè)管理者還是一個(gè)管理者