【正文】 共建立 8個(gè) hash鏈，每個(gè) hash鏈?zhǔn)且粋€(gè)以鏈表頭開(kāi)始的雙向循環(huán)鏈表， 每個(gè) ncache任何時(shí)候都同時(shí)既在 hash鏈上，又在 LRU鏈上 。 ncache的 hash值用下列公式計(jì)算： hn=7amp。 文件名和文件名緩沖區(qū) 核心在內(nèi)存中建立了一個(gè)高速的名字緩沖區(qū)，用來(lái)存放最近使用過(guò)的文件名，核心認(rèn)為“最近使用過(guò)的文件名馬上還要使用的可能性最大” 。 在增加新目錄時(shí)，先查看目錄中各目錄項(xiàng)是否占用多余空間，如有，則進(jìn)行壓縮，把釋放的空間分配給新目錄項(xiàng)。 /* 目錄項(xiàng)入口長(zhǎng)度（占用長(zhǎng)度） */ short d_namelen； /* 目錄項(xiàng)名字長(zhǎng)度 */ char d_name [MAXNAMLEN+1] /* 名字字符串， +1為串結(jié)束符 \0 */ } 由于目錄中各目錄項(xiàng)的長(zhǎng)度是變化的，因此必須在目錄項(xiàng)中標(biāo)明本目錄項(xiàng)的長(zhǎng)度。 變長(zhǎng)目錄項(xiàng)的目錄結(jié)構(gòu) define MAXNAMLEN 255 struct direct { long d_ino。 在 UNIX的每個(gè)文件系統(tǒng)中，有三個(gè) i 節(jié)點(diǎn)號(hào)是有固定用途的： 0號(hào) i節(jié)點(diǎn) ： 表示空目錄項(xiàng)，當(dāng)某個(gè)目錄項(xiàng)被刪除時(shí)，該目錄項(xiàng)的 i 節(jié)點(diǎn)號(hào)被置為 0。 /*目錄項(xiàng)名字字符串 */ } 每個(gè)目錄項(xiàng)的長(zhǎng)度通常是確定的，為 16個(gè)字節(jié)，其中前兩個(gè)字節(jié)存放文件的 i節(jié)點(diǎn)號(hào) d_ino，后面 14個(gè)字節(jié)存放文件名d_name。 / /home /bin /home/log /home/student /home/student/xiaolan /home/student/xiaolan/src /每個(gè)目錄項(xiàng)由數(shù)據(jù)結(jié)構(gòu) direct來(lái)定義： define MAXNAMLEN 14 struct direct { short d_ino。 409 bckup 230 src 409 。 584 xiaolan 584 。 290 log 376 student 376 。 153 。 153 home 0 tst 85 bin 85 。 每一個(gè)目錄項(xiàng)中通常包含兩部分內(nèi)容： 文件的 i 節(jié)點(diǎn)號(hào) 文件名 目錄 /home/student/xiaolan 的路徑和目錄結(jié)構(gòu) 2 。 6．目錄和目錄項(xiàng) 在 UNIX文件系統(tǒng)中，目錄的組織形式采用的是樹(shù)形結(jié)構(gòu)，一個(gè)邏輯文件系統(tǒng)就是一棵目錄樹(shù)。 系統(tǒng)只需要維護(hù)一張較小的表（位示圖）就可以快速地檢測(cè)指定資源的忙閑狀態(tài)，或快速查找可用的空閑資源。文件系統(tǒng)一旦建立后，它們的位置就是固定不變的。 每個(gè)柱面組中的超級(jí)塊拷貝塊的存放位置為安全起見(jiàn)不一定都裝在柱面組中的最前面，而是可浮動(dòng)地裝在該柱面組中的任何位置。 目前大多數(shù)在大存儲(chǔ)環(huán)境下運(yùn)行的 UNIX版本都采用這種存貯結(jié)構(gòu)，其優(yōu)點(diǎn)是能快速定位數(shù)據(jù)塊。第二級(jí)（即柱面組塊）又是由超級(jí)塊拷貝塊、柱面組信息塊， i節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)所組成。整個(gè)存儲(chǔ)結(jié)構(gòu)是一維的。 UNIX的普通文件和目錄文件就保存在這樣的文件系統(tǒng)中。內(nèi)存活動(dòng) i節(jié)點(diǎn)表就是由這 64個(gè) hash鏈表組成。 NULL 鏈 表 尾 活動(dòng) i節(jié)點(diǎn) hash鏈表 當(dāng)某個(gè)文件（即某個(gè)磁盤(pán) i節(jié)點(diǎn)）被打開(kāi)時(shí)，根據(jù)該 i節(jié)點(diǎn)所對(duì)應(yīng)的設(shè)備號(hào)和 i節(jié)點(diǎn)號(hào)計(jì)算其 hash值： hn=(devno+inumber)%64 可得到 0~63共 64個(gè) hash值。 空閑的活動(dòng) i節(jié)點(diǎn)相互鏈接在一起構(gòu)成“空閑活動(dòng) i節(jié)點(diǎn)鏈表”，這是一個(gè)雙向（非循環(huán)）鏈表，分別由鏈頭指針和鏈尾指針指向空閑活動(dòng) i節(jié)點(diǎn)鏈表的開(kāi)始和結(jié)束?；顒?dòng) i節(jié)點(diǎn)表中的每一項(xiàng)就是一個(gè)活動(dòng) i節(jié)點(diǎn)緩沖區(qū)，用來(lái)存放一個(gè)被打開(kāi)文件的 inode。最長(zhǎng)要存取三次間址索引塊才能找到相應(yīng)數(shù)據(jù)的文件系統(tǒng)塊號(hào)（要取出數(shù)據(jù)則要讀 4次磁盤(pán)）。根據(jù)要讀寫(xiě)的數(shù)據(jù)在文件中的位置可計(jì)算出該數(shù)據(jù)所在的邏輯塊號(hào)，查索引表就可找到邏輯塊所在的文件系統(tǒng)塊號(hào)。 struct inode { 活動(dòng) i節(jié)點(diǎn)鏈接指針 狀態(tài)標(biāo)志 設(shè)備號(hào) i節(jié)點(diǎn)號(hào) 最近訪問(wèn)的 i節(jié)點(diǎn)在目錄中的位置 空閑 i節(jié)點(diǎn)鏈接指針 struct inmon { 文件模式和類型（ FIFO、 DIR、 CHR、 BLK、 REG、 LNK等） 文件鏈接數(shù) 文件所有者標(biāo)識(shí)數(shù)（ UID） 文件所屬用戶組標(biāo)識(shí)數(shù)（ GID） 文件大小 文件最近存取時(shí)間（ atime, mtime, ctime） 數(shù)據(jù)塊索引表 其它信息 } } 數(shù)據(jù)塊索引表 數(shù)據(jù)塊索引表用于檢索本文件占用的數(shù)據(jù)塊。 超級(jí)塊 磁盤(pán) i節(jié)點(diǎn)表 數(shù)據(jù)存儲(chǔ)區(qū) 磁盤(pán) imon表 imon imon imon imon imon ?文件所有者標(biāo)識(shí)（ UID） ?用戶組標(biāo)識(shí)（ GID） ?文件類型（ FIFO、 DIR、 CHR、 BLK、 REG、 LNK等） ?文件保護(hù)模式（存取許可權(quán)） mode ?文件存取時(shí)間（ atime, mtime, ctime） ?鏈接數(shù)目 link ?文件大小 size ?文件數(shù)據(jù)塊索引表 index table imon 與 inode 的關(guān)系 進(jìn)程要讀寫(xiě)一個(gè)文件時(shí)，先在內(nèi)存的活動(dòng) i節(jié)點(diǎn)表（即inode表）中申請(qǐng)一個(gè)空閑的活動(dòng) i節(jié)點(diǎn)，并把磁盤(pán)上 i節(jié)點(diǎn)（ imon）中的各項(xiàng)參數(shù)讀入其中，當(dāng)核心操作完成后，如果必要，就把在內(nèi)存中的活動(dòng) i節(jié)點(diǎn)寫(xiě)回到磁盤(pán)上去。 i節(jié)點(diǎn)通常以靜態(tài)的形式存放在磁盤(pán)的 i節(jié)點(diǎn)表中。 網(wǎng) 絡(luò) 虛擬文件系統(tǒng) VFS 網(wǎng)絡(luò)文件 系統(tǒng) NFS 本地文件 系統(tǒng) UFS 物理存 儲(chǔ)介質(zhì) 虛擬文件系統(tǒng) VFS 網(wǎng)絡(luò)文件 系統(tǒng) NFS 本地文件 系統(tǒng) UFS 物理存 儲(chǔ)介質(zhì) 用戶 用戶 A機(jī)器 B機(jī)器 基于虛擬文件系統(tǒng)的體系結(jié)構(gòu) 文件系統(tǒng)結(jié)構(gòu) 本地文件系統(tǒng) 1．文件的存貯結(jié)構(gòu) UNIX的普通文件的邏輯結(jié)構(gòu)是無(wú)格式的有序字節(jié)流，而它們的物理存貯結(jié)構(gòu)是以索引方式來(lái)組織的。 用戶感覺(jué)使用的是一個(gè)整體的，比本地機(jī)器上實(shí)際硬盤(pán)空間大得多的文件系統(tǒng)。 本地文件系統(tǒng)的構(gòu)成 一個(gè)根文件系統(tǒng) + 若干子文件系統(tǒng)所組成 根文件系統(tǒng) 存放本操作系統(tǒng)的最主要和最基本的部分 可獨(dú)立啟動(dòng)運(yùn)行 系統(tǒng)起動(dòng)后，根文件系統(tǒng)就不能卸下來(lái) 子文件系統(tǒng) 主要存放應(yīng)用程序和用戶文件 一般不能獨(dú)立啟動(dòng) 系統(tǒng)運(yùn)行過(guò)程中可隨時(shí)安裝和卸下 網(wǎng)絡(luò)文件系統(tǒng)（ NFS） 是本地機(jī)器上的文件系統(tǒng)和遠(yuǎn)地機(jī)器上的文件系統(tǒng)之間的介質(zhì)，它管理和控制所有有關(guān)對(duì)遠(yuǎn)地文件的各種操作，給本地用戶提供一個(gè)訪問(wèn)遠(yuǎn)地文件的使用方便的高層接口，避免用戶直接涉及網(wǎng)絡(luò)通訊方面的具體細(xì)節(jié)。 事實(shí)上無(wú)論是同步寫(xiě)還是異步寫(xiě)，其根本區(qū)別在于本進(jìn)程是否等待磁盤(pán)驅(qū)動(dòng)程序完成操作后所發(fā)出的中斷信號(hào)。 算法 breada 輸入 ：（ 1）立即讀的文件系統(tǒng)塊號(hào) （ 2）異步讀的文件系統(tǒng)塊號(hào) 輸出：含有立即讀的數(shù)據(jù)的緩沖區(qū) { if（第一塊不在高速緩沖中） { 為第一塊獲得緩沖區(qū)（ getblk）； if（緩沖區(qū)內(nèi)容無(wú)效） 啟動(dòng)磁盤(pán)讀； } if（第二塊不在高速緩沖中） { 為第二塊獲得緩沖區(qū)（ getblk）； if（緩沖區(qū)數(shù)據(jù)有效） 釋放緩沖區(qū)（ brelse）； else 啟動(dòng)磁盤(pán)讀； } if（第一塊本來(lái)就在高速緩沖中） { 讀第一塊（ bread）； return（緩沖區(qū)）； } sleep（第一個(gè)緩沖區(qū)包含有效數(shù)據(jù)的事件）； return（緩沖區(qū)）； } 寫(xiě)磁盤(pán)塊 bwrite 啟動(dòng)磁盤(pán)驅(qū)動(dòng)程序的寫(xiě)操作 如果是“同步寫(xiě)”，則本進(jìn)程睡眠等待磁盤(pán)寫(xiě)操作的完成，磁盤(pán)寫(xiě)操作完成后，中斷喚醒本進(jìn)程，本進(jìn)程釋放該緩沖區(qū)并返回； 如果是“異步寫(xiě)”，則無(wú)需等待磁盤(pán)寫(xiě)操作的完成，將緩沖區(qū)放到空閑鏈表的表頭，以便隨后某個(gè)進(jìn)程申請(qǐng)空閑緩沖區(qū)時(shí)，將其寫(xiě)到磁盤(pán)上去。 預(yù)讀的命中率： 不一定達(dá)到 100%，但良好的系統(tǒng)結(jié)構(gòu)和算法可使命中率達(dá)到較高的水平。 緩沖區(qū)的檢索算法 在 UNIX文件系統(tǒng)中的下層，即直接與邏輯存儲(chǔ)設(shè)備聯(lián)系的部分，包含如下基本算法： getblk 申請(qǐng)一個(gè)緩沖區(qū) brelse 釋放一個(gè)緩沖區(qū) bread 讀一個(gè)磁盤(pán)塊 breada 讀一個(gè)磁盤(pán)塊，預(yù)讀另一個(gè)磁盤(pán)塊 bwrite 寫(xiě)磁盤(pán)塊 申請(qǐng)一個(gè)緩沖區(qū)算法 getblk 根據(jù)緩沖池的結(jié)構(gòu)，核心申請(qǐng)一個(gè)緩沖區(qū)分配個(gè)磁盤(pán)塊時(shí)，可能出現(xiàn)的 五種典型狀況 ： ① 該塊已在 hash隊(duì)列中，并且緩沖區(qū)是空閑的； ② hash隊(duì)列中找不到該塊，需從空閑鏈表中分配一個(gè)緩沖區(qū)； ③ hash隊(duì)列中找不到該塊，在從空閑鏈表中分配一個(gè)緩沖區(qū)時(shí)，發(fā)現(xiàn)該空閑緩沖區(qū)標(biāo)記有“延遲寫(xiě)”，核心必須寫(xiě)出緩沖區(qū)內(nèi)容到磁盤(pán)上，再重新分配一個(gè)空閑緩沖區(qū)； ④ hash隊(duì)列中找不到該塊，并且空閑鏈表已空； ⑤ 該塊已在 hash隊(duì)列中，但該緩沖區(qū)目前狀態(tài)為“忙”。 緩沖池中的緩沖區(qū) 個(gè)數(shù) 是固定不變的，每個(gè)緩沖區(qū)在不同時(shí)刻存放著不同的磁盤(pán)數(shù)據(jù)塊，具有不同的 hash值，因此處在不同的 hash鏈表中。 在空閑緩沖區(qū)鏈表中的緩沖區(qū)一定在某個(gè) hash鏈表中；在hash鏈表中的緩沖區(qū)不一定在空閑鏈中。（同時(shí)在兩個(gè)隊(duì)列中） 申請(qǐng)緩沖區(qū)的兩個(gè)途徑： 要指定緩沖區(qū) —— 在 hash鏈表中查找 要空閑緩沖區(qū) —— 在空閑鏈表中查找 進(jìn)一步說(shuō)明 一個(gè)緩沖區(qū)只有當(dāng)它是空閑狀態(tài)時(shí)，它才同時(shí)處在 hash鏈表和空閑鏈表中。 這 63 個(gè) hash 鏈表就構(gòu)成了數(shù)據(jù)緩沖區(qū)高速緩沖的緩沖池，所有的緩沖區(qū)都存放在緩沖池中的某一個(gè)鏈表中。 RND： 隨機(jī)數(shù)，其值為： RND=MAXBSIZE / DEV_BSIZE MAXBSIZE： 最大文件系統(tǒng)塊的大小 DEV_BSIZE： 物理設(shè)備塊大小 hashno 的取值范圍： 0 ~ 62 緩沖池的結(jié)構(gòu) 具有相同 hashno 的緩沖區(qū)鏈接在同一個(gè) hash鏈表中，因此系統(tǒng)中共有 63 個(gè) hash 鏈表，分別鏈接 hashno 為 0 ~ 62 的緩沖區(qū)。 緩沖區(qū)設(shè)置 當(dāng)核心需有一個(gè)空閑緩沖區(qū)時(shí)，它根據(jù)要裝入的數(shù)據(jù)類型，從相應(yīng)的空閑緩沖區(qū)鏈表的表頭位置取下一個(gè)空閑緩沖區(qū)，裝入一個(gè)磁盤(pán)數(shù)據(jù)塊； 根據(jù)該數(shù)據(jù)塊所對(duì)應(yīng)的 設(shè)備號(hào)和塊號(hào)數(shù)據(jù)對(duì) 計(jì)算其 hashno（散列、雜湊）值，根據(jù)其 hashno 的值放入到相應(yīng) hash 鏈表的鏈頭。避免在取用空閑緩沖區(qū)時(shí)，逐個(gè)判斷緩沖區(qū)中的內(nèi)容。在鏈表頭位置的就是“最近最少使用”的空閑緩沖區(qū)。 ③ 取用裝有指定內(nèi)容的空閑緩沖區(qū) 從鏈表頭開(kāi)始查找，找到