页面置换算法_后端通用面试教程-慕课网

1. 前言

操作系统的核心管理逻辑可以简化为进程管理、内存管理、文件管理。之前的小节已经介绍了进程的基本概念，每个进程都有独立的地址空间，这些地址空间被分为大小相同的块，定义为页（Page）。然而物理机的内存硬件空间是有限的，举例来说，我们装配最常见的 4G 内存条，但是很多进程例如单机游戏，运行时都需要占用几个 G 的内存空间，所以就需要用到虚拟内存。

2. 页面置换算法

面试官提问： 操作系统的页面置换算法是什么？常用算法有哪些？

题目解析：

首先要明确页面置换算法是针对内存管理的算法。

页面置换算法是虚拟内存的运行机制核心，内存被分页之后，每个页都是一段连续的地址，每个进程拥有的都是一段虚拟地址，需要经过内存管理单元（Memory Management Unit，也就是 MMU）将虚拟地址转换为物理地址。

操作系统的 CPU 和内存都是稀缺资源，所以资源比较紧张，内存具有非常高的 I/O 速度，但是空间很小。硬盘具有很大的存储空间，但是 I/O 能力一般。所以操作系统综合了两者的特性，将硬盘作为内存的缓存，虚拟内存就是硬盘空间的一部分。进程运行时，操作系统访问内存空间，如果访问的页面在内存中不存在则从硬盘中将其调入，如果内存没有空闲空间，则将内存中的一段数据调出到硬盘空间。

我们介绍三种最常见的内存管理算法：LRU、FIFO、OPT 算法。

2.1 LRU 算法

LRU（Least Recently Used）即最近最少使用算法，算法的核心思想是如果在过去一段时间没有访问过的页面，在未来最近一段时间也不会访问。

算法的实现是给每个页面设置一个时间戳，记录最近一次访问的时间，如果发生缺页错误，则从所有页面中淘汰时间戳最久远的一个。

LRU 算法案例示例：

访问页面序号	5	0	2	8	0	4	8
物理块 1	5	5	5	8	8	8	8
物理块 2		0	0	0	0	0	0
物理块 3			2	2	2	4	4
是否发生缺页	是	是	是	是	否	是	否

对于第 4 次访问页面时，因为所有物理块都有页面，所以发生缺页错误，需要替换出最近最少访问的页面，也就是序号为 5 的页面，即物理块 1 的内容被置换。

2.2 FIFO 算法

FIFO（First In First Out）即先进先出算法，也就是常见数据结构的队列模型。当物理块存储空间不够时，优先淘汰在最先进入物理块的页面，也就是驻留时间最久的页面。

FIFO 算法虽然相对简单，但是不符合操作系统的实际运行情况，因为驻留时间最久的页面，大多数情况是经常访问的页面，FIFO 算法会增加缺页错误的概率。

FIFO 算法案例示例：

访问页面序号	5	0	2	8	0	4	8
物理块 1	5	5	5	8	8	8	8
物理块 2		0	0	0	0	4	0
物理块 3			2	2	2	2	4
是否发生缺页	是	是	是	是	否	是	否

FIFO 算法相对于 LRU 的区别在于，只考虑页面的驻留时间，在第 6 次访问页面时，不会因为上次是序号 0 的页面刚进行了访问就不进行替换，因为序号 0 的页面是最早进入物理块的，所以替换为了序号为 4 的页面。

2.3 OPT 算法

OPT（Optiomal）最优页面置换算法，算法的核心思想是置换最长时间不会使用的页面，这需要预判未来的页面置换顺序，目前的操作系统无法做到对于进程未来需要使用的页面进行预测，所以算法也没有实际落地的实现。主要作用是对于已经给定的页面顺序，作为最优置换算法的比较标杆，比如对于给定的页面顺序 5 0 2 8 0 4 8 可以对比 FIFO 算法以及 OPT 算法的页面置换效率，判断 FIFO 算法是否足够高效。

访问页面序号	5	0	2	8	0	4	8	0
物理块 1	5	5	5	8	8	8	8	8
物理块 2		0	0	0	0	0	0	0
物理块 3			2	2	2	4	4	4
是否发生缺页	是	是	是	是	否	是	否	否

对于访问页面序号是 4 时，因为可以看到未来会有页面序号 8 和 0 的访问，不会有序号 2 的访问，所以置换物理块 3 中的页面序号 2。

3. 小结

页面调度的目的是尽可能少的发生缺页错误，因为发生缺页错误时需要从硬盘置换空间，所以会降低进程的执行效率。常见的页面置换算法除了本文介绍的 FIFO、LRU、OPT，还有时钟置换算法，候选人可以自行了解。