28 文件存储空间管理

2017-06-23 本文已影响42人 saviochen

文件存储空间分配方法与内存分配有许多相同之处，即同样采用连续或离散分配方式。文件存储空间的分配单位是磁盘块而不是字节。

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

空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法，循环首次适应算法等。

系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应该予以合并。

当文件较小时，采用连续分配方式，当文件较大时，可采用离散分配方式。

空闲链表法是将所有空闲盘区拉成一条空闲链。把链表分成两种形式，空闲盘块链和空闲盘区链。

这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。

当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。

当删除文件而释放空间时，系统将回收的盘块依次插入空闲盘块链的末尾，其优点是用于分配和回收一个盘块的过程简单，但在为文件分配盘块时，可能要重复操作多次。

这是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链，在每个盘区上除了含有只是下一个空闲盘区的指针外，还应有能指明本盘区大小（盘块数）的信息。

盘区分配与内存的动态分配类似，可采用首次适应算法，在回收盘区时，同样也要将回收区和相邻接的空闲盘区相合并，在采用首次适应算法时，可以采用显式链接法提高检索速度，在内存中为空闲盘区建立一张链表。

利用二进制的一位表示磁盘中的一个盘块的使用情况，当其值为0时，表示对应的盘块空闲，为1时，表示已经分配，磁盘上的所有盘块都有一个二进制位与之对应。由所有盘块所对应的位构成一个集合，称为位示图，通常可用m×n个位数来构成位示图，并使m×n等于磁盘的总块数。

对于盘块的分配分为如下三步：

对于盘块的回收分为如下两步：

空闲表法和空闲链表法都不适用于大型系统，因为这会使空闲表或空闲链表很长，在UNIX采用的成组链接法，结合上述两种方法。

1. 空线盘块的组织，空闲盘块栈用来存放当前可用的一组空闲盘块的盘块号（最多含100个号），以及栈中尚有的空闲盘块号数N，顺便指出，N兼做栈顶指针使用，栈是临界资源，系统设置一把锁供进程互斥访问。其中，S.free(0)是栈底，栈满时栈顶为S.free(99)。
1. 文件区中的所有空闲盘块被分成若干个组，如每100个盘块作为一组。
1. 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块S.free(0)~S.free(99)中，这样，由各组的第一个盘块可链接成一条链。
1. 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。
1. 最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)~S.free(99)中，而在S.free(0)中则存放0，作为空闲盘块链的结束。

当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成：

首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。
若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。
然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。

在系统回收空闲盘块时，须调用盘块回收过程进行回收：