Memory Management in Operating System
Table of Contents
1. 操作系统内存管理基本知识
计算机系统的主要用途是执行程序。按照冯诺依曼计算机体系，这些程序在执行时必须存在于内存中。为改善 CPU 使用率和对用户的响应速度，计算机必须在内存中保留多个进程。我们需要对内存进行管理，使得各个进程能够有条理地执行。
1.1. 地址绑定
在源代码里我们通常用一个变量代表地址，我们可以将变量绑定到可重定位地址，加载程序再将重定位地址绑定成绝对地址。每次绑定都是从一个地址空间到另一个地址空间的映射。
绑定可以在下面三个时期的任何一个时期中进行：
(1)、编译时进行绑定：如果在编译时就知道内存的地址，那么可以直接绑定绝对地址。MS-DOS 操作系统的 .COM 格式程序就是在编译时绑定成绝对地址的。
(2)、加载时进行绑定：如果在编译时并不知道进程将驻留在何处，在编译时必须生成可重定位代码，这时绑定需要延迟在加载时进行。
(3)、执行时进行绑定：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才发生。在执行时绑定需要特定硬件支持，绝大多数计算机采用执行时绑定。
1.2. 逻辑地址和物理地址
什么是逻辑地址？CPU 生成的地址通常称为逻辑地址（logical address），比如 C 语言中，取地址操作得到的地址就是逻辑地址。所有逻辑地址的集合，就是逻辑地址空间。
什么是物理地址？而内存单元所看到的地址，即加载到内存地址寄存器（memory-address register）中的地址，通常称为物理地址（physical address）。所有物理地址的集合，就是物理地址空间。
如果在编译时或加载时进行地址绑定，则会生成相同的逻辑地址和物理地址。如果在执行时进行地址绑定会生成不同的逻辑地址和物理地址。由于绝大多数计算机采用执行时绑定，所以逻辑地址和物理地址一般是不同的。
在运行时从逻辑地址到物理地址的映射是由称为内存管理单元（MMU）的硬件来完成的。如图 1 所示。
Figure 1: 内存管理单元（MMU）
2. 内存管理方案
内存必须容纳操作系统和各种用户进程。应该尽可能有效地分配内存的各个部分，这是通过硬件——MMU 来完成的。下面介绍四种内存管理算法：连续内存分配、分页机制、分段机制、带有分页的分段。详细内容可参见《操作系统概念》第 9 章，该书对分页机制和分段机制的定义和优缺点表述得很好。
2.1. 连续内存分配
采用连续内存分配时，每个进程位于一个连续的内存区域。随着进程的运行和结束，连续内存分配将导致严重的内存碎片问题。内存碎片有两种：外部碎片和内部碎片，下文将介绍。
2.1.1. 外部碎片和内部碎片
内存碎片分为 外部碎片 和 内部碎片 。
外部碎片：频繁的分配与回收，导致空闲的内存空间被分为小片段，如果小片段之和可以满足进程需求，但是并不连续时，这些小片段就是外部碎片。
内部碎片：内存以固定大小的块为单位进行分配，进程所分配的内存可能比所需要的内存要大，二者的差就是内部碎片。
关于外部碎片问题可以采用紧缩（移动内存内容，使空闲内存合并到一起，代价比较高）方法解决，下面介绍的分页机制也可以解决外部碎片问题。
2.2. 分页机制
分页内存管理允许进程的物理地址空间可以是非连续的。
什么是页？物理内存分为固定大小的块，称为帧（frame）。逻辑内存也分为同样大小的块，称为页（page）。
分页机制是通过页表将逻辑地址和物理地址对应起来。
2.2.1. 页式管理的优缺点
页式管理优点：它不会产生外部碎片（只会产生内部碎片），比段式管理系统的空间浪费要小得多。
页式管理缺点：页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。
2.3. 分段机制
从用户的观点出发，将逻辑内存和物理内存对应。
2.3.1. 段式管理的优缺点
段式管理优点：段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。（保护和共享等能在段级上进行，这非常方便！）
段式管理的缺点：容易在段间留下许多空余的零碎存储空间（外部碎片）不好利用，造成浪费。
2.4. 带有分页的分段
带有分页的分段机制可以兼取页式和段式内存管理的优点。
2.4.1. 线性地址
下面介绍一下线性地址的概念。以 IA-32 架构以例，它就是 00000000h~ffffffffh（即 0~4G）的线性结构，是 32 个比特位能表示的一段连续的地址，但它是一个概念上的地址，是个抽象的地址，并不存在现实之中。线性地址主要是为分页机制而产生的，如图 2 所示。
Figure 2: 带有分页的分段机制
处理器在得到逻辑地址后首先通过分段机制转换为线性地址，线性地址再通过分页机制转换为物理地址。
2.5. IA-32 架构的内存管理
本节很多内容参考《Intel® 64 and IA-32 Architectures Software Developer's Manual Volume 3A: System Programming Guide Part 1》第 3 章。
IA-32 采用的是带有分页的分段机制（它的分段是必须的，分页是可选的）。
2.5.1. 实模式（没有分页管理）
8086（它是 16 位的 CPU，有 16 根数据线和 20 根地址线）的工作模式为实模式。图 3 描述了 8086 的逻辑地址转换为物理地址的过程。
Figure 3: 8086 的逻辑地址转换为物理地址的过程
8086 中逻辑地址由段值和偏移表示，形式为“段值：偏移”。8086 物理地址为：物理地址 = 段值×16 + 偏移。其中×16 就是左移 4 位，如逻辑地址“1111：2222H”对应的物理地址为 13332H（即 11110+2222H）。
备注 1：什么是 64K 限制和 640K 限制？
16 位 CPU 下关于内存的使用，DOS 有两个著名的限制，一是 64K 限制，另一个是 640K 限制。所谓 64K 限制，就是 DOS 下连续使用的内存最大仅能达到 64K（因为指针寄存器只有 16 位）。所谓 640K 限制，8086 能寻址 1M 的内存，下面的 640K 称为常规内存区给应用程序，上面的 384K 称为高端内存留给系统使用，这样在 DOS 下实际使用的内存就只有 640K 了。比尔·盖茨 1981 年说过一句著名的话——“无论对谁来说，640K 内存已经足够。”
备注 2：16 位 CPU，由于其指针寄存器为 16 位，理论上的寻址为 64KB（216），正是由于 8086 使用了段机制才使得 8086 能寻址 1M 内存。
备注 3：80386 处理器被复位或加电的时候以实模式启动，然后通过加载 CR0 使其中的保护模式使能位置位而进入保护模式。实模式下不能进行分页管理。
2.5.2. 保护模式分段机制
把前面介绍的图 2 的内容具体到 IA-32 架构下可得到图 4 所示。
Figure 4: IA-32 架构下的地址映射
逻辑地址到线性地址转换（分段机制）如图 5 所示。
Figure 5: IA-32 架构下逻辑地址到线性地址的转换
逻辑地址为 48 位，由 16 位的选择符（Segment Selector）加上 32 位的偏移组成。其实图 5 和 8086 的物理地址的形成（参见图 6）非常相似。
Figure 6: 8086 的逻辑地址转换为物理地址的过程
图 5 和图 6 比较相似，只是 IA-32 架构中多了个描述符表（Descriptor Table），这是个什么东西呢？解释如下：进程的逻辑地址空间分为两个部分，一部分为该进程私有（保存在本地描述符表 LDT 中），一部分为所有进程共享（保存在全局描述表 GDT 中，GDT 在整个系统中只有一个）。
如果我们把逻辑地址到线性地址的转换画具体点，可得到图 7 所示。
Figure 7: IA-32 架构下逻辑地址到线性地址的具体转换过程
在图 7 中，段选择子（Segment Selector）中有一个 TI（Table Indicator）位，用来表示段是在 GDT 中还是在 LDT 中。
2.5.3. 保护模式分页机制
分页机制（可选的）在分段机制之后进行，用来完成线性地址到物理地址的转换。常采用两级页表结构，如图 8 所示。
Figure 8: 两级页表结构
两级页表结构中，第一级称为页目录，第二级称为页表。
页目录和页表都可以看成是“偏移量”。既然是偏移量，那就有对应的基址了。
页目录的基址是什么呢？是控制寄存器 CR3。
页表的基址又是什么呢？它由 CR3 和页目录计算出。
如果我们把线性地址到物理地址的转换画具体点（图示名称和前面有细微差别，但表达意义一样），可得到图 9。
Figure 9: 80x86 线性地址到物理地址的转换（分页机制）示意图
备注：控制寄存器 CR0 中有个 PG 位，它是分页机制的开关（分页机制是可选的），上图示意的是启用分页机制的情况。控制寄存器 CR3 中保存着页目录的基地址。
2.5.4. 80386 地址转换示意图
图 10 给出了 80386 保护模式下地址转换示意图（摘自《操作系统概念（第六版）》9.6 节）。
Figure 10: Intel 80386 的地址转换
2.5.5. Tips：什么是段选择子（或段选择符）
段寄存器中的值，在实模式下被称为段值，在保护模式下被称为段选择子。