文件存储空间管理（空闲表法，空闲链表法，位示图法，成组链表法）

1.存储空间的划分与初始化

1.文件卷（逻辑卷)的概念

存储空间的划分:将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘).

2.目录区与文件区

存储空间的初始化：将各个文件卷划分为目录区、文件区。

• 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
• 文件区用于存放文件数据。

有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷。

2.几种管理方法

1.空闲表法

空闲表中记录每个连续空闲区的起始盘块号、盘块数。
适用于连续分配方式。

1.如何分配磁盘块:

与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。
同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

2.如何回收磁盘块:

与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：
①回收区的前后都没有相邻空闲区;
②回收区的前后都是空闲区;
③回收区前面是空闲区;
④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。

2.空闲链表法

1.空闲盘块链

以盘块为单位组成一条空闲链。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。

• 操作系统保存着链头、链尾指针。
• 如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
• 如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

2.空闲盘区链

以盘区为单位组成一条空闲链。
离散分配、连续分配都适用。为个文件分配多个盘块时效率更高。

1.如何分配:
若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，
从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。
若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

2.如何回收:
若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。
若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

3.位示图法

连续分配，离散分配都适用。

1.位示图:

• 每个二进制位对应一个盘块。
• 在本例中，“0”代表盘块空闲，“1”代表盘块已分配。
• 位示图一般用连续的“字”来表示,例题中一个字的字长是16位，字中的每一位对应一个盘块。
• 可以用（字号，位号)对应一个盘块号。也可以描述位（行号，列号）

2.相关计算

1. (字号,位号)=(i,j)的二进制位对应的盘块号$b=n\ast i+j$
2. b号盘块对应的$字号i=b/n，位号j=b\%n$

注意：字号、位号、盘块号到底是从0开始还是从1开始。

3.如何分配

若文件需要k个块，
①顺序扫描位示图，找到k个相邻或不相邻的“0”;
②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;
③将相应位设置为“1”。

4.如何回收:

①根据回收的盘块号计算出对应的字号、位号;
②将相应二进制位设为“0”

4.成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。
UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。
并且要保证内存与外存中的“超级块”数据一致。

1.如何分配

1.如果需求的空闲块为1，小于第一分组的块数
①检查第一个分组的块数是否足够。1<100，因此是足够的。
②分配第一个分组中的1个空闲块，并修改相应数据。

2.如果需求的空闲块为100，等于第一分组的块数
①检查第一个分组的块数是否足够。100=100，是足够的。
②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中。

2.如何回收

1.假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块。
2.假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。
需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。