前言

不多 BB，直接上「硬菜」。

正文

文件系統(tǒng)的基本組成

文件系統(tǒng)是操作系統(tǒng)中負(fù)責(zé)管理持久數(shù)據(jù)的子系統(tǒng)，說簡單點(diǎn)，就是負(fù)責(zé)把用戶的文件存到磁盤硬件中，因?yàn)榧词褂?jì)算機(jī)斷電了，磁盤里的數(shù)據(jù)并不會(huì)丟失，所以可以持久化的保存文件。

文件系統(tǒng)的基本數(shù)據(jù)單位是文件，它的目的是對(duì)磁盤上的文件進(jìn)行組織管理，那組織的方式不同，就會(huì)形成不同的文件系統(tǒng)。

Linux 最經(jīng)典的一句話是：「一切皆文件」，不僅普通的文件和目錄，就連塊設(shè)備、管道、socket 等，也都是統(tǒng)一交給文件系統(tǒng)管理的。

Linux 文件系統(tǒng)會(huì)為每個(gè)文件分配兩個(gè)數(shù)據(jù)結(jié)構(gòu)：索引節(jié)點(diǎn)（index node）和目錄項(xiàng)（directory entry），它們主要用來記錄文件的元信息和目錄層次結(jié)構(gòu)。

• 索引節(jié)點(diǎn)，也就是 inode，用來記錄文件的元信息，比如 inode 編號(hào)、文件大小、訪問權(quán)限、創(chuàng)建時(shí)間、修改時(shí)間、數(shù)據(jù)在磁盤的位置等等。索引節(jié)點(diǎn)是文件的唯一標(biāo)識(shí)，它們之間一一對(duì)應(yīng)，也同樣都會(huì)被存儲(chǔ)在硬盤中，所以索引節(jié)點(diǎn)同樣占用磁盤空間。

• 目錄項(xiàng)，也就是 dentry，用來記錄文件的名字、索引節(jié)點(diǎn)指針以及與其他目錄項(xiàng)的層級(jí)關(guān)聯(lián)關(guān)系。多個(gè)目錄項(xiàng)關(guān)聯(lián)起來，就會(huì)形成目錄結(jié)構(gòu)，但它與索引節(jié)點(diǎn)不同的是，目錄項(xiàng)是由內(nèi)核維護(hù)的一個(gè)數(shù)據(jù)結(jié)構(gòu)，不存放于磁盤，而是緩存在內(nèi)存。

由于索引節(jié)點(diǎn)唯一標(biāo)識(shí)一個(gè)文件，而目錄項(xiàng)記錄著文件的名，所以目錄項(xiàng)和索引節(jié)點(diǎn)的關(guān)系是多對(duì)一，也就是說，一個(gè)文件可以有多個(gè)別字。比如，硬鏈接的實(shí)現(xiàn)就是多個(gè)目錄項(xiàng)中的索引節(jié)點(diǎn)指向同一個(gè)文件。

注意，目錄也是文件，也是用索引節(jié)點(diǎn)唯一標(biāo)識(shí)，和普通文件不同的是，普通文件在磁盤里面保存的是文件數(shù)據(jù)，而目錄文件在磁盤里面保存子目錄或文件。

目錄項(xiàng)和目錄是一個(gè)東西嗎？

雖然名字很相近，但是它們不是一個(gè)東西，目錄是個(gè)文件，持久化存儲(chǔ)在磁盤，而目錄項(xiàng)是內(nèi)核一個(gè)數(shù)據(jù)結(jié)構(gòu)，緩存在內(nèi)存。

如果查詢目錄頻繁從磁盤讀，效率會(huì)很低，所以內(nèi)核會(huì)把已經(jīng)讀過的目錄用目錄項(xiàng)這個(gè)數(shù)據(jù)結(jié)構(gòu)緩存在內(nèi)存，下次再次讀到相同的目錄時(shí)，只需從內(nèi)存讀就可以，大大提高了文件系統(tǒng)的效率。

注意，目錄項(xiàng)這個(gè)數(shù)據(jù)結(jié)構(gòu)不只是表示目錄，也是可以表示文件的。

那文件數(shù)據(jù)是如何存儲(chǔ)在磁盤的呢？

磁盤讀寫的最小單位是扇區(qū)，扇區(qū)的大小只有 512B 大小，很明顯，如果每次讀寫都以這么小為單位，那這讀寫的效率會(huì)非常低。

所以，文件系統(tǒng)把多個(gè)扇區(qū)組成了一個(gè)邏輯塊，每次讀寫的最小單位就是邏輯塊（數(shù)據(jù)塊），Linux 中的邏輯塊大小為 4KB，也就是一次性讀寫 8 個(gè)扇區(qū)，這將大大提高了磁盤的讀寫的效率。

以上就是索引節(jié)點(diǎn)、目錄項(xiàng)以及文件數(shù)據(jù)的關(guān)系，下面這個(gè)圖就很好的展示了它們之間的關(guān)系：

索引節(jié)點(diǎn)是存儲(chǔ)在硬盤上的數(shù)據(jù)，那么為了加速文件的訪問，通常會(huì)把索引節(jié)點(diǎn)加載到內(nèi)存中。

另外，磁盤進(jìn)行格式化的時(shí)候，會(huì)被分成三個(gè)存儲(chǔ)區(qū)域，分別是超級(jí)塊、索引節(jié)點(diǎn)區(qū)和數(shù)據(jù)塊區(qū)。

• 超級(jí)塊，用來存儲(chǔ)文件系統(tǒng)的詳細(xì)信息，比如塊個(gè)數(shù)、塊大小、空閑塊等等。

• 索引節(jié)點(diǎn)區(qū)，用來存儲(chǔ)索引節(jié)點(diǎn)；

• 數(shù)據(jù)塊區(qū)，用來存儲(chǔ)文件或目錄數(shù)據(jù)；

我們不可能把超級(jí)塊和索引節(jié)點(diǎn)區(qū)全部加載到內(nèi)存，這樣內(nèi)存肯定撐不住，所以只有當(dāng)需要使用的時(shí)候，才將其加載進(jìn)內(nèi)存，它們加載進(jìn)內(nèi)存的時(shí)機(jī)是不同的：

• 超級(jí)塊：當(dāng)文件系統(tǒng)掛載時(shí)進(jìn)入內(nèi)存；

• 索引節(jié)點(diǎn)區(qū)：當(dāng)文件被訪問時(shí)進(jìn)入內(nèi)存；

虛擬文件系統(tǒng)

文件系統(tǒng)的種類眾多，而操作系統(tǒng)希望對(duì)用戶提供一個(gè)統(tǒng)一的接口，于是在用戶層與文件系統(tǒng)層引入了中間層，這個(gè)中間層就稱為虛擬文件系統(tǒng)（Virtual File System，VFS）。

VFS 定義了一組所有文件系統(tǒng)都支持的數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)接口，這樣程序員不需要了解文件系統(tǒng)的工作原理，只需要了解 VFS 提供的統(tǒng)一接口即可。

在 Linux 文件系統(tǒng)中，用戶空間、系統(tǒng)調(diào)用、虛擬機(jī)文件系統(tǒng)、緩存、文件系統(tǒng)以及存儲(chǔ)之間的關(guān)系如下圖：

Linux 支持的文件系統(tǒng)也不少，根據(jù)存儲(chǔ)位置的不同，可以把文件系統(tǒng)分為三類：

• 磁盤的文件系統(tǒng)，它是直接把數(shù)據(jù)存儲(chǔ)在磁盤中，比如 Ext 2/3/4、XFS 等都是這類文件系統(tǒng)。

• 內(nèi)存的文件系統(tǒng)，這類文件系統(tǒng)的數(shù)據(jù)不是存儲(chǔ)在硬盤的，而是占用內(nèi)存空間，我們經(jīng)常用到的 /proc 和 /sys 文件系統(tǒng)都屬于這一類，讀寫這類文件，實(shí)際上是讀寫內(nèi)核中相關(guān)的數(shù)據(jù)數(shù)據(jù)。

• 網(wǎng)絡(luò)的文件系統(tǒng)，用來訪問其他計(jì)算機(jī)主機(jī)數(shù)據(jù)的文件系統(tǒng)，比如 NFS、SMB 等等。

文件系統(tǒng)首先要先掛載到某個(gè)目錄才可以正常使用，比如 Linux 系統(tǒng)在啟動(dòng)時(shí)，會(huì)把文件系統(tǒng)掛載到根目錄。

文件的使用

我們從用戶角度來看文件的話，就是我們要怎么使用文件？首先，我們得通過系統(tǒng)調(diào)用來打開一個(gè)文件。

fd = open(name, flag); # 打開文件
...
write(fd,...);         # 寫數(shù)據(jù)
...
close(fd);             # 關(guān)閉文件

上面簡單的代碼是讀取一個(gè)文件的過程：

• 首先用 open 系統(tǒng)調(diào)用打開文件，open 的參數(shù)中包含文件的路徑名和文件名。

• 使用 write 寫數(shù)據(jù)，其中 write 使用 open 所返回的文件描述符，并不使用文件名作為參數(shù)。

• 使用完文件后，要用 close 系統(tǒng)調(diào)用關(guān)閉文件，避免資源的泄露。

我們打開了一個(gè)文件后，操作系統(tǒng)會(huì)跟蹤進(jìn)程打開的所有文件，所謂的跟蹤呢，就是操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一個(gè)打開文件表，文件表里的每一項(xiàng)代表「文件描述符」，所以說文件描述符是打開文件的標(biāo)識(shí)。

操作系統(tǒng)在打開文件表中維護(hù)著打開文件的狀態(tài)和信息：

• 文件指針：系統(tǒng)跟蹤上次讀寫位置作為當(dāng)前文件位置指針，這種指針對(duì)打開文件的某個(gè)進(jìn)程來說是唯一的；

• 文件打開計(jì)數(shù)器：文件關(guān)閉時(shí)，操作系統(tǒng)必須重用其打開文件表?xiàng)l目，否則表內(nèi)空間不夠用。因?yàn)槎鄠€(gè)進(jìn)程可能打開同一個(gè)文件，所以系統(tǒng)在刪除打開文件條目之前，必須等待最后一個(gè)進(jìn)程關(guān)閉文件，該計(jì)數(shù)器跟蹤打開和關(guān)閉的數(shù)量，當(dāng)該計(jì)數(shù)為 0 時(shí)，系統(tǒng)關(guān)閉文件，刪除該條目；

• 文件磁盤位置：絕大多數(shù)文件操作都要求系統(tǒng)修改文件數(shù)據(jù)，該信息保存在內(nèi)存中，以免每個(gè)操作都從磁盤中讀??；

• 訪問權(quán)限：每個(gè)進(jìn)程打開文件都需要有一個(gè)訪問模式（創(chuàng)建、只讀、讀寫、添加等），該信息保存在進(jìn)程的打開文件表中，以便操作系統(tǒng)能允許或拒絕之后的 I/O 請(qǐng)求；

在用戶視角里，文件就是一個(gè)持久化的數(shù)據(jù)結(jié)構(gòu)，但操作系統(tǒng)并不會(huì)關(guān)心你想存在磁盤上的任何的數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)的視角是如何把文件數(shù)據(jù)和磁盤塊對(duì)應(yīng)起來。

所以，用戶和操作系統(tǒng)對(duì)文件的讀寫操作是有差異的，用戶習(xí)慣以字節(jié)的方式讀寫文件，而操作系統(tǒng)則是以數(shù)據(jù)塊來讀寫文件，那屏蔽掉這種差異的工作就是文件系統(tǒng)了。

我們來分別看一下，讀文件和寫文件的過程：

• 當(dāng)用戶進(jìn)程從文件讀取 1 個(gè)字節(jié)大小的數(shù)據(jù)時(shí)，文件系統(tǒng)則需要獲取字節(jié)所在的數(shù)據(jù)塊，再返回?cái)?shù)據(jù)塊對(duì)應(yīng)的用戶進(jìn)程所需的數(shù)據(jù)部分。

• 當(dāng)用戶進(jìn)程把 1 個(gè)字節(jié)大小的數(shù)據(jù)寫進(jìn)文件時(shí)，文件系統(tǒng)則找到需要寫入數(shù)據(jù)的數(shù)據(jù)塊的位置，然后修改數(shù)據(jù)塊中對(duì)應(yīng)的部分，最后再把數(shù)據(jù)塊寫回磁盤。

所以說，文件系統(tǒng)的基本操作單位是數(shù)據(jù)塊。

文件的存儲(chǔ)

文件的數(shù)據(jù)是要存儲(chǔ)在硬盤上面的，數(shù)據(jù)在磁盤上的存放方式，就像程序在內(nèi)存中存放的方式那樣，有以下兩種：

• 連續(xù)空間存放方式

• 非連續(xù)空間存放方式

其中，非連續(xù)空間存放方式又可以分為「鏈表方式」和「索引方式」。

不同的存儲(chǔ)方式，有各自的特點(diǎn)，重點(diǎn)是要分析它們的存儲(chǔ)效率和讀寫性能，接下來分別對(duì)每種存儲(chǔ)方式說一下。

連續(xù)空間存放方式

連續(xù)空間存放方式顧名思義，文件存放在磁盤「連續(xù)的」物理空間中。這種模式下，文件的數(shù)據(jù)都是緊密相連，讀寫效率很高，因?yàn)橐淮未疟P尋道就可以讀出整個(gè)文件。

使用連續(xù)存放的方式有一個(gè)前提，必須先知道一個(gè)文件的大小，這樣文件系統(tǒng)才會(huì)根據(jù)文件的大小在磁盤上找到一塊連續(xù)的空間分配給文件。

所以，文件頭里需要指定「起始?jí)K的位置」和「長度」，有了這兩個(gè)信息就可以很好的表示文件存放方式是一塊連續(xù)的磁盤空間。

注意，此處說的文件頭，就類似于 Linux 的 inode。

連續(xù)空間存放的方式雖然讀寫效率高，但是有「磁盤空間碎片」和「文件長度不易擴(kuò)展」的缺陷。

如下圖，如果文件 B 被刪除，磁盤上就留下一塊空缺，這時(shí)，如果新來的文件小于其中的一個(gè)空缺，我們就可以將其放在相應(yīng)空缺里。但如果該文件的大小大于所有的空缺，但卻小于空缺大小之和，則雖然磁盤上有足夠的空缺，但該文件還是不能存放。當(dāng)然了，我們可以通過將現(xiàn)有文件進(jìn)行挪動(dòng)來騰出空間以容納新的文件，但是這個(gè)在磁盤挪動(dòng)文件是非常耗時(shí)，所以這種方式不太現(xiàn)實(shí)。

另外一個(gè)缺陷是文件長度擴(kuò)展不方便，例如上圖中的文件 A 要想擴(kuò)大一下，需要更多的磁盤空間，唯一的辦法就只能是挪動(dòng)的方式，前面也說了，這種方式效率是非常低的。

那么有沒有更好的方式來解決上面的問題呢？答案當(dāng)然有，既然連續(xù)空間存放的方式不太行，那么我們就改變存放的方式，使用非連續(xù)空間存放方式來解決這些缺陷。

非連續(xù)空間存放方式

非連續(xù)空間存放方式分為「鏈表方式」和「索引方式」。

我們先來看看鏈表的方式。

鏈表的方式存放是離散的，不用連續(xù)的，于是就可以消除磁盤碎片，可大大提高磁盤空間的利用率，同時(shí)文件的長度可以動(dòng)態(tài)擴(kuò)展。根據(jù)實(shí)現(xiàn)的方式的不同，鏈表可分為「隱式鏈表」和「顯式鏈接」兩種形式。

文件要以「隱式鏈表」的方式存放的話，實(shí)現(xiàn)的方式是文件頭要包含「第一塊」和「最后一塊」的位置，并且每個(gè)數(shù)據(jù)塊里面留出一個(gè)指針空間，用來存放下一個(gè)數(shù)據(jù)塊的位置，這樣一個(gè)數(shù)據(jù)塊連著一個(gè)數(shù)據(jù)塊，從鏈頭開是就可以順著指針找到所有的數(shù)據(jù)塊，所以存放的方式可以是不連續(xù)的。

隱式鏈表的存放方式的缺點(diǎn)在于無法直接訪問數(shù)據(jù)塊，只能通過指針順序訪問文件，以及數(shù)據(jù)塊指針消耗了一定的存儲(chǔ)空間。隱式鏈接分配的穩(wěn)定性較差，系統(tǒng)在運(yùn)行過程中由于軟件或者硬件錯(cuò)誤導(dǎo)致鏈表中的指針丟失或損壞，會(huì)導(dǎo)致文件數(shù)據(jù)的丟失。

如果取出每個(gè)磁盤塊的指針，把它放在內(nèi)存的一個(gè)表中，就可以解決上述隱式鏈表的兩個(gè)不足。那么，這種實(shí)現(xiàn)方式是「顯式鏈接」，它指把用于鏈接文件各數(shù)據(jù)塊的指針，顯式地存放在內(nèi)存的一張鏈接表中，該表在整個(gè)磁盤僅設(shè)置一張，每個(gè)表項(xiàng)中存放鏈接指針，指向下一個(gè)數(shù)據(jù)塊號(hào)。

對(duì)于顯式鏈接的工作方式，我們舉個(gè)例子，文件 A 依次使用了磁盤塊 4、7、2、10 和 12 ，文件 B 依次使用了磁盤塊 6、3、11 和 14 。利用下圖中的表，可以從第 4 塊開始，順著鏈走到最后，找到文件 A 的全部磁盤塊。同樣，從第 6 塊開始，順著鏈走到最后，也能夠找出文件 B 的全部磁盤塊。最后，這兩個(gè)鏈都以一個(gè)不屬于有效磁盤編號(hào)的特殊標(biāo)記（如 -1 ）結(jié)束。內(nèi)存中的這樣一個(gè)表格稱為文件分配表（File Allocation Table，F(xiàn)AT）。

由于查找記錄的過程是在內(nèi)存中進(jìn)行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。但也正是整個(gè)表都存放在內(nèi)存中的關(guān)系，它的主要的缺點(diǎn)是不適用于大磁盤。

比如，對(duì)于 200GB 的磁盤和 1KB 大小的塊，這張表需要有 2 億項(xiàng)，每一項(xiàng)對(duì)應(yīng)于這 2 億個(gè)磁盤塊中的一個(gè)塊，每項(xiàng)如果需要 4 個(gè)字節(jié)，那這張表要占用 800MB 內(nèi)存，很顯然 FAT 方案對(duì)于大磁盤而言不太合適。

接下來，我們來看看索引的方式。

鏈表的方式解決了連續(xù)分配的磁盤碎片和文件動(dòng)態(tài)擴(kuò)展的問題，但是不能有效支持直接訪問（FAT除外），索引的方式可以解決這個(gè)問題。

索引的實(shí)現(xiàn)是為每個(gè)文件創(chuàng)建一個(gè)「索引數(shù)據(jù)塊」，里面存放的是指向文件數(shù)據(jù)塊的指針列表，說白了就像書的目錄一樣，要找哪個(gè)章節(jié)的內(nèi)容，看目錄查就可以。

另外，文件頭需要包含指向「索引數(shù)據(jù)塊」的指針，這樣就可以通過文件頭知道索引數(shù)據(jù)塊的位置，再通過索引數(shù)據(jù)塊里的索引信息找到對(duì)應(yīng)的數(shù)據(jù)塊。

創(chuàng)建文件時(shí)，索引塊的所有指針都設(shè)為空。當(dāng)首次寫入第 i 塊時(shí)，先從空閑空間中取得一個(gè)塊，再將其地址寫到索引塊的第 i 個(gè)條目。

索引的方式優(yōu)點(diǎn)在于：

• 文件的創(chuàng)建、增大、縮小很方便；

• 不會(huì)有碎片的問題；

• 支持順序讀寫和隨機(jī)讀寫；

由于索引數(shù)據(jù)也是存放在磁盤塊的，如果文件很小，明明只需一塊就可以存放的下，但還是需要額外分配一塊來存放索引數(shù)據(jù)，所以缺陷之一就是存儲(chǔ)索引帶來的開銷。

如果文件很大，大到一個(gè)索引數(shù)據(jù)塊放不下索引信息，這時(shí)又要如何處理大文件的存放呢？我們可以通過組合的方式，來處理大文件的存。

先來看看鏈表 + 索引的組合，這種組合稱為「鏈?zhǔn)剿饕龎K」，它的實(shí)現(xiàn)方式是在索引數(shù)據(jù)塊留出一個(gè)存放下一個(gè)索引數(shù)據(jù)塊的指針，于是當(dāng)一個(gè)索引數(shù)據(jù)塊的索引信息用完了，就可以通過指針的方式，找到下一個(gè)索引數(shù)據(jù)塊的信息。那這種方式也會(huì)出現(xiàn)前面提到的鏈表方式的問題，萬一某個(gè)指針損壞了，后面的數(shù)據(jù)也就會(huì)無法讀取了。

還有另外一種組合方式是索引 + 索引的方式，這種組合稱為「多級(jí)索引塊」，實(shí)現(xiàn)方式是通過一個(gè)索引塊來存放多個(gè)索引數(shù)據(jù)塊，一層套一層索引，像極了俄羅斯套娃是吧。

Unix 文件的實(shí)現(xiàn)方式

我們先把前面提到的文件實(shí)現(xiàn)方式，做個(gè)比較：

那早期 Unix 文件系統(tǒng)是組合了前面的文件存放方式的優(yōu)點(diǎn)，如下圖：

它是根據(jù)文件的大小，存放的方式會(huì)有所變化：

• 如果存放文件所需的數(shù)據(jù)塊小于 10 塊，則采用直接查找的方式；

• 如果存放文件所需的數(shù)據(jù)塊超過 10 塊，則采用一級(jí)間接索引方式；

• 如果前面兩種方式都不夠存放大文件，則采用二級(jí)間接索引方式；

• 如果二級(jí)間接索引也不夠存放大文件，這采用三級(jí)間接索引方式；

那么，文件頭（Inode）就需要包含 13 個(gè)指針：

• 10 個(gè)指向數(shù)據(jù)塊的指針；

• 第 11 個(gè)指向索引塊的指針；

• 第 12 個(gè)指向二級(jí)索引塊的指針；

• 第 13 個(gè)指向三級(jí)索引塊的指針；

所以，這種方式能很靈活地支持小文件和大文件的存放：

• 對(duì)于小文件使用直接查找的方式可減少索引數(shù)據(jù)塊的開銷；

• 對(duì)于大文件則以多級(jí)索引的方式來支持，所以大文件在訪問數(shù)據(jù)塊時(shí)需要大量查詢；

這個(gè)方案就用在了 Linux Ext 2/3 文件系統(tǒng)里，雖然解決大文件的存儲(chǔ)，但是對(duì)于大文件的訪問，需要大量的查詢，效率比較低。

為了解決這個(gè)問題，Ext 4 做了一定的改變，具體怎么解決的，本文就不展開了。

空閑空間管理

前面說到的文件的存儲(chǔ)是針對(duì)已經(jīng)被占用的數(shù)據(jù)塊組織和管理，接下來的問題是，如果我要保存一個(gè)數(shù)據(jù)塊，我應(yīng)該放在硬盤上的哪個(gè)位置呢？難道需要將所有的塊掃描一遍，找個(gè)空的地方隨便放嗎？

那這種方式效率就太低了，所以針對(duì)磁盤的空閑空間也是要引入管理的機(jī)制，接下來介紹幾種常見的方法：

• 空閑表法

• 空閑鏈表法

• 位圖法

空閑表法

空閑表法就是為所有空閑空間建立一張表，表內(nèi)容包括空閑區(qū)的第一個(gè)塊號(hào)和該空閑區(qū)的塊個(gè)數(shù)，注意，這個(gè)方式是連續(xù)分配的。如下圖：

當(dāng)請(qǐng)求分配磁盤空間時(shí)，系統(tǒng)依次掃描空閑表里的內(nèi)容，直到找到一個(gè)合適的空閑區(qū)域?yàn)橹?。?dāng)用戶撤銷一個(gè)文件時(shí)，系統(tǒng)回收文件空間。這時(shí)，也需順序掃描空閑表，尋找一個(gè)空閑表?xiàng)l目并將釋放空間的第一個(gè)物理塊號(hào)及它占用的塊數(shù)填到這個(gè)條目中。

這種方法僅當(dāng)有少量的空閑區(qū)時(shí)才有較好的效果。因?yàn)?，如果存?chǔ)空間中有著大量的小的空閑區(qū)，則空閑表變得很大，這樣查詢效率會(huì)很低。另外，這種分配技術(shù)適用于建立連續(xù)文件。

空閑鏈表法

我們也可以使用「鏈表」的方式來管理空閑空間，每一個(gè)空閑塊里有一個(gè)指針指向下一個(gè)空閑塊，這樣也能很方便的找到空閑塊并管理起來。如下圖：

當(dāng)創(chuàng)建文件需要一塊或幾塊時(shí)，就從鏈頭上依次取下一塊或幾塊。反之，當(dāng)回收空間時(shí)，把這些空閑塊依次接到鏈頭上。

這種技術(shù)只要在主存中保存一個(gè)指針，令它指向第一個(gè)空閑塊。其特點(diǎn)是簡單，但不能隨機(jī)訪問，工作效率低，因?yàn)槊慨?dāng)在鏈上增加或移動(dòng)空閑塊時(shí)需要做很多 I/O 操作，同時(shí)數(shù)據(jù)塊的指針消耗了一定的存儲(chǔ)空間。

空閑表法和空閑鏈表法都不適合用于大型文件系統(tǒng)，因?yàn)檫@會(huì)使空閑表或空閑鏈表太大。

位圖法

位圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)盤塊的使用情況，磁盤上所有的盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)。

當(dāng)值為 0 時(shí)，表示對(duì)應(yīng)的盤塊空閑，值為 1 時(shí)，表示對(duì)應(yīng)的盤塊已分配。它形式如下：

1111110011111110001110110111111100111 ...

在 Linux 文件系統(tǒng)就采用了位圖的方式來管理空閑空間，不僅用于數(shù)據(jù)空閑塊的管理，還用于 inode 空閑塊的管理，因?yàn)?inode 也是存儲(chǔ)在磁盤的，自然也要有對(duì)其管理。

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

前面提到 Linux 是用位圖的方式管理空閑空間，用戶在創(chuàng)建一個(gè)新文件時(shí)，Linux 內(nèi)核會(huì)通過 inode 的位圖找到空閑可用的 inode，并進(jìn)行分配。要存儲(chǔ)數(shù)據(jù)時(shí)，會(huì)通過塊的位圖找到空閑的塊，并分配，但仔細(xì)計(jì)算一下還是有問題的。

數(shù)據(jù)塊的位圖是放在磁盤塊里的，假設(shè)是放在一個(gè)塊里，一個(gè)塊 4K，每位表示一個(gè)數(shù)據(jù)塊，共可以表示 4 * 1024 * 8 = 2^15 個(gè)空閑塊，由于 1 個(gè)數(shù)據(jù)塊是 4K 大小，那么最大可以表示的空間為 2^15 * 4 * 1024 = 2^27 個(gè) byte，也就是 128M。

也就是說按照上面的結(jié)構(gòu)，如果采用「一個(gè)塊的位圖 + 一系列的塊」，外加「一個(gè)塊的 inode 的位圖 + 一系列的 inode 的結(jié)構(gòu)」能表示的最大空間也就 128M，這太少了，現(xiàn)在很多文件都比這個(gè)大。

在 Linux 文件系統(tǒng)，把這個(gè)結(jié)構(gòu)稱為一個(gè)塊組，那么有 N 多的塊組，就能夠表示 N 大的文件。

下圖給出了 Linux Ext2 整個(gè)文件系統(tǒng)的結(jié)構(gòu)和塊組的內(nèi)容，文件系統(tǒng)都由大量塊組組成，在硬盤上相繼排布：

最前面的第一個(gè)塊是引導(dǎo)塊，在系統(tǒng)啟動(dòng)時(shí)用于啟用引導(dǎo)，接著后面就是一個(gè)一個(gè)連續(xù)的塊組了，塊組的內(nèi)容如下：

• 超級(jí)塊，包含的是文件系統(tǒng)的重要信息，比如 inode 總個(gè)數(shù)、塊總個(gè)數(shù)、每個(gè)塊組的 inode 個(gè)數(shù)、每個(gè)塊組的塊個(gè)數(shù)等等。

• 塊組描述符，包含文件系統(tǒng)中各個(gè)塊組的狀態(tài)，比如塊組中空閑塊和 inode 的數(shù)目等，每個(gè)塊組都包含了文件系統(tǒng)中「所有塊組的組描述符信息」。

• 數(shù)據(jù)位圖和 inode 位圖， 用于表示對(duì)應(yīng)的數(shù)據(jù)塊或 inode 是空閑的，還是被使用中。

• inode 列表，包含了塊組中所有的 inode，inode 用于保存文件系統(tǒng)中與各個(gè)文件和目錄相關(guān)的所有元數(shù)據(jù)。

• 數(shù)據(jù)塊，包含文件的有用數(shù)據(jù)。

你可以會(huì)發(fā)現(xiàn)每個(gè)塊組里有很多重復(fù)的信息，比如超級(jí)塊和塊組描述符表，這兩個(gè)都是全局信息，而且非常的重要，這么做是有兩個(gè)原因：

• 如果系統(tǒng)崩潰破壞了超級(jí)塊或塊組描述符，有關(guān)文件系統(tǒng)結(jié)構(gòu)和內(nèi)容的所有信息都會(huì)丟失。如果有冗余的副本，該信息是可能恢復(fù)的。

• 通過使文件和管理數(shù)據(jù)盡可能接近，減少了磁頭尋道和旋轉(zhuǎn)，這可以提高文件系統(tǒng)的性能。

不過，Ext2 的后續(xù)版本采用了稀疏技術(shù)。該做法是，超級(jí)塊和塊組描述符表不再存儲(chǔ)到文件系統(tǒng)的每個(gè)塊組中，而是只寫入到塊組 0、塊組 1 和其他 ID 可以表示為 3、 5、7 的冪的塊組中。

目錄的存儲(chǔ)

在前面，我們知道了一個(gè)普通文件是如何存儲(chǔ)的，但還有一個(gè)特殊的文件，經(jīng)常用到的目錄，它是如何保存的呢？

基于 Linux 一切皆文件的設(shè)計(jì)思想，目錄其實(shí)也是個(gè)文件，你甚至可以通過 vim 打開它，它也有 inode，inode 里面也是指向一些塊。

和普通文件不同的是，普通文件的塊里面保存的是文件數(shù)據(jù)，而目錄文件的塊里面保存的是目錄里面一項(xiàng)一項(xiàng)的文件信息。

在目錄文件的塊中，最簡單的保存格式就是列表，就是一項(xiàng)一項(xiàng)地將目錄下的文件信息（如文件名、文件 inode、文件類型等）列在表里。

列表中每一項(xiàng)就代表該目錄下的文件的文件名和對(duì)應(yīng)的 inode，通過這個(gè) inode，就可以找到真正的文件。

通常，第一項(xiàng)是「.」，表示當(dāng)前目錄，第二項(xiàng)是「..」，表示上一級(jí)目錄，接下來就是一項(xiàng)一項(xiàng)的文件名和 inode。

如果一個(gè)目錄有超級(jí)多的文件，我們要想在這個(gè)目錄下找文件，按照列表一項(xiàng)一項(xiàng)的找，效率就不高了。

于是，保存目錄的格式改成哈希表，對(duì)文件名進(jìn)行哈希計(jì)算，把哈希值保存起來，如果我們要查找一個(gè)目錄下面的文件名，可以通過名稱取哈希。如果哈希能夠匹配上，就說明這個(gè)文件的信息在相應(yīng)的塊里面。

Linux 系統(tǒng)的 ext 文件系統(tǒng)就是采用了哈希表，來保存目錄的內(nèi)容，這種方法的優(yōu)點(diǎn)是查找非常迅速，插入和刪除也較簡單，不過需要一些預(yù)備措施來避免哈希沖突。

目錄查詢是通過在磁盤上反復(fù)搜索完成，需要不斷地進(jìn)行 I/O 操作，開銷較大。所以，為了減少 I/O 操作，把當(dāng)前使用的文件目錄緩存在內(nèi)存，以后要使用該文件時(shí)只要在內(nèi)存中操作，從而降低了磁盤操作次數(shù)，提高了文件系統(tǒng)的訪問速度。

軟鏈接和硬鏈接

有時(shí)候我們希望給某個(gè)文件取個(gè)別名，那么在 Linux 中可以通過硬鏈接（Hard Link） 和軟鏈接（Symbolic Link） 的方式來實(shí)現(xiàn)，它們都是比較特殊的文件，但是實(shí)現(xiàn)方式也是不相同的。

硬鏈接是多個(gè)目錄項(xiàng)中的「索引節(jié)點(diǎn)」指向一個(gè)文件，也就是指向同一個(gè) inode，但是 inode 是不可能跨越文件系統(tǒng)的，每個(gè)文件系統(tǒng)都有各自的 inode 數(shù)據(jù)結(jié)構(gòu)和列表，所以硬鏈接是不可用于跨文件系統(tǒng)的。由于多個(gè)目錄項(xiàng)都是指向一個(gè) inode，那么只有刪除文件的所有硬鏈接以及源文件時(shí)，系統(tǒng)才會(huì)徹底刪除該文件。

軟鏈接相當(dāng)于重新創(chuàng)建一個(gè)文件，這個(gè)文件有獨(dú)立的 inode，但是這個(gè)文件的內(nèi)容是另外一個(gè)文件的路徑，所以訪問軟鏈接的時(shí)候，實(shí)際上相當(dāng)于訪問到了另外一個(gè)文件，所以軟鏈接是可以跨文件系統(tǒng)的，甚至目標(biāo)文件被刪除了，鏈接文件還是在的，只不過指向的文件找不到了而已。

文件 I/O

文件的讀寫方式各有千秋，對(duì)于文件的 I/O 分類也非常多，常見的有

• 緩沖與非緩沖 I/O

• 直接與非直接 I/O

• 阻塞與非阻塞 I/O VS 同步與異步 I/O

接下來，分別對(duì)這些分類討論討論。

緩沖與非緩沖 I/O

文件操作的標(biāo)準(zhǔn)庫是可以實(shí)現(xiàn)數(shù)據(jù)的緩存，那么根據(jù)「是否利用標(biāo)準(zhǔn)庫緩沖」，可以把文件 I/O 分為緩沖 I/O 和非緩沖 I/O：

• 緩沖 I/O，利用的是標(biāo)準(zhǔn)庫的緩存實(shí)現(xiàn)文件的加速訪問，而標(biāo)準(zhǔn)庫再通過系統(tǒng)調(diào)用訪問文件。

• 非緩沖 I/O，直接通過系統(tǒng)調(diào)用訪問文件，不經(jīng)過標(biāo)準(zhǔn)庫緩存。

這里所說的「緩沖」特指標(biāo)準(zhǔn)庫內(nèi)部實(shí)現(xiàn)的緩沖。

比方說，很多程序遇到換行時(shí)才真正輸出，而換行前的內(nèi)容，其實(shí)就是被標(biāo)準(zhǔn)庫暫時(shí)緩存了起來，這樣做的目的是，減少系統(tǒng)調(diào)用的次數(shù)，畢竟系統(tǒng)調(diào)用是有 CPU 上下文切換的開銷的。

直接與非直接 I/O

我們都知道磁盤 I/O 是非常慢的，所以 Linux 內(nèi)核為了減少磁盤 I/O 次數(shù)，在系統(tǒng)調(diào)用后，會(huì)把用戶數(shù)據(jù)拷貝到內(nèi)核中緩存起來，這個(gè)內(nèi)核緩存空間也就是「頁緩存」，只有當(dāng)緩存滿足某些條件的時(shí)候，才發(fā)起磁盤 I/O 的請(qǐng)求。

那么，根據(jù)是「否利用操作系統(tǒng)的緩存」，可以把文件 I/O 分為直接 I/O 與非直接 I/O：

• 直接 I/O，不會(huì)發(fā)生內(nèi)核緩存和用戶程序之間數(shù)據(jù)復(fù)制，而是直接經(jīng)過文件系統(tǒng)訪問磁盤。

• 非直接 I/O，讀操作時(shí)，數(shù)據(jù)從內(nèi)核緩存中拷貝給用戶程序，寫操作時(shí)，數(shù)據(jù)從用戶程序拷貝給內(nèi)核緩存，再由內(nèi)核決定什么時(shí)候?qū)懭霐?shù)據(jù)到磁盤。

如果你在使用文件操作類的系統(tǒng)調(diào)用函數(shù)時(shí)，指定了 O_DIRECT 標(biāo)志，則表示使用直接 I/O。如果沒有設(shè)置過，默認(rèn)使用的是非直接 I/O。

如果用了非直接 I/O 進(jìn)行寫數(shù)據(jù)操作，內(nèi)核什么情況下才會(huì)把緩存數(shù)據(jù)寫入到磁盤？

以下幾種場景會(huì)觸發(fā)內(nèi)核緩存的數(shù)據(jù)寫入磁盤：

• 在調(diào)用 write 的最后，當(dāng)發(fā)現(xiàn)內(nèi)核緩存的數(shù)據(jù)太多的時(shí)候，內(nèi)核會(huì)把數(shù)據(jù)寫到磁盤上；

• 用戶主動(dòng)調(diào)用 sync，內(nèi)核緩存會(huì)刷到磁盤上；

• 當(dāng)內(nèi)存十分緊張，無法再分配頁面時(shí)，也會(huì)把內(nèi)核緩存的數(shù)據(jù)刷到磁盤上；

• 內(nèi)核緩存的數(shù)據(jù)的緩存時(shí)間超過某個(gè)時(shí)間時(shí)，也會(huì)把數(shù)據(jù)刷到磁盤上；

阻塞與非阻塞 I/O VS 同步與異步 I/O

為什么把阻塞 / 非阻塞與同步與異步放一起說的呢？因?yàn)樗鼈兇_實(shí)非常相似，也非常容易混淆，不過它們之間的關(guān)系還是有點(diǎn)微妙的。

先來看看阻塞 I/O，當(dāng)用戶程序執(zhí)行 read ，線程會(huì)被阻塞，一直等到內(nèi)核數(shù)據(jù)準(zhǔn)備好，并把數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝到應(yīng)用程序的緩沖區(qū)中，當(dāng)拷貝過程完成，read 才會(huì)返回。

注意，阻塞等待的是「內(nèi)核數(shù)據(jù)準(zhǔn)備好」和「數(shù)據(jù)從內(nèi)核態(tài)拷貝到用戶態(tài)」這兩個(gè)過程。過程如下圖：

知道了阻塞 I/O ，來看看非阻塞 I/O，非阻塞的 read 請(qǐng)求在數(shù)據(jù)未準(zhǔn)備好的情況下立即返回，可以繼續(xù)往下執(zhí)行，此時(shí)應(yīng)用程序不斷輪詢內(nèi)核，直到數(shù)據(jù)準(zhǔn)備好，內(nèi)核將數(shù)據(jù)拷貝到應(yīng)用程序緩沖區(qū)，read 調(diào)用才可以獲取到結(jié)果。過程如下圖：

注意，這里最后一次 read 調(diào)用，獲取數(shù)據(jù)的過程，是一個(gè)同步的過程，是需要等待的過程。這里的同步指的是內(nèi)核態(tài)的數(shù)據(jù)拷貝到用戶程序的緩存區(qū)這個(gè)過程。

舉個(gè)例子，訪問管道或 socket 時(shí)，如果設(shè)置了 O_NONBLOCK 標(biāo)志，那么就表示使用的是非阻塞 I/O 的方式訪問，而不做任何設(shè)置的話，默認(rèn)是阻塞 I/O。

應(yīng)用程序每次輪詢內(nèi)核的 I/O 是否準(zhǔn)備好，感覺有點(diǎn)傻乎乎，因?yàn)檩喸兊倪^程中，應(yīng)用程序啥也做不了，只是在循環(huán)。

為了解決這種傻乎乎輪詢方式，于是 I/O 多路復(fù)用技術(shù)就出來了，如 select、poll，它是通過 I/O 事件分發(fā)，當(dāng)內(nèi)核數(shù)據(jù)準(zhǔn)備好時(shí)，再以事件通知應(yīng)用程序進(jìn)行操作。

這個(gè)做法大大改善了應(yīng)用進(jìn)程對(duì) CPU 的利用率，在沒有被通知的情況下，應(yīng)用進(jìn)程可以使用 CPU 做其他的事情。

下圖是使用 select I/O 多路復(fù)用過程。注意，read 獲取數(shù)據(jù)的過程（數(shù)據(jù)從內(nèi)核態(tài)拷貝到用戶態(tài)的過程），也是一個(gè)同步的過程，需要等待：

實(shí)際上，無論是阻塞 I/O、非阻塞 I/O，還是基于非阻塞 I/O 的多路復(fù)用都是同步調(diào)用。因?yàn)樗鼈冊?read 調(diào)用時(shí)，內(nèi)核將數(shù)據(jù)從內(nèi)核空間拷貝到應(yīng)用程序空間，過程都是需要等待的，也就是說這個(gè)過程是同步的，如果內(nèi)核實(shí)現(xiàn)的拷貝效率不高，read 調(diào)用就會(huì)在這個(gè)同步過程中等待比較長的時(shí)間。

而真正的異步 I/O 是「內(nèi)核數(shù)據(jù)準(zhǔn)備好」和「數(shù)據(jù)從內(nèi)核態(tài)拷貝到用戶態(tài)」這兩個(gè)過程都不用等待。

當(dāng)我們發(fā)起 aio_read 之后，就立即返回，內(nèi)核自動(dòng)將數(shù)據(jù)從內(nèi)核空間拷貝到應(yīng)用程序空間，這個(gè)拷貝過程同樣是異步的，內(nèi)核自動(dòng)完成的，和前面的同步操作不一樣，應(yīng)用程序并不需要主動(dòng)發(fā)起拷貝動(dòng)作。過程如下圖：

下面這張圖，總結(jié)了以上幾種 I/O 模型：

在前面我們知道了，I/O 是分為兩個(gè)過程的：

1. 數(shù)據(jù)準(zhǔn)備的過程

2. 數(shù)據(jù)從內(nèi)核空間拷貝到用戶進(jìn)程緩沖區(qū)的過程

阻塞 I/O 會(huì)阻塞在「過程 1 」和「過程 2」，而非阻塞 I/O 和基于非阻塞 I/O 的多路復(fù)用只會(huì)阻塞在「過程 2」，所以這三個(gè)都可以認(rèn)為是同步 I/O。

異步 I/O 則不同，「過程 1 」和「過程 2 」都不會(huì)阻塞。

用故事去理解這幾種 I/O 模型

舉個(gè)你去飯?zhí)贸燥埖睦?，你好比用戶程序，飯?zhí)煤帽炔僮飨到y(tǒng)。

阻塞 I/O 好比，你去飯?zhí)贸燥?，但是飯?zhí)玫牟诉€沒做好，然后你就一直在那里等啊等，等了好長一段時(shí)間終于等到飯?zhí)冒⒁贪巡硕肆顺鰜恚〝?shù)據(jù)準(zhǔn)備的過程），但是你還得繼續(xù)等阿姨把菜（內(nèi)核空間）打到你的飯盒里（用戶空間），經(jīng)歷完這兩個(gè)過程，你才可以離開。

非阻塞 I/O 好比，你去了飯?zhí)?，問阿姨菜做好了沒有，阿姨告訴你沒，你就離開了，過幾十分鐘，你又來飯?zhí)脝柊⒁?，阿姨說做好了，于是阿姨幫你把菜打到你的飯盒里，這個(gè)過程你是得等待的。

基于非阻塞的 I/O 多路復(fù)用好比，你去飯?zhí)贸燥?，發(fā)現(xiàn)有一排窗口，飯?zhí)冒⒁谈嬖V你這些窗口都還沒做好菜，等做好了再通知你，于是等啊等（select 調(diào)用中），過了一會(huì)阿姨通知你菜做好了，但是不知道哪個(gè)窗口的菜做好了，你自己看吧。于是你只能一個(gè)一個(gè)窗口去確認(rèn)，后面發(fā)現(xiàn) 5 號(hào)窗口菜做好了，于是你讓 5 號(hào)窗口的阿姨幫你打菜到飯盒里，這個(gè)打菜的過程你是要等待的，雖然時(shí)間不長。打完菜后，你自然就可以離開了。

異步 I/O 好比，你讓飯?zhí)冒⒁虒⒉俗龊貌巡舜虻斤埡欣锖?，把飯盒送到你面前，整個(gè)過程你都不需要任何等待。