连续内存分配

外部碎片和内部碎片

• 外部碎片指的是尚未分配出去、由于太小而无法分配出去的内存空间（化整为零）
• 内部碎片指的是已经分配出去、但没有完全得到利用的内存空间

单一连续分配

单一连续分配只适用于单用户、单任务的操作系统中，它会把整个内存区划分为系统区和用户区，一道用户程序就会独占整个用户区，因此存储器的利用率非常低、内部碎片很大（分配了整个用户区，但实际用到的空间并不多）。

固定分区分配

固定分区分配是最简单的多道程序的存储管理方式，依然是将整个内存区划分为系统区和用户区，但是用户区进一步细分：划分为多个固定大小的分区，系统启动后就已经分好了分区，一个分区放一个进程。

每个分区的大小可以相等也可以不等：

• 如果每个分区大小相等，缺乏灵活性：对于小进程，无法利用全部空间而产生内部碎片；对于大进程，找不到大小足够的分区。

• 如果每个分区的大小不等，提高了灵活度，可以将用户区划分为大量的小分区、适量的中分区、少量的大分区，并维护一张记录了分区号、分区大小、分区起始地址、分区分配状态的分区使用表。每次需要为进程分配内存空间的时候，先在这张表上进行检索，找到一个合适的分区分配给它。

  这种划分方式可以认为不存在过小的、分配不出去的内存空间，不会产生外部碎片；但是，由于提前划分了分区，不能保证一个进程完全利用完某个分区，分区会产生内部碎片：

  

  浪费了 7+23+87+211K=328K 的空间

动态分区分配

概括

动态分区分配方式比前面的分配方式要灵活很多，类似于按需分配，不是预先划分好，而是进程需要多少内存空间，就给它多少内存空间。

但这种分配方式需要考虑的问题是，当一个进程有多个空闲的内存分区可供选择的时候，它应该使用哪个空间呢？比如进程 2 运行完释放了 20K 的内存空间，此时进程 4 进来，也需要用到 20K 的内存空间，它既可以选择占用进程 2 释放的空间，也可以选择占用后面没被用到的一大片空间。

因此，我们需要一种算法来决定进程 4 的选择，而且为了更好地描述内存使用情况，我们同样要像固定分区分配一样维护一张空闲分区表或者一个空闲分区链。

主要过程

假设进程 X 需要用到 x 大小的内存空间，在某种算法下，系统会检索空闲分区表或者空闲分区链，决定将某个空闲分区分配给这个进程。假设这个空闲分区大小为 y（y>x），若 y-x 的值小于预先设定的一个阈值，说明进程可以充分利用这个空闲分区，可以将整个分区直接分配给进程；若 y-x 的值大于这个阈值，说明空闲分区无法得到完全的利用，可以将整个分区能够被充分利用的那部分（也即 x）划分给进程，而剩下的 y-x 则继续留在空闲分区表（因为只记录空闲分区，所以没有 “状态” 项）或者空闲分区链（不讲不考察）中。

基于顺序搜索的算法

首次适应（FF）

将多个空闲分区按照地址递增的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 由于地址一开始就是确定下来的，能够保证顺序始终是递增的，因此这种算法无需频繁地变更空闲分区的顺序，而且每次优先利用低地址空间，保证了高地址空间有足够大的空闲区域可供大进程使用。
• 但是，因为每次优先利用低地址空间，所以低地址空间被不断分割，产生了大量的外部碎片；而且，每次都是从头开始寻找空闲空间，效率并不高。

邻近适应（NF）

邻近适应算法（循环首次适应算法）克服了首次适应算法的缺点，它同样是将多个空闲分区按照地址递增的顺序排列，不同的是，每次查找都是从上次查找结束的位置开始查找的

• 不会从头开始一个个找，一定程度上提高了效率；而且，它会更趋向于往后推进，避免了对低地址空间重复地进行分割，进而避免了大量外部碎片的产生。

• 优点同时也是缺点，由于邻近适应算法更趋向于往后推进，所以更可能分割高地址空间，这就破坏了首次适应算法的初衷，导致大进程可能没有足够的空闲空间可利用。

最佳适应（BF）

连续分配的方式规定，为各个进程分配的必须是一块连续的空间，因此对于一块内存空间来说，若它不断被分割，则意味着它能容纳下大进程的可能性越低。为了保证有足够的内存空间可以容纳大进程，基本思想应该是优先利用小的空闲分区，而保留大的空闲分区。

最佳适应算法将空闲分区按照容量递增的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 分配操作主要集中在小的空闲分区那里进行，保证了有大的空闲分区可以用来容纳大进程。
• 因为要按照容量递增的顺序排列，而每次内存的分配和回收都会改变某一块空间的大小，每次在进行分配和回收的时候，基本都要重新进行排序，算法开销大。而且，由于分配操作集中在小的空闲分区进行，导致它们不断被分割，容易产生大量外部碎片。

最坏适应 （WF）

为了克服最佳适应算法的缺点，最坏适应算法规定，将空闲分区按照容量递减的顺序排列，每次分配内存的时候顺序查找空闲分区表，找到第一个大小能满足要求的空闲分区。

• 最坏适应算法优先使用大的空闲分区，而大的空闲分区由于容量充足，即使被不断分割，也可以保证剩余空间不至于太小，依然能够被新的进程利用，大幅度减少了外部碎片的产生。
• 但是，这又破坏了最佳适应算法的初衷，因为优先使用大的空闲分区，很容易导致后续的大进程没有足够大小的空闲分区可以利用。并且，这种算法也无法避免分配和回收之后的重新排序。

总结

由于动态分区分配不是事先划分好区域，而是 “按需分配”，所以不会出现区域划分出去后无法完全得到利用的情况，也即不会产生内部碎片；但是可能出现内存空间太小而无法被分配出去的情况，也即可能产生外部碎片。

基于索引搜索的算法

当系统很大的时候，内存分区会很多，这时候还采取基于顺序搜索的动态分区分配算法的话，效率并不高。因此出现了基于索引搜索的动态分区分配算法。

快速适应

快速适应算法（分类搜索算法）将空闲分区按照进程常用的空间大小进行分类，比如 2KB 为一类，4KB 为一类，6KB 为一类等，对于每一类空闲分区，会有一个单独的空闲分区链表。此外，还会有一张总的管理索引表，索引表的每一个表项对应了一类空闲分区。

在为进程分配分区的时候，首先会根据进程长度，从索引表中找到能容纳它的最小空闲区链表，接着将该链表的第一块分配给进程。

• 因为前面已经进行了合理的分类，因此这种方法不会对任何分区产生分割，也不会产生外部或者内部碎片，并且查找效率很高
• 但是，回收、合并分区时的算法复杂，系统开销比较大

伙伴系统

接下来的伙伴关系和哈希算法为自学内容

举个例子

假设系统总的内存为 512KB，现有进程活动如下：

• 进程 A 请求 100KB，进程 B 请求 50KB，进程 C 请求 100KB
• 进程 A 释放 100KB
• 进程 D 请求 20KB
• 进程 D 释放 20KB
• 进程 B 释放 50KB

按照伙伴系统的算法，内存的分配和回收是怎么进行的呢？

首先，一开始肯定是整片空的内存空间，进程 A 请求 100KB，因为 64<100<128，即 2⁶<100<2⁷，所以寻找是否有 2⁷=128 的空闲分区，当然是没有的（目前只有 512KB)，所以寻找是否有 2⁸=256 的空闲分区，也没有，所以寻找是否有 2⁹=512 的空闲分区，找到了，此时就把 512KB 一分为二：

一半的 256KB 加入到对应的空闲分区链表，一半的 256KB 用于分配，对这一半继续一分为二：

一半的 128KB 加入到对应的空闲分区链表，一半的 128KB 用于分配，这一半对进程 A 来说足够了，于是占用它：

进程 B 请求 50KB，因为 32<50<64，即 2⁵<100<2⁶，所以寻找是否有 2⁶=64 的空闲分区，没有，所以寻找是否有 2⁷=128，找到了，此时就把 128KB 一分为二：

一半的 64KB 加入到对应的空闲分区链表，一半的 64KB 用于分配，这一半对进程 B 来说足够了，于是占用它：

进程 C 请求 100KB，因为 64<100<128，即 2⁶<100<2⁷，所以寻找是否有 2⁷=128 的空闲分区，没有，所以寻找是否有 2⁸=256 的空闲分区，找到了，此时就把 256KB 一分为二：

一半的 128KB 加入到对应的空闲分区链表，一半的 128KB 用于分配，这一半对进程 C 来说足够了，于是占用它：

进程 A 释放 100KB：

进程 D 请求 20KB，因为 16<20<32，即 2⁴<100<2⁵，所以寻找是否有 2⁵=32 的空闲分区，没有，所以寻找是否有 2⁶=64 的空闲分区，找到了，此时就把 64KB 一分为二：

一半的 32KB 加入到对应的空闲分区链表，一半的 32KB 用于分配，这一半对进程 D 来说足够了，于是占用它：

进程 D 释放 20KB，回收 32KB，由于事先已经有一个 32KB，所以此时两个互为伙伴的 32KB 进行合并：

进程 B 释放 50KB，回收 64KB，由于事先已经有一个 64KB，所以此时两个互为伙伴的 64KB 进行合并，形成 128KB，由于事先已经有一个 128KB，所以此时两个互为伙伴的 128KB 进行合并，形成 256KB：

计算伙伴地址的方法：对于给定的内存块，若它的大小为 2^k，起始地址为 x，

• 如果 x/2^k 为奇数，则伙伴地址为 x - 2^k
• 如果 x/2^k 为偶数，则伙伴地址为 x + 2^k

哈希算法

快速适应和伙伴系统都是将空闲分区按照大小进行分类，并为每一类建立一个独立的空闲分区链表，再用一个总的索引表进行记录。不过，如果分类过多，则索引表的表项也会过多，这时候搜索索引表的时间开销就会比较大。

因此，哈希算法选择建立一张哈希表（而不是普通的索引表），这张哈希表以空闲分区大小作为关键字，每次需要进行分配的时候，会根据所需空闲分区的大小，通过哈希函数快速计算得到该空闲分区在表中的位置，从而得到对应的空闲分区链表。

动态可重定位分区分配

动态可重定位分区分配算法与动态分区分配算法基本一致，仅仅增加了紧凑功能。

连续分配为某个进程分配的必须是一块连续的空间，若多个空闲分区不是相邻的，即便它们的大小总和已经满足进程的需求，也无法进行分配。采用紧凑技术解决这个问题。紧凑技术把内存中各个进程进行移动并使其相邻，从而化零为整，带来了更大的空闲分区：

在这里会发现，每次发生紧凑，各个程序和数据的物理地址就要发生改变。

• 假定我们先前采用的是静态重定位装入方式，那么在模块装入内存的时候，就已经把逻辑地址转换为物理地址了，每次发生紧凑，都要在程序上重新修改一次物理地址。
• 如果我们采用动态重定位装入方式，各个程序和数据的地址全部都是逻辑地址，当程序需要访问地址时，无需修改程序上的地址，只需要将该逻辑地址与当前重定位寄存器里存放的物理起始地址进行相加。每次发生紧凑时，也只需要用紧凑后的新起始地址去替换重定位寄存器里的旧起始地址。