大學操作系統(tǒng)

1、9.5 事件排序事件排序 n前發(fā)生關(guān)系前發(fā)生關(guān)系 (用符號用符號“”表示表示 ).n如果如果A和和B是同一進程內(nèi)部的事件，而且是同一進程內(nèi)部的事件，而且A在在B前執(zhí)行，則有前執(zhí)行，則有AB。n如果如果A是一個由某一進程發(fā)送消息的事件，是一個由某一進程發(fā)送消息的事件，B是由另一進程接收該消息的事件，則有是由另一進程接收該消息的事件，則有 AB。n如果如果 AB 且且 BC，則有則有 AC。n非自反的偏序非自反的偏序?qū)崿F(xiàn)實現(xiàn) n將每個系統(tǒng)事件都打上一個將每個系統(tǒng)事件都打上一個“時間郵戳時間郵戳”。 n每一個事件對每一個事件對A和和B, 如果如果AB, 則則A的郵戳時的郵戳時間應(yīng)小于間應(yīng)小于B的郵戳

2、時間。的郵戳時間。n在每個進程在每個進程Pi內(nèi)部定義一個相關(guān)聯(lián)的邏輯內(nèi)部定義一個相關(guān)聯(lián)的邏輯時鐘時鐘 Lci。n由簡單的計數(shù)器來實現(xiàn)，即作為在一個進程內(nèi)由簡單的計數(shù)器來實現(xiàn)，即作為在一個進程內(nèi)任何兩個連續(xù)執(zhí)行的事件之間的增量。任何兩個連續(xù)執(zhí)行的事件之間的增量?！啊钡膶崿F(xiàn)的實現(xiàn)n一進程在接收到一個消息一進程在接收到一個消息, 而且該消息的郵而且該消息的郵戳時間戳時間TS比接收進程邏輯時鐘的當前值還比接收進程邏輯時鐘的當前值還大時大時, 接收進程推進它的邏輯時鐘。接收進程推進它的邏輯時鐘。Count=TS+1。n如果事件如果事件A和事件和事件B的郵戳時間相同的郵戳時間相同, 則事則事件是并發(fā)的。件

3、是并發(fā)的。9.6 進程互斥進程互斥 (DME) n假設(shè)假設(shè)n系統(tǒng)包含系統(tǒng)包含n個進程個進程; 每個進程每個進程 Pi 都存在于不同的處理機當中都存在于不同的處理機當中.n每個進程有個臨界區(qū)需要互斥每個進程有個臨界區(qū)需要互斥.n必要條件必要條件n如果進程如果進程Pi 正在它的臨界區(qū)域內(nèi)執(zhí)行，則在這個臨界區(qū)域內(nèi)沒有正在它的臨界區(qū)域內(nèi)執(zhí)行，則在這個臨界區(qū)域內(nèi)沒有其他進程其他進程 Pj 執(zhí)行執(zhí)行.n這里給出三個算法來確保執(zhí)行進程在其臨界區(qū)內(nèi)互斥這里給出三個算法來確保執(zhí)行進程在其臨界區(qū)內(nèi)互斥. n集中算法集中算法n分布算法分布算法n令牌算法令牌算法DME：集中方式集中方式 n指派一個協(xié)調(diào)者進程指派一個協(xié)

4、調(diào)者進程( (coordinator),),負負責控制對于臨界區(qū)的進入。責控制對于臨界區(qū)的進入。n每一個要求進入臨界區(qū)的進程都必須發(fā)每一個要求進入臨界區(qū)的進程都必須發(fā)送一個請求給協(xié)調(diào)者進程。送一個請求給協(xié)調(diào)者進程。n協(xié)調(diào)者決定哪個進程可以進入臨界區(qū)域，協(xié)調(diào)者決定哪個進程可以進入臨界區(qū)域，之后給它發(fā)送答復消息。之后給它發(fā)送答復消息。n當進程收到協(xié)調(diào)者進程的回答信號后當進程收到協(xié)調(diào)者進程的回答信號后, 它它才能進入自己的臨界區(qū)才能進入自己的臨界區(qū).DME: 集中方式集中方式 n當一個進程退出臨界區(qū)時，發(fā)送一個釋當一個進程退出臨界區(qū)時，發(fā)送一個釋放信號給協(xié)調(diào)者進程，然后再繼續(xù)運行。放信號給協(xié)調(diào)者進程

5、，然后再繼續(xù)運行。n無死鎖，若協(xié)調(diào)者進程公平（如無死鎖，若協(xié)調(diào)者進程公平（如FCFS)，無餓死無餓死n每次進入臨界區(qū)需要三個消息：每次進入臨界區(qū)需要三個消息：n請求請求n回答回答n釋放釋放DME: 分布方式分布方式 n算法算法n進程進程Pi想進入臨界區(qū)，產(chǎn)生一個時間戳想進入臨界區(qū)，產(chǎn)生一個時間戳TSi, 發(fā)消息發(fā)消息request(Pi,TSi)給所有其他進程給所有其他進程; n進程進程Pj接收到接收到request消息后，可能立即，消息后，可能立即，也可能延遲回復也可能延遲回復reply消息；消息；n當進程當進程Pi接收到所有進程回復的接收到所有進程回復的reply消息消息后，可以進入臨界區(qū)

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

7、回復則立即回復Pi, (Pi 要求要求占先占先).n否則，延遲回復否則，延遲回復.分布方式分布方式優(yōu)點優(yōu)點n確保無死鎖確保無死鎖n確保無饑餓確保無饑餓n因為進入臨界區(qū)域是依照時間戳順序，時間因為進入臨界區(qū)域是依照時間戳順序，時間戳順序確保戳順序確保FCFS.n每次進入臨界區(qū)僅需要每次進入臨界區(qū)僅需要的的消息數(shù)量消息數(shù)量 2 (n 1)n這是全分布算法最好的結(jié)果這是全分布算法最好的結(jié)果 DME例子例子n考慮考慮p1,p2,p3構(gòu)成的系統(tǒng)構(gòu)成的系統(tǒng)nP1,p3想進入其臨界區(qū)域想進入其臨界區(qū)域nP1發(fā)發(fā)request(1,15)給給p2和和p3, p3發(fā)送發(fā)送request(3,6)給給p1和和p2

8、. nP2接到請求后，立即回答接到請求后，立即回答p1和和p3；nP1接到接到p3的請求后也立即回答的請求后也立即回答(因為因為p1的時間郵的時間郵戳比戳比P3的時間郵戳大的時間郵戳大)nP3接到接到P1的請求的請求,延遲回答延遲回答;nP3接到來自接到來自P1和和p2的回答的回答,進入臨界區(qū)進入臨界區(qū);nP3離開臨界區(qū)域離開臨界區(qū)域,向向P1發(fā)回答消息發(fā)回答消息,P1進入臨界進入臨界區(qū)域區(qū)域DME: 三個缺點三個缺點n每個進程必須知道所有其他進程的存在，每個進程必須知道所有其他進程的存在，這使進程動態(tài)增減變的復雜這使進程動態(tài)增減變的復雜n若其中一個進程失效，則整個算法崩潰，若其中一個進程失效

9、，則整個算法崩潰，為此需要動態(tài)監(jiān)視所有進程狀態(tài)為此需要動態(tài)監(jiān)視所有進程狀態(tài)n不想進入臨界區(qū)的進程也必須參與協(xié)調(diào)過不想進入臨界區(qū)的進程也必須參與協(xié)調(diào)過程因而算法比較適合穩(wěn)定且數(shù)量較少的程因而算法比較適合穩(wěn)定且數(shù)量較少的進程集合進程集合 標志傳遞方式標志傳遞方式(token passing) n這種方式僅適合于邏輯拓撲結(jié)構(gòu)為環(huán)形的系統(tǒng)這種方式僅適合于邏輯拓撲結(jié)構(gòu)為環(huán)形的系統(tǒng) n系統(tǒng)中有一個標志系統(tǒng)中有一個標志, 它作為特殊類型的消息在系統(tǒng)它作為特殊類型的消息在系統(tǒng)中環(huán)行中環(huán)行n當一個進程接收到這個標志后當一個進程接收到這個標志后, 它就可以進入其臨它就可以進入其臨界區(qū)界區(qū), 并扣留這個標志并扣留這

10、個標志 n當它退出臨界區(qū)之后當它退出臨界區(qū)之后, 標志才被釋放標志才被釋放, 并沿環(huán)路繼續(xù)并沿環(huán)路繼續(xù)繞行繞行 n如果一個接收到標志的進程并不想進入其臨界區(qū)如果一個接收到標志的進程并不想進入其臨界區(qū), 只需放行此標志只需放行此標志 標志傳遞方式標志傳遞方式(token passing)n需要考慮兩種失效情況需要考慮兩種失效情況 n如果消息丟失如果消息丟失, 則應(yīng)能發(fā)現(xiàn)并選擇一個進程則應(yīng)能發(fā)現(xiàn)并選擇一個進程產(chǎn)生一個新的標志產(chǎn)生一個新的標志; n如果一個進程夭折了如果一個進程夭折了, 則邏輯環(huán)就將斷裂則邏輯環(huán)就將斷裂, 此時系統(tǒng)應(yīng)能重構(gòu)一個新的邏輯環(huán)此時系統(tǒng)應(yīng)能重構(gòu)一個新的邏輯環(huán).9.7 進程同步

11、與進程通訊進程同步與進程通訊 n消息傳遞消息傳遞 (Message Passing) n套接字套接字( (Socket) ) n遠程過程調(diào)用遠程過程調(diào)用( (Remote Procedure Call，RPC) ) n遠程方法啟用遠程方法啟用( (Remote Method Invocation，RMI) ) 消息傳遞消息傳遞 (Message Passing)n同步消息傳遞同步消息傳遞 -send( (接收者接收者,消息消息,回答回答) ): 將消息發(fā)送將消息發(fā)送給指定的接收者給指定的接收者, 然后掛起然后掛起, 等待來自接等待來自接收者的回答消息收者的回答消息, 之后繼續(xù)。之后繼續(xù)。 -r

12、eceive( (發(fā)送者發(fā)送者,消息消息) ): 等待接收來自等待接收來自發(fā)送進程的消息。發(fā)送進程的消息。 -reply( (發(fā)送者發(fā)送者,回答回答) ): 將回答信息發(fā)給將回答信息發(fā)給發(fā)送進程發(fā)送進程, 使之繼續(xù)執(zhí)行。使之繼續(xù)執(zhí)行。 同步消息傳遞站點站點A, 進程進程PiSend(接收者，消息，回答接收者，消息，回答)阻塞阻塞繼續(xù)繼續(xù)站點站點B, 進程進程Pjreceive(發(fā)送者，消息發(fā)送者，消息)Reply(發(fā)送者，回答發(fā)送者，回答)n異步消息傳遞異步消息傳遞 -send(接收者接收者,消息消息/回答回答): 將消息或回將消息或回答發(fā)送給接收者答發(fā)送給接收者, 然后繼續(xù)。然后繼續(xù)。 -r

13、eceive(發(fā)送者發(fā)送者,消息消息/回答回答): 由發(fā)送者由發(fā)送者處接收消息或回答處接收消息或回答, 然后繼續(xù)。然后繼續(xù)。 消息傳遞消息傳遞 (Message Passing)異步消息傳遞異步消息傳遞站點站點A, 進程進程Pisend(接收者，消息接收者，消息)繼續(xù)繼續(xù)receive(發(fā)送者，回答發(fā)送者，回答)站點站點B, 進程進程Pjreceive(發(fā)送者，消息發(fā)送者，消息)send(接收者，回答接收者，回答)9.7.2 套接字套接字(Socket)n套接字定義為通訊的一端套接字定義為通訊的一端 n地址形式為地址形式為( (IP,port) ) n套接字是一種低級套接字是一種低級(low

14、level)、不完全可靠的通不完全可靠的通訊方式訊方式 nAll Ports pri(Pj ), Pi 等待等待;n否則否則 Pi 回退回退.nThe scheme is deadlock-free. nFor every edge Pi Pj in the wait-for graph, Pi has a higher priority than Pj. Thus a cycle cannot exist.nPossibility of starvation-low priority process may always be rolled back.nResolve: use timest

15、amp instead of priority等等-死死( (wait-die) ) n基于非剝奪策略?；诜莿儕Z策略。n當一個進程當一個進程Pi要求另外一個進程要求另外一個進程Pj保持的資源時，保持的資源時，Pi被允許等待，僅當它具有比被允許等待，僅當它具有比Pj更小的郵戳時間，更小的郵戳時間，即即Pi是比是比Pj更老，否則更老，否則Pi回退?；赝?。n例如，設(shè)進程例如，設(shè)進程 P1, P2, P3分別具有郵戳時間分別具有郵戳時間 5, 10, 15。n如果如果P1要求要求P2占用的資源占用的資源, 則則P1等待。等待。n如果如果P3要求要求P2占用的資源占用的資源, 則則P3回退?；赝?。n等

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

17、給的資源給P1，P2回退；回退；n如果如果P3要求要求P2占用的資源，則占用的資源，則P3等待。等待。n等待邊等待邊n( (更年輕更年輕) ) PiPj ( (更老更老) )l銀行家算法銀行家算法 指定系統(tǒng)中某個進程為銀行家指定系統(tǒng)中某個進程為銀行家，由它保持執(zhí)行由它保持執(zhí)行銀行家算法所必需的信息銀行家算法所必需的信息。銀行家負責系統(tǒng)中資源的分配。銀行家負責系統(tǒng)中資源的分配。l優(yōu)點和缺點優(yōu)點和缺點easy implementationmay incur too much overheadpossibility of bottleneckif banker fails, the algorith

18、m fails9.8.3 死鎖檢測死鎖檢測n每個站點保持一個局部等待圖。每個站點保持一個局部等待圖。 n站點：所有進程站點：所有進程(或者持有或者請求或者持有或者請求)本地站點本地站點的資源。的資源。站點 AP1P2P3P5P2P4P3站點 B9.8.3 死鎖檢測死鎖檢測( (Cont.) )n全局等待圖是所有局部等待圖的合并。全局等待圖是所有局部等待圖的合并。 P1P2P3P5P4站點站點 A 和站點和站點 B的全局等待圖的全局等待圖9.9 資源管理資源管理9.9.1 集中方式集中方式n中央資源管理者負責系統(tǒng)中所有資源的中央資源管理者負責系統(tǒng)中所有資源的分配分配. 系統(tǒng)資源表系統(tǒng)資源表資源類

19、型資源類型 資源數(shù)量資源數(shù)量 物理位置物理位置 物理特性物理特性 分配狀態(tài)分配狀態(tài) 9.9.1 集中方式集中方式( (Cont.) )n優(yōu)點優(yōu)點n可以做出全局優(yōu)化的資源分配策略可以做出全局優(yōu)化的資源分配策略。n系統(tǒng)擴充和裁減容易系統(tǒng)擴充和裁減容易n這只需要在系統(tǒng)資源分配表中增加一個新項目或這只需要在系統(tǒng)資源分配表中增加一個新項目或刪除一個舊項目刪除一個舊項目 n減少了資源管理算法的開銷減少了資源管理算法的開銷n除中央資源管理者外，其它站點不參與資源決策除中央資源管理者外，其它站點不參與資源決策事務(wù)事務(wù)。9.9.1 集中方式集中方式( (Cont.) )n缺點缺點n可靠性低可靠性低n因為一旦資源

20、管理者失效，則整個系統(tǒng)癱瘓。因為一旦資源管理者失效，則整個系統(tǒng)癱瘓。n盡管引入多個資源管理者可以克服這一缺點，但盡管引入多個資源管理者可以克服這一缺點，但保持多副本的一致性是困難的。保持多副本的一致性是困難的。n中央資源管理者可能成為系統(tǒng)的瓶頸中央資源管理者可能成為系統(tǒng)的瓶頸 n由于中央資源管理者的存在，使整個系統(tǒng)失由于中央資源管理者的存在，使整個系統(tǒng)失去了自治性。去了自治性。9.9.2 分布方式分布方式n每個站點都有一個局部資源表每個站點都有一個局部資源表，用于記用于記載屬于該站點的局部資源載屬于該站點的局部資源n當一個站點要申請局部資源時當一個站點要申請局部資源時，它可由本地它可由本地得到

21、。得到。n當一個站點要申請全局資源時，它向其它站當一個站點要申請全局資源時，它向其它站點發(fā)送申請命令點發(fā)送申請命令，其它站點根據(jù)情況做出分其它站點根據(jù)情況做出分配決策。配決策。9.9.2 分布方式分布方式(Cont.)n優(yōu)點優(yōu)點n可靠性高可靠性高n因為任何一個站點、資源或服務(wù)的失效通常不會因為任何一個站點、資源或服務(wù)的失效通常不會影響整個系統(tǒng)影響整個系統(tǒng)n每個站點具有較高的自治性每個站點具有較高的自治性n它可以將其所擁有的資源提供給整個系統(tǒng)使用，它可以將其所擁有的資源提供給整個系統(tǒng)使用，也可留為私用也可留為私用 9.9.2 分布方式分布方式(Cont.)n缺點缺點n通訊量增加通訊量增加n因為要

22、獲得有關(guān)資源的信息因為要獲得有關(guān)資源的信息，每個站點都需要與每個站點都需要與其它站點交換信息其它站點交換信息。n每個站點都需要為資源分配策略的實施付出每個站點都需要為資源分配策略的實施付出開銷開銷n即資源分配設(shè)施消耗局部資源。即資源分配設(shè)施消耗局部資源。 9.9.3 層次方式層次方式 n集中方式與分布方式的結(jié)合集中方式與分布方式的結(jié)合，同時兼有同時兼有二者的優(yōu)點二者的優(yōu)點, 并克服二者的缺點并克服二者的缺點 n對于局部資源對于局部資源n采用分布式管理策略采用分布式管理策略 n對于全局資源對于全局資源n采用集中式管理策略采用集中式管理策略 9.10 分布式文件系統(tǒng)分布式文件系統(tǒng)(Distribu

23、ted File System，DFS) n一般結(jié)構(gòu)一般結(jié)構(gòu) n命名與透明性命名與透明性 n遠程文件存取遠程文件存取 Remote File Accessn遠程文件服務(wù)遠程文件服務(wù) n副本復制副本復制 n有狀態(tài)服務(wù)與無狀態(tài)服務(wù)有狀態(tài)服務(wù)與無狀態(tài)服務(wù) n緩存策略緩存策略 9.10.1 一般結(jié)構(gòu) n分布式文件系統(tǒng)(DFS)是集中式文件系統(tǒng)的分布式實現(xiàn)9.10.2 命名與透明性命名與透明性 n命名是邏輯實體到物理實體的映射命名是邏輯實體到物理實體的映射n對于真正意義的對于真正意義的DFS，整個系統(tǒng)具有統(tǒng)一的整個系統(tǒng)具有統(tǒng)一的命名機制，用戶以透明的視圖共享所有文件命名機制，用戶以透明的視圖共享所有文件

24、和存儲器。和存儲器。n三種命名形式：三種命名形式：n網(wǎng)絡(luò)命名方式，命名與物理位置完全相關(guān)，網(wǎng)絡(luò)命名方式，命名與物理位置完全相關(guān)，不透明不透明 n遠程安裝方式，遠程安裝是不透明的，一旦遠程安裝方式，遠程安裝是不透明的，一旦安裝完畢，遠程訪問是透明的安裝完畢，遠程訪問是透明的 n完全分布方式，所有文件具有全局唯一的名完全分布方式，所有文件具有全局唯一的名字，文件名與物理位置無關(guān)字，文件名與物理位置無關(guān) 9.10.3 遠程文件存取遠程文件存取 n遠程文件服務(wù)遠程文件服務(wù) n工作模式工作模式:n向服務(wù)員提出文件訪問請求向服務(wù)員提出文件訪問請求 n服務(wù)員執(zhí)行相應(yīng)操作服務(wù)員執(zhí)行相應(yīng)操作 n將結(jié)果返回給顧客

25、將結(jié)果返回給顧客 n實現(xiàn)實現(xiàn): RPCn副本復制緩存副本復制緩存 n將遠程文件復制到本地，然后如同本地文件一將遠程文件復制到本地，然后如同本地文件一樣訪問樣訪問 n問題問題: 一致性一致性 副本復制緩存副本復制緩存 n文件仍然由一個位于服務(wù)器上的主拷貝標識，文件仍然由一個位于服務(wù)器上的主拷貝標識，但其副本可能分散在多個站點上但其副本可能分散在多個站點上n當進程所需文件不在本地時，由服務(wù)器向本地當進程所需文件不在本地時，由服務(wù)器向本地緩存一個副本緩存一個副本.n存取操作在緩存副本上執(zhí)行存取操作在緩存副本上執(zhí)行.n緩存粒度緩存粒度n塊為單位，塊為單位，n整個文件為單位整個文件為單位.n緩存一致性問

26、題緩存一致性問題n保證主文件和緩存副本的一致保證主文件和緩存副本的一致.緩存副本存放方式緩存副本存放方式 n磁盤緩存磁盤緩存n更可靠更可靠n本地機器故障后恢復容易本地機器故障后恢復容易n內(nèi)存緩存內(nèi)存緩存n速度快速度快n支持無盤客戶端工作站支持無盤客戶端工作站 緩存更新策略緩存更新策略 n通寫通寫( (write through) ) 每當緩存副本發(fā)生變化每當緩存副本發(fā)生變化時就更新主本時就更新主本 n可靠性高；可靠性高；n一致性好；一致性好；n效率很低。效率很低。n延遲寫延遲寫( (delayed write) ) 副本數(shù)據(jù)經(jīng)過若干副本數(shù)據(jù)經(jīng)過若干次訪問次訪問( (更新更新) )后才最終寫回主

27、本后才最終寫回主本n實現(xiàn)效率較高；實現(xiàn)效率較高；n一致性差；一致性差；n可靠性低可靠性低，一旦副本所在結(jié)點失效則更新數(shù)據(jù)可能丟一旦副本所在結(jié)點失效則更新數(shù)據(jù)可能丟失。失。 緩存更新緩存更新策略策略( (Cont.) )n增量刷新增量刷新( (incremental flush) )n定時掃描緩存數(shù)據(jù)，只將上次更新后發(fā)生變定時掃描緩存數(shù)據(jù)，只將上次更新后發(fā)生變化的數(shù)據(jù)塊回寫到主本?；臄?shù)據(jù)塊回寫到主本。n關(guān)閉寫關(guān)閉寫( (write on close) )n只在文件被關(guān)閉時才將緩存信息寫回主本。只在文件被關(guān)閉時才將緩存信息寫回主本。 n適合于長時間對數(shù)據(jù)進行較多更新操作的應(yīng)用環(huán)適合于長時間對數(shù)據(jù)

28、進行較多更新操作的應(yīng)用環(huán)境境.9.10.4 有狀態(tài)服務(wù)與無狀態(tài)服務(wù)有狀態(tài)服務(wù)與無狀態(tài)服務(wù)n有狀態(tài)服務(wù)有狀態(tài)服務(wù)(State-full service)n服務(wù)器端保持文件狀態(tài)信息服務(wù)器端保持文件狀態(tài)信息n打開文件表，塊緩沖打開文件表，塊緩沖n無狀態(tài)服務(wù)無狀態(tài)服務(wù)(Stateless service)n服務(wù)器端不保持文件狀態(tài)信息服務(wù)器端不保持文件狀態(tài)信息n無打開文件表，塊緩沖無打開文件表，塊緩沖有狀態(tài)服務(wù)有狀態(tài)服務(wù)(state-full service)n特征特征nAPI界面中包含顯式的打開和關(guān)閉命令界面中包含顯式的打開和關(guān)閉命令n對于打開命令，文件服務(wù)器端需要將文件控對于打開命令，文件服務(wù)器端需

29、要將文件控制信息讀入內(nèi)存打開文件表中，同時維持文制信息讀入內(nèi)存打開文件表中，同時維持文件的讀寫指針件的讀寫指針n關(guān)閉時若控制信息已變化則回寫磁盤關(guān)閉時若控制信息已變化則回寫磁盤有狀態(tài)服務(wù)有狀態(tài)服務(wù)( (Cont.) )n優(yōu)點優(yōu)點n界面一致，遠程文件界面一致，遠程文件API與本地文件與本地文件API相同相同 n狀態(tài)信息在內(nèi)存，響應(yīng)快狀態(tài)信息在內(nèi)存，響應(yīng)快 n可以通過預(yù)先讀等手段提高訪問速度可以通過預(yù)先讀等手段提高訪問速度 n可以對文件加鎖可以對文件加鎖n缺點缺點n對于小量偶然性訪問使用麻煩，開銷大對于小量偶然性訪問使用麻煩，開銷大n服務(wù)器端以服務(wù)器端以open和和close識別遠程客戶會話期，一

30、識別遠程客戶會話期，一旦用戶不活動要及時撤銷文件控制信息，若遠程用旦用戶不活動要及時撤銷文件控制信息，若遠程用戶忘記戶忘記close則給狀態(tài)表維護帶來困難則給狀態(tài)表維護帶來困難無狀態(tài)服務(wù)無狀態(tài)服務(wù)(stateless service)n特征特征nAPI界面中不包含文件打開和關(guān)閉命令界面中不包含文件打開和關(guān)閉命令 n服務(wù)器端在內(nèi)存文件控制表中不保持遠程文服務(wù)器端在內(nèi)存文件控制表中不保持遠程文件訪問的控制信息件訪問的控制信息 n每個文件讀寫命令必須是自包含的每個文件讀寫命令必須是自包含的( (self contained) ) n遠程文件讀寫命令中包括：文件名、位置遠程文件讀寫命令中包括：文件名、

31、位置(記錄號記錄號)、內(nèi)存地址、內(nèi)存地址無狀態(tài)服務(wù)無狀態(tài)服務(wù)( (Cont.) ) n優(yōu)點優(yōu)點n服務(wù)器不需在內(nèi)存中保持文件狀態(tài)信息，節(jié)服務(wù)器不需在內(nèi)存中保持文件狀態(tài)信息，節(jié)省空間省空間n沒有打開文件數(shù)的限制沒有打開文件數(shù)的限制n不需識別遠程用戶的會話期，實現(xiàn)簡單，客不需識別遠程用戶的會話期，實現(xiàn)簡單，客戶崩潰時不會造成服務(wù)器錯誤戶崩潰時不會造成服務(wù)器錯誤n缺點缺點n大量訪問速度慢大量訪問速度慢n無法實現(xiàn)預(yù)先讀無法實現(xiàn)預(yù)先讀 選舉算法選舉算法nBully算法算法nSuppose That process Pi send a request that is not answered by the

32、coordinator within time interval T. In this situation, it is assumed that the coordinator has failed, and Pi tries to elect itself as the new coordinator. This task is completed through the following algorithm.Bully算法算法nProcess Pi send an election message to every process with a higher priority numb

33、er. Process Pi then wait for a time interval T for an answer from anyone of these processes.nIf no response is received within time T, Pi assumes that all processes with numbers greater than i have failed, and elects itself the new coordinator. Process Pi restart a new copy of the coordinator and se

34、nds a message to inform all active process with priority number less than I that Pi is the coordinator. Bully算法算法nIf an answer is received, Pi begins a time interval T, waiting to receive a message informing it that a process with higher priority number has been elected. (some other process is elect

35、ing itself coordinator, and should report the result within time T). If no message is sent within T, then the process with a higher number is assumed to have failed, and process Pi should restart the algorithm.Bully算法算法nIf Pi is not the coordinator, then, at any time during execution, Pi may receive one of the following messages from process Pj: