操作系统理论 第八章（磁盘存储器的管理）—第二节（文件存储空间的管理）

写在前面：

1. 本系列笔记主要以《计算机操作系统（汤小丹…）》为参考，大部分内容出于此书，笔者的工作主要是挑其重点展示，另外配合下方视频链接的教程展开思路，在笔记中一些比较难懂的地方加以自己的一点点理解（重点基本都会有标注，没有任何标注的难懂文字应该是笔者因为强迫症而加进来的，可选择性地忽略）。
2. 视频链接：操作系统（汤小丹等第四版）_哔哩哔哩_bilibili

一、空闲表法和空闲链表法

1、空闲表法

（1）空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表。

（2）与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。需要说明的是，虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地。

2、空闲链表法

（1）空闲盘块链：

        将磁盘上的所有空闲空间以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户；当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次。

（2）空闲盘区链：

        将磁盘上的所有空闲盘区拉成一条链，在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小的信息。分配盘区的方法与内存动态分区分配类似，通常采用首次适应算法；在回收盘区时，同样也要将回收区与相邻的空闲盘区相合并。在采用首次适应算法时，为提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。

二、位示图法

1、位示图

        位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，当其值为“0”时表示对应的盘块空闲，为“1”时表示已分配（有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志）。

        磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用m×n个位数来构成位示图，并使m×n等于磁盘的总块数。位示图也可描述为一个二维数组map[m, n]。

        从位示图中很容易找到一个或一组相邻接的空闲盘块。此外，由于位示图很小，占用空间少，因而可将它保存在内存中，从而在每次进行盘区分配时，无需首先把磁盘分配表读入内存，从而省掉许多磁盘的启动操作。位示图常用于微型机和小型机中，如Linux。

2、盘块的分配

（1）顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位（“0”表示空闲时）。

（2）将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号b=n(i-1)+j，式中n代表每行的位数。

（3）修改位示图，令map[i, j]=1。

3、盘块的回收

（1）将回收盘块的盘块号转换成位示图中的行号和列号，其中转换公式如下。

（2）修改位示图，令map[i, j]=0。