空閒空間的管理

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

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

• 空閒表法：使用一個表格來維護磁碟空閒塊的資訊。表格中的每個條目表示一個空閒塊，包含塊的起始地址和長度。當需要儲存資料塊時，可以在表格中找到合適的空閒塊，並將其標記為已佔用。
• 空閒連結串列法：使用連結串列來維護磁碟空閒塊的資訊。每個連結串列節點表示一個空閒塊，包含塊的起始地址和長度，以及指向下一個空閒塊的指標。通過遍歷連結串列，可以找到合適的空閒塊，並將其標記為已佔用。
• 點陣圖法：使用一個點陣圖來表示磁碟的空閒塊資訊。點陣圖中的每個位表示一個塊的狀態，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操作的開銷，目錄查詢時可以將當前使用的目錄快取到記憶體中。這樣，在以後需要使用該目錄中的檔案時，只需在記憶體中進行操作，減少了磁碟存取次數，提高了檔案系統的存取速度。

總結

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

檔案系統的結構主要包括普通檔案和目錄兩類。普通檔案是儲存使用者資料的基本單位，目錄用於組織和管理檔案。

總的來說，空閒空間的管理和檔案系統的結構設計都是為了提高檔案系統的效能和效率，以滿足使用者對儲存和存取資料的需求。