操作系统入门（七） 内存篇之虚拟内存技术和页面置换算法

操作系统内存知识体系大纲

上一节介绍了内存的连续分配、离散分配和段页式存储，本节将介绍内存扩充技术中的虚拟内存技术，正是虚拟内存技术的存在使得计算机能容纳远超其物理内存大小的数据量。

本节内容涉及逻辑/物理内存空间、内存连续/离散分配、页面、页表、地址转换、局部性原理等前置知识，
如果对这些内容不了解的朋友建议先阅读下面这两篇文章再来看本节内容 。

操作系统入门（五） 内存篇之地址重定位、逻辑空间、物理空间以及程序如何装入内存

操作系统入门（六） 内存篇之30张图爆肝内存连续分配管理、页式存储、段式存储和段页式存储

01 什么是虚拟内存技术

为了引出虚拟内存技术，我们需要了解传统连续分配和传统离散分配的内存策略具有以下缺点。

1、一次性：程序必须一次性全部装入内存后才能开始运行。这会造成两个问题：① 程序很大时，不能全部装入内存，导致程序无法运行；②
由于需要将程序整个装入内存，内存能容纳的进程数减少，并发度下降。

2、驻留性：一旦程序/进程被装入内存，就会一直驻留在内存中，直至进程运行结束。

事实上，进程的不同数据段和代码段在整个进程运行期间只有若干个时间段会被用到，而非每时每刻都被用到，这就导致了内存中会驻留大量的、暂时用不到的
数据段和代码段，浪费了宝贵的内存资源。

为了解决这些问题，虚拟内存技术就应运而生。

- 虚拟内存技术

虚拟内存技术是指在程序装入内存时，可以将程序即将用到的部分装入内存，暂时用不到的部分留在外存；程序运行时，当访问的信息不在内存时（缺页），操作系统将这些信息从外存调入内存，使得程序得以继续运行。当数据调入内存时，如果内存空间不够，操作系统会将内存中其他暂时用不到的信息换出到外存。而之所以可以这样做是因为程序运行
遵循局部性原理 。

在操作系统的换入换出下，看起来似乎有一个比实际内存大得多的内存空间可以容纳得下这些进程，因此叫虚拟内存。实际的物理内存大小没有变，只是在逻辑上对内存进行了扩充。

虚拟内存的特征如下：

1、多次性：一个进程可以分多次装入内存，而非一次性装入；

2、对换性：进程无需一直常驻内存，允许代码段和数据段在进程进入运行态时换入，进入就绪态和阻塞态时换出；

3、虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量大于实际内存容量，能够分配给更多进程。

连续分配策略要求一个进程必须被分配连续的内存空间，这意味着进程无法分多次调入内存，必须一次性全部调入内存，因此连续分配技术很难使用虚拟内存技术，或者说使用了虚拟内存技术，就很难做到连续分配内存空间给进程。
因此虚拟内存的实现需要建立在离散分配管理的基础上 。

例如一个进程A会占4M空间，操作实行连续分配和虚拟内存技术，允许该进程分多次装入，第一次装入1M，在物理内存的范围是
4096~5120。随着时间推移，0~4096和
5120~+∞的内存空间可能被其他进程占用。进程A第二次再调入1M到内存中，后面进程A前面的1M和后面的1M在物理内存空间就不是连续的。

除非在第二次调入进程A的部分时，将第一次调入的部分挪到更大的内存空间，再在后面把第二次调入的部分接到第一次调入的内存单元之后。但将进程的内存块拷贝需要消耗大量CPU时间，这是不值得的。

基本的分页存储、分段存储和段页式存储结合虚拟内存技术，演变成了现在的请求分页存储、请求分段存储和请求段页式存储。

在请求分页存储中，当访问的内存页不在内存时，操作系统将所需页面从外存调入内存，该过程称为 请求调页
；当内存空间不够时，操作系统将内存中暂时用不到的内存页数据换出到外存，该过程称为 页面置换 ；

- 请求分页管理

请求分页管理是在基本的段页式存储的基础上增加了 请求调页（换入） 和 页面置换（换出） 这两个功能。

要实现 请求调页和页面置换 需要考虑以下问题：

1、操作系统请求一个页面前要知道该页面是否已经在内存中，如果已存在则无需再到外存中读取；

2、如果不在，那么操作系统就需要查询该页面的外存地址是多少；

3、内存不足时，操作系统要选择换出哪些页面；

4、要换出的页面是否被修改过，如果被修改过则该页面需要写回外存，覆盖更新外存的页面；如果没被修改过，则内存的该页面可以被直接覆盖，无需更新对应的外存页；

为了实现上述4个点，操作系统在页表增加了状态位、外存地址、修改位 和 访问次数 这4个字段。

在请求分页系统中，每当要访问的页面不在内存时，就会产生一个 缺页中断 ，然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，被放入到阻塞队列，调页完成后再将进程唤醒，放回就绪队列。

如果内存中有空闲（内存）块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存中被修改过，则要将其写回外存。未修改过的页面不用写回外存。

因此，请求分页管理比基本分页管理的地址变换机构多了3个步骤：

请求调页（缺页时发生）；

页面置换（调入页面但内存不足时发生）；

修改页表；

注意：

1、一条CPU指令执行可能会引发多次缺页中断，如：copy A to B 这条指令将逻辑地址A中的数据复制到
逻辑地址B，而A、B属于不同的页面，则有可能产生两次缺页中断。

2、快表中的表项对应的页面一定是内存中存在的页面，页面换出外存则快表中对应表项也要删除，否则会访问到错误页面。

3、访问页面导致的页表项修改（如修改位置为1，访问次数+1）时，只需改动快表中的表项，只有当快表表项删除时才写回内存的页表中，这样可以减少访问内存的次数。但页面调入内存时既需要修改快表也要修改慢表表项。

4、只有执行写指令才需要修改“修改位”。

5、换入换出页面都需要启动慢速的磁盘IO操作，如果换出换出太频繁会严重影响进程执行效率，也会导致CPU频繁切换进程，把CPU时间浪费在进程切换上。

02 页面置换算法

页面置换算法决定内存不足时把内存中的哪些页面换出。因缺页导致的页面换入换出会发生磁盘IO，频繁的缺页就会导致频繁的磁盘IO以及进程频繁切换，因此一个好的页面置换算法应该追求更少的缺页率。

此外，缺页时未必发生页面置换，若还有可用的空闲内存块（也就是剩余内存充足的情况下）， 就不用进行页面置换。

下面介绍几种常见的页面置换算法。

- 最佳置换算法（OPT）

每次选择淘汰的页面是最长时间内不被访问的页面，这样可以保证最低的缺页率。

最佳置换算法无法实现，因为系统无法预判进程执行过程中会访问哪些页面，以及访问的顺序，系统只能知道当前指令要访问那个页面。

虽然该算法无法实现，但是可以作为其他算法的标准，其他算法的缺页率约接近OPT算法，就说明该算法性能越好，越接近完美。

- 先进先出置换算法（FIFO）

将调入内存的页面根据调入顺序排成一个队列，需要换出页面时选择队头页面（即最早换入到内存的页）即可。队列的最大长度取决于系统为进程分配了多少个内存块。

FIFO可能会出现Belady异常，即当系统为进程分配的内存块数增大时，缺页次数不减反增的异常现象。

该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，该算法的性能较差。

- 最近最少未使用算法（LRU）

每次淘汰的页面是最近最久未使用的页面，“最近的页面”是指当前仍在内存中的页面。“最久”是指此时在内存中（在外存中的不算）最久未使用的页面。

LRU实现方式有2种：

A. 计数器

最简单的方法是在进程的页表加一列“最近使用时间”的字段，并且进程内部保存一个计数器s，该计数器从0开始，每一次访问页面都对计数器加1（s++），并且将s赋值给对应页号的“最近使用时间”字段。

当需要淘汰页面时，需要查询页表找到使用时间最小的页面淘汰即可。

举个例子，假设某个进程只被分配了3个内存块，一开始，该进程所有页面的计数器值为0。

访问了7，0，1号页面后，计数器分别自增了3次，每次自增后计数器都会赋值到对应页号的“最近使用时间”字段。

此时最近最久未使用的页面就是页面7。

之后再访问2号页面，系统就会遍历页表查到7号的最近使用时间最早，因此将7换出，并更新2号页项的使用时间为4。

该方法每次淘汰页面时都要查询整个页表，找到在使用时间最小（即最早）的页面进行淘汰。

B.使用哈希链表

使用哈希链表的情况下，操作系统会将进程的所有页面组织成哈希链表（哈希表+双向链表）这种数据结构。使用哈希链表实现LRU算法可以做到对页面的查询（get）以及页面的换入换出（put）达到O(1)的复杂度。

由于涉及到哈希表和双向链表等于数据结构相关的知识，因此本节中不再赘述，感兴趣的朋友可以查看我个人网站中LRU算法的哈希链表实现。

操作系统如何管理内存——哈希链表和LRU算法:

_https://www.zbpblog.com/blog-325.html_

- 最不经常使用算法（LFU）

LFU算法是指优先淘汰内存中使用次数最少的页面。

LRU（最近最少使用算法） 和 LFU（最不经常使用算法）的区别在于：

LRU是优先淘汰内存中最久没有使用过的数据， 淘汰依据是某个数据距离上次被访问的时间有多久 ；

LFU是优先淘汰内存中使用次数最少的数据， 淘汰依据是某个数据被使用的频率或次数 。

对该算法的具体实现感兴趣的朋友可以查看我个人网站中LFU算法链接（LFU的实现比LRU更复杂）。

操作系统如何管理内存——LFU算法:

_https://zbpblog.com/blog-326.html_

PS：抛开和内存的知识不说，LRU 和 LFU也经常会被作为面试数据结构与算法知识的考点。

- 时钟置换算法（CLOCK）

时钟置换算法的理念是优先换出内存中未访问的页中最早进入内存的页，该算法和LRU算法的理念极为相似，都是先换出内存中最久未访问的页。

具体实现如下：每个页面在页表项中有一个访问位字段表示该页面最近是否有被访问过。内存中的页面链接成 一个循环队列，指针p指向当前访问的页的下一个页。

当某页被访问时，其访问位字段置为1。

当需要淘汰一个页面时，检查指针p指向的页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，指针p继续检查下一个页面，若第一轮扫描中，所有页面都是1，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK
算法选择一个淘汰页面最多会经过两轮扫描）。

**

和LRU不同的是，clock算法使用了一个循环队列，不会改变队列中节点的位置，但是会更新节点的访问位。时钟算法又称为 最近未使用算法（NRU） 。

- 页面缓冲算法（PB，page buffering)

该算法是在FIFO算法的基础上，区分内存中修改过和未修改过的页面，优先置换未修改过的页面。

该算法维护两个链表来管理某进程所有在内存中的页，一个是修改页链表（保存内存中被修改过的页），一个是非修改页链表（保存内存中未被修改过的页）。

假设现在有一个页面X要被换入到内存中，PB算法下页面置换的过程如下。

a. 当某进程内存不足且发生缺页时，把非修改页链表的头节点弹出（假设弹出的页面叫做页面A），该页面A作为被置换页面（该过程遵循FIFO）。

被换入的页面X要被链入到非修改页链表 或者 修改页链表。到底被链入哪个链表取决于页面X是因读访问被换入还是因为写访问被换入。

被读访问则链入非修改页链表末尾，被写访问则链入修改页链表末尾。

虽然页面A被换出，但由于它没被修改过，因此A不会写回到磁盘，而是直接被覆盖。

b.
当非修改页链表中有页面被修改，则该页节点会放入到修改页链表末尾。当修改页达到一定数量时，系统会一次性将他们一起写回磁盘（可以异步操作），从而减少磁盘IO请求次数（一次IO请求写回多个页）。

写回磁盘后，系统将修改页链表的节点统统链入到非修改页链表尾部。

所以，发生缺页时只需读磁盘，无需写回磁盘，进程可以尽快的重新启动。这两个链表充当了页面缓存的作用。页面缓冲算法也是一种节省磁盘IO请求的理念。

03 页面分配策略

- 驻留集

驻留集是操作系统分配给一个进程的物理块集合。通俗的来说就是操作系统会分配多大的实际内存给某进程。

考虑一个极端情况，若某进程共有100个页面那么大，则该进程的驻留集大小为100时，进程可以全部放入物理内存，该进程运行期间不会发生缺页。若驻留集大小为1，则表示进程只有1个页面能放入到内存，其他99个页面要放到外存，那么进程运行期间必定会极频繁地缺页。

若驻留集太小，会导致缺页频繁（又称为内存抖动），系统要花大量的时间来处理缺页，实际用于进程执行的时间很少；

驻留集太大，又会导致多道程序并发度下降（因为能装入内存的进程数量少了），内存利用率降低。

因此系统为进程分配多少物理内存，一个合适的驻留集有多大决定了进程的运行效率，这也是页面分配策略要做的事情。

- 页面分配策略

页面分配策略分为 固定分配 和 可变分配 两种。

固定分配：操作系统在进程装入内存运行前为进程分配数量固定的物理块，并且在该进程运行过程中不变。即驻留集大小不可变。

可变分配：操作系统在进程装入时分配一定数量的物理块，在进程运行期间根据该进程缺页率适当增加或较少分配给它的内存。即驻留集大小可变。

在内存不足的情况下，为了换入本进程的页面而换出其他进程的页面的行为称为全局置换，反之称为局部置换。按这个原则来分，页面分配策略也可以分为全局置换和局部置换两种。

局部置换：发生缺页时，只能选本进程自己的物理块进行置换。

全局置换：发生缺页时，可以将操作系统保留的空闲物理块分配给缺页进程，也可以将其他进程持有的物理块换出到外存，然后分配给缺页进程。

PS：全局置换下，操作系统会保持一个空闲物理块队列，当一个进程用完了分配给自己的物理块而导致缺页时，系统先将队列中的空闲块分配给缺页进程。当队列中的空闲物理块用完之后，才会选择其他进程未锁定的页面换出，然后腾出来的页再分配给缺页进程。但这么一来会导致其他进程的缺页率增加。

按照 可变/固定分配 和 局部/全局置换 这两个维度，页面置换策略可以组合成下面3种情况。

- 页面调入的时机

页面调入的时机有两个：

进程初次装入内存时需要分配多个物理块给进程马上会用到的代码段和数据段；

运行期间缺页时调入页面，该情况下每次只能调入一页，IO开销较大。

运行之前进程有关的代码和数据全部放在磁盘的文件区，因此第一次调入会从文件区调入到内存。运行过程中的页面换入换出则发生在内存和磁盘的对换区之间。

- 内存抖动

系统中刚换出的页面马上换入内存，刚换入的页面又马上换出到外存， 这种内存页面频繁缺页和换入换出的现象称为内存抖动 。

产生抖动的原因是进程经常访问的那些页面的数量高于进程可用的物理块数（驻留集不够）。这可能是因为操作系统的页面分配策略不合理导致的，也可能是因为系统投入运行的程序数量太多，内存分给每个进程的内存块不足导致的。

产生抖动的后果是CPU时间消耗在页面对换上，而非进程运行上，导致进程运行效率降低。

下面是CPU利用率和多道程序度（数量）的关系：

内存抖动可能引发恶性循环，因为操作系统监控到CPU利用率降低就会想继续把更多进程投入作业以提高CPU利用率，结果导致情况恶化。

如何避免和控制抖动：

1.挂起优先级低的进程，或者大进程，或者缺页率高的进程（相当于减少作业数量），腾出内存空间供剩余的抖动进程使用。

2.监控每个进程的缺页率，按进程缺页率决定和改变分配的内存块数量，缺页率高的进程系统应该分配给这个进程更大的驻留集。

3.使用工作集策略。

- 工作集

为了让系统分配一个合适大小的驻留集给进程，科学家们提出了工作集的概念。工作集是指某进程运行过程中，
操作系统划出一个大小为n的固定窗口，窗口内是该进程最近访问的n个页面，n个页面中的不重复页面就是工作集 。

一个进程被分配的驻留集大小应大于等于工作集大小（而且该过程是动态的，因为工作集大小也会随时间变化而变化），使得工作集内的页面总是留存在内存中（CPU总能在内存中命中工作集页面），从而有效避免进程频繁缺页。

例如如下图所示，某个进程运行到正在访问第23个页面时，它的工作集为
24,15,18,23，工作集的大小为4，那么系统应该将分配给该进程的内存块（驻留集）控制在4或4以上。

假设运行了一段时间后，该进程运行到如下图中17号页面，此时它的工作集为
18,24,17，工作集大小为3，那么系统应该将分配给该进程的内存块（驻留集）控制在3或3以上。

如果某一时刻，进程的工作集大小越小，说明该段时间内进程正在集中的访问少数的几个页，即说明进程在该段时间内的 局部性越强 。