操作系统对文件存储空间的四种管理方式，主要有空闲盘块表法、空闲块链接法、位示图法和成组链接法。
（一）空闲盘块表法
计算机系统在工作期间频繁地创建和删除文件。为了记载磁盘上哪些盘块当前是空闲的，文件系统需要创建一个空闲盘块表，如图5-18所示。
图5-18 空闲盘块表
可以看出，所有连续的空闲盘块在表中占据一项，其中标出第一个空闲块号和该项中所包含的空闲块个数，以及相应的物理块号。如第1项（序号为1）中，表示空闲块有4个，首块是2，即连续的空闲块依次是2、 3、4和5。
空闲块分配：在建新文件时，要为它分配盘空间。为此，系统检索空闲盘块表，寻找合适的表项。如果对应空闲区的大小恰好是所申请的值，就把该项从表中清除；如果该区大于所需数量，则把分配后剩余的部分记在表项中。
空闲块回收：当用户删除一个文件时，系统回收该文件占用的盘块，且把相应的空闲块信息填回空闲盘块表中。如果释放的盘区和原有空闲区相邻接，则把它们合并成一个大的空闲区，记在一个表项中。
优点：把若干连续的空闲块组合在一个空闲表项中，它们一起被分配或释放，特别适用于存放连续文件。
缺点：若存储空间有大量的小空闲区时，则空闲表变得很大，使检索效率降低。同时，如同内存的动态分区分配一样，随着文件不断地创建和删除，磁盘空间将被分割成许多小块。这些小空闲区无法用来存放文件，从而产生了外存的外部碎片，造成磁盘空间的浪费。虽然理论上可采用紧缩办法，使盘上所有文件紧靠在一起，使所有的外存碎片拼接成一大片连续的磁盘空闲空间，但这样做要花费大量的时间，代价很大。
（二）空闲块链接法
这种方法与链接文件结构有相似之处，只是链上的盘块都是空闲块而已。如图5-19所示，所有的空闲盘块链接在一个队列中，用一个指针（空闲块链头）指向第1个空闲块，而各个空闲块中都含有下一个空闲区的块号，最后一块的指针项记为NULL，表示链尾。
图5-19 空闲块链接
当分配空闲块时，从链头取下一块，然后使空闲链头指向下一块。若需n块，则重复上述动作n次。当删除文件时，只需把新释放的盘块依次链入空闲链头，且使空闲链头指向最后释放的那一块。
优缺点：这种技术易于实现，只需要用一个内存单元保留链头指针。但其工作效率低，因为在链上增加或移走空闲块时需要很多I/O操作。
（三）位示图法
它利用一串二进位值反映磁盘空间的分配情况，也称位向量（Bit Vector）法。每个盘块都对应一个二进制位。如果盘块是空闲的，对应位是1；如果盘块已分出去，则对应位是0（注意，有些系统标志方式与此恰好相反）。例如，设下列盘块是空闲的：2，3，4，5，8，9，10，11，12，13，17，18，25，26，27，…，则位示图向量是：
0011110011111100011000000111…
位示图法（Bit Map）的优点：在寻找第1个空闲块或几个连续的空闲块时相对简单和有效。实际上，很多计算机都提供位操作指令，可以有效地用于查找。为了找到第1个空闲块，系统顺序检查位示图中的每个字，查看其值是否等于0。第1个不是0的位就对应第1个空闲块。块号的计算公式如下：
块号=字长ד0”值字数 首位“1”的偏移
位示图大小由盘块总数确定。如果磁盘容量较小，它占用的空间较少，就可以复制到内存中，使得盘块的分配和释放都可高速进行。当关机或文件信息转储时，位示图信息需完整地在盘上保留下来。当然，为节省位示图所占用的空间，可把盘块成簇构造，即若干连续的盘块（如22=4块）为一簇，每一簇在位示图中占一位。这样，对盘块就按簇进行分配了。
（四）空闲块成组链接法
用空闲块链接法可以节省内存，但实现效率低。一种改进办法是把所有空闲盘块按固定数量分组，例如每50个空闲块为一组，组中的第1块为“组长”块。第1组的50个空闲块块号放在第2组的组长块中，而第2组的其余49块是完全空闲的。第2组的50个块号又放在第3组的组长块中。依此类推，组与组之间形成链接关系。最后一组的块号（可能不足50块）通常放在文件系统超级块中（每个文件系统都有一个超级块，其中保存对整个文件系统进行控制和管理的重要信息。它存放在盘块中。当加载文件系统后，通常把它复制到一个内存缓冲区中）。这样，平常对盘块的分配和释放就在内存超级块中进行，如图5-20所示。UNIX系统中就采用这种方法。
图5-20 空闲块成组链接
空闲块分配：如图5-20所示，在超级块中有一个保存空闲块号的数组和一个表示其中有效元素个数的整数。这种结构就相当于堆栈结构。所以，我们把该数组称为空闲块号栈，相应的整数称作栈标。当为新建文件分配空闲盘块时，总是先把栈标的数值减1，如图5-20中所示情况：40-1=39。以39作为检索空闲块号栈的索引，得到盘块号111，它就是当前分出去的第1个空闲块。如果需要分配20个盘块，则上述操作就重复执行20次。
如果当前栈标的值是1，需要分配2个空闲盘块，那么，栈标值减1后，结果为0，此时系统做特殊处理：以0作为索引下标，得到盘块号150，它是第78组的组长；然后，把150号盘块中的内容——下一组（即第77组）所有空闲盘块的数量（50）和各个盘块的块号——分别放入超级块的栈标和空闲块号栈中，于是空闲块号栈中就记载了第77组盘块的情况；最后把150盘块分配出去。至此，分出去1块。接着再分配一个盘块，此时工作简单多了：50-1=49，以49为索引得到第77组的151号块。
空闲块释放：在图5-20所示的情况下，若要删除一个文件，它占用3个盘块，块号分别是69，75和87。首先释放69号块，其操作过程是：把块号69放在栈标40所对应的元素中，然后栈标值加1，变为41。接着分别释放75号块和87号块。最后，超级块中栈标的值为43，空闲块号栈中新加入的3个盘块出现的次序是69、75、87。
如果栈标的值是50，表示该栈已满，此时还要释放一个盘块89号，则进行特殊处理：先将该栈中的内容（包括栈标值和各空闲块块号）写到需要释放的新盘块（即89号）中；将栈标及栈中盘块号清为0；以栈标值0为索引，将新盘块号89写入相应的栈单元中，然后栈标值加1——栈标值变为1。这样，盘块89号就成为新组的组长块。
图5-20中第1组只有49块，它们的块号存于第二组的组长块3950号中。该块中记录第1组的总块数为50，而首块块号标志为0。这是什么意思？原来这个“0”并不表示物理块号，而是分配警戒位，作为空闲盘块链的结束标志。如果盘块分配用到这个标志，说明磁盘上所有空闲块都用光了，系统要发告警信号，必须进行特殊处理。
优缺点：成组链接法是UNIX系统中采用的空闲盘块管理技术，它兼具空闲盘块表法和空闲块链接法的优点，克服了两种方法中表（或链）太长的缺点。当然，成组链接法在管理上要复杂一些，尤其当盘块分配出现栈空，盘块释放遇到栈满时，要做特殊处理。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。