文件分配方法：

• 连续分配

• 链式分配

• 索引分配

空闲空间管理方法：

• 空闲表法

• 空闲链表法

• 位示图法

• 成组链接法

一、文件分配

1. 连续分配

连续分配是指在创建文件时，给文件分配一组连续的块。

以该方式管理的文件称为连续文件。

优点

• 简单、容易实现。

• 对于顺序文件，能很快检索文件中的数据块，连续读/写多个数据块内容时，性能较好。

缺点

• 它不利于文件尺寸的动态增长。

• 该分配方案可能会导致磁盘碎片，严重降低外存空间的利用率。

2. 链式分配

为文件分配非连续的若干数据块，数据块之间用指针相连，这种分配方式称为链式分配，以该方式管理的文件称为链接文件。

链接方式的类型：

• 隐式链接

• 显式链接

隐式链接

• 在文件目录的每个目录项中都须含有指向链接文件第一个盘块和最后一个盘块的指针。

• 文件目录表中有start块号，每块中有下一块号。

• 特点

  • 只适合于顺序访问，对随机访问效率低，可靠性差。

隐式链接：

显式链接

• 把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中(整个磁盘仅设置一张)。

• 查找在内存中进行。

• 由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。

显式链接：

优点

• 链接分配技术不要求文件存储到彼此相邻的数据块中，消除连续分配引起的碎片，提高了外存空间的利用率。

• 链接分配技术还能适应文件尺寸的动态增长。

缺点

(隐式链接)链接分配技术适合于文件的顺序存取，但对于随机存取却相当低效。

二、空闲空间管理方法

1. 位示图

• 位表，又称为位示图，其中的每一位对应一个磁盘块。位的值为0或1，分别表示磁盘块空闲，或磁盘块已分配

• 利用位表容易找到一个或一组空闲盘块

• 位表适合于以上各种文件分配方法

• 位表很小，可以装入内存

2. 链接空闲区

• 每个空闲分区包含一个指向下一个分区的指针，并记载分区大小

• 无空闲分区表空间开销

• 适合于各种文件分配方法

• 若每次分配一个磁盘块，则可取空闲分区链的第一个盘块进行分配，并调整空闲分区链首指针和分区链大小

• 若采用可变分区法，可用首次适应算法，从链表头开始查找，找到的第一个适合的分区则可分配，然后调整空闲分区链首指针和分区链大小

3. 索引

• 将空闲分区视为文件，按文件存储空间分配法为空闲分区建立索引

• 索引表中为每一个空闲分区建立一个索引项

• 为可变分区建立索引比为磁盘块建立索引效率高

• 适合于各种文件分配法

4. 空闲块列表

• 在这种方法中，每块都指定一个序号，所有空闲块的序号保存在磁盘的一个保留区中。

• 磁盘上用于空闲块列代表的空间小于磁盘空间的1%

• 两种有效技术把该表一小部分保存到内存中：

  • 该表可视为一个下堆栈
  • 该表可视为一个FIFO队列