空闲表法

空闲表法属于连续分配方式。系统为外存上所有空闲区建立一张空闲表,每个空闲区对应一个空闲表项。

优点:分配速度快,可减少 I/O 频率。对于较小的文件(1~5 个盘块),可以采用连续分配方式为文件分配几个相邻的盘块

盘块的分配

空闲盘区的分配和内存的动态分配相似,也是采用 首次适应算法最佳适应算法等。

盘块的回收

采用类似内存回收的方法,即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接,对相邻接者要合并。

空闲链表法

空闲盘块链

将磁盘上所有的空闲空间拉成一条链,每个盘块都有指向下一个空闲盘块的指针。

优点:分配与回收的过程简单

缺点:分配与回收的效率很低,且空闲盘区链长

盘块的分配

分配时从链头取出适当数目的空闲盘块分配给用户。

盘块的回收

回收时将回收的盘块一次插入空闲盘块链的末尾。

空闲盘区链

将磁盘上所有的空闲盘区拉成一条链,每个盘区都有指向下一个空闲盘区的指针和本盘区的盘块数。

优点:分配与回收的效率很高,且空闲盘区链短

缺点:分配与回收的过程复杂

盘块的分配

空闲盘区的分配和内存的动态分配相似,通常采用 首次适应算法

盘块的回收

采用类似内存回收的方法,即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接,对相邻接者要合并。

位示图法

利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有盘块都由一个二进制位与之对应。当其值为 0 时,表示对应盘块空闲,值为 1 时候,表示已分配。

优点:

  1. 很容易找到一个或一组相邻接的空闲盘块
  2. 位示图很小,占用空间小,可以保存在内存中,节省许多磁盘启动的开销

缺点:位示图大小会随着磁盘容量的增加而增大,因此常用于小型计算机

盘块的分配

  1. 顺序扫描位示图,从中找出一个或一组值为 0 的二进制位
  2. 通过行号 i 和列号 j,转换为对应的盘块号 (n 为每行位数)
  3. 修改位示图,令 map[i, j]=1

盘块的回收

  1. 将盘块号转换为位示图中的行号和列号。
  2. 修改位示图,令 map[i, j]=0

成组链接法

解析

第一组为超级块,保存在空闲盘块号栈中,每一组有一个 N 记录该组中的空闲块数量,每一组的第一项也就是 s.free[0],链接到下一组的第一块,后续项直接指向一个空闲盘块。每一组的第一项都是一个栈节点

盘块的分配

从超级块开始分配,分配一个 N 减 1,N=1 时,说明该组已经没有空闲盘块,此时将 s.free[0]指向的栈节点内容复制到超级块中,然后这个栈节点就没用了,将这个节点分配出去。

盘块的回收

每回收一个,都记录到超级块中,并 N 加 1,当超级块满后,就把超级块的内容复制到新回收的盘块中,超级块的第一项指向这个新盘块,于是超级块的 N=1,又可以继续回收了。

文件分配表 FAT

FAT虽然是用来记录文件中各个块的先后链接关系,但同时也标记了空闲的盘区块,可以用来进行空闲盘块管理。