高級(jí)操作系統(tǒng)課件-第五章命名培訓(xùn)資料

1、高級(jí)操作系統(tǒng)課件-第五章命名 問題：給定實(shí)體的一個(gè)無結(jié)構(gòu)的名稱問題：給定實(shí)體的一個(gè)無結(jié)構(gòu)的名稱（如標(biāo)識(shí)符），如何定位該實(shí)體？（如標(biāo)識(shí)符），如何定位該實(shí)體？ 解決方案：解決方案： 簡單方法簡單方法 基于起始位置的方法基于起始位置的方法 分層方法分層方法 廣播和多播廣播和多播 轉(zhuǎn)發(fā)指針轉(zhuǎn)發(fā)指針 廣播廣播 適用于局域網(wǎng)適用于局域網(wǎng) 在廣域網(wǎng)內(nèi)變得低效在廣域網(wǎng)內(nèi)變得低效 多播多播 只發(fā)送給一組符合條件的主機(jī)只發(fā)送給一組符合條件的主機(jī) 可進(jìn)行多播實(shí)體的定位服務(wù)可進(jìn)行多播實(shí)體的定位服務(wù) 可用于定位最近副本可用于定位最近副本使用使用 (proxy, skeleton) 對(duì)的轉(zhuǎn)發(fā)指針對(duì)的轉(zhuǎn)發(fā)指針通過在代理中存

2、儲(chǔ)一個(gè)捷徑來重定向轉(zhuǎn)發(fā)指針通過在代理中存儲(chǔ)一個(gè)捷徑來重定向轉(zhuǎn)發(fā)指針移動(dòng)移動(dòng) IP原理原理起始移動(dòng)代理起始移動(dòng)代理當(dāng)移動(dòng)主機(jī)轉(zhuǎn)移到另一個(gè)網(wǎng)絡(luò)時(shí)，將轉(zhuǎn)交地址在起始移動(dòng)代理中注冊當(dāng)移動(dòng)主機(jī)轉(zhuǎn)移到另一個(gè)網(wǎng)絡(luò)時(shí)，將轉(zhuǎn)交地址在起始移動(dòng)代理中注冊缺點(diǎn)：缺點(diǎn)：客戶必須首先與起始位置聯(lián)系，而這一位置可能與實(shí)體相鄰很遠(yuǎn)客戶必須首先與起始位置聯(lián)系，而這一位置可能與實(shí)體相鄰很遠(yuǎn)使用了固定的起始位置使用了固定的起始位置 類似類似DNS，網(wǎng)絡(luò)被劃分為一組域，網(wǎng)絡(luò)被劃分為一組域 目錄節(jié)點(diǎn)：記錄域包含的實(shí)體目錄節(jié)點(diǎn)：記錄域包含的實(shí)體 葉域的目錄節(jié)點(diǎn)葉域的目錄節(jié)點(diǎn)N記錄實(shí)體記錄實(shí)體E在域中的位置在域中的位置 更高一層域的目錄節(jié)

3、點(diǎn)更高一層域的目錄節(jié)點(diǎn)N記錄實(shí)體記錄實(shí)體E的位置，的位置，包含指向包含指向N的指針的指針把定位服務(wù)劃分為域的分層組織，每個(gè)域都有關(guān)聯(lián)的目錄節(jié)點(diǎn)把定位服務(wù)劃分為域的分層組織，每個(gè)域都有關(guān)聯(lián)的目錄節(jié)點(diǎn)實(shí)體信息存儲(chǔ)示例，這里的實(shí)體在不同的葉域中擁有兩個(gè)地址實(shí)體信息存儲(chǔ)示例，這里的實(shí)體在不同的葉域中擁有兩個(gè)地址在分層組織的定位服務(wù)中的在分層組織的定位服務(wù)中的位置查找位置查找更新操作更新操作插入請(qǐng)求被轉(zhuǎn)發(fā)到第一個(gè)知道實(shí)體插入請(qǐng)求被轉(zhuǎn)發(fā)到第一個(gè)知道實(shí)體E的節(jié)點(diǎn)的節(jié)點(diǎn)轉(zhuǎn)發(fā)指向葉節(jié)點(diǎn)的指針?biāo)纬傻逆溵D(zhuǎn)發(fā)指向葉節(jié)點(diǎn)的指針?biāo)纬傻逆溨羔樉彺嬷羔樉彺?緩存指向最底層域所用目錄節(jié)點(diǎn)的引用緩存指向最底層域所用目錄節(jié)點(diǎn)的

4、引用指針緩存指針緩存 (2) 緩存項(xiàng)需要失效，因?yàn)樗祷亓艘粋€(gè)非本地地址，緩存項(xiàng)需要失效，因?yàn)樗祷亓艘粋€(gè)非本地地址，盡管該地址仍然有效盡管該地址仍然有效可擴(kuò)展性問題可擴(kuò)展性問題(1) 分層定位服務(wù)存在的一個(gè)主要問題是根節(jié)分層定位服務(wù)存在的一個(gè)主要問題是根節(jié)點(diǎn)存儲(chǔ)所有實(shí)體的位置并為每個(gè)實(shí)體處理點(diǎn)存儲(chǔ)所有實(shí)體的位置并為每個(gè)實(shí)體處理請(qǐng)求，容易成為瓶頸請(qǐng)求，容易成為瓶頸 解決辦法：將根節(jié)點(diǎn)和其他高層目錄節(jié)點(diǎn)解決辦法：將根節(jié)點(diǎn)和其他高層目錄節(jié)點(diǎn)劃分為多個(gè)子節(jié)點(diǎn)劃分為多個(gè)子節(jié)點(diǎn) 問題：子節(jié)點(diǎn)的物理放置問題：子節(jié)點(diǎn)的物理放置 集中放置集中放置 均勻放置均勻放置 實(shí)體的創(chuàng)建地相鄰的節(jié)點(diǎn)實(shí)體的創(chuàng)建地相鄰的節(jié)點(diǎn)

5、可擴(kuò)展性問題可擴(kuò)展性問題(2) 在定位服務(wù)覆蓋的網(wǎng)絡(luò)中均勻放置根節(jié)點(diǎn)的子節(jié)點(diǎn)所存在在定位服務(wù)覆蓋的網(wǎng)絡(luò)中均勻放置根節(jié)點(diǎn)的子節(jié)點(diǎn)所存在的可擴(kuò)展性問題的可擴(kuò)展性問題 無引用對(duì)象的問題無引用對(duì)象的問題 引用計(jì)數(shù)引用計(jì)數(shù) 簡單引用計(jì)數(shù)簡單引用計(jì)數(shù) 高級(jí)引用計(jì)數(shù)高級(jí)引用計(jì)數(shù) 引用列表引用列表 對(duì)象圖例，對(duì)象相互包含對(duì)方的引用對(duì)象圖例，對(duì)象相互包含對(duì)方的引用 在通信不可靠的情況下維護(hù)正確的引用計(jì)數(shù)所存在的問題在通信不可靠的情況下維護(hù)正確的引用計(jì)數(shù)所存在的問題加權(quán)引用計(jì)數(shù)中權(quán)數(shù)的初始值加權(quán)引用計(jì)數(shù)中權(quán)數(shù)的初始值創(chuàng)建新引用時(shí)的權(quán)數(shù)值創(chuàng)建新引用時(shí)的權(quán)數(shù)值復(fù)制引用時(shí)的權(quán)數(shù)值復(fù)制引用時(shí)的權(quán)數(shù)值 在引用的部分權(quán)數(shù)達(dá)到

6、在引用的部分權(quán)數(shù)達(dá)到1時(shí)創(chuàng)建一個(gè)時(shí)創(chuàng)建一個(gè)間接權(quán)數(shù)間接權(quán)數(shù) 骨架跟蹤引用它的代理骨架跟蹤引用它的代理 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 不需要可靠通信：冪等操作不需要可靠通信：冪等操作 進(jìn)程發(fā)生故障時(shí)，容易保持引用表的一致性進(jìn)程發(fā)生故障時(shí)，容易保持引用表的一致性 缺點(diǎn)缺點(diǎn) 引用表的規(guī)模問題：注冊的引用在有效時(shí)間內(nèi)引用表的規(guī)模問題：注冊的引用在有效時(shí)間內(nèi)有效（分發(fā)租用）有效（分發(fā)租用） 名稱空間名稱空間 名稱解析名稱解析 名稱空間的實(shí)現(xiàn)名稱空間的實(shí)現(xiàn) 名稱名稱組織在組織在名稱空間名稱空間（Name Space）中）中 節(jié)點(diǎn)的有向圖：節(jié)點(diǎn)的有向圖： 根節(jié)點(diǎn)根節(jié)點(diǎn) 目錄節(jié)點(diǎn)：存儲(chǔ)目錄表（目錄節(jié)點(diǎn)：存儲(chǔ)目錄表（對(duì)）對(duì)）

7、葉子節(jié)點(diǎn)：存儲(chǔ)所表示實(shí)體的信息葉子節(jié)點(diǎn)：存儲(chǔ)所表示實(shí)體的信息 路徑：邊標(biāo)簽序列，如路徑：邊標(biāo)簽序列，如“/home/steen/mbox”UNIX 文件系統(tǒng)的通用組織結(jié)構(gòu)文件系統(tǒng)的通用組織結(jié)構(gòu)根塊：系統(tǒng)啟動(dòng)時(shí)自動(dòng)加載到內(nèi)存，用于加載操作系統(tǒng)根塊：系統(tǒng)啟動(dòng)時(shí)自動(dòng)加載到內(nèi)存，用于加載操作系統(tǒng)超級(jí)塊：整個(gè)文件系統(tǒng)的信息：大小、空閑塊信息超級(jí)塊：整個(gè)文件系統(tǒng)的信息：大小、空閑塊信息索引節(jié)點(diǎn)：與節(jié)點(diǎn)關(guān)聯(lián)的文件數(shù)據(jù)信息索引節(jié)點(diǎn)：與節(jié)點(diǎn)關(guān)聯(lián)的文件數(shù)據(jù)信息目錄：作為文件實(shí)現(xiàn)，包含文件名和索引節(jié)點(diǎn)的映射目錄：作為文件實(shí)現(xiàn)，包含文件名和索引節(jié)點(diǎn)的映射名稱解析名稱解析 定義定義:給定一個(gè)路徑名，應(yīng)該能夠查找出存給定

8、一個(gè)路徑名，應(yīng)該能夠查找出存儲(chǔ)在由該名稱指向節(jié)點(diǎn)中的任何信息儲(chǔ)在由該名稱指向節(jié)點(diǎn)中的任何信息 別名：同一實(shí)體的另一名稱別名：同一實(shí)體的另一名稱 硬鏈接硬鏈接：多個(gè)絕對(duì)路徑名指向同一結(jié)點(diǎn)：多個(gè)絕對(duì)路徑名指向同一結(jié)點(diǎn) 符號(hào)鏈接符號(hào)鏈接：節(jié)點(diǎn)存儲(chǔ)絕對(duì)路徑名：節(jié)點(diǎn)存儲(chǔ)絕對(duì)路徑名鏈接和掛載鏈接和掛載 (1)命名圖中的符號(hào)鏈接的概念命名圖中的符號(hào)鏈接的概念鏈接和掛載鏈接和掛載通過指定的訪問協(xié)議裝配遠(yuǎn)程名稱空間通過指定的訪問協(xié)議裝配遠(yuǎn)程名稱空間掛載掛載：以透明的方式合并不同的名稱空間；：以透明的方式合并不同的名稱空間；掛接點(diǎn)掛接點(diǎn)（mount point）和）和掛載點(diǎn)掛載點(diǎn)（mounting point）需

9、要的信息：訪問協(xié)議的名稱、服務(wù)器的名稱和外部名稱空間的掛載點(diǎn)的名稱，可以表需要的信息：訪問協(xié)議的名稱、服務(wù)器的名稱和外部名稱空間的掛載點(diǎn)的名稱，可以表示成一個(gè)示成一個(gè)URL。對(duì)對(duì)/remote/vu/mbox的名稱解析的名稱解析DNS name space 劃分示例劃分示例命名服務(wù)命名服務(wù)是一種允許用戶和進(jìn)程添加、刪除和查找名稱的服務(wù)，由是一種允許用戶和進(jìn)程添加、刪除和查找名稱的服務(wù)，由名稱服務(wù)器名稱服務(wù)器實(shí)現(xiàn)實(shí)現(xiàn)為全局層、行政層、管理層實(shí)現(xiàn)節(jié)點(diǎn)的名稱服務(wù)器之間的比較為全局層、行政層、管理層實(shí)現(xiàn)節(jié)點(diǎn)的名稱服務(wù)器之間的比較內(nèi)容內(nèi)容全局層全局層行政層行政層管理層管理層網(wǎng)絡(luò)的地理范圍網(wǎng)絡(luò)的地理范圍世

10、界范圍世界范圍組織組織部門部門節(jié)點(diǎn)數(shù)目節(jié)點(diǎn)數(shù)目少少許多許多極多極多查詢響應(yīng)查詢響應(yīng)秒秒毫秒毫秒立即立即更新的傳播情況更新的傳播情況延遲延遲立即立即立即立即復(fù)制數(shù)目復(fù)制數(shù)目許多許多沒有或很少?zèng)]有或很少?zèng)]有沒有是否采用客戶端緩存是否采用客戶端緩存是是是是有時(shí)有時(shí)迭代名稱解析原理迭代名稱解析原理 （iterative name resolution）解析解析root:,對(duì)應(yīng)于對(duì)應(yīng)于ftp.cs.vu.nl/pub/globe/index.txt#用來指明一臺(tái)服務(wù)器的地址，該服務(wù)器負(fù)責(zé)處理用來指明一臺(tái)服務(wù)器的地址，該服務(wù)器負(fù)責(zé)處理涉及到的節(jié)點(diǎn)涉及到的節(jié)點(diǎn)最后，客戶端會(huì)與該最后，客戶端會(huì)與該FTP服務(wù)器

11、聯(lián)系，后者發(fā)送會(huì)被請(qǐng)求的文件服務(wù)器聯(lián)系，后者發(fā)送會(huì)被請(qǐng)求的文件遞歸名稱解析原理遞歸名稱解析原理 recursive name resolution.解析解析root:,對(duì)應(yīng)于對(duì)應(yīng)于ftp.cs.vu.nl/pub/globe/index.txt缺點(diǎn)：要求名稱服務(wù)器有較高性能缺點(diǎn)：要求名稱服務(wù)器有較高性能優(yōu)點(diǎn)：緩存效果更有效；減少通信開銷優(yōu)點(diǎn)：緩存效果更有效；減少通信開銷對(duì)對(duì) 進(jìn)行遞歸名稱解析，名稱服務(wù)器進(jìn)行遞歸名稱解析，名稱服務(wù)器緩存用于后續(xù)查詢的中間結(jié)果緩存用于后續(xù)查詢的中間結(jié)果服務(wù)器所服務(wù)器所在節(jié)點(diǎn)在節(jié)點(diǎn)需要解析的標(biāo)識(shí)符需要解析的標(biāo)識(shí)符 查詢查詢傳遞給下一傳遞給下一個(gè)服務(wù)器個(gè)服務(wù)器遞歸和緩

12、存遞歸和緩存返回請(qǐng)求者返回請(qǐng)求者cs#-#vu#nl#root#迭代名稱解析與遞歸名稱解析通信代價(jià)比較迭代名稱解析與遞歸名稱解析通信代價(jià)比較 名稱、標(biāo)識(shí)符和地址名稱、標(biāo)識(shí)符和地址 無層次命名無層次命名 簡單方法簡單方法 基于起始位置的方法基于起始位置的方法 分層方法分層方法 刪除無引用的實(shí)體刪除無引用的實(shí)體 無引用對(duì)象的問題無引用對(duì)象的問題 引用計(jì)數(shù)引用計(jì)數(shù) 簡單引用計(jì)數(shù)簡單引用計(jì)數(shù) 高級(jí)引用計(jì)數(shù)高級(jí)引用計(jì)數(shù) 引用列表引用列表 結(jié)構(gòu)化命名結(jié)構(gòu)化命名 名稱空間名稱空間 名稱解析名稱解析 名稱空間的實(shí)現(xiàn)名稱空間的實(shí)現(xiàn) 假設(shè)某個(gè)移動(dòng)實(shí)體幾乎從不會(huì)離開域假設(shè)某個(gè)移動(dòng)實(shí)體幾乎從不會(huì)離開域D，即使離開也，即使離開也很快返回。如何利用該信息在分層定位服務(wù)中加快查很快返回。如何利用該信息在分層定位服務(wù)中加快查詢操作的速度？詢操作的速度？ 假設(shè)一個(gè)實(shí)體從位置假設(shè)一個(gè)實(shí)體從位置A轉(zhuǎn)移到位置轉(zhuǎn)移到位置B，期間經(jīng)過了幾，期間經(jīng)過了幾個(gè)中間位置（停留時(shí)間都很短），最終到達(dá)個(gè)中間位置（停留時(shí)間都很短），最終到達(dá)B 。在分。在分層定位服務(wù)中更改地址可能花費(fèi)較長時(shí)間，因此在經(jīng)層定位服務(wù)中更改地址可能花費(fèi)較長時(shí)間，因此在經(jīng)過中間位置時(shí)，應(yīng)避免更改地址，那么經(jīng)過中間位置過中間位置時(shí)，應(yīng)避免更改地址，那么