【文章內(nèi)容簡(jiǎn)介】 實(shí)體之間存在著一一對(duì)應(yīng)關(guān)系 ， 即它不允許兩個(gè)文件具有相同的名字 。 在多道程序系統(tǒng)中 ， 尤其是多用戶的分時(shí)系統(tǒng)中 ， 重名是很難避免的 ， 這就很難準(zhǔn)確地找到用戶所需要的文件 。 顯然 ， 如果由人工來(lái)管理文件名注冊(cè) ， 以避免命名沖突 ， 則是很麻煩的 。 （ 4）保密性差。 （ 5）不便于實(shí)現(xiàn)文件共享 。 第五章 文件系統(tǒng) 42 二級(jí)目錄 1. 思想 各個(gè)用戶使用各自的名空間，用戶的名空間構(gòu)成了所謂的用戶文件目錄表 (UFD)。管理這些用戶目錄表的總文件目錄稱為主目錄表（ MFD）。主目錄表中每個(gè)表目給出了用戶目錄的名字、目錄大小及其所在的物理位置等。 2. 特點(diǎn) （ 1）提高了檢索目錄的速度 。 （ 2）在不同的用戶目錄中， 可以使用相同的文件名。 （ 3）不同用戶還可使用不同的文件名來(lái)訪問(wèn)系統(tǒng)中的同一個(gè)共享文件 。 第五章 文件系統(tǒng) 43 二級(jí)目錄結(jié)構(gòu)圖 用戶名W a n gZ h a n gG a o指向子 目錄指針W a n g 用 戶 目 錄A l p h aT e s tA l p h aT e s tR e p o r tT e s tZ h a n g 用 戶 目 錄R e p o r tT e s tG a o 用 戶 目 錄B e t aD e v i c eM i s xB e t aD e v i c eM i s x第五章 文件系統(tǒng) 44 多級(jí)目錄 1. 多級(jí)樹(shù)型目錄 思想：文件目錄的第一級(jí)系統(tǒng)目錄為樹(shù)的根結(jié)點(diǎn) ， 定義為根目錄 ， 第 2級(jí)和以下各級(jí)目錄均為樹(shù)的分支結(jié)點(diǎn)/枝結(jié)點(diǎn) （ 非終結(jié)點(diǎn) ） ， 均定義為子目錄 ， 只有樹(shù)的葉子結(jié)點(diǎn) （ 終結(jié)點(diǎn) ） 才為文件 。 b i n l i b u s e rxu lu gum a i l b o x…p r o g . c… …a . e x eu s rd e ve t c…l i b…b i n U N I X t m p i n c l u d es t d i o . h m a t h . h／ 根…第五章 文件系統(tǒng) 45 在根目錄之下 ， lib etc dev tmp usr bin UNIX UNIX子目錄 (包括操作系統(tǒng)核心程序 ) include 根目錄和子目錄都是文件 ，稱為 目錄文件 。 第五章 文件系統(tǒng) 46 2. 在樹(shù)型目錄結(jié)構(gòu)中 ， 文件名有兩種表示方法： 絕對(duì)路徑名和 相對(duì)路徑名 。 從根開(kāi)始到達(dá)文件的路徑 ， 稱為 絕對(duì)路徑 。 例如 ， 文件 /usr/user/u/c/ 它表示根目錄中有子目錄 usr， usr中有子目錄 user， 在 user子目錄下有一子目錄 lu， lu下的一個(gè)文件是 。 絕對(duì)路徑名總是從根目錄開(kāi)始 ， 并且是唯一的 。 在 UNIX中 ， 路徑各部分之間用 “ /” 分隔 。 在 MSDOS中 ， 其分隔符是 “ ＼ ” ，不管使用什么分隔符 ， 如果路徑名的第一個(gè)字符是分隔符 ，那么這個(gè)路徑就是絕對(duì)路徑 。 第五章 文件系統(tǒng) 47 另一種文件名表示法稱為 相對(duì)路徑名 。 它常和工作目錄(也稱 當(dāng)前目錄 )的概念一起使用 。 用戶可以指定一個(gè)目錄作為當(dāng)前的工作目錄 。 這時(shí) ， 所有的路徑名 ， 如果不是從根目錄開(kāi)始 ， 則都是相對(duì)于工作目錄的 。 例如 ， 如果當(dāng)前的工作目錄是 /usr/user/lu， 則絕對(duì)路徑名為 /usr/user/lu/簡(jiǎn)單地用 。 大多數(shù)支持樹(shù)型結(jié)構(gòu)的操作系統(tǒng) ， 在每個(gè)目錄中有兩個(gè)特殊的目錄項(xiàng) “ ” 和 “ ” ， “ ” 指當(dāng)前目錄 ， “ ”指 其父目錄 。 在圖 中 ， 若某進(jìn)程的工作目錄為 /usr/user/lu， 它可以使用 “ ” 沿樹(shù)向上到達(dá)其父目錄 /user。 該進(jìn)程使用路徑名 /xu/mailbox 訪問(wèn)子目錄 xu下的文件 mailbox。 第五章 文件系統(tǒng) 48 文件目錄項(xiàng)的組織 1. CP/M中的目錄項(xiàng) 圖 CP/M目錄項(xiàng)的內(nèi)容 dr 文件名 類型 ex cr 磁盤塊 號(hào)0 1 8 9 11 12 13 14 15 16 31盤 驅(qū) 動(dòng) 器 號(hào)范圍 塊數(shù)第五章 文件系統(tǒng) 49 2. MSDOS中的目錄項(xiàng) 文 件 名0 7類 型8 A屬性B保留C F保留 時(shí)間 日期 首簇號(hào) 文件長(zhǎng) 度10 15 16 17 18 19 1A 1B 1C 1F圖 MSDOS的目錄項(xiàng) 第五章 文件系統(tǒng) 50 3. UNIX中的目錄項(xiàng) UNIX中使用的目錄結(jié)構(gòu)非常簡(jiǎn)單， 每個(gè)目錄項(xiàng)僅包含一個(gè)文件名及其 i節(jié)點(diǎn)號(hào)， 即 第五章 文件系統(tǒng) 51 圖 查找 /usr/ast/mbox的過(guò)程 1 根目錄1 4 b i n7 d e v14 l i b9 e t c6 u s r8 t m p從根目 錄查/ u s r得到 i 節(jié)點(diǎn)6…1 3 2i 節(jié)點(diǎn) 6i 節(jié)點(diǎn)6 指出/ u s r 在塊 1 3 2 中6 1 19 d i c k30 e r i k51 j i m26 a s t45 b a l71 xu查/ u s r / a s t得到 i 節(jié)點(diǎn) 26目錄/ u s r塊 1 3 2 存放…4 0 6i 節(jié)點(diǎn) 26i 節(jié)點(diǎn) 26 指出/ u s r / a s t 在4 06 塊中26 6 64 g r a n t s92 b o o k s60 m b o x81 m i n i x17 s r c24 g i r s目錄/ u s r / a s t塊 4 0 6查/ u s r / a s t / m b o x得到 i 節(jié)點(diǎn) 60…1 4 71 3 51 2 61 3 8…i 節(jié)點(diǎn) 60i 節(jié)點(diǎn) 60 中指出 / u s r/ a s t / m b o x所 占 用 的 塊第五章 文件系統(tǒng) 52 文件存儲(chǔ)空間的管理 空白文件目錄 1. 思想 將盤上一個(gè)個(gè)連續(xù)未分配的區(qū)域作為一個(gè)空白文件目錄登記在一張表中。 表 5 3 空白文件目錄例 序 號(hào) 第一個(gè)空白塊號(hào) 空白塊個(gè)數(shù) 物理塊號(hào) 1 2 3 4 2 9 15 — 4 3 5 — （ 2， 3， 4， 5） （ 9， 10， 11） （ 15， 16， 17，18， 19） — 第五章 文件系統(tǒng) 53 空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。 分配 ：當(dāng)某用戶提出請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)依次檢索空白文件目錄的各表項(xiàng)， 直至找到一個(gè)滿足要求的空白文件為止。再將該盤區(qū)分配給用戶 (進(jìn)程 )，同時(shí)修改空白文件目錄表。 釋放 ：系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法， 如果被釋放的物理塊號(hào)與某一目錄項(xiàng)中的物理塊號(hào)相鄰，則還要進(jìn)行合并空白文件。 Ⅰ 小的連續(xù)區(qū)過(guò)多時(shí)，表目大，查找慢。 Ⅱ 釋放時(shí)可能會(huì)出現(xiàn)插入現(xiàn)象。 Ⅲ 僅使用于連續(xù)結(jié)構(gòu)。 第五章 文件系統(tǒng) 54 空白塊鏈法 將所有空白塊用鏈接指針或索引結(jié)構(gòu)把它們組織成一個(gè)空白文件 。 采用鏈接結(jié)構(gòu)時(shí) ， 釋放和分配的空白塊都可以在鏈?zhǔn)滋庍M(jìn)行 ， 其主要問(wèn)題是要修改幾個(gè)有關(guān)的鏈接字 。 這種方法只要求在主存中保存一個(gè)指針 ， 令它指向第一個(gè)空白塊 。 當(dāng)修改鏈接字時(shí) ， 要讀幾個(gè)盤塊 ， 工作量較大 。 如果采用索引表 ， 則只需修改索引表中幾個(gè)有關(guān)項(xiàng) ， 但是索引表占用的存儲(chǔ)空間較大 ， 對(duì)系統(tǒng)來(lái)說(shuō)也是負(fù)擔(dān) 。 (1)單塊鏈 (2)成組塊鏈 若干塊形成一個(gè)組，組與組之間鏈接。 第五章 文件系統(tǒng) 55 第五章 文件系統(tǒng) 56 （ 1）分配一個(gè)空閑塊 查 L單元內(nèi)容（空閑塊數(shù)）： 當(dāng)空閑塊數(shù) 1 i : ＝ L＋空閑塊數(shù)； 從 i單元得到一空閑塊號(hào)； 把該塊分配給申請(qǐng)者； 空閑塊數(shù)減 1。 當(dāng)空閑塊數(shù)＝ 1 取出 L＋ 1單元內(nèi)容（一組的第一塊塊號(hào)或 0）； 其值＝ 0 無(wú)空閑塊，申請(qǐng)者等待； 不等于零把該塊內(nèi)容復(fù)制到專用塊； 該塊分配給申請(qǐng)者； 把專用塊內(nèi)容讀到主存 L開(kāi)始的區(qū)域。 第五章 文件系統(tǒng) 57 （ 2）歸還一塊 查 L單元的空閑塊數(shù)； 當(dāng)空閑塊數(shù) 100， 空閑塊數(shù)加 1； j : ＝ L＋空閑塊數(shù)； 歸還塊號(hào)填入 j單元。 當(dāng)空閑塊數(shù)＝ 100 ，把主存中登記的信息寫入歸還塊中； 把歸還塊號(hào)填入 L＋ 1單元； 將 L單元置成 1。 當(dāng)設(shè)備安裝完畢，系統(tǒng)就將專用塊復(fù)制到主存中。專用塊指示的空閑塊分配完后若再有申請(qǐng)要求時(shí)，就把下一組空閑塊及盤物理塊號(hào)復(fù)制到專用塊中重復(fù)進(jìn)行。搜索到全 0塊時(shí)，系統(tǒng)應(yīng)向操作員發(fā)出警告，表明空閑塊已用完。注意：開(kāi)始時(shí)空閑塊是按順序排列的，只要符合分組及組間連接原則，空閑塊可按任意次序排列。事實(shí)上，經(jīng)過(guò)若干次分配、釋放操作后，空閑塊物理塊號(hào)必定不能按序排列了。 第五章 文件系統(tǒng) 58 位示圖 (Bit Map) 用一串二進(jìn)制位反映磁盤空間中分配使用情況 , 每個(gè)物理塊對(duì)應(yīng)一位 , 分配物理塊為 1，否則為 0。 申請(qǐng)物理塊時(shí)，可以在位示圖中查找為 0的位，返回對(duì)應(yīng)物理塊號(hào)。歸還時(shí)，將對(duì)應(yīng)位轉(zhuǎn)置 0。 位示圖描述能力強(qiáng)，適合各種物理結(jié)構(gòu)。 第五章 文件系統(tǒng) 59 圖 位示圖例 0 0 0 1 1 0 0 10 0 1 1 1 0 0 00 0 0 0 0 0 1 10 0 1 1 1 1 1 10 1 2 3 4 5 6 7字節(jié) 1字節(jié) 2字節(jié) 3字節(jié) n位… …例：一個(gè)盤組共 100個(gè)柱面（ 0～ 99），每個(gè)柱面有 8個(gè)磁道（ 0～ 7），每個(gè)磁道上 4個(gè)扇區(qū)（ 0～ 3），用 32位的字構(gòu)成位示圖，需要多少字？ 第五章 文件系統(tǒng) 60 計(jì)算公式： 已知字號(hào) i，位號(hào) j 塊號(hào)＝ i 字長(zhǎng)＋ j 已知塊號(hào)： 字號(hào)＝塊號(hào) div 字長(zhǎng) 位號(hào)＝塊號(hào) mod 字長(zhǎng) 已知塊號(hào)，則磁盤地址：