空闲表法
空闲表法属于连续分配方式。系统为外存上所有空闲区建立一张空闲表,每个空闲区对应一个空闲表项。
优点:分配速度快,可减少 I/O 频率。对于较小的文件(1~5 个盘块),可以采用连续分配方式为文件分配几个相邻的盘块
盘块的分配
空闲盘区的分配和内存的动态分配相似,也是采用 首次适应算法、最佳适应算法等。
盘块的回收
采用类似内存回收的方法,即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接,对相邻接者要合并。
空闲链表法
空闲盘块链
将磁盘上所有的空闲空间拉成一条链,每个盘块都有指向下一个空闲盘块的指针。
优点:分配与回收的过程简单
缺点:分配与回收的效率很低,且空闲盘区链长
盘块的分配
分配时从链头取出适当数目的空闲盘块分配给用户。
盘块的回收
回收时将回收的盘块一次插入空闲盘块链的末尾。
空闲盘区链
将磁盘上所有的空闲盘区拉成一条链,每个盘区都有指向下一个空闲盘区的指针和本盘区的盘块数。
优点:分配与回收的效率很高,且空闲盘区链短
缺点:分配与回收的过程复杂
盘块的分配
空闲盘区的分配和内存的动态分配相似,通常采用 首次适应算法。
盘块的回收
采用类似内存回收的方法,即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接,对相邻接者要合并。
位示图法
利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有盘块都由一个二进制位与之对应。当其值为 0 时,表示对应盘块空闲,值为 1 时候,表示已分配。
优点:
- 很容易找到一个或一组相邻接的空闲盘块
- 位示图很小,占用空间小,可以保存在内存中,节省许多磁盘启动的开销
缺点:位示图大小会随着磁盘容量的增加而增大,因此常用于小型计算机
盘块的分配
- 顺序扫描位示图,从中找出一个或一组值为 0 的二进制位
- 通过行号 i 和列号 j,转换为对应的盘块号 (n 为每行位数)
- 修改位示图,令 map[i, j]=1
盘块的回收
- 将盘块号转换为位示图中的行号和列号。 ,
- 修改位示图,令 map[i, j]=0
成组链接法
第一组为超级块,保存在空闲盘块号栈中,每一组有一个 N 记录该组中的空闲块数量,每一组的第一项也就是 s.free[0],链接到下一组的第一块,后续项直接指向一个空闲盘块。每一组的第一项都是一个栈节点。
盘块的分配
从超级块开始分配,分配一个 N 减 1,N=1 时,说明该组已经没有空闲盘块,此时将 s.free[0]指向的栈节点内容复制到超级块中,然后这个栈节点就没用了,将这个节点分配出去。
盘块的回收
每回收一个,都记录到超级块中,并 N 加 1,当超级块满后,就把超级块的内容复制到新回收的盘块中,超级块的第一项指向这个新盘块,于是超级块的 N=1,又可以继续回收了。
文件分配表 FAT
FAT虽然是用来记录文件中各个块的先后链接关系,但同时也标记了空闲的盘区块,可以用来进行空闲盘块管理。