第十章 文件系統(tǒng)

這部分主要是一些較高層的策略問題沃缘，主要是面向上層開發(fā)人員，而不涉及太多具體實(shí)現(xiàn)则吟。

1. 文件操作

1.1 基本操作集合

文件為抽象數(shù)據(jù)類型槐臀。操作系統(tǒng)提供 6 個系統(tǒng)調(diào)用構(gòu)成操作文件的最小集合，包括

• 創(chuàng)建 create逾滥，首先在文件系統(tǒng)中為文件找到空間峰档，其次，在目錄中創(chuàng)建新文件的條目
• 寫入 write寨昙，指定文件名稱和要寫入文件的信息讥巡，系統(tǒng)根據(jù)文件名稱搜索目錄已查找文件位置。系統(tǒng)應(yīng)維護(hù)寫指針舔哪，用于指向需要進(jìn)行下次寫操作的文件位置欢顷。寫的時候同時更新寫指針。
• 讀取 read捉蚤，指明文件名稱和文件的內(nèi)容應(yīng)讀到哪里抬驴。系統(tǒng)根據(jù)文件名稱定位文件內(nèi)容，同時需要維護(hù)一個讀指針缆巧，指向要進(jìn)行下一次讀取操作的文件位置布持。同樣，讀操作需要同時更新讀指針陕悬。

讀寫操作可以使用相同的指針题暖。稱為 當(dāng)前文件位置指針。這個指針的初始化受文件訪問模式影響捉超，APPEND 會置于末尾胧卤，否則是文件頭。

• 重新定位 seek拼岳，移動當(dāng)前文件位置指針到指定位置枝誊，不涉及實(shí)際 I/O 操作。
• 刪除 delete惜纸， 搜索給定文件名叶撒，找到對應(yīng)的目錄條目绝骚，釋放占用的文件空間，并刪除對應(yīng)條目痊乾。
• 截?cái)?truncate 文件皮壁。用戶可能想刪除文件的內(nèi)容，但保留它的屬性哪审。實(shí)際上就是只改動文件長度屬性蛾魄。

1.2 打開文件表

以上操作大多涉及搜索目錄，得到文件的相關(guān)條目湿滓，為了避免這種搜索滴须，OS 一般要求訪問文件前需要先 open()。OS 有個打開文件表叽奥，維護(hù)所有打開文件的信息扔水。如果不用了再 close()。create/delete 操作的是未 open() 的朝氓。
open() 函數(shù)返回一個文件句柄 (Windows) 或者稱為文件描述符 (UNIX-like)魔市，后續(xù)操作都以這個值作為指針，避免重復(fù)搜索赵哲。同時待德，open() 一般也支持訪問模式信息，如 CREATE, APPEND 等枫夺。OS 會根據(jù)文件系統(tǒng)的權(quán)限子系統(tǒng)檢查 open() 是否合法将宪。

文件系統(tǒng)的設(shè)計(jì)哲學(xué)顯然是一種 “有狀態(tài)” 通信。有狀態(tài)和無狀態(tài)的區(qū)別主要是是否單次操作需要攜帶所有必要信息橡庞。如果是無狀態(tài)较坛，那么每次都要指定文件名、訪問模式扒最、當(dāng)前文件指針等等丑勤，NFS 就是這么設(shè)計(jì)的；有狀態(tài)就得把狀態(tài)維護(hù)起來吧趣，放在一個數(shù)據(jù)結(jié)構(gòu)里确封，每次操作只需要攜帶一個指針以讓系統(tǒng)知道操作的是哪個項(xiàng)。這兩種設(shè)計(jì)哲學(xué)廣泛分布于計(jì)算機(jī)領(lǐng)域再菊，如 TCP 和 UDP，TCP 有狀態(tài)颜曾，每條鏈接的狀態(tài)信息由 OS 維護(hù)纠拔，而 UDP 每次讀寫數(shù)據(jù)互不干擾，OS 并沒有 UDP 的狀態(tài)信息（可能需要維護(hù)其它信息泛豪，如端口信息）

通常稠诲，OS 采用兩級內(nèi)部表：單獨(dú)進(jìn)程表 和 系統(tǒng)總表侦鹏。

• 單獨(dú)進(jìn)程表跟蹤進(jìn)程打開的所有文件，存儲了當(dāng)前文件位置指針臀叙、權(quán)限略水、訪問模式等信息。
• 系統(tǒng)表包含與進(jìn)程無關(guān)的信息劝萤，如文件在磁盤上的位置渊涝，mtime/ctime/atime，文件大小等床嫌。一旦進(jìn)程打開了一個文件就會產(chǎn)生一個條目跨释，如后續(xù)再有進(jìn)程 open()，只需要在打開計(jì)數(shù)上加 1 即可厌处。每次 close() 會減 1鳖谈，OS 會回收計(jì)數(shù)為 0 的條目。所以 open() 后的文件不用了一定要 close()阔涉。

1.3 同步

OS 可以提供強(qiáng)制 (Windows) 或建議(UNIX-like) 的文件鎖定機(jī)制缆娃。強(qiáng)制鎖會要求文件操作的所有 API 都檢查鎖，也即一個進(jìn)程加了鎖瑰排，OS 會確保其它進(jìn)程調(diào)用 open() 這類函數(shù)的時候會被阻塞贯要。這是一個內(nèi)核級別的實(shí)現(xiàn)。而建議鎖是指凶伙，一個進(jìn)程加了鎖郭毕，其它進(jìn)程需要主動去檢查這個鎖的狀態(tài)，再決定是否操作文件函荣。Linux 文件鎖 的實(shí)現(xiàn)可以參考這篇文章显押。
Java 實(shí)現(xiàn)文件互斥訪問時通過要訪問文件的 FileChannel 的 lock() 取得 FileLock 來做得。FileLock 支持共享和非共享傻挂，同時支持字節(jié)級別的鎖定乘碑。

public abstract FileLock lock(long position, long size, boolean shared)
        throws IOException;

2. 文件類型與結(jié)構(gòu)

實(shí)現(xiàn)文件類型的常見技術(shù)是將類型作為文件名的一部分，即放在擴(kuò)展名里金拒。UNIX 系統(tǒng)采用位于某些文件開始部分的魔數(shù)（magic number）大致表明文件類型兽肤，但不是所有文件都有魔數(shù)。Linux 的可執(zhí)行文件是依賴于其執(zhí)行權(quán)限而不是拓展名绪抛。所以綜上资铡，文件類型的區(qū)分方法千奇百怪。
文件類型決定文件結(jié)構(gòu)幢码。OS 必須支持至少一種結(jié)構(gòu)笤休，即可執(zhí)行文件的結(jié)構(gòu)，以便系統(tǒng)能加載和運(yùn)行程序症副。但是店雅，OS 一般也不應(yīng)該規(guī)定太多文件結(jié)構(gòu)政基，誰支持誰就得負(fù)責(zé)，這個讓 OS 來做 OS 就很虧闹啦。

Linux 大致有這些文件類型：普通文件沮明、目錄、字符設(shè)備窍奋、塊設(shè)備荐健、套接字、符號鏈接

3. 訪問方法

• 順序訪問
  文件信息按順序加以處理费变，編輯器和編譯器通常以這種方式訪問文件摧扇。適合磁帶
• 直接訪問
  文件由固定長度的邏輯記錄組成，以允許程序按任意順序進(jìn)行隨機(jī)訪問挚歧。數(shù)據(jù)庫通常是這種類型的扛稽。直接訪問可以由順序訪問進(jìn)行模擬，但是效率低下滑负。適合磁盤等在张。
• 其它訪問方法
  其它訪問方法通常建立在直接訪問之上，并涉及建立文件索引“剑現(xiàn)代通用 OS 都是這種帮匾。

4. 目錄與磁盤的結(jié)構(gòu)

文件系統(tǒng)底層是磁盤，向上提供前面提到的 API痴鳄，那么必須維護(hù)目錄來組織這些文件瘟斜。

4.1 一些概念

1. 磁盤 磁盤是一塊單獨(dú)的物理設(shè)備
2. 分區(qū) 磁盤格式化后才能使用，格式化實(shí)際上就是對磁盤進(jìn)行分區(qū)痪寻，分為不同的部分螺句，每個部分有些元數(shù)據(jù)表明物理存儲的一些信息，也就是文件系統(tǒng)的元數(shù)據(jù)橡类。按傳統(tǒng)分區(qū)技術(shù)蛇尚，分區(qū)一般分為主分區(qū)和擴(kuò)展分區(qū)升薯；分區(qū)表格式有主引導(dǎo)分區(qū)（Master Boot Record, MBR栗涂，已逐漸淘汰) 和 GPT（GUID Partition Table) 分區(qū)杆怕。比如 Windows 的 C 盤办铡、D 盤就是分完區(qū)后的結(jié)果。詳見鳥哥的 Linux 私房菜磁盤部分
3. 文件系統(tǒng) 文件系統(tǒng)和分區(qū)不是一個概念矢劲，分區(qū)一般說的是物理存儲設(shè)備邀杏，文件系統(tǒng)是描述存儲設(shè)備的內(nèi)容格式驰徊。
4. LVM Logical Volume Manager Linux 下的邏輯卷管理器庶诡，向上屏蔽掉底層物理磁盤的細(xì)節(jié)虾标。實(shí)際上就是讓 OS 能操作多塊磁盤以及支持?jǐn)U容、縮容等操作。傳統(tǒng)分區(qū)有很多限制璧函。

LVM

PV(Physical Volume)：物理卷，處于LVM最底層基显，可以是物理硬盤或者分區(qū)蘸吓。
PE(Physical Extend)：物理區(qū)域，PV中可以用于分配的最小存儲單元撩幽，可以在創(chuàng)建PV的時候制定（默認(rèn)為4MB）库继，如1M, 2M, 4M, 8M, 32M, 64M…組成同一VG中所有PV的PE大小應(yīng)該相同。
VG(Volume Group)：卷組窜醉，建立在PV之上宪萄，可以含有一個到多個PV。
LV(Logical Volume)：邏輯卷榨惰，建立在VG之上拜英，相當(dāng)于原來分區(qū)的概念。不過大小可以動態(tài)改變琅催。

5. VFS Linux 支持多種文件系統(tǒng)居凶，為了屏蔽底層細(xì)節(jié)，VFS 扮演了中間層的角色

4.2 目錄

目錄（directory）可以理解為一個字典藤抡，記錄的是文件名到磁盤存儲位置的映射侠碧。目錄可以分為單級目錄、兩級目錄缠黍、樹形目錄（主流目錄結(jié)構(gòu)）弄兜、無環(huán)圖目錄（為了共享子目錄）。

UNIX-Like 既支持基于軟鏈接的共享瓷式，這個時候文件系統(tǒng)并不把軟連解當(dāng)作實(shí)際節(jié)點(diǎn)替饿，刪了之后也依然保留，需要程序員自己意識到被刪了蒿往；也支持基于硬鏈接的共享盛垦，后者修改了 inode 的內(nèi)容，會由文件系統(tǒng)管理節(jié)點(diǎn)瓤漏。詳見相關(guān)博客腾夯。

4.3 文件系統(tǒng)掛載

文件系統(tǒng)在使用前得先掛在到某個目錄，掛載位置稱為掛載點(diǎn)蔬充，被掛載的稱為設(shè)備蝶俱。比如, Linux 中，/home 一般是個單獨(dú)的分區(qū)饥漫，內(nèi)核會在啟動的時候?qū)⑵鋻燧d到根目錄下的 /home 處榨呆。然后我們才可以通過 /home/test.c 直接訪問 test.c 文件。

Linux 默認(rèn)只有一個分區(qū)庸队，即 /积蜻，這個分區(qū)上運(yùn)行著發(fā)行版默認(rèn)的文件系統(tǒng)闯割。這個 / 里面可以裝文件，也可以掛載其它文件系統(tǒng)竿拆。這里首先得認(rèn)識到 OS 目錄樹和文件系統(tǒng)不是一個概念宙拉。你可以在 /test1 掛載一個 ext3 文件系統(tǒng)，可以在 /test2 掛載一個 xfs 文件系統(tǒng)丙笋，可以在 /test3 放一個普通文件谢澈。掛載可以看作根目錄的某個節(jié)點(diǎn)被另外一顆樹替代。Windows 會在啟動時自動安裝所有文件系統(tǒng)（卷 C, D...)御板，如果我們插入 U 盤锥忿，Windows 會識別并把 U 盤掛載到目錄樹上，只不過這個目錄樹是兩級的怠肋。Linux 的掛載點(diǎn)一般可以是任何位置敬鬓，Windows 的新版本似乎也可以，但不清楚灶似。

4.4 保護(hù)

UNIX-like 文件系統(tǒng)的一般權(quán)限 和 SUID, SGID, SBIT等

第十一章 文件系統(tǒng)實(shí)現(xiàn)

1. 文件系統(tǒng)的結(jié)構(gòu)

文件系統(tǒng)一般分層實(shí)現(xiàn)列林，從上往下：

• 邏輯文件系統(tǒng)。管理元數(shù)據(jù)信息酪惭，包括文件系統(tǒng)的所有結(jié)構(gòu)希痴，但不包括實(shí)際數(shù)據(jù)。通過文件控制塊（File Control Block, FCB) 包含文件的信息春感，如權(quán)限砌创、位置等
• 文件組織模塊。負(fù)責(zé)映射文件的邏輯塊到物理塊地址鲫懒。每個文件的邏輯塊是連續(xù)編號的嫩实，但是物理塊不是。
• 基本文件系統(tǒng)窥岩。負(fù)責(zé)向設(shè)備驅(qū)動程序發(fā)送命令甲献，讀寫物理塊，維護(hù)緩存等颂翼。
• I/O 控制晃洒。負(fù)責(zé)底層硬件通信

內(nèi)存和磁盤之間的 I/O 以塊 (block) 為單位，塊的大小與磁盤扇區(qū)大小無關(guān)朦乏。同時球及，上述模塊在實(shí)際實(shí)現(xiàn)中可能揉在一起。

2. 文件系統(tǒng)的實(shí)現(xiàn)

2.1 元數(shù)據(jù)

首先考慮一下文件系統(tǒng)需要維護(hù)哪些信息呻疹。分別從磁盤上和內(nèi)存中來考慮（下述不區(qū)分卷和分區(qū)的概念吃引，因?yàn)榫韺?shí)際上就是個邏輯分區(qū)）:

2.1.1 磁盤上

• 每個分區(qū)的引導(dǎo)控制塊 (boot control block)。如果分區(qū)不包含 OS，則這塊為空镊尺，也即一個 OS 有多個分區(qū)朦佩。它通常為卷的第一塊，有自己的格式鹅心。因?yàn)樵谝龑?dǎo)式系統(tǒng)沒有加載文件系統(tǒng)代碼吕粗，不能解釋文件系統(tǒng)的格式。每個分區(qū)都可以有引導(dǎo)控制塊旭愧，這是多重引導(dǎo)，即多系統(tǒng)的基礎(chǔ)宙暇。個人感覺這部分不屬于文件系統(tǒng)的一部分输枯。

BIOS/UEFI 是啟動檢測程序。他們運(yùn)行后占贫，會去讀 MBR/GPT 分區(qū)桃熄，然后 MBR/GPT 分區(qū)可以直接加載內(nèi)核文件來啟動 OS，也可以將控制流轉(zhuǎn)到其它引導(dǎo)控制塊型奥。

• 分區(qū)控制塊瞳收。存儲了分區(qū)內(nèi)的詳細(xì)信息，如分區(qū)內(nèi)的塊的數(shù)量厢汹、大小螟深、空閑塊和指針、空閑的 FCB 數(shù)量和指針等烫葬。也即 UNIX-like 中的超級塊 (superblock)
• 目錄結(jié)構(gòu)界弧。在 Linux 中，包括文件名和 inode 號碼搭综。
• 每個文件的 FCB 包括該文件的許多詳細(xì)信息垢箕。也即 Linux 中的 inode。

2.1.2 內(nèi)存中

• 掛載表兑巾。包含設(shè)備的掛載信息条获，條目包括一個指向該設(shè)備的文件系統(tǒng)超級塊的指針。
• 目錄結(jié)構(gòu)緩存蒋歌。
• 系統(tǒng)打開文件表帅掘。
• 進(jìn)程打開文件表。
• 緩沖區(qū)奋姿。保存文件系統(tǒng)的塊锄开。

2.2 操作函數(shù)

2.2.1 創(chuàng)建文件/文件夾

創(chuàng)建文件時，應(yīng)用程序調(diào)用邏輯文件系統(tǒng)称诗，由其分配一個新的 FCB萍悴。如果文件系統(tǒng)的實(shí)現(xiàn)在文件系統(tǒng)創(chuàng)建時（格式化的時候）已經(jīng)創(chuàng)建了所有 FCB，如 ext 文件系統(tǒng)，則可從空閑的 FCB 集合中分配一個可用的 FCB癣诱。然后邏輯文件系統(tǒng)用文件名和新的 FCB 去更新其對應(yīng)的目錄文件计维，并寫回磁盤，這個過程會調(diào)用下面的文件組織模塊撕予。
UNIX 不區(qū)分文件和文件目錄的處理鲫惶，而 Windows 提供兩套系統(tǒng)調(diào)用。

2.2.2 打開文件

文件使用前需要先打開实抡。open() 首先需要搜索系統(tǒng)打開文件表查詢是否已經(jīng)打開欠母，如是，直接在進(jìn)程打開文件表中新建條目并指向系統(tǒng)打開表中的條目吆寨，同時更新計(jì)數(shù)赏淌；否則，需要搜索文件所在目錄啄清，這個通常緩存在內(nèi)存中六水，找到文件后，將其 FCB 復(fù)制到系統(tǒng)打開文件表辣卒，并在進(jìn)程打開文件表中重復(fù)前面相同的動作掷贾。
進(jìn)程打開文件表中的條目一般包含一個指針指向系統(tǒng)表，所有文件操作通過這個指針進(jìn)行荣茫，所以文件表不需要包含文件名想帅，因?yàn)榭梢酝ㄟ^指針訪問 FCB。這個在 UNIX 中稱為 文件描述符（file descriptor)计露，在 Windows 中稱為 文件句柄 (file handle)博脑。

2.2.3 讀寫文件

讀文件需要指定文件描述符，然后內(nèi)核訪問進(jìn)程的打開文件表票罐，獲取系統(tǒng)打開文件表的索引叉趣，再根據(jù)系統(tǒng)文件表中存儲的 FCB（可能在內(nèi)存中也可能是一個指向磁盤的指針），然后獲取文件的元數(shù)據(jù)该押，包括數(shù)據(jù)存儲位置疗杉、當(dāng)前位置指針等。然后向下發(fā)送讀取指令蚕礼，最后由 I/O 設(shè)備完成讀取烟具。讀到的內(nèi)容放入指定的緩沖中。
寫文件類似奠蹬，只不過一般都是寫緩沖朝聋，落盤的策略一般由文件系統(tǒng)自行安排或者應(yīng)用程序手動調(diào)用 fsync。

2.2.4 關(guān)閉文件

關(guān)閉文件需要刪除進(jìn)程打開文件表中的條目囤躁，并遞減系統(tǒng)打開文件表中的計(jì)數(shù)冀痕。當(dāng)所有打開該文件的用戶關(guān)閉它時荔睹，任何更新的元數(shù)據(jù)落盤，并且刪除系統(tǒng)表中的條目言蛇。

2.3 分區(qū)與掛載

分區(qū)并不一定得有文件系統(tǒng)僻他，沒有格式化的分區(qū)也可以使用，稱為裸盤腊尚，原始磁盤 (raw disk)吨拗。例如，UNIX 的交換空間就是使用的裸盤婿斥，數(shù)據(jù)庫也經(jīng)常使用劝篷。
根分區(qū)，包括 OS 內(nèi)核和其它系統(tǒng)文件在啟動時掛載民宿。其它卷可以在引導(dǎo)時自動掛載或在啟動后手動掛載携龟，取決于 OS。
掛載的實(shí)現(xiàn)一般時標(biāo)記某個 FCB 為掛載點(diǎn)勘高，同時在其里寫入安裝表中條目的指針，即完成掛載坟桅。

2.4 虛擬文件系統(tǒng)

VFS 實(shí)際上就是 OOP 技術(shù)的一種體現(xiàn)华望，通過中間層來屏蔽底層多種實(shí)現(xiàn)。

3. 目錄實(shí)現(xiàn)

• 線性表仅乓。主要是復(fù)雜度偏高
• 哈希表赖舟。主要是擴(kuò)容，可能需要借助一致性哈希算法
• 平衡樹夸楣。

4. 分配方法

4.1 連續(xù)分配

連續(xù)分配的好處是宾抓，簡單，支持順序訪問和直接訪問豫喧，對于磁盤結(jié)構(gòu)石洗，讀取效率高。缺點(diǎn)是紧显，本質(zhì)上是一個動態(tài)存儲分配問題讲衫，也就存在這類型問題的所有問題，如外部碎片孵班，如何快速找到一個最好的可用分配涉兽，文件增大怎么做篙程。
外部碎片可以通過復(fù)制-整理算法來做枷畏，這個技術(shù)在垃圾回收算法中常用。存在 STW 問題虱饿，而且需要額外存儲空間來做整理拥诡。文件增大一般通過擴(kuò)展來解決触趴，即一開始先分配一塊，如果增大袋倔，再分配一塊雕蔽，第一塊鏈接到后一塊上。

4.2 鏈接分配

鏈接分配解決了上述所有問題宾娜，但是不能有效支持文件的隨機(jī)訪問批狐。順序訪問的情況下，與索引分配一樣前塔，對于磁盤結(jié)構(gòu)嚣艇，可能效率低下，因?yàn)橐煌ＰD(zhuǎn)磁盤頭华弓。同時食零，因?yàn)殒溄又羔樞枰臻g，所以有效存儲率變低了寂屏。
鏈接分配的一個重要變種就是文件分配表（File Allocation Table, FAT)贰谣，廣泛用于 MS-DOS。每個卷的開頭部分的磁盤存儲一張表迁霎，表里存儲了卷上的所有塊的指針吱抚，從而解決隨機(jī)訪問的問題。

4.3 索引分配

索引分配將所有指針放在一起形成索引塊考廉，解決隨機(jī)訪問的問題秘豹。每個 FCB 里存儲了各自的索引塊。
UNIX 文件系統(tǒng)使用一種組合策略來優(yōu)化索引的存儲昌粤，inode 的前12 個指針是直接索引既绕，直接指向文件的數(shù)據(jù)塊的地址；接下來的 3 個指針指向間接塊涮坐，分別是一級間接塊凄贩、二級間接塊、三級間接塊膊升，對應(yīng)二級怎炊、三級、四級索引廓译。

5. 空閑空間管理

為了跟蹤空閑磁盤空間评肆，需要維護(hù)一個空閑空間列表。創(chuàng)建和刪除文件塊都需要修改這個空閑空間列表非区。一般通過位圖來實(shí)現(xiàn)瓜挽，例如 UNIX；也可以通過鏈表等征绸。

后面還包括對效率久橙、性能俄占、恢復(fù)、一致性淆衷、NFS 的討論缸榄，這里不再總結(jié)。