目录
6.4.1 空闲表
1、存储空间的分配与回收
2、空闲表法的优缺点
6.4.2 空闲链表
1、空闲盘块链
2、空闲盘区链
6.4.3 位示图
1、位示图的表示
2、存储空间的分配
3、存储空间的回收
4、位示图法的优缺点
6.4.4 成组链接
1、空闲盘块的组织
plus 个人理解图示
2、空闲盘块的分配
3、空闲盘块的回收
4、综合举例
文件管理要解决的重要问题之一：如何为新创建的文件分配存储空间。
① 存储空间的基本分配单位是盘块。
② 其分配方法与内存的分配有许多相似之处，即同样可采取连续分配方式或离散分配方式。
③ 系统应为分配存储空间而设置相应的数据结构，并提供对存储空间进行分配和回收的手段。
磁盘空间的管理
跟踪磁盘上的空闲块数目和块号，形成空闲块登记表。空闲块登记表是盘块分配和回收的依据。空闲块登记表有四种实现方案：
6.4.1 空闲表
空闲表法属于连续分配方式，它为每个文件分配一块连续的存储空间。
系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。
1、存储空间的分配与回收
适合于可变大小分区的连续分配方式。
分配步骤：
- 顺序查找空闲分区表中的各个表项，直至找到第一个大小合适的空闲分区；
- 将该空闲分区分配给文件，同时修改空闲分区表，删除相应的表项。
当删除文件并释放出空间时，系统回收其存储空间，合并相邻的空闲分区。
2、空闲表法的优缺点
① 优点：实现简单。对于最佳适应分配算法，可以将各空闲分区按照（长度）从小到大的顺序进行排列，再利用有效的查找算法，能很快找到需要大小的空闲分区。
② 缺点：当存储空间中的空闲分区分布较分散且数量较多时，空闲分区表将会很大。需要很大的内存空间，会降低空闲分区表的检索速度。
6.4.2 空闲链表
用专门的空闲表登记空闲分区信息会浪费一定的存储空间，而且不适合登记分散且数目很多的空闲分区。不利于基于存储块的链接文件和索引文件的存储空间分配。
空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链、空闲盘区链。
1、空闲盘块链
将磁盘上的所有空闲空间，以盘块为单位拉成一条链。
- 当因创建文件而请求存储空间时：系统从链首开始依次摘下空闲盘块分配给用户。
- 当因删除文件而释放存储空间时：系统将回收的盘块依次插入空闲盘块链的末尾。
优点：分配和回收一个盘块的过程非常简单。
2、空闲盘区链
- 将磁盘上的所有空闲盘区拉成一条链，其中每个盘区可包含若干个盘块。
- 每个盘区含有：指示下一个空闲盘区的指针和指明本盘区盘块数的信息。
- 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。
- 在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。
为了提高对空闲盘区的检索速度，可以采用显式链接方法，即在内存中为空闲盘区创建一条链表。链中每个结点内容包括：起始盘块号、盘块数、指向下一个空闲盘区的指针。
缺点
① 一段时间后，空闲分区链表中可能包含太多小分区，使文件分配到的存储空间过于离散。
② 删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长的时间。
③ 若一个文件需要申请连续的存储空间，则需要花费较长的时间查找符合大小的、相邻的空闲分区。
因此，这种空闲空间组织方法适合于非连续存储文件。
6.4.3 位示图
利用二进制位 0、1 表示存储空间中存储块的使用状态：
- 空闲分区：0
- 已分配分区：1
磁盘上的所有盘块都有一个二进制位，由所有盘块所对应的位构成一个集合，称为位示图。
通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘的总块数。位示图也可以被描述为一个二维数组。
1、位示图的表示
2、存储空间的分配
注意：公式并不总是为上述图中公式，需要根据位示图是从 0 开始编号，还是从 1 开始编号来自行选择公式。
3、存储空间的回收
同样注意：公式并不总是为上述图中公式，需要根据位示图是从 0 开始编号，还是从 1 开始编号来自行选择公式。
4、位示图法的优缺点
优点：可以容易地找到一个或一组连续的空闲分区。例如，我们需要找到 8 个相邻接的空闲盘块，这只需在位示图中连续找出 8 个其值为 “0” 的位即可。
缺点：很难一次性将该位示图全部装入内存。即使内存足够大，可以存放全部或绝大部分位示图数据，搜索一个大位示图也会降低文件系统的性能。
6.4.4 成组链接
1、空闲盘块的组织
① 设置空闲盘块号栈：存放空闲盘块的盘块号和栈中空闲盘块的总数；
② 前一组的第一个盘块记录后一组所有的盘块号以及盘块总数；
③ ……依次类推，组与组之间形成链接关系；
④ 最后一组少登记一个盘块号，多登记一个空闲盘块链的结束标志。
组的概念：我们设置每 100 个盘块为 1 组，实际上靠栈的大小来约束，即栈中最多存放 100 个盘块号。当栈满且再来一个新的空闲盘块时，将栈中已有的所有盘块号出栈并写入该空闲盘块中，最后压入该空闲盘块的盘块号，此时栈中只有一个盘块号。
plus 个人理解图示
图 1 为盘块号 300 到来之前：301~400 正好填满栈，栈中有 100 个盘块号。图 2 为盘块号 300 到来之后：301~400 写入盘块号为 300 的盘块中，并且栈中变为只有 1 个盘块号。
内存栈中的盘块号就相当于一个指针，指向外存中相应的盘块。本图中没有画出一般的盘块，只画了暂存上一组盘块号的盘块，即盘块 300 。图中的所有箭头都是指向外存中相应的盘块。特殊地，盘块 300 中暂存了上一组的盘块号，而这些盘块号又指向相应的盘块。
2、空闲盘块的分配
基本操作：首先检查空闲盘块号栈是否上锁，若未上锁，则从栈顶取出一空闲盘块号，分配与之对应的盘块给用户，将栈顶指针下移一格。
特殊情况：栈顶指针指向栈底盘块号即 S.free(0)，它是当前栈中最后一个可分配的盘块号。
- 该盘块号所指向的盘块记录了下一组空闲盘块号
- 调用磁盘读过程将其所指向盘块的内容读入栈中
- 即下一组空闲盘块号成为空闲盘块号栈的新内容
- 最后还需要把原栈底盘块号对应的盘块分配出去
当一个盘块记录有下一组空闲盘块号时，这并不代表它不再能被分配出去，只要在将它分配出去之前把其中记录的内容读入栈中即可。
3、空闲盘块的回收
基本操作：调用盘块回收过程进行回收，将被回收盘块的盘块号记录到空闲盘块号栈的栈顶，并执行空闲盘块数加一的操作。
特殊情况：当栈中空闲盘块号数目达到 100 时，表示栈已满；若再有新的盘块被回收，则将现有栈中的 100 个盘块号记入其中，再将该盘块的盘块号作为栈底。
4、综合举例
（1）该磁盘目前有多少空闲盘块？
（2）若某个文件需要 3 个盘块，请问该如何分配？
（3）删除某一文件并回收其所占的 5 个盘块，盘块号依次为 700、711、703、788、701，请画出回收后的盘块链接情况。
（1）简便方法：直接把各个计数单元中的数值相加即可。
具体思路如下：
- 内存栈中有 2 个盘块号
- 盘块 300 当中有 100 个盘块号
- 盘块 400 当中有 100 个盘块号
- 盘块 500 当中有 99 个盘块号
一共有：2 + 100 + 100 + 99 = 301 个空闲盘块。
（2）基本思路：先分配内存空闲盘块栈中盘块号指向的盘块，若不够，则把栈底盘块号指向的盘块的内容读入，再把该盘块号指向的盘块分配出去。
- 第一块：分配盘块号 299 指向的盘块
- 第二块：分配盘块号 300 指向的盘块（见下图）
- 第三块：分配盘块号 301 指向的盘块
（3）注意：该小题续接（2）小题，不是从题干图示状态开始！
后面的回收就很简单了，我懒得画也画不下了。
