连续内存分配

内存必须容纳操作系统和各种用户进程，因此应该尽可能有效的分配内存的各个部分。

内存通常分为两个区域，一个用于驻留操作系统，另一个用于用户进程。操作系统可以位于低内存，也可以位于高内存，影响这一决定的主要因素是中断向量的位置，由于中断向量通常位于低内存，因此程序员通常将操作系统页放在低内存。

内存映射与保护

在说内存分配之前，先说说内存映射与保护的问题，通过采用重定位寄存器和界限地址寄存器，可以实现这种保护。

重定位寄存器含有最小的物理地址值，界限地址寄存器含有逻辑地址的范围值(例如：重定位=100050， 界限=74500)。有了重定位寄存器和界限地址寄存器，每个逻辑地址必须小于界限地址寄存器。MMU动态的将逻辑地址加上重定位寄存器的值后映射成物理地址，映射后的物理地址再交送内存单元。

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

内存分配

现在我们就来讨论一下内存分配，最简单的内存分配方式之一就是将内存分为多个固定大小的分区(parttiion)。每个分区只能容纳一个进程，因此，多道程序的程度会受到分区数所限制。如果使用这种多分区方法，当一个分区空闲的时候，可以从输入队列中选择一个进程，以调入到空闲分区，当进程终止时，其分区可以被其他进程所使用。这种方法最初为IBM OS/360 操作系统所使用，不过现在已经不再使用了。

下面来介绍可变分区方案。在可变分区方案里，操作系统有一个表,用于记录哪些内存可用和哪些内存已经被使用，在一开始，所有的内存都可用于用户进程，因此可以作为一大块可用内存，称为孔(hole)。当有新进程需要内存时，为该进程查找足够大的孔，如果找到，可以从该进程分配所需的内存，孔内未分配的内存可以下次再用。

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

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

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

分配方法

上面讲的这种方法是通用动态存储分配问题的一种情况(根据一组空闲孔来分配大小为 n 的请求)。这个问题有许多解决方法，从一组可用孔中选择一个空闲的最常用方法有首次适应(first-fit)、最佳适应(best-fit)、最差适应(worst-fit)。

1. 首席适应:分配第一个足够大的孔，查找可以从头开始，也可以从上次首次适应结束时开始，一旦找到足够大的空闲空间孔，就可以停止。
2. 最佳适配: 分配最小的足够大的孔，必须查找整个列表，除非列表按大小排序，这种方法可以产生最小剩余孔。
3. 最差适应: 分配最大的孔，同样，必须查找整个列表，除非列表按大小排序，这种方法可以产生最大剩余孔，该孔可能比最佳适应方法产生的比较剩余孔更为有用。

碎片

首次适应方法和最佳适应方法都有外部碎片问题,随着进程的装入和移出内存，空闲内存被分为小片段，当所有总的可用内存之和可以满足请求，但并不连续时，这就出现了外部碎片的问题。这个问题可能很严重。在最坏的情况下，每两个进程之间就有空闲块(或浪费)。如果这些内存块是一整块，那么就可以再运行多个进程。

在首次适应和最佳适应之间的选择可能会影响碎片的量(对一些系统来说首次适应更好，对另一些系统最佳适应更好)。另一个影响因素是从空闲块的哪端开始分配(顶端还是末端)。不管使用哪种算法，外部碎片始终是个问题。

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

一种解决外部碎片的问题的方法是紧缩(compaction),紧缩的目的是移动内存内容，以便所有空间合并成一整块。但紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或装入市进行的，那么就不能紧缩。紧缩仅在重定位是动态并在运行时可采用。如果地址被动态重定位，可以首先移动程序和数据，然后再根据新基地址的值来改变基地址寄存器，如果能采用紧缩，还需要评估其开销，最简单的合并算法是简丹的将所有进程移动到内存的一端，而将所有的孔移到内存的另一端，以便生成一个大的空闲块，这种方案开销较大。

另一种可能解决碎片问题的方法是允许物理地址空间为非连续。这样只要有物理内存就可以为进程分配，这种方案有两种互补的实现技术: 分页和分段，这两种技术也可以合并。