空閑空間的管理

關於空閑空間的管理，前面提到的是已被占用的數據塊的組織和管理。接下來要解決的問題是，當我要保存一個數據塊時，應該將其放在硬碟的哪個位置。難道需要掃描所有的塊，隨意找個空的地方放嗎？

然而，這種方式效率太低了。因此，我們需要引入一種管理磁碟空閑空間的機制。下麵介紹幾種常見的方法：

• 空閑表法：使用一個表格來維護磁碟空閑塊的信息。表格中的每個條目表示一個空閑塊，包含塊的起始地址和長度。當需要保存數據塊時，可以在表格中找到合適的空閑塊，並將其標記為已占用。
• 空閑鏈表法：使用鏈表來維護磁碟空閑塊的信息。每個鏈表節點表示一個空閑塊，包含塊的起始地址和長度，以及指向下一個空閑塊的指針。通過遍歷鏈表，可以找到合適的空閑塊，並將其標記為已占用。
• 點陣圖法：使用一個點陣圖來表示磁碟的空閑塊信息。點陣圖中的每個位表示一個塊的狀態，1表示已占用，0表示空閑。通過對點陣圖進行操作，可以快速找到空閑塊並標記為已占用。

你可以想象一下如果給你一張MySQL表，在已經分配好所有id主鍵後，你可能會覺得一直順序寫入就可以了，但是一旦中間有刪除的操作，這就會存在有空閑的id行沒用上，你去保存有空閑的數據行可以怎麼做？

空閑表法

它通過建立一張表來記錄所有的空閑區域，表中包括空閑區的第一個塊號和該空閑區的塊個數。需要註意的是，這種方法適用於連續分配。如圖所示：

當系統需要分配磁碟空間時，它會順序掃描空閑表的內容，直到找到一個合適的空閑區域為止。而當用戶撤銷一個文件時，系統會回收文件的空間。此時，系統會再次順序掃描空閑表，尋找一個空閑表條目，並將釋放空間的第一個物理塊號及其占用的塊數填入該條目中。

然而，空閑表法在空閑區較少的情況下才能發揮較好的效果。如果存儲空間中存在大量小的空閑區域，空閑表會變得非常龐大，從而降低查詢效率。此外，這種分配技術適用於建立連續文件。

空閑鏈表法

除了空閑表法之外，我們還可以使用空閑鏈表法來管理磁碟的空閑空間。在空閑鏈表法中，我們使用鏈表的方式來組織和管理空閑塊。如下圖：

每個空閑塊都包含一個指針，指向下一個空閑塊。當需要創建文件時，我們可以從鏈表的頭部開始依次獲取所需的塊數。相反地，當需要回收空間時，我們可以將這些空閑塊依次接入鏈表的頭部。

使用空閑鏈表法的好處是它的實現相對簡單，只需要在主存中保存一個指針，指向鏈表的頭部即可。然而，空閑鏈表法也有一些局限性。由於無法進行隨機訪問，它的工作效率較低。每當在鏈表上增加或移動空閑塊時，都需要進行大量的輸入/輸出操作。此外，空閑鏈表法也會消耗一定的存儲空間，因為每個數據塊都需要包含一個指針。

需要註意的是，空閑鏈表法和空閑表法都不適合用於大型文件系統，因為它們會導致空閑表或空閑鏈表變得過大。在大型文件系統中，我們需要考慮更高效的管理方法來提高性能和減少空間消耗。

點陣圖法

除了空閑表法和空閑鏈表法，我們還可以使用點陣圖法來管理磁碟的空閑空間。點陣圖法利用二進位位來表示磁碟中每個塊的使用情況，每個塊都有一個對應的二進位位。

當二進位位的值為0時，表示對應的盤塊是空閑的；當二進位位的值為1時，表示對應的盤塊已經被分配。點陣圖的形式如下所示：

11111111111111100011101101111...

在 Linux 文件系統就採用了點陣圖的方式來管理空閑空間，點陣圖不僅用於管理數據空閑塊，還用於管理inode（索引節點）空閑塊。因為inode也是存儲在磁碟上的，所以需要對其進行管理。

點陣圖法的優點是實現簡單，存儲空間占用小。通過位運算可以快速判斷一個盤塊是否空閑，以及找到一個空閑盤塊。由於點陣圖法不需要額外的數據結構來記錄空閑塊的信息，因此在大型文件系統中，點陣圖法往往是一種較為高效的管理方法。

文件系統的結構

文件系統的結構主要包括普通文件和目錄兩類。普通文件是存儲用戶數據的基本單位，而目錄則用於組織和管理文件。下麵我們來詳細瞭解它們的存儲方式。

文件的存儲

在Linux文件系統中，文件的存儲是通過點陣圖的方式進行管理的。當用戶創建一個新文件時，Linux內核會根據inode的點陣圖來找到空閑可用的inode，併進行分配。當需要存儲數據時，它會通過塊的點陣圖來找到空閑的數據塊，併進行分配。然而，經過仔細計算後，我們會發現存在一些問題。

數據塊的點陣圖是存儲在磁碟塊中的，假設每個塊的大小為4K，那麼一個塊能夠表示的位數就是4 × 1024 × 8 = 2^{15個塊。由於每個數據塊的大小為4K，那麼最大可以表示的空間就是2}15 × 4 × 1024 = 2^27個位元組，即128M。

換句話說，按照上述結構，如果使用"一個塊的點陣圖 + 一系列的塊"以及"一個塊的inode點陣圖 + 一系列的inode結構"來表示空間，最大能夠表示的空間也只有128M。然而，現在很多文件的大小都超過了這個限制。

因此，在Linux文件系統中，引入了塊組的概念來解決這個問題。每個塊組包含一個塊的點陣圖和一系列的塊，以及一個inode的點陣圖和一系列的inode結構。通過增加塊組的數量，文件系統就能夠表示更大的文件。這樣，用戶就可以利用多個塊組來存儲大文件，從而突破了128M的限制。

最前面的第一個塊是引導塊，在系統啟動時用於啟用引導，接著後面就是一個一個連續的塊組了，塊組的內容如下：

• 超級塊，它包含了文件系統的重要信息，比如inode總個數、塊總個數、每個塊組的inode個數、每個塊組的塊個數等等。超級塊對於文件系統的正常運行起著至關重要的作用。
• 塊組描述符，它包含了文件系統中各個塊組的狀態信息，比如塊組中空閑塊和inode的數目等。每個塊組都包含了文件系統中所有塊組的組描述符信息，這樣可以方便地管理和維護整個文件系統。
• 數據點陣圖和inode點陣圖，它們用於表示對應的數據塊或inode是空閑的，還是被使用中。數據點陣圖和inode點陣圖的使用可以有效地管理文件系統的空閑空間和資源。
• inode列表，它包含了塊組中所有的inode。inode用於保存文件系統中與各個文件和目錄相關的所有元數據，比如文件的大小、許可權、所屬用戶等。
• 數據塊，它包含了文件的有用數據。

你可能會發現每個塊組裡有很多重覆的信息，比如超級塊和塊組描述符表，這兩個都是全局信息，而且非常重要。這麼做有兩個原因：

• 一是如果系統崩潰破壞了超級塊或塊組描述符，有關文件系統結構和內容的所有信息都會丟失。如果有冗餘的副本，該信息是可能恢復的。
• 二是通過使文件和管理數據儘可能接近，可以減少磁頭尋道和旋轉，從而提高文件系統的性能。不過，Ext2的後續版本採用了稀疏技術。稀疏技術的做法是，超級塊和塊組描述符表不再存儲到文件系統的每個塊組中，而是只寫入到塊組0、塊組1和其他ID可以表示為3、5、7的冪的塊組中。這樣可以進一步減少重覆的信息，提高文件系統的存儲效率和性能。

目錄的存儲

在前面我們已經瞭解了普通文件的存儲方式，但是目錄作為一個特殊文件，它的存儲方式又是怎樣的呢？

基於 Linux 一切皆文件的設計思想，目錄實際上也是一個文件，你甚至可以使用vim打開它。目錄文件也有一個inode，其中也包含指向其他塊的指針。

然而，與普通文件不同的是，普通文件的塊中保存的是文件的實際數據，而目錄文件的塊中保存的是目錄中每個文件的信息。

目錄文件的塊中最簡單的保存格式是一個列表，即將目錄下的文件信息（例如文件名、文件inode、文件類型等）逐項列在表中。

列表中的每一項代表該目錄下的文件名和對應的inode。通過這個inode，我們可以方便地找到真正的文件。

通常，目錄文件的第一項是「.」，表示當前目錄，第二項是「..」，表示上一級目錄，隨後是每個文件的文件名和對應的inode(如果想要查看的話，vim是不可以直接顯示inode的，可以使用ls -i命令來顯示目錄中的文件名和對應的inode號碼)。然而，當一個目錄包含大量文件時，按順序逐項查找效率較低。

為了提高查找效率，目錄文件的存儲格式可以改為哈希表。通過對文件名進行哈希計算並保存哈希值，我們可以通過哈希值快速定位到相應的塊，以獲取文件信息。Linux系統的ext文件系統採用了這種哈希表的存儲方式，它的優點在於查找速度快、插入和刪除操作相對簡單，但需要採取一些預防措施以避免哈希衝突。

目錄查詢是通過在磁碟上反覆搜索完成，需要不斷地進行 I/O 操作，開銷較大。所以，為了減少磁碟I/O操作的開銷，目錄查詢時可以將當前使用的目錄緩存到記憶體中。這樣，在以後需要使用該目錄中的文件時，只需在記憶體中進行操作，減少了磁碟訪問次數，提高了文件系統的訪問速度。

總結

空閑空間的管理是文件系統中一個重要的問題。為了有效地管理磁碟空閑空間，我們可以使用空閑表法、空閑鏈表法和點陣圖法等方法。其中，空閑表法使用表格來維護磁碟空閑塊的信息，空閑鏈表法使用鏈表來維護磁碟空閑塊的信息，點陣圖法使用點陣圖來表示磁碟空閑塊的狀態。每種方法都有其優缺點，適用於不同規模和需求的文件系統。

文件系統的結構主要包括普通文件和目錄兩類。普通文件是存儲用戶數據的基本單位，目錄用於組織和管理文件。

總的來說，空閑空間的管理和文件系統的結構設計都是為了提高文件系統的性能和效率，以滿足用戶對存儲和訪問數據的需求。