成组链接法

空闲表法、空闲链表法不适用于大型文件系统,因为空闲表或空闲链表可能过大。UX 系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”,当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
image.png

分配

情况 1

image.png
即把第 201 物理块分配出去,然后修改超级块的空闲盘块数为 99.

情况 2

如果要分配 100 个物理块,那么就先将 300 块的数据复制到超级块中,然后将 300-201 块全部分配出去,之后让指针指向 400-301 即可。如下图:
image.png

回收

情况 1

image.png
超级块中原本缺 201 块。要回收时,由于超级块对应的第一组并没有满,所以直接将该块插入第一组中,同时修改超级块的对应内容。

情况 2

image.png
超级块中原本存储着指向 301-400 分组的链接,现在要插入新的一个块 300,由于其他分组都已满,所以先将超级块的内容复制到新回收的 300 块中,然后修改超级块的内容为一个空闲块,一个链接指向 300 块。