文件存储管理计算机操作系统

文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间，文件被存储在磁盘上，因此磁盘的空间管理很重要。磁盘的空间管理类似于内存的空间管理，即同样可采取连续分配方式或离散分配方式。最早的磁盘分配方法是连续分配，将文件连续顺序地存放在磁盘空间。连续分配具有顺序访问时磁头移动距离小、文件查找速度快、管理简单等优点。但是连续分配不仅要求文件长度固定，需要预先知道文件长度，而且还不能适应文件的自动增长。最终，连续分配会造成磁盘空间存在大量的“碎片”，造成磁盘空间浪费。非连续分配方式把文件分割成固定大小的页面，同样也将磁盘空间划分为磁盘块。磁盘块的分配方式可适应文件的动态增长和收缩，磁盘空间的管理效率高，是目前采用的主要分配方式。

为了实现存储空间的分配，系统首先必须能记住存储空间的使用情况。为此，系统应为分配存储空间而设置相应的数据结构；其次，系统应提供对存储空间进行分配和回收的手段。下面介绍几种常用的文件存储空间的管理方法。

7.5.1 空闲表

空闲表法主要适合连续文件。将一个文件连续分配到磁盘存储空间中。系统通过一个空闲表管理磁盘的所有空闲区。空闲表中包括表项序号、第一个空闲盘块号、空闲区的空闲盘块数等信息，见表7-1。

表7-1 空闲表

根据磁盘空闲表为文件分配空闲区的方法与内存的空闲区分配方法相似，也可以采用首次适应算法、最佳适应算法等。当需要为一个文件分配磁盘空闲区时，系统首先找到空闲盘块数适合文件大小的磁盘空闲区，将该磁盘空闲区分配给用户进程，并删除该空闲区在空闲表中的记录。

当文件删除，需要回收磁盘空间时，首先需要考虑该回收区是否与空闲表中的某个空闲区存在相邻关系，以决定是否需要合并空闲区。如果需要合并，则修改相邻空闲区在空闲表中的信息；如果不需要合并，则将回收的空闲区信息作为一条记录添加到空闲表中。

磁盘的连续分配具有寻道时间短、访问速度快、磁盘I／O频率较低的优点，在磁盘分配方法中一直占有一定的地位，可用于虚拟存储器管理中的外存对换空间的分配。缺点是空闲表需要占用太大的存储空间。

7.5.2 空闲链表

空闲链表分配方法属于非连续分配方式。该分配方法需要在磁盘的每个空闲盘块中设置一个指向下一个空闲块的指针，指针将所有的空闲块链接在一起。系统中保存有指向第一个空闲块的指针。

根据空闲链中构成的元素是空闲盘块还是空闲盘区，空闲链有两种形式：空闲盘块链和空闲盘区链。

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

（2）空闲盘区链。这是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小（盘块数）的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。

空闲链表法的优点是适合文件动态增长和收缩，缺点是效率较低。回收一个磁盘块时，需要查找空闲链以决定回收的空闲块在空闲链中的位置，访问磁盘的次数多。DOS操作系统采用的就是该种分配方法。

7.5.3 位示图

位示图是利用若干个字节构成一个表，表中的每一字位表示一个磁盘块的使用情况，字位的次序与磁盘物理块的相对次序一致。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。用（m×n）的个位数来构成位示图，并使（m×n）等于磁盘的总块数，如图7-14所示。

图7-14 位示图

根据位示图进行盘块分配时，有如下几步：(www.xing528.com)

（1）首先扫描位示图，找到文件所需要的一个或一组值为0的空闲块。

（2）将所找的空闲块转换为盘块号。如果找到的空闲块为第i行第j列，则盘块号q为

式中，n表示位示图每行的位数，在图7-14中，n为16。

（3）将位示图中相应位置的状态改为已经分配，即将“0”变为“1”。

例如，如果需要从磁盘中分配一个盘块，查位示图，得到第1行第2列为0，即为空闲，位示图中有16列。则对应位示图的磁盘块号q为

分配的磁盘块号为2。当2号磁盘块分配后，立即修改位示图中第1行第2列的值为1。

磁盘块回收步骤如下：

（1）将回收的盘块号转换为位示图中的行和列号：

i=（q-1）div n+1

j=（q-1）mod n+1

其中，div表示求模后得到的商；mod表示求模后的余数。

（2）修改位示图中相应的字位，从“1”改为“0”，表示已经回收为空闲。

例如：如果回收的盘块号为18，则

i=（q-1）div n+1=（18-1）div 16+1=2

j=（q-1）mod n+1=（18-1）mod 16+1=2

得到位示图中的第2行第2列，将其值由1改为0，表示该盘块已经回收，为空闲。

位示图法的主要优点是容易得到一个或一组相邻的空闲磁盘块，位示图占用的空间少，可以保存在内存中，减少了访问磁盘的次数。目前，位示图主要用于微机或小型机的磁盘分配上，如Apple-DOS操作系统和CP／M操作系统都用了位示图法。