第四章 文件管理

8.文件存储空间管理

空闲表法：
  空闲盘块表和在内存管理的动态分区分配中学习过的空闲分区表是类似的，空闲盘块表记录了每一个空闲区间的起始位置和这个空闲区间的长度这两个信息。像第一个空闲区间是0，1这两个空闲块，所以这个空闲区间对应的是第一个表项，第一个空闲盘块号是0，空闲盘块数是2。空闲区间10-14在空闲盘块表中对应表项的第一个空闲盘块号是10，空闲盘块数是5。 空闲表法适用于文件的物理结构是连续分配方式。

​   分配磁盘块：采用空闲表法为文件分配的是连续的存储空间。举例：假设此时新创建的文件请求3个磁盘块，如果采用首次适应算法，系统会依次检查这个空闲表中的各个表项，找到第一个能够满足3个块的空闲区间。分配之后需要修改空闲盘块表（修改起始盘块号和空闲盘块数）。最佳适应与最坏适应和在内存管理中学习过的思想是一样的，最佳适应是找到一个能满足要求且最小的空闲区间进行分配；最坏适应就是找到一个能满足需求并且最大的连续空闲区间进行分配。

​   回收磁盘块：与内存管理中的动态分区分配类似，有四种情况①回收区的前后都没有相邻空闲区，这种情况下需要在空闲盘块表中新增一个表项。②回收区的前后都是空闲区，则需要把前后的空闲区和新回收的区域合并为同一个空闲区，此时空闲盘块表中表项数-1。③回收区的前面是空闲区。④回收区的后面是空闲区，最后这两种情况并不会导致空闲盘块表的表项数改变。

​   空闲盘区链比起空闲盘块链来说为一个文件分配多个盘块时的效率更高。因为空闲盘块链只能从链中一个一个的把这些磁盘块摘下来，而空闲盘区链可以一次摘出一大片连续的空闲区间，所以为一个文件分配多个盘块时的效率更高。

​    位示图法：位示图一般会存储为连续的“字”，比如说在这个例子中一个字的字长是16位，每个字由16个二进制位组成，因此可以用（字号，位号）这样的二元组来定位到其中的某一个二进制位。所以考试中经常考察的就是如何从（字号，位号）推算出它所对应的盘块号，或者怎么从盘块号逆推出这个盘块号所对应的（字号，位号）。位示图法连续分配和离散分配都适用。在连续分配时，在扫描位示图的时候可以尝试找到连续的K个空闲块（连续的K个“0”，因为在位示图中“0”表示空闲）；在离散分配时，在扫描位示图的时候可以不用非得找到连续的K个空闲块。

成组链接法：
  文件卷的目录区中会设置一个专门的磁盘块作为“超级块”，当系统启动时要把“超级块”读入内存，并且在整个过程中需要保持内存和外存中的“超级块”的数据一致。
  在超级块中记录了下一组空闲盘块的数量，比如说下一组总共有100个空闲盘块，另外它还需要记录这100个空闲盘块的盘块号依次是多少，通过这些盘块号就可以依次找到下一个分组的各个盘块了，第1个空闲分组共有100个，分别是201～300号磁盘块，需要注意300号磁盘块它作为这个分组的第一个磁盘块在这个块当中还需要记录下一组空闲盘块的信息，同样的这个地方的100表示的是下一个空闲盘块的分组总共有100个空闲盘块，下面的的数字代表了下一个分组的各个盘块的盘块号，所以通过这些盘块号又可以找到再下一分组的盘块分别是哪些，同样与刚才类似，在这个分组当中400号盘块是这个分组当中的第一个盘块，所以400号盘块也会再记录再下一个分组的盘块数和各个盘块的盘块号，用这种方式就可以把整个系统中所有的空闲盘块给一一连起来。在倒数第二个分组的第一个盘块的起始位置这里可以设置为一个特殊的值-1，用来表示再下一个分组已经是最后一个分组了（所以如果找到这个值为-1的结点的话就证明在之后已经没有更多的分组了。另外需要注意其实每一个分组的盘块号并不需要连续，这个地方把这些数字设置为连续的原因是为了更方便的看出每一个分组到底有多少个盘块。另外需要在成组链接法中每一个分组的盘块数量有一个上限，这个例子中每个分组最多只有100个盘块，另外需要注意最后一个分组的盘块数是要比前面的分组的盘块数少一个（原因是在倒数第二个分组的第一个盘块的起始位置这里可以设置为一个特殊的值-1，用来表示再下一个分组已经是最后一个分组了，这里占用了）。

​   成组链接法如何分配：假设此时某一个文件需要分配一个空闲块，首先需要检查第一个分组中的磁盘块到底够不够这个文件的需求，由于此时超级块已经是读入内存的了，所以在进行这个检查的时候并不需要读磁盘操作，只需要找到内存当中超级块的数据并且检查一下下一组的空闲盘块数是否大于此时要求得到的空闲盘块数，由于1<100，所以说明这个第一个分组中的空闲盘块是足够分配的，接下来就会把这些分组中的最后这个盘块（201号盘块）分配给这个文件，这个盘块分配出去之后就需要把超级块中记录的201号盘块号的数据删除并且要把超级块中用于表示下一个分组的空闲盘块数-1；如此便完成了分配一个空闲块的事情。 如果此时需要分配100个空闲块，第一件事同样是检查第一个分组到底够不够分配，由于此时第一个分组的数量共有100个空闲盘块，因此第一个分组是足够分配的，因此接下来会把第一个分组的100个磁盘块全部分配出去，不过这里需要注意的是300号磁盘块存储了再下一个分组的磁盘块的信息，因此如果把300号磁盘块直接分配给那个文件不做任何处理的话那么和下一组的链接信息就断掉了，因此在我们把300号磁盘块正式分配给文件之前我们需要把300号磁盘块中的数据将其复制到超级块中，这样就可以保证虽然这个分组已经全部分配给这个文件了，但是下一个分组的链接信息依然是保存在超级块当中的。如果文件要求的是更多数量的空闲块的话，那么我们依然可以用同样的方法把这些分组一个一个的全部分配出去，不过需要注意的就是每一个分组正式分配出去之前需要把这个分组指向下一个分组的链接信息都先复制到超级块中。所以超级块其实就是充当了链头的作用，在这个链头当中永远要保持指向下一个分组的一系列信息。

​   成组链接法如何回收空闲块：假设每一个分组的磁盘块上限是100块，而第一个分组此时只有99块，假如此时还要再回收一个空闲块的话，由于此时第一个分组还没有满，所以我们可以把这个空闲块插到第一个分组当中，比如回收的是201号块，那么就可以把201号块的链接信息放到超级块中，并且把超级块中的下一组空闲盘块数+1，这是第一种情况如果分组没满的话可以把回收的空闲块插到第一个分组当中。第二种情况：假设现在第一个分组已经满了（第一个分组现在共有100个块），如果此时还要再回收一个空闲块的话应该怎么处理？由于这个分组已经满了，显然这个空闲块不能把它放到这个分组中，所以可以把这个新回收的块作为一个新的分组，不过需要注意的是我们需要把这个超级块中的内容复制到新回收的块当中，这样这个新回收的块作为一个新的分组它就拥有了指向下一个分组的链接指针，而由于超级块是永远指向第一个分组，所以超级块的数据就需要进行修改，让它指向第一个分组也就是新的这个回收块组成的新分组，由于这个新分组当中只有一个空闲块，所以超级块中表示下一个分组空闲块数的位置的值是1。

总结：
  空闲表法可能结合首次适应、最佳适应等策略进行考察，需要回顾在内存管理中学过的这些算法的策略；在空闲表法中注意回收时是否需要合并。
  最常考察的还是位示图法，要能够自己推出盘块号<—>(字号，位号)之间的相互转换公式。需要注意题目的条件，二进制的0/1到底哪个代表空闲，哪个代表不空闲；字号，位号，盘块号到底是从0开始还是从1开始。
  成组链接法是UNIX系统采用的策略，适合大型文件系统。成组链接法的规则比较复杂，并且不太方便用文字进行描述，所以这个知识点很难作为考题进行考察，不过只要理解了刚才分析的过程即使考到了也能够解决。