【正文】 最長要存取三次間址索引塊才能找到相應(yīng)數(shù)據(jù)的文件系統(tǒng)塊號（要取出數(shù)據(jù)則要讀 4次磁盤）。 直接 0 直接 1 直接 2 直接 11 一次間址 二次間址 三次間址 數(shù)據(jù)塊索引表 一級間址塊 二級間址塊 三級間址塊 數(shù)據(jù)塊 inode表的結(jié)構(gòu) 在內(nèi)存中，活動(dòng) i節(jié)點(diǎn)表類似于數(shù)據(jù)緩沖區(qū)高速緩沖中的緩沖池結(jié)構(gòu)。活動(dòng) i節(jié)點(diǎn)表中的每一項(xiàng)就是一個(gè)活動(dòng) i節(jié)點(diǎn)緩沖區(qū)，用來存放一個(gè)被打開文件的 inode。（以下 把活動(dòng) i節(jié)點(diǎn)緩沖區(qū)簡稱為“活動(dòng) i節(jié)點(diǎn)” ）。 空閑的活動(dòng) i節(jié)點(diǎn)相互鏈接在一起構(gòu)成“空閑活動(dòng) i節(jié)點(diǎn)鏈表”，這是一個(gè)雙向（非循環(huán)）鏈表，分別由鏈頭指針和鏈尾指針指向空閑活動(dòng) i節(jié)點(diǎn)鏈表的開始和結(jié)束。如下圖所示： 鏈 表 頭 空 閑 i 節(jié) 點(diǎn) 1 空 閑 i 節(jié) 點(diǎn) 2 空 閑 i 節(jié) 點(diǎn) 3 空 閑 i 節(jié) 點(diǎn) n 空閑活動(dòng) i節(jié)點(diǎn)鏈表為雙向（非循環(huán)）鏈表，分別由鏈表頭指針和鏈表尾指針指向空閑鏈表的首尾。 NULL 鏈 表 尾 活動(dòng) i節(jié)點(diǎn) hash鏈表 當(dāng)某個(gè)文件（即某個(gè)磁盤 i節(jié)點(diǎn)）被打開時(shí)，根據(jù)該 i節(jié)點(diǎn)所對應(yīng)的設(shè)備號和 i節(jié)點(diǎn)號計(jì)算其 hash值： hn=(devno+inumber)%64 可得到 0~63共 64個(gè) hash值。具有相同 hash值的活動(dòng) i節(jié)點(diǎn)鏈接在同一個(gè) hash鏈表中，這樣內(nèi)存中就有 64個(gè) hash鏈表，每個(gè)hash鏈表都是由 hash鏈頭開始的雙向鏈表（與數(shù)據(jù)緩沖區(qū)鏈表不同的是此處的空閑和非空閑鏈表都是非循環(huán)的） 。內(nèi)存活動(dòng) i節(jié)點(diǎn)表就是由這 64個(gè) hash鏈表組成。如下圖所示： inode inode inode inode inode inode inode inode inode 空閑鏈表頭 Hash鏈表頭 hn=0 hn=1 hn=63 NULL 空閑鏈表尾 活動(dòng) inode 表的結(jié)構(gòu) 文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu) 在 UNIX系統(tǒng)中，一個(gè)物理磁盤通常被劃分成一個(gè)或多個(gè)邏輯文件系統(tǒng)（簡稱文件系統(tǒng)或子文件系統(tǒng)），每個(gè)邏輯文件系統(tǒng)都被當(dāng)作一個(gè)由邏輯設(shè)備號標(biāo)識的邏輯設(shè)備。 UNIX的普通文件和目錄文件就保存在這樣的文件系統(tǒng)中。邏輯文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)可分為兩類型： 一級存儲(chǔ)結(jié)構(gòu)型 ：常用于運(yùn)行環(huán)境較小的文件系統(tǒng)中 二級存儲(chǔ)結(jié)構(gòu)型 ：常用于運(yùn)行環(huán)境較大（特別是硬盤空間較大）的文件系統(tǒng)中 ① 、一級存儲(chǔ)結(jié)構(gòu)型 這種類型的邏輯文件系統(tǒng)由超級塊、索引節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)組成，（如果是根文件系統(tǒng)，就還包括引導(dǎo)塊）。整個(gè)存儲(chǔ)結(jié)構(gòu)是一維的。 引導(dǎo)塊 超級塊 i節(jié)點(diǎn)表塊 數(shù)據(jù)區(qū) 引導(dǎo)塊： boot程序 超級塊： fs結(jié)構(gòu)，存放文件系統(tǒng)的靜態(tài)參數(shù) i 節(jié)點(diǎn)表塊：磁盤 imon表 數(shù)據(jù)區(qū)： 各數(shù)據(jù)塊 ② 、兩級存儲(chǔ)結(jié)構(gòu)型 這種存儲(chǔ)結(jié)構(gòu)的文件系統(tǒng)由兩級組成：第一級由超級塊和若干個(gè) 柱面組塊 （ cylinder group block）所組成（如果是根文件系統(tǒng)則還包括引導(dǎo)塊）。第二級（即柱面組塊）又是由超級塊拷貝塊、柱面組信息塊， i節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)所組成。文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)是二維的。 目前大多數(shù)在大存儲(chǔ)環(huán)境下運(yùn)行的 UNIX版本都采用這種存貯結(jié)構(gòu)，其優(yōu)點(diǎn)是能快速定位數(shù)據(jù)塊。 第一級存儲(chǔ)結(jié)構(gòu) 引導(dǎo)塊 超級塊 1號柱面組塊 2號柱面組塊 …… n號柱面組塊 第二級存儲(chǔ)結(jié)構(gòu) 超級塊拷貝塊 柱面組信息塊 i節(jié)點(diǎn)表塊 數(shù)據(jù)區(qū) 超級塊 是由 fs定義的數(shù)據(jù)結(jié)構(gòu)，用于存放文件系統(tǒng)的靜態(tài)參數(shù)： struct fs { 內(nèi)存超級塊鏈接指針 超級塊的磁盤地址 柱面組塊的位移量 最近修改時(shí)間 文件系統(tǒng)大小 文件系統(tǒng)塊大小 柱面組數(shù) 柱面組大小 片大小 文件系統(tǒng)標(biāo)識數(shù) 文件系統(tǒng)標(biāo)志區(qū) 最近訪問的柱面組號 確定分配算法的參數(shù) } 超級塊拷貝塊： 在每個(gè)柱面組塊中存放有一個(gè)超級塊拷貝塊，其目的是使系統(tǒng)在超級塊被意外破壞時(shí)，能從任何一個(gè)柱面組中進(jìn)行恢復(fù)而不致使整個(gè)文件系統(tǒng)陷入癱瘓。 每個(gè)柱面組中的超級塊拷貝塊的存放位置為安全起見不一定都裝在柱面組中的最前面，而是可浮動(dòng)地裝在該柱面組中的任何位置。 一般性的方法是：如果第 n號柱面組中的超級塊拷貝塊開始于該柱面組中的第 i磁道，則第 n+1柱面組中的超級塊拷貝塊開始于該柱面組中的第 i+1磁道。文件系統(tǒng)一旦建立后，它們的位置就是固定不變的。 柱面組信息塊（ cg塊） 柱面組信息塊中存放的是有關(guān)該柱面組的靜態(tài)參數(shù)，它由數(shù)據(jù)結(jié)構(gòu) cg來定義： struct cg { 內(nèi)存中柱面組塊的鏈接指針 本柱面組塊中 i節(jié)點(diǎn)表大小 本柱面組塊中數(shù)據(jù)區(qū)大小 最近一次所用塊的位置 最近一次所用片的位置 最近一次所用 i節(jié)點(diǎn)的位置 本柱面組空閑數(shù)據(jù)塊總數(shù) i節(jié)點(diǎn)位示圖 空閑塊位示圖 } 位示圖： 位示圖為一張表，其中的每一個(gè)二進(jìn)制位（ bit）的值來表示某一個(gè)資源（例如數(shù)據(jù)塊或 i節(jié)點(diǎn)）的狀態(tài)，這樣每檢測一個(gè)字節(jié)的值就可以知道八個(gè)資源的狀態(tài)；每檢測一個(gè)四字節(jié)的整數(shù)的值就可以知道 32個(gè)資源的狀態(tài)。 系統(tǒng)只需要維護(hù)一張較小的表（位示圖）就可以快速地檢測指定資源的忙閑狀態(tài)，或快速查找可用的空閑資源。 文件系統(tǒng)的數(shù)據(jù)塊 在文件系統(tǒng)中，按存儲(chǔ)單位來劃分，由大到小可有下列層次： 文件系統(tǒng) (file system) 柱面組 (cylinder group) 柱面 (cylinder) 磁道 (track) 扇區(qū) (sector) DEV_BSIZE 512字節(jié) 文件系統(tǒng)的邏輯塊大?。? DEV_BSIZE * 2? 即 1k、 2k、 4k、 8k、 16k … 目的：提高傳輸速度，減少 overhead 文件系統(tǒng)的邏輯片大?。? DEV_BSIZE * 2? 即 1k、 2k、 4k、 8k、 16k … 目的：減少文件尾的碎片浪費(fèi)。 6．目錄和目錄項(xiàng) 在 UNIX文件系統(tǒng)中，目錄的組織形式采用的是樹形結(jié)構(gòu)，一個(gè)邏輯文件系統(tǒng)就是一棵目錄樹。 目錄也被當(dāng)作文件進(jìn)行處理，一個(gè)目錄文件的結(jié)構(gòu)為表狀結(jié)構(gòu)，其中通常包含有若干表項(xiàng)，稱為目錄項(xiàng)，這些目錄項(xiàng)既可以是普通文件的入口，也可以是子目錄的入口。 每一個(gè)目錄項(xiàng)中通常包含兩部分內(nèi)容： 文件的 i 節(jié)點(diǎn)號 文件名 目錄 /home/student/xiaolan 的路徑和目錄結(jié)構(gòu) 2 。 2 。 153 home 0 tst 85 bin 85 。 2 。 153 。 2 。 290 log 376 student 376 。 153 。 584 xiaolan 584 。 376 。 409 bckup 230 src 409 。 584 。 / /home /bin /home/log /home/student /home/student/xiaolan /home/student/xiaolan/src /每個(gè)目錄項(xiàng)由數(shù)據(jù)結(jié)構(gòu) direct來定義： define MAXNAMLEN 14 struct direct { short d_ino。 /*目錄項(xiàng) i節(jié)點(diǎn)號 */ char d_name [MAXNAMELEN]。 /*目錄項(xiàng)名字字符串 */ } 每個(gè)目錄項(xiàng)的長度通常是確定的，為 16個(gè)字節(jié)，其中前兩個(gè)字節(jié)存放文件的 i節(jié)點(diǎn)號 d_ino，后面 14個(gè)字節(jié)存放文件名d_name。 這種定長目錄項(xiàng)在算法實(shí)現(xiàn)方面比較簡單，在使用靈活方面都有所不便，并且可能因許多目錄項(xiàng)名字長度不足 14字符面有空間浪費(fèi)。 在 UNIX的每個(gè)文件系統(tǒng)中，有三個(gè) i 節(jié)點(diǎn)號是有固定用途的： 0號 i節(jié)點(diǎn) ： 表示空目錄項(xiàng)，當(dāng)某個(gè)目錄項(xiàng)被刪除時(shí)，該目錄項(xiàng)的 i 節(jié)點(diǎn)號被置為 0。 1號 i節(jié)點(diǎn) ： 表示壞塊文件，所有的磁盤壞塊都劃歸到該節(jié)點(diǎn)上； 2號 i節(jié)點(diǎn) ： 固定表示該邏輯文件系統(tǒng)的根（ root）目錄； 3號 i節(jié)點(diǎn) ： 表示該文件系統(tǒng)中的 lost+found 目錄。 變長目錄項(xiàng)的目錄結(jié)構(gòu) define MAXNAMLEN 255 struct direct { long d_ino。 /* 目錄項(xiàng) i節(jié)點(diǎn)號 */ short d_reclen。 /* 目錄項(xiàng)入口長度（占用長度） */ short d_namelen； /* 目錄項(xiàng)名字長度 */ char d_name [MAXNAMLEN+1] /* 名字字符串， +1為串結(jié)束符 \0 */ } 由于目錄中各目錄項(xiàng)的長度是變化的，因此必須在目錄項(xiàng)中標(biāo)明本目錄項(xiàng)的長度。前一個(gè)目錄項(xiàng)釋放時(shí)，把該目錄項(xiàng)的空間全部合并到前一個(gè)目錄項(xiàng)中，形成前面一個(gè)目錄項(xiàng)占用空間大于實(shí)際使用的空間。 在增加新目錄時(shí)，先查看目錄中各目錄項(xiàng)是否占用多余空間，如有，則進(jìn)行壓縮，把釋放的空間分配給新目錄項(xiàng)。 變長目錄結(jié)構(gòu)增加了算法復(fù)雜性和工作量，通常用在硬件性能較高的大型系統(tǒng)中。 文件名和文件名緩沖區(qū) 核心在內(nèi)存中建立了一個(gè)高速的名字緩沖區(qū)，用來存放最近使用過的文件名，核心認(rèn)為“最近使用過的文件名馬上還要使用的可能性最大” 。 名字緩沖區(qū)是由 ncache定義的數(shù)據(jù)結(jié)構(gòu)，只包含文件名和索引節(jié)點(diǎn)指針等重要信息： struct ncache { hash鏈表指針 LRU鏈表指針 文件 i節(jié)點(diǎn)指針 /* 這里只需要節(jié)點(diǎn)指針，因內(nèi)存 中已有活動(dòng) i節(jié)點(diǎn)表 */ 文件父目錄節(jié)點(diǎn)指針 文件名 確認(rèn)信息 } 鏈 表 頭 名 字 緩 沖 區(qū) 1 名 字 緩 沖 區(qū) 2 名 字 緩 沖 區(qū) 3 名 字 緩 沖 區(qū) n 名字緩沖區(qū)（ ncache）鏈表為定長雙向循環(huán)鏈表 為提高查找文件名的速度，還根據(jù)每個(gè) ncache的 hash值，將其掛接到一個(gè) hash鏈表中。 ncache的 hash值用下列公式計(jì)算： hn=7amp。(*namep+*(namep1+slen)+slen+(int)VP) namep：為指向名字字符串的指針 slen： 為名字長度 VP： 為父目錄節(jié)點(diǎn)指針 計(jì)算出相應(yīng)的 hash值（ 0~7）。共建立 8個(gè) hash鏈，每個(gè) hash鏈?zhǔn)且粋€(gè)以鏈表頭開始的雙向循環(huán)鏈表， 每個(gè) ncache任何時(shí)候都同時(shí)既在 hash鏈上，又在 LRU鏈上 。 n