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

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

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

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

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

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

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

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

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

9、院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 分布式算法分布式算法 算法的條件算法的條件:系統(tǒng)中的事件必須有全局的順序系統(tǒng)中的事件必須有全局的順序 算法的工作過程如下算法的工作過程如下:當(dāng)當(dāng)一一個個進(jìn)進(jìn)程程要要進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)時時，它它構(gòu)構(gòu)造造一一條條包包括括臨臨界界區(qū)區(qū)名名、進(jìn)進(jìn)程程號號和和當(dāng)當(dāng)前前時時間間的的請請求求消消息息，然然后后把把該該消消息息廣廣播播給給其其他他的的所所有有進(jìn)進(jìn)程程。這這里里假假設(shè)設(shè)，消息的發(fā)送是可靠的。消息的發(fā)送是可靠的。當(dāng)一個進(jìn)程收到請求后，根據(jù)它的狀態(tài)采取相應(yīng)的動作：當(dāng)一個進(jìn)程收到請求后，根據(jù)它的狀態(tài)采取相應(yī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ū)中，它不回答僅僅把請求加入隊列。如果接收者已經(jīng)在臨界區(qū)中，它不回答僅僅把請求加入隊列。(3)(3)如如果果接接收收者者不不在在臨臨界界區(qū)區(qū)，但但它它也也想想進(jìn)進(jìn)入入臨臨界界區(qū)區(qū)，就就要要將將收收到到消消息息的的時時間間戳戳和和它它廣廣播播消消息息的的時時間間戳戳比比較較.如如果果到到來來的的消消息息時時間間戳戳早早，接接收收者者回回答答發(fā)送者發(fā)送者OKOK消息；反之接收者把到來的請求加入隊列，不回答消息；反之接收者把到來的請求加入隊列，不回答.南京理工大學(xué)計算機(jī)學(xué)院

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

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

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

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

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

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

17、的進(jìn)程發(fā)送ELECTIONELECTION消息；消息；(2)(2)如果沒有進(jìn)程響應(yīng)，進(jìn)程如果沒有進(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é)束選舉。注注意意：一一個個進(jìn)進(jìn)程程只只能能從從號號碼碼比比它它小小的的進(jìn)進(jìn)程程處處得得到到一一個個選選擇擇消息消息南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(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啟動選舉啟動選舉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,都都啟啟動動選選舉舉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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)2.環(huán)形算法環(huán)形算法 這這個個算算法法使使用用環(huán)環(huán)，但但不不是是令令牌牌環(huán)環(huán)。這這里里假假定定所所有有的的進(jìn)進(jìn)程程都都是是有有序序號號

19、的的，即即每每個個進(jìn)進(jìn)程程都都知知道道它它的的后后繼繼進(jìn)進(jìn)程程。當(dāng)當(dāng)一一個個進(jìn)進(jìn)程程發(fā)發(fā)現(xiàn)現(xiàn)管管理理員員不不能能工工作作時時，它它把把包包含含其其進(jìn)進(jìn)程程號號的的ELECTIONELECTION消消息息發(fā)發(fā)給給它它的的后后繼繼進(jìn)進(jìn)程程；接接收收消消息息的的進(jìn)進(jìn)程程再再向向后后繼繼進(jìn)進(jìn)程程發(fā)發(fā)送送ELECTIONELECTION消消息息。如如果果接接收收進(jìn)進(jìn)程程沒沒有有反反應(yīng)應(yīng)，發(fā)發(fā)送送消消息息的的進(jìn)進(jìn)程程便便向向下下一一個個進(jìn)進(jìn)程程發(fā)發(fā)消消息息。每每一一次次發(fā)發(fā)送送ELECTIONELECTION，進(jìn)進(jìn)程程都都要要將將自自己己的的進(jìn)進(jìn)程程號號加加入入消息。消息。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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 最最后后，第第一一個個發(fā)發(fā)出出該該選選舉舉（ELECTIONELECTION）消消息息進(jìn)進(jìn)程程收收到到該該消消息息,再再將將其其轉(zhuǎn)轉(zhuǎn)換換為為協(xié)協(xié)調(diào)調(diào)（COORDINATORCOORDINATOR）消消息息后后，再再循循環(huán)環(huán)一一周周,通通知知誰誰是是管管理理員員，誰誰是是組組成成員員，這這時時消消息息包包中中進(jìn)進(jìn)程程號號最最高高的的進(jìn)進(jìn)程程將將成成

21、為為管管理理員員。當(dāng)當(dāng)這這個個消消息息循循環(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)運行，結(jié)果是一樣的，只是浪費了帶寬。沿環(huán)運行，結(jié)果是一樣的，只是浪費了帶寬。南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(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ū)別別是是它它的地址空間是共享的。的地址空間是共享的。線程相對于進(jìn)程，猶如進(jìn)程相對于機(jī)器線程相對于進(jìn)程，猶如進(jìn)程相對于機(jī)器 2.2.線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng)線程的使用，將并行性引入到順序執(zhí)行的系統(tǒng).多線程組織的常用模型：多線程組織的常用模型：南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 1)1)分配器工作者模型分配器工作者模型 有一個分配器線程喚醒工作者線程可用信號燈有一個分配器線程喚醒工作者線程可用信號燈 2

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

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

25、線程的個數(shù)，動態(tài)，動態(tài)個數(shù)個數(shù)不定不定 線程的代碼與進(jìn)程一樣，由多個過程組成。線程的代碼與進(jìn)程一樣，由多個過程組成。線程包中臨界區(qū)控制利用互斥體（線程包中臨界區(qū)控制利用互斥體（mutex),mutex),其總處于：其總處于：打開和鎖住兩種狀態(tà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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù) 線程可由算法進(jìn)行調(diào)度，如優(yōu)先級調(diào)度、循環(huán)調(diào)度等線程可由算法進(jìn)行調(diào)度

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

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

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

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

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

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

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

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

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

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

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

38、系統(tǒng)與WEB服務(wù)服務(wù)2 2設(shè)計分配算法的主要相關(guān)問題設(shè)計分配算法的主要相關(guān)問題1）確定式還是啟發(fā)式）確定式還是啟發(fā)式 確確定定式式適適用用進(jìn)進(jìn)程程是是否否可可預(yù)預(yù)知知;啟啟發(fā)發(fā)是是指指以以經(jīng)經(jīng)驗驗性性規(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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服

39、務(wù) 3 3處理機(jī)分配算法實現(xiàn)中的問題處理機(jī)分配算法實現(xiàn)中的問題 1 1）對負(fù)載的測量）對負(fù)載的測量 2 2）額外開銷的處理）額外開銷的處理 3 3）問題的復(fù)雜度）問題的復(fù)雜度 4 4）穩(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ī)學(xué)院南京理工大學(xué)計算機(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)度概念的算法概念的算法.算法使用一個矩陣算法使用一個矩陣 列是處理機(jī)的進(jìn)程表列是處理機(jī)的進(jìn)程表 行是時間段的進(jìn)程表行是時間段的進(jìn)程表主主要要思思想想:每每個個處處理理機(jī)機(jī)采采用用時時

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

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

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

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

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

47、的文件訪問服務(wù) 3.3.提供目錄服務(wù)提供目錄服務(wù) 提供文件命名及文件名到文件標(biāo)識的映射功能提供文件命名及文件名到文件標(biāo)識的映射功能 4.4.事務(wù)服務(wù)事務(wù)服務(wù) 為為用用戶戶提提供供的的最最高高層層服服務(wù)務(wù),提提供供并并發(fā)發(fā)服服務(wù)務(wù),保保證證文文件件的的一一致性致性南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.2 文件服務(wù)文件服務(wù) 在在UNlXUNlX和和DOSDOS系系統(tǒng)統(tǒng)中中，文文件件是是沒沒有有任任何何解解釋釋的的字字節(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)，這這個個結(jié)結(jié)構(gòu)構(gòu)的的意意義義是是由由操操作作系系統(tǒng)統(tǒng)解解釋釋的的。這這樣樣，文文件件便便由由數(shù)數(shù)據(jù)據(jù)和和屬屬性性構(gòu)構(gòu)成成，其其中中，屬屬性性包包括括文文件件長長度度、訪訪問問時時間間、訪訪問問控控制制表表和和擁擁有有者者，文文件件長長度度和和數(shù)數(shù)據(jù)據(jù)可可為為用用戶戶使使用用，其其它它屬性均為目錄服務(wù)使用，可以將這種文件看作一種文件對象。屬性均為目錄服務(wù)使用，可以將這種文件看作一種文件對象。南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WE

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

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

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

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

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

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

56、院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB服務(wù)服務(wù)4.3 目錄服務(wù)目錄服務(wù) 目目錄錄服服務(wù)務(wù)定定義義了了構(gòu)構(gòu)成成文文件件(或或目目錄錄)名名的的某某種種字字母母表表示示語語法法。文文件件名名可可以以是是由由一一個個或或多多個個字字符符、數(shù)數(shù)字字及及特特殊殊字字符符構(gòu)構(gòu)成成的的字字符符串串。有有些些系系統(tǒng)統(tǒng)通通過過句句點點將將文文件件名名分分成成兩兩部部分分，如如progprogc c表表示示C C語語言言文文件，件，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)成成的的目目錄錄和和文文件件就就不不再再只只是是樹樹型型結(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ī)學(xué)院南京理工大學(xué)計算機(jī)學(xué)院分布式系統(tǒng)與分布式系統(tǒng)與WEB

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

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

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

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

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

63、權(quán)權(quán)轉(zhuǎn)轉(zhuǎn)讓讓給給其它用戶的操作。其它用戶的操作。南京理工大學(xué)計算機(jī)學(xué)院南京理工大學(xué)計算機(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)建建日日期期、最最后后訪訪問問日日期期和和最最后后修修改改日日期期、文文件件類類型型、文文件件所所屬屬目目錄錄和和訪訪問問控控制制信信息息等等，我我們們稱稱這這些些信信息息為為文文件件屬屬性性。文文件件系系統(tǒng)統(tǒng)將將文文件件屬屬性性作作為為一一組組不不可可分分解解的的數(shù)數(shù)據(jù)據(jù)，文文件件屬屬性性可可以以執(zhí)行讀寫訪問，執(zhí)行讀寫訪問，但沒有長度或結(jié)構(gòu)等操作但沒有長度或結(jié)構(gòu)等操作目目錄

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

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

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