之前几篇博客记录了OS内存管理的一些知识和技术，接下来将继续深入，介绍一些页面置换算法，这里包括一些我们大家都略有耳闻的算法。

置换算法

当出现缺页故障时，需要从外存调入新的页面到内存中去，而如果此时内存已满，于是就要按照一定策略置换一些物理页帧出来，这就是置换算法的目的。而置换算法的目标就是尽量减少页面的调入调出次数

页面置换算法主要可分为两大类：

1. 局部页面置换算法

置换页面的选择范围仅限于当前进程占用的物理页面内。比较有代表性的算法有最优置换算法、FIFO算法、最近最久未使用算法、时钟算法、最不常用算法

2. 全局页面置换算法

全局页面置换算法的选择范围是所有可换出的物理页，比较有代表性的算法有工作集算法、缺页率算法

1. 局部页面置换算法

所谓局部页面置换，就是说，如果OS给一个程序固定分配了5个物理页帧，当这些页帧满了后，如何进行页面置换。

---

最优置换算法（opt算法）

思路就是，当产生缺页时，计算每个逻辑页面的下一次访问时间，选择未来最长时间不访问的页面进行置换。

比如现在内存里面有a、b、c三个物理页帧，现在来了一个d页面，又知道a在未来的第3个页面后又会重新需要访问、b在未来的第2个页面后又会重新需要访问，c则是未来的第5个时间。那么这样的话，按照opt算法，我们就将c物理页面换出，将d页面放置在原来c页面的位置即可。

细心的筒子可以发现一个问题，我这里说在未来的第几个页面又会重新需要，那真的运行一个程序的时候，OS哪里可能知道未来那个页面会被重新使用 ？所以说，这是一个纯理想的算法，无法实现，只能作为置换算法的一个性能评估依据。

再举个栗子，大家可以自己在脑子里模拟一下执行过程，这里假设在0时刻，abcd四个页都已经在内存中了。紫色的圈表示在该时刻出现了缺页异常，红色的箭头表示置换的是哪个页。

FIFO算法

FIFO即First-In-First-out，先入先出算法，思想就是将那个在内存中驻留时间最长的页面进行置换。这里实现的方法可以是通过维护一个链表，按照页面的到来顺序，依次插入链表尾部，每次要置换页的时候，就对链首继续置换，新页插入到链表尾。

但是，这个算法的性能比较差，因为它不知道未来页面的到来情况（毕竟它只看到的是已经驻留的页面），有可能频繁的将一些再次会用到的页进行置换。此外，FIFO还有可能出现belady现象（变成女人??? exm??? 开个玩笑。。 ）这个现象阐述的是这样一种情况，若OS给进程分配的物理页面数量增加，缺页次数并不一定因为物理页面数量的增加而减少，反而会更多。

所以，总的来说，FIFOF很少单独使用，会配合一些其他算法使用，例如后面会讲到的时钟算法。

FIFO也来个栗子，假设在0时刻之前，abcd四个页面的到来顺序为abcd，可见，出现页面置换的次数较多。

值得注意的是，在FIFO算法中，会存在Belady现象，这个现象就是说，随着OS给每一个进程所分配的物理页数量增加，出现缺页异常的次数非但没有减少，反而增加了。

注意：这里并不是说，一直增加物理页面数量，缺页异常一直增加，这显然是不对的，假设一个进程被分配到的物理页面数量无穷大，那缺页异常肯定是0. Belady现象只是说在某一小段区间内，出现缺页异常的次数随着分配的物理页面增多而增多。

最近最久未使用算法 （Least Recently Used, LRU）

这个算法从英文的字面意思上就可以理解它在干什么了。其实还是一个模拟未来页面到来情况的思想，算是对OPT算法的一个近似，LRU算法认为，最近那个最近一直没被使用的页，在未来也最有可能不会被使用，所以将它置换出去（实际上，这也是基于我们程序有较好局部性的特征基础之上的）。

缺页时，计算内存中每个逻辑页面的上一次访问时间，置换上一次访问时间距离现在最远的那个页面（即时间最小） 。

栗子如下，假设在0时刻abcd四个页面已经驻留在内存中了。

LRU的实现方法大致有两种：

1. 基于链表的实现

OS维护一个按最近一次访问时间排序的页面链表，其中，链表首节点是最近刚刚使用过的页面，而链表尾结点是最久未使用的页面，按照上图所示例子的话，在t=5时刻之前，链表的状态如下：

每次缺页的适合，就将链表尾部的页面进行置换，并把它移到链表的首部去。t=5时刻置换页动作完成后，链表的状态如下：

2. 基于栈的实现

思路和链表的实现差不多，如下图：

时钟算法（clock）

像上面的LRU算法，性能其实是不错的，唯一的缺点就是维护链表或栈相对来说要麻烦一些，于是出现了时钟算法，它的思路是对页面的访做大致的统计，不一定是完全严格按照LRU的思路，比如，在t=1时刻的页面a和t=2时刻的页面b，时钟算法有可能第一个换页面b而不是a。

时钟算法采用了一种特殊的数据结构——环形列表，且在页表项中增加了一个访问位（还记得吗？之前的博客虚存管理中提到过，当时说这个位是为了页面置换时用的），环形列表的指针指向最先调入的页面。

算法的思想是，访问页面时，在页表项纪录页面的访问情况，缺页时，从指针出开始顺序地、循环地查找未被访问的页面进行置换。时钟算法其实是LRU和FIFO的折中。

算法实现的pseudo code如下：

while(目标页面不存在)
{if(当前指针所指的页表项的访问位为0){替换当前页；赋值当前页表项的访问位为1；}else{赋值当前指针所指的页表项的访问位为1;}指针下移一位；
}

例子如下，假设在0时刻，时钟算法的当前指针指向第一项，蓝色的那一项就是当前指针所指项：

在上图中，需要注意的是，如果存在页表项，只是其对应的访问位为0的时候，在访问该页时，只会将访问位置为1。而出现页面置换时，操作完后，指针要下移一位。

关于clock算法，还有其改进算法，称为二次机会法，由于笔者表达能力有限，这里给个视频讲解链接。 >>二次机会算法<<，其思路和clock算法是很相似的。

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

最不常用算法并不是说这个算法不常用。。。

其实，这也是对未来将出现的页面的另一种模拟。该算法认为，当前访问次数较少的页面，在未来也有较大概率不会被访问，于是，每次出现缺页异常时，选择访问次数最少的那个页面，并将之淘汰。

举例如下，上标表示该页的访问次数：

2. 全局页面置换算法

所谓全局页面置换算法，就是指OS基于多个进程之间的考虑（即全局的思想），为进程分配可变数目的物理页帧。最终目的还是为了减少出现缺页异常的数量。

---

下面介绍几个概念：

工作集（working set）

工作集指的是一个进程当前正在使用的逻辑页面的集合，可表示为一个二元函数$W(t,△)$,其中$t$是进程当前执行的时刻，$△$称为工作集窗口（working-set window），即一个定长的页面访问时间窗口。

则：
$W(t,△)$是指当前时刻t前的$△$时间窗口中的所有访问页面组成的集合。
$|W(t,△)|$是指工作集大学，即页面数量。

一般来说，进程的初始阶段，随着访问新页面的逐步建立，工作集的数量会增加，然后进程中间阶段会比较平稳，一旦又有新的页访问，工作集会产生一定波动，然后再保持平稳，整体呈以下图示状态：

常驻集

常驻集指的是在当前某个时刻，进程实际驻留在内存当中的页面集合。

常驻集和工作集的区别是，前者指在内存中的物理页，而工作集是指逻辑页。

工作集置换算法

该算法的思路是，在访存时，换出不在工作集中的页面；而在缺页时，换入缺失的页面。

如上图所示，稍加解释一下。在t=1时刻，由于缺页C，于是将之换入，在t=2时刻，由于C页面已经存在，是一次访存操作，因为工作集的窗口大小为4，所以当前的工作集为 { d , a , c } \{d,a,c\} {d,a,c}，于是需要将页面e替换出去，后面的操作同理。

缺页率置换算法（page fault frequency，PFF）

该算法中，需要记录两个时间$t_{current}和t_{last}$，分别表示当前缺页时间和上一次产生缺页异常的时间。算法思路是：

如果$t_{current}-t_{last}>T$,则置换所有在$[t_{last},t_{current}]$间没有被访问过的页

如果$t_{current}-t_{last}\le T$,则增加缺失的页到工作集中。

这里的T指的是窗口大小。

直观的一个理解是，当$t_{current}-t_{last}>T$，这说明距离上一次产生缺页异常的时间较远，即在较长一段时间内没有发生缺页异常，于是将一些自上一次发生缺页异常以来，存在于工作集中又从未被访问过的页置换出去（因为它们很有可能不再会被访问了）；而当$t_{current}-t_{last}\le T$时，这说明距离上一次产生缺页异常的时间较近，，需要把缺失的页放进来。