文件系统的磁盘空间分配与回收策略

文件系统的磁盘空间分配策略

连续分配

连续分配是一种较为简单直观的磁盘空间分配策略。在这种策略下，每个文件在磁盘上都占据一组连续的块。例如，假设一个文件需要 5 个磁盘块来存储，系统会在磁盘上找到连续的 5 个空闲块分配给该文件。

优点

顺序访问效率高：当文件以顺序方式读取或写入时，磁头可以沿着磁盘表面连续移动，无需频繁寻道。例如，对于大型视频文件的播放，连续分配使得数据可以快速且流畅地被读取，极大地提高了播放的流畅度。
实现简单：文件系统在管理连续分配时，只需要记录文件起始块的地址以及文件所占用的块数。例如，在一个简单的文件系统中，文件的元数据（如文件大小、起始块号等）可以简单地存储在文件目录项中，系统通过起始块号和块数就能轻松定位文件的所有数据块。

缺点

磁盘碎片问题：随着文件的不断创建和删除，磁盘上会出现许多不连续的空闲块，即外部碎片。例如，假设磁盘最初是连续的空闲空间，先后创建了大小为 10 块、20 块和 30 块的文件 A、B、C，之后删除了文件 B，此时磁盘上就会出现一个 20 块的空闲区域，但如果接下来要创建一个 25 块的文件 D，由于没有连续的 25 块空闲空间，即使总的空闲空间足够，文件 D 也无法创建。
文件大小受限：如果磁盘上没有足够大的连续空闲空间，即使总的空闲空间足够，也无法创建大文件。比如，磁盘总空闲空间为 100 块，但最大的连续空闲空间只有 30 块，那么大于 30 块的文件就无法在该磁盘上创建。

代码示例（简单模拟连续分配）

class Disk:
    def __init__(self, total_blocks):
        self.total_blocks = total_blocks
        self.free_blocks = list(range(total_blocks))
        self.allocated_files = {}

    def allocate(self, file_name, size):
        if len(self.free_blocks) < size:
            print(f"Not enough free space to allocate {file_name}")
            return
        start_block = self.free_blocks[0]
        end_block = start_block + size - 1
        if end_block >= len(self.free_blocks):
            print(f"Not enough contiguous space to allocate {file_name}")
            return
        allocated_blocks = self.free_blocks[:size]
        self.free_blocks = self.free_blocks[size:]
        self.allocated_files[file_name] = allocated_blocks
        print(f"{file_name} allocated from block {start_block} to {end_block}")

    def deallocate(self, file_name):
        if file_name not in self.allocated_files:
            print(f"{file_name} not found")
            return
        blocks = self.allocated_files[file_name]
        self.free_blocks.extend(blocks)
        self.free_blocks.sort()
        del self.allocated_files[file_name]
        print(f"{file_name} deallocated")

# 使用示例
disk = Disk(100)
disk.allocate('file1', 10)
disk.deallocate('file1')

链接分配

链接分配解决了连续分配中的一些问题，它允许文件的各个块分散存储在磁盘上，通过链表的方式将这些块链接起来。

隐式链接

在隐式链接中，每个数据块中除了存储数据外，还包含指向下一个数据块的指针。文件的目录项中只记录文件的起始块号。例如，当读取文件时，系统从起始块开始，通过块中的指针依次读取后续的块。

优点
- 有效利用磁盘空间：避免了外部碎片问题，只要有空闲块，文件就可以继续增长。比如，一个文件最初占用 5 个块，随着数据的增加，即使磁盘上没有连续的空闲块，系统也可以为其分配分散的空闲块，通过指针将它们链接起来。
- 文件大小灵活：文件可以动态增长，不受连续空闲空间大小的限制。只要磁盘上有空闲块，文件就能不断扩大。
缺点
- 随机访问效率低：由于文件块是通过链表链接的，要访问文件中的某个特定块，需要从起始块开始依次遍历链表，直到找到目标块。例如，要访问文件的第 100 块，即使知道块号，也需要从起始块开始，通过 99 次指针跳转才能找到，这大大增加了访问时间。
- 指针可靠性问题：如果某个块中的指针损坏，可能导致后续块无法访问，从而使整个文件损坏。而且，指针占用一定的磁盘空间，减少了实际可用于存储数据的空间。

显式链接

显式链接将文件块之间的链接信息集中存储在一个表中，通常称为文件分配表（FAT）。FAT 中每个表项对应一个磁盘块，表项的值为该块的下一个块的块号。文件的目录项中记录文件的起始块号。

优点
- 随机访问性能提升：与隐式链接相比，通过 FAT 表可以直接根据块号找到目标块的下一个块的位置，不需要从起始块开始依次遍历。例如，要访问文件的第 n 块，只需要在 FAT 表中查找第 n 块对应的表项，获取下一个块的块号，大大提高了随机访问效率。
- 可靠性增强：由于链接信息集中存储在 FAT 表中，不像隐式链接那样分散在各个数据块中，因此某个数据块损坏不会影响整个文件的链接结构，只要 FAT 表本身没有损坏，文件就可以正常访问。
缺点
- FAT 表空间开销：FAT 表需要占用一定的磁盘空间，对于大容量磁盘，FAT 表可能会非常大。例如，对于一个有 1000000 个块的磁盘，FAT 表就需要 1000000 个表项，每个表项如果占用 4 字节，那么 FAT 表就需要 4MB 的空间。
- FAT 表维护成本：每次文件的创建、删除或修改都需要更新 FAT 表，这增加了系统的维护开销。例如，当一个文件删除时，不仅要释放文件占用的块，还需要在 FAT 表中清除相应的链接信息。

代码示例（简单模拟显式链接）

class Disk:
    def __init__(self, total_blocks):
        self.total_blocks = total_blocks
        self.free_blocks = list(range(total_blocks))
        self.fat = [-1] * total_blocks
        self.allocated_files = {}

    def allocate(self, file_name, size):
        if len(self.free_blocks) < size:
            print(f"Not enough free space to allocate {file_name}")
            return
        start_block = self.free_blocks[0]
        current_block = start_block
        for _ in range(size - 1):
            next_block = self.free_blocks[1]
            self.fat[current_block] = next_block
            self.free_blocks.pop(0)
            current_block = next_block
        self.free_blocks.pop(0)
        self.allocated_files[file_name] = start_block
        print(f"{file_name} allocated starting from block {start_block}")

    def deallocate(self, file_name):
        if file_name not in self.allocated_files:
            print(f"{file_name} not found")
            return
        start_block = self.allocated_files[file_name]
        current_block = start_block
        while current_block != -1:
            next_block = self.fat[current_block]
            self.free_blocks.append(current_block)
            self.fat[current_block] = -1
            current_block = next_block
        self.free_blocks.sort()
        del self.allocated_files[file_name]
        print(f"{file_name} deallocated")

# 使用示例
disk = Disk(100)
disk.allocate('file1', 10)
disk.deallocate('file1')

索引分配

索引分配结合了连续分配和链接分配的优点。在这种策略下，系统为每个文件创建一个索引块，索引块中记录了文件各个数据块的块号。

单层索引

单层索引是最基本的索引分配方式。文件的目录项中记录索引块的块号。例如，当文件需要读取某个数据块时，系统首先从目录项中获取索引块的块号，然后读取索引块，从索引块中找到目标数据块的块号，最后读取目标数据块。

优点
- 随机访问高效：与链接分配相比，索引分配可以直接通过索引块找到目标数据块的块号，大大提高了随机访问效率。例如，对于一个大文件，要访问其中任意一块，只需要读取索引块和目标数据块，无需像链接分配那样依次遍历链表。
- 磁盘空间利用灵活：文件块可以分散存储在磁盘上，避免了外部碎片问题。同时，由于索引块记录了所有数据块的位置，文件大小的增长也不受连续空闲空间的限制。
缺点
- 索引块空间开销：每个文件都需要一个索引块，对于大量小文件，索引块占用的空间可能会比较可观。例如，对于 1000 个小文件，每个文件都需要一个索引块，如果每个索引块占用 1KB 空间，那么仅仅索引块就需要占用 1MB 空间。
- 索引块大小限制：索引块的大小是有限的，如果文件非常大，可能一个索引块无法记录所有数据块的块号。例如，假设一个索引块可以记录 1000 个块号，而一个文件需要 10000 个块，那么就需要多个索引块来管理，这增加了管理的复杂性。

多层索引

为了解决单层索引中索引块大小限制的问题，可以采用多层索引。例如，二级索引中，首先有一个主索引块，主索引块中的每个表项指向一个二级索引块，二级索引块再记录数据块的块号。如果文件更大，还可以采用三级、四级等多层索引。

优点
- 支持大文件：通过多层索引，可以管理非常大的文件。例如，在二级索引中，假设主索引块可以记录 100 个二级索引块的块号，每个二级索引块可以记录 1000 个数据块的块号，那么总共可以管理 100 * 1000 = 100000 个数据块，对于大多数文件来说已经足够。
- 空间利用平衡：对于小文件，只需要使用单层索引甚至不需要索引块（如非常小的文件可以直接在目录项中记录数据块号），而对于大文件则采用多层索引，这样在整体上平衡了索引块的空间开销。
缺点
- 复杂性增加：多层索引增加了文件系统管理的复杂性。从文件的创建、删除到数据的读取和写入，都需要更多的步骤来处理多层索引结构。例如，在写入数据时，需要判断当前索引块是否已满，是否需要创建新的二级索引块等。
- 访问时间增加：对于多层索引，访问一个数据块可能需要多次读取索引块。例如，在二级索引中，要访问一个数据块，可能需要先读取主索引块，再读取二级索引块，最后才能读取数据块，这增加了访问时间。

代码示例（简单模拟单层索引）

class Disk:
    def __init__(self, total_blocks):
        self.total_blocks = total_blocks
        self.free_blocks = list(range(total_blocks))
        self.allocated_files = {}

    def allocate(self, file_name, size):
        if len(self.free_blocks) < size + 1:
            print(f"Not enough free space to allocate {file_name}")
            return
        index_block = self.free_blocks[0]
        self.free_blocks.pop(0)
        data_blocks = []
        for _ in range(size):
            data_block = self.free_blocks[0]
            self.free_blocks.pop(0)
            data_blocks.append(data_block)
        self.allocated_files[file_name] = (index_block, data_blocks)
        print(f"{file_name} allocated with index block {index_block}")

    def deallocate(self, file_name):
        if file_name not in self.allocated_files:
            print(f"{file_name} not found")
            return
        index_block, data_blocks = self.allocated_files[file_name]
        self.free_blocks.append(index_block)
        self.free_blocks.extend(data_blocks)
        self.free_blocks.sort()
        del self.allocated_files[file_name]
        print(f"{file_name} deallocated")

# 使用示例
disk = Disk(100)
disk.allocate('file1', 10)
disk.deallocate('file1')

文件系统的磁盘空间回收策略

基于引用计数的回收

引用计数是一种简单而直接的磁盘空间回收策略。对于每个文件或数据块，系统维护一个引用计数，记录有多少个地方引用了该文件或块。

工作原理

当一个文件被创建时，其引用计数设为 1。如果其他文件或程序创建了对该文件的链接（如硬链接），引用计数加 1。当一个引用被删除（如删除一个硬链接或关闭对文件的访问），引用计数减 1。当引用计数变为 0 时，说明该文件不再被任何地方引用，系统可以回收该文件占用的磁盘空间。

优点

回收及时：一旦文件的引用计数变为 0，就可以立即回收其占用的磁盘空间，不会造成空间的浪费。例如，当一个临时文件被创建并使用完毕后，只要所有对它的引用都被删除，它占用的空间就能马上被回收，供其他文件使用。
实现相对简单：只需要在文件的元数据中增加一个引用计数字段，并在文件创建、链接、删除等操作时更新这个字段即可。例如，在一个简单的文件系统中，文件的目录项可以包含文件大小、起始块号和引用计数等信息，当进行文件操作时，相应地修改引用计数。

缺点

无法处理循环引用：如果存在文件之间的循环引用（如文件 A 引用文件 B，文件 B 又引用文件 A），即使这两个文件不再被其他外部对象引用，它们的引用计数也不会变为 0，导致这些文件占用的磁盘空间无法回收。例如，在一个复杂的数据库系统中，可能存在多个表之间的相互引用，如果形成循环引用，基于引用计数的回收策略就无法处理。
维护开销：每次文件的链接或删除操作都需要更新引用计数，这增加了系统的维护开销。尤其是在文件操作频繁的系统中，频繁的引用计数更新可能会影响系统的性能。

标记 - 清除回收

标记 - 清除是一种更为复杂但功能强大的磁盘空间回收策略，常用于处理循环引用等问题。

工作原理

标记阶段：系统从根对象（如文件系统的根目录）开始，遍历所有的文件和目录，标记所有可以访问到的文件和数据块。例如，从根目录开始，找到所有直接包含的文件和子目录，然后递归地标记子目录中的文件和子目录，以此类推，直到标记完所有可达的文件和块。
清除阶段：在标记完成后，系统遍历整个磁盘空间，回收所有未被标记的文件和数据块。这些未标记的部分就是不再被任何可达对象引用的，也就是可以回收的空间。

优点

处理循环引用：能够有效地处理文件之间的循环引用问题。因为只要从根对象无法到达的文件和块，无论是否存在循环引用，都会在清除阶段被回收。例如，对于前面提到的文件 A 和文件 B 的循环引用情况，只要它们从根目录不可达，就会被回收。
全面回收：可以全面地回收所有不再使用的磁盘空间，不会遗漏任何不可达的文件和块。这对于长时间运行且文件操作复杂的系统来说非常重要，可以避免磁盘空间的碎片化和浪费。

缺点

开销较大：标记 - 清除过程需要遍历整个文件系统，这在大型文件系统中会消耗大量的时间和资源。例如，对于一个包含数百万个文件和目录的大型存储系统，一次标记 - 清除操作可能需要很长时间才能完成，期间可能会影响系统的正常运行。
空间碎片化：在清除过程中，可能会导致磁盘空间碎片化。因为回收的块可能是分散的，后续文件分配时可能难以找到连续的大块空间。例如，回收了 10 个分散的块，而接下来要创建一个需要 8 个连续块的文件，就可能因为没有连续的 8 个块而无法创建。

延迟回收策略

延迟回收策略是在文件删除时并不立即回收其占用的磁盘空间，而是将这些空间标记为可重用，在后续有文件需要分配空间时优先使用这些已标记的空间。

工作原理

当一个文件被删除时，系统并不实际释放其占用的磁盘块，而是将这些块标记为“已删除但可重用”。当有新文件需要分配空间时，系统首先检查这些已标记的块，如果有足够的符合要求的块，就优先分配这些块。只有当已标记的块无法满足需求时，才去寻找真正的空闲块。

优点

减少磁盘 I/O 操作：由于不需要在文件删除时立即进行磁盘块的回收操作（如将块标记为空闲并更新相关的数据结构），减少了磁盘 I/O 操作。这对于磁盘 I/O 性能瓶颈明显的系统来说，可以提高整体性能。例如，在一个频繁进行文件删除和创建的数据库系统中，延迟回收策略可以避免频繁的磁盘块状态更新操作。
提高空间分配效率：优先使用已删除文件的空间，可以减少外部碎片的产生。因为已删除文件的块通常是相邻的，新文件分配这些块时可以获得较好的连续性。例如，一个文件删除后留下了 10 个连续的块，后续创建的文件如果大小合适，可以直接使用这 10 个连续块，提高了空间分配的效率。

缺点

空间占用问题：在文件删除到实际回收空间之间的这段时间，已删除文件的空间仍然被占用，可能导致系统在这段时间内可用空间看起来比实际情况少。例如，一个系统总空间为 100GB，删除了一个 10GB 的文件但采用延迟回收策略，此时系统显示可用空间可能仍然是原来的数值，而不是增加了 10GB，这可能会给用户造成误解。
数据安全隐患：由于已删除文件的空间没有立即回收，在新文件使用这些空间之前，已删除文件的数据仍然存在于磁盘上。这可能会带来数据安全问题，尤其是在多用户或不安全的环境中，可能存在数据被恢复的风险。例如，在公共计算机上，用户删除文件后，其他人可能通过一些数据恢复工具恢复这些文件的数据。

回收策略的综合应用

在实际的文件系统中，往往会综合应用多种回收策略来取长补短。例如，可以结合引用计数和标记 - 清除策略。对于一般的文件，使用引用计数来及时回收空间，而对于可能存在循环引用的复杂文件结构，定期执行标记 - 清除操作来确保所有不再使用的空间都能被回收。同时，对于一些性能敏感的场景，可以适当采用延迟回收策略来减少磁盘 I/O 操作，提高系统的整体性能。在具体实现时，需要根据文件系统的应用场景、性能要求和数据安全需求等因素来合理选择和组合这些回收策略，以达到最优的磁盘空间管理效果。例如，在一个面向普通用户的桌面操作系统文件系统中，可能更注重空间回收的及时性和简单性，以提高用户体验；而在一个企业级的存储系统中，可能更注重数据安全和空间的高效利用，需要综合考虑多种策略来满足复杂的业务需求。