- 文件管理要解决的重要问题之一：如何为新创建的文件分配存储空间。
- 存储空间的基本分配单位是磁盘块。
- 系统应为分配存储空间而设置相应的数据结构；提供对存储空间进行分配和回收的手段。
- 跟踪磁盘上的空闲块数目和块号，形成空闲块登记表 空闲块登记表是盘块分配和回收的依据。
- 空闲块登记表有四种实现方案：空闲表，空闲链表，位示图法，成组链接法
一、空闲表
1.属于连续分配方式，为每个文件分配一块连续的存储空间，适合于可变大小分区的连续分配方式。
2.系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。
3.空闲表的存储空间分配与回收
- 分配存储空间的步骤： 首先顺序查找空闲分区表中的各个表项，直至找到第一个大小适合的空闲分区。 然后，将该分区分配给文件，同时修改空闲分区表，删除相应表项。
- 删除文件释放出空间时，系统回收其存储空间，合并相邻空闲分区。
二、空闲链表
1.将所有空闲盘区拉成一条空闲链，适合于非连续存储文件。
2.根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链，空闲盘区链。
3.空闲盘块链
- 将磁盘上的所有空闲空间，以盘块为单位拉成一条链。
- 当因创建文件而请求分配存储空间时：系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。
- 当用户因删除文件而释放存储空间时： 系统将回收的盘块依次插入空闲盘块链的末尾。(并不排序)
4.空闲盘区链
- 将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。
- 在每个盘区上含有：用于指示下一个空闲盘区的指针，能指明本盘区大小(盘块数)的信息。
- 分配盘区的方法通常采用首次适应算法。
- 在回收盘区时，要将回收区与相邻接的空闲盘区相合并。
- 为了提高对空闲盘区的检索速度，在内存中为空闲盘区建立一张链表（显式链接）。 每个分区结点内容：起始盘块号、盘块数、指向下一个空闲盘区的指针。
三、位示图
1.利用二进制位0、1表示存储空间中存储块的使用状态：空闲分区->0，已分配分区->1
2.磁盘上的所有盘块都有一个二进制位，由所有盘块所对应的位构成一个集合，称为位示图。位示图很小，可以保存在内存中。
3.盘块的分配
- 顺序扫描位示图，从中找出一个值为“0”的二进制位（空闲位）
- 将所找到的空闲位号转换成与之相应的空闲块号： b=n*(i-1)+j
- b为对应的空闲块的块号，n为位示图中每行的位数，i、j分别为空闲位在位示图的行号、列号
- 修改位示图：令map[i,j]＝1
4.盘块的回收
- 将回收盘块的盘块号转换成位示图中的行号和列号
- i=(b-1)DIV n + 1，j=(b-1) MOD n + 1
- 修改位示图：令 map [i,j]＝0
四、成组链接
1.空闲盘块的组织
- 将磁盘所有空闲盘块分组 （比如100个盘块一组）
- 设置空闲盘块号栈，存放：当前可用的一组空闲盘块的盘块号，栈中尚有的空闲盘块总数
- 后一组的所有盘块号以及盘块总数登记在前一组的第一个盘
- 最后一组少登记一个盘块号，多登记一个空闲盘块链的结束标志
2.空闲盘块的分配
- 首先检查空闲盘块号栈是否上锁，如未上锁，从栈顶取出一空闲盘块号，分配与之对应的盘块给用户，将栈顶指针下移一格（出栈）
- 若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号：
- 在该盘块号所对应的盘块（即S.free(0)所指的盘块）中记有下一组可用的盘块号
- 调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去
- 分配一相应的缓冲区作为该盘块的缓冲区
- 最后，把栈中的空闲盘块数减1并返回
3.空闲盘块的回收
- 将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作
- 当栈中空闲盘块号数目已达100时，表示栈已满
- 将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底
