第五章分布式OS

1、第五章分布式操作系統(tǒng)第1節(jié)分布式系統(tǒng)概述1966 Michael J. Flynn提出按照指令流和數(shù)據(jù)流的多重性狀況對(duì)計(jì)算機(jī)系統(tǒng)進(jìn)行分類。指令流是指機(jī)器 執(zhí)行的指令序列；數(shù)據(jù)流是指由指令流調(diào)用的數(shù)據(jù)序列；多重性是指系統(tǒng)性能瓶頸部件上處于同一執(zhí)行階段 的指令或數(shù)據(jù)的最大可能個(gè)數(shù)。因而，把計(jì)算機(jī)系統(tǒng)分成四類。它們是：?jiǎn)沃噶盍鲉螖?shù)據(jù)流(Single Instruction Stream Single Data Stream 簡(jiǎn)稱 SISD)，單指令流多數(shù)據(jù)流系統(tǒng)(Single Instruction Stream Multi pie Data Stream簡(jiǎn)稱 SIMD )，多指令流單數(shù)據(jù)流系統(tǒng)(M

2、ulti pie Instruction Stream Multi pie Data Stream 簡(jiǎn)稱 MISD )和多指令流多數(shù)據(jù)流系統(tǒng)( Mult ip le Instruction Multi ple Data 簡(jiǎn)稱 MIMD )。Single Instruction Multi pie簡(jiǎn)稱MIMD )。在SIMD系統(tǒng)n2個(gè)處理機(jī)組成的并行計(jì)由多臺(tái)計(jì)算機(jī)所組成的計(jì)算機(jī)系統(tǒng)可以分為兩大類：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流系統(tǒng)(Data 簡(jiǎn)稱 SIMD )和多指令流多數(shù)據(jù)流系統(tǒng)( Multi pie Instruction Multi pie Data 中各處理機(jī)在同一時(shí)間執(zhí)行同一條指令，但是各處理機(jī)處理

3、的數(shù)據(jù)卻不同。例如由 算機(jī)系統(tǒng)就是一種 SIMD系統(tǒng)。它計(jì)算兩個(gè)n n矩陣A和B之加法C = A + B，其中A = a i, j，B = bi, j和C = ci, j，ci, j = ai, j + bi, j (1 i, j n)。在MIMD系統(tǒng)中各處理機(jī)獨(dú)立地執(zhí)行各自指令流來(lái)處理多個(gè)數(shù)據(jù)流。各處 理機(jī)通過(guò)通信來(lái)協(xié)同工作。分布式計(jì)算機(jī)系統(tǒng)( Distributed Computing System)是屬于MIMD多機(jī)系統(tǒng)的一 種新形式，是計(jì)算機(jī)網(wǎng)絡(luò)的高級(jí)發(fā)展階段。它是由多個(gè)分散的計(jì)算機(jī)經(jīng)互連網(wǎng)絡(luò)連接而成的計(jì)算機(jī)系統(tǒng)。其 中各個(gè)資源單位(物理的或邏輯的)既相互協(xié)同又高度自治，能在全系統(tǒng)范圍

4、內(nèi)實(shí)現(xiàn)資源管理，動(dòng)態(tài)地進(jìn)行 任務(wù)分配或功能分配，并且能夠并行地運(yùn)行分布式程序。圖5-1分布式系統(tǒng)的體系結(jié)構(gòu)分布式計(jì)算機(jī)系統(tǒng)是由若干非共享內(nèi)存和時(shí)鐘的計(jì)算機(jī)組成，它們通過(guò)一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)彼此交換消息; 并且每臺(tái)計(jì)算機(jī)由自己的內(nèi)存和運(yùn)行自己的操作系統(tǒng)，如圖5-1所示。分布式計(jì)算機(jī)系統(tǒng)強(qiáng)調(diào)資源、任務(wù)、功能和控制的全面分布。就資源分布而言，既包括處理機(jī)、輸入輸出設(shè)備、通信接口和輔助存儲(chǔ)器等物理資源，也包括進(jìn)程、文件、目錄、表和數(shù)據(jù)庫(kù)等邏輯資源。它們分 布于物理上分散的若干場(chǎng)點(diǎn)中。而各場(chǎng)點(diǎn)經(jīng)互連網(wǎng)絡(luò)連接，彼此通信構(gòu)成統(tǒng)一的計(jì)算機(jī)系統(tǒng)。分布式計(jì)算機(jī)系統(tǒng)的工作方式也是分布的。 各場(chǎng)點(diǎn)可以根據(jù)下面兩個(gè)原則進(jìn)行分

5、工： 一種是把一個(gè)任務(wù) 分解成多個(gè)可以并行執(zhí)行的子任務(wù)，分配給各場(chǎng)點(diǎn)協(xié)同完成。這種方式稱為任務(wù)分布。另一種是把系統(tǒng)的總 的功能劃分成若干子功能，分配給各場(chǎng)點(diǎn)分別承擔(dān)。這種方式稱為功能分布。不論是任務(wù)分布還是功能分布， 分配方案均可依處理內(nèi)容動(dòng)態(tài)地確定。在分布式操作系統(tǒng)控制下，各個(gè)場(chǎng)點(diǎn)能夠較均等地分擔(dān)控制功能，獨(dú) 立地發(fā)揮自身的控制作用，但是它們又能相互配合，在彼此通信協(xié)調(diào)的基礎(chǔ)上實(shí)現(xiàn)全系統(tǒng)的全局管理。§ 1. 分布式計(jì)算機(jī)系統(tǒng)的特點(diǎn)分布式計(jì)算機(jī)系統(tǒng)具有如下明顯的主要特點(diǎn)：它們經(jīng)互連網(wǎng)絡(luò)連接成一個(gè)單一系結(jié)構(gòu)模塊性： 分布式計(jì)算機(jī)系統(tǒng)的資源單位形成相對(duì)獨(dú)立的模塊， 統(tǒng)。模塊在一定范圍內(nèi)的

6、增減或替換不影響系統(tǒng)的整體性。資源分散性(distributed )：系統(tǒng)資源分布于物理上分散的若干場(chǎng)點(diǎn)中。在對(duì)用戶透明基礎(chǔ)上實(shí)現(xiàn)資 源共享，使單個(gè)用戶的可用資源成倍地增長(zhǎng)。協(xié)同自治性(autonomous)：系統(tǒng)資源的操作是高度自治的，既不存在全系統(tǒng)的主/從控制關(guān)系，又能利用處理局部化的原則以減少各場(chǎng)點(diǎn)間的通信量。一起解決同一個(gè)問(wèn)題。工作并行性(parallesm):分布式計(jì)算機(jī)系統(tǒng)中分散的資源單位可以相互協(xié)作， 在分布式操作系統(tǒng)控制下，實(shí)現(xiàn)按任務(wù)資源重復(fù)或按功能時(shí)間重疊等不同形式的并行性。系統(tǒng)透明性(transparency):系統(tǒng)對(duì)于用戶是透明的。用戶可以像單機(jī)系統(tǒng)一樣使用分布式計(jì)算機(jī)系

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

8、的一個(gè)方向。一些專家亦斷言： 將來(lái)任何一個(gè)有效的計(jì)算機(jī)系統(tǒng)，都將是一個(gè)分布式系統(tǒng)。§ 2. 分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)耦合度是系統(tǒng)模塊之間分布式計(jì)算機(jī)系統(tǒng)的體系結(jié)構(gòu)可用處理機(jī)之間的耦合度為主要標(biāo)志來(lái)加以描述。互連的緊密程度，它是數(shù)據(jù)傳輸率、響應(yīng)時(shí)間、并行處理能力等性能指標(biāo)的綜合反映，主要取決于所選用的 互連拓?fù)浣Y(jié)構(gòu)和通信鏈路的類型。運(yùn)程計(jì)算機(jī)網(wǎng)絡(luò)采用串行數(shù)據(jù)傳輸，且受復(fù)雜的通信協(xié)議制約，故其耦合度最低，屬于松散耦合系統(tǒng)(loosely couple)。如果一個(gè)大的計(jì)算被分解成位于松散耦合系統(tǒng)上的一個(gè)進(jìn)程集合，則此計(jì)算稱為大粒度 (large grained)并行計(jì)算。具有共享內(nèi)存的多

9、處理機(jī)系統(tǒng)有著很高的并行處理速度，固其耦合度最高，屬于緊密耦合系統(tǒng)(loosely couple)。分布式計(jì)算機(jī)系統(tǒng)是兩者發(fā)展的產(chǎn)物，它既考慮地理上分散環(huán)境的限制， 又滿足一定的并行性的要求，所以其耦合度屬于兩者之間，一般屬于中等耦合系統(tǒng)。按地理環(huán)境衡量耦合度，分布式計(jì)算機(jī)系統(tǒng)可以分為機(jī)體內(nèi)系統(tǒng)、建筑物內(nèi)系統(tǒng)、建筑物間系統(tǒng)和不同 地理范圍的區(qū)域系統(tǒng)等，它們的耦合度依次由高到低。按應(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)所完成的 工作。第二種是面向管理信息的

10、分布式數(shù)據(jù)處理系統(tǒng)。耦合度可以適當(dāng)降低。第三種是面向過(guò)程控制的分布 式計(jì)算機(jī)控制系統(tǒng)。耦合度要求適中，當(dāng)然對(duì)于某些實(shí)時(shí)應(yīng)用，其耦合度的要求可能很高。分布式計(jì)算機(jī)系統(tǒng)可看作是并行處理系統(tǒng)的一種常見形式和特例。Tanenbaum和Renesse將分布式系統(tǒng)分成三類：小型機(jī)類型(minicomputer model):在小型機(jī)類型中，分布式系統(tǒng)由若干小型機(jī)組成(例如， 個(gè)計(jì)算機(jī)支持多個(gè)用戶并且提供訪問(wèn)遠(yuǎn)程資源。處理機(jī)個(gè)數(shù)和用戶數(shù)之比通常小于工作站類型 (workstation model) ：在工作站類型中， 分布式系統(tǒng)由直到幾百臺(tái)工作站組成。VAX) 。每1。每個(gè)用戶有一臺(tái)工作站完成用戶的任務(wù)。藉

11、助于分布式文件系統(tǒng)，用戶可以訪問(wèn)任何數(shù)據(jù)，而不管其位置。處理機(jī)個(gè)數(shù)和 用戶數(shù)之比通常等于 1。 Athena 和 Andrew 是其例子。處理機(jī)池類型(Processor pool model):在處理機(jī)池類型中，按照用戶的需求分配一個(gè)或多個(gè)處理機(jī)給用戶。一旦完成任務(wù)它們返回處理機(jī)池等待新的分配。處理機(jī)個(gè)數(shù)和用戶數(shù)之比通常大于1。Amoeba是一個(gè)工作站和處理機(jī)池類型組合的試驗(yàn)系統(tǒng)。從用分布式操作系統(tǒng)是由一個(gè)通信網(wǎng)絡(luò)連接的若干自治的計(jì)算機(jī)所組成的分布式計(jì)算系統(tǒng)的操作系統(tǒng)。 戶觀點(diǎn)看分布式操作系統(tǒng)是由一個(gè)虛擬單機(jī)組成。第2節(jié) 分 布式系統(tǒng)的拓?fù)浣Y(jié)構(gòu)分布式系統(tǒng)中的場(chǎng)點(diǎn)可用不同的方式將它們從物理上連

12、結(jié)起來(lái)，每種方式都有優(yōu)缺點(diǎn)。下面簡(jiǎn)單討論幾種常用的連結(jié)方式并按以下標(biāo)準(zhǔn)來(lái)比較它們的性能：基本開銷：連結(jié)系統(tǒng)中的各個(gè)場(chǎng)點(diǎn)要多少花費(fèi)？通信開銷：從場(chǎng)點(diǎn) A發(fā)送消息到場(chǎng)點(diǎn)B需要多少時(shí)間?可靠性：若系統(tǒng)中的場(chǎng)點(diǎn)或通信鏈路故障，余下的場(chǎng)點(diǎn)是否仍能彼此通信？A 到結(jié)點(diǎn) B 的連線為方便討論，我們把各種拓?fù)浣Y(jié)構(gòu)用圖形表示出，其中的結(jié)點(diǎn)對(duì)應(yīng)于場(chǎng)點(diǎn)，從結(jié)點(diǎn) 對(duì)應(yīng)于這兩個(gè)場(chǎng)點(diǎn)之間的直接鏈路。定義 5-1 一個(gè)系統(tǒng)稱之為分割的( partition )，如果它已被分劃成兩個(gè)或多個(gè)子系統(tǒng)，且不同子系統(tǒng)中的場(chǎng) 點(diǎn)已不再能彼此通信。§ 1. 全互連結(jié)構(gòu)在一個(gè)全互連結(jié)構(gòu)中，每個(gè)場(chǎng)點(diǎn)都直接與系統(tǒng)中所有其它的場(chǎng)點(diǎn)相連

13、(圖5-2)，這種構(gòu)形的基本開銷很高，因?yàn)槊繉?duì)場(chǎng)點(diǎn)之間都必須有一條直接通信鏈路。但在這種環(huán)境中，場(chǎng)點(diǎn)間的消息轉(zhuǎn)移非常快，因?yàn)槿?何兩場(chǎng)點(diǎn)間的消息轉(zhuǎn)移只需要經(jīng)由一條通信線路就可直達(dá)。此外，這種結(jié)構(gòu)是很可靠的，因?yàn)橹挥性谙喈?dāng)多 的通信鍵路故障的情況下，才可能分割該系統(tǒng)。那么任何單條圖5-2全互連拓?fù)浣Y(jié)構(gòu)§ 2.部分互連結(jié)構(gòu)在一個(gè)部分互連結(jié)構(gòu)中，有些場(chǎng)點(diǎn)間存在直接通信鏈路，但有些則沒(méi)有，如圖5-3所示。因此這種構(gòu)形的基本開銷比全互連結(jié)構(gòu)要低，但場(chǎng)點(diǎn)間的消息轉(zhuǎn)移可能經(jīng)由若干中間的場(chǎng)點(diǎn)，以致延緩了通信速度。例如， 在圖5-3中，從場(chǎng)點(diǎn).發(fā)送一消息到場(chǎng)點(diǎn)必須經(jīng)由場(chǎng)點(diǎn)和。此外，部分互連系統(tǒng)也不如全

14、互連系統(tǒng)可靠，因?yàn)槠渲械囊粋€(gè)通信鍵路故障就可能分割該系統(tǒng)。例如， 在圖5-3中，若從場(chǎng)點(diǎn)到場(chǎng)點(diǎn)的通信鏈路故障，則該系統(tǒng)便分割成兩個(gè)子系統(tǒng)，一個(gè)包括，； 一個(gè)包括和，而且這兩個(gè)子系統(tǒng)中的場(chǎng)點(diǎn)彼此不再能通信。為了減少這種情況發(fā)生，通常讓每個(gè)場(chǎng)點(diǎn)要 少與另外兩個(gè)場(chǎng)點(diǎn)連給。例如，如果我們?cè)趫D5-3中增加一條從場(chǎng)點(diǎn)到場(chǎng)點(diǎn)的通信鍵路，通信鏈路故障都不可能導(dǎo)致對(duì)該系統(tǒng)的分割。§ 3.層次結(jié)構(gòu)層次結(jié)構(gòu)中的各場(chǎng)點(diǎn)組織成樹形結(jié)構(gòu)。如圖5-4所示，其中，除根以外每一場(chǎng)點(diǎn)有一個(gè)唯一的父親和若干個(gè)（或0個(gè)）孩子。這種構(gòu)形的基本開銷一般小于部分互連結(jié)構(gòu)。在 這種環(huán)境中，父子之間可直接通信，孩子之間只能經(jīng)由它們

15、的共同父親進(jìn)行通信，從某個(gè)兄弟向另一兄弟發(fā)送消息，須 先向上發(fā)送給它們的父親，然后再由其父親向下發(fā)送給相應(yīng) 的兄弟。類似地，堂兄姐妹之間只能經(jīng)由其共同的祖父進(jìn)行 通信。除葉結(jié)點(diǎn)若父場(chǎng)點(diǎn)故障，那么，它的孩子們彼此就不能相互通信，也不能與其它進(jìn)程通信。一般而言, 外，任何中間結(jié)點(diǎn)故障都可能將這種結(jié)構(gòu)分割成若干不相交的子樹。§ 4.星形結(jié)構(gòu)在星形結(jié)構(gòu)中，系統(tǒng)中的場(chǎng)點(diǎn)之一與系統(tǒng)中所有其余場(chǎng)點(diǎn)相連，其它的 場(chǎng)點(diǎn)之間彼此不直接相連，見圖5-5。這種構(gòu)形的基本開銷是場(chǎng)點(diǎn)個(gè)數(shù)的線性函數(shù)，其通信速度看起來(lái)也不會(huì)很慢，因?yàn)閺膱?chǎng)點(diǎn)向場(chǎng)點(diǎn)轉(zhuǎn)移消息至多需 要兩次轉(zhuǎn)接，即從到中央場(chǎng)點(diǎn)，再?gòu)闹醒雸?chǎng)點(diǎn)到，但這種通信

16、速度卻是難 以預(yù)測(cè)的，因?yàn)橹醒雸?chǎng)點(diǎn)可能變成瓶頸，雖然轉(zhuǎn)移消息所需轉(zhuǎn)接的次數(shù)不多， 但轉(zhuǎn)移消息所花的時(shí)間可能不少。在一些星形結(jié)構(gòu)系統(tǒng)中，中央場(chǎng)點(diǎn)完全擔(dān)負(fù)圖5-5星形結(jié)構(gòu)著消息轉(zhuǎn)接的任務(wù)。如果中央場(chǎng)點(diǎn)故障，那么該系統(tǒng)就完全地被分割了。§ 5.環(huán)形結(jié)構(gòu)在環(huán)形結(jié)構(gòu)中，每個(gè)場(chǎng)點(diǎn)物理上恰好與另外兩個(gè)場(chǎng)點(diǎn)相連，見圖5-6。這樣的環(huán)形結(jié)構(gòu)可以是單向的，也可以是雙向的。在單向環(huán)結(jié)構(gòu)中，其中的一個(gè)場(chǎng)點(diǎn)只能給它的鄰近場(chǎng)點(diǎn)之一直接轉(zhuǎn)移消息，且所有的場(chǎng)點(diǎn) 必須按相同的方向轉(zhuǎn)移消息。在雙向環(huán)結(jié)構(gòu)中，其中的一個(gè)場(chǎng)點(diǎn)可將信息轉(zhuǎn)移給它的兩個(gè)鄰近場(chǎng)點(diǎn)。這種結(jié) 構(gòu)的基本開銷不會(huì)很高，但通信代價(jià)可能較高，因?yàn)閺囊粋€(gè)場(chǎng)點(diǎn)向另

17、一場(chǎng)點(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ò)中場(chǎng)點(diǎn)的個(gè)數(shù)。圖5-7多存取總線結(jié)構(gòu)圖5-6環(huán)形結(jié)構(gòu)在雙向環(huán)形結(jié)構(gòu)中，其中兩條通信鏈路故障就可能導(dǎo)致分割整個(gè)系統(tǒng)。在單向環(huán)形結(jié)構(gòu)中，單個(gè)場(chǎng)點(diǎn)或 單條通信鏈路故障，就可能分割整個(gè)系統(tǒng)。一種補(bǔ)救的辦法是通過(guò)提供雙通信鏈路來(lái)擴(kuò)充這種結(jié)構(gòu)，但這顯 然會(huì)增加基本開銷，如圖5-6(b)所示。§ 6.多存取總線結(jié)構(gòu)在多存取總線結(jié)構(gòu)(簡(jiǎn)稱總線結(jié)構(gòu))中，有一條共享的通信鏈路(即總線)。系統(tǒng)中所有的場(chǎng)點(diǎn)都直接與這條通信鏈路相連，它可以組織成直線狀，見圖5

18、-7(a)，也可以組織成環(huán)狀，如圖5-7(b)所示，其中的場(chǎng)點(diǎn)可以經(jīng)由這條總線彼此直接進(jìn)行通信。這類結(jié)構(gòu)的基本開銷是場(chǎng)點(diǎn)個(gè)數(shù)的線性函數(shù)，通信代價(jià)也很低，除非這條 總線變成了瓶頸。這類結(jié)構(gòu)類似于帶有一個(gè)中央場(chǎng)點(diǎn)的星形結(jié)構(gòu)，其中某個(gè)場(chǎng)點(diǎn)故障不會(huì)影響其它場(chǎng)點(diǎn)間的 通信，但是，若這條總線故障，那么該結(jié)構(gòu)就完全地被分割了。(a)§ 7.環(huán)-星形結(jié)構(gòu)環(huán)-星形結(jié)構(gòu)由環(huán)、星型結(jié)構(gòu)疊加而成,其優(yōu)缺點(diǎn)介于星形和環(huán)形結(jié)構(gòu)之間,見圖5-8。§ 8.有規(guī)則結(jié)構(gòu)有規(guī)則結(jié)構(gòu)（見圖 5-9）中的每 個(gè)場(chǎng)點(diǎn)都與它相鄰的上、下、左、右 場(chǎng)點(diǎn)相連，因而具有高性能、高速度、 和高可靠性。不過(guò)，這種結(jié)構(gòu)比較復(fù) 雜，

19、且一般要求各場(chǎng)點(diǎn)是完全一致的， 構(gòu)造這種系統(tǒng)的費(fèi)用也較高。圖5-8環(huán)-星形結(jié)構(gòu)§ 9.不規(guī)則結(jié)構(gòu)不規(guī)則結(jié)構(gòu)中的各場(chǎng)點(diǎn)間的連接關(guān)系無(wú)一定規(guī)則可依，其優(yōu)點(diǎn)是：可 隨意增加不同類型的結(jié)點(diǎn)，各結(jié)點(diǎn)互連起來(lái)也較方便，還可提供任意 冗余和重組能力；其缺點(diǎn)是運(yùn)行時(shí)需要較復(fù)雜的路徑選擇算法（見圖5-10 ）。§ 10.立方體互連結(jié)構(gòu)圖5-10不規(guī)則結(jié)構(gòu)立方體互連結(jié)構(gòu)又稱 n維立方體分布式網(wǎng)絡(luò)結(jié)構(gòu)。位于該立方體的角頂。立方體的每條邊把兩個(gè)場(chǎng)點(diǎn)連接起來(lái)， 它計(jì)算機(jī)相連。例如，n=3，n=4時(shí)立方體互連結(jié)構(gòu)如圖這種結(jié)構(gòu)把2n= N而每個(gè)場(chǎng)點(diǎn)則有5-11所示，其中,個(gè)計(jì)算機(jī)互連起來(lái)，各計(jì)算機(jī)分別n

20、個(gè)全雙向通路把它和 n個(gè)其 n為立方體的維數(shù)。圖5-13局域網(wǎng)圖5-12遠(yuǎn)程網(wǎng)中的通信處理機(jī)此外，還有交叉開關(guān)網(wǎng)、樹形網(wǎng)、網(wǎng)狀網(wǎng)、立方體網(wǎng)和超立方體等。n = 4N = 16圖5-11立方體互連結(jié)構(gòu)第3節(jié)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)分為兩大類：遠(yuǎn)程網(wǎng)（全局網(wǎng)）和局域網(wǎng)。兩者的主要區(qū)別在于它的所處的地理區(qū)域的大小 不同。遠(yuǎn)程網(wǎng)（remote network）由分散在一個(gè)較大地理區(qū)域（如全國(guó)、甚至全球）的若干自治的處理機(jī)組成， 而局域網(wǎng)（local area network簡(jiǎn)記為L(zhǎng)AN）則由分散在一個(gè)較小的地理區(qū)域（如一座樓房或若干相鄰的建筑物）的若干處理機(jī)組成，這種不同點(diǎn)隱含了通信網(wǎng)絡(luò)的速度和可靠性中的

21、主要變異并反映在操作系統(tǒng)的設(shè)計(jì)中。§ 1.運(yùn)程網(wǎng)遠(yuǎn)程網(wǎng)又稱廣域網(wǎng)（wide area network簡(jiǎn)記為 WAN ）。它的研究工作始于 60年代末期。設(shè)計(jì)和研制的 第一個(gè)網(wǎng)是ARPA網(wǎng)，它的設(shè)計(jì)工作始于1968年。它已從最初只含四個(gè)場(chǎng)點(diǎn)的試驗(yàn)性網(wǎng)絡(luò)模型發(fā)展成全美國(guó) 范圍乃至美國(guó)范圍之外的網(wǎng)絡(luò)系統(tǒng)，即我們現(xiàn)在經(jīng)常講Internet?，F(xiàn)今，若干商用遠(yuǎn)程網(wǎng)已投放市場(chǎng)，如美國(guó)的Telenet，加拿大的Datapac系統(tǒng)等，這些網(wǎng)絡(luò)給它們的用戶提供了使用網(wǎng)絡(luò)中各種軟硬件資源的能力。由于遠(yuǎn)程網(wǎng)中的場(chǎng)點(diǎn)是物理分散在一個(gè)較大的地理區(qū)域上，因此，其中的通信線路由于種種原因會(huì)相當(dāng)慢且不那么可靠。一些典

22、型的通信線路是電話線、微波線和衛(wèi)星通信頻道。這些通信線路是由特殊的通信處 理機(jī)cp （見圖5-12）控制的，通信處理機(jī)負(fù)責(zé)定義一種接口，網(wǎng)絡(luò)中的各場(chǎng)點(diǎn)通過(guò)這種接口進(jìn)行通信，相互 轉(zhuǎn)移信息。現(xiàn)以ARPA網(wǎng)為例來(lái)討論有關(guān)問(wèn)題。該網(wǎng)絡(luò)提供了在地理上分散的各場(chǎng)點(diǎn)（稱為主機(jī)host能彼此通信的能力，這些host在類型、速度、字長(zhǎng)、操作系統(tǒng)等方面都可以不同。每個(gè)host計(jì)算機(jī)通過(guò)一個(gè)本地小型機(jī)（稱為接口消息處理機(jī)IMP）連到網(wǎng)絡(luò)上。這個(gè)完整的網(wǎng)絡(luò)系統(tǒng)則由這些IPM通過(guò)寬帶通信線（50千位/秒）互連而成，每個(gè)IMP可以編程存放消息并向鄰近的IMP轉(zhuǎn)移消息，當(dāng)一個(gè)host轉(zhuǎn)移一條消息到它的局部 IMP時(shí)，該消

23、息的前32位包含目的host的地址，這條消息通過(guò)網(wǎng)絡(luò)從IMP轉(zhuǎn)移給另一 IMP直至最終到達(dá)的它目的IMP。然后，由目的IMP將此消息轉(zhuǎn)移給目的hosto§ 2.局域網(wǎng)H用戶進(jìn)程？ 2I主機(jī)操祜系統(tǒng)I局域網(wǎng)（LAN ）早在70年代初就開始研制了。它通常設(shè)計(jì)成覆蓋一個(gè)較少的地理區(qū)域（如一幢樓房或 若干相鄰的建筑），而且一般在辦公室類型的環(huán)境中使用，由于這類系統(tǒng)中的所有場(chǎng)點(diǎn)彼此比較接近，因此 與遠(yuǎn)程網(wǎng)相比，其中的通信線路速度較快，而且出錯(cuò)率較 低。最常用的通信線路是雙絞線，寬帶同軸電纜，光纖等，最常用的的結(jié)構(gòu)是星形、環(huán)形和總線形等。典型的LAN可由若干不同的微型機(jī)，各種共享的外 圍設(shè)備（如

24、激光打印機(jī)和磁盤）、工作站，一個(gè)或多個(gè)網(wǎng) 關(guān)（它們是用于訪問(wèn)其它網(wǎng)絡(luò)的一些特定處理機(jī)）組成（見網(wǎng)紹主機(jī)hast|CPH'CPCPCP通信處理機(jī)工ftttfl*CFUCPUCPU1網(wǎng)給 主機(jī)（host）H用戶進(jìn)程莊機(jī)操祜系統(tǒng)I圖5-13）o以太網(wǎng)（Ethernet）是用于構(gòu)造LAN的常用結(jié) 構(gòu)。這種通信介質(zhì)是一條帶有沖突檢測(cè)手段的多存取同軸 電纜。網(wǎng)絡(luò)中的各場(chǎng)點(diǎn)間的消息是以消息包形式轉(zhuǎn)移的， 因?yàn)闆](méi)有中央控制機(jī)，所以很容易將新的場(chǎng)點(diǎn)加到網(wǎng)絡(luò) 中。局域網(wǎng)中通信線路傳輸速度較高，一般在10Mbit/s （每秒10兆位）左右，高速以太網(wǎng)可以達(dá)到 100Mbit/s以上，千兆以太網(wǎng)可以達(dá)到1Gb

25、it/s以上。傳輸距離在 0.110km。常用的局域網(wǎng)有共享式和交換式以太網(wǎng)，光纖分布數(shù)字接口（ FDDI ）網(wǎng)，異步傳輸模式（ATM ）網(wǎng)，Novell網(wǎng)，3COM網(wǎng)，Omninet，王安網(wǎng)，PLANSeries 網(wǎng)和 PCnet 等。§ 3.網(wǎng)絡(luò)分層結(jié)構(gòu)及通信協(xié)議計(jì)算機(jī)網(wǎng)絡(luò)的功能可統(tǒng)一用分層結(jié)構(gòu)（hierarchy）來(lái)表示，其內(nèi)核是物理信道，由內(nèi)向外（或從低到高）下層的功能是5-14 ）。各結(jié)點(diǎn)同等功interface）。由于各層依次分為物理層（physic layer）、數(shù)據(jù)鏈路（data link ）層、網(wǎng)絡(luò)（network ）層、傳輸（trans port）層、 會(huì)話（ss

26、esion）層、表示（representation）層和應(yīng)用（application ）層。各層的功能相對(duì)獨(dú)立， 上一層的基礎(chǔ)，且一般僅相鄰層間有接口關(guān)系，以便于網(wǎng)絡(luò)結(jié)點(diǎn)及整個(gè)網(wǎng)絡(luò)的設(shè)計(jì)和實(shí)現(xiàn)（見圖物理信道是傳輸電信號(hào)的媒介或通路。各個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)具有上述七個(gè)功能層或其中一部分。能層之間的通信規(guī)則和約定稱為協(xié)議（Protocol ），相鄰層間的通信規(guī)則和約定稱為接口（存在多個(gè)層次，相應(yīng)地就有多層協(xié)議和多層之間的接口。物理層控制網(wǎng)絡(luò)結(jié)點(diǎn)與物理信道的物理連接，物理層協(xié)議規(guī)定了與建立、維持和斷開物理信道有關(guān)的特性，保證在相鄰結(jié)點(diǎn)間能夠正確地進(jìn)行比特的發(fā)送和接收。數(shù)據(jù)鏈路層協(xié)議保差錯(cuò)控制、數(shù)據(jù)鏈路層是在物

27、理信道上建立的，具有一定信息傳輸格式和傳輸控制功能的信道。證數(shù)據(jù)塊從數(shù)據(jù)鏈路的一端正確地傳送至另一端。為此，這一層協(xié)議包含數(shù)據(jù)塊的形成和識(shí)別、 流量控制等通信控制方法。擁擠控制、差網(wǎng)絡(luò)層控制數(shù)據(jù)塊穿越網(wǎng)絡(luò)的活動(dòng)。網(wǎng)絡(luò)層協(xié)議規(guī)定數(shù)據(jù)塊格式、路徑選擇、流量控制、 錯(cuò)控制等方法。以上三層實(shí)現(xiàn)信息傳輸功能，是一切網(wǎng)絡(luò)結(jié)點(diǎn)都應(yīng)具備的計(jì)算杠Ar應(yīng)用JB門應(yīng)用S6表示層占會(huì)話啟心傳輔JB中維結(jié)點(diǎn)3網(wǎng)終層+334f3網(wǎng)絡(luò)層?數(shù)據(jù)鏈路層+卡?4?數(shù)據(jù)鏈路Jg1暢毘層*114«1物理層圖5-14計(jì)算機(jī)網(wǎng)絡(luò)的分層結(jié)構(gòu)傳輸層和會(huì)話層是訪問(wèn)結(jié)點(diǎn)才具有的功能。有些計(jì)算機(jī)網(wǎng)絡(luò)把這兩層合并為一層。在兩個(gè)訪問(wèn)結(jié)點(diǎn)之間

28、 的邏輯信道上傳送的數(shù)據(jù)塊，穿越網(wǎng)絡(luò)層后由傳輸層進(jìn)入信息處理部分，傳輸層的功能側(cè)重于用戶進(jìn)程之間交換的數(shù)據(jù)如何可靠、經(jīng)濟(jì)地轉(zhuǎn)移；會(huì)話層則側(cè)重于用戶功能的實(shí)現(xiàn)，如確認(rèn)對(duì)方是否有權(quán)參加會(huì)晤，以及 對(duì)進(jìn)程間的對(duì)話進(jìn)行控制和管理。表示層控制與數(shù)據(jù)表示有關(guān)的功能，包括字符集轉(zhuǎn)換、數(shù)據(jù)的壓縮與恢復(fù)、 數(shù)據(jù)的加密與破譯、 虛實(shí)終端間的轉(zhuǎn)換等網(wǎng)絡(luò)服務(wù)功能。應(yīng)用層對(duì)用戶進(jìn)程不僅提供與信息轉(zhuǎn)移有關(guān)的服務(wù)， 還提供系統(tǒng)管理和應(yīng)用管理，如網(wǎng)絡(luò)資源的實(shí)際分布，將信息處理作業(yè)自動(dòng)分散到網(wǎng)絡(luò)中若干臺(tái)計(jì)算機(jī)上執(zhí) 行，對(duì)分布式數(shù)據(jù)庫(kù)自動(dòng)進(jìn)行存取等。以上四層完成與信息處理有關(guān)的服務(wù)功能。網(wǎng)絡(luò)分層和網(wǎng)絡(luò)協(xié)議的集合稱為網(wǎng)絡(luò)體系結(jié)構(gòu)。

29、 在各層網(wǎng)絡(luò)協(xié)議中較低層的協(xié)議通常用硬件實(shí)現(xiàn)， 或由 硬件和軟件共同實(shí)現(xiàn)， 而較高層協(xié)議則一般用軟件實(shí)現(xiàn)。所有用于實(shí)現(xiàn)各層網(wǎng)絡(luò)協(xié)議的軟件均稱為網(wǎng)絡(luò)軟件。事實(shí)上，圖 5-14是國(guó)際標(biāo)準(zhǔn)化組織（ISO）制定的用于計(jì)算機(jī)網(wǎng)絡(luò)的開放系統(tǒng)互連（ Open SystemInterconnection簡(jiǎn)記為OSI）標(biāo)準(zhǔn)七層通信協(xié)議結(jié)構(gòu)圖。不難看出， ISO 的 OSI 七層協(xié)議并不能滿足資源共享和分布計(jì)算的要求， 因?yàn)樗推邔訁f(xié)議只是些功能協(xié) 議，即只實(shí)現(xiàn)了某幾種功能，也不能實(shí)現(xiàn)任務(wù)的分解、負(fù)載的平衡及其它動(dòng)態(tài)調(diào)度，因而，需要在網(wǎng)絡(luò)基礎(chǔ) 上建立計(jì)算機(jī)網(wǎng)絡(luò)操作系統(tǒng)。§ 4. 微機(jī)局域網(wǎng)一般說(shuō)來(lái)，單臺(tái)微

30、機(jī)的性能是不夠強(qiáng)的，因而，人們往往把多臺(tái)微機(jī)連接成較大的系統(tǒng)以共享資源。這 種用網(wǎng)絡(luò)把多臺(tái)微機(jī)連接起來(lái)而構(gòu)成的系統(tǒng)便稱為微機(jī)局域網(wǎng)。微機(jī)局域網(wǎng)既保持了微機(jī)體積小、價(jià)格低、 使用方便靈活的特點(diǎn)，又彌補(bǔ)了單臺(tái)微機(jī)資源有限、性能不夠強(qiáng)的不足，從而引起人們高度的重視并迅速發(fā) 展起來(lái)。在選用一個(gè)微機(jī)局域網(wǎng)時(shí)，應(yīng)主要注意以下幾方面的問(wèn)題。使用環(huán)境 工作站分布的地理區(qū)域有多大； 安裝工作站的數(shù)量有多少； 運(yùn)行環(huán)境的抗干擾和屏蔽性能如何。分布式操作系統(tǒng)（Distributed Op erating System，縮寫為DOS）是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。 它在這種多機(jī)環(huán)境下，負(fù)責(zé)控制和管理以協(xié)同方式工

31、作的多種系統(tǒng)（的物理和邏輯）資源，進(jìn)程的同步和執(zhí) 行，處理機(jī)間的通信、調(diào)度等控制事務(wù)，自動(dòng)實(shí)行全系統(tǒng)范圍內(nèi)的任務(wù)分配和負(fù)載平衡并具有高度并行性的 一種高級(jí)軟件系統(tǒng)。它與單機(jī)系統(tǒng)（集中式操作系統(tǒng)）以及網(wǎng)絡(luò)操作系統(tǒng)都有不同程度的區(qū)別，其復(fù)雜程度 也明顯高于它們。分布式操作系統(tǒng)和單機(jī)操作系統(tǒng)的主要區(qū)別在于進(jìn)程管理、資源管理和系統(tǒng)結(jié)構(gòu)。§ 5. 多機(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ò)充而成。但是，它在管理和利用

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

33、需外來(lái)干預(yù)；整個(gè)系統(tǒng)的靈活性也較差。獨(dú)立式 獨(dú)立式操作系統(tǒng)的主要特點(diǎn)是：某些程序所使用的子程序必須是再入式或復(fù)制 系統(tǒng)中的每臺(tái)處理機(jī)的管理程序僅為自身的需要服務(wù)。品，以便為每臺(tái)處理機(jī)提供各自單獨(dú)的副本。 各臺(tái)處理機(jī)借助公用信息相互聯(lián)系。整個(gè)系統(tǒng)除了公用信息外， 處理機(jī)的管理程序還可管理和使用各自的專用信息，因此，其信息的存取控制比主從式復(fù)雜。 系統(tǒng)中的每臺(tái)處理機(jī)各自都有一套顯示設(shè)備、I / O 設(shè)備、文件、目錄等。分布式 可由多臺(tái)處理機(jī)同時(shí)執(zhí)行管理、控制和服務(wù)程序， 但“主處理機(jī)” 是浮動(dòng)的， 可由一臺(tái)切換為另臺(tái)。由于多臺(tái)處理機(jī)可同時(shí)執(zhí)行同一管理、控制和服務(wù)程序，因此，這些程序必須是再入式的。

34、 在這種操作系統(tǒng)的管理和控制下，整個(gè)系統(tǒng)中的所有資源單元均可獲較好的負(fù)載平衡。 當(dāng)服務(wù)請(qǐng)求發(fā)生沖突時(shí)，可根據(jù)固定的優(yōu)先級(jí)或動(dòng)態(tài)控制策略確定的優(yōu)先級(jí)予以解決。 當(dāng)系統(tǒng)中出現(xiàn)局部故障時(shí)，可通過(guò)自動(dòng)重構(gòu)，適度降級(jí)(graceful degradation)使用，或通過(guò)錯(cuò)誤恢復(fù)手段使系統(tǒng)繼續(xù)運(yùn)行，因而系統(tǒng)有較好的可用性和可靠性。§ 6. 設(shè)計(jì)分布式操作系統(tǒng)時(shí)應(yīng)考慮的問(wèn)題分布式操作系統(tǒng)是在分布式計(jì)算機(jī)系統(tǒng)環(huán)境下運(yùn)行的， 在這種多機(jī)環(huán)境下， 并行性不再只是宏觀上的概 念，而確已在微觀上也得到了實(shí)現(xiàn)。系統(tǒng)中各處理機(jī)不僅要執(zhí)行自身接收的任務(wù)，還可能相互聯(lián)系、請(qǐng)求服 務(wù)或封鎖，而所有這些都要通過(guò)通信機(jī)

35、制進(jìn)行，這種通信機(jī)制專門負(fù)責(zé)系統(tǒng)中各進(jìn)程及各處理機(jī)之間的相互 通信。因此，在設(shè)計(jì)分布式操作系統(tǒng)時(shí)應(yīng)注意考慮以下問(wèn)題：分布式操作系統(tǒng)是為分布式多機(jī)系統(tǒng)設(shè)計(jì)的， 因此， 它不僅對(duì)于在各場(chǎng)點(diǎn)上分別執(zhí)行的任務(wù)及相關(guān)的 資源負(fù)有管理和控制的職責(zé)，而且還要負(fù)責(zé)協(xié)調(diào)各場(chǎng)點(diǎn)間的交互關(guān)系。它不僅要保證在不同場(chǎng)點(diǎn)上執(zhí)行的進(jìn) 程彼此互不干擾并嚴(yán)格同步，而且還必須保證避免或妥善地解決各處理機(jī)對(duì)某些資源的競(jìng)爭(zhēng)所可能引起的死 鎖、饑餓及公正性等問(wèn)題。分布式操作系統(tǒng)的結(jié)構(gòu)本身也應(yīng)是分布式的，系統(tǒng)中的各場(chǎng)點(diǎn)都可包含該操作系統(tǒng)或其中的一部分。 一般把分布式操作系統(tǒng)劃分成若干不相交的并行模塊，并將它們分別指派給系統(tǒng)中的各場(chǎng)點(diǎn)，且

36、每個(gè)場(chǎng)點(diǎn)都 有一個(gè)局部操作系統(tǒng)的內(nèi)核模塊的副本。在系統(tǒng)運(yùn)行時(shí)，各場(chǎng)點(diǎn)間的邏輯關(guān)系是完全平等的。分布式操作系 統(tǒng)的模塊可以全部并行地在各場(chǎng)點(diǎn)上運(yùn)行，而控制流和數(shù)據(jù)流的移動(dòng)則在各場(chǎng)點(diǎn)上的局部操作系統(tǒng)的內(nèi)核模 塊的合作協(xié)調(diào)下進(jìn)行。分布式操作系統(tǒng)可劃分為高層和局部，劃分的原則是：局部操作系統(tǒng)。消息轉(zhuǎn)移等管理功能也劃歸為本場(chǎng)點(diǎn)局部操 屬于本機(jī)獨(dú)立運(yùn)行的基本管理功能劃歸為本場(chǎng)點(diǎn)（本機(jī)） 本場(chǎng)點(diǎn)（本機(jī)）與其它場(chǎng)點(diǎn)（它機(jī)）之間的通信、同步、 作系統(tǒng)。死鎖處理、錯(cuò)誤處理與系統(tǒng)重構(gòu)等及其它公 各場(chǎng)點(diǎn)間協(xié)調(diào)合作完成的功能，如任務(wù)分配、負(fù)載平衡、 共事務(wù)劃歸為高層操作系統(tǒng)。這種劃分使各場(chǎng)點(diǎn)在運(yùn)行中既有自治性，又能使系

37、統(tǒng)中各場(chǎng)點(diǎn)協(xié)調(diào)一致地進(jìn)行合作。 分布式操作系統(tǒng)的基本調(diào)度單位已不再是單機(jī)操作系統(tǒng)的進(jìn)程，而是一種任務(wù)隊(duì)列， 這種隊(duì)列是由位于多個(gè)場(chǎng)點(diǎn)上的并發(fā)進(jìn)程所組成的任何隊(duì)列。同一任務(wù)隊(duì)列中的諸并發(fā)進(jìn)程可分布在不同的場(chǎng)點(diǎn)上并行地執(zhí) 行；同一場(chǎng)點(diǎn)上也可執(zhí)行多個(gè)不同的任務(wù)隊(duì)列中的并發(fā)進(jìn)程。在緊密耦合的分布式系統(tǒng)中，理機(jī)共享存儲(chǔ)器和時(shí)鐘，通信是經(jīng)由共享存儲(chǔ)器進(jìn)行的，系統(tǒng)資源的耦合程度很高，因而需要專門的各種軟 件和硬件機(jī)制來(lái)解決沖突和競(jìng)爭(zhēng)等問(wèn)題。在松散耦合的分布式系統(tǒng)中，各處理機(jī)無(wú)共享存儲(chǔ)器和時(shí)鐘，而都 配有自己的本地資源，它們彼此之間經(jīng)由各種通信線路進(jìn)行通信。因此，分布式操作系統(tǒng)必須解決的主要問(wèn) 題是處理機(jī)以及

38、進(jìn)程之間的通信和同步。所以，多機(jī)系統(tǒng)的耦合方式不同，相應(yīng)的分布式操作系統(tǒng)所要解決 的主要問(wèn)題也不同。 在分布式系統(tǒng)中，需要提供一個(gè)支持資源共享的環(huán)境，把任務(wù)分解并分配到相應(yīng)的場(chǎng)點(diǎn)。若整個(gè)系統(tǒng) 由不同類型的處理機(jī)組成，由于每個(gè)處理機(jī)的處理能力及硬設(shè)備配置等方面都可能各具特點(diǎn)。因此，操作系 統(tǒng)應(yīng)該根據(jù)這些特點(diǎn)給處理機(jī)分配任務(wù)。若系統(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)。并且要包含適當(dāng)?shù)奶幚泶?/p>

39、施，如自 分布式操作系統(tǒng)必須具有探測(cè)任一處理機(jī)停機(jī)或發(fā)生故障的能力， 動(dòng)重構(gòu)，、降級(jí)使用和錯(cuò)誤恢復(fù)等。§ 7. 構(gòu)造分布式操作系統(tǒng)的途徑對(duì)于如何構(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ò)充式對(duì)現(xiàn)有的操作系統(tǒng)進(jìn)行修改和擴(kuò)充， 使之具有分布處理和通信的功能。 這種途徑通過(guò)盡量保持與現(xiàn)有操 作系統(tǒng)的相容性而使重新編寫

40、新軟件的工作量減到最少。而且存在一個(gè)與開發(fā)期間的新版本進(jìn)行比較的原有 工作版本，這就給我們提供了測(cè)試和比較新版本性能的基礎(chǔ)。這種途徑的不利之處是開發(fā)期間的某些決策由 于要考慮到如何與原有操作系統(tǒng)相容而不得不采取折衷方案。層次式 在現(xiàn)有操作系統(tǒng)和用戶之間增加一個(gè)層次以提供分布處理和通信功能。這類系統(tǒng)有點(diǎn)類似網(wǎng)絡(luò)操作系統(tǒng)，它具有前述兩種途徑的優(yōu)點(diǎn)且不必改動(dòng)現(xiàn)有的操作家統(tǒng),其不足之處在于所有對(duì)底層操作系統(tǒng)的引用由于必須經(jīng)由中間層而使系統(tǒng)性能受到了衰減，此外，還有不少局限性。利用這三種途徑構(gòu)造分布式操作系統(tǒng)的示意圖，見圖5-15。USERSDOSU3ER3DOSf USER、(U5ERUSERS )r

41、 USERS DOS/OSDOS/OS,1DOSD05I OS JL OS J從頭開始修改擴(kuò)充層吹式圖5-15構(gòu)造分布式操作系統(tǒng)的三種途徑第4節(jié)分布式操作系統(tǒng)的結(jié)構(gòu)模型分布式操作系統(tǒng)的結(jié)構(gòu)是指其整體邏輯結(jié)構(gòu)，主要有以下幾種：分布式操作系統(tǒng)內(nèi)核：各場(chǎng)點(diǎn)上都配有一個(gè)分布式操作系統(tǒng)內(nèi)核，它僅提供存儲(chǔ)管理、輔存管理、進(jìn) 程管理、進(jìn)程間的同步與通信等核心管理功能及相應(yīng)的操作原語(yǔ)。例如，Accent和V核就屬于這種結(jié)構(gòu)模型。集成式：集成式(integrated model )意指每個(gè)場(chǎng)點(diǎn)上運(yùn)行著一個(gè)比較完整或集成的高度可組合的標(biāo)準(zhǔn) 化的操作系統(tǒng)模塊集，該集包含相應(yīng)場(chǎng)點(diǎn)上所需要的幾乎所有的服務(wù)功能，決大多數(shù)

42、工作都是在本場(chǎng)點(diǎn)上完 成的。每個(gè)場(chǎng)點(diǎn)也可訪問(wèn)遠(yuǎn)程資源，即當(dāng)必要時(shí)才發(fā)生場(chǎng)點(diǎn)間的交叉訪問(wèn)。LOCUS等就是這種模型的例子。服務(wù)池模型和資源池模型。對(duì)于前者，系統(tǒng)中的所有服務(wù)功能都是由服務(wù) 命名服務(wù)類、終端服務(wù)類和通信服務(wù)類等。對(duì)于后者，系統(tǒng)管理著一個(gè) 文件、服務(wù)程序和數(shù)據(jù)等，其中的資源可動(dòng)態(tài)地分配給申請(qǐng)者，用完后客戶/服務(wù)器(client/server)模型：在這種模型中，系統(tǒng)中的場(chǎng)點(diǎn)分為客戶和服務(wù)器兩大類。分布式操 作系統(tǒng)的所有服務(wù)程序及相應(yīng)的共享信息都分散地駐留在一些特定的場(chǎng)點(diǎn)上，并加以實(shí)現(xiàn)。而客戶場(chǎng)點(diǎn)僅包 含足以訪問(wèn)相應(yīng)服務(wù)器場(chǎng)點(diǎn)上服務(wù)程序及相應(yīng)的共享信息的接口軟件，參見。這種模型常常分為

43、兩種形式： 池按服務(wù)類提供的，如文件服務(wù)類、 可重用的資源池，如處理機(jī)、外設(shè)、 再收回到資源池中供再次使用。中央式：系統(tǒng)在硬件結(jié)構(gòu)上有一個(gè)中央場(chǎng)點(diǎn)和若干衛(wèi)星場(chǎng)點(diǎn)。中央場(chǎng)點(diǎn)運(yùn)行一個(gè)中央控制程序，由它 處理所有對(duì)分布式操作系統(tǒng)的調(diào)用。每個(gè)衛(wèi)星場(chǎng)點(diǎn)上運(yùn)行的進(jìn)程彼此不能直接通信，它們只能借助中央控制 程序進(jìn)行交往。以構(gòu)成單個(gè)場(chǎng)點(diǎn)上的局部操作系由各場(chǎng)點(diǎn)上的局部操作系統(tǒng)的核模塊分散式：分散式模型意指將分布式操作系統(tǒng)的功能分散到各個(gè)場(chǎng)點(diǎn), 統(tǒng)，使得每個(gè)場(chǎng)點(diǎn)上的局部操作系統(tǒng)僅擔(dān)負(fù)整個(gè)系統(tǒng)的部分管理功能。 和核外部分采用協(xié)商、合作的方式來(lái)實(shí)現(xiàn)對(duì)全系統(tǒng)的管理。第5節(jié) 分布式操作系統(tǒng)的層次用戶接層崩務(wù)支持層a程通信

44、層從層次觀點(diǎn)看，一個(gè)分布式操作系統(tǒng)大致可分成四層， 由內(nèi)向外依次是執(zhí)行層、進(jìn)程通信層、服務(wù)支持層和用戶接口 層。如圖5-16所示。其中，執(zhí)行層主要對(duì)分布式系統(tǒng)中分散的 各類資源進(jìn)行分配、回收、控制和管理。在該層上各場(chǎng)點(diǎn)有自 己的局部操作系統(tǒng)，它們一方面以自治的方式對(duì)本地資源進(jìn)行 管理，另一方面又相互合作，直至對(duì)全系統(tǒng)范圍內(nèi)的資源實(shí)現(xiàn)圖5-16分布式操作系統(tǒng)的層次結(jié)構(gòu) 共同管理。 這一層上的操作系統(tǒng)對(duì)本場(chǎng)點(diǎn)具有集中管理的特征，而對(duì)系統(tǒng)中的其它場(chǎng)點(diǎn)具有分散管理的特征， 以便同其它層次銜接。 進(jìn)程通信層主要以消息轉(zhuǎn)移為基礎(chǔ)，建立包括遠(yuǎn)程過(guò)程調(diào)用在內(nèi)的進(jìn)程間的同步和通信機(jī)制。在該層上，對(duì) 于緊密耦合系

45、統(tǒng)，各處理機(jī)之間進(jìn)行數(shù)位或數(shù)組級(jí)的聯(lián)系；對(duì)于松散耦合系統(tǒng)，各處理機(jī)之間依靠消息（報(bào) 文）轉(zhuǎn)移機(jī)制實(shí)現(xiàn)網(wǎng)絡(luò)的通信協(xié)議。因此，這一層上的操作系統(tǒng)具有分散管理的特征。其中包服務(wù)支持層主要提供若干基本的抽象邏輯結(jié)構(gòu)的服務(wù)功能及大多數(shù)服務(wù)功能所需要的公共信息，括“請(qǐng)求 /應(yīng)答”協(xié)議及其它服務(wù)層協(xié)議的定義；定義控制信息，信件（報(bào)文），數(shù)據(jù)等的格式，完成數(shù)據(jù)類型和格式轉(zhuǎn)換等。為客戶（client）的請(qǐng)求查尋和定位相應(yīng)的服務(wù)器（servers）。絕大多數(shù)的命名和尋址功能。進(jìn)程調(diào)度，并發(fā)控制和死鎖處理等。保護(hù)，認(rèn)證（authenticatin）和錯(cuò)誤恢復(fù)等。用戶接口層是用戶見到的分布式操作系統(tǒng)的最外層， 該層為

46、用戶提供分布式處理的各種直接服務(wù)， 如命 令解釋器，各種語(yǔ)言編譯器，文件系統(tǒng)，目錄和終端服務(wù)程序以及與用戶應(yīng)用相關(guān)的若干實(shí)用服務(wù)程序。若 這些服務(wù)涉及到全系統(tǒng)范圍，則操作系統(tǒng)顯然應(yīng)具有分布管理的特征。第6節(jié) 分 布式系統(tǒng)中的通信問(wèn)題§ 1. 發(fā)送策略當(dāng)場(chǎng)點(diǎn) A 上的一個(gè)進(jìn)程希望同場(chǎng)點(diǎn) B 上的另一個(gè)進(jìn)程進(jìn)行通信時(shí)，如何發(fā)送消息？若從 A 到 B 之間只 有一條物理信道（例如，在星型或?qū)哟涡徒Y(jié)構(gòu)中），那么，該消息只能經(jīng)由這條物理信道發(fā)送。但是，如果 從A到B存在多條物理信道，那么，發(fā)送該消息就有選擇性。每個(gè)場(chǎng)點(diǎn)有一個(gè)發(fā)送表，記錄可用來(lái)發(fā)送消息 到其它場(chǎng)點(diǎn)的所有可能的信道，該表還可以包含

47、各種信道的速度和開銷。常用的幾種發(fā)送策略是：固定發(fā)送。從 A到B的信道事先已規(guī)定好并且不得更改，除非硬件的故障影響到它的通信能力。通 常選擇物理上長(zhǎng)度最短的信道，以減少通信開銷。虛擬線路。從 A到B的信道在一段時(shí)期內(nèi)是固定的，在不同時(shí)期，從A向B發(fā)送的消息可能經(jīng)由不同的信道發(fā)送。動(dòng)態(tài)發(fā)送。用于從 A到B發(fā)送消息的信道僅當(dāng)該消息發(fā)送時(shí)才確定。由于這種選擇是自動(dòng)進(jìn)行的， 單一的消息可能分給不同的信道。一般講，一個(gè)場(chǎng)點(diǎn)發(fā)送消息給另一個(gè)場(chǎng)點(diǎn)時(shí)所選定的信道是當(dāng)時(shí)最少使用 的那條信道。A和B之間確立了一條上述幾種方案各有利弊。固定發(fā)送不適用于通信負(fù)載的改變。即如果已在場(chǎng)點(diǎn) 信道，那么消息只能經(jīng)由這條信道傳

48、送，即使這條信道已經(jīng)超載，而其它信道還處于尚未滿載的狀態(tài)。可以 利用虛擬線路策略進(jìn)行改善或通過(guò)動(dòng)態(tài)發(fā)送策略來(lái)加以完全地解決。固定發(fā)送和虛擬線路策略可以確保按消 息的發(fā)送次序從 A 向 B 發(fā)送消息。采用動(dòng)態(tài)發(fā)送策略，消息的到達(dá)次序不一定和消息的發(fā)送次序相一致。這 可以通過(guò)給每條消息賦以一個(gè)順序號(hào)來(lái)解決。長(zhǎng)的形式，并把這種定長(zhǎng)的形式稱為消息包（ packet） 息包都可以經(jīng)由網(wǎng)絡(luò)中不同的路徑單獨(dú)地發(fā)送到其目的地， 組成一條完整的消息。線路轉(zhuǎn)換需要安裝時(shí)間但傳送每條消息的開銷較少； 移每條消息的開銷較大。此外，在采用消息包轉(zhuǎn)換方法時(shí)， 為整”。消息轉(zhuǎn)換和消息包轉(zhuǎn)換需要較少的安裝時(shí)間， 但轉(zhuǎn)每條消息

49、可能得先“化整為零”，然后再“集零§ 2. 連接策略有許多不同的方法來(lái)連接一對(duì)彼此希望通信的場(chǎng)點(diǎn)（或進(jìn)程）。最常用的方法有線路轉(zhuǎn)換、消息轉(zhuǎn)換和 消息包轉(zhuǎn)換。線路轉(zhuǎn)換（circulate switch）:如果兩個(gè)進(jìn)程希望通信，那么就在它們之間設(shè)立一條永久性的物理通 信鏈路。這條通信鏈路供其消息轉(zhuǎn)移期間使用，在這段期間其它進(jìn)程不能使用這條鏈路。這種方案與電話系 統(tǒng)類似，一旦一條通話線路已對(duì)通話雙方開通（例如甲方給乙方打電話），其它人就不能使用這條信道，除 非甲乙兩方已明顯地結(jié)束其通話（例如一方已掛起話筒）。消息轉(zhuǎn)換（message switch）：如果兩個(gè)進(jìn)程希望通信，那么就確定一個(gè)臨時(shí)

50、的通信鏈路供其消息轉(zhuǎn)移期間 使用。物理通信鏈路則根據(jù)需要在用戶間動(dòng)態(tài)進(jìn)行分配，而且只允許使用較短的一段時(shí)間。每條消息由一個(gè) 數(shù)據(jù)再加上某些系統(tǒng)信息（如發(fā)送處，接收處和錯(cuò)誤校正碼等）組成，這些系統(tǒng)信息將輔助通信網(wǎng)絡(luò)正確地 將消息轉(zhuǎn)移到目的地。這種方案與郵局系統(tǒng)類似，每封信可看作是包含發(fā)送處和接收處的一條消息，而且來(lái) 自不同用戶的信件（消息）可在相同通信線路上轉(zhuǎn)移。消息包轉(zhuǎn)換（Packet switch）:消息一般是可變長(zhǎng)度的。為了簡(jiǎn)化系統(tǒng)的設(shè)計(jì)。常常把消息設(shè)計(jì)成定。一條邏輯消息可能不得不劃分成若干消息包，每個(gè)消 當(dāng)這些消息包都到達(dá)其目的地后，還得拼裝起來(lái)§ 3. 爭(zhēng)奪處理從而發(fā)由于一條

51、通信鏈路往往連結(jié)多個(gè)場(chǎng)點(diǎn)， 而這些場(chǎng)點(diǎn)有可能希望同時(shí)在這條通信鏈路上轉(zhuǎn)移信息， 生爭(zhēng)奪現(xiàn)象。這種情況在環(huán)結(jié)構(gòu)或多存取總線結(jié)構(gòu)中表現(xiàn)得尤為突出。已研究出了不少解決爭(zhēng)奪現(xiàn)象的技術(shù)，常用的有沖突檢測(cè)，令牌轉(zhuǎn)移和消息槽。沖突檢測(cè)： 一個(gè)場(chǎng)點(diǎn)要在某條通信線路上轉(zhuǎn)移消息之前， 它必須進(jìn)行監(jiān)測(cè)以確定當(dāng)前在該通信線路上 是否正在轉(zhuǎn)移另外的消息。 若該通信線路空閑， 則這個(gè)場(chǎng)點(diǎn)可以開始發(fā)送， 否則它必須等待 （同時(shí)繼續(xù)監(jiān)測(cè)） 直到這條線路空閑。如果兩個(gè)或多個(gè)場(chǎng)點(diǎn)恰好都要在這條線路上同時(shí)開始轉(zhuǎn)移消息（它們各自都認(rèn)為沒(méi)有別人正在使用該線路），那么，它們必須停止轉(zhuǎn)移。每個(gè)場(chǎng)點(diǎn)在某個(gè)隨機(jī)的時(shí)間片后再繼續(xù)轉(zhuǎn)移。注意，當(dāng)場(chǎng)

52、 點(diǎn)在一條線路上開始了其消息轉(zhuǎn)移后，還得繼續(xù)監(jiān)測(cè)，以便及早發(fā)現(xiàn)來(lái)自其他場(chǎng)點(diǎn)的消息沖突。采用這種途 徑的主要問(wèn)題是，當(dāng)系統(tǒng)非常忙時(shí)，可能發(fā)生許多沖突現(xiàn)象，因此整個(gè)系統(tǒng)的性能由于沖突檢測(cè)方面的工作 而受到衰減。這種方法已成功地用在以太網(wǎng)系統(tǒng)Metcalfe and Boggs l976 。令牌轉(zhuǎn)移（Token Passing）:令牌是一個(gè)特殊的消息類型，它不斷地在系統(tǒng)（通常在一個(gè)環(huán)結(jié)構(gòu)）中 循環(huán)。希望轉(zhuǎn)移消息的場(chǎng)點(diǎn)必須等待直至令牌到達(dá)。當(dāng)令牌到達(dá)后，該場(chǎng)點(diǎn)就從環(huán)中取走令牌并開始轉(zhuǎn)移它 的消息，當(dāng)它完成了相應(yīng)的消息轉(zhuǎn)移后再重新發(fā)送令牌，這就給另一個(gè)場(chǎng)點(diǎn)提供了占有令牌的機(jī)會(huì)，一旦占 有，就可開始它的消

53、息轉(zhuǎn)移。如果令牌丟失。那么系統(tǒng)應(yīng)能發(fā)現(xiàn)這種情況并產(chǎn)生一個(gè)新令牌。該方法已由Primenet 系統(tǒng)所采用 Nelson and Gordon, 1978 。消息槽（slot）:若干定長(zhǎng)的消息槽連續(xù)不斷地在系統(tǒng)（通常是一個(gè)環(huán)結(jié)構(gòu)）中循環(huán)。每個(gè)消息槽可以容 納一定長(zhǎng)的消息和有關(guān)的控制信息（如像發(fā)送處，接收處，消息槽滿/ 空等）。希望轉(zhuǎn)移消息的場(chǎng)點(diǎn)必須等待直到一個(gè)空消息槽到達(dá)，然后，該場(chǎng)點(diǎn)將它的消息插入這個(gè)空消息槽并附上適當(dāng)?shù)目刂菩畔?，此消息在網(wǎng) 絡(luò)中繼續(xù)流動(dòng)，當(dāng)它到達(dá)某個(gè)特定的場(chǎng)點(diǎn)時(shí)，該場(chǎng)點(diǎn)就查看此消息槽的控制信息，以確認(rèn)此消息槽是否包含 了發(fā)送給它的消息；若沒(méi)有，它就放過(guò)此消息槽，否則，它取走消息

54、糟中的消息，重新設(shè)置控制信息以指明 該消息槽為空。然后，這個(gè)場(chǎng)點(diǎn)或者利用此消息槽去發(fā)送它自己的消息或者釋放該消息槽。由于一個(gè)消息槽 只能包含定長(zhǎng)的消息，因此，一條邏輯消息可能不得不分成若干組，每組用單一的消息槽發(fā)送。這種方法已 在劍橋數(shù)字通信環(huán)中采用 Wilkes and Wheeler l979§ 4. 保密向題系統(tǒng)必須提供適當(dāng)?shù)拇胧┳層脩舯Ｗo(hù)他們的信息(數(shù)據(jù))。編碼是保護(hù)信息的常用方法之一。信息在發(fā) 送之前先予以編碼，當(dāng)信息到達(dá)其目的地后就進(jìn)行譯碼。經(jīng)編碼后的信息即使被他人獲取也不見得有用，除 非他能進(jìn)行譯碼。問(wèn)題在于如何研制一個(gè)不可能(或很難)破譯的編碼系統(tǒng)。對(duì)此，有許多解決辦

55、法，最常 用的一種就是提供一個(gè)通用的編碼算法 令Ek和Dk分別表示具有保密鍵 k 必須滿足下面的特性：E, 個(gè)通用的譯碼算法D，并對(duì)每次應(yīng)用提供一個(gè)保密鍵(key)，的那個(gè)特定應(yīng)用的編碼和譯碼算法，那么，對(duì)于任何消息m,該編碼系統(tǒng) Dk(Ek(m) = m ;Ek和Dk都能有效地計(jì)算；該系統(tǒng)的保密性只依賴于鍵 一個(gè)稱之為 “數(shù)據(jù)編碼標(biāo)準(zhǔn)”k 的保密性而不依賴于算法 E 和 D 的保密性。(Data Encryption Standard)的編碼系統(tǒng)已由美國(guó)國(guó)家標(biāo)準(zhǔn)局所采用。不過(guò),該方案還存在“鍵分布”問(wèn)題，即，開始通信之前，保密鍵必須秘密地轉(zhuǎn)移給發(fā)送者和接收者，但在一個(gè)通 信網(wǎng)絡(luò)環(huán)境中很難有效

56、地完成這一點(diǎn)。解決此問(wèn)題的辦法之一是利用一個(gè)“公共鍵” (public key )編碼方案Diffie and He11man， 1976。每個(gè)用戶有一個(gè)公共鍵和一個(gè)私有鍵，兩個(gè)彼此知道他們的公共鍵的用戶才可 以相互通信?；谏鲜鏊枷氲木幋a有案已由Rivest，Shamir和Adleman1978設(shè)計(jì)出來(lái)了。這個(gè)方案曾被認(rèn)為是差不多不可破譯的。其中的公共編碼鍵是一對(duì)偶(e, n)，私有鍵是對(duì)偶(d, n),這里e, d, n都是正整數(shù)。每條消息用0 n-1 之間的一個(gè)整數(shù)表示(較長(zhǎng)的消息可分成若干較短的消息，它們每一個(gè)都可用這樣的一個(gè)整數(shù)表示)，函 數(shù)E和D定義為eE(m) = m mod n = CD(C) = Cd mod nn 可用下式計(jì)算其中 p 和 q 是隨機(jī)選取的兩個(gè)較大的素?cái)?shù) (例如，與(p - 1) (q - 1)互質(zhì)的較大整數(shù)，即d滿足n = p q它們是由 100 位或更多位數(shù)字組成) ， d 是隨機(jī)選取的一個(gè)這里的主要問(wèn)題是選擇編碼和譯碼鍵。整數(shù)GCD(d, (p - 1) (q - 1) = 1而 e 則應(yīng)滿足e d mod (p - 1) (q - 1) = 1應(yīng)指出的是，雖然n