1、空闲表法和空闲链表法

1.1、空闲表法

1.1.1、空闲表

　　系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等。空闲盘块表如下：

1.1.2、存储空间的分配与回收

　　空闲盘区的分配与内存的动态分配类似，采用首次适应算法、循环首次适应算法等。

　　在系统为某新创建的文件分配空闲盘块时，顺序的查找空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲表。

　　系统对用户释放的存储空间做回收时，采取类似于内存回收的方法。

1.2、空闲链表法

　　空闲链表法：将所有空闲盘区拉成一条空闲链，根据构成的链所用基本元素的不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链。

　　空闲盘块链：将磁盘上所有空闲空间，以盘块为单位拉成一条链。

　　空闲盘区链：将磁盘上所有的空闲盘区(每个盘区包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应能有指明本盘区大小信息(盘块数)。

2、位示图法

2.1、位示图

　　位示图：利用二进制的以为来表示磁盘中一个盘块的使用情况，当值为0时，表示对应盘块空闲；为1时，表示已分配。

　　所有盘块所对应的位构成一个集合，称为位示图。

　　位示图可描述为一个二维数组。

2.2、盘块的分配

　　1.顺序扫描位示图

　　2、将所找到的一个或一组二进制位转换成与之相应的盘块号。

　　3、修改位示图。

2.3、盘块的回收

　　1、将回收盘块的盘块号转换成位示图的行号和列号；

　　2、修改位示图。

2.4、优点

　　容易找到空闲盘块，占用空间少，可保存在内存中，每次进行盘区分配时，无需把盘区分配表读入内存，节省很多磁盘启动操作。

3、成组链接法

　　空闲表与空闲链表法不适用大型文件系统，会使表太长。

　　成组链表法适用于大型文件系统。

3.1、空闲盘块的组织

　　空闲盘块号栈：存放当前可用的一组空闲盘块的盘块号，以及栈中尚有的空闲盘块号数N。

　　栈是临界资源，每次仅允许一个进程访问，系统为栈设置了锁。

　　文件区中的所有空闲盘块被分成若干个组；

　　每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的中S.free(0) ~ S.free(99)。如此，各组的第一个盘块可链成一条链。

　　将第一组含有的盘块总数N和所有的盘块号记入空闲盘块栈中，作为当前可供分配的空闲盘块号。

3.2、空闲盘块的分配与回收

　　分配：先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已栈底，即S.free(0)，表示这是当前栈中最后一个可分配的盘块号。由于该盘块号所对应的盘块中记有下一组可用的盘块号，因此需要调用个磁盘读过程，将占地盘块号对应的盘块内存读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。然后在分配一相应的缓冲区(作为盘块的缓冲区)，最后把栈中的空闲盘块数减1并返回。

　　回收：将回收盘块的盘块号记录空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当占中盘块数目达100，标识栈已满，将现有栈中的100个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。