文件存储空间的管理
目录
参考资料：
为了实现上述任何一种文件组织方式，都需要为文件分配盘块，因此必须知道磁盘上哪些盘块是可用于分配的。故在为文件分配磁盘时，除了需要文件分配表外，系统还应为可分配存储空间设置相应的数据结构，即设置一个磁盘分配表(Disk Allocation Table)，用于记住可供分配的存储空间情况。
此外，还应提供对盘块进行分配和回收的手段。不论哪种分配和回收方式，存储空间的基本分配单位都是磁盘块而非字节。
下面介绍几种常用的文件存储空间的管理方法。
1 空闲表法和空闲链表法
1.1 空闲表法
系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，表项中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表，如下图所示。
空闲表用在文件的连续分配方式中
存储空间的分配与回收
空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。
在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。
系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。
应该说明，在内存分配上，虽然较少采用连续分配方式，然而在外存的管理中，由于这种分配方式具有较高的分配速度，可减少访问磁盘的 I/O 频率，故它在诸多分配方式中仍占有一席之地。
1.2 空闲链表法
空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。
构成链的单位不同
空闲盘块链
空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。
当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次挂在空闲盘块链的末尾。
这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次，分配和回收的效率较低。又因为它是以盘块为单位，相应的空闲盘块链会很长。
分配和回收多个盘块时效率低
空闲盘区链
空闲盘区链将磁盘上的所有空闲盘区(每个盘区可包含若个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。
分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。
空闲盘区链的优点和缺点刚好与空闲盘块链的优缺点相反，即分配与回收的过程比较复杂，但分配和会收的效率可能较高，每次为文件分配多个连续的块，且空闲盘区链较短。
2 位示图法
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为 “0” 时，表示对应的盘块空闲；为 “1” 时，表示已分配。本质就是用一位的两种状态来标志空闲和已分配两种情况。
磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用 m * n 个位数来构成位示图，并使 m * n 等于磁盘的总块数，如下图所示。位示图也可描述为一个二维数组 map [ m,n ]：
盘块的分配
根据位示图进行盘块分配时，可分三步进行：//查找->转换->修改
- 顺序扫描位示图，从中找到值为“0”的二进制位。
- 将所找到的二进制位转换成与之相应的盘块号。
- 修改位示图，令
map [ i,j ] = 1。
盘块的回收
盘块的回收分两步：
- 将回收盘块的盘块号转换成位示图中的行号和列号。
- 修改位示图。令
map [ i,j ] = 0。
位视图的主要优点是从图中很容易找到一个或一组相邻接的空闲盘块。例如，我们需要找到 6 个相邻接的空闲盘块，这只需在位示图中找出 6 个其值连续为 “0” 的位即可。
此外，由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。
位视图占用空间下，查找速度快
因此，位示图常用于微型机和小型机中，如 CP/M、Apple-DOS 等 OS 中。
3 成组链接法
参考资料：
空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。在 UNIX 系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。
3.1 空闲盘块的组织
- 空闲盘块号栈
用来存放当前可用的一组空闲盘块的盘块号(最多含 100 个号)，以及栈中尚有的空闲盘块(号)数 N。顺便指出，N 还兼作栈顶指针用。例如，当 N = 100 时，它指向 S.free(99)。
使用栈来保存盘块号，每一个栈保存 100 个盘块
由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。下图示出了空闲盘块号栈的结构。其中，S.free(0) 是栈底，栈满时的栈顶为 S.free(99)。
这是一个单链表 + 栈的结构，不是树 + 栈 !
- 文件区
文件区中的所有空闲盘块被分成若干个组，比如，将每 100 个盘块作为一组。假定盘上共有 10000 个盘块，每块大小为 1KB，其中第 201 ~ 7999 号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为 7901 ~ 7999；次末组为 7801 ~ 7900，倒数第二组的盘块号为 301 ~ 400；第一组为 201 ~ 300，如上图所示。
- 盘块链
将每一组含有的盘块总数 N 和该组所有的盘块号记入其前一组的第一个盘块的 S.free(0) ~ S.free(99) 中。这样，由各组的第一个盘块可链成一条链。
- 空闲盘块号
将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。
- 结尾标志
最末一组只有 99 个盘块，其盘块号分别记入其前一组的 S.free(1) ~ S.free(99) 中而在 S.free(0) 中则存放 “0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为 99，不应是 100，因为这是指可供使用的空闲盘块。其编号应为（1 ~ 99），0 号中放空闲盘块链的结尾标志。)
3.2 空闲盘块的分配与回收
当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。
该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。
若该盘块号已是栈底，即 S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减 1 并返回。
对
S.free(0)需要做特殊处理，因为这个盘块记有下一组可用的盘块号
在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加 1 操作。当栈中空闲盘块号数目已达 100 时表示栈已满，便将现有栈中的 100 个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。