大學(xué)操作系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

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

13、eceive(發(fā)送者發(fā)送者,消息消息/回答回答): 由發(fā)送者由發(fā)送者處接收消息或回答處接收消息或回答, 然后繼續(xù)。然后繼續(xù)。 消息傳遞消息傳遞 (Message Passing)異步消息傳遞異步消息傳遞站點(diǎn)站點(diǎn)A, 進(jìn)程進(jìn)程Pisend(接收者，消息接收者，消息)繼續(xù)繼續(xù)receive(發(fā)送者，回答發(fā)送者，回答)站點(diǎn)站點(diǎn)B, 進(jìn)程進(jìn)程Pjreceive(發(fā)送者，消息發(fā)送者，消息)send(接收者，回答接收者，回答)9.7.2 套接字套接字(Socket)n套接字定義為通訊的一端套接字定義為通訊的一端 n地址形式為地址形式為( (IP,port) ) n套接字是一種低級(jí)套接字是一種低級(jí)(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當(dāng)一個(gè)進(jìn)程當(dāng)一個(gè)進(jìn)程Pi要求另外一個(gè)進(jìn)程要求另外一個(gè)進(jìn)程Pj保持的資源時(shí)，保持的資源時(shí)，Pi被允許等待，僅當(dāng)它具有比被允許等待，僅當(dāng)它具有比Pj更小的郵戳?xí)r間，更小的郵戳?xí)r間，即即Pi是比是比Pj更老，否則更老，否則Pi回退?；赝?。n例如，設(shè)進(jìn)程例如，設(shè)進(jìn)程 P1, P2, P3分別具有郵戳?xí)r間分別具有郵戳?xí)r間 5, 10, 15。n如果如果P1要求要求P2占用的資源占用的資源, 則則P1等待。等待。n如果如果P3要求要求P2占用的資源占用的資源, 則則P3回退。回退。n等

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

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

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

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

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

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

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

23、ted File System，DFS) n一般結(jié)構(gòu)一般結(jié)構(gòu) n命名與透明性命名與透明性 n遠(yuǎn)程文件存取遠(yuǎn)程文件存取 Remote File Accessn遠(yuǎn)程文件服務(wù)遠(yuǎn)程文件服務(wù) n副本復(fù)制副本復(fù)制 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)的分布式實(shí)現(xiàn)9.10.2 命名與透明性命名與透明性 n命名是邏輯實(shí)體到物理實(shí)體的映射命名是邏輯實(shí)體到物理實(shí)體的映射n對(duì)于真正意義的對(duì)于真正意義的DFS，整個(gè)系統(tǒng)具有統(tǒng)一的整個(gè)系統(tǒng)具有統(tǒng)一的命名機(jī)制，用戶以透明的視圖共享所有文件命名機(jī)制，用戶以透明的視圖共享所有文件

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

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

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

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

28、進(jìn)行較多更新操作的應(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對(duì)于打開命令，文件服務(wù)器端需要將文件控對(duì)于打開命令，文件服務(wù)器端需

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

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

31、位置(記錄號(hào)記錄號(hào))、內(nèi)存地址、內(nèi)存地址無狀態(tài)服務(wù)無狀態(tài)服務(wù)( (Cont.) ) n優(yōu)點(diǎn)優(yōu)點(diǎn)n服務(wù)器不需在內(nèi)存中保持文件狀態(tài)信息，節(jié)服務(wù)器不需在內(nèi)存中保持文件狀態(tài)信息，節(jié)省空間省空間n沒有打開文件數(shù)的限制沒有打開文件數(shù)的限制n不需識(shí)別遠(yuǎn)程用戶的會(huì)話期，實(shí)現(xiàn)簡單，客不需識(shí)別遠(yuǎn)程用戶的會(huì)話期，實(shí)現(xiàn)簡單，客戶崩潰時(shí)不會(huì)造成服務(wù)器錯(cuò)誤戶崩潰時(shí)不會(huì)造成服務(wù)器錯(cuò)誤n缺點(diǎn)缺點(diǎn)n大量訪問速度慢大量訪問速度慢n無法實(shí)現(xiàn)預(yù)先讀無法實(shí)現(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: