高級操作系統-筆記

高級操作系統-筆記

?分布式系統簡介

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

來越復雜）

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

軟件在用戶看來看作單一系統

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

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

?和并行計算相比

?GPU貴，廉價CPU集群便宜

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

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

?和獨立PC相比優勢：數據共享、設備共享、通訊方便、靈活性強，缺點：軟件少，網絡通信引入

的問題網絡安全

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

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

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

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

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

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

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

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

更新寫）提升至U64個CPU

?多CPU開關型：（為了支持更多CPU互聯）

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

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

?多級互聯：最經典的是NXNOmega,logN開關級，每級N/2個開關，總開關數

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

23N/2）個不阻塞。

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

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

baseline-l,intercube-l0MINs

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

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

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

證明）

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

網任意k級？？？

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

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

（CSMA/CD）

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

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

加？？？（網孔隨著CPU數目平方根增加）

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

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

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

備通常操作系統所應具備的基本功能外，還應該具有聯網功能，支持網絡體系結構和各種網絡

通信協議，提供網絡互連能力，支持有效可靠安全地數據傳輸。（早期只有基本功能：通訊、

文件、打印等。現在功能不斷擴展，性能大幅提高。）

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

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

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

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

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

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

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

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

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

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

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

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

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

?DS設計問題

?透明性：將DS看作一個整體的分時系統。

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

問不一樣）

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

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

道多計算機并行執行，最難實現。解決方法：編譯器、運行系統和操作系統來合理地利用

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

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

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

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

?大內核：性能好

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

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

?以下幾個方面：

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

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

性越大）

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

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

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

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

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

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

可縮放性好。

?分布式系統同步

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

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

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

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

?邏輯時鐘同步

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

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

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

?Lamport

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

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

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

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

?時間值.進程號

?賦值方法

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

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

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

?物理時鐘同步

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

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

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

?Cristian

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

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

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

同步一次。

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

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

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

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

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

?非集中同步

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

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

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

值、考慮網絡中延遲

?分布式互斥

?集中互斥算法

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

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

前一個進程釋放發送給協調器，然后解除后一個阻塞，進入臨界區。

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

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

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

?若不在且不想占用該臨界區，發送0K

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

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

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

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

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

?無死鎖無餓死無單點失敗（對某節點崩潰敏感）

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

?每個進程進行統一編號，構成邏輯環

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

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

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

需要每個節點存儲環結構）

?無餓死，也對崩潰敏感

?分布式選舉算法

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

進程統一的基礎上選出協調者

?Bully算法

?進程P發現協調者不響應時，發起選舉。

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

?無人響應則P獲勝成為協調者

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

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

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

時也能知道大的

?環算法

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

?發送者把自己的進程號加入表中繼續轉發，直到始發者收到自己的進程號。發送協調者消

息再繞環一次，通知誰是協調者。

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

?原子事務

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

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

?磁帶系統擁有原子事務要么全有要么全無的特性

?在線數據庫系統的原子事務設計，要么操作全執行要么都不執行，失敗后需要能夠返回最初狀

態

?事務模型

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

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

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

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

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

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

孤立性（并行事務不干擾，并行提交但會根據系統以某種順序執行）、持久性（一旦提交

永久存在）

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

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

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

日志后崩潰，可以恢復后繼續工作，如果某下屬崩潰，則協調者給他不斷發消息。如果協

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

?并發控制算法

?加鎖

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

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

?讀鎖共享，寫鎖互斥。

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

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

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

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

?樂觀并發控制

?現實中沖突非常少

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

終止否則提交。

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

件要么提交要么釋放。

?優點：避免了死鎖，允許最大限度的并行

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

升

?時間戳

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

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

早。

?不會出現死鎖

?死鎖

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

?處理方法

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

?避免，不在DS中采用

?檢測消除

?DS死鎖檢測

?集中式

?各機有自己的資源圖，中心機器有整個系統的資源圖，檢測到回路（發

現死鎖）就中止一個進程。

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

發送給協調者（發送消息更少）、協調者需要時主動去請求

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

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

?分布式

?Chandy-Misra-Haas

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

發送者進程，接收者進程）

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

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

就發送多少消息。

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

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

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

者）

?預防，很困難

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

嚴格增序

?基于時間戳

?Lamport時間戳

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

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

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

?分布式路由算法

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

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

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

?最短路由算法

?Dijkstra源節點到所有節點的最短路徑

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

?N={s},對每個不在N的節點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,直到所有節點都在N里

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

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

的當前最短距離

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

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

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

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

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

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

路由表傳送到所有臨界點，直達路由表在某一點穩定

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

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

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

低

?特殊網絡的單播路由算法

?雙向環

?消息沿一個方向轉發，方向由源節點根據目標節點的決定方向

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

己是des,存m

?二維算法，網格、圓環（二位圓環比網格多了周圍鄰接，n連著1）

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

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

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

?最大最短路由，折線路由對圓環不最優。選擇最大個數的最短路徑鄰居。但不一定最優。

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

?超立方

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

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

?兩個節點亦或u異或w=r,逐位異或

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

?算法

?當前節點u,目標節點W

?計算r=u異或W

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

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

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

?特殊網絡多播

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

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

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

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

是NP問題

?基于路徑的算法

?構建哈密爾頓回路，每個節點經過且只經過一次

?根據回路把多播集合轉發出去

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

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

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

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

?高信道網絡：從低到高。低信道網絡：從高到低

?使用高信道網絡：

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

?若d是v的鄰居，就直接發到d

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

?低通訊網絡同理

?基于樹的算法

?Lan貪婪組播

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

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

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

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

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

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

?U網格算法

?定義字典序(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)

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

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

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

?重復分割

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

?虛信道與虛網絡

?通過網絡分區避免死鎖，分割沒有回路的子網

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

?方法：多個虛信道對一個物理信道、物理網絡分成多個虛網絡

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

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

?不引發死鎖增強適應性

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

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

?可以將網絡分為多個子集，每個子集都不包含相鄰節點

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

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

?一般化算法

?將網絡分為k個子集SI,S2，…,Sk互斥

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

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

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

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

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

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

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

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

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

?問題：如何分配

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

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

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

道間互相依賴，算法復雜

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

?轉彎模型

?平面自適應模型

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

?位降低虛信道數目犧牲全適應性

?容錯單播

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

?2維網絡與圓環

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

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

節點先轉化為凸

?安全/非安全節點

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

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

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

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

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

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

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

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

?Y錯誤阻塞同理。

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

?最優容錯路由算法

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

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

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

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

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

?面向目標路由

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

同理圍起來的區域是RMP

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

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

由就得順著邊界走。

?面向源路由

?構建路徑A、B

路徑B

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

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

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

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

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

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

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

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

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

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

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

塊信息的分布情況，

?基于其他故障類型

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

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

是非活躍的

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

?基本安全/不安全規則下的活躍節點

?擴展安全/不安全規則下的活躍節點

?超立方

?基于局部

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

確保、無限制出錯有最有

?出錯小于n-1不確保

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

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

?u是源節點，w是目標節點

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

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

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

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

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

?基于有限全局信息

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

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

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

?計算安全等級

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

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

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

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

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

節點的海明距離路徑

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

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

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

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

消息轉給這個節點實現次優路由，路徑長度|s異或d|+2

?基于擴展安全(略)

?容錯組播

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

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

在出現錯誤的時候，問題會更復雜。

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

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

相當于每一位單獨計數

?簡單策略

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

?當口優多個維度是1,則任選其一發送

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

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

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

級就隨機

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

?SLBM和MSLBM都是最優的，但是MSLBM的消息總量更小

?分布式進程與系統機管理

?分布式系統模型

?工作站模型

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

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

與無盤相比，網絡負擔更輕

分頁+臨時文件

需大量磁盤，費用較高

網絡負擔更輕

分頁+臨時文件+系統二進制文件

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

分頁+臨時文件+系統二進制文件網絡負擔更輕'也減輕文件服務器的負擔

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

完整的局部文件系統幾乎沒有網絡負擔，無需文件服務器

（網絡操作系統）失去透明性

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

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

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

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

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

錄性能降低。

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

?服務器驅動

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

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

?客戶端驅動

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

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

?透明計算：同構系統，系統調用時處理

?系統調用時的處理

?處理系統調用的錯誤

?處理只能在本機/遠程主機運行的系統調用

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

?處理時間有關的系統調用

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

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

實現很難（如何手機內核相關數據、轉移相關子進程）

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

?處理機池

?優點：節約電量、廉價終端、相同資金算力更強、理論依據：排隊論

?用戶每秒產生\lambda個請求，系統每秒處理\mu個請求，平均響應時間T=l/（\mu-

lambda）,請求排隊等待

系統每秒能

處理口個請求

用戶每秒共

產生入個請求

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

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

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

?混合模型

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

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

?體系結構的樣式

?大型系統的開發關鍵：體系結構的設計和使用

?表示法：體系結構樣式

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

?鏈接器：組件之間鏈接，數據交換

?樣式：

?分層體系結構

?基于對象的體系結構

通過遠程調用機制來連接

如：客戶-服務器系統體系結構

?以數據為中心的體系結構

?系統體系結構

?集中式

?C/S模型

應用分層

?用戶接口層

?處理層

?數據層

?例：

?Internet搜索引擎

?金融決策支持系統

?多層:Cs/Ss

?多層體系結構

(b)(d)

文字處銀行應Web瀏

理軟件用程序覽

?非集中式

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

?C/S水平分布性

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

數據集中子集共享的部分，實現負載均衡

?比如p2P系統，分為結構化、非結構化

?覆蓋網絡時用一個確定性過程構成

?分布式哈希表DHT

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

實現整個DHT網絡的尋址和存儲。

?實現：從一個大的標識符空間選取一個隨機關鍵值賦給數據項和節點，查

詢該數據項時返回對應節點的網絡地址

?Chord系統（主流DHT之一）

?節點按邏輯組成一個環，關鍵值k的數據項映射到最新的標識符

id>=k的節點

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

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

據項隨機分布在網絡節點中

?因此用泛洪查詢數據項

?超級對等體，上下文傳送網絡

?超級對等體

?在非結構化點對點系統中，隨著網絡增

大，相關數據項的點位變得更加困難

?解決方案：放棄點對點系統的對稱性，如

,上下文傳送網絡（contentdelivery

network,CDN）

?節點提供緩存空間，讓Web用戶

快速訪問

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

查詢這些節點，而這種節點通常

稱為超級對等體（superpeer）

?混合

?邊界服務器系統，如ISP

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

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

?協作分布式系統（BT）

?BitTorrent（2003）

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

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

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

?BitTorrent的跟蹤器（tracker）

?維護活動節點的記錄

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

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

?結果表明，系統的瓶頸由跟蹤器導致

?協作DS

?GlobuleCDN2006

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

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

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

?分布式處理機分配算法

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

?基本模型、彳皖、目標

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

相同

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

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

?新進程的產生及處理機的分配

?創建子進程：shell（系統命令解釋程序）來完成，時用戶執行其指定命令的對應程序,

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

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

?非遷移的：創建時系統就決定它分配到哪臺機器上且不可遷移

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

實現

?分配算法優化目標：

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

機周期數）

處理機的利用率=執行用戶匚作的周期數/小時

執行用戶的周期數/小時-idle周期數/小時

?平均響應最小化

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

l<i<n

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

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

i進程的響應時間

i進程的響應率

i進程的執行時間

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

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

局部調度

?靜態：分配在編譯階段完成，動態：執行時

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

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

?近