当前位置：首页 > news >正文

文件的分配方式（对磁盘非空闲块的管理）和文件存储空间的管理（对磁盘空闲块的管理）

news 2025/10/27 22:01:32

第一部分：文件的分配方式 (Allocation Methods)
- 1. 连续分配
- 2. 链接分配
- 3. 索引分配
第二部分：文件存储空间的管理 (Free Space Management)
- 1. 空闲表法 / 空闲链表法
- 2. 空闲块位图 / 位向量
- 3. 空闲块链表
- 4. 成组链接
总结对比

第一部分：文件的分配方式 (Allocation Methods)

这部分解决的是：当一个文件需要存储到磁盘上时，操作系统如何为它分配磁盘块？ 其核心目标是高效地进行文件的随机访问和顺序访问，并减少外部碎片。主要有三种方式：

1. 连续分配

原理：每个文件在磁盘上占据一组连续的物理块。在文件的目录项中，只需要记录起始块号和文件长度（以块为单位）。
- 例如：文件A（长度3块） -> 起始块号：5 -> 则占据块5, 6, 7。
优点：
1. 实现简单：目录项信息最少。
2. 性能极高：
  - 顺序访问性能最好，因为磁头移动距离最小。
  - 随机访问容易，计算 目标地址 = 起始地址 + 偏移量 即可。
缺点：
1. 外部碎片：随着文件的创建和删除，磁盘上会留下许多空闲的“洞”，很难分配给新文件，必须定期进行“磁盘压缩”。
2. 文件长度不易动态增长：创建文件时必须声明其最终大小。如果原位置后面没有足够的连续空间，文件就无法扩展，必须被移动。
适用场景：CD-ROM、DVD等只读介质，或者文件大小固定的系统。

2. 链接分配

原理：文件的数据块可以分散在磁盘的任何地方。每个块的末尾有一个指针，指向文件的下一个块。目录项只需记录第一块的块号和最后一块的块号。
- 例如：文件A -> 起始块号：5 -> 5 -> 9 -> 12 -> NULL
优点：
1. 解决了外部碎片：利用了每一个空闲块，磁盘利用率高。
2. 文件可以动态增长：只需从空闲空间管理中获取一个新块，并修改最后一个块的指针指向它即可。
缺点：
1. 只能顺序访问：要访问第i块，必须从第一块开始，沿着指针链一路读下去，性能差（O(n)）。
2. 可靠性差：任何一个指针丢失或损坏都会导致文件后续部分全部丢失。
3. 指针占用空间：每个数据块需要拿出少量字节存储指针。
变体：文件分配表 (FAT)
- 为了解决链接分配的缺点，MS-DOS和Windows早期文件系统采用了FAT。
- 原理：把每个文件的指针链提取出来，集中存放在磁盘卷开头的一张大表（File Allocation Table）中。
- 每个磁盘块在F表中对应一个表项，表项内容指向该文件的下一个块号。文件的目录项只需记录起始块号。
- 优点：
  - 整个FAT表可以缓存到内存，极大地加快了随机访问的速度（无需读磁盘块就能遍历链）。
  - 解决了指针占用数据块空间的问题。
- 缺点：FAT表本身可能非常大，需要占用大量内存。

3. 索引分配

原理：为每个文件创建一个独立的索引块。索引块是一个磁盘块，它里面不存文件数据，而是存放指向该文件所有数据块的指针数组。目录项中记录该索引块的地址。
- 例如：文件A的索引块 -> [5, 9, 12, ...]
优点：
1. 完美支持直接/随机访问：要访问第i块，先去索引块找到第i个指针，然后直接访问该数据块。性能是O(1)（一次读索引块，一次读数据块）。
2. 没有外部碎片。
3. 文件可以动态增长（只要索引块还有空位）。
缺点：
1. 空间开销：每个文件都需要至少一个额外的索引块。小文件会有空间浪费。
2. 文件大小限制：一个索引块能存储的指针数量是有限的，限制了文件的最大大小。
解决大文件方案：
- 链式索引：一个索引块指向下一个索引块（如V7 Unix）。
- 多级索引：主索引块指向多个二级索引块，二级索引块再指向数据块（如Linux ext2/ext3）。
- 组合索引：索引块中同时包含直接指针、一级间接指针、二级间接指针等（如Unix Inode）。

第二部分：文件存储空间的管理 (Free Space Management)

这部分解决的是：操作系统如何跟踪和分配磁盘上的空闲块？ 当需要创建新文件或扩展现有文件时，系统需要快速找到可用的空闲块。

1. 空闲表法 / 空闲链表法

原理：类似于连续分配，系统维护一张表或一个链表，每个表项记录一个连续空闲区的起始块号和块数。
分配：通常采用首次适应或最佳适应算法来寻找合适的空闲区。
回收：回收空间时需要与相邻的空闲区进行合并。
特点：容易产生外部碎片，适用于连续分配方式。

2. 空闲块位图 / 位向量

原理：用一个巨大的位图 (Bitmap) 来表示整个磁盘的空闲状态。每个磁盘块对应一个二进制位。
- 1 代表该块已分配（繁忙）。
- 0 代表该块空闲。
操作：
- 分配：扫描位图，找到第一个为 0 的位，将其置 1，并返回对应的块号。
- 回收：将相应块号对应的位由 1 置为 0。
优点：
- 查找效率高：位图可以全部载入内存，进行快速的位操作和查找（现代CPU有专门指令）。
- 简单可靠。
缺点：
- 位图本身需要占用一定的存储空间（但相对于整个磁盘来说很小）。例如，管理一个4TB（2^32字节）、4KB每块的磁盘，位图需要 2^32 / 2^12 = 2^20 = 1M 个位，即128KB。
适用场景：最常用的方法，如Windows NTFS、Linux ext系列文件系统均采用此法。

3. 空闲块链表

原理：将所有空闲的磁盘块用指针链接成一个链表。系统保存一个指向第一个空闲块的指针。
操作：
- 分配：从链头取下一块，将指针指向下一个空闲块。
- 回收：将回收的块插入到链表的头部。
优点：实现简单。
缺点：
- 效率低：每次分配和回收都需要进行I/O操作来读写链表指针，无法在内存中完成所有操作，性能差。
- 不适合大型文件系统。

4. 成组链接

原理：是空闲链表法和索引法的结合，Unix文件系统所采用的高效方法。
工作方式：
1. 将所有空闲块分成若干组，如每组100个块。
2. 每一组的第一个空闲块不用于存储数据，而是用来存储下一组100个空闲块的块号（相当于一个索引）。
3. 第一组的空闲块信息（共100个块号）缓存在内存中。
操作：
- 分配：直接从内存中的组里分配一个块。如果这组只剩最后一个块，这个块里存放的是下一组的块号列表，系统会先把下一组的信息读入内存，再分配这个块。
- 回收：将回收的块号放入内存中的组。如果组已满（100个），就把当前内存中的这100个块号写回到新回收的块中，然后用内存记录这个新回收的块（作为新组的头），新组里现在有1个块（它自己）。
优点：
- 绝大多数操作都在内存中完成，效率极高。
- 不需要像位图那样占用额外的存储空间（信息存储在空闲块自身）。
缺点：实现相对复杂。

总结对比

特性	文件的分配方式 (管理已用块)	存储空间管理 (管理空闲块)
核心问题	文件数据如何排布以利于访问？	如何快速找到空闲块分配给新文件？
主要方法	1. 连续分配 2. 链接分配 (FAT) 3. 索引分配 (Inode)	1. 空闲表/链表法 2. 位图法 (最常用) 3. 成组链接法 (Unix)
设计目标	访问速度、碎片、动态增长	跟踪效率、分配/回收速度
相互关系	分配方式从存储管理申请空闲块；文件删除时又向存储管理归还空闲块。	存储管理为分配方式提供底层支持。