設(shè)計一個文件系統(tǒng)，需要考慮哪些因素？

文件系統(tǒng)的實現(xiàn)

在對文件有了基本認(rèn)識之后，現(xiàn)在是時候把目光轉(zhuǎn)移到文件系統(tǒng)的實現(xiàn)上了。之前用戶關(guān)心的一直都是文件是怎樣命名的、可以進(jìn)行哪些操作、目錄樹是什么，如何找到正確的文件路徑等問題。而設(shè)計人員關(guān)心的是文件和目錄是怎樣存儲的、磁盤空間是如何管理的、如何使文件系統(tǒng)得以流暢運行的問題，下面我們就來一起討論一下這些問題。

文件系統(tǒng)布局

文件系統(tǒng)存儲在磁盤中。大部分的磁盤能夠劃分出一到多個分區(qū)，叫做磁盤分區(qū)(disk partitioning) 或者是磁盤分片(disk slicing)。每個分區(qū)都有獨立的文件系統(tǒng)，每塊分區(qū)的文件系統(tǒng)可以不同。磁盤的 0 號分區(qū)稱為 主引導(dǎo)記錄(Master Boot Record, MBR)，用來引導(dǎo)(boot) 計算機(jī)。在 MBR 的結(jié)尾是分區(qū)表(partition table)。每個分區(qū)表給出每個分區(qū)由開始到結(jié)束的地址。系統(tǒng)管理員使用一個稱為分區(qū)編輯器的程序來創(chuàng)建，調(diào)整大小，刪除和操作分區(qū)。這種方式的一個缺點是很難適當(dāng)調(diào)整分區(qū)的大小，導(dǎo)致一個分區(qū)具有很多可用空間，而另一個分區(qū)幾乎完全被分配。

MBR 可以用在 DOS 、Microsoft Windows 和 Linux 操作系統(tǒng)中。從 2010 年代中期開始，大多數(shù)新計算機(jī)都改用 GUID 分區(qū)表（GPT）分區(qū)方案。

下面是一個用 GParted 進(jìn)行分區(qū)的磁盤，表中的分區(qū)都被認(rèn)為是 活動的(active)。

當(dāng)計算機(jī)開始引 boot 時，BIOS 讀入并執(zhí)行 MBR。

MBR 做的第一件事就是確定活動分區(qū)，讀入它的第一個塊，稱為引導(dǎo)塊(boot block) 并執(zhí)行。引導(dǎo)塊中的程序?qū)⒓虞d分區(qū)中的操作系統(tǒng)。為了一致性，每個分區(qū)都會從引導(dǎo)塊開始，即使引導(dǎo)塊不包含操作系統(tǒng)。引導(dǎo)塊占據(jù)文件系統(tǒng)的前 4096 個字節(jié)，從磁盤上的字節(jié)偏移量 0 開始。引導(dǎo)塊可用于啟動操作系統(tǒng)。

在計算機(jī)中，引導(dǎo)就是啟動計算機(jī)的過程，它可以通過硬件（例如按下電源按鈕）或者軟件命令的方式來啟動。開機(jī)后，電腦的 CPU 還不能執(zhí)行指令，因為此時沒有軟件在主存中，所以一些軟件必須先被加載到內(nèi)存中，然后才能讓 CPU 開始執(zhí)行。也就是計算機(jī)開機(jī)后，首先會進(jìn)行軟件的裝載過程。

重啟電腦的過程稱為重新引導(dǎo)(rebooting)，從休眠或睡眠狀態(tài)返回計算機(jī)的過程不涉及啟動。

除了從引導(dǎo)塊開始之外，磁盤分區(qū)的布局是隨著文件系統(tǒng)的不同而變化的。通常文件系統(tǒng)會包含一些屬性，如下

緊跟在引導(dǎo)塊后面的是 超級塊(Superblock)，超級塊 的大小為 4096 字節(jié)，從磁盤上的字節(jié)偏移 4096 開始。超級塊包含文件系統(tǒng)的所有關(guān)鍵參數(shù)

文件系統(tǒng)的大小

文件系統(tǒng)中的數(shù)據(jù)塊數(shù)

指示文件系統(tǒng)狀態(tài)的標(biāo)志

分配組大小

在計算機(jī)啟動或者文件系統(tǒng)首次使用時，超級塊會被讀入內(nèi)存。

接著是文件系統(tǒng)中空閑塊的信息，例如，可以用位圖或者指針列表的形式給出。

BitMap 位圖或者 Bit vector 位向量

位圖或位向量是一系列位或位的集合，其中每個位對應(yīng)一個磁盤塊，該位可以采用兩個值：0和1，0表示已分配該塊，而1表示一個空閑塊。下圖中的磁盤上給定的磁盤塊實例（分配了綠色塊）可以用16位的位圖表示為：0000111000000110。

使用鏈表進(jìn)行管理

在這種方法中，空閑磁盤塊鏈接在一起，即一個空閑塊包含指向下一個空閑塊的指針。第一個磁盤塊的塊號存儲在磁盤上的單獨位置，也緩存在內(nèi)存中。

這里不得不提一個叫做碎片(fragment)的概念，也稱為片段。一般零散的單個數(shù)據(jù)通常稱為片段。 磁盤塊可以進(jìn)一步分為固定大小的分配單元，片段只是在驅(qū)動器上彼此不相鄰的文件片段。如果你不理解這個概念就給你舉個例子。比如你用 Windows 電腦創(chuàng)建了一個文件，你會發(fā)現(xiàn)這個文件可以存儲在任何地方，比如存在桌面上，存在磁盤中的文件夾中或者其他地方。你可以打開文件，編輯文件，刪除文件等等。你可能以為這些都在一個地方發(fā)生，但是實際上并不是，你的硬盤驅(qū)動器可能會將文件中的一部分存儲在一個區(qū)域內(nèi)，另一部分存儲在另外一個區(qū)域，在你打開文件時，硬盤驅(qū)動器會迅速的將文件的所有部分匯總在一起，以便其他計算機(jī)系統(tǒng)可以使用它。

然后在后面是一個 inode(index node)，也稱作索引節(jié)點。它是一個數(shù)組的結(jié)構(gòu)，每個文件有一個 inode，inode 非常重要，它說明了文件的方方面面。每個索引節(jié)點都存儲對象數(shù)據(jù)的屬性和磁盤塊位置

有一種簡單的方法可以找到它們 ls -lai 命令。讓我們看一下根文件系統(tǒng)：

inode 節(jié)點主要包括了以下信息

模式/權(quán)限（保護(hù)）

所有者 ID

組 ID

文件大小

文件的硬鏈接數(shù)

上次訪問時間

最后修改時間

inode 上次修改時間

文件分為兩部分，索引節(jié)點和塊。一旦創(chuàng)建后，每種類型的塊數(shù)是固定的。你不能增加分區(qū)上 inode 的數(shù)量，也不能增加磁盤塊的數(shù)量。

緊跟在 inode 后面的是根目錄，它存放的是文件系統(tǒng)目錄樹的根部。最后，磁盤的其他部分存放了其他所有的目錄和文件。

文件的實現(xiàn)

最重要的問題是記錄各個文件分別用到了哪些磁盤塊。不同的系統(tǒng)采用了不同的方法。下面我們會探討一下這些方式。分配背后的主要思想是有效利用文件空間和快速訪問文件 ，主要有三種分配方案

連續(xù)分配

鏈表分配

索引分配

最簡單的分配方案是把每個文件作為一連串連續(xù)數(shù)據(jù)塊存儲在磁盤上。因此，在具有 1KB 塊的磁盤上，將為 50 KB 文件分配 50 個連續(xù)塊。

上面展示了 40 個連續(xù)的內(nèi)存塊。從最左側(cè)的 0 塊開始。初始狀態(tài)下，還沒有裝載文件，因此磁盤是空的。接著，從磁盤開始處（塊 0 ）處開始寫入占用 4 塊長度的內(nèi)存 A 。然后是一個占用 6 塊長度的內(nèi)存 B，會直接在 A 的末尾開始寫。

注意每個文件都會在新的文件塊開始寫，所以如果文件 A 只占用了 3 又 1/2 個塊，那么最后一個塊的部分內(nèi)存會被浪費。在上面這幅圖中，總共展示了 7 個文件，每個文件都會從上個文件的末尾塊開始寫新的文件塊。

連續(xù)的磁盤空間分配有兩個優(yōu)點。

第一，連續(xù)文件存儲實現(xiàn)起來比較簡單，只需要記住兩個數(shù)字就可以：一個是第一個塊的文件地址和文件的塊數(shù)量。給定第一個塊的編號，可以通過簡單的加法找到任何其他塊的編號。

第二點是讀取性能比較強(qiáng)，可以通過一次操作從文件中讀取整個文件。只需要一次尋找第一個塊。后面就不再需要尋道時間和旋轉(zhuǎn)延遲，所以數(shù)據(jù)會以全帶寬進(jìn)入磁盤。

因此，連續(xù)的空間分配具有實現(xiàn)簡單、高性能的特點。

不幸的是，連續(xù)空間分配也有很明顯的不足。隨著時間的推移，磁盤會變得很零碎。下圖解釋了這種現(xiàn)象

這里有兩個文件 D 和 F 被刪除了。當(dāng)刪除一個文件時，此文件所占用的塊也隨之釋放，就會在磁盤空間中留下一些空閑塊。磁盤并不會在這個位置擠壓掉空閑塊，因為這會復(fù)制空閑塊之后的所有文件，可能會有上百萬的塊，這個量級就太大了。

剛開始的時候，這個碎片不是問題，因為每個新文件都會在之前文件的結(jié)尾處進(jìn)行寫入。然而，磁盤最終會被填滿，因此要么壓縮磁盤、要么重新使用空閑塊的空間。壓縮磁盤的開銷太大，因此不可行；后者會維護(hù)一個空閑列表，這個是可行的。但是這種情況又存在一個問題，為空閑塊匹配合適大小的文件，需要知道該文件的最終大小。

想象一下這種設(shè)計的結(jié)果會是怎樣的。用戶啟動 word 進(jìn)程創(chuàng)建文檔。應(yīng)用程序首先會詢問最終創(chuàng)建的文檔會有多大。這個問題必須回答，否則應(yīng)用程序就不會繼續(xù)執(zhí)行。如果空閑塊的大小要比文件的大小小，程序就會終止。因為所使用的磁盤空間已經(jīng)滿了。那么現(xiàn)實生活中，有沒有使用連續(xù)分配內(nèi)存的介質(zhì)出現(xiàn)呢？

CD-ROM 就廣泛的使用了連續(xù)分配方式。

CD-ROM（Compact Disc Read-Only Memory）即只讀光盤，也稱作只讀存儲器。是一種在電腦上使用的光碟。這種光碟只能寫入數(shù)據(jù)一次，信息將永久保存在光碟上，使用時通過光碟驅(qū)動器讀出信息。

然而 DVD 的情況會更加復(fù)雜一些。原則上，一個 90分鐘 的電影能夠被編碼成一個獨立的、大約 4.5 GB 的文件。但是文件系統(tǒng)所使用的 UDF(Universal Disk Format) 格式，使用一個 30 位的數(shù)來代表文件長度，從而把文件大小限制在 1 GB。所以，DVD 電影一般存儲在 3、4個連續(xù)的 1 GB 空間內(nèi)。這些構(gòu)成單個電影中的文件塊稱為擴(kuò)展區(qū)(extends)。

就像我們反復(fù)提到的，歷史總是驚人的相似，許多年前，連續(xù)分配由于其簡單和高性能被實際使用在磁盤文件系統(tǒng)中。后來由于用戶不希望在創(chuàng)建文件時指定文件的大小，于是放棄了這種想法。但是隨著 CD-ROM 、DVD、藍(lán)光光盤等光學(xué)介質(zhì)的出現(xiàn)，連續(xù)分配又流行起來。從而得出結(jié)論，技術(shù)永遠(yuǎn)沒有過時性，現(xiàn)在看似很老的技術(shù)，在未來某個階段可能又會流行起來。

第二種存儲文件的方式是為每個文件構(gòu)造磁盤塊鏈表，每個文件都是磁盤塊的鏈接列表，就像下面所示

每個塊的第一個字作為指向下一塊的指針，塊的其他部分存放數(shù)據(jù)。如果上面這張圖你看的不是很清楚的話，可以看看整個的鏈表分配方案

與連續(xù)分配方案不同，這一方法可以充分利用每個磁盤塊。除了最后一個磁盤塊外，不會因為磁盤碎片而浪費存儲空間。同樣，在目錄項中，只要存儲了第一個文件塊，那么其他文件塊也能夠被找到。

另一方面，在鏈表的分配方案中，盡管順序讀取非常方便，但是隨機(jī)訪問卻很困難（這也是數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)的一大區(qū)別）。

還有一個問題是，由于指針會占用一些字節(jié)，每個磁盤塊實際存儲數(shù)據(jù)的字節(jié)數(shù)并不再是 2 的整數(shù)次冪。雖然這個問題并不會很嚴(yán)重，但是這種方式降低了程序運行效率。許多程序都是以長度為 2 的整數(shù)次冪來讀寫磁盤，由于每個塊的前幾個字節(jié)被指針?biāo)褂茫砸x出一個完成的塊大小信息，就需要當(dāng)前塊的信息和下一塊的信息拼湊而成，因此就引發(fā)了查找和拼接的開銷。

由于連續(xù)分配和鏈表分配都有其不可忽視的缺點。所以提出了使用內(nèi)存中的表來解決分配問題。取出每個磁盤塊的指針字，把它們放在內(nèi)存的一個表中，就可以解決上述鏈表的兩個不足之處。下面是一個例子

上圖表示了鏈表形成的磁盤塊的內(nèi)容。這兩個圖中都有兩個文件，文件 A 依次使用了磁盤塊地址 4、7、 2、 10、 12，文件 B 使用了6、3、11 和 14。也就是說，文件 A 從地址 4 處開始，順著鏈表走就能找到文件 A 的全部磁盤塊。同樣，從第 6 塊開始，順著鏈走到最后，也能夠找到文件 B 的全部磁盤塊。你會發(fā)現(xiàn)，這兩個鏈表都以不屬于有效磁盤編號的特殊標(biāo)記（-1）結(jié)束。內(nèi)存中的這種表格稱為 文件分配表(File Application Table,FAT)。

使用這種組織方式，整個塊都可以存放數(shù)據(jù)。進(jìn)而，隨機(jī)訪問也容易很多。雖然仍要順著鏈在內(nèi)存中查找給定的偏移量，但是整個鏈都存放在內(nèi)存中，所以不需要任何磁盤引用。與前面的方法相同，不管文件有多大，在目錄項中只需記錄一個整數(shù)（起始塊號），按照它就可以找到文件的全部塊。

這種方式存在缺點，那就是必須要把整個鏈表放在內(nèi)存中。對于 1TB 的磁盤和 1KB 的大小的塊，那么這張表需要有 10 億項。。。每一項對應(yīng)于這 10 億個磁盤塊中的一塊。每項至少 3 個字節(jié)，為了提高查找速度，有時需要 4 個字節(jié)。根據(jù)系統(tǒng)對空間或時間的優(yōu)化方案，這張表要占用 3GB 或 2.4GB 的內(nèi)存。FAT 的管理方式不能較好地擴(kuò)展并應(yīng)用于大型磁盤中。而這正是最初 MS-DOS 文件比較實用，并仍被各個 Windows 版本所安全支持。

最后一個記錄各個文件分別包含哪些磁盤塊的方法是給每個文件賦予一個稱為 inode(索引節(jié)點) 的數(shù)據(jù)結(jié)構(gòu)，每個文件都與一個 inode 進(jìn)行關(guān)聯(lián)，inode 由整數(shù)進(jìn)行標(biāo)識。

下面是一個簡單例子的描述。

給出 inode 的長度，就能夠找到文件中的所有塊。

相對于在內(nèi)存中使用表的方式而言，這種機(jī)制具有很大的優(yōu)勢。即只有在文件打開時，其 inode 才會在內(nèi)存中。如果每個 inode 需要 n 個字節(jié)，最多 k 個文件同時打開，那么 inode 占有總共打開的文件是 kn 字節(jié)。僅需預(yù)留這么多空間。

這個數(shù)組要比我們上面描述的 FAT(文件分配表) 占用的空間小的多。原因是用于保存所有磁盤塊的鏈接列表的表的大小與磁盤本身成正比。如果磁盤有 n 個塊，那么這個表也需要 n 項。隨著磁盤空間的變大，那么該表也隨之線性增長。相反，inode 需要節(jié)點中的數(shù)組，其大小和可能需要打開的最大文件個數(shù)成正比。它與磁盤是 100GB、4000GB 還是 10000GB 無關(guān)。

inode 的一個問題是如果每個節(jié)點都會有固定大小的磁盤地址，那么文件增長到所能允許的最大容量外會發(fā)生什么？一個解決方案是最后一個磁盤地址不指向數(shù)據(jù)塊，而是指向一個包含額外磁盤塊地址的地址，如上圖所示。一個更高級的解決方案是：有兩個或者更多包含磁盤地址的塊，或者指向其他存放地址的磁盤塊的磁盤塊。Windows 的 NTFS 文件系統(tǒng)采用了相似的方法，所不同的僅僅是大的 inode 也可以表示小的文件。

NTFS 的全稱是 New Technology File System，是微軟公司開發(fā)的專用系統(tǒng)文件，NTFS 取代 FAT(文件分配表) 和 HPFS(高性能文件系統(tǒng)) ，并在此基礎(chǔ)上進(jìn)一步改進(jìn)。例如增強(qiáng)對元數(shù)據(jù)的支持，使用更高級的數(shù)據(jù)結(jié)構(gòu)以提升性能、可靠性和磁盤空間利用率等。

目錄的實現(xiàn)

文件只有打開后才能夠被讀取。在文件打開后，操作系統(tǒng)會使用用戶提供的路徑名來定位磁盤中的目錄。目錄項提供了查找文件磁盤塊所需要的信息。根據(jù)系統(tǒng)的不同，提供的信息也不同，可能提供的信息是整個文件的磁盤地址，或者是第一個塊的數(shù)量（兩個鏈表方案）或 inode的數(shù)量。不過不管用那種情況，目錄系統(tǒng)的主要功能就是 將文件的 ASCII 碼的名稱映射到定位數(shù)據(jù)所需的信息上。

與此關(guān)系密切的問題是屬性應(yīng)該存放在哪里。每個文件系統(tǒng)包含不同的文件屬性，例如文件的所有者和創(chuàng)建時間，需要存儲的位置。一種顯而易見的方法是直接把文件屬性存放在目錄中。有一些系統(tǒng)恰好是這么做的，如下。

在這種簡單的設(shè)計中，目錄有一個固定大小的目錄項列表，每個文件對應(yīng)一項，其中包含一個固定長度的文件名，文件屬性的結(jié)構(gòu)體以及用以說明磁盤塊位置的一個或多個磁盤地址。

對于采用 inode 的系統(tǒng)，會把 inode 存儲在屬性中而不是目錄項中。在這種情況下，目錄項會更短：僅僅只有文件名稱和 inode 數(shù)量。這種方式如下所示

到目前為止，我們已經(jīng)假設(shè)文件具有較短的、固定長度的名字。在 MS-DOS 中，具有 1 - 8 個字符的基本名稱和 1 - 3 個字符的可拓展名稱。在 UNIX 版本 7 中，文件有 1 - 14 個字符，包括任何拓展。然而，幾乎所有的現(xiàn)代操作系統(tǒng)都支持可變長度的擴(kuò)展名。這是如何實現(xiàn)的呢？

最簡單的方式是給予文件名一個長度限制，比如 255 個字符，然后使用上圖中的設(shè)計，并為每個文件名保留 255 個字符空間。這種處理很簡單，但是浪費了大量的目錄空間，因為只有很少的文件會有那么長的文件名稱。所以，需要一種其他的結(jié)構(gòu)來處理。

一種可選擇的方式是放棄所有目錄項大小相同的想法。在這種方法中，每個目錄項都包含一個固定部分，這個固定部分通常以目錄項的長度開始，后面是固定格式的數(shù)據(jù)，通常包括所有者、創(chuàng)建時間、保護(hù)信息和其他屬性。這個固定長度的頭的后面是一個任意長度的實際文件名，如下圖所示

上圖是 SPARC 機(jī)器使用正序放置。

處理機(jī)中的一串字符存放的順序有正序(big-endian) 和逆序(little-endian) 之分。正序存放的就是高字節(jié)在前低字節(jié)在后，而逆序存放的就是低字節(jié)在前高字節(jié)在后。

這個例子中，有三個文件，分別是 project-budget、personnel 和 foo。每個文件名以一個特殊字符（通常是 0 ）結(jié)束，用矩形中的叉進(jìn)行表示。為了使每個目錄項從字的邊界開始，每個文件名被填充成整數(shù)個字，如下圖所示

這個方法的缺點是當(dāng)文件被移除后，就會留下一塊固定長度的空間，而新添加進(jìn)來的文件大小不一定和空閑空間大小一致。

這個問題與我們上面探討的連續(xù)磁盤文件的問題是一樣的，由于整個目錄在內(nèi)存中，所以只有對目錄進(jìn)行緊湊拼接操作才可節(jié)省空間。另一個問題是，一個目錄項可能會分布在多個頁上，在讀取文件名時可能發(fā)生缺頁中斷。

處理可變長度文件名字的另外一種方法是，使目錄項自身具有固定長度，而將文件名放在目錄末尾的堆棧中。如上圖所示的這種方式。這種方法的優(yōu)點是當(dāng)目錄項被移除后，下一個文件將能夠正常匹配移除文件的空間。當(dāng)然，必須要對堆進(jìn)行管理，因為在處理文件名的時候也會發(fā)生缺頁異常。

到目前為止的所有設(shè)計中，在需要查找文件名時，所有的方案都是線性的從頭到尾對目錄進(jìn)行搜索。對于特別長的目錄，線性搜索的效率很低。提高文件檢索效率的一種方式是在每個目錄上使用哈希表(hash table)，也叫做散列表。我們假設(shè)表的大小為 n，在輸入文件名時，文件名被散列在 0 和 n - 1 之間，例如，它被 n 除，并取余數(shù)?；蛘邔?gòu)成文件名字的字求和或類似某種方法。

無論采用哪種方式，在添加一個文件時都要對與散列值相對應(yīng)的散列表進(jìn)行檢查。如果沒有使用過，就會將一個指向目錄項的指針指向這里。文件目錄項緊跟著哈希表后面。如果已經(jīng)使用過，就會構(gòu)造一個鏈表（這種構(gòu)造方式是不是和 HashMap 使用的數(shù)據(jù)結(jié)構(gòu)一樣？），鏈表的表頭指針存放在表項中，并通過哈希值將所有的表項相連。

查找文件的過程和添加類似，首先對文件名進(jìn)行哈希處理，在哈希表中查找是否有這個哈希值，如果有的話，就檢查這條鏈上所有的哈希項，查看文件名是否存在。如果哈希不在鏈上，那么文件就不在目錄中。

使用哈希表的優(yōu)勢是查找非常迅速，缺點是管理起來非常復(fù)雜。只有在系統(tǒng)中會有成千上萬個目錄項存在時，才會考慮使用散列表作為解決方案。

另外一種在大量目錄中加快查找指令目錄的方法是使用緩存，緩存查找的結(jié)果。在開始查找之前，會首先檢查文件名是否在緩存中。如果在緩存中，那么文件就能立刻定位。當(dāng)然，只有在較少的文件下進(jìn)行多次查找，緩存才會發(fā)揮最大功效。

共享文件

當(dāng)多個用戶在同一個項目中工作時，他們通常需要共享文件。如果這個共享文件同時出現(xiàn)在多個用戶目錄下，那么他們協(xié)同工作起來就很方便。下面的這張圖我們在上面提到過，但是有一個更改的地方，就是 C 的一個文件也出現(xiàn)在了 B 的目錄下。

如果按照如上圖的這種組織方式而言，那么 B 的目錄與該共享文件的聯(lián)系稱為 鏈接(link)。那么文件系統(tǒng)現(xiàn)在就是一個 有向無環(huán)圖(Directed Acyclic Graph, 簡稱 DAG)，而不是一棵樹了。

在圖論中，如果一個有向圖從任意頂點出發(fā)無法經(jīng)過若干條邊回到該點，則這個圖是一個有向無環(huán)圖，我們不會在此著重探討關(guān)于圖論的東西，大家可以自行 google。

將文件系統(tǒng)組織成為有向無環(huán)圖會使得維護(hù)復(fù)雜化，但也是必須要付出的代價。

共享文件很方便，但這也會帶來一些問題。如果目錄中包含磁盤地址，則當(dāng)鏈接文件時，必須把 C 目錄中的磁盤地址復(fù)制到 B 目錄中。如果 B 或者 C 隨后又向文件中添加內(nèi)容，則僅在執(zhí)行追加的用戶的目錄中顯示新寫入的數(shù)據(jù)塊。這種變更將會對其他用戶不可見，從而破壞了共享的目的。

有兩種方案可以解決這種問題。

第一種解決方案，磁盤塊不列入目錄中，而是會把磁盤塊放在與文件本身相關(guān)聯(lián)的小型數(shù)據(jù)結(jié)構(gòu)中。目錄將指向這個小型數(shù)據(jù)結(jié)構(gòu)。這是 UNIX 中使用的方式（小型數(shù)據(jù)結(jié)構(gòu)就是 inode）。

在第二種解決方案中，通過讓系統(tǒng)建立一個類型為 LINK 的新文件，并把該文件放在 B 的目錄下，使得 B 與 C 建立鏈接。新的文件中只包含了它所鏈接的文件的路徑名。當(dāng) B 想要讀取文件時，操作系統(tǒng)會檢查 B 的目錄下存在一個類型為 LINK 的文件，進(jìn)而找到該鏈接的文件和路徑名，然后再去讀文件，這種方式稱為 符號鏈接(symbolic linking)。

上面的每一種方法都有各自的缺點，在第一種方式中，B 鏈接到共享文件時，inode 記錄文件的所有者為 C。建立一個鏈接并不改變所有關(guān)系，如下圖所示。

第一開始的情況如圖 a 所示，此時 C 的目錄的所有者是 C ，當(dāng)目錄 B 鏈接到共享文件時，并不會改變 C 的所有者關(guān)系，只是把計數(shù) + 1，所以此時 系統(tǒng)知道目前有多少個目錄指向這個文件。然后 C 嘗試刪除這個文件，這個時候有個問題，如果 C 把文件移除并清除了 inode 的話，那么 B 會有一個目錄項指向無效的節(jié)點。如果 inode 以后分配給另一個文件，則 B 的鏈接指向一個錯誤的文件。系統(tǒng)通過 inode 可知文件仍在被引用，但是沒有辦法找到該文件的全部目錄項以刪除它們。指向目錄的指針不能存儲在 inode 中，原因是有可能有無數(shù)個這樣的目錄。

所以我們能做的就是刪除 C 的目錄項，但是將 inode 保留下來，并將計數(shù)設(shè)置為 1 ，如上圖 c 所示。c 表示的是只有 B 有指向該文件的目錄項，而該文件的前者是 C 。如果系統(tǒng)進(jìn)行記賬操作的話，那么 C 將繼續(xù)為該文件付賬直到 B 決定刪除它，如果是這樣的話，只有到計數(shù)變?yōu)?0 的時刻，才會刪除該文件。

對于符號鏈接，以上問題不會發(fā)生，只有真正的文件所有者才有一個指向 inode 的指針。鏈接到該文件上的用戶只有路徑名，沒有指向 inode 的指針。當(dāng)文件所有者刪除文件時，該文件被銷毀。以后若試圖通過符號鏈接訪問該文件將會失敗，因為系統(tǒng)不能找到該文件。刪除符號鏈接不會影響該文件。

符號鏈接的問題是需要額外的開銷。必須讀取包含路徑的文件，然后要一個部分接一個部分地掃描路徑，直到找到 inode 。這些操作也許需要很多次額外的磁盤訪問。此外，每個符號鏈接都需要額外的 inode ，以及額外的一個磁盤塊用于存儲路徑，雖然如果路徑名很短，作為一種優(yōu)化，系統(tǒng)可以將它存儲在 inode 中。符號鏈接有一個優(yōu)勢，即只要簡單地提供一個機(jī)器的網(wǎng)絡(luò)地址以及文件在該機(jī)器上駐留的路徑，就可以連接全球任何地方機(jī)器上的文件。

還有另一個由鏈接帶來的問題，在符號鏈接和其他方式中都存在。如果允許鏈接，文件有兩個或多個路徑。查找一指定目錄及其子目錄下的全部文件的程序?qū)⒍啻味ㄎ坏奖绘溄拥奈募＠?，一個將某一目錄及其子目錄下的文件轉(zhuǎn)存到磁帶上的程序有可能多次復(fù)制一個被鏈接的文件。進(jìn)而，如果接著把磁帶讀入另一臺機(jī)器，除非轉(zhuǎn)出程序具有智能，否則被鏈接的文件將被兩次復(fù)制到磁盤上，而不是只是被鏈接起來。

相關(guān)參考：

https://zhuanlan.zhihu.com/p/41358013

https://www.linuxtoday.com/blog/what-is-an-inode.html

https://www.lifewire.com/what-is-fragmentation-defragmentation-2625884

https://www.geeksforgeeks.org/free-space-management-in-operating-system/

https://sites.ualberta.ca/dept/chemeng/AIX-43/share/man/info/C/a_doc_lib/aixprggd/genprogc/fsyslayout.htm

https://en.wikipedia.org/wiki/Disk_partitioning

https://en.wikipedia.org/wiki/Master_boot_record

https://en.wikipedia.org/wiki/Booting

https://www.computerhope.com/jargon/f/fileprot.htm

https://en.wikipedia.org/wiki/File_attribute

https://en.wikipedia.org/wiki/Make_(software)

https://unix.stackexchange.com/questions/60034/what-are-character-special-and-block-special-files-in-a-unix-system

https://www.computerhope.com/jargon/d/director.htm

https://www.computerhope.com/jargon/r/regular-file.htm

https://baike.baidu.com/item/固態(tài)硬盤/453510?fr=aladdin

《現(xiàn)代操作系統(tǒng)》第四版

《Modern Operation System》fourth

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。