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