内存页面置换算法

页面置换算法的概念

置换算法的功能和目标

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

设计目标：
1.尽可能减少页面的调入调出次数；
2.把未来不再访问或短期内不访问的页面调出。

页面锁定(frame locking)（有些页面必须在内存里面）

1.描述必须常驻内存的逻辑页面

2.操作系统的关键部分

3.要求响应速度的代码和数据

4.页表中的锁定标志位(lock bit)

置换算法的评价方法

页面置换算法分类

■ 局部页面置换算法

置换页面的选择范围仅限于当前进程占用的物理页面内

最优算法、先进先出算法、最近最久未使用算法

时钟算法、最不常用算法

■ 全局页面置换算法

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

工作集算法、缺页率算法

页面置换算法总结

最优页面置换算法(OPT, optimal)

基本思路：置换在未来最长时间不访问的页面

算法实现:

1、缺页时，计算内存中每个逻辑页面的下一次访问时间

2、选择未来最长时间不访问的页面

算法特征

1、缺页最少，是理想情况

2、实际系统中无法实现

3、无法预知每个页面在下次访问前的等待时间

4、这个算法可以作为置换算法的性能评价依据

（实际使用：在模拟器上运行某个程序，并记录每一次的页面访问情况,第二遍运行时使用最优算法）

先进先出算法（First-In First-Out, FIFO）

**基本思路：**选择在内存驻留时间最长的页面进行置换

算法实现:

1、维护一个记录所有位于内存中的逻辑页面链表

2、链表元素按驻留内存的时间排序，链首最长，链尾最短

3、出现缺页时，选择链首页面进行置换，新页面加到链尾

算法特征

1、实现简单

2、性能较差，调出的页面可能是经常访问的

3、进程分配物理页面数增加时，缺页并不一定减少(Belady现象)

4、很少单独使用

最近最久未使用算法(Least Recently Used, LRU)

基本思路：

1、选择最长时间没有被引用的页面进行置换

2、如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问

算法实现:

1、缺页时，计算内存中每个逻辑页面的上一次访问时间

2、选择上一次使用到当前时间最长的页面

算法特征

最优置换算法的一种近似

LRU算法的可能实现方法

页面链表

·系统维护一个按最近一次访问时间排序的页面链表

链表首节点是最近刚刚使用过的页面

链表尾节点是最久未使用的页面

·访问内存时，找到相应页面，并把它移到链表之首

·缺页时，置换链表尾节点的页面

活动页面栈

·访问页面时，将此页号压入栈顶，并栈内相同的页号抽出

·缺页时，置换栈底的页面

特征

·开销比较大

时钟置换算法（Clock）

基本思路：

仅对页面的访问情况进行大致统计

数据结构:

1、在页表项中增加访问位，描述页面在过去一段时间的内访问情况

2、各页面组织成环形链表

3、指针指向最先调入的页面

算法实现：

1、访问页面时，在页表项记录页面访问情况

2、缺页时，从指针处开始顺序查找未被访问的页面进行置换

算法特征：

时钟算法是LRU和FIFO的折中

时钟置换算法的实现：

■ 页面装入内存时，访问位初始化为0

■ 访问页面（读/写)时，访问位置1

■ 缺页时，从指针当前位置顺序检查环形链表

·访问位为0，则置换该页

·访问位为1，则访问位置0，并指针移动到下一个页面，直到找到可置换的页面

改进的Clock算法

基本思路：

减少修改页的缺页处理开销

算法实现：

1、在页面中增加修改位，并在访问时进行相应修改

2、缺页时，修改页面标志位，以跳过有修改的页面

最不常用算法（Least Frequently Used, LFU）

基本思路：

缺页时，置换访问次数最少的页面

算法实现：

1、每个页面设置一个访问计数（多位计数）

2、访问页面时，访问计数加1

3、缺页时，置换计数最小的页面

算法特征：

1、算法开销大

2、开始时频繁使用，但以后不使用的页面很难置换

**解决方法：**计数定期右移、衰减

LRU和LFU的区别

·LRU关注多久未访问,时间越短越好

·LFU关注访问次数，次数越多越好

Belady现象

现象：采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象

原因：

1、FIFO算法的置换特征与进程访问内存的动态特征矛盾

2、被它置换出去的页面并不一定是进程近期不会访问的

哪些置换算法没有Belady现象？

时钟(CLOCK)置换算法，最近最久未使用（LRU）算法，最佳置换算法（OPT）

时钟/改进的时钟页面置换是否有Belady现象？

没有

为什么LRU页面置换算法没有Belady现象？

对于每一时刻，下一步访问的页面我们也是已知的。当N=n+1时，如果下一步会产生缺页，说明下一步会访问的页面不在这n+1个页面中。假设这n+1个页面的集合为W，则当N=n时，内存中的页面是W的一个子集。如果一个元素都不在W中，那么也肯定不存在于W的子集中。反之如果一个元素不存在于W的子集合中，不一定不存在W中。

所以N=n+1时会出现缺页的情况，在N=n时一定缺页。N=n缺页时，N=n+1不一定缺页。所以S一定时，f关于N单调递减。

LRU一般都有栈的特性，一个N+1大小的cache很自然的就包含了大小为N的cache的内容。所以随着cache大小增加，hit rate要么不变，要么提高。

LRU、FIFO和Clock的比较

■LRU算法和FIFO本质上都是先进先出的思路

LRU依据页面的最近访问时间排序

LRU需要动态地调整顺序

FIFO依据页面进入内存的时间排序

FIFO依据页面进入内存的时间排序

■LRU可退化成FIFO

如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同

例如：给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3…

■LRU算法性能较好，但系统开销较大

■FIFO算法系统开销较小，会发生Belady现象

■Clock算法是它们的折衷

页面访问时，不动态调整页面在链表中的顺序，仅做标记

缺页时，再把它移动到链表末尾

■对于未被访问的页面，Clock和LRU算法的表现一样好

（注：和fifo也一样了，没有之前参考的信息）

■对于被访问过的页面，Clock算法不能记录准确访问顺序，而LRU算法可以

全局页面置换算法

■ 思路：全局置换算法为进程分配可变数目的物理页面

■ 全局置换算法要解决的问题

1、进程在不同阶段的内存需求是变化的

2、分配给进程的内存也需要在不同阶段有所变化

3、全局置换算法需要确定分配给进程的物理页面数

CPU利用率与并发进程数的关系

■CPU利用率与并发进程数存在相互促进和制约的关系

进程数少时，提高并发进程数，可提高CPU利用率

并发进程导致内存访问增加

并发进程的内存访问会降低了访存的局部性特征

局部性特征的下降会导致缺页率上升和CPU利用率下降

工作集

一个进程当前正在使用的逻辑页面集合，可表示为二元函数W(t,D)

·t是当前的执行时刻

D 称为工作集窗口（working-set window），即一个定长的页面访问时间窗口

W(t,D)是指在当前时刻t前的 D时间窗口中的所有访问页面所组成的集合

| W(t,D) |指工作集的大小，即页面数目

W(t,D)={时间窗内所以页面的集合}

工作集的变化

■进程开始执行后，随着访问新页面逐步建立较稳定的工作集

■当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定

■局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值

常驻集

在当前时刻，进程实际驻留在内存当中的页面集合

■工作集与常驻集的关系

工作集是进程在运行过程中固有的性质

常驻集取决于系统分配给进程的物理页面数目和页面置换算法

■缺页率与常驻集的关系

常驻集包含工作集时，缺页较少

工作集发生剧烈变动（过渡）时，缺页较多

进程常驻集大小达到一定数目后，缺页率也不会明显下降

工作集置换算法

■思路：换出不在工作集中的页面

■窗口大小τ：当前时刻前τ个内存访问的页引用是工作集，τ被称为窗口大小

■实现方法（开销也大）

·访存链表：维护窗口内的访存页面链表

·访存时，换出不在工作集的页面；更新访存链表

·缺页时，换入页面；更新访存链表

超过工作集窗口大小的页面及调出，例如a，时间4的时候已经过了窗口大小所以换出。

缺页率置换算法（PFF, Page-Fault-Frequency）

缺页率（两种表示方式）

1、缺页次数/内存访问次数

2、缺页平均时间间隔的倒数（一般使用这个）

影响缺页率的因素

页面置换算法（可控）

分配给进程的物理页面数目

页面大小

程序的编写方法（可控）

缺页率置换算法（PFF, Page-Fault-Frequency）

通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内

·若进程缺页率过高，则增加常驻集以分配更多的物理页面

·若进程缺页率过低，则减少常驻集以减少它的物理页面数

缺页率置换算法的实现

■访存时，设置引用位标志

■缺页时，计算从上次缺页时间tlast到现在tcurrent的时间间隔

如果t_current–t_last>T,则置换所有在[tlast , tcurrent ]时间内没有被引用的页(缺页率比较低，把不用的置换出去)

如果t_current–t_last≤T,则增加缺失页到工作集中

抖动和负载控制

抖动问题(thrashing)

■抖动

进程物理页面太少，不能包含工作集

造成大量缺页，频繁置换

进程运行速度变慢

■产生抖动的原因

随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升

■操作系统需在并发水平和缺页率之间达到一个平衡

选择一个适当的进程数目和进程需要的物理页面数

负载控制

■通过调节并发进程数（MPL）来进行系统负载控制

平均缺页间隔时间(MTBF) =缺页异常处理时间(PFST)：

实际上我们利用第二条竖线，缺页之后，有一个缺页出现的平均间隔和缺页处理的时间，这两个构成一个比例，如果间隔大于处理时间，cpu是能够处理的，就在Ni/o点之前，如果间隔小于处理时间，cpu基本上就满负荷的去做处理还忙不过来了， 对于这种情况就已经到了这条线的底下了