页面置换算法

1. 概念¶

1.1 置换算法的概念¶

出现缺页异常，需要调入新的页面而内存已满时，置换算法会选择被置换的物理页面

设计目标

尽可能减少页面调入调出次数
把未来不再访问或短期内不访问的页面调出

页面锁定

必须常驻内存的逻辑页面
在页表中有锁定标志位

1.2 评价方法¶

可以记录进程访问内存的页面轨迹，然后进行评价。进程的地址访问用(页号，位移)表示，对页面置换来说不需要位移信息，只保留页号即可

有了记录后，模拟页面置换行为，记录产生缺页次数即可

1.3 置换算法分类¶

局部页面置换算法

分配给一个进程的物理页面数目确定，置换选择范围仅限于当前进程占用的物理页面

最优算法
先进先出算法 FIFO
最近最久未使用算法 LRU
时钟算法、最不常用算法 (LRU的近似)

全局页面置换算法

置换页面的选择范围是所有可换出的物理页面

工作集算法
缺页率算法

2. 局部置换算法¶

2.1 最优置换算法 OPT¶

置换未来最长时间不被访问的内存页，即按照下一次使用时间排序

特征: 缺页最少、最理想情况，但无法实现

可以作为置换算法的评价依据

如下图，进程有四个物理页面，6个逻辑页面，第5次访问e时缺页，换出最晚使用的d页面，之后第10次访问d缺页，一共两次缺页

2.2 先进先出 FIFO¶

选择内存驻留时间最长的页面进行替换

维护一个链表来记录进入内存先后顺序

特征

实现简单，性能较差
很少单独使用
存在Belady现象，即增加分配的物理页面，缺页数不一定减少

如下图，假设最开始四个页面进入顺序是a->b->c->d，那么产生缺页时从头到尾开始换出页面，一共产生5次缺页

2.3 最近最久未使用算法 (Least Recently Used)¶

选择最长时间没有被引用的页面进行置换，即依靠局部性

缺页时，计算每个逻辑页面的上一次访问时间

是最优置换算法的一种近似

过程如下，产生3次缺页

可能实现方法

页面链表
活动页面栈

leetcode

2.4 时钟置换算法 (Clock)¶

是LRU和FIFO的折中

对页面访问情况进行大致统计，相比LRU统计太过详细，可以降低开销

数据结构

页表项中加入访问位，描述页面在过去一段时间的访问情况
各页面组织成环形链表
指针指向最先调入的页面

缺页时，从指针处开始顺序查找未被访问的页面进行置换，扫过为1的位置访问位清0，换入后将使用位置1，指针推到下一位

如下图，前4次访问将abcd都置为1；第5次访问e时指针扫描一遍都清零，然后换出a换入e，指针下移；之后第6位b利用位改为1；第7位b改为0，换出c，指针下移到d；第8位将b置1；第9位换入c，指针到e；第10位全部清零，换出e，下移到b

改进

减少修改页的缺页处理开销，页表中加上修改位，缺页时跳过有修改的页面，对其修改如下，当使用位为0修改位为1时写回修改页，都为1时先把使用位置0

2.5 最不常用算法 (Least Frequently Used)¶

也是对LRU的简化，缺页时置换访问次数最少的页面

每个页面加一个访问计数，缺页时置换计数最小的页面

特征

开销大
开始时频发使用，以后不使用的页面很难换出
- 解决方法: 定期右移使用次数

如下图，页面右上角数字代表访问次数

Belady现象¶

采用FIFO等算法时，分配的物理页面数增加，缺页次数反而升高

原因

FIFO算法的置换特征与进程访问内存的动态特征矛盾
被置换出去的页面不一定是进程近期不会访问的

如以下情形，四个物理页面缺页次数反而更多

LRU算法没有Belady现象，理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法

LRU FIFO和Clock的比较¶

LRU依据页面的最近访问时间排序，页面进入后需要动态调整
FIFO依据页面进入内存时间排序，进入时间固定不变

LRU可以退化为FIFO，页面进入内存后没有被访问

Clock算法是LRU和FIFO的折中

Clock页面进入后不动态调整，但会做标记，缺页的时候会进行扫描

对于没有访问过的页面，三种算法一致
访问过的页面，LRU好于Clock好于FIFO

3. 全局置换算法¶

局部置换算法没有考虑进程访存的差异，全局算法要考虑给进程分配多少物理页面，有时多分配一个页面缺页次数就会有明显下降

全局置换算法: 依据进程的需求，给进程分配可变数目的物理页面

要解决的问题

进程在不同阶段的内存需求是变化的
分配给进程的内存也需要在不同阶段有所变化
全局置换算法需要确定分配给进程的物理页面数

3.1 工作集置换算法¶

OPT在全局中的一种体现

工作集 一个进程当前正在使用的逻辑页面集合可以表现为二元函数 $W(t,\Delta)$

$t$ 当前执行时刻
$\Delta$ 工作集窗口
$W(t,\Delta)$ 指当前时刻 $t$ 前的 $\Delta$ 时间窗口中所有访问页面组成的集合
$|W(t,\Delta)|$ 指工作集大小，即页面数目

如对以下页面访问顺序

2 6 1 5 7 7 7 7 5 1 6

如果 $\Delta$ 窗口长度为10，那么 $W(t,\Delta)={1,2,5,6,7}$

工作集变化情形如下

常驻集 进程实际驻留在内存当中的页面集合，用常驻集来对工作集作近似

工作集是进程在运行过程中的固有性质，常驻集取决于系统分配给进程的物理页面数目和页面置换算法

通过常驻集控制缺页率

常驻集包含工作集，缺页较少
工作集发剧烈变动，缺页较多
常驻集大小达到一定数目，缺页率不会明显下降

算法思路

换出不在工作集中的页面

有一个窗口大小 $\tau$ ，当前时刻前 $\tau$ 个内存访问的页引用是工作集

例如1时刻，过去4个窗口内的工作集就是a c d e

3.2 缺页率置换算法¶

缺页率 缺页次数/内存访问次数或缺页平均时间间隔的倒数

通过调节常驻集大小，使每个进程保持在一个合理范围，如下图所示

若缺页率过高，增加常驻集
若缺页率过低，减少常驻集

算法

访存时，设置引用位标志
缺页时，计算上次缺页时间 $t_{last}$ 到这次 $t_{current}$ 之间的间隔
- 如果缺页率低， $t_{current}-t_{last}>T$ ，置换工作集中所有在 $[t_{last}, t_{current}]$ 没有被引用的页
- 如果缺页率高， $t_{current}-t_{last} \le T$ ，增加缺失页到工作集中

如下图，窗口大小为2，在时刻4缺页时，缺页间隔大于2，所以置换出没有访问到的页面a和e；而在时刻6，间隔小于等于2，所以只进行添加

置换在缺页中断时完成

3.3 抖动和负载控制¶

抖动进程物理页面太少，不能包含工作集，造成大量缺页，频繁置换 -> 进程运行速度变慢

操作系统需要在并发和缺页率之间达到一个平衡，通过控制并发进程数来进行系统的负载均衡