连续内存分配及其方式详解

内存应容纳操作系统和各种用户进程，因此应该尽可能有效地分配内存。本节介绍一种早期方法：连续内存分配。

内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。操作系统可以放在低内存，也可放在高内存，这取决与中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统也放在低内存。因此，本节只讨论操作系统位于低内存的情况，其他情况的讨论也类似。

通常，我们需要将多个进程同时放在内存中。因此我们需要考虑，如何为输入队列中需要调入内存的进程分配内存空间。在采用连续内存分配时，每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。

内存保护

在深入讨论内存分配前，我们应先讨论内存保护问题。结合《内存交换》一节中讨论的两个想法，我们可以防止进程访问不属于它的内存。如果一个系统有重定位寄存器和界限寄存器，则能实现我们的目标。

重定位寄存器含有最小的物理地址值，界限寄存器含有逻辑地址的范围值（例如，重定位=100040，界限=74600）。每个逻辑地址应在界限寄存器规定的范围内。MMU（内存管理单元）通过动态地将逻辑地址加上重定位寄存器的值，来进行映射。映射后的地址再发送到内存（图1 ）。

图 1 重定位和界限寄存器的硬件支持

当 CPU 调度器选择一个进程来执行时，作为上下文切换工作的一部分，分派器会用正确的值来加载重定位寄存器和界限寄存器。由于 CPU 所产生的每个地址都需要与这些寄存器进行核对，所以可以保证操作系统和其他用户的程序和数据不受该运行进程的影响。

重定位寄存器方案提供了一种有效方式，以便允许操作系统动态改变大小。许多情况都需要这一灵活性。例如，操作系统的驱动程序需要代码和缓冲空间。如果一个驱动程序（或其他操作系统的服务）不常使用，可以不必在内存中保留它的代码和数据，这部分空间可以用于其他目的。这类代码有时称为暂时的操作系统代码，它们根据需要再调入或调出。因此，使用这种代码可以在程序执行时动态改变操作系统的大小。

内存分配

现在我们讨论内存分配。最为简单的内存分配方法之一，就是将内存分为多个固定大小的分区。每个分区可以只包含一个进程。因此，多道程序的程度受限于分区数。如果使用这种多分区方法，那么当一个分区空闲时，可以从输入队列中选择一个进程，以调入空闲分区。当该进程终止时，它的分区可以用于其他进程。

这种方法最初为 IBMOS/360 操作系统所使用，现在已不再使用。下面所描述的方法是固定分区方案的推广（称为 MVT），它主要用于批处理环境。这里所描述的许多思想也可用于采用纯分段内存管理的分时操作系统。

对于可变分区方案，操作系统有一个表，用于记录哪些内存可用和哪些内存已用。开始，所有内存都可用于用户进程，因此可以作为一大块的可用内存，称为块。最后，正如将会看到的，内存有一个集合，以包含各种大小的块。

随着进程进入系统，它们将被加入输入队列。操作系统根据所有进程的内存需求和现有可用内存的情况，决定哪些进程可分配内存。当进程分配到空间时，它就加载到内存，并开始竞争 CPU。当进程终止时，它将释放内存，该内存可以被操作系统分配给输入队列内的其他进程。

任何时候，都有一个可用块大小的列表和一个输入队列。操作系统根据调度算法来对输入队列进行排序。内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用块来加载进程。操作系统可以等到有足够大的空间，或者可以往下扫描输入队列，以确定是否有其他内存需求较小的进程可以被满足。

通常，如上所述，可用的内存块为分散在内存里的不同大小的块的集合。当新进程需 要内存时，系统为该进程查找足够大的块。如果块太大，那么就分为两块：一块分配给新进程，另一块还回到块集合。当进程终止时，它将释放内存，该内存将还给块的集合。如果新块与其他块相邻，那么将这些块合并成大块。这时，系统可以检查，是否有进程在等待内存空间，以及新合并的内存空间是否满足等待进程等。

这种方法是通用动态存储分配问题（根据一组空闲块来分配大小为 n 的请求）的一个特例。这个问题有许多解决方法。

从一组可用块中选择一个空闲块的最为常用方法包括：首次适应、最优适应及最差适应：

• 首次适应：分配首个足够大的块。查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲块，就可以停止。
• 最优适应：分配最小的足够大的孔。应查找整个列表，除非列表按大小排序。这种方法可以产生最小剩余块。
• 最差适应：分配最大的块。同样，应查找整个列表，除非列表按大小排序。这种方法可以产生最大剩余块，该块可能比最优适应产生的较小剩余块更为适用。

模拟结果显示，首次适应和最优适应在执行时间和利用空间方面都好于最差适应。首次适应和最优适应在利用空间方面难分伯仲，但是首次适应要更快些。

碎片

用于内存分配的首次适应和最优适应算法都有外部碎片的问题。

随着进程加载到内存和从内存退出，空闲内存空间被分为小的片段。当总的可用内存之和可以满足请求但并不连续时，这就出现了外部碎片问题：存储被分成了大量的小块，这个问题可能很严重。

在最坏情况下，每两个进程之间就有空闲（或浪费的）块。如果这些内存是一整块，那么可能可以再运行多个进程。

选择首次适应或者最优适应，可能会影响碎片的数量。（对一些系统来说，首次适应更好；对另一些系统，最优适应更好）。另一因素是从空闲块的哪端开始分配。（哪个是剩余的块，是上面的还是下面的？）不管使用哪种算法，外部碎片始终是个问题。

根据内存空间总的大小和平均进程大小的不同，外部碎片问题或许次要或许重要。例如，采用首次适应方法的统计说明，不管使用什么优化，假定有 N 个可分配块，那么可能有 0.5N 个块为外部碎片。即 1/3 的内存可能不能使用。这一特性称为 50%规则。

内存碎片可以是内部的，也可以是外部的。假设有一个 18 464 字节大小的孔，并采用 多分区分配方案。假设有一个进程需要 18 462 字节。如果只能分配所要求的块，那么还剩下一个 2 字节的块。维护这一小块的开销要比块本身大很多。

因此，通常按固定大小的块为单位（而不是字节）来分配内存。采用这种方案，进程所分配的内存可能比所需的要大。这两个数字之差称为内部碎片，这部分内存在分区内部，但又不能用。

外部碎片问题的一种解决方法是紧缩。它的目的是移动内存内容，以便将所有空闲空间合并成一整块。然而，紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或加载时进行的，那么就不能紧缩。只有重定位是动态的，并且在运行时进行的，才可采用紧缩。

如果地址被动态重定位，可以首先移动程序和数据，然后再根据新基地址的值来改变基地址寄存器。如果能采用紧缩，那么还要评估开销。最简单的合并算法是简单地将所有进程移到内存的一端，而将所有的块移到内存的另一端，从而生成一个大的空闲块。这种方案比较昂贵。

外部碎片化问题的另一个可能的解决方案是，允许进程的逻辑地址空间是不连续的，这样，只要有物理内存可用，就允许为进程分配内存。有两种互补的技术可以实现这个解决方案：分段和分页。这两个技术也可以组合起来。

碎片是一个常见问题，当需要管理数据块时它就可能出现。