9.5事件排序前發(fā)生關系(用符號“”表示).如果A和B是同一進程內部的事件，而且A在B前執(zhí)行，則有AB。如果A是一個由某一進程發(fā)送消息的事件，B是由另一進程接收該消息的事件，則有AB。如果AB且BC，則有AC。實現

將每個系統(tǒng)事件都打上一個“時間郵戳”。

每一個事件對A和B,如果AB,則A的郵戳時間應小于B的郵戳時間。在每個進程Pi內部定義一個相關聯(lián)的邏輯時鐘Lci。由簡單的計數器來實現，即作為在一個進程內任何兩個連續(xù)執(zhí)行的事件之間的增量。“”的實現一進程在接收到一個消息,而且該消息的郵戳時間TS比接收進程邏輯時鐘的當前值還大時,接收進程推進它的邏輯時鐘。Count=TS+1。如果事件A和事件B的郵戳時間相同,則事件是并發(fā)的。可以通過進程一致數打破這個關系并創(chuàng)造一個全序關系。9.6進程互斥假設系統(tǒng)包含n個進程;每個進程Pi

都存在于不同的處理機當中.每個進程有個臨界區(qū)需要互斥.必要條件如果進程Pi

正在它的臨界區(qū)域內執(zhí)行，則在這個臨界區(qū)域內沒有其他進程

Pj

執(zhí)行.這里給出兩個算法來確保執(zhí)行進程在他們的臨界區(qū)域內互斥.集中方式

指派一個協(xié)調者進程(coordinator),負責控制對于臨界區(qū)的進入。每一個要求進入臨界區(qū)的進程都必須發(fā)送一個請求給協(xié)調者進程。協(xié)調者決定哪個進程可以進入臨界區(qū)域，之后給它發(fā)送答復消息。當進程收到協(xié)調者進程的回答信號后,它才能進入自己的臨界區(qū).集中方式

當一個進程退出臨界區(qū)時，發(fā)送一個釋放信號給協(xié)調者進程，然后再繼續(xù)運行。每次進入臨界區(qū)需要三個消息：請求,回答,釋放 網絡與分布式進程的互斥較復雜，不能用P、V原語。假設有n個處理機，每個處理機只有一個進程，編號也是1~n。協(xié)調者PnRP1P2Pn-1Pn-2分布方式

算法進程Pi想進入臨界區(qū)，產生一個時間戳TSi,發(fā)消息request(Pi,TSi)給所有其他進程;進程Pj接收到request消息后，可能立即，也可能延遲回復reply消息；當進程Pi接收到所有進程回復的reply消息后，可以進入臨界區(qū)；分布方式

(續(xù).)進程Pi離開臨界區(qū)后，給所有延遲回復的進程發(fā)reply消息決定進程Pj立即回復request(Pi,TS)消息還是延遲回復主要基于三個因素:如果Pj當前正在臨界區(qū)中，延遲回復.如果Pj不想進入臨界區(qū)，立即回復.如果Pj想進入但尚未進入臨界區(qū)，則比較二者的時間戳TS.如果所持有的時間戳大于TS;則立即回復Pi,(Pi

要求占先).否則，延遲回復.

Ricard和Agrawala分布互斥算法P2P1PnPiRequest(Pi,TS)R分布方式優(yōu)點確保無死鎖確保無饑餓因為進入臨界區(qū)域是依照時間戳順序，時間戳順序確保FCFS.每次進入臨界區(qū)僅需要的消息數量

2

(n–1)這是全分布算法最好的結果

三個缺點每個進程必須知道所有其他進程的存在，這使進程動態(tài)增減變的復雜若其中一個進程失效，則整個算法崩潰，為此需要動態(tài)監(jiān)視所有進程狀態(tài)不想進入臨界區(qū)的進程也必須參與協(xié)調過程．因而算法比較適合穩(wěn)定且數量較少的進程集合標志傳遞方式(tokenpassing)需要考慮兩種失效情況如果消息丟失,則應能發(fā)現并選擇一個進程產生一個新的標志;如果一個進程夭折了,則邏輯環(huán)就將斷裂,此時系統(tǒng)應能重構一個新的邏輯環(huán).P2P1PiPnToken接到標志可以進入CS，并扣留Token當每個進程都申請進入時，平均每個進程需要一個消息當所有進程都不申請進入時，則將產生無數個消息當只有一個進程申請進入時，最多n-1個消息9.7進程同步與進程通訊

消息傳遞(MessagePassing)套接字(Socket)

遠程過程調用(RemoteProcedureCall，RPC)

遠程方法啟用(RemoteMethodInvocation，RMI)

消息傳遞(MessagePassing)同步消息傳遞 -send(接收者,消息,回答):將消息發(fā)送給指定的接收者,然后掛起,等待來自接收者的回答消息,之后繼續(xù)。-receive(發(fā)送者,消息):等待接收來自發(fā)送進程的消息。-reply(發(fā)送者,回答):將回答信息發(fā)給發(fā)送進程,使之繼續(xù)執(zhí)行。消息傳遞(MessagePassing)異步消息傳遞-send(接收者,消息/回答):將消息或回答發(fā)送給接收者,然后繼續(xù)。-receive(發(fā)送者,消息/回答):由發(fā)送者處接收消息或回答,然后繼續(xù)。消息傳遞(MessagePassing)消息傳遞(MessagePassing)套接字通訊

Socket(161.25.19.8/80)Socket(146.86.5.20/1625)主機X(146.86.5.20)網絡服務器(161.25.19.8)9.7.3遠程過程調用

(RPC)套接字是一種低級(lowlevel)、不完全可靠的通訊方式RPCs提供一種高級通訊方式Clientmakesprocedurecallto“remote”serverusingordinaryprocedurecallmechanisms.WidelyacceptedandstandardizedmechanismindistributedenvironmentRPCcanbesynchronizedorasynchronous呼叫方調用參數打包發(fā)送

等待接收開包結果返回消息參數接收開包

調用打包發(fā)送結果執(zhí)行過程返回客戶代理服務員代理客戶服務員消息被呼叫方Vec,MAX,10調用消息返回消息v……顧客進程：…………RPC_name(vec,MAX,10)(掛起)…………vec:=v(繼續(xù))…………服務進程：…………RPC_name(v,n,k)v:=vec;n:=MAX;k:=10;FORI:=1TOnDOv[I]:=v[I]*k;……站點A站點B例:遠程方法啟用

(RemoteMethodInvocation，RMI)Java中的RPC版本被命名為RMI

一個線程可以啟用另外一個遠程對象中的方法

“遠程”指處于不同的Java虛擬機(JVM)中遠程方法啟用(Cont.)RPC與RMI的比較RPC支持過程型程序設計風格RMI支持面向對象程序風格RPC的參數為普通數據類型RMI的參數為對象9.8死鎖處理

死鎖預防

全局資源排序基于“優(yōu)先權

/回退”方式的時間戳死鎖避免分布銀行家算法死鎖檢測

對每個資源類型的實例集中方式分布方式9.8.1死鎖預防

死鎖預防

全局資源排序+請求排序給每個進程賦予一個唯一的優(yōu)先數.如果一個進程沒持有資源編號大于i的資源，則可以申請優(yōu)先數i

的資源.優(yōu)點和缺點simpleimplementationlittleoverheaddifficultyinglobalresourceorderinginconvenientfordistributedprocessestoabidebytheprotocol每個文件讀寫命令必須是自包含的(selfcontained)適合于長時間對數據進行較多更新操作的應用環(huán)境.如果Pj當前正在臨界區(qū)中，延遲回復.通寫(writethrough)–每當緩存副本發(fā)生變化時就更新主本如果P3要求P2占用的資源，則P3等待。遠程文件存取RemoteFileAccessRPC_name(vec,MAX,10)套接字(Socket)網絡與分布式進程的互斥較復雜，不能用P、V原語。-send(接收者,消息/回答):將消息或回答發(fā)送給接收者,然后繼續(xù)。littleoverhead通寫(writethrough)–每當緩存副本發(fā)生變化時就更新主本文件仍然由一個位于服務器上的主拷貝標識，但其副本可能分散在多個站點上通寫(writethrough)–每當緩存副本發(fā)生變化時就更新主本給每個進程賦予一個唯一的優(yōu)先數.優(yōu)先級死鎖預防每個進程Pi被賦予一個唯一的優(yōu)先數

優(yōu)先數用來決定進程Pi

是否應該等待進程Pj;

如果pri(Pi)>pri(Pj),Pi

等待;否則Pi

回退.Theschemeisdeadlock-free.ForeveryedgePi

Pjinthewait-forgraph,PihasahigherprioritythanPj.Thusacyclecannotexist.Possibilityofstarvation--lowpriorityprocessmayalwaysberolledback.Resolve:usetimestampinsteadofpriority等-死(wait-die)

基于非剝奪策略。當一個進程Pi要求另外一個Pj保持的資源時，Pi被允許等待，僅當它具有比Pj更小的郵戳時間，即Pi是比Pj更老，否則Pi回退。例如，設進程P1,P2,P3分別具有郵戳時間5,10,15。如果P1要求P2占用的資源,則P1等待。如果P3要求P2占用的資源,則P3回退。等待邊(更老)Pi

Pj(更年輕)傷-等(wound-wait)基于剝奪策略，是等－死的改版。當進程Pi要求進程Pj當前所保持的資源時，則Pi獲準等待的條件是它具有比Pj更大的郵戳時間，即Pi比Pj更年輕，否則Pj回退，即Pj被Pi所傷。例如,設進程P1,P2,P3分別具有郵戳時間5,10,15。如果P1要求P2所占用的資源，則將剝奪P2的資源給P1，P2回退；如果P3要求P2占用的資源，則P3等待。等待邊(更年輕)

Pi

Pj(更老)9.8.2死鎖避免銀行家算法

指定系統(tǒng)中某個進程為銀行家，由它保持執(zhí)行銀行家算法所必需的信息。銀行家負責系統(tǒng)中資源的分配。優(yōu)點和缺點easyimplementationmayincurtoomuchoverheadpossibilityofbottleneckifbankerfails,thealgorithmfails9.8.3死鎖檢測每個站點保持一個局部等待圖。

站點：所有進程或者持有戶或者請求本地站點的資源。站點

AP1P2P3P5P2P4P3站點

B9.8.3死鎖檢測(Cont.)全局等待圖是所有局部等待圖的合并。P1P2P3P5P4站點A和站點B的全局等待圖9.9資源管理9.9.1集中方式中央資源管理者負責系統(tǒng)中所有資源的分配.系統(tǒng)資源表資源類型資源數量

物理位置

物理特性

分配狀態(tài)

……………9.9.1集中方式(Cont.)優(yōu)點可以做出全局優(yōu)化的資源分配策略。系統(tǒng)擴充和裁減容易這只需要在系統(tǒng)資源分配表中增加一個新項目或刪除一個舊項目

減少了資源管理算法的開銷除中央資源管理者外，其它站點不參與資源決策事務。9.9.1集中方式(Cont.)缺點可靠性低因為一旦資源管理者失效，則整個系統(tǒng)癱瘓。盡管引入多個資源管理者可以克服這一缺點，但保持多副本的一致性是困難的。中央資源管理者可能成為系統(tǒng)的瓶頸由于中央資源管理者的存在，使整個系統(tǒng)失去了自治性。9.9.2分布方式每個站點都有一個局部資源表，用于記載屬于該站點的局部資源當一個站點要申請局部資源時，它可由本地得到。當一個站點要申請全局資源時，它向其它站點發(fā)送申請命令，其它站點根據情況做出分配決策。9.9.2分布方式(Cont.)每個站點管理其自己的資源。當Pi申請局部資源時，可由本地獲得當Pi申請其它站點資源時，由其它站點作出裁決9.9.2分布方式(Cont.)優(yōu)點可靠性高因為任何一個站點、資源或服務的失效通常不會影響整個系統(tǒng)每個站點具有較高的自治性它可以將其所擁有的資源提供給整個系統(tǒng)使用，也可留為私用9.9.2分布方式(Cont.)缺點通訊量增加因為要獲得有關資源的信息，每個站點都需要與其它站點交換信息。每個站點都需要為資源分配策略的實施付出開銷即資源分配設施消耗局部資源。9.9.3層次方式

集中方式與分布方式的結合，同時兼有二者的優(yōu)點,并克服二者的缺點

對于局部資源采用分布式管理策略對于全局資源采用集中式管理策略9.10分布式文件系統(tǒng)

(DistributedFileSystem，DFS)

一般結構命名與透明性遠程文件存取RemoteFileAccess遠程文件服務副本復制有狀態(tài)服務與無狀態(tài)服務緩存策略一般結構

分布式文件系統(tǒng)(DFS)是集中式文件系統(tǒng)的分布式實現命名與透明性

命名是邏輯實體到物理實體的映射對于真正意義的DFS，整個系統(tǒng)具有統(tǒng)一的命名機制，用戶以透明的視圖共享所有文件和存儲器。三種命名形式：網絡命名方式，命名與物理位置完全相關，不透明遠程安裝方式，遠程安裝是不透明的，一旦安裝完畢，遠程訪問是透明的完全分布方式，所有文件具有全局唯一的名字，文件名與物理位置無關9.10.3遠程文件存取

遠程文件服務工作模式:向服務員提出文件訪問請求服務員執(zhí)行相應操作將結果返回給顧客實現:RPC副本復制緩存將遠程文件復制到本地，然后如同本地文件一樣訪問問題:一致性副本復制緩存

文件仍然由一個位于服務器上的主拷貝標識，但其副本可能分散在多個站點上當進程所需文件不在本地時，由服務器向本地緩存一個副本.存取操作在緩存副本上執(zhí)行.緩存粒度塊為單位，整個文件為單位.緩存一致性問題保證主文件和緩存副本的一致.緩存副本存放方式

磁盤緩存更可靠本地機器故障后恢復容易內存緩存速度快支持無盤客戶端工作站緩存更新策略

通寫(writethrough)–每當緩存副本發(fā)生變化時就更新主本

可靠性高；一致性好；效率很低。延遲寫(delayedwrite)

–副本數據經過若干次訪問(更新)后才最終寫回主本實現效率較高；

一致性差；可靠性低，一旦副本所在結點失效則更新數據可能丟失。緩存更新策略(Cont.)增量刷新(incrementalflush)定時掃描緩