8.2　文件存储空间的管理

本节概览：先建立「文件存储空间的管理」的框架，再依次展开下列小节。

1. 空闲表法和空闲链表法
2. 位示图法
3. 成组链接法

存储空间的分配与回收：空闲盘区的分配与内存的分区（动态）分配类似，同样采用首次适应算法和最佳适应算法等，二者对存储空间的利用率大体相当，都优于最坏适应算法。

为新创建文件分配空闲盘块时，先顺序检索空闲表各表项，直至找到第一个大小能满足要求的空闲区，将该盘区分配给用户（进程），同时修改空闲表。

结合插图「图8-9 空闲盘块表」理解本节要点。

（2）存储空间的分配与回收空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。

根据位示图进行盘块分配时分三步。

1. 顺序扫描位示图，找出一个或一组其值为「0」的二进制位（以「0」表示空闲时）
2. 修改位示图，令 map[i, j] = 1
3. 将找到的二进制位转换成相应盘块号：b = n(i - 1) + j，其中 n 为每行位数

位示图利用二进制的一位表示磁盘中一个盘块的使用情况：值为「0」表示对应盘块空闲，为「1」表示已分配（有的系统约定相反，本质都是用一位的两种状态区分空闲与已分配）。

磁盘上所有盘块都有一个二进制位与之对应，由所有位构成的集合称为位示图。

盘块的回收分两步。

1. 将回收盘块的盘块号转换成位示图中的行号和列号：i = (b - 1) DIV n + 1，j = (b - 1) MOD n + 1
2. 修改位示图，令 map[i, j] = 0

文件区中所有空闲盘块被分成若干组，例如每 100 个盘块为一组。以 10000 块、每块 1 KB、第 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」作为链结束标志。

成组链接法用于大型文件系统的空闲盘块管理。空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号（最多含 100 个号），以及栈中尚有的空闲盘块数 N；N 还兼作栈顶指针用。

空闲盘块的分配与回收：系统为文件分配盘块时，调用盘块分配过程，先检查空闲盘块号栈是否上锁，未上锁则从栈顶取一空闲盘块号分配给用户，栈顶指针下移一格。若该盘块号已是栈底（最后一个可分配盘块），则需特殊处理。