内存管理(四)——虚拟内存

前言

上一篇介绍完了内存分页，接下来就是内存管理的重头戏——虚拟内存了。

在正式介绍虚拟内存之前，先简单地介绍一下相关技术的发展过程。虽然我们的物理内存相较于过去已经变大了很多，但是程序所要占用的内存也一直在增大，而且增长速度甚至超过了物理内存的扩大速度。所以科学家们经常会想，有没有办法在有限的内存条件下，能够运行尽可能多的程序。

于是慢慢发展出了覆盖技术，再到交换技术，再到我们现在所使用的虚拟内存技术。

覆盖技术

把程序按照其自身逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来覆盖运行，从而共用一个分区。

• 必要部分（常用功能）的代码和数据常驻内存；
• 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要时才装入内存；
• 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖，即这些模块共用一个分区。

缺点：

• 需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了编程的复杂度。
• 覆盖模块访问外部存储器的时间开销很大。

交换技术

以进程为交换的单位，需要把进程的整个地址空间换入换出，增加了处理器的开销。

• 可将暂时不能运行的程序送到外存 ，从而获得空闲内存空间；
• 操作系统把一个进程的整个地址空间的内存保存到外存中（换出 swap out），而将外存中的某个进程的地址空间读入到内存中（换入 swap in）。换入换出内容的大小为整个程序的地址空间。

缺点：

• 以整个进程为单位进行交换，交换的开销很大。

覆盖和交换的比较

• 覆盖的单位是程序模块；交换的单位是程序。
• 覆盖发生在运行程序的内部；交换发生在内存中程序与操作系统之间。
• 覆盖需要程序员指定各个模块之间的覆盖关系；交换是由操作系统自动进行的，不需要额外的人为操作。

虚拟内存技术

在内存分段或分页的基础上，通过将内存中暂时不使用的页或段调出保存在外存上，从而腾出更多空间存放将要装入的页或段。

虚存技术 = 内存分页（或分段）+ 请求调页 + 页面置换

• 在装入程序时，不必将其全部装到内存中，而只需将当前需要执行的部分页面或段装入内存，就可让程序开始执行；
• 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序；
• 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出更多空间存放将要装入的页或段。

虚拟内存的理论大小 = min(内存+外存，CPU寻址范围)

虚拟内存的代价：

• 虚存的管理需要额外的数据结构，从而需要占用额外的内存。
• 虚拟地址到物理地址的转换需要额外的开销。
• 页面的换入换出需要磁盘 I/O，比较耗时。

前提

由于程序的局部性原理，在某一时刻，内存中会存在许多暂时不使用的页，如果能将这些页先换出内存暂存，等需要时再换入，就可以使用更大的内存空间。相当于是拿时间换空间。

程序的局部性原理（Principle of locality）：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。

• 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短的时间内。
• 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小的区域内。

具体实现

大部分虚拟存储系统都采用虚拟页式内存管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能。

内存分页管理和请求调页（即缺页中断）都在上一篇中讲过了，这里就不再赘述了。接下来讲一下页面置换的实现。

页面置换分为局部和全局两种：

• 局部指的是针对一个进程进行页面置换（只看某个进程页面的使用情况，也只会置换这个进程的页面）
• 全局指的是针对所有进程进行页面置换（同时兼顾所有进程页面的使用情况）

局部页面置换算法

局部页面置换只针对一个进程来进行操作。通过以下几种算法实现，常见的有以下几种：

最佳页面置换算法：OPT（Optimal），置换在未来最长时间不访问的页面。是理想中的算法，在实际系统中难以实现（无法准确预测未来的使用情况）。

先进先出置换算法：FIFO，First In First Out，选择在内存驻留时间最长的页面进行置换。可以用一个先入先出的队列实现。

最近最少使用置换算法：LRU，Least Recently Used，选择最长时间没有被访问的页面进行置换。可以使用链表或者栈实现。

最近最不常用置换算法：LFU，Least Frequently Used，选择一段时间内访问次数最少的页面进行置换。实现：对每个页面设置一个访问计数器，访问时加一，在发生缺页中断时，淘汰计数值最小的页。也可以用定期位移的办法。

时钟页面置换算法：Clock，将页表组织成环形链表，并把指针指向最老的页面（依靠页表项中的访问位，最近被访问过为 1，否则为 0）。

二次机会算法：在时钟算法的基础上，同时使用访问位和脏位来指导置换。只有两个位都为 0，才置换页面；若两个位都为 1，先将访问位置为 0。

全局页面置换算法

局部页面置换算法都针对一个进程来进行操作的，然而OS可以同时执行多个程序，如果每一个程序都采取一个固定的局部页面置换算法会带来一些问题（并发的程序访问会降低程序的局部性，从而导致缺页率上升和 CPU 利用率降低），所以引入了全局页面置换算法。

工作集

当前时刻，进程正在使用的逻辑页面集合，用二元函数 W=(t,△) 表示。t 为当前的执行时刻，△ 为工作集窗口。t 是一直变的，工作集窗口也一直在滑动。

常驻集

当前时刻，进程实际驻留在内存中的页面集合。常驻集越接近工作集，表示发生缺页率越小。

• 工作集是进程在运行过程中固有的性质；而常驻集取决于系统分配给进程的物理页面数目（预先分配），以及所采用的页面置换算法。

工作集页面置换算法

随着工作集窗口的移动，只要页面不在工作集中，就置换出去。

缺页率页面置换算法

PFF（Page Fault Frequency），根据缺页率，动态地调整常驻集的大小，从而使缺页率保持在一个合理的范围内。

• 若进程缺页率过高 则增加常驻集以分配更多物理页面数。
• 若进程缺页率过低 减少常驻集将一些页面置换到外存。

工作集算法每一次访问都在考虑置换哪一个页面到外存；而缺页率算法只有在时间间隔够大的时候才置换到外存。

抖动问题

Thrashing，如果分配给一个进程的物理页面太少，不能包含整个的工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢。

后备存储

Backing Store，指的是暂时存储从内存中换出的代码和数据。

• 一个虚拟地址空间的页面可以被映射到一个文件中的某个位置
• 代码段可以映射到可执行二进制文件
• 动态加载的共享库程序段可以映射到动态调用的库文件
• 其他段可能被映射到交换文件（swap file）

特征

• 更大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离。
• 部分交换：与交换技术相比，虚拟存储的调入和调出是对部分虚拟地址空间进行的。
• 不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续性。

用户空间和内核空间

虚拟内存空间分为用户空间和内核空间。

• 内核空间（Kernal Space），这个空间只有内核程序可以访问；
• 用户空间（User Space），这部分内存专门给应用程序使用。

用户空间中的代码被限制了只能使用一个局部的内存空间，我们说这些程序在用户态（User Mode） 执行。内核空间中的代码可以访问所有内存，我们称这些程序在内核态（Kernal Mode） 执行。

应用程序如果需要进入内核空间，就需要通过系统调用。

虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

用户空间的分布情况：

用户空间内存，从低到高分别是 6 种不同的内存段：

• 代码段（.text），存放二进制可执行代码。这部分区域大小在程序运行前就已经确认，并且不能修改；
• 已初始化数据段（.data），包括所有有初值的全局变量和用static修饰的静态变量、常量数据；
• 未初始化数据段（.bss），包括未初始化的静态变量；
• 堆段，包括动态分配的内存，从低地址开始向上增长。堆是先进先出的（FIFO）。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）；
• 文件映射段，包括动态库、共享内存等，从低地址开始向上增长；
• 栈段，包括函数的局部变量、参数、返回值等。栈是先进后出的（FILO）。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；栈段可以通过系统调用自动地扩充空间，但是不能回收空间，所以栈段设置得太大会导致内存泄露。

上述几种内存区域中数据段、BSS 段、堆通常是被连续存储在内存中，在位置上是连续的，而代码段和栈往往会被独立存放。

代码段、数据段、BSS 段的大小固定。

在 BSS 段上方有一个随机的 gap 区域，

在这 6 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或 mmap() ，就可以分别在堆和文件映射段动态分配内存。

总结

为了在有限的内存空间中尽可能地运行更多的程序，渐渐地发展出覆盖技术、交换技术以及目前所使用的虚拟内存技术。

虚拟内存技术是在段页式管理（以 Linux 为例）的基础上加上页面置换实现的。页面置换算法有局部和全局两种，其中局部页面置换算法只考虑单个进程的使用情况，而全局页面置换算法则考虑所有可置换的页面。

虚拟内存空间分为用户空间和内核空间，内核空间只有操作系统可以使用，且是进程间共享的；而用户空间是操作系统分配给用户使用的，是进程私有的。用户空间又依据类型分为了六种不同的内存段供用户使用。