内存管理 I（内存管理的基本原理和要求、连续分配管理方式）

一、内存管理的基本原理和要求

内存管理（Memory Management）是操作系统设计中最重要和最复杂的内容之一。虽然计算机硬件技术一直在飞速发展，内存容量也在不断增大，但仍然不可能将所有用户进程和系统所需要的全部程序与数据放入主存，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。操作系统对内存的划分和动态分配，就是内存管理的概念。

有效的内存管理在多道程序设计中非常重要，它不仅可以方便用户使用存储器、提高内存利用率，还可以通过虚拟技术从逻辑上扩充存储器。

内存管理的主要功能有：

在进行具体的内存管理之前，需要了解进程运行的基本原理和要求。

【总结】：

1. 内存的概念

内存可存放数据。程序执行前需要先放到内存中才能被 CPU 处理——缓和 CPU 与硬盘之间的速度矛盾。

2. 程序的链接与装入

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

• 编译。由编译程序将用户源代码编译成若干目标模块（编译就是把高级语言翻译为机器语言）。
• 链接。由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块。
• 装入（装载）。由装入程序将装入模块装入内存运行。

1）程序的链接

程序的链接有以下三种方式。

（a）静态链接

在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。将几个目标模块装配成一个装入模块时，需要解决两个问题：

• ① 修改相对地址，编译后的所有目标模块都是从 0 开始的相对地址，当链接成一个装入模块时要修改相对地址。
• ② 变换外部调用符号，将每个模块中所用的外部调用符号也都变换为相对地址。

（b）装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享。

（c）运行时动态链接

对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。其优点是能加快程序的装入过程，还可节省大量的内存空间。

2）内存的装入

内存的装入模块在装入内存时，同样有以下三种方式：

（a）绝对装入

由于程序中的逻辑地址与实际内存地址完全相同，因此不需对程序和数据的地址进行修改。

（b）可重定位装入（静态重定位）

（c）动态运行时装入（动态重定位）

动态重定位的优点：可以将程序分配到不连续的存储区；在程序运行之前可以只装入部分代码即可投入运行，然后在程序运行期间， 根据需要动态申请分配内存；便于程序段的共享。

3. 逻辑地址与物理地址

编译后，每个目标模块都从 0 号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编址的逻辑地址空间（或虚拟地址空间），对于 32 位系统，逻辑地址空间的范围为 0~2³²-1 。进程在运行时，看到和使用的地址都是逻辑地址。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。

操作系统通过内存管理部件（MMU）将进程使用的逻辑地址转换为物理地址。进程使用虚拟内存空间中的地址，操作系统在相关硬件的协助下，将它 “转换” 成真正的物理地址。逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。

4. 进程的内存映像

不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像。一个进程的内存映像一般有几个要素：

• 代码段：即程序的二进制代码，代码段是只读的， 可以被多个进程共享。
• 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。
• 进程控制块（PCB）：存放在系统区。操作系统通过 PCB 来控制和管理进程。
• 堆：用来存放动态分配的变量。通过调用 malloc 函数动态地向高地址分配空间。
• 栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长。

代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样。当调用像 malloc 和 free 这样的 C 标准库函数时，堆可以在运行时动态地扩展和收缩。用户栈在程序运行期间也可以动态地扩展和收缩，每次调用一个函数，栈就会增长；从一个函数返回时，栈就会收缩。

5. 内存保护

确保每个进程都有一个单独的内存空间。内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法：

1）在 CPU 中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当 CPU 要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。

2）采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。

实现内存保护需要重定位寄存器和界地址寄存器，因此要注意两者的区别。重定位寄存器是用来 “加” 的，逻辑地址加上重定位寄存器中的值就能得到物理地址；界地址寄存器是用来 “比” 的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。

加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器。这种方案允许操作系统内核修改这两个寄存器的值，而不允许用户程序修改。

6. 内存共享

并不是所有的进程内存空间都适合共享，只有那些只读的区域才可以共享。可重入代码又称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。但在实际执行时，也可以为每个进程配以局部数据区，把在执行中可能改变的部分复制到该数据区，这样，程序在执行时只需对该私有数据区中的内存进行修改，并不去改变共享的代码。

下面通过一个例子来说明内存共享的实现方式：

考虑一个可以同时容纳 40 个用户的多用户系统，他们同时执行一个文本编辑程序，若该程序有 160KB 代码区和 40KB 数据区，则共需 8000KB 的内存空间来支持 40 个用户（即 (40KB + 160KB) × 40）。如果 160KB 代码是可分享的纯代码，则不论是在分页系统中还是在分段系统中，整个系统只需保留一份副本即可，此时所需的内存空间仅为 40KB × 40 + 160KB = 1760KB 。

• 对于分页系统，假设页面大小为 4KB ，则代码区占用 40 个页面、数据区占用 10 个页面。为实现代码共享，应在每个进程的页表中都建立 40 个页表项，它们都指向共享代码区的物理页号。此外，每个进程还要为自己的数据区建立 10 个页表项，指向私有数据区的物理页号。

• 对于分段系统，由于是以段为分配单位的，不管该段有多大，都只需为该段设置一个段表项（指向共享代码段始址，以及段长 160KB）。由此可见，段的共享非常简单易行。

此外，在进程与线程章节中我们介绍过基于共享内存的进程通信，由操作系统提供同步互斥工具。我们后续还将介绍一种内存共享的实现——内存映射文件。

7. 内存分配与回收

存储管理方式随着操作系统的发展而发展。在操作系统由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配。为了能更好地适应不同大小的程序要求，又从固定分区分配发展到动态分区分配。为了更好地提高内存的利用率，进而从连续分配方式发展到离散分配方式——页式存储管理。引入分段存储管理的目的，主要是为了满足用户在编程和使用方面的要求，其中某些要求是其他几种存储管理方式难以满足的。

二、连续分配管理方式

【总结】：

连续分配方式是指为一个用户程序分配一个连续的内存空间，譬如某用户需要 100MB 的内存空间，连续分配方式就在内存空间中为用户分配一块连续的 100MB 空间。连续分配方式主要包括单一连续分配、固定分区分配和动态分区分配。

1. 单一连续分配

2. 固定分区分配

下图是固定分区说明表和内存分配情况的示例图：

3. 动态分区分配

1）动态分区分配的基本原理

下图是动态分区分配的示例图：

【思考】：

（a）系统要用什么样的数据结构记录内存的使用情况？

（b）当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

在动态分区分配中，与固定分区分配类似，设置一张空闲分区链（表），并按始址排序。分配内存时，检索空闲分区链，找到所需的分区，若其大小大于请求大小，便从该分区中按请求大小分割一块空间分配给装入进程（若剩余部分小到不足以划分，则无须分割），余下部分仍留在空闲分区链中。

（c）如何进行分区的回收操作？

回收内存时，系统根据回收分区的始址，从空闲分区链中找到相应的插入点，此时可能出现四种情况：

• ① 回收区与插入点的后一空闲分区相邻，将这两个分区合并，并修改后一分区表项的始址和大小

• ② 回收区与插入点的前一空闲分区相邻，将这两个分区合并， 并修改前一分区表项的大小为两者之和

• ③ 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，取消后一分区表项

• ④ 回收区没有相邻的空闲分区，此时应为回收区新建一个表项，填写始址和大小，并插入空闲分区链

2）基于顺序搜索的分配算法

在进程 / 作业装入或换入主存时，若内存中有多个足够大的空闲块，则操作系统需要按照一定的分配算法从空闲分区链（表）中选出一个分区，以分配给该进程 / 作业使用，这就是动态分区的分配策略。按分区检索方式，可分为顺序分配算法和索引分配算法。

顺序分配算法是指依次搜索空闲分区链上的空闲分区，以寻找一个大小满足要求的分区，顺序分配算法有以下四种。

（a）首次适应（First Fit）算法

首次适应算法最简单，通常也是最好和最快的。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，因此增加了开销。

（b）最佳适应（Best Fit）算法

最佳适应算法虽然称为 “最佳” ，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，会产生最多的外部碎片。

（c）最坏适应（Worst Fit）算法

最坏适应算法与最佳适应算法相反，它选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大内存块，因此性能也非常差。

（d）邻近适应（Next Fit）算法

邻近适应算法试图解决这个问题。但它常常导致在内存空间的尾部（因为在一遍扫描中，内存前面部分使用后再释放时，不会参与分配）分裂成小碎片。通常比首次适应算法要差。

【总结】：

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序	/
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程；算法开销大，回收分区后可能需要对空闲分区队列重新排序
临近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表）	不用每次都从低地址的小分区开始检索。算法开销小，回收分区后一般不需要对空闲分区队列重新排序	会使高地址的大分区也被用完

3）基于索引搜索的分配算法

当系统很大时，空闲分区链可能很长，此时采用顺序分配算法可能很慢。因此，在大、中型系统中往往采用索引分配算法。

索引分配算法的思想是，根据其大小对空闲分区分类，对于每类（大小相同）空闲分区，单独设立一个空闲分区链，并设置一张索引表来管理这些空闲分区链。当为进程分配空间时，在索引表中查找所需空间大小对应的表项，并从中得到对应的空闲分区链的头指针，从而获得一个空闲分区。索引分配算法有以下三种。

（a）快速适应算法

空闲分区的分类根据进程常用的空间大小进行划分。分配过程分为两步：

• ① 首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表；
• ② 然后从链表中取出第一块进行分配。

优点是查找效率高、不产生内部碎片；缺点是回收分区时，需要有效地合并分区，算法比较复杂，系统开销较大。

（b）伙伴系统

规定所有分区的大小均为 2 的 k 次幂（k 为正整数)。

当需要为进程分配大小为 n 的分区时（2^i-1 < n ≤ 2ⁱ），在大小为 2ⁱ 的空闲分区链中查找。若找到，则将该空闲分区分配给进程。否则，表示大小为 2ⁱ 的空闲分区已耗尽，需要在大小为 2ⁱ⁺¹ 的空闲分区链中继续查找。

若存在大小为 2ⁱ⁺¹ 的空闲分区，则将其等分为两个分区，这两个分区称为一对伙伴，其中一个用于分配，而将另一个加入大小为 2ⁱ 的空闲分区链。若不存在，则继续查找，直至找到为止。回收时，也可能需要对伙伴分区进行合并。

（c）哈希算法

根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表。

4. 总结

以上三种内存分区管理方法（单一连续分配、固定分区分配、动态分区分配）有一个共同特点，即用户程序在主存中都是连续存放的。

在连续分配方式中，我们发现，即使内存有超过 1GB 的空闲空间，但若没有连续的 1GB 空间，则需要 1GB 空间的作业仍然是无法运行的；但若采用非连续分配方式，则作业所要求的 1GB 内存空间可以分散地分配在内存的各个区域，当然，这也需要额外的空间去存储它们（分散区域）的索引，使得非连续分配方式的存储密度低于连续分配方式。

非连续分配方式根据分区的大小是否固定，分为分页存储管理和分段存储管理。在分页存储管理中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分页存储管理和请求分页存储管理。

三、小结

1、为什么要进行内存管理？

在单道系统阶段，一个系统在一个时间段内只执行一个程序，内存的分配极其简单，即仅分配给当前运行的进程。引入多道程序后，进程之间共享的不仅仅是处理机，还有主存储器。然而，共享主存会形成一些特殊的挑战。若不对内存进行管理，则容易导致内存数据的混乱，以至千影响进程的并发执行。因此，为了更好地支持多道程序并发执行，必须进行内存管理。