【正文】 的另一個(gè)空閑的緩沖區(qū)鏈表。 緩沖區(qū)中的數(shù)據(jù)與某個(gè)磁盤(pán)數(shù)據(jù)塊一一對(duì)應(yīng)，這種對(duì)應(yīng)有兩個(gè)特點(diǎn) ： ① 一個(gè)磁盤(pán)數(shù)據(jù)塊在緩沖池中最多只能有一個(gè)副本； ② 緩沖區(qū)與數(shù)據(jù)塊的對(duì)應(yīng)是動(dòng)態(tài)的， LRU數(shù)據(jù)塊將被釋放。 釋放一個(gè)緩沖區(qū)算法 brelse ? 喚醒等待緩沖區(qū)的所有進(jìn)程 ? 提高處理機(jī)的執(zhí)行級(jí)別以封鎖同級(jí)或低級(jí)的中斷 ? 將該緩沖區(qū)放到空閑隊(duì)列的尾部（緩沖區(qū)有效）或頭部（緩沖區(qū)無(wú)效） ? 降低處理機(jī)的執(zhí)行級(jí)別以開(kāi)放中斷 讀一個(gè)磁盤(pán)塊 bread ? 由 getblk 算法申請(qǐng)一個(gè)可用的緩沖區(qū) ? 如果緩沖區(qū)中的內(nèi)容有效，則直接返回該緩沖區(qū) ? 如果緩沖區(qū)中的內(nèi)容無(wú)效，則啟動(dòng)磁盤(pán)去讀所需的數(shù)據(jù)塊 ? 等待磁盤(pán)操作完成后返回 算法 bread 輸入：文件系統(tǒng)號(hào) 輸出：含有數(shù)據(jù)的緩沖區(qū) { 得到該塊的緩沖區(qū)（算法 getblk）； if（緩沖區(qū)數(shù)據(jù)有效） return（緩沖區(qū)）； 啟動(dòng)磁盤(pán)讀； sleep（等待“讀盤(pán)完成”事件）； return（緩沖區(qū)）； } 讀一個(gè)磁盤(pán)塊并預(yù)讀另一個(gè)磁盤(pán)塊 breada 預(yù)讀的前提： 程序是在一個(gè)有限的空間內(nèi)運(yùn)行，程序?qū)?shù)據(jù)的訪問(wèn)是可預(yù)見(jiàn)的。 預(yù)讀的結(jié)果： 放在緩沖池內(nèi)，以免需要的時(shí)候再去啟動(dòng)磁盤(pán)讀數(shù)據(jù)塊。本進(jìn)程不再關(guān)心該緩沖區(qū)實(shí)際被寫(xiě)出的時(shí)間和結(jié)果，而直接返回去作其它事情。 算法 bwrite 輸入：緩沖區(qū) 輸出：無(wú) { 啟動(dòng)磁盤(pán)讀； if（ I/O同步） { sleep（等待“ I/O完成”事件）； 釋放緩沖區(qū)（ brelse）； } else if （緩沖區(qū)標(biāo)記著延遲寫(xiě)） 為緩沖區(qū)做標(biāo)記以放到空閑緩沖區(qū)鏈表頭部； } 數(shù)據(jù)緩沖區(qū)高速緩沖的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： ? 提供了對(duì)磁盤(pán)塊的統(tǒng)一的存取方法 ? 消除了用戶對(duì)用戶緩沖區(qū)中數(shù)據(jù)的特殊對(duì)齊需要 ? 減少了磁盤(pán)訪問(wèn)的次數(shù)，提高了系統(tǒng)的整體 I/O效率 ? 有助于保持文件系統(tǒng)的完整性 缺點(diǎn)： ? 數(shù)據(jù)未及時(shí)寫(xiě)盤(pán)而帶來(lái)的風(fēng)險(xiǎn) ? 額外的數(shù)據(jù)拷貝過(guò)程，大量數(shù)據(jù)傳輸時(shí)影響性能 第四章 文件和文件系統(tǒng)的內(nèi)部結(jié)構(gòu) 現(xiàn)代 UNIX的文件系統(tǒng)通?？捎扇竽K組成： ①本地文件系統(tǒng)（ UFS） ——User File System ② 網(wǎng)絡(luò)文件系統(tǒng)（ NFS） ——Network File System ③ 虛擬文件系統(tǒng)（ VFS） ——Virtual File System 本地文件系統(tǒng)（ UFS） 是 UNIX系統(tǒng)中的基本文件系統(tǒng)，它通常固定存放在本地機(jī)器的存貯設(shè)備上，任何一種結(jié)構(gòu)形式的文件系統(tǒng)都必然會(huì)直接或間接地與某個(gè)本地文件系統(tǒng)相聯(lián)系。 虛擬文件系統(tǒng)（ VFS） VFS是整個(gè)操作系統(tǒng)的用戶界面，它給用戶提供一個(gè)統(tǒng)一的文件系統(tǒng)使用接口，避免用戶涉及各個(gè)子文件系統(tǒng)的特征部分。 虛構(gòu)文件系統(tǒng)接受來(lái)自用戶的操作請(qǐng)求，根據(jù)該操作所訪問(wèn)的文件是存放在本地機(jī)器上，還是存放在遠(yuǎn)地機(jī)器上而分別把操作交給本地文件系統(tǒng)或網(wǎng)絡(luò)文件系統(tǒng)；本地文件系統(tǒng)或網(wǎng)絡(luò)文件系統(tǒng)（實(shí)際上再傳給遠(yuǎn)地機(jī)器上的本地文件系統(tǒng)）進(jìn)行相應(yīng)的操作后，將結(jié)果返回到虛擬文件系統(tǒng)中再傳回給用戶。 每個(gè)文件都是由一個(gè)索引節(jié)點(diǎn) i節(jié)點(diǎn)來(lái)表示的，每個(gè) i節(jié)點(diǎn)由其 i節(jié)點(diǎn)號(hào)來(lái)標(biāo)識(shí)。每個(gè)磁盤(pán) i節(jié)點(diǎn)表項(xiàng)是由數(shù)據(jù)結(jié)構(gòu) imon定義的，描述對(duì)應(yīng)文件的 靜態(tài)參數(shù) 。 內(nèi)存活動(dòng) i節(jié)點(diǎn)由數(shù)據(jù)結(jié)構(gòu) inode來(lái)定義，它除了包含磁盤(pán)上對(duì)應(yīng)的 imon中的各項(xiàng)參數(shù)外，還包含有其它的參數(shù)，如該活動(dòng) i節(jié)點(diǎn)的狀態(tài)、文件所在的邏輯設(shè)備號(hào)、 i節(jié)點(diǎn)號(hào)、活動(dòng) i節(jié)點(diǎn)鏈接指針，最近使用的 i節(jié)點(diǎn)在目錄中的位置等 動(dòng)態(tài)信息 。它包含 12項(xiàng)直接索引表目和 3項(xiàng)間接索引表目。 系統(tǒng)根據(jù)計(jì)算出來(lái)的邏輯塊號(hào)判斷是否包含在直接索引表中，如果是，則取出直接索引表中的文件系統(tǒng)塊號(hào)；如不是，則看是否包含在一次間接索引塊中，否則再尋找二次和三次間接索引塊。 直接 0 直接 1 直接 2 直接 11 一次間址 二次間址 三次間址 數(shù)據(jù)塊索引表 一級(jí)間址塊 二級(jí)間址塊 三級(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)緩沖區(qū)簡(jiǎn)稱為“活動(dòng) i節(jié)點(diǎn)” ）。如下圖所示： 鏈 表 頭 空 閑 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)）鏈表，分別由鏈表頭指針和鏈表尾指針指向空閑鏈表的首尾。具有相同 hash值的活動(dòng) i節(jié)點(diǎn)鏈接在同一個(gè) hash鏈表中，這樣內(nèi)存中就有 64個(gè) hash鏈表，每個(gè)hash鏈表都是由 hash鏈頭開(kāi)始的雙向鏈表（與數(shù)據(jù)緩沖區(qū)鏈表不同的是此處的空閑和非空閑鏈表都是非循環(huán)的） 。如下圖所示： 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è)物理磁盤(pán)通常被劃分成一個(gè)或多個(gè)邏輯文件系統(tǒng)（簡(jiǎn)稱文件系統(tǒng)或子文件系統(tǒng)），每個(gè)邏輯文件系統(tǒng)都被當(dāng)作一個(gè)由邏輯設(shè)備號(hào)標(biāo)識(shí)的邏輯設(shè)備。邏輯文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)可分為兩類型： 一級(jí)存儲(chǔ)結(jié)構(gòu)型 ：常用于運(yùn)行環(huán)境較小的文件系統(tǒng)中 二級(jí)存儲(chǔ)結(jié)構(gòu)型 ：常用于運(yùn)行環(huán)境較大（特別是硬盤(pán)空間較大）的文件系統(tǒng)中 ① 、一級(jí)存儲(chǔ)結(jié)構(gòu)型 這種類型的邏輯文件系統(tǒng)由超級(jí)塊、索引節(jié)點(diǎn)表塊和數(shù)據(jù)區(qū)組成，（如果是根文件系統(tǒng)，就還包括引導(dǎo)塊）。 引導(dǎo)塊 超級(jí)塊 i節(jié)點(diǎn)表塊 數(shù)據(jù)區(qū) 引導(dǎo)塊： boot程序 超級(jí)塊： fs結(jié)構(gòu)，存放文件系統(tǒng)的靜態(tài)參數(shù) i 節(jié)點(diǎn)表塊：磁盤(pán) imon表 數(shù)據(jù)區(qū)： 各數(shù)據(jù)塊 ② 、兩級(jí)存儲(chǔ)結(jié)構(gòu)型 這種存儲(chǔ)結(jié)構(gòu)的文件系統(tǒng)由兩級(jí)組成：第一級(jí)由超級(jí)塊和若干個(gè) 柱面組塊 （ cylinder group block）所組成（如果是根文件系統(tǒng)則還包括引導(dǎo)塊）。文件系統(tǒng)的存儲(chǔ)結(jié)構(gòu)是二維的。 第一級(jí)存儲(chǔ)結(jié)構(gòu) 引導(dǎo)塊 超級(jí)塊 1號(hào)柱面組塊 2號(hào)柱面組塊 …… n號(hào)柱面組塊 第二級(jí)存儲(chǔ)結(jié)構(gòu) 超級(jí)塊拷貝塊 柱面組信息塊 i節(jié)點(diǎn)表塊 數(shù)據(jù)區(qū) 超級(jí)塊 是由 fs定義的數(shù)據(jù)結(jié)構(gòu)，用于存放文件系統(tǒng)的靜態(tài)參數(shù)： struct fs { 內(nèi)存超級(jí)塊鏈接指針 超級(jí)塊的磁盤(pán)地址 柱面組塊的位移量 最近修改時(shí)間 文件系統(tǒng)大小 文件系統(tǒng)塊大小 柱面組數(shù) 柱面組大小 片大小 文件系統(tǒng)標(biāo)識(shí)數(shù) 文件系統(tǒng)標(biāo)志區(qū) 最近訪問(wèn)的柱面組號(hào) 確定分配算法的參數(shù) } 超級(jí)塊拷貝塊： 在每個(gè)柱面組塊中存放有一個(gè)超級(jí)塊拷貝塊，其目的是使系統(tǒng)在超級(jí)塊被意外破壞時(shí)，能從任何一個(gè)柱面組中進(jìn)行恢復(fù)而不致使整個(gè)文件系統(tǒng)陷入癱瘓。 一般性的方法是：如果第 n號(hào)柱面組中的超級(jí)塊拷貝塊開(kāi)始于該柱面組中的第 i磁道，則第 n+1柱面組中的超級(jí)塊拷貝塊開(kāi)始于該柱面組中的第 i+1磁道。 柱面組信息塊（ cg塊） 柱面組信息塊中存放的是有關(guān)該柱面組的靜態(tài)參數(shù)，它由數(shù)據(jù)結(jié)構(gòu) cg來(lái)定義： 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）的值來(lái)表示某一個(gè)資源（例如數(shù)據(jù)塊或 i節(jié)點(diǎn)）的狀態(tài)，這樣每檢測(cè)一個(gè)字節(jié)的值就可以知道八個(gè)資源的狀態(tài)；每檢測(cè)一個(gè)四字節(jié)的整數(shù)的值就可以知道 32個(gè)資源的狀態(tài)。 文件系統(tǒng)的數(shù)據(jù)塊 在文件系統(tǒng)中，按存儲(chǔ)單位來(lái)劃分，由大到小可有下列層次： 文件系統(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)。 目錄也被當(dāng)作文件進(jìn)行處理，一個(gè)目錄文件的結(jié)構(gòu)為表狀結(jié)構(gòu)，其中通常包含有若干表項(xiàng)，稱為目錄項(xiàng)，這些目錄項(xiàng)既可以是普通文件的入口，也可以是子目錄的入口。 2 。 2 。 2 。 153 。 376 。 584 。 /*目錄項(xiàng) i節(jié)點(diǎn)號(hào) */ char d_name [MAXNAMELEN]。 這種定長(zhǎng)目錄項(xiàng)在算法實(shí)現(xiàn)方面比較簡(jiǎn)單，在使用靈活方面都有所不便，并且可能因許多目錄項(xiàng)名字長(zhǎng)度不足 14字符面有空間浪費(fèi)。 1號(hào) i節(jié)點(diǎn) ： 表示壞塊文件，所有的磁盤(pán)壞塊都劃歸到該節(jié)點(diǎn)上； 2號(hào) i節(jié)點(diǎn) ： 固定表示該邏輯文件系統(tǒng)的根（ root）目錄； 3號(hào) i節(jié)點(diǎn) ： 表示該文件系統(tǒng)中的 lost+found 目錄。 /* 目錄項(xiàng) i節(jié)點(diǎn)號(hào) */ short d_reclen。前一個(gè)目錄項(xiàng)釋放時(shí)，把該目錄項(xiàng)的空間全部合并到前一個(gè)目錄項(xiàng)中，形成前面一個(gè)目錄項(xiàng)占用空間大于實(shí)際使用的空間。 變長(zhǎng)目錄結(jié)構(gòu)增加了算法復(fù)雜性和工作量，通常用在硬件性能較高的大型系統(tǒng)中。 名字緩沖區(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）鏈表為定長(zhǎng)雙向循環(huán)鏈表 為提高查找文件名的速度，還根據(jù)每個(gè) ncache的 hash值，將其掛接到一個(gè) hash鏈表中。(*namep+*(namep1+slen)+slen+(int)VP) namep：為指向名字字符串的指針 slen： 為名字長(zhǎng)度 VP： 為父目錄節(jié)點(diǎn)指針 計(jì)算出相應(yīng)的 hash值（ 0~7）。