【文章內(nèi)容簡介】 結(jié)點(diǎn)中的地址項(xiàng) iaddr(10)來提供一次間接地址 。 這種方式的實(shí)質(zhì)就是一級(jí)索引分配方式 。圖中的一次間址塊也就是索引塊 ， 系統(tǒng)將分配給文件的多個(gè)盤塊號(hào)記入其中 。 在一次間址塊中可存放 1K個(gè)盤塊號(hào) ， 因而允許文件長達(dá) 4 MB。 第四章 存儲(chǔ)器管理 (3) 多次間接地址 。 當(dāng)文件長度大于 4 MB+40 KB時(shí) (一次間址與 10個(gè)直接地址項(xiàng) )， 系統(tǒng)還須采用二次間址分配方式 。 這時(shí) ， 用地址項(xiàng) iaddr(11)提供二次間接地址 。 該方式的實(shí)質(zhì)是兩級(jí)索引分配方式 。 系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的盤號(hào) 。 在采用二次間址方式時(shí) ， 文件最大長度可達(dá)4 GB。 同理 ， 地址項(xiàng) iaddr(12)作為三次間接地址 ， 其所允許的文件最大長度可達(dá) 4 TB。 第四章 存儲(chǔ)器管理 文件物理結(jié)構(gòu)的比較 ? 順序文件 的優(yōu)點(diǎn)是不需要額外的空間開銷 ， 只要在文件目錄中指出文件的大小和首塊的塊號(hào)即可 ， 對(duì)順序的訪問效率很高 。 適應(yīng)于順序存取且文件不經(jīng)常修改的情況 。 缺點(diǎn)是文件動(dòng)態(tài)地增長和縮小時(shí)系統(tǒng)開銷很大；文件創(chuàng)建時(shí)要求用戶提供文件的大?。淮鎯?chǔ)空間浪費(fèi)較大 。 ? 鏈接文件 克服了連續(xù)文件的不足之處 ， 但文件的隨機(jī)訪問系統(tǒng)開銷較大 。 適應(yīng)于順序訪問的文件 。 ? 索引文件 既適應(yīng)于順序訪問 ， 也適應(yīng)于隨機(jī)訪問 ， 是一種比較 好的文件物理結(jié)構(gòu) ， 但要有用于索引表的空間開銷和文件索引的時(shí)間開銷 。 UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子 。 第四章 存儲(chǔ)器管理 文件目錄管理 ? 一個(gè)文件的說明信息稱為該文件的 目錄 。用戶向系統(tǒng)提供符號(hào)名，系統(tǒng)根據(jù)文件的符號(hào)名找到它的物理地址。 ?功能：實(shí)現(xiàn)文件的按名存取，實(shí)現(xiàn)符號(hào)名與具體物理地址之間的轉(zhuǎn)換，文件的共享和保護(hù)。 第四章 存儲(chǔ)器管理 對(duì)目錄管理的要求如下： (1) 實(shí)現(xiàn)“按名存取”。 (2) 提高對(duì)目錄的檢索速度。 (3) 文件共享。 (4) 允許文件重名。 第四章 存儲(chǔ)器管理 一 .文件控制塊和索引結(jié)點(diǎn) 1. 文件控制塊 （ FCB） 文件控制塊是系統(tǒng)在管理文件時(shí)所必需信息的數(shù)據(jù)結(jié)構(gòu)，文件與 FCB一一對(duì)應(yīng)，是文件存在的唯一標(biāo)志。 (1) 基本信息類 ： ① 文件名 ； ② 文件物理地址 ： 順序文件： 鏈接文件： 索引文件： ③ 文件邏輯結(jié)構(gòu) ； 起始?jí)K號(hào)、塊數(shù) 起始?jí)K號(hào) 索引表首址 ④ 用戶名： 文件主、核準(zhǔn)用戶、用戶組等 ⑤ 文件長度： ⑥ 文件類型： 第四章 存儲(chǔ)器管理 (2) 存取控制信息類 文件主的權(quán)限；核準(zhǔn)用戶的權(quán)限；一般用戶的權(quán)限。 (3) 使用信息類 ： ① 文件建立日期及時(shí)間； ② 文件最近訪問日期及時(shí)間； ③ 文件最近修改日期及時(shí)間； ④ 文件鏈接計(jì)數(shù)。 第四章 存儲(chǔ)器管理 一 .文件控制塊和索引結(jié)點(diǎn) ? 屬性： 舉例： MSDOS的文件控制塊 文件名 擴(kuò)展名 屬性 保留 時(shí)間 日期 起始?jí)K號(hào) 文件長度 8B 4B 2B 2B 2B 10B 1B 3B 位 b7 b6 b5 b4 b3 b2 b1 b0 含義 保留 保留 歸檔 子目錄 卷標(biāo) 系統(tǒng) 隱藏 只讀 時(shí)間：最近修改時(shí)間 位 b15 ～ b11 b10 ～ b5 b4 ～ b0 含義 小時(shí) 分鐘 秒 ? 日期：最近修改日期 位 b15 ～ b9 b8 ～ b5 b4 ～ b0 含義 相對(duì)于 1980年的年份偏移量 月份 日期 第四章 存儲(chǔ)器管理 2. 索引結(jié)點(diǎn)（ i節(jié)點(diǎn)） （ 1） 索引結(jié)點(diǎn)的引入 FCB內(nèi)容 = 文件名 + 文件其他描述信息 i節(jié)點(diǎn) 傳統(tǒng) unix目錄項(xiàng)： 文件名（ 14B） i節(jié)點(diǎn)編號(hào)（ 2B） 文件名 （ 255B） i節(jié)點(diǎn)編號(hào) （ 4B） 本目錄項(xiàng)長度 文件名長度 Unix S5fs 第四章 存儲(chǔ)器管理 （ 2）磁盤 i結(jié)點(diǎn) ? 文件屬性：文件類型及存取權(quán)限； ? 文件主標(biāo)識(shí)符 ；同組用戶標(biāo)識(shí)符； ? 文件物理地址 ； ? 文件長度 ； ? 文件創(chuàng)建日期、時(shí)間； ? 文件最近訪問日期、時(shí)間； ? 文件最近修改日期時(shí)間。 第四章 存儲(chǔ)器管理 （ 3）內(nèi)存 i結(jié)點(diǎn) ? 磁盤 i節(jié)點(diǎn)號(hào)； ? 邏輯設(shè)備號(hào)； ? 狀態(tài)位： i節(jié)點(diǎn)是否上鎖或被修改； ? 訪問計(jì)數(shù)； ? 下一個(gè)內(nèi)存 i節(jié)點(diǎn)指針。 第四章 存儲(chǔ)器管理 二 . 目錄結(jié)構(gòu) 1. 單級(jí)目錄結(jié)構(gòu) ： 整個(gè)文件系統(tǒng)只建立一張目錄表。 文件名 物理地址 其他描述信息 狀態(tài)位 文件名 1 1 文件名 2 1 0 … 優(yōu)點(diǎn)： ? 實(shí)現(xiàn)簡單 ?能實(shí)現(xiàn)按名存取 缺點(diǎn)： ?查找速度慢； ? 不允許重名 ； 第四章 存儲(chǔ)器管理 2. 兩級(jí)目錄結(jié)構(gòu) Report Test Zhang用戶目錄 Test Gao用戶目錄 Beta Device Misx Beta Device Misx Wang用戶目錄 (UFD) Alpha Test file1 Alpha Test Report 用戶名 用戶目錄指針 Wang Zhang Gao 系統(tǒng)目錄或主目錄 第四章 存儲(chǔ)器管理 兩級(jí)目錄的優(yōu)點(diǎn) ： (1)提高了檢索目錄的速度 (2) 在不同的用戶目錄中， 可以使用相同的文件名。 (3) 不同用戶還可使用不同的文件名來訪問系統(tǒng)中的同一個(gè)共享文件 第四章 存儲(chǔ)器管理 3. 多級(jí)目錄結(jié)構(gòu) (1) 目錄結(jié)構(gòu) A B C F E D 1 3 A B D 2 G A 4 A C 5 6 7 10 11 J N K 12 J M K 13 A H F 14 15 16 b 17 18 19 20 21 a 8 9 根目錄 第四章 存儲(chǔ)器管理 (2) 路徑名： ? 絕對(duì)路徑： 根目錄 /子目錄名 … /文件名 ? 相對(duì)路徑： 當(dāng)前目錄 /子目錄名 … /文件名 (3) 當(dāng)前目錄 ?多級(jí)目錄的優(yōu)點(diǎn)： ? 層次清楚； ? 允許文件重名； ? 進(jìn)一步提高目錄檢索速度； ? 容易實(shí)現(xiàn)共享 第四章 存儲(chǔ)器管理 三 . 目錄查詢技術(shù) 1. 線性檢索法 ： /usr/ast/mbox 根目錄 tmp 8 usr 6 etc 9 lib 14 dev 7 bin 4 .. 1 . 1 6 i節(jié)點(diǎn) 132 26 i節(jié)點(diǎn) 496 /usr子目錄 file2 20 bal 45 ast 26 jim 51 erik 30 dick 19 .. 1 . 6 /ast子目錄 ab 78 src 17 mini 81 mbox 60 book 92 grant 64 .. 6 . 26 第四章 存儲(chǔ)器管理 2. Hash方法 對(duì)于 Hash索引文件目錄 ， 可利用 Hash方法進(jìn)行查詢：系統(tǒng)利用用戶提供的文件名并將它變換為文件目錄的索引值 ，再利用該索引值到目錄中查找 。 這可顯著地提高檢索速度 。 Hash方式不支持使用通配符的模式匹配查找功能 ，此時(shí)還是需要利用線性查找方式 。 在進(jìn)行文件名的轉(zhuǎn)換時(shí) ， 有可能把 n個(gè)不同的文件名轉(zhuǎn)換為相同的 Hash值 ， 即出現(xiàn)所謂的 “ 沖突 ” 。 第四章 存儲(chǔ)器管理 2. Hash方法 一種處理此 “ 沖突 ” 的有效規(guī)則是： (1) 在利用 Hash法索引查找目錄時(shí) ， 如果目錄表中相應(yīng)的目錄項(xiàng)是空的 ， 則表示系統(tǒng)中并無指定文件 。 (2) 如果目錄項(xiàng)中的文件名與指定文件名相匹配 ， 則表示該目錄項(xiàng)正是所要尋找的文件所對(duì)應(yīng)的目錄項(xiàng) ， 故而可從中找到該文件所在的物理地址 。 (3) 如果在目錄表的相應(yīng)目錄項(xiàng)中的文件名與指定文件名并不匹配 ， 則表示發(fā)生了 “ 沖突 ” ， 此時(shí)須將其 Hash值再加上一個(gè)常數(shù) (該常數(shù)應(yīng)與目錄的長度值互質(zhì) )， 形成新的索引值 ， 再返回到第一步重新開始查找 。 第四章 存儲(chǔ)器管理 文件存儲(chǔ)空間的管理 一. 空閑表法 1. 數(shù)據(jù)結(jié)構(gòu)： 序號(hào) 第一空閑盤塊號(hào) 空閑盤塊數(shù) 1 2 4 2 9 3 3 15 5 4 — — 2. 分配與回收： 連續(xù)分配方式，采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等 第四章 存儲(chǔ)器管理 二 . 空閑鏈表法 (1) 空閑盤塊鏈 6 5 7 8 10 300 310 ? … 5 6 7 8 299 300 310 （ 2）空閑盤區(qū)鏈 分區(qū)序號(hào) 、 起始?jí)K號(hào) 、盤塊數(shù)等 第四章 存儲(chǔ)器管理 三 . 位示圖法 ： 第四章 存儲(chǔ)器管理 (1) 順序掃描位示圖 ， 從中找出一個(gè)或一組其值為 “ 0”的二進(jìn)制位 (“0”表示空閑時(shí) )。 (2) 將所找到的