教材：《高級操作系統》何炎祥等編科學出版社

第一章分布式計算機系統

主要內容：分布式計算機系統的特征、結構；分布式操作系統概述。

學時：45'*4

重點：分布式操作系統的結構模型和層次劃分。

1-1分布式計算機系統

一、分布式系統的出現

1、應用需求

計算機系統的性能越來越好，但是，人們的要求越來越高。

典型應用：

①氣象預報

②地震預報

③結構分析

④大量的事務處理：銀行系統、交通系統、公安系統、電力調度系統……

2、技術支撐mu

①計算機性能價格比

a）單機系統價高：深騰（萬0次）、神州、銀河、曙光

多機系統價低

b）單機性能價格比變化（提高10"倍）

早期：1000萬美元的機器，每秒鐘執行1條指令

現代：1000美元的機器，每秒鐘執行1000萬條指令

②現代硬件技術使單機無法滿足更高的速度要求

例：設，每個CPU的速率為50MlpS,當前的技術可以將10,000個這樣的CPU芯片組

成一個系統，從而獲得如下峰值速度

50MIPS*10,000=500,000MIPS（5000億次）

而執行一條指令的時間為

1/500,000MIPS=l/（500,000,000,000/S）=2*1012%J>=2微微秒=0.002納秒

即該計算機0.2微微秒執行一條指令。電子運動的速度為

300,000km/s=300,000,000,000mm/s=0.3/（10',2）mm/s

0.2微微秒電子信號可以傳送的距離為

0.3/(10'12)mm/s*2*1012s=0.6mm

這就是說，單CPU的機器要達到此速度，至少要被限制在邊長為0.6mm的立方體內。

而這種CPU所產生的熱量會立即將它熔化。

③高速計算機網絡出現

提供了信號高速傳輸的可能，使得可以將多臺計算機鏈在一起——走并行之路

④網絡中存在大量的空閑資源

時差、任務的隨機性等帶來的網絡中資源利用的不平衡

結論：計算機性能價格比的大幅度提高和網絡技術的發展，導致了分布式系統的出現。

問題：

①如何在給定的峰值速度下，獲得最大的實際有效速度？

②如何有效地組織任務，有效地利用網絡中的各類資源？

二、分布式計算機系統的概念

1、基本內容

多機+網絡

2、注意

不是簡單的互連

3、概念

多個分散的計算機通過網絡互連構成的既互相協同、又高度自治的、能實現資

源共享和任務與功能動態分配的統一計算機系統

4、強調

自治、協同、共享資源

5、要求

資源、任務、功能、控

全面分布：任務分布(工作方式)

資源分布

需要進行：任務分解、功能分解

三、分布式系統的特點

1、資源共享

內容：硬件資源：CPU、Mem、Printer、Disk^OtherDevices

軟件資源：各種系統或者應用程序

2

資源管理程序模型:

Client/Server模型OO模型

接口提供服務

問題：

如何實現CPU的共享？—任務委托（RPC）

如何實現Disk的共享？——分布式文件系統取某個“東西”

2、開放性

分布式的要求：網絡連接的是多臺異構機，這里，開放的目的是:

可伸縮性+可移植性+互操作性

AAA

硬旅模（自動為降級）異構露牛系統數據系換的實現

軟件的擴充/剪裁為用戶提供多種服務

不同的系統用“可轉換”接口<】不同的系統用“統一”的接口

3、并行性

多用戶、多進程同時使用

微觀并行（多資源：多CPU、外設……）

宏觀并行、微觀串行（單一資源共享）——并發

4、容錯性

基本方法：硬件冗余（雙工、鏡像）、軟件恢復

5、透明性

位置透明］

遷移透明I綜合?一r訪問透明

副本透明x-1位置透明

并發透明J

四、優缺點

*與高性能的大型主機（MainFrame）系統相比

3

①經濟一較高的性能價格比

②速度——平均響應時間比大型機系統短

③對固有分布性問題求解的適應性

④可擴充性——比較松散的構成，使得節點的增減很容易］

⑤可靠性——自動降級運行保障，故障時不停機｝給系統設計帶來新任務

⑥寬適應性——增加了對分散用戶要求協同的支持J

*與分散系統（每人一臺微機或者工作站）相比

共享資源、加強通信、通過負載平衡提高系統的效率

0

擴充了系統能力

*問題

①控制比較復雜，尤其是在資源管理上

要附加許多協調操作——資源屬于局部工作站

②性能、可靠性對網絡的依賴性強

③安全保密——基礎不好。用戶掌握有許多軟件接口

④相應的應用軟件較少，需要大力開發

五、分布式系統的結構

1、關于系統性能評價的幾個視角

基本開銷——構建系統所需開銷

通訊開銷——運行中的系統開銷

可靠性——結點故障、鏈路故障

2、幾種典型的拓撲結構

①全互連

特點：每對結點之間均直接連接

優點：可靠性高，通信方便

缺點：連接成本高

②部分互連

特點：并不是每對結點之間均直接連接，但有間接連接

優點：連接成本低

缺點：可靠性差，通信不方便，容易在

出故障時造成網絡分割，如：左圖中的結點v故障。

③樹型結構（分層結構）

特點：連接如同樹狀

優點：連接成本低，控制方便，可按分層完成

缺點：可靠性差，通艮/普，容易因故障造成分割

如何尋找通路,尋找最近代的公共祖先

④星形結構

特點：每個結點與中心結點直接連接

優點：連接成本低，控制方便，通信比較方便

缺點：可靠性低，特別是存在中心結點的

破壞問題和瓶頸問題。

⑤環形結構

特點：連接呈環狀

優點：可靠性較高，連接成本低

缺點：通信成本較高

單向環雙向環

最大轉接次數n-1n/2

分割損傷

單向環單通信鏈路雙向環

@總線結構

特點：每結點均直接與總線連接

優點：可靠性高，通信方便，成本低

缺點：總線可能成為瓶頸

QQQQQ

O

5

線性總線環形總線

⑦環一星形結構

特點：兼有環形與星形的連接

優點：可靠性高，通信方便

缺點：成本高

⑧有規則結構

特點：結點排成陣列，每個結點均與上下左右的節點連接

優點：可靠性高，通信方便

缺點：成本高，一般要求各個結點一致

隨意增加結點，通信路徑算法復雜

⑩n立方體結構

將2"=N個計算機互連起來，每個計算機有n個全雙向通路

3、系統的耦合度

①按地域分

機體內n緊

建筑物內

建筑物間

6

區域系統（不同地理范圍）松

②按應用分

分布式并行計算1緊

分布式過程控制系統

分布式數據處理系統V松

4、資源管理方式

資源要拿出來為大家共用。怎么辦？作為分布式系統中的一個最重要的方面，是盡可能

好地發揮資源的效率，因此，其管理方式是非常重要的。一般來說，對單個資源，有如下4

種管理方式。

①全集中管理

僅由一個管理機構管理

②分擔管理

分職能進行管理

③輪流管理

④全分散管理

多個機構按一定的原則協商管理

1-2分布式操作系統概述

基本概念回顧

1、操作系統

管理硬件資源、控制程序運行、改善人機界面、為應用軟件提供支撐的一種系統軟件國

科P43]

為了提高計算機的利用率、方便用戶使用計算機以及提高計算機的響應時間而配置的一

種軟件隅典P687]

控制和管理計算機資源，方便用戶使用的程序和數據結構的集合。輟PR

AnOSisaprogramthatactsasanintermediatebetweenauserofcomputerand

computerhardware.ThePurposeofanOSistoprovideanenvironmentinwhichusercan

executeprogramsinaconvenientandefficientmanner.IS,bcrschatzP21

2、認識操作系統的兩種觀點MP?”

資源管理：OS高效地管理整個系統的各個部分

虛擬機：為用戶提供一臺比物理計算機更容易使用的計算機。

3、操作系統的組成

7

os一般由如下幾部分組成

①進程管理

②內存管理

③I/O管理

④外存管理

⑤文件系統

@網絡

⑦保護系統

⑧命令解釋系統

一、基本概念

分布式OS是分布式計算機系統上的OS,實現系統范圍內的任務、資源分配，使系統

的資源得到有效的利用，并給用戶提供方便、有效的環境。

其主要特點為：

①常用信息傳遞方式實現進程通信——多結點運行造成的

②進程調度、資源分配、系統管理按照分布處理的要求進行

③盡可能保持系統的負載平衡

④具有故障的檢測與處理功能

網絡OS與分布式OS：

網絡OS用來將各個計算機上的OS有機地聯系起來，提供可靠的網絡通信能力，提供

遠程作業錄入、分時系統服務，以及文件傳輸服務。

網絡OS看系統：系統中的計算機是獨立的，它們可以根據用戶的需要，幫助系統中的

其它工作站完成該用戶要求的任務。------個可以互相幫忙的機器集合

分布式OS看系統：系統由獨立的計算機組成，這些計算機在OS的協調下完成系統所

接受的任務。-----個協同工作的系統

二、多機OS的基本結構

1、主從式

特點：始終由一臺處理機（主處理機）執行系統的管理，其它處理機（從機）通過向

主處理機的申請而獲得系統中的有關資源的服務。

問題：主處理機容易成為瓶頸。

適應：負載精確給定，或從機能力小的非對稱系統。

優點：設計實現較簡單——與多道程序系統類似。

2、獨立式

專用信息自主控制，公用信息協商處理/以委托方式提供

每臺處理機的管理程序僅為自身服務，它們借助公用信息實現互相聯系。為了保證系

統正常運行，每臺處理機由自己的系統管理自己的資源（每臺一個副本）

8

問題：協調能力難以提高

3、分布式

每臺處理機同時執行管理程序，它們通過通訊等機制實現協調。

程序必須是可再入的。

問題：控制難度大、程序較復雜。

三、分布式OS設計要考慮的問題

核心模塊：內存管理、外存管理、進程管理、進程通信與同步

1、協調管理

各個結點的資源的管理、控制、關系的協調，防止互相干擾、死鎖、饑餓。

2、功能分布

除每個結點擁有一個共同的核心外，其它的可以分布到不同的結點上去執行。每一

個結點在邏輯上是平等的，控制流和數據流的轉移則是在各個結點上的局部OS核心模塊

的合作協調下完成的。

3、層次劃分

根據2,分布式OS可以分成高層和局部兩部分：

局部：本結點獨立運行的基本管理功能：結點間通信、同步、消息傳遞

高層：需協調合作完成的功能：任務分配、負載平衡、死鎖處理、錯誤檢測、系統

重構，其它公共事務。

4、調度單位

任務隊列由進程組成，同一隊列的并發進程可以由不同的結點執行，同一結點可以執

行多個不同隊列中的并發進程。

當一個隊列被調度時，它所含的并發進程可以分布到系統中的各個結點執行。當然，

一個結點可以同時執行多個不同隊列中的進程。

5、任務/進程通信、遷移、遠程任務的控制

6、耦合度

緊耦合：共享Mem和Clock,要由專門的機制解決競爭和沖突

松耦合：以機間的通信與同步為主，競爭、沖突為輔。

7、自動重構、降級使用、錯誤恢復

四、結構模型

1、內核

在每個結點上安裝一個分布式OS的內核，它包括內存管理、外存管理、進程管理、

進程同步與通訊、各種原語操作

例如：V、Accent的內核就是這種結構

2、集成式

9

每個結點有一個比較完整的或者集成的、高度可組合的標準化OS模塊集。絕大多數

的工作在本結點完成。

例如：LOCUS是這種結構。

文件服務器

結點A

時鐘服務器

總線

文件服務器文件服務器

時鐘服務器時鐘服務器

結點B結點C

3、Client/Server模型

服務程序、公共信息——分布于特定服務器上;

接口軟件和應用軟件——客戶機上

例如：

文件服務器時鐘服務器

文件系統代碼程序時鐘管理代碼程序

結點A結點B

總線

文件服務器接口軟件

時鐘服務器接口軟件

Client應用程序

結點C

10

4^中央式

系統中只有一個中央結點，其它為從（衛星）結點，各從結點上的進程必須通過中央

控制程序進行交往。

控制簡單，效率低下。

5、分散式

每個結點承擔部分功能。

權力分散、協同合作、充分自治。

五、構造途徑

途徑做法優/缺點

全新設計統籌考慮周期長、工作量大；系統效率高

修改擴充（混合體）修改擴充原系統與原系統兼容、工作量小，系統

效率低

層次（增加一層）增加分布處理與機間通信功能結構清晰、性能衰減

如：DBMS利用OS讀寫指定內容大大降低了系統工作效率。

六、層次劃分

1、用戶接口層

提供用戶可見的功能——直接服務

用戶接口層

命令處理、文件系統、目錄、終端服務、

服務支持層

此部分可以實現分散管理

進程通信

2、服務支持層執行層

基本服務功能及其相關服務數據

?請求/應答等服務層協議

?定義控制信息、報文、數據格式、數據類型及格式轉換。

?客戶機請求查詢、定位、命名、尋址

?進程調度、并發控制、任務分配、負載平衡、死鎖處理

?保護、鑒別、認證、錯誤恢復

3、進程通信

此部分有分散管理特征，與系統耦合度有關。

4、執行層

各類資源的分配、回收、控制和管理

對內呈集中管理，對外呈分散協同管理。

II

七、控制策略

集中式——中央控制站點（瓶頸）

分布式——共同管理

八、分布式系統與計算機網絡系統的比較眄P18]

評價視角分布式系統網絡

計算機的使用動態分配遠程注冊

透明位置不透明

文件存放

系統的局部的

資源歸屬系統局部結點

容錯能力有無

透明性高低

資源共享類似類似

結論整體系統系統集合

主要內容：分布式計算機系統的特征、結構；分布式操作系統概述。

重點：分布式操作系統的結構模型和層次劃分。

思考題：

1、如何實現CPU、打印機、磁盤的共享？各有什么樣的實現形式？

2、分布式系統的定義與分布式系統之間的特點的聯系。

3、分布式系統是一種特殊的用網絡互連的多個計算機組成的系統，請指出分布式系統

和一般的網絡系統的本質區別？

4、如何理解分布式系統中的多資源共享和單資源共享？它們有哪些異同？

5、選擇一種分布式OS的設計實現途徑，并敘述你選擇該方法的理由。

12

第2章分布式通信

主要內容：分布式通信的有關問題。組（播）通信、RPC通信及其

實現、PCAPo

學時：45，*6

重點：組播通信

難點：多對多RPC

2-1概述

在分布式系統中，許多功能是通過通信來實現的。也就是，通

過網絡，進行機間通信。其中涉及到以下幾方面的問題。

一、發送策略（結點）——信道的選擇策略

在不同的結點之間選擇適當的信道。

為了實現此策略，每個結點需要保持一張“發送表”，用來記

錄一些可能的信道及其性能參數（速度、位置、開銷……）o常用

的策略有3種。

1、固定發送

使用事先定好的、不可改變的信道，除非硬件故障

2、虛擬線路發送

分時段固定。

3、動態發送

發送時選定。因此，不能保證接受的順序與發送的順序一致，

有可能出現先發送的消息后到的現象。

二、連接策略（進程）——信道的保持策略（對動態和分時有用）

兩個進程通信期間如何保持信道。

1、線路轉換

線路轉換Q-----------?O---------2---------?O-------PB

線路固定

特點：占用，故障時難以自動替換；線路使用效率低，但傳輸快,

控制簡單

2、消息輪換

建立臨時的通信鏈路，消息上帶有系統信息：發送處、接受處、

錯誤校驗……——如同郵局。

消息輪換后------2----------2----------B

特點：線路不固定，但對一個消息來說，線路是唯一的

線路利用率較高，控制比較簡單。

3、消息包轉換

2

將消息切成定長的“包”，這些包可以通過不同的鏈路發送

一2-------?€>-------->O'、、

d二二'二/

消息包轉換A-------2--------B

特點：線路不固定，且對一個消息來說，使用線路不唯

控制復雜，信息到達順序可能與發送順序不同

線路利用率高，線路容錯能力強

策略特征

線路轉換固定鏈路

消息輪換可臨時尋找鏈路，一個消息是一個傳遞單位

消息包轉換一個消息被切分成多個包，各包可用不同的臨時鏈路

三、爭奪處理——信道的爭用處理策略

解決對通信網絡的爭用問題。

1、沖突監測

先監測、后使用：發現空閑，則發送，否則等待。

3

問題：當系統比較忙時，將因反復檢測而使性能衰減

2、令牌傳遞(TokenPassing)

擁有令牌者執行發送

問題:增加了作為令牌的消息的傳輸與處理,令牌有丟失的可能;

適應環形網

3、消息槽(Slot)

消息槽是運送消息的工具，如同公共汽車，用戶在站臺上等待,

“車”來時，并且有“空座”時上車，到站時有接受者將其接下車。

更像機場的行李提取系統。

四、保密策略(略)DES,RSA等

RSA加密解密算法：E(m)=memodn=C

D(C)=Cdmodn=m

公共鍵(e,n),私有鍵(d,n)

q,pN2100,為素數，n=p*q

GCD(d,(p-l)*(q-l))=l

GCD(e*d,(p-l)*(q-l))=l

2-2消息傳遞

一、消息傳遞原語

4

消息可以是按幀發送的，也可以是按消息發送的，“幀”是系

統規定的消息的一種形式，包括它的大小和形式。系統在對消息打

包時，要附加一些關于消息說明的數據。

1、原語

Send,Receive,Reply

2、同步型

模式：Send(&wait)-----------?[Receive(&wait)j--------------------?Continue

優點：同步與通信一同完成；需要的緩沖區少；容易實現

缺點：效率低，減少了并發程度

3、異步型

模式：Send--------?Continue

優點：利于系統優點的發揮

缺點：需要緩沖區多，控制困難(緩沖區溢出、同步問題)

4、討論

a)同步消息適應于Client/Server模型

一般地，Server一旦接到請求，就進行處理，并將結果返回給

請求者。如：時鐘服務。

Server的執行邏輯:

WhileTruedo

Receive（請求）；Send

進行請求處理;

Reply（結果）

End{While}

ServerClient

b)其它形式的發送與接收

ConditionalSend——僅在接收者等待時發送

SelectiveReceive—用戶可選擇幾個進程去接收發送來的消息

c)Charlotte分布式OS的7個通信原語［何P25］

該系統由Wisconsin大學研制。

MakeLink(varendl,end2:link)

Destroy(myendzlink)

Send(L:link;buffer;address;length:integer)

Receive(L:link;buffer;address;length:integer)

Cance(L:link;d:direction),d可以是Send或者Receiveo

該原語用來撤銷一個存在的Send和Receive操作。如果相應的

操作已完成，則Cance操作失敗。

Wait(L:link;d:direction;e:description)

GetResult(...)查詢Wait返回的結果。

二、組播通信(Multicast)

［組通信：GroupCommunication；多點傳送：Multicasting(向指

6

定的多個機器發送)；廣播通信：Broadcasting[TP73]]

1、組播通信的概念及用途

這是一種1對多的通信

概念：一個進程根據需要同時向一組指定的進程發送同一個消息。

用途：

①以重復服務獲取系統的容錯性

②在系統中尋找一個對象(例如：一個文件)

③用于保持多副本數據的一致性

④多結點數據的刷新(例如：新聞組)

2、基本實現形式

ProcedureMulticast(destination：ARRAYOFPortID；m：Message);

Vari：CARDINAL;

Fori=0ToHIGH(destination)Do

Send(destination(i),m)

考慮用一個代理(Agent)進行實現。

3、存在的問題

①是否可以保證每個端口都可以獲得發送的消息？

②是否可以保證每個端口都可以按照發送的順序接收發送的消

息？

7

例如：Ai發送mi，A2發送m2，A1先于A?發送。問題

①Bi、Bz、……、Bn全能收到？

②Bl、B2>...、Bn全能按照統一順序（mbm2,或者m2,mi）

收到？

4、對策

①建立原子組播

任何一條以原子組播方式發送的消息，要么被指定的所有成員

成功接收，要么任一成員均未收到。

——如何實現原子組播？

措施：

i.發送者以監控形式等待每個接收者回答，超時不回答者被

刪除

ii.發送者失效時，由一個已接到消息的成員充當發送者完成

后續任務

②定序技術

8

解決接收消息的順序與發送消息的順序不一致問題。

給每一個消息配一個全局定序的表示——全局序號。它可以是

時間戳，由系統維持一個序號發生器，建立一個協議——FIFO定

序原則。

序號發生器：時鐘；專用序號發生器；序號產生協議。

③基本原子組播的修改

基本原子組播要求過于嚴格，使得系統的運行效率非常低，實

際上，有的情況下，這是不需要的。

i.不可靠組播——只播不檢查。例如：網上News

ii.可靠組播——不要求所有的接收者都完成接收。例如：資

源（文件）請求。

iii.可靠原子組播一基本原子組播。例如：副本更新。

iv.全定序原子組播——每個消息一個消息標識，如果一個成

員收到了一條消息，并且不可能收到具有更小標識的消

息，則將此消息傳遞給自己的應用程序。例如股票系統中

的買賣系統。

9

由于消息在被發出后需要經過不同的站點進行傳輸，所以，導

致A、B到達P2和P3的順序是不一致的。全定序可以防止這種現象發

生。

基本原子組播的4種修改比較見下表:

各種組播檢查收到否要求都收到要求按順序收到

不可靠組播XXX

可靠組播4XX

可靠原子組播74X

全定序原子組播7qq

④發送者失效

當發送者失效時，必須選一個接替者，以便使工作能夠繼續

下去。每個成員維持一個組播消息的歷史記錄表，并執行組內成

員之間的定期主動回復（如：報告當前接到的最大消息標志），

以減少歷史紀錄的長度。

⑤多次應答帶來的效率問題的解決方法

i.延遲發送

網絡結點的通信處理程序收到一組播消息后，暫時不向自己

的應用程序發送，而是等到收到其它的消息確認本次組播滿足原

子性和定序等要求后才發送。

10

ii.被動回復

每個發送者擁有一個計數器，每個消息帶有一個自身對應的

計數值，當接收者發現中間斷檔時，發詢問信息。

5、組播通信實例------個簡單交易系統

2-3RPC

RPC(RemoteProcedureCall)是B.J.Nelson提出的(博士論文:

RemoteProcedureCalls),用于實現對非本地結點上的過程的調用,

是基于Client/Server的。與一般的過程調用類似，但因其“遠程”

而需要更復雜的通信支持系統。

11

RPC通訊模型洞P32]

ClientServer

V______________楚金--1

發出遠程過I程請求------------接收調用信息提取參數并分析之

等待回答f相應過程----------調用所指過程

FLz*

接收服務結果回送執行結果

二、RPC的結構與實現[何「35]

RPC的實現構架如下圖

CallSendSendCall

其中，Stub用來實現具體的通信準備，由系統對應RPC自動生

成，有的書譯為“存根”

RPC機制主要包含Stub、綁定、控制部分、傳輸部分。其宏觀

實現過程如下圖。包括入下幾步：

1、用戶以本地方式調用系統產生的Client方的一個Stub過

程；

2、該Stub將用戶提供的參數按照網絡通信的要求封裝成消

息包，并將它們發給Client方的RPCruntime；

3、RPCruntime將它們發送到指定結點；

4、遠程RPCruntime接收此消息，并將此消息發送給相應

Server的Stub；

5、Server的Stub拆封消息，形成被調過程p要求的形式，

并調用P；

6、p按照所獲參數進行執行，并將結果返回給Server的

Stub；

7、Server的Stub將此結果封裝成消息，發送給Server的

RPCruntime,然后逐級地傳送給用戶。

RPCruntime傳輸部分的主要功能

1、提供對網絡傳輸層協議的選擇；

2、建立放邏輯信道，發送/接收消息；

3、管理RPC中的消息緩沖。

13

用戶代碼用戶Stub

V

RPCp(L>-—根據p建立Client和Server的綁定RPC的runtime（內核）

RPCruntime控制部分的主要功能

1、確定RPC中消息的方向；

2、結點之間會合與進程同步（等待應答/服務請求）;

3、狀態信息處理。

14

三、相關問題處理

1、遠程過程所在結點的獲取方法

i.系統生成Stub時，一同記入，這種做法不太靈活；

ii.執行調用前，首先執行組播，以獲取結點信息。因而導致

這種方法比較慢；

iii.系統維持一個表，記載遠程過程的位置。其內容由遠程過

程所在結點提供。

2、RPC的語義問題

數據格式轉換禁止使用指針考慮調用者/被調用者失效

由于遠程傳輸所帶來的可靠性問題，RPC實現的不同可能

導致結果不同。以下是四種常用的語義定義。

i.Last-of-many最后一次結果有效;

ii.At-most-once僅執行一次（成功返回一次、或者不

成功返回）;

iii.At-least-once成功返回至少一次;

iv.Exactly-once正常情況下，恰好返回一次。

3、同步RPC與異步RPC

15

同步RPC需要等待；異步RPC利于并行，但是需要一個會合

點(Rendevous)

2-4多對多RPC

一、總體結構

二、作用

當一個Client的某項請求需要多個Server才能完成時，它將此請求

以“服務請求”的方式發給這些Server,為了保持Client一方的一

致性，在Client與這些Server之間設置一個agent-group,來代理

Client完成有關任務。

三、實現過程

Client用m2m方式發送調用請求

16

Agent-group等待Client的請求，并將獲得的請求置于一個管道中

分配線程：取出管道中的服務請求，并將其放入相應的請求隊列

前調hook將一■個請求發送給Server-group,一■個Sever-group

中有多個hook提交的申請

Server-group執行服務請求，返回結果。

Agent-group收集線程：讀取返回結果，由回調hook過濾，重組

數據，將結果返回給Client

Client用do-sv-chk檢查返回結果（在結果緩沖區中）

四、執行過程示意

ClientAgent-GroupServer-Group

等待Client的調用，并將其存于管道中

v

V分配線程:/執行服務請求

用m2m乎送多用多調產取出管道中的請求，放入相應隊歹y

v

待返回結果

V

用do-svZrhk檢查返回結果前調hook將一請求發給Ser^er-Group/

I個/

結果'緩沖區收集線程：，/

、'、、"讀取返回結果，由回調hook過濾，事由

收集線程重組，在調用完成時，返回結果

2-5異步分布進程通信模型

17

一、邏輯通道分類

同步通信：進程p發出消息后，等待進程q的應答，所以，進程q

接收消息的順序與P發送消息的順序是相同的。但是，同步通信限

制了進程的并發性。

異步通信：往往采用信箱技術。進程p只將消息發到指定信箱，這

樣，P和q之間的通信可以通過一個邏輯通路（通道）來實現。這

雖然提高了進程的并發性，但是，后發的消息可能先到—稱之為

“超越”。

按照對超越行為的約束的不同，通道可以被分成4種。

1、無限制：可以任意超越；

2、FIFO：不允許發生超越；

3、F通道：對消息分類，不同的消息用有不同的超越權限。

a）t類（兩端堵塞）：既不能超越別人，也不能被別人超越；

（相當于2——FIFO）

b）。類（普通型）：既可以超越別人，也可以被別人超越；（相

當于1——無限制）

c）b類（向后堵塞）：不可被后來者超越；

d）f類（向前阻塞）：不可以超越先來者。

4、層次通道

a）將通道分層，各層有自己的類型

b）較低層（號小）者優先級高

18

m4mi

較低層

m4>mi可以超越m3、m4

二、通道代理模型(PCAP------Process-CanneIAgent-Process)

思想：引進一個ChannelAgent來處理異步通信的“超越”問題。p

將消息發給通道代理Cpq,q將要接收的要求也發給Cpq,Cpq根據有

關規定和要求將P送來的消息送入q的信箱。

1、通道語法規則(略)

設<m“m2,……,mn>是一個消息系列，G是通道語法規則集，它

由一組超越規則組成。可傳送集D為所有的可以傳遞的消息

D={ml3SbS2,S3,使得<S2mSi>n/<S3m>}

其中，Si可以看成是其它的消息序列。我們用。、f、b、t分別表示F

通道的相應消息，貝IJF通道的4條規則可以表示為：

<S2OjOjSi>―><S2OjOjSi>

<S2ofSi>-><S2foSi>

<S2boSi>-><S2obS1>

<S2bfSi>-><S2fbSi>

用Gu表示第u層的通道規則、&表示層間規則，則可以用下式表示

層次通道規則

19

Gh=UGuURh

2、PCAP算法

約定：m--------■個消息

V——q進程接收消息的要求

Sm——發送序列

Sv------由V組成的要求序列

1、if收到p發來的消息m,thenSm=mSm；

2、if收到q發來的要求V,thenSv=VSv;

3、ifSvW①&SmW①then

3.1V=First(Sv)；

3.2Whilemm￡V&mGSm&m可發送do

3.2.1V=First(Sv)；

3.2.2Sm=After(m,Sm);

3.2.3V=V-{m};

3.2.4Send(m,q)

思考題：

1、設計一個令牌的實現方法。

2、設計一個消息槽的實現方法。

3、如何理解下列句子：進程的同步型通信使得進程的通信與

同步同時完成，進程的異步通信則幾乎將通信和同步完全分

20

開。

4、為什么要通過設置消息傳遞原語來實現消息的傳遞？

5、總結全定序原子組播所能解決的問題及其為了提高效率

又采用了那些策略？

6、客戶stub是系統根據"remotecall”而生成的，服務器stub

應該如何產生？這項工作由誰去做？

7、遠程過程調用如何獲得過程所在的節點？你知道哪幾種

方法？它們各有什么優缺點？

8、為什么一個進程同時調用多個節點的過程是叫“多對多

RPC”，而不叫“一對多RPC”？

9、為什么討論“多對多RPC”模型時只是討論了一個Client

調用多個Server的問題？

21

第3章分布式協同處理

主要內容：時間校準、分布式算法、選擇算法

學時：學'*6

重點：分布式互斥

難點：NTP,分布式互斥

3-1時間定序與時間戳

一、物理時間校準

協調宇宙時間UTC：在分布式系統中，由于有多個主機存在，

各主機的時鐘是有一定的差異的，雖然這個時鐘可以通過使用一

個稱為UTC的接收器來校準，但是，消息在網絡中的傳送是需

要時間的。因此，當一臺機器使用服務器所給的時間時，要給一

個相應的誤差估計。

1、Cristian時鐘同步方式----服務器時間

如圖所示，進程p向時間服務器s申請系統時間（mQ,

nV至少用時min到達s,s在時刻t用叫傳回給p,至少用時min,

X、A2是網絡的其他因素占用的時間：

mt

客戶進程時間服務器

p發送mrs返回mtm倒達

mt中含有時間t

T?>und=min+A1+A2+min

一般地，P考慮用t+Twnd/2估計當前時刻，所以，它將自己

的時鐘置為t+Tr。11nd/2，此結果的精度為土[Tround/2-min],也就

上圖是按照A/A2畫的，一般地，應該用|A「A2|/2代替（△一

A2）/2

上述計算是基于系統中只有一個時間服務器的，當系統有多

個時間服務器時，用戶可以從任一個服務器獲得時間。

2、Berkeley算法——容錯平均時間

1989年，Gusella與Zatti提出一種“容錯平均值”時鐘：在

系統中有一個主機，它定期輪詢需要同步時鐘的從機，根據獲取

的t+Twnd/2估計從機的本地時間，最后將所有從機的本地時間

的平均值作為系統時間。

Gusella與Zatti作了一個15臺機器的實驗，利用他們所給的

算法，系統在20?25ms內實現同步。最大來回時間為10ms,局

2

部時鐘偏差率＜2*10-5。

3、網絡時間協議（NTP）

此協議被用來保證Internet中時間服務器的時鐘同步。時間

服務器被鏈入一個邏輯分層結構的網絡中。主服務器直接連接時

間資源（如：UTC接收器），以主服務器為根，實現分層同步。

當某個服務器發生故障時，可以進行適當替換。

服務器B

服務器A上層結點對下層結點實施控制

NTP可以用組播、過程調用、對稱等三種模式實現同步:

1）組播

某一/幾個服務器定期向局域網上運行的服務器廣播時間，

后者收到時間后，通過加上一個估計延遲來設置自己的時間

T=t+min

用于高速局域網，但精度不高。

2）過程調用

類似于Cristian方法。精度比組播要高。T=t+TrOund/2

3

3）對稱模式

一個NTP消息中包含3個時間：發消息者接受的上個NTP

消息的發出時刻、到達時刻，本消息的發出時刻。如：mi中含有

Tj-5、1-4、Tj.3，m2中含有Tn、一2、T^o

A發出NTP消息m”B回應NTP消息m2，設6是B相對于A

的偏差（B比A快6秒），mi、m2的實際傳輸時間分別為t1、t2,

從而，

JTj-2=Tj.3+tj+8]§=Tj.2-Tj.3—tj

Tj=Tj-i+68=Tj-i-Tj+t2

26=Tj.2-Tj.3-ti+Tj.i-Tj+ti

8=[Tj.2-Ti3+TM-Ti]/2-[ti-12]/2

Tj.3+Tn-T,]/2-[ti+tij/l+ti

=[!\_2-Tj.3+TM-Tj]/2+[ti+tij/l-ti

令

Ai=[Ti.2-Ti3+TM-Tj]/2

di=[t!+t2]=Ti-TM+Ti.2-Ti.3（注意：雖然根據T”Ti4>Ti2>

"3可以求出ti+t2,但是不能分別求出t1、t2）

從而有

6=Ai+dj/2-tj<Ai+dj/2

8=Ai-dj/2+t2>Ai-dj/2

這就是說

4

A1-d,/2<8<Ai+dj/2

這說明，可以根據3和&估計6的值。一般地，系統將最近的

8個vAi,&>記下來，用與最小的人對應的Ai來估計6。

二、邏輯時鐘

1、事件定序關系

1978年，Lamport指出，由于在分布式系統中不能實現完美

的時鐘同步，一般就不能用物理時鐘給兩個事件定序，但可以用

因果關系來描述進程中兩個事件發生的順序。Lamport提出了

HB(Happen-Before)關系。對于事件e1、e2,

①如果存在進程p,P包含ei、e2,且ei在e2前發生，貝！］e2；

②如果存在消息m,e1為Send(m),e?為Receive(m),貝！Jeee2；

③如果ei-?e2&e2->e3,貝1處一>e3；

④如果ece?,ei均不成立,則和e2可以并發：?4隹；

2、進程的邏輯時鐘一Lamport校正算法(僅用于排序)

每個進程P有一個邏輯時鐘(單調增長的軟件計數器)Tp,則

有如下協議：

①在進程p的一個事件發生前，執行Tp=Tp+l；

②當進程p發送消息m時，在m上攜帶時鐘值：(m,Tp)；

③當進程q接收消息(m,Tp)時，取Tq=max{Tq,Tp}+1實

現進程之間的協調

5

3、邏輯時鐘排序與HB（HappenBefore）的關系

①如果pfq,貝UTpVTq；

②如果TpVTq,貝！Jpfq不一定成立；可能有p||q。

4、邏輯時鐘與事件的全排序

按照進程的邏輯時鐘協議，在一個系統中，不同的事件可能

擁有相同的邏輯時間。所以，一次難以獲得系統內的全排序。為

了獲得全排序，還需要將“進程”這一因素加進去。這樣，我們

可以用序對（Tp,Pa）來進行定序。其中Tp為時間的邏輯時鐘值,

Pa為進程P的優先級。我們稱之為時間戳。在需要排序時，當邏

輯時鐘值相同時，就比較它們的優先級，優先級高者優先。

3-2分布式互斥

本節討論臨界區的互斥保護問題。——資源的互斥使用

要求：（1）安全性（2）可用性（3）定序

一、基本假設

①在分布式系統中，每個進程是平等的。它們都擁有申請和

“審批”資源的權利；

②系統有n個結點，結點和進程一一對應；

③進程按照發送者發送消息的順序接收消息；

④每條消息在有限時間內是可送達的；

6

⑤每個進程可以給其它任意進程發消息。

二、集中式算法——可以理解為一個資源有唯一的協調者,不

同的資源有不同的協調者

將臨界資源的互斥問題交由一個進程統一管理。我們稱此進

程為協調者進程。

算法：

1、等待新消息

2、如果是Release消息，則查看Request隊列是否為空。

a）如果該隊列空，則轉1繼續等待下一個請求；

b）如果不空，則從該Request隊列中取下一個請求，并給

其發送者發Reply消息。轉1等待下一個請求；

3、如果是Request消息，則查看臨界資源是否有效。

a）如果有效，則給發送此Request的進程發Reply消息，

轉1繼續等待下一個請求；

b）如果無效，則將此Request掛到相應隊列中；轉1等待

下一個請求；

4、進行出錯處理，然后轉1。

討論：

①每完成一次臨界區操作，要發Request、Reply>Release

三個消息;

7

②當協調者進程故障時，需要安排新進程代替它：選一個

進程；通知其它進程；建立相應隊列；恢復工作。

三、Lamport算法

1978年，Lamport提出了第一個分布式算法。

基本思想：資源是大家的，因此，要想獲得某一資源的使用

權，必須征得大家的同意；面對沖突，則按“定序”進行處理。

主要數據結構：每個進程擁有一個全局請求隊列。

算法：

1、當進程p要進入臨界區時，向系統中的所有進程發送

Request(Tp,p),并將此請求放入自己的請求隊列；

2、當進程q接到此消息，將其放入自己的請求隊列，并返回

一個帶有時間戳的Reply(Tq)；[Tq>=Tp+l]

3、當下面的條件成立時，p進入臨界區，否則p等待：

a)Request(Tp,p)在p的隊列的隊首；

b)p收到全部其它進程的時間戳遲于Tp的Reply。