高級操作系統(tǒng)-筆記

高級操作系統(tǒng)-筆記

?分布式系統(tǒng)簡介

?誕生：強大的微處理器（超大規(guī)模集成電路）+高速計算機網(wǎng)絡+（用戶對計算機要求越來越高越

來越復雜）

?定義：分布式系統(tǒng)是多個獨立計算機的的集合而在用戶看來是一臺單獨計算機，硬件上獨立自治，

軟件在用戶看來看作單一系統(tǒng)

?三個特性：模塊性，并行性，自治性

?目標：增加處理能力、可拓展、可靠、資源共享

?和并行計算相比

?GPU貴，廉價CPU集群便宜

?并行：指令級、CPU距離1m內、總線速度忽略

?分布：任務級、CPU距離1km內、速度10/100/1000...Mbps、可靠性、可拓展、靈活

?和獨立PC相比優(yōu)勢：數(shù)據(jù)共享、設備共享、通訊方便、靈活性強，缺點：軟件少，網(wǎng)絡通信引入

的問題網(wǎng)絡安全

.和計算機網(wǎng)絡的關系，相同之處：拓撲結構（異構通訊）（底層硬件和通信軟件沒有區(qū)別），不同

之處：全局管理、并行操作、自治控制要求更高

?DS硬件分類（弗林分類）（指令流數(shù)目、數(shù)據(jù)流數(shù)目）SISD單處理器計算機、SIMD向量機、

MISD無實例、MIMD所有分布式（因此弗林分類對DS沒意義）

?DS分類（共享存儲器多處理器/無共享存儲器多計算機、總線型/開關型、（按傳輸速率）緊耦合

（主要是并行）/松耦合（主要是分布））

?多CPU總線型：高速母板多CPU，問題：CPU過多總線過載性能急劇下降，可以用cache減

少訪存。引入一致性問題，可用高速緩存寫解決（寫cache也寫mem,其他cache監(jiān)聽總線

更新寫）提升至U64個CPU

?多CPU開關型：（為了支持更多CPU互聯(lián)）

?交叉桿結構：交叉點連接CPU和mem，優(yōu)點：多CPU同時訪存，缺點：訪問同一存儲要

等待（阻塞）。nCPUnMem交叉開關nA2個。

?多級互聯(lián)：最經(jīng)典的是NXNOmega,logN開關級，每級N/2個開關，總開關數(shù)

NlogN/2，問題：延遲（開關級有延遲）、阻塞（經(jīng)過同一開關級）N!個置換中只有

23N/2）個不阻塞。

?除了Omega還有baseline和intercube網(wǎng)絡，旋轉180°就叫OmegaA-l,

AA以上六個在拓撲上等價。

baseline-l,intercube-l0MINs

?2n-l級的baseline+baselineA-l網(wǎng)絡（即Benes網(wǎng)絡）對N!置換都是非阻塞的。

（共用一層節(jié)點）而2n-l的Inercube+IntercubeA-l及Omega+OmegaA-l和他

們的2n-l級Benes網(wǎng)拓撲不等價，沒法證明N!不阻塞。（只有n=3Omega已經(jīng)被

證明）

?拓撲序列相等則拓撲等價，前n級可以6個中任意兩種，后面k級網(wǎng)可以實6種n級

網(wǎng)任意k級？？？

?緊耦合共享存儲多處理器，比較困難昂貴

?多計算機總線型，不共享存儲器通信量會少，不需要高速總線，一條低速LAN足夠

（CSMA/CD）

?多計算機開關型，網(wǎng)孔/超立方體結構，二維的超立方體叫網(wǎng)孔，n維超立方體每個節(jié)點和

n個CPU相連，只有相鄰CPU可以直接通訊，其他的要跳，最長路徑隨著維數(shù)成對數(shù)增

加？？？（網(wǎng)孔隨著CPU數(shù)目平方根增加）

?分布式系統(tǒng)軟件重要性遠超硬件重要性。操作系統(tǒng)遠不象硬件那樣清晰明了，因為，軟件本身就是

不明確的。但依舊將軟件分為松散耦合和緊耦合，與底層硬件分布類型無關。

?網(wǎng)絡操作系統(tǒng)，松散耦合硬件松散耦合軟件。它是用戶和網(wǎng)絡之間的一個接口，它除了應該具

備通常操作系統(tǒng)所應具備的基本功能外，還應該具有聯(lián)網(wǎng)功能，支持網(wǎng)絡體系結構和各種網(wǎng)絡

通信協(xié)議，提供網(wǎng)絡互連能力，支持有效可靠安全地數(shù)據(jù)傳輸。（早期只有基本功能：通訊、

文件、打印等?，F(xiàn)在功能不斷擴展，性能大幅提高。）

?特征：硬件獨立、多用戶、支持網(wǎng)絡實用程序及管理、支持多種客戶端、提供目錄服務、

提供多種增值服務、可操作強（不論硬件軟件都可互聯(lián)）

?類型：集中模式（單主機多終端）、c\s（服務器集中資源管理與安全控制，客戶端請求

服務）、p2p對等模式（每臺計算機同時是客戶端和服務器）

?網(wǎng)絡中每臺計算機可以不同構，至少信息交換格式保持一致，每臺計算機高度自治性。

?分布式，緊耦合硬件上松散耦合軟件，給用戶形成單系統(tǒng)映像

?特征：統(tǒng)一的全局進程間通訊、全局保護方案、進程管理在所有機器上相同、所有機器統(tǒng)

一的一組系統(tǒng)調用、相同的文件系統(tǒng)、除了受保護和安全限制每個文件在任意機器可以訪

問、CPU必須運行相同內核、全局文件系統(tǒng)、允許每個內核來管理它自己的存儲器（換頁、

進程調度等都應該本地內核管理）

?多處理器分日攜作系統(tǒng)：緊耦合硬件緊耦合軟件，（多CPU共享Mem），使用單一運行隊列

調度所有進程。如時間片輪換系統(tǒng)。進程優(yōu)先分配給最近使用的CPU（如果很多空閑CPU）,

如果某進程被I/O阻塞則先掛起（時間很長）或者等待（時間很短）。

?DS設計問題

?透明性：將DS看作一個整體的分時系統(tǒng)。

?高層次透明：對用戶透明，低層次：對程序員透明（很難）（遠程文件訪問和本地文件訪

問不一樣）

?體現(xiàn)方面：位置透明（不知道軟硬件資源在哪）、遷移透明（資源隨便改動位置名字不

變）、復制透明（不知道多少文件副本）、并發(fā)透明（不知道多用戶）、并行透明（不知

道多計算機并行執(zhí)行，最難實現(xiàn)。解決方法：編譯器、運行系統(tǒng)和操作系統(tǒng)來合理地利用

多個計算機的并行性而不是讓用戶自已來安排）

?靈活性：DS系統(tǒng)結構問題，大內核（什么都能做）/微內核（甚至一個服務一個內核）

?微內核：基本服務：進程間通訊、存儲管理、底層進程管理調度、底層輸入輸出。優(yōu)點：

高度模塊化、容易安裝調試新服務

?大內核：性能好

?可靠性：系統(tǒng)的可靠性=每臺計算機可靠性的布爾或（因為很多DS工作需要一定的正常服務器,

所以很多時候使用布爾與）

?以下幾個方面：

?通用性（可用性可以通過設計來提高而不是采用大量關鍵部件同時工作來獲得）（比如冗

余）（高可靠必須高可用，數(shù)據(jù)決不就是或篡改，拷貝越多可靠性越高，但不一致的可能

性越大）

?安全性，文件及其他資源被保護以免被非授權使用

?容錯：服務器崩潰后的信息恢復

?性能：度量（響應時間、吞吐率、利用率、網(wǎng)絡容量消耗）

?提高性能：減少通訊、考慮計算粒度（有許多小計算需要高度交互的作業(yè)不要分布運行）

?可縮放性，硬件拓展問題，希望算力隨著數(shù)目線性增強（但現(xiàn)實總會飽和，且過多會下降）如

果一個DS算法效率E,當數(shù)目n達到頂點M后，隨著n變多性能下降平穩(wěn)，則稱該DS算法

可縮放性好。

?分布式系統(tǒng)同步

?進程通訊問題（并非共享存儲通訊）

?特性：信息分布在多臺機器、進程根據(jù)局部信息決定、對系統(tǒng)中任意機器失敗可以容錯、不存在公

共時鐘或其他全局時間源（前三點決定不允許單一節(jié)點收集全局信息，第四點中單機系統(tǒng)時間確定,

但DS不一定一致，時鐘同步非常重要）

?邏輯時鐘同步

?時鐘：記錄時鐘的電路，相關的倆寄存器：計數(shù)器，保持寄存器。

?邏輯時鐘，不需要在事件發(fā)生的確切時間上達成一致，只需要在先后順序達成一致

?物理始終，不僅各個節(jié)點順序一致，且與實際時間的誤差不超過某個值

?Lamport

?a->ba在b前發(fā)生，或者a發(fā)送b接受，a->b&b->c則a->c,并發(fā)：x不->y且y不-

>x,事件分配所有進程認可的時間值C（-）,只增不減

?每個消息有自己的發(fā)送者時間，到達時，接收者時間更小則更新為發(fā)送者時間

?本算法假定任意兩個事件發(fā)生時間之差至少為1,包括單機連續(xù)收發(fā)

?時間值.進程號

?賦值方法

?在同一進程中，如果事件a在事件b之前發(fā)生，則C(a)<C(b)

?如果a和b分別是一個消息的發(fā)送和接收事件，則C(a)<C(b)

?對所有事件a和b,C(a)/C(b)

?物理時鐘同步

?當UTC時間為t,則機器p上時鐘值為Cp(t)o在理想情況下，對于所有的p和t,Cp(t)=t。換句

話說,dC/dt=L如果存在某個常數(shù)p使得：l-pvdC/dtwl+p則該定時器的誤差在允許的范

圍之內。常數(shù)p由廠商設定。有時也稱之為最大漂移率。

?Cristian

?假定有一臺WWW接收器作時間服務器

?如果兩個時鐘朝著UTC兩個相反的方向漂移，則在它們同步后的At時刻，它們之間的相差為

2pAto如果操作系統(tǒng)的設計者要保證任意兩個時鐘相差不超過5,則時鐘必須每b/2p秒

同步一次。

?每臺機器周期低于8/2p秒地周期請求時間服務器獲得標準時間C_UTC,問題：時間不可

以調后，如果比UTC快則如何？解決：中斷等待直到對準。問題：消息通訊也需要時間，

解決：機器記錄詢問和回答時間，時間差大于某個閾值就丟棄

?Berkeley時間服務器輪詢每個服務器時間，取平均再分發(fā)給所有服務器，時間服務器需要定時

手動調整。更精確的做法是考慮延遲。

?非集中同步

?時間劃分為固定長度地再同步間隔。第i間隔從TO+iR開始至I」TO+(i+l)R時刻，TO是過去

認可的某時刻，R是系統(tǒng)參數(shù)。每個間隔開始所有機器廣播自己的時間值，廣播后收集S

間隔內其他機器的時間值，直到收集齊計算平均值，校正。改進：去掉m個最大值和最小

值、考慮網(wǎng)絡中延遲

?分布式互斥

?集中互斥算法

?一個進程要讀寫共享數(shù)據(jù)需要進入臨界區(qū)(和其他進程互斥)

?選擇一個進程當作協(xié)調器，誰想進臨界區(qū)就請求協(xié)調器。其他再申請則阻塞對申請排隊，

前一個進程釋放發(fā)送給協(xié)調器，然后解除后一個阻塞，進入臨界區(qū)。

?分布式互斥算法(Ricart&Agrawala)2(n-l)條消息

?某進程進入臨界區(qū)則建立消息，包含臨界區(qū)名字、進程號、當前時間，發(fā)送個其他進程

(也可以組通訊廣播)。假定通訊可靠。某進程收到請求則

?若不在且不想占用該臨界區(qū)，發(fā)送0K

?已在臨界區(qū)，不回答且把該請求排隊

?相進但沒進，比較時間戳，先來后到轉入前兩情況

?發(fā)送者等到所有0K反饋就進入臨界區(qū)，釋放時發(fā)0K。如果同一個臨界區(qū)有其他進程排隊,

就發(fā)送0K給該進程，并移去隊列頭。

?當某個節(jié)點崩潰則整體算法無法工作，解決：沉默改為恢復拒絕消息，超時視為崩潰

?無死鎖無餓死無單點失?。▽δ彻?jié)點崩潰敏感）

?分布式互斥算法令牌環(huán)算法O~n-1個消息

?每個進程進行統(tǒng)一編號，構成邏輯環(huán)

?初始化。獲得令牌，令牌循環(huán)一圈，當進程收到令牌，檢查自己是否申請臨界區(qū)。如果時

則進入，離開后就傳給下一個鄰居，否則直接給鄰居。

?檢測令牌丟失很難，檢測崩潰容易，檢測到下家崩潰就重新構造環(huán)（k->k+2）（這也說明

需要每個節(jié)點存儲環(huán)結構）

?無餓死，也對崩潰敏感

?分布式選舉算法

?每個進程都知道其他進程號，但不知道其工作狀態(tài)。選舉算法目的是，選舉開始后，確保所有

進程統(tǒng)一的基礎上選出協(xié)調者

?Bully算法

?進程P發(fā)現(xiàn)協(xié)調者不響應時，發(fā)起選舉。

?向所有進程號比他大地進程發(fā)送ELECTION消息

?無人響應則P獲勝成為協(xié)調者

?若有更大的進程響應，則它接管

?總是最大進程號的進程獲勝

?進程只會從比它小的進程收到ELECTION,獲勝后新協(xié)調者將獲勝消息發(fā)給所有進程。同

時也能知道大的

?環(huán)算法

?每個進程知道自己的上下鄰居，下鄰居失效就繞開

?發(fā)送者把自己的進程號加入表中繼續(xù)轉發(fā)，直到始發(fā)者收到自己的進程號。發(fā)送協(xié)調者消

息再繞環(huán)一次，通知誰是協(xié)調者。

?轉發(fā)的時候各個進程就可以判斷誰暫時是最大的

?原子事務

?更高級別的抽象，算法和進程并行層面。

?多進程模型，要么全有要么全無

?磁帶系統(tǒng)擁有原子事務要么全有要么全無的特性

?在線數(shù)據(jù)庫系統(tǒng)的原子事務設計，要么操作全執(zhí)行要么都不執(zhí)行，失敗后需要能夠返回最初狀

態(tài)

?事務模型

?假設：獨立進程、隨機出錯，通訊可靠，存儲器可靠

?事務原語：BNGIN_TRANSACTION標記開始，END一標記結束并提交，ABORT.取消事

務并恢復舊值，READ讀，WRITE寫

?事務中允許普通語句和過程調用（庫過程，系統(tǒng)調用…）

?BEGIN_...END_為事務體,要么全有要么全無

?特性ACID:原子性（不可分割）、一致性（不破壞系統(tǒng)的恒定，比如銀行的資金恒定）、

孤立性（并行事務不干擾，并行提交但會根據(jù)系統(tǒng)以某種順序執(zhí)行）、持久性（一旦提交

永久存在）

?嵌套事務，持久性針對最頂層事務

?事務提交，DS上的提交需要多機寫作，兩階段協(xié)議：險些提交日志，再發(fā)送給相關進程請

求提交，收到全部響應后決定提交否則中止，并寫入日志，通知下屬。如果協(xié)調者初始化

日志后崩潰，可以恢復后繼續(xù)工作，如果某下屬崩潰，則協(xié)調者給他不斷發(fā)消息。如果協(xié)

調者后面崩潰了，則查看日志決定自己干什么。

?并發(fā)控制算法

?加鎖

?對文件加鎖，鎖一般由事務系統(tǒng)請求、釋放，不需要人為干預。

?可以用集中加鎖管理程序實現(xiàn)，也可以各機本地管理實現(xiàn)。

?讀鎖共享，寫鎖互斥。

?鎖的粒度越小越精確，更高的并發(fā)性，但開銷更大，更容易死鎖。

?二階段鎖：第一個階段申請，第二個階段釋放

?死鎖：二階段也會死鎖。解決方法：按序請求加鎖防止保持-等待循環(huán)，死鎖掃描，

計時擁有鎖的時間超過正常時間判定死鎖

?樂觀并發(fā)控制

?現(xiàn)實中沖突非常少

?沖突處理，記錄文件寫歷史，提交時檢測其他事務是否修改過本事務文件，本事務

終止否則提交。

?適合基于私有工作空間的情況，各個事務獨立修改自己文件互不干擾。結束后新文

件要么提交要么釋放。

?優(yōu)點：避免了死鎖，允許最大限度的并行

?缺點：有時會失效，所有事務需要重新運行，重負載的情況下失效可能性會直線上

升

?時間戳

?BEGIN一時分配一個時間戳，每個文件由讀取和寫入的時間戳，判斷最近讀取寫入。

如果讀寫時間戳早于當前事務時間戳，則說明正常運行，否則中止，事務開始的太

早。

?不會出現(xiàn)死鎖

?死鎖

?通訊死鎖：A->BB->CC->A出現(xiàn)死鎖，資源死鎖：互斥訪問資源

?處理方法

?鴕鳥算法：忽略死鎖，很多系統(tǒng)沒有系統(tǒng)級思索機制

?避免，不在DS中采用

?檢測消除

?DS死鎖檢測

?集中式

?各機有自己的資源圖，中心機器有整個系統(tǒng)的資源圖，檢測到回路（發(fā)

現(xiàn)死鎖）就中止一個進程。

?全局信息維護：本地增刪弧同時發(fā)送給全局資源圖、本地增刪弧周期性

發(fā)送給協(xié)調者（發(fā)送消息更少）、協(xié)調者需要時主動去請求

?由于更新不及時會導致假死鎖，釋放的消息來得晚，全局形成回路。解

決方法：使用lamport提供時間戳

?分布式

?Chandy-Misra-Haas

?等待者P0發(fā)送探測消息給占用資源進程P1,（0,0,1）（被阻塞進程，

發(fā)送者進程，接收者進程）

?接收到消息，如果本進程也在等待，則更新消息，字段2改成自己，3

改成占有等待資源的進程號，然后發(fā)送給占有資源的進程。有多少等待

就發(fā)送多少消息。

?若消息回到了字段1的進程，則說明存在回路

?DS死鎖處理，最初發(fā)送探測消息的進程自殺、把進程號添加在探測消息尾部,

回到初始發(fā)送者就看誰的進程號最大，請它自殺（或用其他方法選出一個犧牲

者）

?預防，很困難

?不理想的方法：只允許進程占有一個資源、進程開始申請所有資源、申請資源

嚴格增序

?基于時間戳

?Lamport時間戳

?等待-死亡算法只允許老進程;新進程等待，否則死亡

?受傷-等待算法允許老進程搶占資源，被搶占的中止

?等待-死亡算法會造成新進程不停的中止

?分布式路由算法

?通訊延遲：拓撲結構、交換(存儲轉發(fā)(分組交換，用時間步數(shù)通訊步數(shù)評估)、分割通過(減少

阻塞：電路交換、虛擬分割-通過(信道忙才存儲分組)蟲孔路由：將分組分片，忙則流量控制阻

塞))、流量控制、路由路徑(路由函數(shù)，依賴于目標節(jié)點和本節(jié)點、臨近節(jié)點、源節(jié)點等)

?最短路由算法

?Dijkstra源節(jié)點到所有節(jié)點的最短路徑

?D(v)為源s到v的距離，l(v,w)時v到w的而距離

?N={s},對每個不在N的節(jié)點v,令D(v)=l(s,v),還未連接的D(v)=inf

?找到w不屬于N，使D(w)最小，將w加入N,更新所有N中v,D(v)=min(D(v),D(w)

+l(w,v))

?重復找W,直到所有節(jié)點都在N里

?Ford分布式算法尋找到目標節(jié)點d的最短距離

?每個節(jié)點都有把(n,D(v))標記，n是目前最短路徑的下一個節(jié)點，D(v)是該節(jié)點到目標節(jié)點

的當前最短距離

?D(d)=0,其他節(jié)點(_,inf)

?對每個節(jié)點vHd,考察所有鄰居D(w),D(v)=min(D(v),D(w)+l(w,v))

?更新(n,D'(v))n是給你最小值的鄰居，更新D(v)

?所有節(jié)點每輪更新，也適用于異步系統(tǒng)(隨機更新)

?ARPAnet路由算法可靠、分布式路由算法(internet路由算法的前身)

?每個節(jié)點維護一個路由表，里邊記錄到所有其他節(jié)點的最優(yōu)路徑延遲。每隔固定時間間隔,

路由表傳送到所有臨界點，直達路由表在某一點穩(wěn)定

?某節(jié)點失效后，造成不期望的循環(huán)。不對接受節(jié)點進行標識，某些節(jié)點會接受無用消息。

?改進：路由表包含路徑而不是下一跳(開銷非常大)、路由表包含最近的I跳

?ARPAnet適用于所有拓撲類型，但是每個節(jié)點需要存儲路由表,且對某些特殊網(wǎng)絡效率太

低

?特殊網(wǎng)絡的單播路由算法

?雙向環(huán)

?消息沿一個方向轉發(fā)，方向由源節(jié)點根據(jù)目標節(jié)點的決定方向

?目標順時針近就順發(fā)否則擬發(fā)（m,des），收到此逆消息，自己不是目標節(jié)點，轉發(fā)。若自

己是des,存m

?二維算法，網(wǎng)格、圓環(huán)（二位圓環(huán)比網(wǎng)格多了周圍鄰接，n連著1）

?XY路由算法先沿著X維轉發(fā)，再沿著y軸轉發(fā)，最不靈活

?最短且完全適應路由，中間節(jié)點也找最短路徑

?折線路由，沿著45。前進，每個信道擁塞概率相同時最好

?最大最短路由，折線路由對圓環(huán)不最優(yōu)。選擇最大個數(shù)的最短路徑鄰居。但不一定最優(yōu)。

?點（邊）分離路徑，除了源節(jié)點和目標節(jié)點，兩條路徑無公共節(jié)點，則叫分離路徑

?超立方

?Q0是一個節(jié)點的退化圖，Qn=K2xQn-1,K2兩個節(jié)點的完全圖。Qn節(jié)點地址維

u=u_nu_n-l...u_l,,每個維度只取0/1

?最短路徑（海明距離）H（u,w）=\SigmaA{n}_{i=l}h（u_i,w_i）,h（a,b）=ifa=bthen

0else1

?兩個節(jié)點亦或u異或w=r,逐位異或

?uA（i）為反轉i維坐標

?算法

?當前節(jié)點u,目標節(jié)點W

?計算r=u異或W

?找到r的第i位維1,沿著i維轉發(fā),r_i=0,直到全Or

?多路徑路由，若兩個節(jié)點u和w再n維中海明距離是k,則u和w之間由n個點分離路徑,

其中k個長度為k的路徑，n-k個路徑長度為k+2

?特殊網(wǎng)絡多播

?多播：一個源像任意多個目標節(jié)點傳送同樣的消息，可以并行操作

?性能評估：通訊量（消息傳送到所有目標需要通訊的數(shù)目），時間（消息傳遞）

?多播路徑優(yōu)化問題、多播回路優(yōu)化問題、steiner樹優(yōu)化問題（包含所有目標點的給定拓撲的子

樹，求最小總長度的子樹）、組播樹問題（通往所有目標節(jié)點長度最短的子樹拓撲）。這些都

是NP問題

?基于路徑的算法

?構建哈密爾頓回路，每個節(jié)點經(jīng)過且只經(jīng)過一次

?根據(jù)回路把多播集合轉發(fā)出去

?若有鄰居在下個目標前但距離更近，則抄近路

?如果使用雙向鏈接，則只需要一個哈密爾頓路徑

?利用哈密爾頓路徑為每個節(jié)點定一個順序，相鄰節(jié)點等價于相差1,r(u)=r(x,y)=ify%

2--0thenyn+xelseyn+n-x-1

?高信道網(wǎng)絡：從低到高。低信道網(wǎng)絡：從高到低

?使用高信道網(wǎng)絡：

?由v和d,r(v)<r(d)分別是中間節(jié)點和目標節(jié)點

?若d是v的鄰居，就直接發(fā)到d

?若d不是,則選擇鄰居u使得r(u)=max{r(w)|r(w)<r(d)w是v的鄰居}

?低通訊網(wǎng)絡同理

?基于樹的算法

?Lan貪婪組播

?對于每個節(jié)點，輸入包含目標節(jié)點地址列表的信息

?如果自己的地址在列表，則保存該信息

?若列表非空，則決定把目標列表地址轉發(fā)到某些鄰居

?n位地址每一位都有一個計數(shù)器，計數(shù)器內容代表維數(shù)信息

?具有最大計數(shù)值的那一維會被選中，轉發(fā)到那個鄰居上

?剩余的目標中重復上一步，直到多播集合為空

?U網(wǎng)格算法

?定義字典序(x_l,y_l)<_t(x_2,y_2),x_l<x_2或者x_l=x_2andy_l<y_2

?邊分離性質，設P(n_l,n_2)是是n_l與n_2之間最短路徑，如果n_l<_tn_2<_t

n_3<_tn_4貝！］P(n_l,n_2)與P(n_3,n_4)

?假定源節(jié)點是(0,0)

?按照字典順序重新排列目標節(jié)點，把源節(jié)點放在前面

?把列表劃分成倆相等的子列表，源節(jié)點把多播消息發(fā)送給第二個字列表第一個節(jié)點

?重復分割

?如果源節(jié)點不是(0,0)則重新定義讓他變成(0,0)

?虛信道與虛網(wǎng)絡

?通過網(wǎng)絡分區(qū)避免死鎖，分割沒有回路的子網(wǎng)

?問題：資源申請和分配，目標：無死鎖、自適應、容錯

?方法：多個虛信道對一個物理信道、物理網(wǎng)絡分成多個虛網(wǎng)絡

?例：單向環(huán)多進程啟動可能會死鎖，解決：雙環(huán)路由，分為高虛信道和低虛信道，大進程向小

進程通訊用高虛，小進程先用高信道，到達最大節(jié)點后改用低信道

?不引發(fā)死鎖增強適應性

?虛信道類算法：引入足夠多的虛信道

?但虛信道太多會影響效率

?可以將網(wǎng)絡分為多個子集，每個子集都不包含相鄰節(jié)點

?比如黑白棋盤二維網(wǎng)格，黑白分別為兩個子集，消息從白到黑，虛信道標記加1,黑到

白標記不變。這樣虛信道數(shù)目少了一半

?一般化算法

?將網(wǎng)絡分為k個子集SI,S2，…,Sk互斥

?當一個消息從低標子集傳到高標則稱之正移動反之為負移動

?負移動，虛信道標記+1

?虛信道從1開始計數(shù)，所需信道數(shù)就是路由路徑中負移動的個數(shù)

?目標找到一個合適的k和相應的劃分，使得路由中負移動個數(shù)最小

?逃逸信道算法：同時使用兩種路由算法：標記為非等待的虛信道為完全適應性路由，限制

性但五四所的的路由標記為等待（逃逸）信道

?完全適應路由，使用標記為非等待的虛信道

?限制性無死鎖，使用等待的虛信道

?可選方案：開始用完全適應路由，出現(xiàn)阻塞切換到限制性路由

?問題：如何分配

?拓展1：等待信道被占用時使用非等待信道，增強靈活性、引入新的信道依賴性，

但難以得到無死鎖充分條件，算法判斷過嚴

?拓展2:不同的目標使用不同信道，可以得到無死鎖充分必要條件，但不同目標信

道間互相依賴，算法復雜

?部分自適應（對一小部分虛信道有效）和無死鎖路由算法

?轉彎模型

?平面自適應模型

?某一時刻將路由的自由度限制到幾個維度，降低對硬件的要求

?位降低虛信道數(shù)目犧牲全適應性

?容錯單播

?CPU增多失效的可能性會加大，目標：CPU失效仍有效，仍要有一定的適應性和無死鎖

?2維網(wǎng)絡與圓環(huán)

?基于局部信息，只知道局部的錯誤分布，比如鄰居

?錯誤區(qū)域，如果是凸性就可以設計簡單的容錯無死鎖路由，如果是凹則加入一些非錯誤

節(jié)點先轉化為凸

?安全/非安全節(jié)點

?初始化：錯誤節(jié)點是不安全的，非錯誤節(jié)點是安全的

?迭代：如果有兩個及以上非安全鄰居則自己也不安全

?擴展定義的迭代：安全節(jié)點在兩個維度都有不安全的鄰居則自己也不安全

?算法如果沒有錯誤阻塞則按照無錯的路由算法

?若X/Y錯誤阻塞，則在Y/X路由

?如果X錯誤阻塞，Y的距離接近0,則進行曲折路由

?隨便選擇一個Y方向，開始曲折路由，試著從X到達目標。繼續(xù)沿著X方向，直

到Y方向正確為止。即沿著出錯塊的邊緣路由。

?Y錯誤阻塞同理。

?基于有限全局信息，知道所有錯誤區(qū)域的位置

?最優(yōu)容錯路由算法

?設(0,0)為源節(jié)點，(i,j)是目標節(jié)點。如果沒有出錯塊過X和Y軸則存在一個最優(yōu)路

徑長度為|i|+[j|o

?上述結果對任何目標節(jié)點和源節(jié)點都成立，叫源是安全的。

?拓展：允許X與Y有出錯塊，只要到源的距離大于川和UI,源就是擴展安全的。

?探討適應性：假定源節(jié)點(0,0),目標節(jié)點(i,j),路由永遠向東北方向

?面向目標路由

?建立最短路徑區(qū)域RMP,畫從(i,j)到Y軸的線，遇到出錯塊就從南繞過去，X

同理圍起來的區(qū)域是RMP

?源通過最有優(yōu)路徑向目標發(fā)送初始信號，目標接到信號后，沿著RMP建立算

法回復信號，建立RMP。源在RMP內自適應路由算法，但遇到邊界剩下的路

由就得順著邊界走。

?面向源路由

?構建路徑A、B

路徑B

?目標位于A南側或者東側不能過A

?目標位于B北側的或者西側就不能通過B

面向源路由的步驟是這樣的：首先使用任何一個適應性最小路由，直到遇到出錯塊的一個

路徑（路徑1或路徑2）為止。

.（遇到路徑1的L,）,如果目標節(jié)點在路徑1的南側或東側，那么路由消息將一直留在七，直

第7章自適應、無死鎖和容錯珞由147

到到達出錯塊的4和4的邊界為止；否則將穿過

?（遇到路徑2的4）,如果目標節(jié)點在路徑2的北側或西側，那么路由消息將一直留在4,直

到到達出錯塊的4和4的邊界為止；否則將穿過4。

在上述方.法中，兩個虛信道足以避免死鎖。一個高單的方法是為東北和東南方向的路由使

用正向子網(wǎng)，對西北和西南方向的路由使用負向子網(wǎng)。在［53］中還討論了多錯誤塊情形下的出錯

塊信息的分布情況，

?基于其他故障類型

?解決非矩形凸錯誤塊，把出錯塊非出錯節(jié)點移出去，保持凸型

?初始化：所有出錯節(jié)點都是非活躍的，所有安全節(jié)點都是較活躍的，非安全節(jié)點開始都

是非活躍的

?迭代：如果一個非安全節(jié)點有兩個及以上活躍鄰居，那他也活躍。

?基本安全/不安全規(guī)則下的活躍節(jié)點

?擴展安全/不安全規(guī)則下的活躍節(jié)點

?超立方

?基于局部

?可達四種情況：出錯組件小于n-1,不確保有最優(yōu)路徑、小于n-1確保，無限制出錯不

確保、無限制出錯有最有

?出錯小于n-1不確保

?等位序列[dl,d2,...,dk],記錄當前節(jié)點和目標節(jié)點不同的所有維度

?消息格式(k,[dl,d2,...],消息，標記)k是剩余路徑長度，標記是繞道首選維度

?u是源節(jié)點，w是目標節(jié)點

?初始化：把(k,[dl,…,dk],m,0)送給P(u)，接收到(k,[dl，…,dk],m,tag)如果k

為。保存m,否則轉到中間節(jié)點處理

?中間節(jié)點處理:如果dj可以連通,就發(fā)送消息(k-l,[dl，…,dj-l,dj+ldk],m,tag)

給uAd」，如果等位序列節(jié)點無法聯(lián)通，對所有j,tag(dj)=

l,h=min{i:tag(i)=0},tag(h)=l,給u'h)發(fā)送(k+1,[dl,...,dk,h],m,tag)

?基于有限全局信息

?安全等級：每個節(jié)點知道周圍鄰居中失效節(jié)點大致數(shù)目，S(a)=k是節(jié)點a的安全等級，

就叫a是k安全的，一個失效節(jié)點是0安全的，是最低的安全等級，一個n-安全節(jié)點

(安全節(jié)點)是最安全高級別，如果kNn那么k安全就是不安全的

?計算安全等級

?節(jié)點a采集周圍節(jié)點S按升排列(S0,SL...Sn-l)

?如果對每個i,Si>=i,則S(a)=n

?若對每個i<=k-1S>=i&sk<k,貝！]S(a)=k

?算法：每個非出錯節(jié)點都是n安全，迭代n-1此達到穩(wěn)定

?如果一個節(jié)點是k安全的(k>0)則在k海明距離內，至少存在一個從該節(jié)點到任意

節(jié)點的海明距離路徑

?當源的安全等級不小于源和目標之間的距離的時候，可以保證最優(yōu)路由：在每一步

選擇最高安全等級的鄰居產(chǎn)生最優(yōu)路徑(當然必須是異或里為1的維度)

?只要存在一個安全等級不小于|s異或d|-l的鄰居，仍可以通過轉發(fā)到該節(jié)點實現(xiàn)

最優(yōu)路由，否則如果存在一個安全等級不小于|s異或d|+l的空閑鄰居，也可以將

消息轉給這個節(jié)點實現(xiàn)次優(yōu)路由，路徑長度|s異或d|+2

?基于擴展安全(略)

?容錯組播

?有限全局信息，超立方，使用安全等級

?如果沒有出錯組件，網(wǎng)和超立方中的大部分組播問題都是NP完全問題，需要啟發(fā)式方法。

在出現(xiàn)錯誤的時候，問題會更復雜。

?中間節(jié)點U（包括源節(jié)點s）向他合適的鄰居發(fā)送目標節(jié)點集合{Uul,u2，…,um}

?相對地址r_i=u異或u_i,|r_i|=r_i中1的個數(shù)，地址總和as=\Sigma_{r_i\inR}r_i,

相當于每一位單獨計數(shù)

?簡單策略

?對第一個目標節(jié)點u_i,當r_i第d位為1,則u發(fā)送rJA（d）給u（d）

?當口優(yōu)多個維度是1,則任選其一發(fā)送

?也可以對維進行優(yōu)先度排序，最大限度共享減少流量，所以需要地址總和。同時要避免

找錯及回退、繞路，需要使用安全等級。

?基于安全等級的組播算法SLBM，優(yōu)先級順序，安全等級越高，優(yōu)先級越高，同一個優(yōu)先

級就隨機

?修正的-MSLBM,相同優(yōu)先級的時候，哪個維度在as高，哪個維度的優(yōu)先級就高

?SLBM和MSLBM都是最優(yōu)的，但是MSLBM的消息總量更小

?分布式進程與系統(tǒng)機管理

?分布式系統(tǒng)模型

?工作站模型

?高速LAN拼接高級個人電腦

?有盤工作站，內部有硬盤

與無盤相比，網(wǎng)絡負擔更輕

分頁+臨時文件

需大量磁盤，費用較高

網(wǎng)絡負擔更輕

分頁+臨時文件+系統(tǒng)二進制文件

費用較高，二進制更新比較復雜

分頁+臨時文件+系統(tǒng)二進制文件網(wǎng)絡負擔更輕'也減輕文件服務器的負擔

+文件緩存費用較高，cache一致性的問題

完整的局部文件系統(tǒng)幾乎沒有網(wǎng)絡負擔，無需文件服務器

（網(wǎng)絡操作系統(tǒng)）失去透明性

?無盤工作站，使用一或多遠程文件服務器。價格低廉、容易維護、沒有噪音、對稱性（所

有終端都一樣）靈活性（增減方便），缺點是對網(wǎng)絡使用頻繁

?工作站模型優(yōu)點：用戶有固定的專有算力，有保障的響應時間，缺點是每個用戶的資源與

日俱增，很多機器是空閑的

?早期嘗試使用空閑工作站的軟件必須指定某臺機器、各機運行環(huán)境不一定同構、多用戶登

錄性能降低。

?目標：找到空閑機器、透明計算、機器不再空閑怎么辦

?服務器驅動

?遠程查看各機的注冊文件（各機空閑會把自己登記在公用注冊文件或者廣播空閑狀態(tài)其

他機器更新私用注冊文件）查詢開銷低但是維護成本大

?客戶端驅動

?調用remote時廣播發(fā)送請求，說明程序ID、內存需求、是否浮點等

?空閑工作站以負載為正比延遲回復

?透明計算：同構系統(tǒng)，系統(tǒng)調用時處理

?系統(tǒng)調用時的處理

?處理系統(tǒng)調用的錯誤

?處理只能在本機/遠程主機運行的系統(tǒng)調用

?讀鍵盤、寫屏幕/調整數(shù)據(jù)段大小、程序計數(shù)器計數(shù)等

?處理時間有關的系統(tǒng)調用

?更多復雜的問題，如：寫一個臨時文件，在哪個主機上更高效？

?如果機器不再空閑：L啥也不干2.殺掉進程（會丟失信息-＞可以警告）3.遷移到其他機器,

實現(xiàn)很難（如何手機內核相關數(shù)據(jù)、轉移相關子進程）

?處理機池模型，希望提供用戶十倍百倍以上的CPU性能

?處理機池

?優(yōu)點：節(jié)約電量、廉價終端、相同資金算力更強、理論依據(jù)：排隊論

?用戶每秒產(chǎn)生\lambda個請求，系統(tǒng)每秒處理\mu個請求，平均響應時間T=l/（\mu-

lambda）,請求排隊等待

系統(tǒng)每秒能

處理口個請求

用戶每秒共

產(chǎn)生入個請求

?n機組成的獨立排隊系統(tǒng)（每個機器都有一個排隊系統(tǒng)）響應時間依舊是T,如果請求到達

速率和處理機處理速率都為n倍則平均響應時間為T/n,用于反駁分布式計算，但平均響

應時間不是唯一的性能指標，DS價格低、對多用戶穩(wěn)定性強

?混合模型

?每個用戶提供專用工作站+處理機池，交互在工作站，非交互式進程在處理池中運行

?優(yōu)點：交互相應迅速、資源有效利用、設計簡單

?體系結構的樣式

?大型系統(tǒng)的開發(fā)關鍵：體系結構的設計和使用

?表示法：體系結構樣式

?組件：模塊單元，帶良好接口

?鏈接器：組件之間鏈接，數(shù)據(jù)交換

?樣式：

?分層體系結構

?基于對象的體系結構

通過遠程調用機制來連接

如：客戶-服務器系統(tǒng)體系結構

?以數(shù)據(jù)為中心的體系結構

?系統(tǒng)體系結構

?集中式

?C/S模型

應用分層

?用戶接口層

?處理層

?數(shù)據(jù)層

?例：

?Internet搜索引擎

?金融決策支持系統(tǒng)

?多層:Cs/Ss

?多層體系結構

(b)(d)

文字處銀行應Web瀏

理軟件用程序覽

?非集中式

?C/S垂直分布性：前面的

?C/S水平分布性

?客戶或服務器物理上被分割為邏輯上相等的幾個部分，每個部分都操作在整個

數(shù)據(jù)集中子集共享的部分，實現(xiàn)負載均衡

?比如p2P系統(tǒng)，分為結構化、非結構化

?覆蓋網(wǎng)絡時用一個確定性過程構成

?分布式哈希表DHT

?不需要服務器的情況下，每個C維持一個小范圍路由并存儲一部分數(shù)據(jù)，

實現(xiàn)整個DHT網(wǎng)絡的尋址和存儲。

?實現(xiàn)：從一個大的標識符空間選取一個隨機關鍵值賦給數(shù)據(jù)項和節(jié)點，查

詢該數(shù)據(jù)項時返回對應節(jié)點的網(wǎng)絡地址

?Chord系統(tǒng)（主流DHT之一）

?節(jié)點按邏輯組成一個環(huán)，關鍵值k的數(shù)據(jù)項映射到最新的標識符

id>=k的節(jié)點

?非結構化p2p:隨機化算法構成覆蓋網(wǎng)絡，（比如CDN）

?每個節(jié)點維持一個鄰節(jié)點列表，拿這個列表用隨機的方法來構造，同時數(shù)

據(jù)項隨機分布在網(wǎng)絡節(jié)點中

?因此用泛洪查詢數(shù)據(jù)項

?超級對等體，上下文傳送網(wǎng)絡

?超級對等體

?在非結構化點對點系統(tǒng)中，隨著網(wǎng)絡增

大，相關數(shù)據(jù)項的點位變得更加困難

?解決方案：放棄點對點系統(tǒng)的對稱性，如

,上下文傳送網(wǎng)絡（contentdelivery

network,CDN）

?節(jié)點提供緩存空間，讓Web用戶

快速訪問

,而代理程序（Broker）可以快速

查詢這些節(jié)點，而這種節(jié)點通常

稱為超級對等體（superpeer）

?混合

?邊界服務器系統(tǒng)，如ISP

?Internet服務提供商(InternetServiceProvider,ISP)

圖2.13把因特網(wǎng)看作是由一系列邊界服務器組成的

?協(xié)作分布式系統(tǒng)（BT）

?BitTorrent（2003）

?基本思想：當一個終端用戶要查找某個文件時，

他可以從其他用戶那里下載文件塊，直到所下載

的文件塊能夠組裝成完整的文件為止BramCohen

?BitTorrent的跟蹤器（tracker）

?維護活動節(jié)點的記錄

?通常，每個文件（或文件集）只有一個跟蹤器

?特性：節(jié)點被強制為其他節(jié)點提供幫助！

?結果表明，系統(tǒng)的瓶頸由跟蹤器導致

?協(xié)作DS

?GlobuleCDN2006

?終端用戶自愿提供增強的webserver

?每個服務器有:可以把客戶的請求重定位到其他服務器組件的組件、分析訪

問模式的組件、管理web頁面復制的組件

?分布式處理機分配算法

?理由：硬件上多機，軟件上每個作業(yè)會有多個任務進程，如何分配資源如何分配負載

?基本模型、彳皖、目標

?硬件同構（至少代碼兼容），有些還假定系統(tǒng)有多個互不相關的處理機池，每個處理機池

相同

?互聯(lián)拓撲：系統(tǒng)是完全互聯(lián)的（任二機可通訊，但并不一定都物理直連，只是底層通訊掩

蓋了，但有一些分配算法會用到網(wǎng)絡廣播或多播的特性）

?新進程的產(chǎn)生及處理機的分配

?創(chuàng)建子進程：shell（系統(tǒng)命令解釋程序）來完成，時用戶執(zhí)行其指定命令的對應程序,

另一種情況下用戶進程本身也可以創(chuàng)建多個子進程

?處理及分配策略（子進程）

?非遷移的：創(chuàng)建時系統(tǒng)就決定它分配到哪臺機器上且不可遷移

?可遷移的：某機負載變重可以將運行的進程遷移到其他機器，負載均衡但非常難以

實現(xiàn)

?分配算法優(yōu)化目標：

?提高處理機利用率，讓處理機在每小時執(zhí)行用戶周期數(shù)盡量多（減少空閑處理

機周期數(shù)）

處理機的利用率=執(zhí)行用戶匚作的周期數(shù)/小時

執(zhí)行用戶的周期數(shù)/小時-idle周期數(shù)/小時

?平均響應最小化

平均響應時間=average{i進程的響應時間

l<i<n

7?進程的響應時間=1進程的等待時間+i進程的執(zhí)行時間

?->最小響應率，對于大多數(shù)用戶來說，響應率比響應時間更重要

i進程的響應時間

i進程的響應率

i進程的執(zhí)行時間

?考慮負載均衡的分配算法分類

?局部：對單個處理器時間片分配，全局：先進行進程對處理器的分配，在完成每個處理器

局部調度

?靜態(tài)：分配在編譯階段完成，動態(tài)：執(zhí)行時

?最優(yōu)/次優(yōu)：一般負載分配是NP完全問題，所以次優(yōu)也可以接受。對最優(yōu)和次優(yōu)有四類算

法：解空間枚舉、圖模型、數(shù)學變成（0/1規(guī)劃…）、隊列模型

?近