操作系统设计/文件系统/分配
分配背后的主要思想是有效地利用文件空间并快速访问文件。有三种类型的分配
- 连续分配
- 链接分配
- 索引分配
除了在磁盘驱动器上存储实际的文件数据外，文件系统还存储有关文件的元数据：每个文件的文件名，上次编辑时间，它在磁盘上的确切位置以及磁盘的哪些部分是“空闲的”。空闲区域当前未被文件数据或元数据使用，因此可用于存储新文件。（存储这些元数据的区域通常称为“inode”、“块”、“文件分配表”等。）
为了跟踪空闲空间，文件系统维护一个空闲空间列表，该列表跟踪所有空闲的磁盘块。要创建文件，需要为文件预留所需空间，并将相应空间从与每个空间链接的空闲列表中删除。
连续分配方法要求每个文件占用磁盘上的一组连续地址。磁盘地址定义了磁盘上的线性排序。当文件必须存储在磁盘上时，系统会搜索与文件大小要求一致的连续块集，即系统会等待直到找到所需数量的内存块按顺序排列。当有可用空间时，系统将文件存储在磁盘上并在目录中进行条目。
连续分配文件的目录条目包含
- 起始块地址
- 分配块的长度
通过这种排序，在块 b 后访问块 b+1 通常不需要任何磁头移动。文件的连续分配由磁盘地址和第一个块的长度定义。如果文件有 n 个块长，并且从位置 b 开始，那么它将占用块 b、b+1、b+2、…、b+n-1。每个文件的目录条目指示起始块的地址和为该文件分配的区域的长度。
在链接分配中，每个文件都是磁盘块的链接列表。目录包含指向文件第一个（以及可选的最后一个）块的指针。例如，一个从块 4 开始的 5 块文件，可能会在块 7 处继续，然后是块 16、块 10，最后是块 27。每个块包含指向下一个块的指针，最后一个块包含一个 NIL 指针。值 -1 可用于 NIL 以将其与块 0 区分开。
通过链接分配，每个目录条目都包含指向文件第一个磁盘块的指针。该指针初始化为 nil（列表结束指针值）以表示空文件。对文件写入会删除第一个空闲块并写入该块。然后将这个新块链接到文件的末尾。要读取文件，只需从块到块地跟踪指针即可。
链接分配没有外部碎片。任何空闲块都可以用来满足请求。请注意，在创建文件时也不需要声明文件的大小。只要有空闲块，文件就可以继续增长。但是，链接分配确实有缺点。主要问题是它效率低下以支持直接访问；它只对顺序访问文件有效。要找到 文件的块，它必须从该文件的开头开始，并跟踪指针，直到到达 块。请注意，每次访问指针都需要磁盘读取。
链接分配不支持文件的随机访问，因为每个块只能从前一个找到。索引分配通过将所有指针集中到索引块中来解决此问题。一个磁盘块仅用于存储文件的 DBA（磁盘块地址）。
每个文件都与其自己的索引节点关联。如果文件很大，那么一个磁盘块可能不足以容纳该文件的所有相关 DBA。如果文件很小，那么一些磁盘块空间会被浪费，因为 DBA 较少，一个磁盘块仍然可以容纳更多 DBA。
该方法解决了碎片问题，因为块可以存储在任何位置。