跳轉到

7.1 FAT 檔案系統#

概念說明#

FAT（File Allocation Table）是 1980 年代隨 DOS 流行的檔案系統，也是 UFS 隨身碟至今仍在用的格式。它的空間配置以「叢集（cluster）」為單位（1 叢集 = 2^n 個磁區），並在磁碟開頭維護一張檔案配置表：表中有 N 個項目（每叢集一項），項目值代表「檔案的下一個叢集編號」——整張表其實就是所有檔案區塊鏈的集合。

  • 項目值 = 下一叢集編號：鏈結的下一站。
  • EOF（如 0xFFFF）：檔案結束。
  • 0：空閒叢集。
  • BAD：壞軌標記。

檔案的目錄項目只記錄起始叢集編號，之後沿 FAT 表走鏈即可讀完整個檔案。這個設計極簡：配置新叢集只要掃表找值為 0 的項目；擴充檔案只要在鏈尾接上新叢集。

FAT 的優點是簡單、恢復容易（FAT 有兩份副本）；缺點是隨機存取慢——要讀檔案第 k 個區塊，必須從頭沿鏈走 k 步，每步在邏輯上都是一次表查詢（FAT 本身通常被作業系統快取在記憶體，但表越大快取壓力越大）；其次是檔案越大碎片越容易累積，鏈越走越跳。FAT32 用 32 位元表項，最大檔案 4GB−1 bytes，這個著名的限制就來自表項位元數。

演算法步驟#

讀檔案第 k 個區塊： 1. 從目錄項取得起始叢集 c₀。 2. 重複 k−1 次：c = FAT[c]（記憶體查表）。 3. 讀取叢集 c（1 次磁碟 I/O）。

寫入（追加）： 1. 沿鏈走到最後叢集 c_last。 2. 掃 FAT 找空閒叢集 c_free；FAT[c_free] = EOF。 3. FAT[c_last] = c_free，寫入資料。

Python 範例#

EOF = -1
class FAT32Sim:
    def __init__(self, total_clusters=64):
        self.fat = [0] * total_clusters   # 0=空閒, EOF=檔尾
        self.files = {}                   # 檔名 → 起始叢集
        self.io = 0

    def _free_cluster(self):
        for i, v in enumerate(self.fat):
            if v == 0: return i
        raise RuntimeError("磁碟滿")

    def create(self, name, n_blocks):
        blocks = []
        for _ in range(n_blocks):
            c = self._free_cluster()
            self.fat[c] = -2                  # 先標記占用，避免重複分配
            blocks.append(c)
        for a, b in zip(blocks, blocks[1:]):
            self.fat[a] = b
        self.fat[blocks[-1]] = EOF
        self.files[name] = blocks[0]

    def read_block(self, name, k):
        c = self.files[name]
        for _ in range(k):                # 沿鏈走 k 步（表查詢，常駐記憶體）
            c = self.fat[c]
        self.io += 1
        return c                          # 第 k 次才真正讀磁碟

    def append(self, name, n=1):
        c = self.files[name]
        while self.fat[c] != EOF:
            c = self.fat[c]
        for _ in range(n):
            nc = self._free_cluster()
            self.fat[nc] = EOF
            self.fat[c] = nc
            c = nc
        self.io += 1

    def fragmentation(self, name):
        """計算檔案的碎片度：鏈中非相鄰跳轉比例"""
        c, hops, jumps = self.files[name], 0, 0
        while self.fat[c] != EOF:
            if self.fat[c] != c + 1: jumps += 1
            hops += 1; c = self.fat[c]
        return jumps / hops if hops else 0

fs = FAT32Sim()
fs.create("a.txt", 5); fs.create("b.txt", 3); fs.create("c.txt", 4)
print("a.txt 第 3 區塊在叢集:", fs.read_block("a.txt", 3))
fs.append("b.txt", 2)
print("b.txt 鏈:", end=" ")
c = fs.files["b.txt"]
while c != EOF: print(c, end="→"); c = fs.fat[c]
print("EOF")
print("b.txt 碎片度:", fs.fragmentation("b.txt"))
print("FAT 表:", fs.fat)

複雜度與 I/O 成本分析#

  • 讀第 k 區塊：k 次表查詢（記憶體）+ 1 次磁碟 I/O；FAT 不在快取時最多 k 次 I/O。
  • 追加：O(鏈長) 走鏈 + O(表長) 找空閒 + 2 次寫 FAT。
  • 空間：FAT32 表本身 = 叢集總數 × 4 bytes；1TB 磁碟、32KB 叢集時約 128MB。
  • 碎片：FAT 的鏈結配置天然碎片化，大檔案連續寫入被夾在中間後就斷鏈——這是 7.3 節碎片整理的由來。

練習#

  1. 用 32 個叢集模擬：建立 3 個檔案、刪除中間檔案、再建立大檔案，計算新檔案的碎片度。
  2. 說明 FAT32 的「單檔 4GB 上限」是結構上的哪個限制造成的。
  3. 比較 FAT 與 inode（7.2 節）在「隨機讀取大檔案中段」的 I/O 次數差異。