黑马程序员技术交流社区

标题: 连续分配 [打印本页]

作者: 光年之外 时间: 2019-1-3 12:41
标题: 连续分配

磁盘直接访问的特点在文件实现时提供了灵活性。在几乎每种情况下，很多文件都是存储在同一个磁盘上的。主要的问题是，如何为这些文件分配空间，以便有效使用磁盘空间和快速访问文件。

磁盘空间分配的主要常用方法有三个：连续分配、链接分配和索引分配。每个方法各有优缺点。虽然有些系统对这三种方法都支持。但是更为常见的是，一个系统只对同一文件系统类型的所有文件采用一种方法。
连续分配
连续分配方法要求，每个文件在磁盘上占有一组连续的块。磁盘地址为磁盘定义了一个线性排序。有了这个排序，假设只有一个作业正在访问磁盘，在块 b 之后访问块 b+1 通常不需要移动磁头。当需要磁头移动（从一个柱面的最后扇区到下一个柱面的第一扇区）时，只需要移动一个磁道。因此，用于访问连续分配文件的所需寻道数量最小，在确实需要寻道时所需的寻道时间也最小。

文件的连续分配可以用首块的磁盘地址和连续的块数来定义。如果文件有 n 块长并从位置 b 开始，则该文件将占有块 b，b+1，b+2，…，b+n-1。每个文件的目录条目包括起始块的地址和该文件所分配区域的长度。

连续分配文件的访问非常容易。对于顺序访问，文件系统会记住上次引用的块的磁盘地址，如需要可读入下一块。对于直接访问一个文件的从块 b 开始的第 i 块，可以直接访问块 b+i。因此，连续分配支持顺序访问和直接访问。

不过，连续分配也有一些问题。一个难题是，为新文件找到空间。用于管理空闲空间的系统决定了这个任务如何完成，虽然可以使用任何管理系统，但是有的系统会比其他的要慢。

连续分配问题可以作为通用动态存储分配问题的一个具体应用，即如何从一个空闲块列表中寻找一个满足大小为 n 的空间。从一组空闲块中寻找一个空闲块的最为常用的策略是，首次适合和最优适合。模拟结果显示在时间和空间使用方面，首次适合和最优适合都要比最坏适合更为高效。首次适合和最优适合在空间使用方面不相上下，但是首次适合一般更快。

所有这些算法都有外部碎片的问题。随着文件的分配和删除，可用磁盘空间被分成许多小片。只要空闲空间分成小片，就会存在外部碎片。当最大连续片不能满足需求时就有问题；存储空间分成了许多小片，其中没有一个足够大以存储数据。因磁盘存储总量和文件平均大小的不同，外部碎片可能是个小问题，但也可能是个大问题。

为了防止外部碎片引起的大量磁盘空间的浪费，将整个文件系统复制到另一个磁盘。原来的磁盘完全变成空的，从而创建了一个大的连续空闲空间。然后，通过从这个大的连续空闲空间采用连续分配方法，将这些文件复制回来。这种方案将所有空闲空间有效合并起来，解决了碎片问题。

这种合并的代价是时间，而且大硬盘的代价可能特别高。合并这些磁盘空间可能需要数小时，可能每周都需进行。有些系统要求，这个功能线下执行且文件系统要卸载。在这停机期间不能进行正常操作，因此生产系统应尽可能地避免合并。大多数的需要整理碎片的现代系统能够和正常的系统操作一起在线执行合并，但是性能下降可能很明显。

连续分配的另一个问题是，确定一个文件需要多少空间。当创建一个文件时，需要找到并分配它所需空间的总数。创建者（程序或人员）又如何知道所创建文件的大小？在某些情况下，这种判断可能相当简单（例如，复制一个现有文件），一般来说，输出文件的大小可能难以估计。

如果为文件分配的空间太小，则可能会发现文件无法扩展。特别是对于最优适合的分配策略，文件两侧的空间可能已经使用。因此，不能在原地让文件更大。

这时，有两种可能办法：
终止用户程序，并给出适当的错误消息。这样，用户必须分配更多的空间，并再次运行该程序。这些重复的运行可能代价很高。为了防止这些问题，用户通常会高估所需的磁盘空间，从而造成相当大的空间浪费。
找一个更大的空间，将文件内容复制到新空间，并释放以前的空间。只要空间存在，就可以重复这些动作，不过如此可能耗时。然而，用户无需获知究竟发生了什么事情；而系统虽有问题仍继续运行，只不过会越来越慢。

即使文件所需的空间总量事先已知，预先分配仍可能很低效。一个文件在很长时间内增长缓慢（数月或数年），仍必须按它的最终大小来分配足够空间，即使这个空间很长时间内不用。因此，该文件有一个很大的内部碎片。

为了最小化这些缺点，有些操作系统使用连续分配的修正方案。这里，最初分配一块连续空间。以后，当这个数量不够时，会添加另一块连续空间（称为扩展）。然后，文件块的位置就记录为：地址、块数、下一扩展的首块的指针。

在有些系统上，文件所有者可以设置扩展大小，但是如果所有者不正确，这种设置会导致低效。如果扩展太大，内部碎片可能仍然是个问题；随着不同大小的扩展的分配和删除，外部碎片可能也是个问题。商用 Veritas 文件系统使用扩展来优化性能。Veritas 是标准 UNIX UFS 的高性能替代。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2