第四章 文件管理 五、文件存储空间管理

目录

一、逻辑结构和物理结构的比较

二、空闲表法

1、磁盘中的空闲块表

2、例子

3、如何回收空闲区间

①回收区的前后都没有相邻空闲区;

②回收区的前后都是空闲区;

③回收区前面是空闲区;

④回收区后面是空闲区;

三、空闲链表法

1、分类

2、空闲盘块链

（1）定义：

（2）如何分配:

（3）如何回收:

（4）优点：

2、空闲盘区链

（1）定义：

（2）如何分配:

（3）如何回收:

（4）优点:

四、位示图法

1、使用矩阵来表示

（1）如何分配：

（2）如何回收：

五、成组链接法

1、定义：

2、超级块：

（1）定义：

3、如何分配：

4、如何回收：

六、总结

---

一、逻辑结构和物理结构的比较

二、空闲表法

1、磁盘中的空闲块表

2、例子

（1）假设要创建一个占三个磁盘块的文件。

（2）找到起始块号为10的空闲区间有3个空闲块。

（3）存入，并更改空闲块表。

3、如何回收空闲区间

①回收区的前后都没有相邻空闲区;

增加一个空闲区

②回收区的前后都是空闲区;

减少一个空闲区

③回收区前面是空闲区;

不变

④回收区后面是空闲区;

不变

三、空闲链表法

1、分类

2、空闲盘块链

（1）定义：

操作系统保存着链头、链尾指针。

（2）如何分配:

若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

（3）如何回收:

回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

（4）优点：

适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。

2、空闲盘区链

（1）定义：

操作系统保存着链头、链尾指针。

（2）如何分配:

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

（3）如何回收:

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

（4）优点:

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

四、位示图法

1、使用矩阵来表示

（1）如何分配：

若文件需要k个块，

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

（2）如何回收：

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

五、成组链接法

1、定义：

• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。
• UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
• 文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

2、超级块：

（1）定义：

所谓超级块，其实就是一个索引块，它的头存的是下一个超级块的地址，其他存的是空闲块的地址

3、如何分配：

Eg :需要1个空闲块

• ①检查第一个分组的块数是否足够。1<100，因此是足够的。
• ②分配第一个分组中的1个空闲块，并修改相应数据。

Eg:需要100个空闲块

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

4、如何回收：

Eg :假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。

需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

六、总结