分布式系統(tǒng)與WEB服務(wù)(2)

《分布式系統(tǒng)與WEB服務(wù)(2)》由會(huì)員分享，可在線閱讀，更多相關(guān)《分布式系統(tǒng)與WEB服務(wù)(2)（88頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)第三章第三章分布式系統(tǒng)的同步分布式系統(tǒng)的同步和進(jìn)程和進(jìn)程 南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)31 時(shí)鐘同步時(shí)鐘同步 分布式算法的主要特征：分布式算法的主要特征：相關(guān)信息分布在多臺(tái)機(jī)器上相關(guān)信息分布在多臺(tái)機(jī)器上 進(jìn)程僅依據(jù)局部的信息作出決定進(jìn)程僅依據(jù)局部的信息作出決定一臺(tái)機(jī)器的故障不應(yīng)引起整個(gè)系統(tǒng)的失敗一臺(tái)機(jī)器的故障不應(yīng)引起整個(gè)系統(tǒng)的失敗沒(méi)有共用的全局時(shí)鐘。沒(méi)有共用的全局時(shí)鐘。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)1 1邏輯

2、時(shí)鐘邏輯時(shí)鐘先看一個(gè)例子先看一個(gè)例子:06121824303642485460081624324048566472800102030405060708090100ABCD三個(gè)有自己時(shí)鐘的進(jìn)程三個(gè)有自己時(shí)鐘的進(jìn)程,時(shí)鐘不同時(shí)鐘不同 運(yùn)行的結(jié)果是運(yùn)行的結(jié)果是消息消息C C在時(shí)間在時(shí)間6060上被上被發(fā)送發(fā)送,卻在時(shí)間點(diǎn)卻在時(shí)間點(diǎn)5454上到達(dá)上到達(dá)南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) LamportLamport的的算算法法以以”先先于于”關(guān)關(guān)系系為為基基礎(chǔ)礎(chǔ)，每每個(gè)個(gè)消消息息都都攜攜帶帶它它的的發(fā)發(fā)送送時(shí)時(shí)間間,當(dāng)當(dāng)它它到到達(dá)達(dá)目目的的地地時(shí)時(shí)，如如

3、果果目目的的地地的的時(shí)時(shí)間間早早于于它它的的發(fā)發(fā)送送時(shí)時(shí)間間，那那么么就就把把目目的的地地的的時(shí)時(shí)間間向向前前拔拔,至至少要比發(fā)送時(shí)間大少要比發(fā)送時(shí)間大1 1個(gè)單位個(gè)單位.0612182430364248707608162432404861697785800102030405060708090 100ABCD用用LamportLamport的的算算法法糾正時(shí)鐘糾正時(shí)鐘南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)該該算算法法解解決決了了全全局局時(shí)時(shí)鐘鐘問(wèn)問(wèn)題題，它它的的條條件件就就是是兩兩個(gè)個(gè)相相關(guān)關(guān)事件之間必須至少相差一個(gè)時(shí)間事件之間必須至少相差一個(gè)時(shí)間

4、2 2時(shí)鐘同步算法時(shí)鐘同步算法 邏邏輯輯時(shí)時(shí)鐘鐘只只給給出出事事物物的的相相對(duì)對(duì)時(shí)時(shí)間間,與與真真實(shí)實(shí)時(shí)時(shí)間間并并不不對(duì)對(duì)應(yīng)應(yīng),故要引入外部物理時(shí)鐘故要引入外部物理時(shí)鐘,常用的時(shí)鐘同步算法常用的時(shí)鐘同步算法:克里司帝安克里司帝安(CRISTIAN)(CRISTIAN)算法算法 具具有有國(guó)國(guó)家家標(biāo)標(biāo)致致時(shí)時(shí)間間接接收收器器的的機(jī)機(jī)器器,注注意意:調(diào)調(diào)整整的的方方法法,通通過(guò)過(guò)調(diào)調(diào)節(jié)節(jié)單單位位時(shí)時(shí)間間內(nèi)內(nèi)的的中中斷斷的的時(shí)時(shí)間間,來(lái)來(lái)逐逐步步完完成成時(shí)時(shí)鐘鐘的的調(diào)調(diào)整整.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)伯克利算法伯克利算法 計(jì)計(jì)算算平平均均時(shí)時(shí)間間

5、,它它是是一一個(gè)個(gè)集集中中式式算算法法,不不能能在在大大規(guī)規(guī)模模的的分布式系統(tǒng)中使用分布式系統(tǒng)中使用 原原理理:定定期期輪輪詢?cè)兠棵颗_(tái)臺(tái)機(jī)機(jī)器器的的時(shí)時(shí)間間,由由結(jié)結(jié)果果計(jì)計(jì)算算平平均均時(shí)時(shí)間間,各機(jī)器依此調(diào)整時(shí)間各機(jī)器依此調(diào)整時(shí)間.3 3同步時(shí)鐘的具體使用同步時(shí)鐘的具體使用 至多一次消息傳送至多一次消息傳送 消消息息的的時(shí)時(shí)間間戳戳比比存存儲(chǔ)儲(chǔ)的的時(shí)時(shí)間間戳戳的的值值早早,就就拒拒絕絕接接受受該該消息消息南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 基于時(shí)鐘的緩沖存儲(chǔ)器（基于時(shí)鐘的緩沖存儲(chǔ)器（CACHECACHE）的一致性）的一致性 使使用用CACHEC

6、ACHE會(huì)會(huì)出出現(xiàn)現(xiàn)一一致致性性問(wèn)問(wèn)題題，原原解解決決的的方方法法:區(qū)區(qū)分分讀讀寫寫緩緩存存,現(xiàn)現(xiàn)在在可可用用同同步步時(shí)時(shí)鐘鐘來(lái)來(lái)解解決決。即即通通過(guò)過(guò)提提供供有有效效期期（利利用有效的租約）用有效的租約）來(lái)控制來(lái)控制CACHECACHE一致性問(wèn)題。一致性問(wèn)題。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)3.2 3.2 互斥操作互斥操作 有有多多個(gè)個(gè)進(jìn)進(jìn)程程的的系系統(tǒng)統(tǒng)經(jīng)經(jīng)常常會(huì)會(huì)碰碰到到臨臨界界區(qū)區(qū)的的操操作作。當(dāng)當(dāng)一一個(gè)個(gè)進(jìn)進(jìn)程程要要訪訪問(wèn)問(wèn)某某個(gè)個(gè)共共享享數(shù)數(shù)據(jù)據(jù)時(shí)時(shí)，它它要要先先進(jìn)進(jìn)人人臨臨界界區(qū)區(qū)進(jìn)進(jìn)行行互互斥斥操操作作，確確保保沒(méi)沒(méi)有有別別的的

7、進(jìn)進(jìn)程程同同時(shí)時(shí)訪訪問(wèn)問(wèn)該該數(shù)數(shù)據(jù)據(jù)。在在單單機(jī)機(jī)系系統(tǒng)統(tǒng)中中，臨臨界界區(qū)區(qū)可可以以用用信信號(hào)號(hào)燈燈、管管程程來(lái)來(lái)實(shí)實(shí)現(xiàn)現(xiàn)。那那么么在在分分布布式式系系統(tǒng)統(tǒng)中中，由由于于不不能能共共享享主主存存，怎怎么么實(shí)實(shí)現(xiàn)現(xiàn)臨臨界界區(qū)區(qū)和和互互斥斥操操作作呢呢?下下面面我我們們討討論論幾種算法。幾種算法。集中式算法集中式算法 該該方方法法就就是是模模擬擬單單機(jī)機(jī)系系統(tǒng)統(tǒng),指指定定一一個(gè)個(gè)管管理理員員進(jìn)進(jìn)行行許許可可管管理理,該該算算法法保保證證了了互互斥斥,每每個(gè)個(gè)臨臨界界區(qū)區(qū)只只需需三三條條消消息息(申申請(qǐng)請(qǐng),許許可可,釋釋放放)南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB

8、服務(wù)服務(wù)1 10 02 2OKOK請(qǐng)求請(qǐng)求C C管理員管理員隊(duì)列空隊(duì)列空管理員管理員1 10 02 2不回答不回答請(qǐng)求請(qǐng)求C C隊(duì)列空隊(duì)列空1 10 02 2OKOK釋放釋放C C管理員管理員隊(duì)列空隊(duì)列空2 2 (A)(A)進(jìn)程進(jìn)程1 1向管理員請(qǐng)求向管理員請(qǐng)求進(jìn)入臨界區(qū)進(jìn)入臨界區(qū),得到許可得到許可 (B)(B)進(jìn)程進(jìn)程2 2向管理員請(qǐng)求進(jìn)向管理員請(qǐng)求進(jìn)入臨界區(qū)入臨界區(qū),管理員不回答管理員不回答 (C)(C)進(jìn)程進(jìn)程2 2向管理員請(qǐng)求進(jìn)向管理員請(qǐng)求進(jìn)入臨界區(qū)入臨界區(qū),管理員許可管理員許可缺點(diǎn)缺點(diǎn):集中式算法管理員是系統(tǒng)的瓶頸集中式算法管理員是系統(tǒng)的瓶頸南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)

9、院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式算法分布式算法 算法的條件算法的條件:系統(tǒng)中的事件必須有全局的順序系統(tǒng)中的事件必須有全局的順序 算法的工作過(guò)程如下算法的工作過(guò)程如下:當(dāng)當(dāng)一一個(gè)個(gè)進(jìn)進(jìn)程程要要進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)時(shí)時(shí)，它它構(gòu)構(gòu)造造一一條條包包括括臨臨界界區(qū)區(qū)名名、進(jìn)進(jìn)程程號(hào)號(hào)和和當(dāng)當(dāng)前前時(shí)時(shí)間間的的請(qǐng)請(qǐng)求求消消息息，然然后后把把該該消消息息廣廣播播給給其其他他的的所所有有進(jìn)進(jìn)程程。這這里里假假設(shè)設(shè)，消息的發(fā)送是可靠的。消息的發(fā)送是可靠的。當(dāng)一個(gè)進(jìn)程收到請(qǐng)求后，根據(jù)它的狀態(tài)采取相應(yīng)的動(dòng)作：當(dāng)一個(gè)進(jìn)程收到請(qǐng)求后，根據(jù)它的狀態(tài)采取相應(yīng)的動(dòng)作：(1)(1)當(dāng)接收者不在臨界區(qū)，并且也不想進(jìn)

10、入臨界區(qū)，就應(yīng)答發(fā)送者當(dāng)接收者不在臨界區(qū)，并且也不想進(jìn)入臨界區(qū)，就應(yīng)答發(fā)送者OKOK消息。消息。(2)(2)如果接收者已經(jīng)在臨界區(qū)中，它不回答僅僅把請(qǐng)求加入隊(duì)列。如果接收者已經(jīng)在臨界區(qū)中，它不回答僅僅把請(qǐng)求加入隊(duì)列。(3)(3)如如果果接接收收者者不不在在臨臨界界區(qū)區(qū)，但但它它也也想想進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)，就就要要將將收收到到消消息息的的時(shí)時(shí)間間戳戳和和它它廣廣播播消消息息的的時(shí)時(shí)間間戳戳比比較較.如如果果到到來(lái)來(lái)的的消消息息時(shí)時(shí)間間戳戳早早，接接收收者者回回答答發(fā)送者發(fā)送者OKOK消息；反之接收者把到來(lái)的請(qǐng)求加入隊(duì)列，不回答消息；反之接收者把到來(lái)的請(qǐng)求加入隊(duì)列，不回答.南京理工大學(xué)計(jì)算機(jī)學(xué)院

11、南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 在在發(fā)發(fā)完完進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)請(qǐng)請(qǐng)求求后后，進(jìn)進(jìn)程程將將等等待待所所有有的的允允許許消消息息，一一旦旦得得到到許許可可，就就可可進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)，當(dāng)當(dāng)退退出出時(shí)時(shí)向向隊(duì)隊(duì)列列中中的的所所有有進(jìn)進(jìn)程程發(fā)發(fā)OKOK消消息息，并并將將它它從從隊(duì)隊(duì)列列中刪除。中刪除。所有進(jìn)程都要參與決定是否進(jìn)入臨界區(qū)，若有進(jìn)程不能做，算法將出錯(cuò)。所有進(jìn)程都要參與決定是否進(jìn)入臨界區(qū)，若有進(jìn)程不能做，算法將出錯(cuò)。由于所有進(jìn)程都要參加算法，所以比集中式算法慢，復(fù)雜，開(kāi)銷大。由于所有進(jìn)程都要參加算法，所以比集中式算法慢，復(fù)雜，開(kāi)銷大。改進(jìn)算法：改進(jìn)算法：不需

12、所有進(jìn)程同意，部分回答不需所有進(jìn)程同意，部分回答OKOK即可即可 令牌環(huán)算法令牌環(huán)算法 進(jìn)進(jìn)程程只只有有擁?yè)碛杏辛盍钆婆茣r(shí)時(shí),才才能能進(jìn)進(jìn)入入臨臨界界區(qū)區(qū),一一個(gè)個(gè)進(jìn)進(jìn)程程從從相相鄰鄰的的進(jìn)進(jìn)程程收收到到令令牌牌時(shí)時(shí)先先檢檢查查自自己己是是非非要要進(jìn)進(jìn)入入臨臨界界區(qū)區(qū);如如果果要要,就就進(jìn)進(jìn)入入,否則就將令牌傳遞給下一個(gè)進(jìn)程否則就將令牌傳遞給下一個(gè)進(jìn)程.缺缺點(diǎn)點(diǎn):令令牌牌可可能能丟丟失失且且檢檢測(cè)測(cè)困困難難，一一個(gè)個(gè)要要進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)的的進(jìn)進(jìn)程最差情況下要等待其他進(jìn)程進(jìn)入和退出臨界區(qū)所用時(shí)間總和程最差情況下要等待其他進(jìn)程進(jìn)入和退出臨界區(qū)所用時(shí)間總和南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)

13、學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 三種算法的特點(diǎn)比較三種算法的特點(diǎn)比較集集中中式式算算法法簡(jiǎn)簡(jiǎn)單單、高高效效，每每次次進(jìn)進(jìn)入入和和離離開(kāi)開(kāi)臨臨界界區(qū)區(qū)只只需需3 3次次消消息息傳傳遞遞：請(qǐng)請(qǐng)求求、許許可可；釋釋放放，分分布布式式算算法法中中，n n個(gè)個(gè)進(jìn)進(jìn)程程需需要要(n-1)(n-1)個(gè)個(gè)請(qǐng)請(qǐng)求求和和(n-1)(n-1)個(gè)個(gè)許許可可，總總共共要要2(n2(n1)1)個(gè)個(gè)消消息息。在在令令牌牌環(huán)環(huán)算算法法中中，所所需需的的消消息息數(shù)數(shù)是是不不固固定定的的。如如果果每每個(gè)個(gè)進(jìn)進(jìn)程程都都要要進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)，那那么么每每個(gè)個(gè)令令牌牌都都有有一一次次進(jìn)進(jìn)人人和和退退出出，平平均均每每次

14、次進(jìn)進(jìn)入入有有個(gè)個(gè)消消息息傳傳遞遞；如如果果令令牌牌被被一一個(gè)個(gè)進(jìn)進(jìn)程程占占有有很很長(zhǎng)長(zhǎng)時(shí)時(shí)間間，那那么進(jìn)入臨界區(qū)需要的消息就不確定。么進(jìn)入臨界區(qū)需要的消息就不確定。進(jìn)進(jìn)程程從從它它發(fā)發(fā)出出進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)的的請(qǐng)請(qǐng)求求到到它它進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)的的時(shí)時(shí)間間延延遲遲在在三三個(gè)個(gè)算算法法中中是是不不同同的的,當(dāng)當(dāng)臨臨界界區(qū)區(qū)很很短短并并且且使使用用頻頻率率很很低低時(shí)時(shí)，進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)時(shí)時(shí)間間延延遲遲的的決決定定因因素素是是進(jìn)進(jìn)人人臨臨界界區(qū)區(qū)的的控控制制機(jī)機(jī)制制當(dāng)當(dāng)臨臨界界區(qū)區(qū)很很長(zhǎng)長(zhǎng)并并且且使使用用的的頻頻率率很高時(shí)，決定因素在于等待時(shí)間，消息數(shù)就能說(shuō)明這一點(diǎn)。很高時(shí)，決定因素在于等

15、待時(shí)間，消息數(shù)就能說(shuō)明這一點(diǎn)。這這三三種種算算法法出出現(xiàn)現(xiàn)故故障障時(shí)時(shí),都都會(huì)會(huì)有有很很大大影影響響,要要避避免免系系統(tǒng)統(tǒng)的的崩崩潰潰,須須注注意意:在容錯(cuò)系統(tǒng)中在容錯(cuò)系統(tǒng)中,次三種算法都不適用次三種算法都不適用.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)3.3選舉算法選舉算法 在在分分布布式式系系統(tǒng)統(tǒng)中中，大大多多數(shù)數(shù)算算法法要要求求有有一一個(gè)個(gè)進(jìn)進(jìn)程程充充當(dāng)當(dāng)管管理理員員或或初初始始啟啟動(dòng)動(dòng)者者等等特特殊殊角角色色。前前面面幾幾個(gè)個(gè)算算法法就就有有這這樣樣的的例例子子。一一般般來(lái)來(lái)說(shuō)說(shuō)，由由哪哪個(gè)個(gè)進(jìn)進(jìn)程程充充當(dāng)當(dāng)特特定定角角色色無(wú)無(wú)關(guān)關(guān)緊緊要要，但

16、但是是必必須須有有一一個(gè)個(gè)進(jìn)進(jìn)程程做做這這個(gè)個(gè)工工作作。下下面面我我們們來(lái)來(lái)看看如如何何選選一一個(gè)個(gè)進(jìn)程擔(dān)當(dāng)特定角色。進(jìn)程擔(dān)當(dāng)特定角色。選選舉舉算算法法的的目目的的是是當(dāng)當(dāng)選選舉舉完完成成后后，能能夠夠讓讓所所有有的的進(jìn)進(jìn)程程知道誰(shuí)是管理員知道誰(shuí)是管理員.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)1.霸道算法霸道算法 該該算算法法提提出出。當(dāng)當(dāng)一一個(gè)個(gè)進(jìn)進(jìn)程程P P注注意意到到管管理理員員不不再再對(duì)對(duì)請(qǐng)請(qǐng)求求作作出反應(yīng)時(shí)，它就開(kāi)始選舉進(jìn)程出反應(yīng)時(shí)，它就開(kāi)始選舉進(jìn)程P P執(zhí)行下列步驟：執(zhí)行下列步驟：(1)(1)向所有向所有進(jìn)程號(hào)比它大進(jìn)程號(hào)比它大的進(jìn)程發(fā)送

17、的進(jìn)程發(fā)送ELECTIONELECTION消息；消息；(2)(2)如果沒(méi)有進(jìn)程響應(yīng)，進(jìn)程如果沒(méi)有進(jìn)程響應(yīng)，進(jìn)程P P成為管理員；成為管理員；(3)(3)如果有進(jìn)程響應(yīng)，該響應(yīng)進(jìn)程成為管理員，如果有進(jìn)程響應(yīng)，該響應(yīng)進(jìn)程成為管理員，P P結(jié)束選舉。結(jié)束選舉。注注意意：一一個(gè)個(gè)進(jìn)進(jìn)程程只只能能從從號(hào)號(hào)碼碼比比它它小小的的進(jìn)進(jìn)程程處處得得到到一一個(gè)個(gè)選選擇擇消息消息南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)2 20 05 53 36 64 41 17 7(A)(A)進(jìn)程進(jìn)程4 4啟動(dòng)選舉啟動(dòng)選舉2 20 05 53 36 64 41 17 7(B)(B)進(jìn)程進(jìn)程

18、5,65,6響應(yīng)響應(yīng),讓讓4 4停止停止2 20 05 53 36 64 41 17 7(C)(C)進(jìn)進(jìn)程程5,6,5,6,都都啟啟動(dòng)動(dòng)選選舉舉2 20 05 53 36 64 41 17 7(D)(D)進(jìn)進(jìn)程程6 6讓讓進(jìn)進(jìn)程程5 5停停止止選舉選舉2 20 05 53 36 64 41 17 7(E)(E)進(jìn)進(jìn)程程6 6成成為為管管理理員員,發(fā)通知發(fā)通知霸道算法圖示霸道算法圖示南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)2.環(huán)形算法環(huán)形算法 這這個(gè)個(gè)算算法法使使用用環(huán)環(huán)，但但不不是是令令牌牌環(huán)環(huán)。這這里里假假定定所所有有的的進(jìn)進(jìn)程程都都是是有有序序號(hào)號(hào)

19、的的，即即每每個(gè)個(gè)進(jìn)進(jìn)程程都都知知道道它它的的后后繼繼進(jìn)進(jìn)程程。當(dāng)當(dāng)一一個(gè)個(gè)進(jìn)進(jìn)程程發(fā)發(fā)現(xiàn)現(xiàn)管管理理員員不不能能工工作作時(shí)時(shí)，它它把把包包含含其其進(jìn)進(jìn)程程號(hào)號(hào)的的ELECTIONELECTION消消息息發(fā)發(fā)給給它它的的后后繼繼進(jìn)進(jìn)程程；接接收收消消息息的的進(jìn)進(jìn)程程再再向向后后繼繼進(jìn)進(jìn)程程發(fā)發(fā)送送ELECTIONELECTION消消息息。如如果果接接收收進(jìn)進(jìn)程程沒(méi)沒(méi)有有反反應(yīng)應(yīng)，發(fā)發(fā)送送消消息息的的進(jìn)進(jìn)程程便便向向下下一一個(gè)個(gè)進(jìn)進(jìn)程程發(fā)發(fā)消消息息。每每一一次次發(fā)發(fā)送送ELECTIONELECTION，進(jìn)進(jìn)程程都都要要將將自自己己的的進(jìn)進(jìn)程程號(hào)號(hào)加加入入消息。消息。2 20 04 46 65 51

20、 13 37 7使用環(huán)形選舉算法使用環(huán)形選舉算法選舉消息選舉消息選舉消息選舉消息2 23 32 25 55 56 65 56 60 0 出現(xiàn)故障的出現(xiàn)故障的管理員管理員南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 最最后后，第第一一個(gè)個(gè)發(fā)發(fā)出出該該選選舉舉（ELECTIONELECTION）消消息息進(jìn)進(jìn)程程收收到到該該消消息息,再再將將其其轉(zhuǎn)轉(zhuǎn)換換為為協(xié)協(xié)調(diào)調(diào)（COORDINATORCOORDINATOR）消消息息后后，再再循循環(huán)環(huán)一一周周,通通知知誰(shuí)誰(shuí)是是管管理理員員，誰(shuí)誰(shuí)是是組組成成員員，這這時(shí)時(shí)消消息息包包中中進(jìn)進(jìn)程程號(hào)號(hào)最最高高的的進(jìn)進(jìn)程程將將成成

21、為為管管理理員員。當(dāng)當(dāng)這這個(gè)個(gè)消消息息循循環(huán)環(huán)一一周周后后，由由發(fā)發(fā)送送進(jìn)進(jìn)程程把把它它從從網(wǎng)網(wǎng)上上清除。清除。圖圖中中2 2和和5 5都都發(fā)發(fā)現(xiàn)現(xiàn)7 7失失效效，分分別別建建立立選選舉舉消消息息，兩兩條條消消息息都都沿環(huán)運(yùn)行，結(jié)果是一樣的，只是浪費(fèi)了帶寬。沿環(huán)運(yùn)行，結(jié)果是一樣的，只是浪費(fèi)了帶寬。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)34 線線 程程 進(jìn)進(jìn)程程因因等等待待而而掛掛起起,使使進(jìn)進(jìn)程程中中可可并并行行部部分分不不能能執(zhí)執(zhí)行行,從從而而使系統(tǒng)性能下降使系統(tǒng)性能下降,故引入故引入-線程線程.1.1.線線程程：就就是是可可以以共共享享地地址址空

22、空間間的的輕輕型型進(jìn)進(jìn)程程，它它有有自自己己的的程程序序寄寄記記數(shù)數(shù)器器棧棧和和寄寄存存器器集集合合。它它與與進(jìn)進(jìn)程程的的主主要要區(qū)區(qū)別別是是它它的地址空間是共享的。的地址空間是共享的。線程相對(duì)于進(jìn)程，猶如進(jìn)程相對(duì)于機(jī)器線程相對(duì)于進(jìn)程，猶如進(jìn)程相對(duì)于機(jī)器 2.2.線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng)線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng).多線程組織的常用模型：多線程組織的常用模型：南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 1)1)分配器工作者模型分配器工作者模型 有一個(gè)分配器線程喚醒工作者線程可用信號(hào)燈有一個(gè)分配器線程喚醒工作者線程可用信號(hào)燈 2

23、)2)團(tuán)隊(duì)模型團(tuán)隊(duì)模型 地位平等地位平等 線程各自獲取和處理自己的請(qǐng)求線程各自獲取和處理自己的請(qǐng)求.3)3)流水線模型流水線模型 管管道道線線模模型型，第第一一個(gè)個(gè)線線程程產(chǎn)產(chǎn)生生一一些些數(shù)數(shù)據(jù)據(jù)傳傳給給下下一一個(gè)個(gè)線線程處理，且持續(xù)下去。程處理，且持續(xù)下去。多多線線程程可可分分時(shí)時(shí)工工作作在在單單CPUCPU上上也也可可工工作作在在多多處處理理器器系系統(tǒng)統(tǒng)上上,而而且且多多線線程程系系統(tǒng)統(tǒng)設(shè)設(shè)計(jì)計(jì)的的好好將將可可與與多多處處理理機(jī)機(jī)工工作作性性能能相當(dāng)相當(dāng).南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)共享緩沖區(qū)共享緩沖區(qū)到達(dá)的工作請(qǐng)求到達(dá)的工作請(qǐng)求郵箱郵

24、箱文件服務(wù)器進(jìn)程文件服務(wù)器進(jìn)程分配器線程分配器線程工作者線程工作者線程到達(dá)的工作請(qǐng)求到達(dá)的工作請(qǐng)求到達(dá)的工作請(qǐng)求到達(dá)的工作請(qǐng)求內(nèi)核內(nèi)核分配器分配器/工作者模型工作者模型流水線模型流水線模型團(tuán)體模型團(tuán)體模型進(jìn)程中線程三種組織方式進(jìn)程中線程三種組織方式南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)3.3.線程包的設(shè)計(jì)的相關(guān)問(wèn)題線程包的設(shè)計(jì)的相關(guān)問(wèn)題線程包就是供用戶或程序員調(diào)用的關(guān)于線程的一組原語(yǔ)。線程包就是供用戶或程序員調(diào)用的關(guān)于線程的一組原語(yǔ)。線程的管理方法有靜態(tài)和動(dòng)態(tài)方法兩種。線程的管理方法有靜態(tài)和動(dòng)態(tài)方法兩種。靜態(tài)靜態(tài)即開(kāi)始就確定好線程的個(gè)數(shù)即開(kāi)始就確定好

25、線程的個(gè)數(shù)，動(dòng)態(tài)，動(dòng)態(tài)個(gè)數(shù)個(gè)數(shù)不定不定 線程的代碼與進(jìn)程一樣，由多個(gè)過(guò)程組成。線程的代碼與進(jìn)程一樣，由多個(gè)過(guò)程組成。線程包中臨界區(qū)控制利用互斥體（線程包中臨界區(qū)控制利用互斥體（mutex),mutex),其總處于：其總處于：打開(kāi)和鎖住兩種狀態(tài)打開(kāi)和鎖住兩種狀態(tài) lock mutex;lock mutex;check data structures lock mutex check data structures lock mutex while(resource busy)mark resource as free;while(resource busy)mark resource as fr

26、ee;wait(condition varable);unlock mutex;wait(condition varable);unlock mutex;mark resource as busy;wakeuo(condition variable);mark resource as busy;wakeuo(condition variable);unlock mutex;unlock mutex;互斥變量與條件變量的使用互斥變量與條件變量的使用南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 線程可由算法進(jìn)行調(diào)度，如優(yōu)先級(jí)調(diào)度、循環(huán)調(diào)度等線程可由算法進(jìn)行調(diào)度

27、，如優(yōu)先級(jí)調(diào)度、循環(huán)調(diào)度等4.4.線程包的實(shí)現(xiàn)線程包的實(shí)現(xiàn)1)1)在用戶空間實(shí)現(xiàn)線程（如圖）在用戶空間實(shí)現(xiàn)線程（如圖）這這種種方方法法是是將將線線程程包包完完全全放放在在用用戶戶空空間間，內(nèi)內(nèi)核核對(duì)對(duì)此此一一無(wú)無(wú)所所知知，在在這這種種方方法法中中，內(nèi)內(nèi)核核只只是是管管理理普普通通的的單單線線程程進(jìn)進(jìn)程程。這這種種方方法法最最明明顯顯的的優(yōu)優(yōu)點(diǎn)點(diǎn)是是它它可可以以在在一一個(gè)個(gè)不不支支持持多多線線程程的的操操作作系系統(tǒng)統(tǒng)上上實(shí)實(shí)現(xiàn)現(xiàn)用用戶戶線線程程包包。同同時(shí)時(shí)它它還還允允許許每每個(gè)個(gè)進(jìn)進(jìn)程程有有自自己己特特定的調(diào)度算法定的調(diào)度算法.線程1線程2線程3線程4線程5線程6運(yùn)行期系統(tǒng)運(yùn)行期系統(tǒng)內(nèi)內(nèi)核核內(nèi)

28、核空間內(nèi)核空間用戶空間用戶空間南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 缺點(diǎn)是：缺點(diǎn)是：數(shù)量太多會(huì)引起資源緊張數(shù)量太多會(huì)引起資源緊張.同時(shí)同時(shí) (1)(1)它也難實(shí)現(xiàn)阻塞系統(tǒng)的調(diào)用它也難實(shí)現(xiàn)阻塞系統(tǒng)的調(diào)用.(2)(2)它它的的調(diào)調(diào)度度是是非非搶搶先先式式的的.進(jìn)進(jìn)程程內(nèi)內(nèi)部部無(wú)無(wú)時(shí)時(shí)鐘鐘中中斷斷,無(wú)法進(jìn)行時(shí)間片的調(diào)度無(wú)法進(jìn)行時(shí)間片的調(diào)度.2)2)在操作系統(tǒng)內(nèi)核實(shí)現(xiàn)（如圖）在操作系統(tǒng)內(nèi)核實(shí)現(xiàn)（如圖）不不需需要要運(yùn)運(yùn)行行系系統(tǒng)統(tǒng),線線程程創(chuàng)創(chuàng)建建或或撤撤銷銷,只只需需一一次次系系統(tǒng)統(tǒng)調(diào)調(diào)用用,比比在在用用戶戶空空間間實(shí)實(shí)現(xiàn)現(xiàn)線線程程開(kāi)開(kāi)銷銷大大.可可通通過(guò)

29、過(guò)在在撤撤銷銷時(shí)時(shí)加加標(biāo)標(biāo)記記，當(dāng)做為新線程創(chuàng)建時(shí)僅需激活即可。當(dāng)做為新線程創(chuàng)建時(shí)僅需激活即可。線程1線程2線程3線程4線程5線程6內(nèi)內(nèi)核核用戶空間用戶空間內(nèi)核空間內(nèi)核空間南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 3)3)調(diào)度員活動(dòng)方法調(diào)度員活動(dòng)方法 結(jié)結(jié)合合前前兩兩種種的的優(yōu)優(yōu)點(diǎn)點(diǎn)(用用戶戶線線程程的的高高性性能能和和內(nèi)內(nèi)核核線線程程的的實(shí)實(shí)現(xiàn)簡(jiǎn)單現(xiàn)簡(jiǎn)單)原原理理：當(dāng)當(dāng)使使用用調(diào)調(diào)度度員員活活動(dòng)動(dòng)方方法法時(shí)時(shí)，內(nèi)內(nèi)核核給給每每個(gè)個(gè)進(jìn)進(jìn)分分配配一一些些“虛虛處處理理器器”，并并由由運(yùn)運(yùn)行行系系統(tǒng)統(tǒng)分分給給線線程程，同同時(shí)時(shí)通通過(guò)過(guò)避避免免在在用用戶戶空

30、空間間和和內(nèi)內(nèi)核核空空間間之之間間的的不不必必要要的的轉(zhuǎn)轉(zhuǎn)換換來(lái)來(lái)實(shí)實(shí)現(xiàn)現(xiàn)高高效效率率。如如：線線程程在在局局部部信信號(hào)號(hào)上上阻阻塞塞并并不不去去涉涉及及內(nèi)內(nèi)核核，而而是是由由用用戶戶運(yùn)運(yùn)行行期期系系統(tǒng)統(tǒng)去去完完成成阻阻塞塞和和調(diào)調(diào)度度。具具體體是是由由內(nèi)內(nèi)核核激激活活用用戶運(yùn)行期系統(tǒng)戶運(yùn)行期系統(tǒng)南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 4)4)線程和線程和RPCRPC 希希望望使使一一個(gè)個(gè)進(jìn)進(jìn)程程中中的的線線程程可可以以有有效效的的調(diào)調(diào)用用同同一一臺(tái)臺(tái)機(jī)機(jī)器器上上的的另另一一個(gè)個(gè)進(jìn)進(jìn)程程中中的的線線程程，具具體體采采用用與與RPC RPC 相相似似的

31、的過(guò)過(guò)程程完完成成。加加速速RPCRPC執(zhí)執(zhí)行行的的技技術(shù)術(shù)，具具體體即即為為當(dāng)當(dāng)一一個(gè)個(gè)線線程程執(zhí)執(zhí)行行請(qǐng)請(qǐng)求求時(shí)時(shí)，它它將將消消失失并并且且它它的的堆堆棧棧和和環(huán)環(huán)境境信信息息也也丟丟棄棄，當(dāng)當(dāng)有有新新的的消消息息進(jìn)進(jìn)入入時(shí)時(shí)，內(nèi)內(nèi)核核動(dòng)動(dòng)態(tài)態(tài)創(chuàng)創(chuàng)建建一一個(gè)個(gè)新新線線程程去去為為其其服服務(wù)務(wù)。優(yōu)優(yōu)點(diǎn)點(diǎn)首首先先線線程程不不用用等等待待所所以以不不保保留留環(huán)環(huán)境境，其其次次創(chuàng)創(chuàng)建建新新線線程程比比存存儲(chǔ)儲(chǔ)一一個(gè)個(gè)存存在在的的線線程程花花費(fèi)費(fèi)少少，節(jié)節(jié)約約了了時(shí)時(shí)間間減減少少了了開(kāi)開(kāi)銷銷，從從而而提提高高了速度。了速度。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服

32、務(wù)服務(wù)35 分布式系統(tǒng)模型分布式系統(tǒng)模型 1 1工作站模型工作站模型 其其主主要要指指：一一組組工工作作站站通通過(guò)過(guò)高高速速局局域域網(wǎng)網(wǎng)互互連連，在在某某一一時(shí)時(shí)刻刻,每臺(tái)機(jī)器只有一個(gè)用戶登錄，即擁有者，要么空閑。每臺(tái)機(jī)器只有一個(gè)用戶登錄，即擁有者，要么空閑。優(yōu)優(yōu)點(diǎn)點(diǎn)：清清晰晰、易易于于理理解解，計(jì)計(jì)算算能能力力固固定定、系系統(tǒng)統(tǒng)反反應(yīng)應(yīng)時(shí)時(shí)間間固固定定、有有一一定定的的自自主主性性、同同時(shí)時(shí)增增強(qiáng)強(qiáng)了了獨(dú)獨(dú)立立性性。缺缺點(diǎn)點(diǎn):資資源源存存在浪費(fèi)在浪費(fèi),資源利用率不高資源利用率不高.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 2.2.空閑工作站的使用空閑

33、工作站的使用 1 1）找出空閑工作站）找出空閑工作站 兩種定位方式：服務(wù)器驅(qū)動(dòng)和客戶端驅(qū)動(dòng)兩種定位方式：服務(wù)器驅(qū)動(dòng)和客戶端驅(qū)動(dòng) 2 2）透明運(yùn)行遠(yuǎn)程進(jìn)程）透明運(yùn)行遠(yuǎn)程進(jìn)程 由內(nèi)核完成由內(nèi)核完成 3 3）機(jī)主人重新使用時(shí)如何處理）機(jī)主人重新使用時(shí)如何處理 直直接接殺殺死死進(jìn)進(jìn)程程、移移植植到到另另一一臺(tái)臺(tái)機(jī)機(jī)器器上上（進(jìn)進(jìn)程程全全部部包包括括子進(jìn)程）子進(jìn)程）南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 3.3.處理機(jī)池模型處理機(jī)池模型 處處理理機(jī)機(jī)池池是是無(wú)無(wú)盤盤工工作作站站的的進(jìn)進(jìn)一一步步發(fā)發(fā)展展。理理論論依依據(jù)據(jù)是是排排隊(duì)隊(duì)論論,具具體體有有理理發(fā)發(fā)師師

34、模模型型、超超市市收收款款等等。CPUCPU根根據(jù)據(jù)需需求求動(dòng)動(dòng)態(tài)態(tài)的的分分配給用戶。模型如圖配給用戶。模型如圖 雖雖然然有有證證明明：用用一一個(gè)個(gè)是是小小系系統(tǒng)統(tǒng)功功能能N N倍倍的的大大系系統(tǒng)統(tǒng)來(lái)來(lái)代代替替N N個(gè)獨(dú)立的小系統(tǒng)的資源可把平均響應(yīng)時(shí)間減少為原來(lái)的個(gè)獨(dú)立的小系統(tǒng)的資源可把平均響應(yīng)時(shí)間減少為原來(lái)的1/N1/N倍。倍。文件服務(wù)器文件服務(wù)器處理機(jī)池處理機(jī)池CPUCPU南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 然然而而平平均均響響應(yīng)應(yīng)時(shí)時(shí)間間不不代代表表一一切切，從從費(fèi)費(fèi)用用角角度度來(lái)來(lái)看看，不不惜惜代價(jià)建造巨型機(jī)甚至是不可能的。代價(jià)建造巨型機(jī)

35、甚至是不可能的。同同時(shí)時(shí)也也并并不不是是有有N N個(gè)個(gè)處處理理器器的的處處理理機(jī)機(jī)池池就就可可比比單單個(gè)個(gè)處處理理器器的性能高的性能高N N倍，倍，而是決定于任務(wù)可分幾部分。而是決定于任務(wù)可分幾部分。4.4.混合模型混合模型 用用那那種種模模型型要要依依情情況況而而定定,若若是是偶偶發(fā)發(fā)的的事事件件為為主主,則則個(gè)個(gè)人人工工作作站站模模型型機(jī)機(jī)可可,若若是是仿仿真真或或工工程程計(jì)計(jì)算算則則用用處處理理機(jī)機(jī)池池較較好好,也也可兩者結(jié)合可兩者結(jié)合.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)36 處理機(jī)分配與調(diào)度處理機(jī)分配與調(diào)度 如何決定進(jìn)程運(yùn)行在那臺(tái)機(jī)器上，

36、即為處理機(jī)的分配。如何決定進(jìn)程運(yùn)行在那臺(tái)機(jī)器上，即為處理機(jī)的分配。1.1.分配模型分配模型1 1）分配策略有兩大類）分配策略有兩大類:非遷移的（進(jìn)程創(chuàng)建后，一直呆到進(jìn)程結(jié)束）非遷移的（進(jìn)程創(chuàng)建后，一直呆到進(jìn)程結(jié)束）遷移的（進(jìn)程可在運(yùn)行中遷移到其它機(jī)器上運(yùn)行）遷移的（進(jìn)程可在運(yùn)行中遷移到其它機(jī)器上運(yùn)行）2 2）分配算法的目標(biāo)：）分配算法的目標(biāo)：(1)(1)最大限度地提高最大限度地提高CPUCPU利用率利用率 (2)(2)盡可能縮短平均響應(yīng)時(shí)間盡可能縮短平均響應(yīng)時(shí)間 (3)(3)最小化響應(yīng)率最小化響應(yīng)率南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)例如：例如：有

37、兩個(gè)處理機(jī)有兩個(gè)處理機(jī)1及及2和和兩個(gè)進(jìn)程兩個(gè)進(jìn)程A及及BA（1億條指令）億條指令）10秒秒6秒秒B（3億條指令）億條指令）30秒秒8秒秒分配分配1：處理機(jī)處理機(jī)1運(yùn)行進(jìn)程運(yùn)行進(jìn)程A，處理機(jī)，處理機(jī)2運(yùn)行進(jìn)程運(yùn)行進(jìn)程B，平均響應(yīng)，平均響應(yīng)時(shí)間為（時(shí)間為（10+8）/2=9秒秒（較優(yōu)）（較優(yōu)）分配分配2：處理機(jī)處理機(jī)2運(yùn)行進(jìn)程運(yùn)行進(jìn)程A，處理機(jī)，處理機(jī)1運(yùn)行進(jìn)程運(yùn)行進(jìn)程B，平均響應(yīng)，平均響應(yīng)時(shí)間為（時(shí)間為（30+6）/2=18秒秒處理機(jī)處理機(jī)1 110MIPS10MIPS處理機(jī)處理機(jī)2 2100MIPS100MIPS5 5秒隊(duì)列秒隊(duì)列南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式

38、系統(tǒng)與WEB服務(wù)服務(wù)2 2設(shè)計(jì)分配算法的主要相關(guān)問(wèn)題設(shè)計(jì)分配算法的主要相關(guān)問(wèn)題1）確定式還是啟發(fā)式）確定式還是啟發(fā)式 確確定定式式適適用用進(jìn)進(jìn)程程是是否否可可預(yù)預(yù)知知;啟啟發(fā)發(fā)是是指指以以經(jīng)經(jīng)驗(yàn)驗(yàn)性性規(guī)規(guī)則則和和信信息指導(dǎo)息指導(dǎo).2）集中式還是分布式）集中式還是分布式 依全局信息做判定依全局信息做判定,以局部信息做判斷以局部信息做判斷.3）最優(yōu)的還是次優(yōu)的）最優(yōu)的還是次優(yōu)的 4）局部的還是全局的）局部的還是全局的 解決轉(zhuǎn)移策略解決轉(zhuǎn)移策略5）發(fā)送者初啟還是接收者初啟）發(fā)送者初啟還是接收者初啟解決定位策略解決定位策略南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服

39、務(wù) 3 3處理機(jī)分配算法實(shí)現(xiàn)中的問(wèn)題處理機(jī)分配算法實(shí)現(xiàn)中的問(wèn)題 1 1）對(duì)負(fù)載的測(cè)量）對(duì)負(fù)載的測(cè)量 2 2）額外開(kāi)銷的處理）額外開(kāi)銷的處理 3 3）問(wèn)題的復(fù)雜度）問(wèn)題的復(fù)雜度 4 4）穩(wěn)定性問(wèn)題）穩(wěn)定性問(wèn)題 4 4典型的處理機(jī)分配算法典型的處理機(jī)分配算法 1)1)圖論決策算法圖論決策算法 2)2)集中式算法（集中式算法（上上下算法）下算法）3)3)層次算法層次算法 邏輯上構(gòu)成分層結(jié)構(gòu)邏輯上構(gòu)成分層結(jié)構(gòu) 4)4)投投標(biāo)標(biāo)算算法法 把把系系統(tǒng)統(tǒng)中中的的資資源源和和任任務(wù)務(wù)作作為為買買方方和和賣賣方方以以尋求平衡尋求平衡.A AB BC CD DG GI IH H2 22 22 25 55 58 8

40、1 11 14 44 43 3A AB BC CD DG GI IH H2 22 22 25 55 58 81 11 14 44 43 3F FF FE EE E3030單位通信量單位通信量2828單位通信量單位通信量南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 5 5調(diào)度調(diào)度假假設(shè)設(shè)進(jìn)進(jìn)程程成成組組創(chuàng)創(chuàng)建建,組組間間通通信信比比組組內(nèi)內(nèi)通通信信要要少少,基基于于協(xié)協(xié)同同調(diào)度調(diào)度概念的算法概念的算法.算法使用一個(gè)矩陣算法使用一個(gè)矩陣 列是處理機(jī)的進(jìn)程表列是處理機(jī)的進(jìn)程表 行是時(shí)間段的進(jìn)程表行是時(shí)間段的進(jìn)程表主主要要思思想想:每每個(gè)個(gè)處處理理機(jī)機(jī)采采用用時(shí)時(shí)

41、間間片片輪輪轉(zhuǎn)轉(zhuǎn)法法,因因此此可可將將進(jìn)進(jìn)程程組的所有成員放在不同處理機(jī)上的同一時(shí)間段組的所有成員放在不同處理機(jī)上的同一時(shí)間段處理機(jī)處理機(jī)時(shí)間片時(shí)間片南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)實(shí)實(shí)現(xiàn)現(xiàn)文文件件服服務(wù)務(wù)的的技技術(shù)術(shù)對(duì)對(duì)于于分分布布式式系系統(tǒng)統(tǒng)的的設(shè)設(shè)計(jì)計(jì)非常重要。非常重要。在在分分布布式式系系統(tǒng)統(tǒng)中中，必必須須提提供供與與傳傳統(tǒng)統(tǒng)文文件件系系統(tǒng)統(tǒng)相相當(dāng)當(dāng)?shù)牡男孕阅苣芎秃涂煽煽靠啃孕?。?shí)實(shí)現(xiàn)現(xiàn)分分布布式式文文件件服服務(wù)務(wù)器器的的技技術(shù)術(shù)源源自自傳傳統(tǒng)統(tǒng)系系統(tǒng)統(tǒng)，但但由由于于要要將將許許多多設(shè)設(shè)施施分分布布在在多多個(gè)個(gè)不不同同的的服服務(wù)務(wù)器器中

42、中，系系統(tǒng)統(tǒng)結(jié)結(jié)構(gòu)構(gòu)有有所所不不同同，因因此此，其技術(shù)要求及高于傳統(tǒng)系統(tǒng)。其技術(shù)要求及高于傳統(tǒng)系統(tǒng)。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)共享共享持久性持久性分布式分布式緩存緩存/副本副本維護(hù)維護(hù)一致性一致性例子例子主存主存1RAM文件系統(tǒng)文件系統(tǒng)1UNIX文件系統(tǒng)文件系統(tǒng)分布式文件系統(tǒng)分布式文件系統(tǒng)SUNNFSWEBWEB服務(wù)器服務(wù)器分布式共享內(nèi)存分布式共享內(nèi)存 IVY遠(yuǎn)程對(duì)象遠(yuǎn)程對(duì)象1CORBA持久對(duì)象存儲(chǔ)持久對(duì)象存儲(chǔ)1CORBA持久對(duì)象存儲(chǔ)持久對(duì)象存儲(chǔ)持久分布式對(duì)象存儲(chǔ)持久分布式對(duì)象存儲(chǔ)PERDIS南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分

43、布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)第第四四章章分布式文件服務(wù)分布式文件服務(wù)南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)41 引引 言言文文件件被被認(rèn)認(rèn)為為是是一一個(gè)個(gè)基基于于磁磁盤盤或或其其它它二二級(jí)級(jí)存存儲(chǔ)儲(chǔ)器器的的存存儲(chǔ)儲(chǔ)結(jié)結(jié)構(gòu)構(gòu)的的抽抽象象。最最簡(jiǎn)簡(jiǎn)單單情情況況下下，文文件件定定義義為為數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)的的序序列列，文文件件系系統(tǒng)統(tǒng)提提供供按按指指定定位位置置讀讀寫寫文文件件數(shù)數(shù)據(jù)據(jù)項(xiàng)項(xiàng)或或子子序序列列的的操操作作。有有些些文文件件系系統(tǒng)統(tǒng)將將文文件件定定義義成成復(fù)復(fù)雜雜數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)的的集集合合(如如記錄等記錄等)，可以用記錄的鍵字來(lái)定位。，可以用

44、記錄的鍵字來(lái)定位。在在集集中中式式文文件件系系統(tǒng)統(tǒng)中中，文文件件系系統(tǒng)統(tǒng)可可以以管管理理大大量量的的文文件件，包包括括讀讀、寫寫或或刪刪除除等等。而而目目錄錄是是一一種種抽抽象象的的文文件件管管理理設(shè)設(shè)施施，它它能能將將文文件件名名映映射射到到一一個(gè)個(gè)文文件件指指針針，這這種種映映射射(即即目目錄錄)一一般般以以特特殊殊類類型型的的文文件件存存儲(chǔ)儲(chǔ)，若若要要訪訪問(wèn)問(wèn)文文件件，需需要要首首先先打打開(kāi)開(kāi)目錄。目錄。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)文文件件系系統(tǒng)統(tǒng)要要負(fù)負(fù)責(zé)責(zé)文文件件共共享享和和訪訪問(wèn)問(wèn)控控制制的的管管理理，限限定定用用戶的訪問(wèn)權(quán)限，

45、為每個(gè)文件定義訪問(wèn)類型等。戶的訪問(wèn)權(quán)限，為每個(gè)文件定義訪問(wèn)類型等。文件系統(tǒng)一般提供以下服務(wù)文件系統(tǒng)一般提供以下服務(wù):文件組織文件組織 文件存儲(chǔ)文件存儲(chǔ) 文件檢索文件檢索 文件命名文件命名 文件共享文件共享 文件保護(hù)。文件保護(hù)。設(shè)設(shè)計(jì)計(jì)文文件件系系統(tǒng)統(tǒng)的的目目的的，是是使使程程序序員員可可以以使使用用抽抽象象操操作作來(lái)訪問(wèn)磁盤空間，來(lái)訪問(wèn)磁盤空間，傳統(tǒng)文件系統(tǒng)的層次結(jié)構(gòu)如下圖所示：傳統(tǒng)文件系統(tǒng)的層次結(jié)構(gòu)如下圖所示：南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 文件系統(tǒng)模塊圖文件系統(tǒng)模塊圖以上也同樣是分布式文件系統(tǒng)的基礎(chǔ)以上也同樣是分布式文件系統(tǒng)的基礎(chǔ).目錄模

46、塊目錄模塊:負(fù)責(zé)文件名到文件標(biāo)識(shí)的映射負(fù)責(zé)文件名到文件標(biāo)識(shí)的映射文件模塊文件模塊:負(fù)責(zé)文件標(biāo)識(shí)到文件的映射負(fù)責(zé)文件標(biāo)識(shí)到文件的映射文件訪問(wèn)文件訪問(wèn):文件數(shù)據(jù)、屬性的讀寫文件數(shù)據(jù)、屬性的讀寫訪問(wèn)控制訪問(wèn)控制:操作的許可性檢查操作的許可性檢查盤塊模塊盤塊模塊:磁盤塊的分配及訪問(wèn)磁盤塊的分配及訪問(wèn)設(shè)備模塊設(shè)備模塊:磁盤磁盤I/O緩沖緩沖南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 另外加上另外加上:1.1.支持共享信息的管理支持共享信息的管理 不必先拷貝，再訪問(wèn)，永久性數(shù)據(jù)管理不必先拷貝，再訪問(wèn)，永久性數(shù)據(jù)管理 2.2.為用戶提供透明的文件訪問(wèn)服務(wù)為用戶提供透明

47、的文件訪問(wèn)服務(wù) 3.3.提供目錄服務(wù)提供目錄服務(wù) 提供文件命名及文件名到文件標(biāo)識(shí)的映射功能提供文件命名及文件名到文件標(biāo)識(shí)的映射功能 4.4.事務(wù)服務(wù)事務(wù)服務(wù) 為為用用戶戶提提供供的的最最高高層層服服務(wù)務(wù),提提供供并并發(fā)發(fā)服服務(wù)務(wù),保保證證文文件件的的一一致性致性南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 綜合而言綜合而言,分布式文件可分為三種服務(wù)分布式文件可分為三種服務(wù):目錄服務(wù)目錄服務(wù),文件服務(wù)文件服務(wù),事務(wù)服務(wù)事務(wù)服務(wù)用戶程序用戶程序用戶程序用戶程序用戶程序用戶程序客戶模塊客戶模塊網(wǎng)絡(luò)網(wǎng)絡(luò)文件服務(wù)文件服務(wù)目錄服務(wù)目錄服務(wù)事物服務(wù)事物服務(wù)文文件件服服務(wù)

48、務(wù)的的RPCRPC界面界面用用戶戶程程序序界界面面APIAPI目目錄錄服服務(wù)務(wù)的的RPCRPC界面界面事事物物服服務(wù)務(wù)的的RPCRPC界面界面南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.2 文件服務(wù)文件服務(wù) 在在UNlXUNlX和和DOSDOS系系統(tǒng)統(tǒng)中中，文文件件是是沒(méi)沒(méi)有有任任何何解解釋釋的的字字節(jié)節(jié)序序列列，文文件件的的結(jié)結(jié)構(gòu)構(gòu)和和意意義義完完全全由由應(yīng)應(yīng)用用程程序序決決定定，操操作作系系統(tǒng)統(tǒng)不不關(guān)關(guān)心心其其結(jié)結(jié)構(gòu)構(gòu)和和意意義義。但但在在某某些些大大型型機(jī)機(jī)的的操操作作系系統(tǒng)統(tǒng)中中，有有許許多多不不同同類類型的文件，每種文件具有不同的特性。型的文

49、件，每種文件具有不同的特性。文文件件可可以以是是一一組組記記錄錄構(gòu)構(gòu)成成的的序序列列，該該記記錄錄又又可可以以是是復(fù)復(fù)雜雜的的結(jié)結(jié)構(gòu)構(gòu)，這這個(gè)個(gè)結(jié)結(jié)構(gòu)構(gòu)的的意意義義是是由由操操作作系系統(tǒng)統(tǒng)解解釋釋的的。這這樣樣，文文件件便便由由數(shù)數(shù)據(jù)據(jù)和和屬屬性性構(gòu)構(gòu)成成，其其中中，屬屬性性包包括括文文件件長(zhǎng)長(zhǎng)度度、訪訪問(wèn)問(wèn)時(shí)時(shí)間間、訪訪問(wèn)問(wèn)控控制制表表和和擁?yè)碛杏姓哒撸奈募L(zhǎng)長(zhǎng)度度和和數(shù)數(shù)據(jù)據(jù)可可為為用用戶戶使使用用，其其它它屬性均為目錄服務(wù)使用，可以將這種文件看作一種文件對(duì)象。屬性均為目錄服務(wù)使用，可以將這種文件看作一種文件對(duì)象。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WE

50、B服務(wù)服務(wù) 關(guān)關(guān)于于文文件件的的另另一一個(gè)個(gè)重重要要問(wèn)問(wèn)題題是是文文件件的的可可修修改改性性。如如果果文文件件創(chuàng)創(chuàng)建建之之后后，不不能能再再修修改改，則則稱稱為為不不可可修修改改(Immutable)(Immutable)文文件件，否否則則稱稱為為可可修修改改(Mutable)(Mutable)文文件件。這這里里主主要要討討論論可可修修改改的文件。的文件。4.2.1 4.2.1 文件服務(wù)的模型和任務(wù)文件服務(wù)的模型和任務(wù) 對(duì)于一般的文件服務(wù)而言，有兩種服務(wù)模型對(duì)于一般的文件服務(wù)而言，有兩種服務(wù)模型 1)1)裝載卸載裝載卸載(Up Load(Up LoadDown Load)Down Load)模

51、型模型 2)2)遠(yuǎn)程訪問(wèn)遠(yuǎn)程訪問(wèn)(Remote Access)(Remote Access)模型模型南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)在在裝裝載載卸卸載載模模型型中中，文文件件服服務(wù)務(wù)僅僅提提供供讀讀文文件件和和寫寫文文件件兩種操作兩種操作。讀讀操操作作用用于于將將整整個(gè)個(gè)文文件件從從服服務(wù)務(wù)器器中中完完全全讀讀出出，寫寫操操作作用用于于將將整整個(gè)個(gè)文文件件從從客客戶戶機(jī)機(jī)寫寫入入服服務(wù)務(wù)器器。在在這這種種模模型型下下，可可以以將將文文件件緩緩沖沖于于客客戶戶機(jī)機(jī)的的主主存存或或磁磁盤盤中中，其其優(yōu)優(yōu)點(diǎn)點(diǎn)是是概概念念簡(jiǎn)簡(jiǎn)單單，應(yīng)應(yīng)用用程程序序可可

52、以以局局部部擁?yè)碛杏胁⒉⒃L訪問(wèn)問(wèn)文文件件，程程序序結(jié)結(jié)束束后后，必必須須將將新新建建或或修修改改過(guò)過(guò)的的文文件件寫寫回回服服務(wù)務(wù)器器。在在此此，不不需需要要復(fù)復(fù)雜雜的的文文件件服服務(wù)務(wù)界界面面，整整個(gè)個(gè)文文件件的的傳傳輸輸是是高高效效的的。但但是是，客客戶戶機(jī)機(jī)必必須須有有足足夠夠的的空空間間來(lái)來(lái)存存儲(chǔ)儲(chǔ)所所需需要要的的文文件件，另另外外，如如果果實(shí)實(shí)際際上上應(yīng)應(yīng)用用程程序序作作用于文件的一小部分，就會(huì)造成很大的浪費(fèi)。用于文件的一小部分，就會(huì)造成很大的浪費(fèi)。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)在在遠(yuǎn)遠(yuǎn)程程訪訪問(wèn)問(wèn)模模型型中中，文文件件服服務(wù)務(wù)將將提

53、提供供大大量量的的文文件件操操作作，包包括括打打開(kāi)開(kāi)、關(guān)關(guān)閉閉 讀讀和和寫寫等等，其其優(yōu)優(yōu)點(diǎn)點(diǎn)是是不不需需要要客客戶戶機(jī)機(jī)具具有有大大量量空空間間。另另外外，當(dāng)當(dāng)應(yīng)應(yīng)用用程程序序只只需需處處理理文文件件中中少少量量數(shù)數(shù)據(jù)據(jù)時(shí)時(shí)，不不需需要將整個(gè)文件全部拷貝到客戶機(jī)上去。要將整個(gè)文件全部拷貝到客戶機(jī)上去。文件服務(wù)的任務(wù)文件服務(wù)的任務(wù) 兩兩個(gè)個(gè)任任務(wù)務(wù)：文文件件存存儲(chǔ)儲(chǔ)和和文文件件尋尋址址。其其中中，文文件件尋尋址址利利用用文文件件位位置置映映射射方方法法完完成成文文件件的的定定位位，文文件件訪訪問(wèn)問(wèn)通通過(guò)過(guò)調(diào)調(diào)用用外外存存訪訪問(wèn)問(wèn)功功能能完完成成文文件件的的存存儲(chǔ)儲(chǔ)，外外存存訪訪問(wèn)問(wèn)功功能能通通

54、常常以以塊塊服服務(wù)務(wù)的的形形式式提提供供。所所以以，文文件件服服務(wù)務(wù)的的基基本本任任務(wù)務(wù)就就是是，提提供供通通用用和和有有效效的操作集合，為多個(gè)客戶提供大容量的外存設(shè)備。的操作集合，為多個(gè)客戶提供大容量的外存設(shè)備。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)另另外外，文文件件服服務(wù)務(wù)還還要要解解決決保保護(hù)護(hù)問(wèn)問(wèn)題題，即即嚴(yán)嚴(yán)格格控控制制用用戶戶對(duì)對(duì)于于文文件件的的訪訪問(wèn)問(wèn)，從從而而保保證證文文件件的的一一致致性性。文文件件服服務(wù)務(wù)可可以以同同時(shí)時(shí)支支持持多多個(gè)個(gè)目目錄錄服服務(wù)務(wù)，這這樣樣，目目錄錄服服務(wù)務(wù)可可以以采采用用多多種種不不同同語(yǔ)語(yǔ)法法，從從而而使

55、使文文件件服服務(wù)務(wù)可可以以用用于于不不同同的的目目錄錄服服務(wù)務(wù)。一一個(gè)個(gè)文文件件服服務(wù)務(wù)可可能能同同時(shí)時(shí)管管理理幾幾個(gè)個(gè)目目錄錄服服務(wù)務(wù)支支持持的的多多個(gè)個(gè)文文件件集集合合，每個(gè)集合中的文件屬性記錄和結(jié)構(gòu)可能還有差異。每個(gè)集合中的文件屬性記錄和結(jié)構(gòu)可能還有差異。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.2.2 4.2.2 文件服務(wù)界面文件服務(wù)界面 所所謂謂界界面面，主主要要提提供供服服務(wù)務(wù)的的基基本本操操作作名名和和調(diào)調(diào)用用格格式式及及簡(jiǎn)單功能描述。簡(jiǎn)單功能描述。文件的文件的UFIDUFID；參數(shù)；參數(shù);數(shù)據(jù)數(shù)據(jù);出錯(cuò)信息出錯(cuò)信息南京理工大學(xué)計(jì)算機(jī)學(xué)

56、院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.3 目錄服務(wù)目錄服務(wù) 目目錄錄服服務(wù)務(wù)定定義義了了構(gòu)構(gòu)成成文文件件(或或目目錄錄)名名的的某某種種字字母母表表示示語(yǔ)語(yǔ)法法。文文件件名名可可以以是是由由一一個(gè)個(gè)或或多多個(gè)個(gè)字字符符、數(shù)數(shù)字字及及特特殊殊字字符符構(gòu)構(gòu)成成的的字字符符串串。有有些些系系統(tǒng)統(tǒng)通通過(guò)過(guò)句句點(diǎn)點(diǎn)將將文文件件名名分分成成兩兩部部分分，如如progprogc c表表示示C C語(yǔ)語(yǔ)言言文文件，件，maimmaimtxttxt表示文本文牛，第二部分一般叫做文件擴(kuò)展名。表示文本文牛，第二部分一般叫做文件擴(kuò)展名。分分布布式式系系統(tǒng)統(tǒng)目目錄錄一一般般也也都都包包含含子子

57、目目錄錄，從從而而使使用用戶戶可可以以給給相相關(guān)關(guān)文文件件：分分組組，形形成成層層次次文文件件系系統(tǒng)統(tǒng)。因因此此，目目錄錄服服務(wù)務(wù)就就包包括括創(chuàng)創(chuàng)建建、刪刪除除、進(jìn)進(jìn)入入、退退出出和和查查找找文文件件等等功功能能。有有的的系系統(tǒng)統(tǒng)還還提提供供建建立立目目錄錄指指針針的的功功能能，指指針針可可以以設(shè)設(shè)置置到到任任何何目目錄錄中中，這這樣樣構(gòu)構(gòu)成成的的目目錄錄和和文文件件就就不不再再只只是是樹(shù)樹(shù)型型結(jié)結(jié)構(gòu)構(gòu)，而而是是圖圖(網(wǎng)網(wǎng)狀狀)結(jié)結(jié)構(gòu)構(gòu)，從從而而使使表表示示能能力力更更強(qiáng)，強(qiáng)，當(dāng)然，管理也就更復(fù)雜。當(dāng)然，管理也就更復(fù)雜。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB

58、服務(wù)服務(wù) 設(shè)設(shè)計(jì)計(jì)分分布布式式文文件件服服務(wù)務(wù)的的關(guān)關(guān)鍵鍵在在于于，是是否否支支持持所所有有機(jī)機(jī)器器對(duì)于目錄層次具有同樣的視圖。對(duì)于目錄層次具有同樣的視圖。4.3.1 4.3.1 目錄服務(wù)的任務(wù)目錄服務(wù)的任務(wù) 大大多多數(shù)數(shù)分分布布式式系系統(tǒng)統(tǒng)都都使使用用兩兩級(jí)級(jí)命命名名方方式式，即即每每個(gè)個(gè)文文件件(或或其其它它對(duì)對(duì)象象)都都有有一一個(gè)個(gè)符符號(hào)號(hào)名名(常常稱稱為為文文件件名名)和和一一個(gè)個(gè)內(nèi)內(nèi)部部二二進(jìn)進(jìn)制制名名(用用UFIDUFID表表示示)。符符號(hào)號(hào)名名一一般般供供程程序序員員或或用用戶戶使使用用，如如prog.cprog.c；內(nèi)內(nèi)部部二二進(jìn)進(jìn)制制名名供供系系統(tǒng)統(tǒng)使使用用。所所謂謂目目錄錄

59、，就就是是一一組組文文件件名名到到UFIDUFID的的映映射射表表。目目錄錄服服務(wù)務(wù)最最基基本本的的任任務(wù)務(wù)就就是是將將文文件件名名映映射射到到UFIDUFID，通通過(guò)過(guò)這這一一映映射射可可以以取取代代傳傳統(tǒng)統(tǒng)文文件件系系統(tǒng)統(tǒng)中中的的打打開(kāi)開(kāi)(Open)(Open)文文件件操操作作，客客戶戶一一旦旦拿拿到到UFIDUFID，便便可可以以操操作文件作文件.南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 目目錄錄服服務(wù)務(wù)本本身身要要確確保保UFIDUFID正正確確送送到到請(qǐng)請(qǐng)求求客客戶戶。目目錄錄服服務(wù)務(wù)還還要要檢檢查查客客戶戶的的合合法法性性，通通過(guò)過(guò)訪訪問(wèn)問(wèn)

60、控控制制表表做做合合法法性性檢檢查查，最最終終決決定是否發(fā)出一個(gè)定是否發(fā)出一個(gè)UFID.UFID.目目錄錄服服務(wù)務(wù)的的功功能能也也可可以以分分解解為為基基本本功功能能和和輔輔助助功功能能兩兩類類,基基本本功功能能提提供供文文件件名名到到文文件件標(biāo)標(biāo)識(shí)識(shí)的的映映射射，它它是是構(gòu)構(gòu)造造面面向向用用戶戶的的目目錄錄服服務(wù)務(wù)的的基基礎(chǔ)礎(chǔ)，包包括括名名字字、結(jié)結(jié)構(gòu)構(gòu)和和訪訪問(wèn)問(wèn)控控制制方方法法。根根據(jù)據(jù)授授權(quán)權(quán)客客戶戶的的請(qǐng)請(qǐng)求求允允許許用用戶戶執(zhí)執(zhí)行行UFIDUFID所所指指出出的的文文件件增增、刪刪操操作作。輔輔助助功功能能包包括括文文件件名名的的詞詞法法分分析析、建建立立目目錄錄形形成成層層次次結(jié)

61、結(jié)構(gòu)構(gòu)和和其其它它復(fù)復(fù)雜雜操操作作。因因此此，目目錄錄服服務(wù)務(wù)可可以以在在給給定定目目錄錄中中查查找找文文件件名名，然然后后得得到到UFIOUFIO，每每個(gè)個(gè)UFIDUFID都都指指出出對(duì)對(duì)于于文文件件的的相相關(guān)關(guān)訪訪問(wèn)問(wèn)權(quán)權(quán)限限，如如對(duì)對(duì)文文件擁有者可讀、寫和刪除，對(duì)于其它用戶只讀。件擁有者可讀、寫和刪除，對(duì)于其它用戶只讀。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)目目錄錄通通常常以以文文件件形形式式存存儲(chǔ)儲(chǔ)，因因此此，目目錄錄服服務(wù)務(wù)本本身身是是文文件件服務(wù)的一個(gè)客戶，每個(gè)目錄本身有一個(gè)服務(wù)的一個(gè)客戶，每個(gè)目錄本身有一個(gè)UFID。4.3.2目錄服務(wù)界

62、面目錄服務(wù)界面目目錄錄服服務(wù)務(wù)定定義義了了一一組組目目錄錄服服務(wù)務(wù)操操作作。不不同同系系統(tǒng)統(tǒng)有有響響應(yīng)應(yīng)的的約定約定.目錄服務(wù)的定義遵循約定記號(hào)。目錄服務(wù)的定義遵循約定記號(hào)。4.3.3文件屬性與目錄訪問(wèn)文件屬性與目錄訪問(wèn)目目錄錄服服務(wù)務(wù)要要進(jìn)進(jìn)行行訪訪問(wèn)問(wèn)控控制制，可可以以通通過(guò)過(guò)訪訪問(wèn)問(wèn)和和更更新新文文件件屬屬性性完完成成。如如可可以以在在新新文文件件名名加加入入目目錄錄時(shí)時(shí)，在在文文件件屬屬性性中中設(shè)設(shè)置置訪訪問(wèn)問(wèn)許許可可；提提供供查查看看文文件件屬屬性性的的操操作作；還還可可以以提提供供允允許許文文件件擁?yè)碛杏姓哒哒J(rèn)認(rèn)定定或或重重設(shè)設(shè)其其它它用用戶戶的的許許可可權(quán)權(quán)限限、及及將將所所有有

63、權(quán)權(quán)轉(zhuǎn)轉(zhuǎn)讓讓給給其它用戶的操作。其它用戶的操作。南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)文文件件系系統(tǒng)統(tǒng)除除管管理理數(shù)數(shù)據(jù)據(jù)外外，還還要要管管理理許許多多相相關(guān)關(guān)信信息息，如如創(chuàng)創(chuàng)建建日日期期、最最后后訪訪問(wèn)問(wèn)日日期期和和最最后后修修改改日日期期、文文件件類類型型、文文件件所所屬屬目目錄錄和和訪訪問(wèn)問(wèn)控控制制信信息息等等，我我們們稱稱這這些些信信息息為為文文件件屬屬性性。文文件件系系統(tǒng)統(tǒng)將將文文件件屬屬性性作作為為一一組組不不可可分分解解的的數(shù)數(shù)據(jù)據(jù)，文文件件屬屬性性可可以以執(zhí)行讀寫訪問(wèn)，執(zhí)行讀寫訪問(wèn)，但沒(méi)有長(zhǎng)度或結(jié)構(gòu)等操作但沒(méi)有長(zhǎng)度或結(jié)構(gòu)等操作目目錄

64、錄服服務(wù)務(wù)不不但但要要確確定定屬屬性性中中的的內(nèi)內(nèi)部部結(jié)結(jié)構(gòu)構(gòu)和和所所存存數(shù)數(shù)據(jù)據(jù)值值，還還要要負(fù)負(fù)責(zé)責(zé)文文件件屬屬性性的的訪訪問(wèn)問(wèn)，包包括括讀讀取取和和修修改改。如如改改變變?cè)L訪問(wèn)問(wèn)日日期、修改文件所屬關(guān)系和管理訪問(wèn)控制表等。期、修改文件所屬關(guān)系和管理訪問(wèn)控制表等。目目錄錄存存儲(chǔ)儲(chǔ)著著所所有有文文件件的的擁?yè)碛杏姓哒?，文文件件擁?yè)碛杏姓哒呖煽梢砸詫?duì)對(duì)其其文文件執(zhí)行所有操作，如創(chuàng)建、讀、寫和刪除等件執(zhí)行所有操作，如創(chuàng)建、讀、寫和刪除等南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)問(wèn)問(wèn)題題是是讓讓誰(shuí)誰(shuí)來(lái)來(lái)執(zhí)執(zhí)行行目目錄錄服服務(wù)務(wù)中中的的LookUp、AddNa

65、me、ReName和和UnName操操作作，查查看看或或修修改改文文件件屬屬性性?當(dāng)當(dāng)用用戶戶具具有有各各自自獨(dú)獨(dú)立立、分分離離的的目目錄錄時(shí)時(shí)，目目錄錄的的UFID可可能能認(rèn)認(rèn)定定為為一一種種權(quán)權(quán)能能，不不需需要要進(jìn)進(jìn)一一步步的的訪訪問(wèn)問(wèn)控控制制；但但是是要要訪訪問(wèn)問(wèn)共共享享目目錄錄時(shí)時(shí)，則則需需要要訪訪問(wèn)問(wèn)控控制制。一一個(gè)個(gè)簡(jiǎn)簡(jiǎn)單單的的解解決決辦辦法法是是，讓讓目目錄錄擁?yè)碛杏姓哒叩牡脑L訪問(wèn)許可模式與文件擁有者的訪問(wèn)許可模式取得一致。問(wèn)許可模式與文件擁有者的訪問(wèn)許可模式取得一致。另另外外，為為用用戶戶同同時(shí)時(shí)提提供供文文件件服服務(wù)務(wù)和和目目錄錄服服務(wù)務(wù)操操作作可可以以克克服服文文件件的的丟

66、丟失失問(wèn)問(wèn)題題。對(duì)對(duì)于于文文件件創(chuàng)創(chuàng)建建，用用戶戶通通過(guò)過(guò)創(chuàng)創(chuàng)建建操操作作指指定定的的文文件件名名和和目目錄錄名名，然然后后依依靠靠文文件件服服務(wù)務(wù)Create操操作作和和目目錄錄服服務(wù)務(wù)AddName操操作作完完成成。對(duì)對(duì)于于文文件件刪刪除除，通通過(guò)過(guò)刪刪除除操操作作指指定一個(gè)定一個(gè)UFID和目錄名和目錄名南京理工大學(xué)計(jì)算機(jī)學(xué)院南京理工大學(xué)計(jì)算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.3.4樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)在在UNIX提提供供的的樹(shù)樹(shù)型型文文件件系系統(tǒng)統(tǒng)中中，包包含含組組織織成成樹(shù)樹(shù)型型結(jié)結(jié)構(gòu)構(gòu)的的許許多多目目錄錄，通通過(guò)過(guò)鏈鏈?zhǔn)故刮奈募呔哂杏卸喽鄠€(gè)個(gè)名名字字，可可以以使使用用基基本本的的文文件件和和目目錄錄服服務(wù)務(wù)來(lái)來(lái)實(shí)實(shí)現(xiàn)現(xiàn)。樹(shù)樹(shù)型型結(jié)結(jié)構(gòu)構(gòu)的的目目錄錄集集合合可可以以通通過(guò)過(guò)葉葉、根根和和內(nèi)內(nèi)部部結(jié)結(jié)點(diǎn)點(diǎn)構(gòu)構(gòu)成成。樹(shù)樹(shù)根根是是一一個(gè)個(gè)目目錄錄，其其UFID是是共共用的。用的。樹(shù)樹(shù)中中任任何何結(jié)結(jié)點(diǎn)點(diǎn)或或葉葉結(jié)結(jié)點(diǎn)點(diǎn)就就是是文文件件或或目目錄錄，可可以以通通過(guò)過(guò)路路徑徑名名命命名名文文件件或或目目錄錄，路路徑徑是是由由多多部部分分組組成成的的表表示示路路徑徑的的名名字字