2.7 文件管理

在計算機應用中，信息的傳輸、處理和存儲是3個最關鍵的問題，而其中信息的存儲方式是其他問題的討論基礎。一個應用必然要生成各種各樣的數據信息，不論是暫時的，還是永久性的，都涉及到信息的存儲問題。前面已經講到過的內存管理所討論的主要是信息的暫時存儲和管理問題，而這里將著重討論永久信息存儲問題。

首先，永久信息的存儲介質是外圍存儲設備，例如硬盤、軟盤和光盤等，它們的存儲方式所涉及到的一個關鍵性概念就是文件。鑒于此類存儲設備在計算機系統中的重要地位，很多操作系統都會將對此類存儲介質的存儲管理納入自己的設計范圍內以進行仔細考慮，于是文件管理就產生了。

文件管理的核心部分是文件系統，它對操作系統的性能影響頗大。現在人們已經提出了很多不同類型的文件系統，形成了操作系統研究與實踐的一道亮麗的風景線。

2.7.1 文件與文件系統

在討論文件時通常還會遇到其他3個概念，即字段、記錄和數據庫。

1.字段

字段是數據的基本單位，一個字段通常是一個有著特定長度和類型的值，比如說雇員姓名等。字段可分為兩種：長度固定和長度可變。對于后者，每個字段通常包括2～3個子域即字段的值、字段的名稱，然后可選擇的就是字段的長度。有的時候，字段可以靠一個特殊字符來表示它的結束，從而不需要有字段的長度，例如某些字符串定義以NULL作為結束標志。

2.記錄

記錄是若干個相關的字段所組成的集合，可以被某些應用程序作為一個整體來看待。例如，一個雇員的記錄包括這樣一些字段：姓名、年齡、工種、住址和聯系方式等。和字段一樣，記錄的長度也分固定和可變兩種。文件是一些相似記錄的集合，都有一個唯一標識的文件名，應用程序或用戶可以通過它來對文件定位。文件可以被創建或者刪除，通常一些訪問權限的設定也都出現在文件這一層次，而在一些更高級的系統中，訪問權限控制可以細分到記錄級、甚至是字段級。

3.數據庫

數據庫用來對一些相關數據進行管理，它通常是通過文件管理相關程序來對一些可能屬于不同類型的文件進行統一管理。一般而言，這些文件或者數據之間的關系是明確界定了的。

文件通常是用戶或者程序管理信息和數據經常要用到的。針對文件有一些比較典型的操作，例如取出文件中的一個或若干個記錄、向文件中插入一個或者若干個記錄、從文件中刪除一個或者若干個記錄等。

還有一個和文件聯系比較緊密的概念就是文件目錄，它為一組文件的統一管理提供了一個簡單且有效的工具，從而成為所有文件管理系統中不可或缺的一部分。

文件系統向用戶或程序提供一個使用文件的統一界面，從而使得對文件的各類操作能夠在更加抽象、更加簡便的層次上進行。文件系統的引入通常有以下幾種目的。

● 滿足用戶管理數據的需要，這其中包括數據存儲和對數據的操作。

● 盡可能保證文件中的數據的有效性。

● 性能優化，以提高系統的吞吐量和響應速度。

● 提供不同類型的存儲設備的I/O支持。

● 降低或消除數據丟失或遭破壞的可能性。

● 提供一個標準的I/O界面。

● 在多用戶系統中，向多個用戶提供I/O支持等。

2.7.2 文件組織與訪問

文件組織是指其中記錄的邏輯結構，它是按照這些記錄訪問方式來劃分的。在外圍存儲設備中存在的文件的物理結構有賴于具體的存儲設備的分塊和分配的策略，這個在后面闡述，這里講述文件組織的類型。

選取一個文件組織類型需要從幾個方面來考慮：信息訪問的速度、信息更新的難易程度、存儲的經濟性及可靠性等。

不同的應用對這幾個方面的要求各有不同，需要在具體情況下進行權衡，畢竟有些方面相互之間會產生矛盾。例如，如果想要存儲經濟，就不好強求訪問速度高了，因為一般而言，提高訪問速度意味著需要更多的冗余信息來提供文件或記錄索引，這就意味著有效存儲信息的所占比例將會有所下降。

現在已經有很多文件組織類型，可以總結出5種基本的類型，其他的文件組織類型要么是其中一種，要么就是其中若干種的混合。這5種基本的文件組織類型就是堆文件、順序文件、索引順序文件、索引文件、快速文件（圖2-12），其性能比較見表2-6。

1.堆文件

文件組織形式中最簡單的莫過于堆文件了。在堆文件組織形式中，數據依照它們被存儲的順序依次排放在存儲設備中，每一個記錄就代表每一次連續數據的存儲，在記錄間有一個特定的分隔符作為界定。每一個記錄都有若干個字段，其中最主要的就是記錄名和記錄的值。

由于在堆文件中，除了記錄信息，沒有其他的冗余信息，所以對信息的檢索只能用完全搜索的辦法。這就是說，如果需要尋找某個特定的記錄，那就需要依次查找每個記錄直到目標出現，而如果想要查找有著某個特定值的記錄，那就麻煩了，需要搜遍所有記錄以找出所有符合條件的。

2.順序文件

最常見的文件結構是順序文件結構。在這種文件類型中，所有的記錄都有著相同的格式：等長、字段數量相同、字段順序也一致。因此，各個記錄只需要保留各自的值即可，而記錄名和記錄的長度等信息可以提取出來作為文件自身的屬性統一存儲，這樣可以提高文件存儲的經濟性。

在每一個記錄中有一個特殊的字段，就是關鍵字。關鍵字唯一標識記錄，通常記錄是按照關鍵字的順序來存儲的。順序文件組織在批處理應用中通常是高效的，而在類似交互式應用中，當涉及到頻繁的記錄查詢或更新的時候，順序文件結構的表現就很差。通常，順序文件的物理存儲采用鏈表結構：若干個記錄共用一個物理塊，而每一個物理塊都會有一個指針指向下一個文件所用到的物理塊。

3.索引順序文件

為了克服順序文件在隨機訪問時的缺點，人們提出了索引順序文件類型。索引順序文件與順序文件相比，所不同的是加入了兩個新的特征：一個是可以支持隨機訪問的索引，一個是溢出文件。索引能夠使得用戶或程序很快找到所需要的記錄，而溢出文件和日志文件比較類似，這樣溢出文件中的記錄就可以通過它們前繼記錄所給出的指針來實現快速訪問了。

在簡單的索引順序文件中，索引只有一級，這時的索引就是一個簡單的順序文件。在這個文件中的記錄包含兩個字段，一個是該記錄的關鍵字，另外一個則是一個指向主文件某個記錄的指針。當需要查找某個字段時，首先在索引文件中查找與該字段對應的關鍵字距離最近的一個索引，在獲得該索引之后，就可以根據該索引給出的指針轉到主文件中的對應位置繼續搜索直到找到所需要的字段為止。如果需要插入一個新的記錄，它會被插入到溢出文件中，而與其關鍵字距離最近的前繼記錄的指針將會被刷新并指向該記錄。另外為了獲得更高的訪問速度，可以引入多級索引結構。

4.索引文件

索引順序文件的一個局限性就是它只對記錄的某一個特定字段建立索引。因此，如果按照一個并非建立了索引的字段值來搜索的話，索引順序文件和順序文件一樣都會表現得很不好。但是，很多時候需要按照不同的字段來搜索記錄。

索引文件的引入就是為了迎合這種需求。索引文件實際上是一個多索引結構，它針對記錄中可能會成為搜索對象的字段建立多個索引文件。在這種索文件組織結構中，記錄的訪問可以完全通過索引直接完成，并且記錄的長度是可以變化的。所有的索引可以分為兩種類型，一種是完全索引，它對所有記錄都建立索引，另一種是部分索引，它只對某些感興趣的記錄建立索引。由于記錄允許變長，所以某些記錄擁有別的字段的可能就沒有。當有新的記錄加入的時候，所有的索引文件都需要更新。

5.快速文件

快速文件組織形式利用哈希表技術，給定一個關鍵詞，可以很快地找到對應的記錄所在的物理塊的地址。

2.7.3 文件共享

在一個多用戶系統中，一個文件通常需要在多個用戶中共享，這個時候就有兩個問題需要考慮：一個是訪問權限，另外一個就是并發訪問管理。

1.權限

為了實現多用戶系統的文件訪問權限控制，不同的用戶或用戶組的權限已經被分別規定了，可以通過限定可訪問文件的用戶或用戶組來實現對文件訪問權限的控制。通常針對一個文件有這么一些訪問權限的規定，比如執行、讀、寫和刪除等，并且各個基本權限可以自由組合形成更為精確的規定。

通常每一個文件都有一個所有者，一般而言，這個文件的所有者也是創建該文件的用戶，對該文件具有完全的訪問權限。另外，每一個多用戶系統還有一個擁有至高權限的用戶，稱為管理員，他對所有文件都擁有完全的訪問權限，可以方便地對系統進行有效管理。

2.訪問管理

當多個用戶擁有對某個文件的寫權限的時候，就需要引入相應的互斥控制機制來維持文件本身邏輯的完整性。一個比較簡單的做法就是當某個用戶需要寫這個文件時，拒絕其他用戶訪問，直到該用戶執行完操作為止。更為精細的做法則是在記錄級上實現互斥，這樣就可以使得一個用戶在對文件的某個記錄進行操作的同時，另外一個用戶可以對文件中的另外一個記錄進行操作，從而提高系統效率。

2.7.4 記錄分塊

上面所提到的文件組織結構是計算機中記錄的邏輯結構，它們最終是要存儲在外圍存儲設備中的，這就涉及到了記錄的物理結構問題。在物理結構中，記錄是以物理塊的形式組織的。

現在就有一個問題提出了，物理塊究竟應該是等長的還是變長的？毫無疑問，變長可以帶來靈活性，可以按照記錄邏輯結構的特點隨意定義塊的長度，但是這樣卻會在I/O緩沖、內存緩沖的分配和管理上帶來麻煩。事實上，在大多數系統中，物理塊長度一定。

這樣就又有一個問題出來了，物理塊的長度如何界定呢？物理塊如果越長，而且文件的記錄按順序排放在物理塊上的話，那么每次I/O訪問就可以往內存讀入越多的記錄，從而能夠提高I/O設備的吞吐量。但是如果文件的記錄是隨機存儲的話，也就說隨意散落在各個物理塊中，則物理塊越長，每次讀入內存的記錄中無用的就越多。事實上，對于這種情況，可以通過碎片整理程序之類的工具實現文件記錄的集中存儲，從而提高每次讀入記錄的有效部分的所占比率。

給定一個記錄的長度，就涉及到如何實現分塊的問題，主要有3種分法。

（1）固定分塊法

記錄定長，每個物理塊都存放整數個記錄，而這個數目都是一樣的。這種方法會導致每個物理塊最后可能會有固定大小的存儲空間被浪費。

（2）變長可跨越分塊法

使用變長記錄，打包進塊，沒有浪費存儲空間，而某些記錄則可能被分開存儲在兩個塊中，由后續塊的指針來標明連續性。

（3）變長不可跨越分塊法

使用變長記錄，但不允許一個記錄分開在兩個塊中存儲。因此，如果下一個記錄比塊的剩余空間大的話，該剩余空間就只能被浪費掉了。

固定分塊法適合記錄定長的順序文件存儲，而變長可跨越分塊法能夠有效利用存儲空間，并且不限制記錄的大小，靈活性很好，但是卻很難實現。變長不可跨越分塊法會導致存儲空間浪費，并且記錄的長度受限于物理塊的長度。

在現代計算機中，虛擬內存技術得到了廣泛應用，這個時候在考慮記錄分塊的時候就需要注意到一個現實，就是記錄分塊技術常常要和虛擬內存技術相關的硬件打交道。由于虛擬內存的最小管理單位是分頁，因此一個比較理想的I/O傳輸的基本單位就是分頁。但是在通常情況下，分頁往往是比較小的，因此在某些計算機系統中就采取將多個分頁的長度和作為一個物理塊的大小，從而實現一次I/O訪問能夠讀取整數個分頁的目的。

2.7.5 外圍存儲設備管理

在文件系統管理中，對文件的物理存儲管理也是一個很重要的內容，這里的文件的物理存儲管理主要就是指外圍存儲設備管理。外圍存儲設備管理包括兩個方面，一個是文件分配，另外一個就是空閑存儲空間管理。

1.文件的存儲空間分配

文件的存儲空間分配涉及到3個方面的內容：一是文件創建之初，分配給它的存儲空間大小如何確定的問題；二是文件存儲空間總是分成若干個內部連續的存儲劃分，這樣一些劃分的大小該如何確定；三是采用什么樣的數據結構來對這些分區進行統一管理，也就是涉及到一個文件分配表的選擇問題。

對于第一個問題的回答有兩個，一個是預分配法，一個是動態分配法。所謂預分配法就是在文件創建之初按其長度的最大值一次性分配給相應大小的存儲空間。這種分配方法在某些可以預知文件最大長度的情況下是很有效的，但是對于一些難以預料文件最大長度的情況，為了避免最后所分配區域不夠用的狀況出現，預分配的存儲空間總是比實際所用到的要大，從而造成了存儲空間的浪費。動態分配法與預分配法相比就具有更大的靈活性，它只有當預先分配的存儲空間不夠用時再動態分配一定數量的存儲空間。

存儲劃分的大小的選取需要從多個角度多加權衡，才能得到比較滿意的答案。如果劃分的連續存儲區域比較大的話，不僅可以提高某些數據訪問的速度，同時還可以減小文件分配表的大小。綜合起來，權衡利弊，可以有以下兩種選擇。

（1）變長、較長的連續區域劃分

這種方式可以提高系統性能，避免存儲空間的浪費，而文件分配表也會比較小。問題是，存儲空間不好使用，這個道理和前面講過的物理塊變長的情況比較類似。

（2）物理塊

物理塊長度較小、定長、容易分配，沒有考慮連續性，分配起來比較容易，并且有一定的靈活性。至于說連續性方面的缺陷，如果采用某些類似文件碎片整理程序的工具對存儲空間進行整理的話，則可以有些補償，進而能夠在某種程度上提高系統的性能。事實上，物理塊是在外圍存儲空間設備管理中廣泛使用的。至于說采取什么樣的數據結構來對這些存儲區域的連續劃分進行管理，有3種可以選擇的方案，即連續分配法、鏈狀分配法和索引分配法。

所謂連續分配法就是在文件創建之初將一片連續的物理塊分配給文件。這是一種預分配法，采用變長存儲劃分。和連續分配法相對的是鏈狀分配法，它不要求各物理塊是連續擺放的，事實上可以是在存儲空間中隨機擺放的。所有物理塊按邏輯順序通過指針穿成一個單向鏈表，索引分配法則在主文件之外對它維護一個索引文件，用于索引主文件中的各個物理塊，從而實現對各物理塊的快速訪問。

2.空閑存儲空間管理

就像已分配的存儲空間需要管理一樣，未分配的存儲空間也需要進行合理的管理，常用的方法主要有3種，即位示圖、空閑塊鏈和索引。位示圖維護一個向量，其每一位與存儲空間中的一個物理塊一一對應。當位值為0時表示與該位對應的物理塊處于空閑狀態，如果位值是1的話，則說明物理塊已經被征用了。空閑塊鏈則是使用鏈表技術將所有空閑存儲區域劃分并按照一定的邏輯順序連接起來，類似地，索引方法也就是利用索引技術將所有空閑存儲區域劃分進行統一管理的。