作業系統學習筆記-檔案管理

前言

正在學習作業系統，記錄筆記。

參考資料：

《作業系統（精髓與設計原理 第8版） 》

第十二章：檔案管理

概述

檔案和檔案系統

檔案管理（File Management）

在大多數一應用中，檔案都是核心元素，相對應的就需要檔案管理。檔案管理的基本目标就是能夠快速準确地找到存儲在磁盤當中的檔案，并将其加載進記憶體，進行讀/寫操作。

要實作檔案管理可以有兩種方式：

• 使用者程式設計實作：對于使用者來講，需要知曉磁盤的實體特性，還有很多其他的要求，顯然這并不是一個很好的方案，對于使用者來說要求太高。
• 作業系統實作：我們重點就是要讨論此方案。

實際上所有的作業系統都提供了檔案管理系統，它由系統實用程式組成，可以作為具有特權的應用程式來運作。

檔案系統屬性：

• 長期存在：檔案存儲在硬碟或其他輔存中，使用者退出系統時檔案不會丢失，
• 程序共享：檔案有名字，具有允許受控共享的相關通路權限。

• 結構化存儲：取決于具體的檔案系統，一個檔案具有針對某個特定應用的内部結構。

  此外，檔案可組織為層次結構或更複雜的結構，以反映檔案之間的關系。

檔案系統提供對檔案進行操作的接口，典型的有以下六種：

• 建立（Create）：在檔案結構中定義并定位一個新檔案。

• 删除（Delete）：從檔案結構中删除并銷毀一個檔案。

  注意這裡的删除并不能真正地把資料從實體磁盤中抹除。（格式化同樣如此）

• 打開（Open）：程序将一個已有檔案聲明為“打開”狀态，以便允許該程序對這個檔案進行操作。
• 關閉（Close）：相關程序關閉一個檔案，以便不再能對該檔案進行操作，直到該程序再次打開它。
• 讀（Read）：程序讀取檔案中的所有或部分資料。
• 寫（Write）：程序更新檔案，要麼通過添加新資料來擴大檔案的尺寸，要麼通過改變檔案中已有資料項的值。

檔案結構

讨論檔案時通常要用到如下四個術語：

• 域（Field）：域是基本的資料單元。

  • 一個域包含一個值

    比如：現有一個工資管理系統，其中有一個名為“花豬”的對象（也可視為一條記錄），其中有一個屬性叫做性别，這個屬性就稱為一個域。

  • 可分為

    基本域

    和

    組合域

    ：
    • 基本域：不可再分，通常為定長。
    • 組合域：可以再分成子域，通常為變長。（如工資屬性可以細分為基本工資、績效工資等）
• 記錄（Record）：是一組相關域的集合。

  • 可視為應用程式的一個單元。

    比如：一條雇員記錄可能包含以下域：名字、社會保險号、工作類型、雇用日期等。

  • 記錄的長度可以是定長的或變長的
• 檔案（File）：一組相似記錄的集合。
  • 被使用者和應用程式視為一個實體，并可通過名字通路
  • 有唯一的檔案名，可以被建立或删除

  • 通路控制通常在檔案級實施

    在有些更複雜的系統中，控制通路也可以在記錄級或域級實施。

• 資料庫（Database）：是一組相關資料的集合。
  • 其本質特征是資料元素間存在着明确的關系
  • 可供不同的應用程式使用

檔案管理系統

檔案管理系統是一組系統軟體，它為使用檔案的使用者和應用程式提供服務。

• 檔案管理系統是使用者或應用程式通路檔案的唯一方式
• 使用者或程式員不需要為每個應用程式開發專用軟體

檔案管理系統需要滿足以下七大需求：

1. 滿足資料管理的要求和使用者的需求，包括存儲資料和執行上述操作的能力。
2. 最大限度地保證檔案中的資料有效。
3. 優化性能：包括總體吞吐量（從系統的角度）和響應時間（從使用者角度）。
4. 為各種類型的儲存設備提供I/O支援。
5. 減少或消除丢失或者破壞資料的可能性。
6. 向使用者程序提供标準I/O接口例程集。
7. 在多使用者系統中為多個使用者提供I/O支援。

在上述第一條中，使用者需求的範圍取決于各種應用程式和計算機系統的使用環境。對于互動式的通用系統，最小需求集合如下：

• 每個使用者實作基本操作：如建立、删除、讀取和修改檔案
• 每個使用者都應能受控地通路其他使用者的檔案
• 每個使用者都應能控制允許對使用者檔案進行哪種類型的通路
• 每個使用者應該能夠按照自己的需要進而對檔案進行重構
• 每個使用者都應能在檔案間移動資料
• 每個使用者都應能備份使用者檔案，并在檔案遭到破壞時恢複檔案
• 每個使用者都應能通過名字而非數字辨別符通路自己的檔案

檔案系統架構

下圖展示了檔案系統軟體架構：

從底層逐層向上介紹：

1. 裝置驅動層：
   • 直接與外圍裝置通信
   • 裝置驅動程式負責啟動裝置上的I/O操作，處理I/O請求的完成
2. 基本檔案系統：也稱為實體I/O層，是計算機系統外部環境的基本接口。
   • 處理在磁盤間或錄音帶系統間交換的資料塊
   • 關注塊在輔存和記憶體緩沖區的位置，而非資料的内容或所涉及的檔案結構
   • 通常是作業系統的一部分
3. 基本I/O管理程式：
   • 負責所有檔案I/O的初始化和終止
   • 需要一定的控制結構來維護裝置的輸入、輸出、排程和檔案狀态
   • 根據所選的檔案來選擇執行檔案I/O的裝置
   • 為了優化性能，參與排程對磁盤和錄音帶的通路
   • 是作業系統的一部分
4. 邏輯I/O：
   • 使使用者和應用程式能夠通路記錄
   • 提供一種通用的記錄I/O能力

   • 維護關于檔案的基本資料

     基本檔案系統處理的是資料塊，而邏輯I/O子產品處理的是檔案記錄。

5. 通路方法：
   • 檔案系統中與使用者最近的一層
   • 在應用程式和檔案系統以及儲存資料的裝置之間提供了一個标準接口

   • 不同的通路方法反映了不同的檔案結構及通路和處理資料的不同方法

     堆（Pile）、順序（Sequential）、索引順序（Indexed Sequential）、索引（Indexed）、散列（Hashed）

檔案管理功能：

下圖展示了檔案管理的要素

• 使用者或應用程序發送操作檔案的指令（建立、删除等）與檔案系統進行互動
• 在執行操作任何檔案之前，檔案系統必須确認和定位所選擇的檔案
• 定位檔案要求使用某種類型的目錄來描述所有檔案的位置及它們的屬性

• 大多數共享系統都實行使用者通路控制

  隻有被授權使用者才允許以特定方式通路特定的檔案

• 檔案的通路是以塊的形式

  雖然使用者和應用程式關注的是記錄，但I/O是以塊為基礎來完成的，是以檔案中的記錄必須組織成一組塊序列來輸出，并在輸入後将各塊組合起來。

• 支援檔案的塊I/O需要許多功能：
  • 管理輔存：包括把檔案配置設定到輔存中的空閑塊
  • 管理空閑存儲空間：以便知道新檔案和現有檔案增長時可以使用哪些塊
  • 必須排程單個的塊I/O請求

檔案組織和通路

檔案管理的評價标準

• 短的存取時間：
  • 需要時可以随機通路單一記錄

  • 無需批處理模式

    如果一個檔案僅以批處理方式處理，且每次都要通路到它的所有記錄，則基本無須關注用于檢索一條記錄的快速通路。

• 易于修改：

  存儲在CD-ROM中的檔案永遠不會被修改，是以易于修改這一點根本不需要考慮。

• 存儲經濟性：

  • 為了節約存儲空間，資料備援應最小（類似記憶體管理中考慮減小零頭的道理）

    另一方面，備援是提高資料通路速度的一種主要手段。例如：使用索引。

• 維護簡單
• 可靠性

下面要介紹五類常見的檔案組織結構：

堆檔案（Pile ）

• 最簡單的檔案組織形式，簡單有效

• 資料按照到達的順序被組織起來，每條記錄由一串資料組成。沒有固定的結構

  類似于本人考試時候時候草稿紙，按照【會寫的】題目順序依次演算，最後再演算之前較難的題，稿紙上的記錄就是做題的順序，不固定。

• 堆的目的僅僅是積累大量的資料并儲存資料

• 記錄可以有不同的域，或者相似但順序不同

  是以，每個域都應能自我描述，并包含域名和值。

• 缺點：

  • 寫入的資料必須具有自解釋性：包含域名和值，

    每個域的長度由分隔符隐式地指定，要麼明确地包含在一個子域中，要麼是該域類型的預設長度。

  • 對于記錄的通路是通過窮舉查找的方式（由于非結構化的原因）

    當資料在處理前采集并存儲時，或當資料難以組織時，會用到堆檔案。當儲存的資料大小和結構不同時，這種類型的檔案空間使用情況很好，能較好地用于窮舉查找，且易于修改。但是，除了這些受限制的使用外，這類檔案對大多數應用都不适用。

順序檔案（Sequential File ）

• 最常用的檔案組織形式

  使用場景：批量的寫入資料，例如：爬蟲

• 每條記錄都使用一種固定的格式
• 所有記錄都具有相同的長度

• 所有記錄都由相同數量、長度固定的域按特定的順序組成

  以上三點可以避免資料的自解釋性，降低成本開銷。

• 缺點：
  • 對記錄的查詢仍然是窮舉查詢
  • 插入一條記錄時并不友善，需要移動後續的所有記錄位置
• 為了解決資料插入的繁瑣，引入了一個特殊的域：關鍵域（key field）/ 主域
  • 通常是每條記錄的第一個域
  • 可以唯一地辨別該記錄（類似資料庫中的主鍵）
• 為了高效處理資料，引入日志檔案（log file）/ 事務檔案（transaction file）
  • 進行檔案處理時，把新的記錄放在一個單獨的堆檔案中，即日志檔案
  • 通過周期性地執行成批更新，把日志檔案合并到主檔案中，并按正确的關鍵字順序産生一個新檔案

索引順序檔案（Indexed Sequential File）

• 索引提供了一個查詢功能，以快速到達所需記錄的附近區域
• 索引檔案中的每條記錄由兩個域組成：關鍵域和指向主檔案的指針，其中關鍵域和主檔案中的關鍵域相同
• 查找某個特定的域，首先要查找索引：
  • 查找關鍵域值等于目标關鍵域值或者位于目标關鍵域值之前且最大的索引
  • 然後在該索引的指針所指的主檔案中的位置處開始查找

  舉個例子說明該方法的有效性：

  考慮一個包含100萬條記錄的順序檔案

  • 查找某個特定的關鍵域值，平均需要通路50萬次記錄（

    (1000000 + 1) / 2

    ）
  • 假設現在建立一個包含了1000項的索引，如果要查找特定記錄：
    • 平均在索引檔案中通路500次（

      (1000 + 1 ) / 2

      ）
    • 接着在主檔案中平均通路500次（

      (1000 + 1 ) / 2

      ）
  由此可見，平均通路次數從500000降低到了1000，大大降低了查詢開銷。
• 檔案按如下方式處理：
  • 主檔案中的每條記錄都包含一個附加域（附加域對應用程式不可見）
  • 附加域是指向溢出檔案的一個指針
  • 向檔案中插入一條新記錄時，它被添加到溢出檔案（overflow file）中

  • 修改主檔案中邏輯順序位于這條新紀錄之前的記錄，使其包含指向新紀錄前面的那條記錄的指針

    如果新紀錄前面的那條記錄也在溢出檔案中，那麼修改新紀錄前面的那條記錄的指針

  • 索引順序檔案有時也按照批處理的方式合并溢出檔案

• 為提供更有效的通路，可以為關鍵域設定多級索引

  同樣以通路包含100萬條記錄的順序檔案

  • 首先建構10000項的低級索引
  • 低級索引再建構100項的進階索引
  • 查詢過程從進階索引開始：
    • 查詢低級索引的一項，平均50次通路（

      (50 + 1) / 2

      ）
    • 找到主檔案中的一項，平均50次通路（

      (50 + 1) / 2

      ）
    • 最後查找主檔案，平均50次通路（

      (50 + 1) / 2

      ）
  • 總共平均查找150次

索引檔案（Indexed File ）

索引順序檔案的是基于檔案的一個域（關鍵域）進行處理，但是在現實中，可能需要對我們所關注的一些域（屬性）進行記錄查詢，這時索引順序檔案就失去了作用。為此，引入了一個多索引的結構。

• 索引檔案摒棄了順序性和關鍵字的概念，隻通過索引通路記錄

• 要求至少有一個索引的指針指向一條記錄就好，不限制記錄放置的位置

  還可以使用長度可變的記錄

• 可以使用兩種類型的索引：

  • 完全索引（exhaustive index）：包含主檔案中每條記錄的索引項

    查詢速度快，但是由于包含記錄的全部索引項，是以會多占用一部分記憶體空間

    為了易于查找，索引自身被組織成一個順序檔案

  • 部分索引（partial index）：隻包含那些有感興趣域的記錄的索引項
  對于變長記錄，某些記錄并不包含所有的域。向主檔案中增加一條新記錄時，索引檔案必須全部更新。

直接檔案或散列/哈希檔案（Direct or Hashed File）

• 可以直接通路磁盤中任何一個位址已知的塊

• 每條記錄中都需要一個關鍵域

  這裡對關鍵域進行Hash操作，較索引檔案節約空間，但是存在哈希沖突，是以查詢速度要慢一些

檔案目錄

内容

檔案目錄解決了這樣一個問題：即給定一個檔案名，就能夠在外存中準确地通路到對應檔案。

與任何檔案管理系統和檔案集合相關聯的是檔案目錄。目錄包含檔案的相關資訊，包括：

• 屬性（Attributes）
• 位置（Location）
• 所有權（Ownership）

目錄自身是一個檔案，它可被各種檔案管理例程通路。

盡管使用者和應用程式也可得到目錄中的某些資訊，但這通常是由系統例程間接提供的。

從使用者角度看，目錄在使用者和應用程式所知道的檔案名和檔案自身之間提供映射。

每個檔案項都包含檔案名。

下表列出了檔案目錄的資訊單元

基本資訊

資訊單元 說明 檔案名 由建立者（使用者或程式）選擇的名字，在同一個目錄中必須是唯一的 檔案類型 如文本檔案、二進制檔案、加載子產品等 檔案組織 供那些支援不同組織的系統使用 位址資訊

資訊單元 說明 卷 訓示存儲檔案的裝置 起始位址 檔案在輔存中的起始實體位址（如在磁盤上的柱面、磁道和塊号） 使用大小 檔案的目前大小，機關為位元組、字或塊 配置設定大小 檔案的最大尺寸 通路控制資訊

資訊單元 說明 所有者 控制檔案的使用者。所有者可授權或拒絕其他使用者的通路，并改變給予它們的權限 通路資訊 該單元的最簡形式包括每個授權使用者的使用者名和密碼 許可的行為 控制讀、寫、執行及在網上傳送 使用資訊

資訊單元 說明 資料建立 檔案首次放到目錄中的時間 建立者身份 通常是目前所有者，但不一定必須是目前所有者 最後一次通路的日期 最後一次讀記錄的日期 最後一次讀使用者的身份 最後一次進行讀的使用者 最後一次修改的日期 最後一次修改、插入或删除的日期 最後一次修改者的身份 最後一次進行修改的使用者 最後一次備份的日期 最後一次把檔案備份到另一個存儲媒體中的日期 目前使用 目前檔案活動的資訊，如打開檔案的程序、是否被一個程序加鎖、檔案是否在記憶體中被修改但未在磁盤中修改等

結構

在介紹目錄結構之前，為了了解檔案結構的需求，我們可以考慮可能在目錄上執行的操作：

• 查找：使用者或應用程式引用一個檔案時，必須查找目錄，以找到該檔案相應的目錄項。
• 建立檔案：建立一個新檔案時，必須在目錄中增加一個目錄項。
• 删除檔案：删除一個檔案時，必須在目錄中删除相應的目錄項。
• 顯示目錄：可能會請求目錄的全部或部分内容。通常，這個請求是由使用者發出的，用于顯示該使用者所擁有的所有檔案和每個檔案的某些屬性（如類型、通路控制資訊、使用資訊）。
• 修改目錄：由于某些檔案屬性儲存在目錄中，因而這些屬性的變化需要改變相應的目錄項。

簡單目錄結構

• 最簡單的結構是一個目錄項清單，每個檔案都有一個目錄項
• 該結構可表示最簡單的順序檔案，檔案名作為關鍵域
• 在組織檔案的時候該結構提供不了幫助
• 使用者在使用這種結構時需要注意不能給兩個不同的檔案取相同的名字（強制性的）

• 檔案查詢速度慢

  實際上若目錄是一個簡單的順序清單，則它對于組織檔案沒有任何幫助。很難滿足使用者需求，尤其在共享系統中會變得更糟。

兩級目錄方案

• 有一個主目錄
• 每位使用者有一個使用者目錄
• 主目錄中的每一項為使用者目錄，并提供位址和通路控制資訊
• 每個使用者目錄為簡單清單檔案
• 對構造結構化檔案集合沒有任何幫助
• 在不同的目錄下，允許給檔案進行相同命名

• 較簡單目錄結構加快了檔案查詢速度

  舉例，有n個使用者，每個使用者有m個檔案：

  • 簡單目錄結構：

    (n × m) / 2

  • 兩級目錄方案：

    (n + m) / 2

層次/樹狀結構目錄

• 有一個主目錄，主目錄下是許多使用者目錄
• 每個使用者目錄下又可以包含子目錄的目錄項和檔案的目錄項
• 樹狀結構目錄降低了為檔案提供唯一名稱的難度

命名

路徑名（pathname）：系統中的任何檔案都可以按照從根目錄或主目錄向下到各個分支，最後直到該檔案的路徑來定位。這一系列目錄名和最後到達的檔案名組成了該檔案的路徑名。

檔案名稱可以相同，隻要路徑名不同就可以。

現假設有一個名為“

HuaZhu”

的使用者目錄，其包含子目錄：

OS → Nachos → code → thread

在

thread

目錄下有一個名為

thread.cc

檔案，現在要定位該檔案

絕對路徑：/HuaZhu/OS/Nachos/code/thread/thread.cc

工作目錄（working directory ）：（如果要求使用者在每次通路檔案時都必須拼寫完整的絕對路徑仍比較複雜）在典型情況下，對互動使用者或程序而言，總有一個目前路徑與之相關聯，通常稱為工作目錄。檔案通常按相對于工作目錄的方式通路，即采用相對路徑。

現假設我正處于

Nachos

目錄下，定位

thread.cc

檔案

相對路徑：./code/thread/thread.cc

絕對路徑和相對路徑的使用沒有絕對的優劣，針對不同的使用場景有不同的選擇。

檔案共享

在多使用者系統中，幾乎總是要求允許檔案在多個使用者間共享，這就會産生兩個問題：

• 通路權限
• 對同時通路的管理

通路權限

下面列出了一些具有代表性的通路權限：

• 無（None）：
  • 使用者不知道檔案是否存在
  • 為了實施這種限制，不允許使用者讀包含該檔案的使用者目錄
• 知道（Knowledge）：

  • 使用者僅僅可确定檔案是否存在并确定其所有者

    沒有更多的通路權限，當然使用者可以向檔案所有者申請。

• 執行（Execution）：

  • 使用者可以加載并執行一個程式，但不能複制它（看不到程式内部，即不可讀檔案）

    私有程式通常具有這種通路限制。

• 讀（Reading）：

  • 使用者可以讀檔案，包括複制和執行

    有些系統還可區分浏覽和複制，對于前一種情況，檔案的内容可以呈現給使用者，但使用者卻無法進行複制。

• 追加（Appending）：

  • 使用者可給檔案添加資料，通常隻能在末尾追加，但不能修改或删除檔案的任何内容

    在許多資源中收集資料時，這種權限非常有用

• 更新（Updating）：
  • 使用者可修改、删除和增加檔案中的資料

  • 通常包括最初寫檔案、完全重寫或部分重寫、移去所有或部分資料

    有些系統還區分不同程度的更新

• 改變保護（Changing protection ）：

  • 使用者可改變已授給其他使用者的通路權限

    通常，隻有檔案的所有者才具有這一權力。在某些系統中，所有者可把這項權力擴充到其他使用者。為防止濫用這種機制，檔案的所有者通常能指定該項權力的持有者改變哪些權限。

• 删除（Deletion）：
  • 使用者可從檔案系統中删除該檔案

這些權限構成了一個層次結構，層次結構中的每個權限都隐含了前面的那些權限

被指定為某個檔案所有者的使用者，通常是最初建立該檔案的使用者。所有者具有前面列出的全部權限，并且可給其他使用者授予權限。通路可以提供給不同類型的使用者：

• 特定使用者（Specific user ）：由使用者ID指定的單個使用者。
• 使用者組（User groups ）：非單獨定義的一組使用者。系統必須能通過某種方式了解使用者組的所有成員。
• 全部（All ）：有權通路該系統的所有使用者。這些是公共檔案。

同時通路

如果允許多個使用者追加或更新一個檔案，作業系統或檔案系統必須強加一些規範：

• 在使用者修改檔案時，允許使用者對整個檔案加鎖
• 更好的方案是對檔案中要修改的記錄進行加鎖

在設計共享通路能力時，必須解決互斥問題和死鎖問題。

二級存儲管理（輔存管理）

在輔存中，檔案是由許多塊組成的。作業系統或檔案管理系統負責為檔案配置設定塊。這時會引發兩個管理問題：

• 輔存中的空間必須配置設定給檔案
• 必須知道哪些空間可用來進行配置設定（空閑空間管理）

檔案配置設定

檔案配置設定涉及以下幾個問題：

• 建立一個新檔案時，是否一次性地給它配置設定所需的最大空間？

• 給檔案配置設定的空間是一個或多個連續的單元，這些單元稱為分區。在配置設定檔案時，分區的大小應該是多少？

  分區（portion）是一組連續的已配置設定塊。分區的大小可以從一個塊大小到整個檔案大小。

• 為跟蹤配置設定給檔案的分區，應使用哪種資料結構或表？

  在DOS或其他系統中，這種表通常稱為檔案配置設定表（File Allocation Table，FAT）

預配置設定

• 要求在發出建立檔案的請求時，聲明該檔案的最大尺寸
• 實際對于許多應用程式來說，可靠的預估檔案的最大尺寸是有難度的

• 使用者和應用程式會将檔案尺寸估計得大一些，此時就會造成浪費

  是以采用動态配置設定要好一些

分區大小

• 一種極端情況是：配置設定大到足以儲存整個檔案的分區

  大小可變的大規模連續分區：能提供較好的性能。大小可變避免了浪費，且會使檔案配置設定表較小，但這又會導緻空間很難再次利用。

• 另一種極端情況是：磁盤空間一次隻配置設定一塊

  塊：小的固定分區能提供更大的靈活性，但為了配置設定，它們可能需要較大的表或更複雜的結構。鄰近性不再是主要目的，主要目的是根據需要來配置設定塊。

  是以需要折中考慮單個檔案的效率和整個系統的效率，具體要考慮以下内容：

  • 鄰近空間可以提高性能
  • 數量較多的小分區會增加用于管理配置設定資訊的表的大小
  • 使用固定大小的分區（例如塊）可以簡化空間的再配置設定
  • 使用可變大小的分區或固定大小的小分區，可減少超額配置設定導緻的未使用存儲空間的浪費

下面考慮三種檔案配置設定的方法，首先下表總結了每種方法的特點：

連續	鍊式	索引	索引
是否預配置設定	需要	可能	可能	可能
分區大小是固定還是可變	可變	固定塊	固定塊	可變
分區大小	大	小	小	中
配置設定頻率	一次	低到高	高	低
配置設定需要的時間	中	長	短	中
檔案配置設定表的大小	一個表項	一個表項	大	中

連續配置設定

說明：

• 圖左：連續檔案配置設定
• 圖右：連續檔案配置設定（緊縮後）
• 在建立檔案時，給檔案配置設定一組連續的塊
• 這是一種使用大小可變分區的預配置設定政策
• 在檔案配置設定表中，每個檔案隻需要一個表項，用于說明起始塊和檔案的長度

• 缺點：随着使用時長的增加，會出現外部碎片

  長時間後很難找到空間大小足夠的連續塊，是以需要緊縮算法來釋放磁盤中的額外空間

鍊式配置設定

說明：

• 圖左：鍊式配置設定
• 圖右：鍊式配置設定（合并後）

• 鍊式配置設定基于單個塊

  連續配置設定與鍊式配置設定是兩個極端

• 鍊中的每塊都包含指向下一塊的指針
• 在檔案配置設定表中，每個檔案同樣隻需要一個表項，用于聲明起始塊和檔案的長度
• 優勢：無外部碎片。最适合順序處理的順序檔案
• 缺點：局部性原
  • 若需要像順序處理那樣一次取入一個檔案中的多個塊，則需要對磁盤的不同部分進行一系列通路。這對于單使用者系統有重大影響，也是共享系統需要關注的。
  • 為克服這個問題，有些系統會周期性地合并檔案（如圖右）

索引配置設定

說明：

• 圖左：基于塊的索引配置設定
• 圖右：基于長度可變分區的索引配置設定
• 每個檔案在檔案配置設定表中都有一個一級索引
• 配置設定給該檔案的每個分區在索引中都有一個表項
• 檔案的索引儲存在一個單獨的塊中，檔案配置設定表中該檔案的表項指向這一塊

• 可以基于固定大小的塊；也可以基于大小可變的分區

  基于塊來配置設定可以消除外部碎片，而按大小可變的分區配置設定可以提高局部性。

  在任何一種情況下，都需要不時地進行檔案整理。在使用大小可變分區的情況下，檔案整理可以減少索引的數量，但對于基于塊的配置設定卻不能減少索引的數量。

• 支援順序通路檔案和直接通路檔案，因而是最普遍的一種檔案配置設定形式

空閑空間管理

目前還未配置設定給任何檔案的空間同樣需要管理。

要實作檔案配置設定技術，首先需要知道磁盤中的哪些塊是可用的，除了上述提到的檔案配置設定表（FAT），還需要磁盤配置設定表（Disk Allocation Table，DAT）。

位表（Bit tables ）：

這種方法使用一個向量，向量的每一位對應于磁盤中的每一塊。0表示空閑塊，1表示已使用塊。

• 優點：
  • 通過它能相對容易地找到一個或一組連續的空閑塊。（是以位表适用于前面描述的任何一種檔案配置設定方法）
  • 位表非常小，但其長度仍然很長。一個塊位圖所需的存儲器容量為：

    磁盤大小（位元組數） / （8 × 檔案系統塊大小

    ）

    例如：對于一個塊大小為512位元組的16GB磁盤，位表會占用4MB的空間。

鍊式空閑區（Chained free portions）：

使用指向每個空閑區的指針和它們的長度值，可将空閑區連結在一起。

• 由于不需要磁盤配置設定表，而僅需要一個指向鍊的開始處的指針和第一個分區的長度，因而這種方法的空間開銷可以忽略不計。
• 該方法适用于所有的檔案配置設定方法。

可靠性

使用鎖來防止程序間幹擾和空間配置設定一緻性。

請求一個檔案配置設定時：

1. 在磁盤中對磁盤配置設定表加鎖，以防止在配置設定完成前另一個使用者修改這個表。
2. 查找磁盤配置設定表，查找可用空間。這裡假設磁盤配置設定表的副本總在記憶體中，若不在，則須先讀入。
3. 配置設定空間，更新磁盤配置設定表，更新磁盤。更新磁盤包括把磁盤配置設定表寫回磁盤。對于鍊式磁盤配置設定，它還包括更新磁盤中的某些指針。
4. 更新檔案配置設定表和更新磁盤。
5. 對磁盤配置設定表解鎖。

後記

本篇已完結

先告一段落喽，非常感謝授課老師的指導以及同學們的幫助。

（如有修改或補充歡迎評論）