章节索引 :

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,还有时钟置换算法,候选人可以自行了解。