操作系统 · 文件系统6 （空闲空间列表）
2021-12-10 17:16:49
操作系统 · 文件系统6（空闲空间列表）
在文件系统中，空闲空间列表是一个重要的组成部分，它用于跟踪存储中的所有未分配的数据块。这些数据块尚未被任何文件占用，因此可以被系统用于未来的文件创建或扩展。
一、空闲空间列表的存储位置
空闲空间列表本身需要存储在磁盘的某个位置，以便系统能够随时访问和更新它。这个位置可以是磁盘的特定区域，如磁盘的开头或结尾，也可以是分散在磁盘上的多个位置。具体存储位置取决于文件系统的设计和实现。
二、空闲空间列表的最佳数据结构
为了高效地管理空闲空间列表，需要选择一种合适的数据结构。以下是几种常见的空闲空间列表数据结构：
位图（Bitmap）
描述：位图是一种紧凑且高效的数据结构，用于表示一系列二进制状态（如空闲或已分配）。在位图中，每个数据块都对应一个位（bit），位的状态（0或1）表示数据块的空闲或已分配状态。
优点：
访问速度快：由于位图在内存中连续存储，因此可以快速地访问和更新任何数据块的状态。
空间效率高：位图只占用很少的内存空间，因为每个数据块只需要一个位来表示。
缺点：
初始化成本高：对于大型磁盘，位图可能需要占用大量的内存空间，并且在初始化时需要扫描整个磁盘以填充位图。
碎片问题：如果空闲空间在磁盘上分布不均匀，位图可能会变得稀疏，导致查找空闲块时效率降低。
示例：MySQL的InnoDB存储引擎在Extent（64个Page数据页）单元中使用了位图（XDES_BITMAP，128个bit）来标识Page是否空闲。
数据一致性：为了确保内存和磁盘上的位图数据一致，需要在分配数据块之前先将位图更新到磁盘上，然后再在内存中设置相应的位。这样可以避免在宕机时发生数据丢失或覆盖写的问题。
链式列表（Linked List）
描述：链式列表是一种动态数据结构，由一系列节点组成，每个节点包含数据块的信息和指向下一个节点的指针。在空闲空间列表中，每个节点表示一个空闲的数据块或一组连续的数据块。
优点：
灵活性高：链式列表可以动态地添加或删除节点，以适应磁盘空间的变化。
易于管理：链式列表可以方便地遍历和搜索空闲块。
缺点：
访问速度慢：由于链式列表在磁盘上可能不连续存储，因此访问节点时可能需要多次磁盘I/O操作。
指针开销：每个节点都需要额外的空间来存储指针，这增加了空间开销。
分组列表（Grouped List）
描述：分组列表将空闲空间划分为多个组，每个组包含一组连续的数据块。每个组都有一个头节点，用于存储该组的信息（如起始地址、大小等）。头节点通常存储在磁盘的特定区域，以便快速访问。
优点：
减少碎片：通过将空闲空间划分为多个组，可以减少碎片的产生，提高磁盘空间的利用率。
访问速度快：由于头节点在磁盘上连续存储，因此可以快速地访问任何组的信息。
缺点：
管理复杂：分组列表需要维护多个组的信息，并且需要在分配和释放空间时更新组的信息。
空间开销：每个组都需要额外的空间来存储头节点信息。
MySQL的页管理：MySQL的页管理也使用了类似分组列表的思想。它使用Inode Entry（segment）通过三种Extent元素（64个Page数据页）的链表（free、not_full、full）来分层管理空闲、未满、已满的Page页链表。同时，也使用数组直接存储了Page页的信息。
综上所述，空闲空间列表是文件系统中用于跟踪未分配数据块的重要数据结构。在选择空闲空间列表的数据结构时，需要权衡访问速度、空间效率、管理复杂性和碎片问题等因素。位图、链式列表和分组列表是三种常见的空闲空间列表数据结构，它们各有优缺点，适用于不同的应用场景。
热门标签
