操作系统学习笔记-11：内存分配（一）：连续分配

存储层次至少具有三级：CPU 寄存器、主存（内存）和辅存（外存）

2. 程序的装入与链接

2.1 概括：

用户程序在执行前必须先进入内存，具体来说包括以下步骤：

• 编译：由编译程序将用户源程序编译成多个目标模块
• 链接：由链接程序将编译后的多个目标模块和所需的库函数链接在一起，形成一个总的装入模块
• 装入：由装入程序将装入模块装入内存运行

2.2 链接：

• 静态链接：直接将编译后的多个目标模块和所需的库函数链接在一起，形成一个不再拆开的装入模块，该模块整体装入内存
• 装入时动态链接：不事先进行链接，而是一边装入内存，一边进行链接，这种方式便于修改和更新
• 运行时动态链接：不事先进行链接，而是一边执行程序，一边进行模块的装入和链接，这种方式可以确保只装入和链接那些在执行时需要用到的模块，而不会引入多余的、实际根本用不到的模块，因此有利于节省内存空间。

2.3 装入

装入模块中指令所涉及的地址是相对地址（逻辑地址），往往并不是装入内存后的实际地址，因此在装入模块装入内存后，需要将原先的相对地址转换成绝对地址（物理地址）。在下面三种装入方式中，对相对地址的处理是不同的。

绝对装入方式：

在单道程序运行环境中，通常可以事先知道程序最终装入内存时的实际地址，所以编译程序产生的目标模块中可以直接使用绝对地址，模块在装入到内存的时候也无需进行地址转换的工作。

静态重定位装入方式：

但在多道程序运行环境中，无法事先知道程序最终装入内存时的实际地址，所以目标模块中只能使用相对地址，所有指令中涉及到的地址都是相对于起始地址 0 来说的。装入模块可以装入到内存的合适位置，并且 在装入的时候 会进行地址转换（重定位）的工作。

“静态”主要体现在程序装入内存后，在运行期间就不能再移动了，因为一旦移动就意味着需要再次更改物理地址，而地址是无法修改的，这时候就会发生错误。

动态重定位装入方式：

但很多时候，程序在内存中的位置会经常发生改变，比如在外存和内存之间对换。位置不会是一成不变的，这时候就要采用动态重定位装入方式。这种方式并不急于在装入的时候就进行地址转换，而是在程序真正执行的时候才去进行地址转换的工作。

这意味着程序在装入内存后，在运行期间是可以移动的。因为不管移动到哪个内存位置，始终会有一个重定位寄存器用于记录和更新装入模块当前的物理起始地址，逻辑地址只需要和这个物理起始地址相加即可得到物理地址。

3. 内存分配：连续分配

3.0 外部碎片和内部碎片

在内存分配中有外部碎片和内部碎片的概念：

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

3.1 单一连续分配

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

3.2 固定分区分配

固定分区分配适用于多道程序环境，依然是将整个内存区划分为系统区和用户区，但是用户区进一步细分：划分为多个 固定大小 的分区，一个分区放一个进程。

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

• 如果每个分区大小相等，实际上是很不灵活的，很可能导致的问题就是：对于小进程，会无法利用完全部空间而产生内部碎片；对于大进程，会找不到大小足够的、可以容纳下自己的分区（因为每一个分区可能被划分得很小）

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

  这种划分方式已经进行了合理的划分，可以认为不存在过小的、分配不出去的内存空间，因此不会产生外部碎片；但是，若进程过大，可能无法找到一个足够大小的分区分配给它，而且由于采用的是划分分区的方式，不能保证一个进程完全利用完某个分区，分区还是可能产生内部碎片的。

3.3 动态分区分配

① 概括

和前面的分配方式不同，动态分区分配方式要灵活得多，就像日常生活中的按需分配，不是预先划分好，而是进程需要多少内存空间，我们就给它多少内存空间。比如说一开始有 100 的空闲空间，进程 1 进来用了 10，进程 2 进来用了 20，进程 3 进来用了 30，需要多少就给多少，以此类推 …..

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

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

② 主要过程

动态分区分配的过程是这样的：

假设进程 X 需要用到 x 大小的内存空间，那么在某种算法下，系统会检索空闲分区表或者空闲分区链，决定将某个空闲分区分配给这个进程。假设这个空闲分区大小为 y（y>x），若 y-x 的值非常地小，甚至小于我们预先设定的一个阈值，那么说明进程可以充分利用这个空闲分区，我们可以将整个分区直接分配给进程；若 y-x 的值大于这个阈值，说明空闲分区无法得到完全的利用，我们可以将整个分区能够被充分利用的那部分（也即 x）划分给进程，而剩下的 y-x 则继续留在空闲分区表或者空闲分区链中。

不过，具体都有哪些算法来决定分区的分配呢？

③ 具体算法：基于顺序搜索

首次适应（FF）

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

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

邻近适应（NF）

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

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

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

最佳适应（BF）

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

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

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

最坏适应（WF）

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

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

最后我们可以来看一张总结图：

总结：

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

④ 具体算法：基于索引搜索

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

快速适应

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

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

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

伙伴系统

伙伴系统的具体规则，书里的描述会更完整：

为了更直观地理解，这里用一个例子来说明。

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

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

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

首先，一开始肯定是整片空的内存空间：

进程 A 请求 100kb，因为 64<100<128，即 2^6^<100<2^7^，所以寻找是否有 2^7^=128 的空闲分区，当然是没有的（目前只有 512kb），所以寻找是否有 2^8^=256 的空闲分区，也没有，所以寻找是否有 2^9^=512 的空闲分区，找到了，此时就把 512kb 一分为二：

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

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

进程 B 请求 50kb，因为 32<50<64，即 2^5^<100<2^6^，所以寻找是否有 2^6^=64 的空闲分区，当然是没有的，所以寻找是否有 2^7^=128，找到了，此时就把 128kb 一分为二：

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

进程 C 请求 100kb，因为 64<100<128，即 2^6^<100<2^7^，所以寻找是否有 2^7^=128 的空闲分区，当然是没有的，所以寻找是否有 2^8^=256 的空闲分区，找到了，此时就把 256kb 一分为二：

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

进程 A 释放 100kb：

进程 D 请求 20kb，因为 16<20<32，即 2^4^<100<2^5^，所以寻找是否有 2^5^=32 的空闲分区，当然是没有的，所以寻找是否有 2^6^=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

哈希算法

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

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

3.4 动态可重定位分区分配

动态可重定位分区分配算法与 动态分区分配算法 基本一致，区别仅在于，它在原有的基础上增加了 紧凑 功能。

到目前为止，我们所讲的都是连续分配的方式，也就是说，为某个进程分配的必须是一块连续的空间 —— 若多个空闲分区不是相邻的，那么即便它们的大小相加后，已经足以满足进程的需求，也无济于事。为此，可以采用紧凑技术解决这个问题。紧凑技术可以把内存中各个进程进行移动，使得它们都相邻，从而把原先分开的各个空闲分区合并在一起，带来了更大的、可以充分利用的空闲分区：

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

• 假定我们先前采用的是静态重定位装入方式，那么在模块装入内存的时候，就已经把逻辑地址转换为物理地址了，就会导致在这里需要再进行一次地址的修改，更麻烦的是，之后每次发生紧凑，都要在程序上重新修改一次物理地址。

• 相反，如果我们采用动态重定位装入方式，那么各个程序和数据的地址其实全程都是逻辑地址，在每次程序执行到需要访问地址的时候，无需修改程序上的地址，只需要 将该逻辑地址与当前重定位寄存器里存放的物理起始地址进行相加 即可。并且，每次发生紧凑的时候，也只需要用紧凑后的新起始地址去替换重定位寄存器里的旧起始地址。

操作系统系列学习笔记：

操作系统学习笔记-1：基础概念

操作系统学习笔记-2：体系结构和运行机制

操作系统学习笔记-3：初识进程和进程控制

操作系统学习笔记-4：进程同步与进程互斥（一）

操作系统学习笔记-5：进程同步与进程互斥（二）：信号量机制

操作系统学习笔记-6：进程同步与进程互斥（三）：经典问题

操作系统学习笔记-7：进程通信

操作系统学习笔记-8：线程

操作系统学习笔记-9：调度

操作系统学习笔记-10：死锁 )