【文章內容簡介】 J的相對路徑名僅是 J本身 。 這樣 ， 把從當前目錄開始直到數(shù)據(jù)文件為止所構成的路徑名 ， 稱為相對路徑名 (relative path name)；而把從樹根開始的路徑名稱為絕對路徑名 (absolute path name)。 53 4. 增加和刪除目錄 (1) 不刪除非空目錄 。 當目錄 (文件 )不空時 ， 不能將其刪除 ， 而為了刪除一個非空目錄 ， 必須先刪除目錄中的所有文件 ， 使之先成為空目錄 ， 后再予以刪除 。 如果目錄中還包含有子目錄 ， 還必須采取遞歸調用方式來將其刪除 ， 在 MSDOS中就是采用這種刪除方式 。 (2) 可刪除非空目錄 。 當要刪除一目錄時 ， 如果在該目錄中還包含有文件 ， 則目錄中的所有文件和子目錄也同時被刪除 。 54 目錄查詢技術 1. 線性檢索法 圖 619 查找 /usr/ast/mbox的步驟 55 2. Hash方法 一種處理此 “ 沖突 ” (1) 在利用 Hash法索引查找目錄時 ， 如果目錄表中相應的目錄項是空的 ， 則表示系統(tǒng)中并無指定文件 。 (2) 如果目錄項中的文件名與指定文件名相匹配 ， 則表示該目錄項正是所要尋找的文件所對應的目錄項 ， 故而可從中找到該文件所在的物理地址 。 (3) 如果在目錄表的相應目錄項中的文件名與指定文件名并不匹配 ， 則表示發(fā)生了 “ 沖突 ” ， 此時須將其 Hash值再加上一個常數(shù) (該常數(shù)應與目錄的長度值互質 )， 形成新的索引值 ， 再返回到第一步重新開始查找 。 56 空閑表法和空閑鏈表法 1. 空閑表法 圖 620 空閑盤塊表 序號 第一空閑盤塊號 空閑盤塊數(shù) 1 2 4 2 9 3 3 15 5 4 — — 文件存儲空間的管理 57 (2) 存儲空間的分配與回收 。 空閑盤區(qū)的分配與內存的動態(tài)分配類似 ， 同樣是采用首次適應算法 、 循環(huán)首次適應算法等 。 例如 ， 在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時 ， 先順序地檢索空閑表的各表項 ， 直至找到第一個其大小能滿足要求的空閑區(qū) ， 再將該盤區(qū)分配給用戶 (進程 )， 同時修改空閑表 。 系統(tǒng)在對用戶所釋放的存儲空間進行回收時 ， 也采取類似于內存回收的方法 ， 即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接 ， 對相鄰接者應予以合并 。 58 2. 空閑鏈表法 (1) 空閑盤塊鏈。 (2) 空閑盤區(qū)鏈 59 位示圖法 1. 位示圖 圖 621 位示圖 60 2. 盤塊的分配 (1) 順序掃描位示圖 ， 從中找出一個或一組其值為 “ 0”的二進制位 (“0”表示空閑時 )。 (2) 將所找到的一個或一組二進制位， 轉換成與之相應的盤塊號。假定找到的其值為 “ 0”的二進制位，位于位示的第 i行、第 j列，則其相應的盤塊號應按下式計算： b=n(i1)+j 式中 ， n代表每行的位數(shù) 。 (3) 修改位示圖， 令 map［ i,j］ =1。 61 3. 盤塊的回收 (1) 將回收盤塊的盤塊號轉換成位示圖中的行號和列號 。 i=(b1)DIV n+1 j=(b1)MOD n+1 (2) 修改位示圖。 令 map ［ i,j］ =1。 62 成組鏈接法 1. 1 0 04 0 03 9 93 0 13 0 01 0 03 0 02 9 9…2 0 22 0 12 9 9…1 0 04 0 03 9 9…2 0 1 3 0 1………9907 9 9 97 9 0 17 9 0 07 8 9 9…7 8 0 17 9 9 9…7 9 0 1空 閑 盤 塊 號棧S . f r e e019899圖 622 空閑盤塊的成組鏈接法 63 2. 當系統(tǒng)要為用戶分配文件所需的盤塊時 ， 須調用盤塊分配過程來完成 。 該過程首先檢查空閑盤塊號棧是否上鎖 ， 如未上鎖 ， 便從棧頂取出一空閑盤塊號 ， 將與之對應的盤塊分配給用戶 ， 然后將棧頂指針下移一格 。 若該盤塊號已是棧底 ， 即 (0)， 這是當前棧中最后一個可分配的盤塊號 。 由于在該盤塊號所對應的盤塊中記有下一組可用的盤塊號 ， 因此 ， 須調用磁盤讀過程 ， 將棧底盤塊號所對應盤塊的內容讀入棧中 ， 作為新的盤塊號棧的內容 ， 并把原棧底對應的盤塊分配出去 (其中的有用數(shù)據(jù)已讀入棧中 )。 然后 ， 再分配一相應的緩沖區(qū) (作為該盤塊的緩沖區(qū) )。 最后 ， 把棧中的空閑盤塊數(shù)減 1并返回 。 64 在系統(tǒng)回收空閑盤塊時 ， 須調用盤塊回收過程進行回收 。 它是將回收盤塊的盤塊號記入空閑盤塊號棧的頂部 ，并執(zhí)行空閑盤塊數(shù)加 1操作 。 當棧中空閑盤塊號數(shù)目已達100時 ， 表示棧已滿 ， 便將現(xiàn)有棧中的 100個盤塊號 ， 記入新回收的盤塊中 ， 再將其盤塊號作為新棧底 。 65 文件卷 ? 磁盤分區(qū) (partition)：通常把一個 物理磁盤 的存儲空間劃分為幾個相互獨立的部分，稱為 分區(qū) 。一個分區(qū)的參數(shù)包括： 磁盤參數(shù) （如每道扇區(qū)數(shù)和磁頭數(shù)）， 分區(qū)的起始和結束柱面 等。 ? 文件卷 (volume)：或稱為 邏輯驅動器 (logical drive)。在同一個文件卷中 使用同一份管理數(shù)據(jù) 進行文件 分配和外存空閑空間管理 ，而在不同的文件卷中使用相互獨立的管理數(shù)據(jù)。 – 一個文件不能分散存放在多個文件卷中 ，其最大長度不超過所在文件卷的容量。 – 通常一個 文件卷只能存放在一個物理外設上 （并不絕對），如一個磁盤分區(qū)或一盤磁帶。 66 ? 格式化 (format)：在一個文件卷上 建立文件系統(tǒng) ，即： – 建立并初始化 用于進行文件分配和外存空閑空間管理的 管理數(shù)據(jù) 。 – 通常，進行格式化操作使得一個文件卷上 原有的文件都被刪除 。 ? 擴展文件卷集 (extended volume set)：一個文件卷由一個或幾個磁盤上的 多個磁盤分區(qū) 依次連接組成?？梢匀菁{長度大于磁盤分區(qū)容量的文件。 – 實例： Windows NT中的擴展文件卷集。 67 ? 磁盤交叉存儲 (disk interleaving)： 將一個文件卷的存儲塊依次分散在多個磁盤上 。如 4個磁盤，則磁盤 0上是文件卷塊 0, 4, 8, … ，磁盤 1上是文件卷塊 1, 5, 9, … 。 – 優(yōu)點： 提高 I/O效率 。如果需要訪問一個文件的多個存儲塊，而它們分散在多個磁盤上，則可以 并發(fā)地向多個磁盤發(fā)出請求 ，并可在此基礎上提供文件系統(tǒng)的 容錯功能 。關鍵： 磁盤訪問時間大部分由旋轉等待時間組成 。 – 需要相應硬件設備：如多個硬盤連接在同一個或不同的SCSI接口上，或者兩個硬盤連接在一個或不同的 IDE接口上（兩個硬盤連接在同一個 IDE接口上，不能提高 I/O效率） – 實例： Windows NT中的 條帶卷 (stripe set)，每個文件卷塊的大小是 64KB。 – 類似例子：在虛擬存儲器中建立 多個交換區(qū) ，分散在多個磁盤上 68 D i sk 0D i sk 1D i sk 2D i sk 3C y cl i ng W ai tD at a T r ans f ertR eques t C om pl et e多個磁盤上的交換區(qū)訪問 69 AABB B BB CCCCC根目錄? C CC圖 623 包含有共享文件的文件系統(tǒng) 文件共享與文件保護 圖 624 基于索引結點的共享方式 W a n g 用戶文 件目錄T e s t rL e e 用戶文 件目錄T e s t rc o u n t ＝ 2文件物 理地址索引結 點T e s t圖 625 進程 B鏈接前后的情況 C 的目錄o w n e r ＝ cc o u n t ＝ 1鏈 接 前C 的目錄o w n e r ＝ cc o u n t ＝ 2建 立 鏈 接 后B 的目錄 B 的目錄o w n e r ＝ cc o u n t ＝ 1擁 有 者 刪 除 文 件 后72 利用符號鏈實現(xiàn)文件共享 在利用符號鏈方式實現(xiàn)文件共享時 ， 只是文件主才擁有指向其索引結點的指針；而共享該文件的其他用戶 ， 則只有該文件的路徑名 ， 并不擁有指向其索引結點的指針 。 這樣 ， 也就不會發(fā)生在文件主刪除一共享文件后留下一懸空指針的情況 。 當文件的擁有者把一個共享文件刪除后 ， 其他用戶試圖通過符號鏈去訪問一個已被刪除的共享文件時 ， 會因系統(tǒng)找不到該文件而使訪問失敗 ， 于是再將符號鏈刪除 ， 此時不會產生任何影響 。 73 UNIX 文件別名的實現(xiàn) ? 基于索引結點 ? 基于符號鏈接 提供文件共享的方法有兩種：各用戶通過唯一的共享文件的 路徑名 訪問共享文件（該方法的訪問 速度慢 ，適用于不經(jīng)常訪問的文件共享），或利用多個目錄中的不同文件名來描述同一共享文件（即 文件別名 ，該方法的訪問 速度快 ，但會 影響文件系統(tǒng)的樹狀結構 ，適用于經(jīng)常訪問的文件共享，同時 存在一定的限制 ）。文件別名的實現(xiàn)方法有以下兩種： 74 1. 基于索引結點 (index node)的文件別名 ? UNIX舉例： ln source target 。 rm source則該文件還存在，文件名為 target； ? 限制：不能跨越不同文件卷；通常不適用于目錄（在UNIX中只對超級用戶允許），否則由樹狀變?yōu)榫W(wǎng)狀。 也稱為硬鏈接（ hard link）；基于改進的多級目錄結構， 將目錄內容分為兩部分：文件名和索引結點 。前者包括文件名和索引結點編號，后者包括文件的其他內容（包括屬主和訪問權限）。通過 多個文件名鏈接(link)到同一個索引結點 ，可建立同一個文件的 多個彼此平等的別名 。別名的數(shù)目記錄在索引結點的鏈接計數(shù)中，若其減至 0，則文件被刪除。 75 2. 基于符號鏈接 (symbolic link, shortcut)的文件別名 ? UNIX舉例： ln s a b 。 rm a則文件 a不存在， b能被控制但無法訪問。若 a是目錄， ln s /user/a /tmp/b則 cd /tmp/b 。 cd ..是進入目錄/user而不是 /tmp； ? 缺點：空間和時間開銷更大。如果設置不當，上下級目錄關系可能會形成環(huán)狀