1、第七章 文件系統7.1 引言7.2 文件的組織7.3 文件目錄7.4 文件和目錄的使用7.5 文件共享7.6 外存存儲空間管理7.7 文件系統舉例 信息是計算機系統中的重要資源。操作系統中的一個重要組成部分，文件系統，就負責信息的組織、存儲和訪問。 文件系統的功能就是提供高效、快速和方便的信息存儲和訪問功能。本章的主要內容就是信息的組織。7.1 引言7.1.1 文件管理的目的7.1.2 文件系統的基本概念7.1.3 文件系統的結構和功能元素返回7.1.1 文件管理的目的 方便的文件訪問和控制：以符號名稱作為文件標識，便于用戶使用； 并發文件訪問和控制：在多道程系統中支持對文件的并發訪問和控制；

2、 統一的用戶接口：在不同設備上提供同樣的接口，方便用戶操作和編程； 多種文件訪問權限：在多用戶系統中的不同用戶對同一文件會有不同的訪問權限； 優化性能：存儲效率、檢索性能、讀寫性能； 差錯恢復：能夠驗證文件的正確性，并具有一定的差錯恢復能力；返回7.1.2 文件系統的基本概念 文件體：文件本身的信息； 文件說明：文件存儲和管理信息；如：文件名、文件內部標識、文件存儲地址、訪問權限、訪問時間等；返回1. 文件文件是具有符號名的數據項的集合。文件名是文件的標識符號。文件包括兩部分：2. 文件系統文件系統是操作系統中管理文件的機構，提供文件存儲和訪問功能。3. 目錄目錄是由文件說明索引組成的用于文件

3、檢索的特殊文件。7.1.3 文件系統的結構和功能元素返回1. 文件系統的結構應用程序多種文件類型（劃分記錄，順序或索引等）基本 I/O 管理（I/O 緩存和調度，性能優化）物理 I/O（基本文件系統）外部存儲器文件系統2. 文件管理的服務功能元素 文件訪問：文件的創建、打開和關閉，文件的讀寫； 目錄管理：用于文件訪問和控制的信息，不包括文件內容 文件結構管理：劃分記錄，順序，索引 訪問控制：并發訪問和用戶權限 限額(quota)：限制每個用戶能夠建立的文件數目、占用外存空間大小等 審計(auditing)：記錄對指定文件的使用信息（如訪問時間和用戶等），保存在日志中(文件系統向上層用戶提供的服

4、務)3. 文件系統的實現功能元素 文件的分塊存儲：與外存的存儲塊相配合 I/O緩沖和調度：性能優化 文件定位：在外存上查找文件的各個存儲塊 外存存儲空間管理：如分配和釋放。主要針對可改寫的外存如磁盤。 外存設備訪問和控制：包括由設備驅動程序支持的各種基本文件系統如硬盤，軟盤，CD ROM等(文件系統要實現的功能模塊)7.2 文件的組織(file organization)7.2.1文件的組織7.2.2 文件的組織類型返回文件組織討論文件的內部邏輯結構，主要考慮因素是文件存儲性能和訪問性能。7.2.1文件的組織 文件邏輯結構的設計要求： 訪問性能：便于檢索；便于修改 存儲性能：向物理存儲轉換方便

5、，節省空間 文件的不同組織層次：域、記錄、文件返回文件的組織是指從用戶觀點出發討論文件內部的邏輯結構(logical structure)或用戶訪問模式；它可以獨立于在外存上的物理存儲。7.2.2 文件的組織類型返回1. 無結構文件文件體為字節流，不劃分記錄，順序訪問，每次讀寫訪問可以指定任意數據長度。當前操作系統中常用的文件組織。2. 累積文件(pile)文件體為無結構記錄序列，通過特定分隔符來劃分記錄，各記錄大小和組成可變。新記錄總是添加到文件末尾。如日志log，或電子郵件的郵箱文件(mailbox)。檢索必須從頭開始。3. 順序文件(sequential file)文件體為大小相同的排序

6、記錄序列。它由一個主文件和一個臨時文件組成。記錄大小相同，按某個關鍵字域(key field)排序，存放在主文件(master file)中。新記錄暫時保存在日志或事務文件(log file or transaction file)中，定期歸并入主文件。4. 索引順序文件(indexed-sequential file)在索引文件中，可將關鍵字域中的取值劃分若干個區間（如AZ可以劃分為A到Z共26個區間），每個區間對應一個索引項，后者指向該區間的開頭記錄。新記錄暫時保存在溢出文件中，定期歸并入主文件。通過劃分層次，在記錄數量較大時，比順序文件大大縮短檢索時間。順序文件是N/2(這時可使用折半查

7、找)，而索引順序文件（一級索引）是i/2 + N/(2*i)，其中i為索引長度。索引還可以是多級的。如：有1000,000條記錄的順序文件的平均檢索長度為500,000，而在添加一個有1000條索引項的索引文件后，平均檢索長度為1000。在順序文件（主文件main file）的基礎上，另外建立索引(index)和溢出文件(overflow file)。這樣做的目的是加快順序文件的檢索速度。關鍵字邏輯地址姓名其它屬性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件順序文件索引順序文件5. 索引文件(indexed file)記錄大小不必相同，

8、不必排序，存放在主文件(primary file)中。索引文件與索引順序文件的區別在于主文件不排序。另外建立索引，每個索引項指向一個記錄，索引項按照記錄中的某個關鍵字域排序。對同一主文件，可以針對不同的關鍵字域相應建立多個索引。索引文件的記錄項通常較小，查找速度快，便于隨機訪問(random access)。6. 哈希文件或直接文件(hashed file or direct file)記錄大小相同。由主文件和溢出文件組成。記錄位置由哈希函數確定。檢索時給出記錄編號，通過哈希函數計算出該記錄在文件中的相對位置。訪問速度快，但在主文件中有空閑空間。7.3 文件目錄7.3.1 目錄內容7.3.2

9、目錄結構類型7.3.3 文件別名的實現返回目錄是由文件說明索引組成的用于文件檢索的特殊文件。文件目錄的內容主要是文件訪問的控制信息（不包括文件內容）。7.3.1 目錄內容 文件名：字符串，通常在不同系統中允許不同的最大長度。可以修改。有些系統允許同一個文件有多個別名(alias)； 別名的數目； 文件類型：可有多種不同的劃分方法，如： 有無結構（記錄文件，流式文件） 內容（二進制，文本） 用途（源代碼，目標代碼，可執行文件，數據） 屬性attribute（如系統，隱含等） 文件組織（如順序，索引等）返回目錄的內容是文件屬性信息(properties)，其中的一部分是用戶可獲取的。1. 基本信息

10、2. 地址信息 存放位置：包括哪個設備或文件卷volume，以及各個存儲塊位置； 文件長度（當前和上限）：以字節、字或存儲塊為單位。可以通過寫入或創建、打開、關閉等操作而變化。3. 訪問控制信息 文件所有者（屬主）：通常是創建文件的用戶，或者改變已有文件的屬主； 訪問權限（控制各用戶可使用的訪問方式）：如讀、寫、執行、刪除等；4. 使用信息 創建時間 最后一次讀訪問的時間和用戶 最后一次寫訪問的時間和用戶7.3.2 目錄結構類型 一級目錄：整個目錄組織是一個線性結構，系統中的所有文件都建立在一張目錄表中。它主要用于單用戶操作系統。它具有如下的特點： 結構簡單； 文件多時，目錄檢索時間長； 有命

11、名沖突：如重名(多個文件有相同的文件名) 或別名(一個文件有多個不同的文件名) 二級目錄：在根目錄下，每個用戶對應一個目錄（第二級目錄）；在用戶目錄下是該用戶的文件，而不再有下級目錄。適用于多用戶系統，各用戶可有自己的專用目錄。返回目錄結構討論目錄的組織結構，設計目標是檢索效率。 多級目錄：或稱為樹狀目錄(tree-like)。在文件數目較多時，便于系統和用戶將文件分散管理。適用于較大的文件系統管理。目錄級別太多時，會增加路徑檢索時間。 目錄名：可以修改。 目錄樹：中間結點是目錄，葉子結點是目錄或文件。 目錄的上下級關系：當前目錄(current directory, working dire

12、ctory)、父目錄(parent directory)、子目錄(subdirectory)、根目錄(root directory)等； 路徑(path)：每個目錄或文件，可以由根目錄開始依次經由的各級目錄名，加上最終的目錄名或文件名來表示；ABC根目錄EPABDFEDBGAEHIJKABCDELMNA多級目錄組織 改進的多級目錄：為了提高目錄檢索速度，可把目錄中的文件說明（文件描述符）信息分成兩個部分： 符號文件目錄：由文件名和文件內部標識組成的樹狀結構，按文件名排序； 基本文件目錄（索引節點目錄）：由其余文件說明信息組成的線性結構，按文件內部標識排序；1內部名ID其它信息地址2345678

13、91011基本文件目錄(ID1)ID4ID5ID7ID9ID10ID11文件名ID3Tu-Lide8Tu-Qi根目錄(ID2)文件名ID7Products5RoomsTu-Lide的目錄(ID3)4Software6Tools文件名IDTools的目錄(ID6)11SA-SD10Univer文件名ID10Univer5ClassroomTu-Lide的目錄(ID3)9Tools基本文件目錄Tu-Lide的目錄(ID3)ProductsRoomsSoftwareTools根目錄(ID2)Tu-LideTu-QiTu-Lide的目錄(ID8)UniverClassroomToolsTools的目錄

14、(ID6)SA-SDUniverID4ID5ID7ID9ID10ID11符號文件目錄的層次結構7.3.3 文件別名的實現 基于索引結點 基于符號鏈接返回提供文件共享的方法有兩種：各用戶通過唯一的共享文件的路徑名訪問共享文件（該方法的訪問速度慢，適用于不經常訪問的文件共享），或利用多個目錄中的不同文件名來描述同一共享文件（即文件別名，該方法的訪問速度快，但會影響文件系統的樹狀結構，適用于經常訪問的文件共享，同時存在一定的限制）。文件別名的實現方法有以下兩種：1. 基于索引結點(index node)的文件別名UNIX舉例：ln source target ; rm source則該文件還存在，文

15、件名為target；限制：不能跨越不同文件卷；通常不適用于目錄（在UNIX中只對超級用戶允許），否則由樹狀變為網狀。也稱為硬鏈接（hard link）；基于改進的多級目錄結構，將目錄內容分為兩部分：文件名和索引結點。前者包括文件名和索引結點編號，后者包括文件的其他內容（包括屬主和訪問權限）。通過多個文件名鏈接(link)到同一個索引結點，可建立同一個文件的多個彼此平等的別名。別名的數目記錄在索引結點的鏈接計數中，若其減至0，則文件被刪除。2. 基于符號鏈接(symbolic link, shortcut)的文件別名 UNIX舉例：ln -s a b ; rm a則文件a不存在，b能被控制但無法

16、訪問。若a是目錄，ln -s /user/a /tmp/b則cd /tmp/b ; cd .是進入目錄/user而不是/tmp； 缺點：空間和時間開銷更大。如果設置不當，上下級目錄關系可能會形成環狀。它是一種特殊類型的文件，其內容是到另一個目錄或文件路徑的鏈接。建立符號鏈接文件，并不影響原文件，實際上它們各是一個文件。可以建立任意的別名關系，甚至原文件是在其他計算機上。7.4 文件和目錄的使用7.4.1 文件訪問7.4.2 文件控制7.4.3 目錄管理7.4.4 偽文件(pseudo file)返回這一部分討論操作系統提供的與文件系統相關的API。7.4.1 文件訪問 打開open：為文件讀寫

17、所進行的準備。給出文件路徑，獲得文件句柄(file handle)，或文件描述符(file descriptor)。需將該文件的目錄項讀入到內存中。 關閉close：釋放文件描述符，把該文件在內存緩沖區的內容更新到外存上。 復制文件句柄dup：用于子進程與父進程間的文件共享，復制前后的文件句柄有相同的文件名、文件指針和訪問權限；返回文件訪問是指圍繞文件內容讀寫進行的文件操作。 讀read、寫write和移動文件讀寫指針lseek：系統為每個打開文件維護一個讀寫指針(read-write pointer)，它是相對于文件開頭的偏移地址(offset)。讀寫指針指向每次文件讀寫的開始位置，在每次讀

18、寫完成后，讀寫指針按照讀寫的數據量自動后移相應數值。 執行exec：執行一個可執行文件； 修改文件的訪問模式（fcntl和ioctl）：提供對打開文件的控制，如：文件句柄復制、讀寫文件句柄標志、讀寫文件狀態標志、文件鎖定控制、流（stream）的控制；7.4.2 文件控制 創建（creat和open）：給出文件路徑，獲得新文件的文件句柄； 刪除unlink：對于symbolic link和hard link，刪除效果是不同的； 獲取文件屬性（stat和fstat）：stat的參數為文件名，fstat的參數為文件句柄； 修改文件名rename； 修改文件屬主chown，修改訪問權限chmod：與

19、相應系統命令類似； 文件別名控制：創建symlink或link，讀取鏈接路徑readlink；返回文件控制是指圍繞文件屬性控制進行的文件操作。7.4.3 目錄管理 進行文件訪問和控制時，由操作系統自動更新目錄內容 目錄創建mkdir，刪除rmdir，修改目錄名rename。只適用于超級用戶：mknod（建立文件目錄項）和unlink（刪除目錄項） 修改當前目錄chdir；返回目錄管理是指目錄訪問和目錄屬性控制。7.4.4 偽文件(pseudo file) 特點 內容并不保存在外存上，而是在其他外部設備上或內存里 隨文件類型的不同，適用于某些文件訪問和控制的系統調用，如：open, read,

20、write, close, chmod, chown。 創建時使用特定的系統調用，如：創建管道pipe，創建管套socket，創建設備文件mknod 類型 設備：字符設備或塊設備，可以直接訪問設備中的字節數據或數據塊。如終端、硬盤、內存等。在UNIX中稱為特殊文件(special file)。 進程間通信：本計算機或通過網絡。如：管道，管套等。返回偽文件是指具有文件某些特征的系統資源或設備，它們的訪問和控制方式與文件類似。7.5 文件共享7.5.1 文件的訪問權限7.5.2 文件的并發訪問返回7.5.1 文件的訪問權限 文件訪問類型： 讀read：可讀出文件內容； 寫write（修改updat

21、e或添加append）：可把數據寫入文件； 執行execute：可由系統讀出文件內容，作為代碼執行； 刪除delete：可刪除文件； 修改訪問權限change protection：修改文件屬主或訪問權限返回設置文件訪問權限的目的是為了在多個用戶間提供有效的文件共享機制； 用戶范圍類型： 指定用戶 用戶組 任意用戶 訪問類型和用戶范圍的組合： 訪問矩陣：矩陣的一維是每個目錄和文件，另一維是用戶范圍，每個元素是允許的訪問方式 訪問策略(policy)：每種文件訪問方式，所允許或禁止的用戶范圍。可以將文件訪問方式推廣到其他操作如用戶管理，備份，網絡訪問等。7.5.2 文件的并發訪問訪問文件之前，必

22、須先打開文件：如果文件的目錄內容不在內存，則將其從外存讀入，否則，仍使用已在內存的目錄內容。這樣，多個進程訪問同一個文件都使用內存中同一個目錄內容，保證了文件系統的一致性。文件鎖定(file lock)：可以協調對文件指定區域的互斥訪問 Solaris 2.3中lockf的鎖定方式： F_UNLOCK：取消鎖定； F_LOCK：鎖定；如果已被鎖定，則阻塞； F_TLOCK：鎖定；如果已被鎖定，則失敗返回 F_TEST：鎖定測試；利用進程間通信，協調對文件的訪問；返回文件并發訪問控制的目的是提供多個進程并發訪問同一文件的機制。7.6 外存存儲空間管理7.6.1 文件存儲空間分配(file all

23、ocation)7.6.2 外存空閑空間管理方法(free space management)7.6.3 文件卷返回討論如何高效地進行數據存儲7.6.1 文件存儲空間分配(file allocation) 預分配(preallocation)：創建時(這時已知文件長度)一次分配指定的存儲空間，如文件復制時的目標文件。 動態分配(dynamic allocation)：需要存儲空間時才分配（創建時無法確定文件長度），如寫入數據到文件。返回1. 新創建文件的存儲空間（文件長度）分配方法2. 文件存儲單位：簇（cluster） 簇的大小 兩個極端：大到能容納整個文件，小到一個外存存儲塊； 簇較大：提

24、高I/O訪問性能，減小管理開銷；但簇內碎片浪費問題較嚴重； 簇較小：簇內的碎片浪費較小，特別是大量小文件時有利；但存在簇編號空間不夠的問題（如FAT12、16、32）；文件的存儲空間通常由多個分立的簇組成，而每個簇包含若干個連續的扇區(sector)。 簇的分配方法：兩種 簇大小可變，其上限較大：I/O訪問性能較好，文件存儲空間的管理困難（類似于動態分區存儲管理） 簇大小固定，較小：文件存儲空間使用靈活，但I/O訪問性能下降，文件管理所需空間開銷較大 文件巻容量與簇大小的關系 文件卷容量越大，若簇的總數保持不變即簇編號所需位數保持不變，則簇越大。缺點：簇內碎片浪費越多 文件卷容量越大，若簇大小

25、不變，則簇總數越多，相應簇編號所需位數越多。如簇編號長度為12、16、32二進制位，即構成FAT12、FAT16、FAT32。3. 文件存儲分配數據結構 連續分配(contiguous)：只需記錄第一個簇的位置，適用于預分配方法。可以通過緊縮(compact)將外存空閑空間合并成連續的區域。 鏈式分配(chained)：在每個簇中有指向下一個簇的指針。可以通過合并(consolidation)將一個文件的各個簇連續存放，以提高I/O訪問性能。 索引分配(indexed)：文件的第一個簇中記錄了該文件的其他簇的位置。可以每處存放一個簇或連續多個簇（只需在索引中記錄連續簇的數目）。采用怎樣的數據結

26、構來記錄一個文件的各個部分的位置。7.6.2 外存空閑空間管理(free space management)方法位示圖(bitmap)：每一位表示一個簇，取值0和1分別表示空閑和占用。空閑空間鏈接(chained free space)：每個空閑簇中有指向下一個空閑簇的指針，所有空閑簇構成一個鏈表。不需要磁盤分配表，節省空間。每次申請空閑簇只需取出鏈表開頭的空閑簇即可。空閑空間索引(indexed free space)：在一個空閑簇中記錄其他幾個空閑簇的位置。返回外存空閑空間管理的數據結構通常稱為磁盤分配表(disk allocation table)，分配的基本單位是簇。文件系統可靠性包括

27、檢錯和差錯恢復。空閑空間的管理方法：三種，均適用于上述幾種文件存儲分配數據結構；注：可以上述方法結合，應用于不同的場合。如：位示圖應用于索引結點表格，鏈接和索引結合應用于文件區的空閑空間。7.6.3 文件卷 磁盤分區(partition)：通常把一個物理磁盤的存儲空間劃分為幾個相互獨立的部分，稱為分區。一個分區的參數包括：磁盤參數（如每道扇區數和磁頭數），分區的起始和結束柱面等。 文件卷(volume)：或稱為邏輯驅動器(logical drive)。在同一個文件卷中使用同一份管理數據進行文件分配和外存空閑空間管理，而在不同的文件卷中使用相互獨立的管理數據。 一個文件不能分散存放在多個文件卷中

28、，其最大長度不超過所在文件卷的容量。 通常一個文件卷只能存放在一個物理外設上（并不絕對），如一個磁盤分區或一盤磁帶。返回 格式化(format)：在一個文件卷上建立文件系統，即： 建立并初始化用于進行文件分配和外存空閑空間管理的管理數據。 通常，進行格式化操作使得一個文件卷上原有的文件都被刪除。 擴展文件卷集(extended volume set)：一個文件卷由一個或幾個磁盤上的多個磁盤分區依次連接組成。可以容納長度大于磁盤分區容量的文件。 實例：Windows NT中的擴展文件卷集。 磁盤交叉存儲(disk interleaving)：將一個文件卷的存儲塊依次分散在多個磁盤上。如4個磁盤，

29、則磁盤0上是文件卷塊0, 4, 8, ，磁盤1上是文件卷塊1, 5, 9, 。 優點：提高I/O效率。如果需要訪問一個文件的多個存儲塊，而它們分散在多個磁盤上，則可以并發地向多個磁盤發出請求，并可在此基礎上提供文件系統的容錯功能。關鍵：磁盤訪問時間大部分由旋轉等待時間組成。 需要相應硬件設備：如多個硬盤連接在同一個或不同的SCSI接口上，或者兩個硬盤連接在一個或不同的IDE接口上（兩個硬盤連接在同一個IDE接口上，不能提高I/O效率） 實例：Windows NT中的條帶卷(stripe set)，每個文件卷塊的大小是64KB。 類似例子：在虛擬存儲器中建立多個交換區，分散在多個磁盤上Disk 0Disk 1Disk 2Disk 3Cycling WaitData TransfertRequestComplete多個磁盤上的交換區訪問7.7 文件系統舉例7.7.1 MS DOS的文件系統7.7.2 Windows NT的文件系統7.7.3 UNIX的文件系統返回7.7.1 MS DOS的文件系統返回多級目錄，不支持文件別名，無用戶訪問權限控制1. 磁盤文件卷結構