内存管理＜原理篇＞（八、页面置换）_用堆栈实现lru算法,置换过程中,置换的是那个页

8.0 页面置换

我们在上一篇已经介绍过了，如果在请求页面的时候，当前没有空闲页，操作系统必须在内存中选择一个页面将其换出内存，以便为了即将调入的页面腾出空间。

如果要换出的页面在内存中已经被修改过了，必须把它写回磁盘以更新该页面在磁盘上的副本。

如果该页面没有被修改过，那就调入的页面就可以直接覆盖。

当发生缺页中断时，怎么淘汰一个页面？

遇到一个问题有多个解的时候，我们自然就想到了算法，不同的算法导致性能不一样，所以我们就来学习一些页面置换算法。

其实在计算机系统中，这种淘汰机制是很容易碰到的，学习这个也可以为我们之后碰到问题打开思路。

这里还藏了一个问题？当需要从内存中换出某个页面时，它是否只能是缺页进程自己的页面？这个要换出的页面是否可以属于另外一个进程？？这个问题我们后面再看

下面，讨论的几种页面置换算法。为此，假设有3个帧并且页面引用的序列为：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（为啥这么长）

8.1 FIFO页面置换

又是FIFO，我记得进程调度的时候，好像也有FIFO，好像也是第一个，看来这个FIFO算法永远都是第一个。

FIFO页面置换算法为每个页面记录了调到内存的的时间，当必须置换页面时，将选择最旧的页面。

其实这个具体实现是很简单的，就是创建一个FIFO对列，来管理所有的内存页面。置换的是对列的首个页面，当需要调入页面到内存时，就将它加到对列的尾部。（之前我一直纠结，如果这个页面再次被调用，需不需要把位置调整，后来仔细看了一下，才发现FIFO不管这些，如果要管这个的话，应该是LRU算法了）

我们就用上面的例子，模拟一下FIFO算法：

这个例子举的是真长啊，首先我们有3个页帧，然后根据页面引用序列开始，一个一个按步骤调入物理页帧中。

刚开始的三个页面引用（7,0,1）都会引起缺页错误，然后到2这个页面，这时候页帧已满，所以换页，根据FIFO算法，7这个页先入队，所以把7换出去，把2换进来，紧接着是页面0，刚好这个页面在物理内存中，所以不需要换，然后到3，根据FIFO页面0是先入队的，所以换出，把3换进来，后来就一直这样循环下去。。。。。

根据图示，总共有15次缺页错误。

FIFO页面置换算法易于理解和编程，就是性能不好，你看上面吧，刚把0换出，然后下一帧就来了0，这不就是瞎搞么。

8.2 最优页面置换

我们通过FIFO算法出现的问题，我们提出了一个优化：就是选一个最长时间不会使用的页面就行淘汰。

这个算法被称为OPT或MIN。

下面我们直接看一个例子：

这个不愧是最优页面置换，确实少了一大推缺页错误。

我们继续走一下流程：

头三个（7,0,1）肯定是缺页了，然后到页面2，页面会换谁呢？明显是7，为啥，因为7到第18次才使用。然后继续0,0是在页帧中，所以不需要换页了，然后到页面3，然后这时候，页面1是到第9次才使用，所以果断换了页面1，之后就此循环。。。。

所以总体来说缺页错误是9个，比较好的算法了。

然而，这个算法是比较难以实现，毕竟我们程序是顺序执行的，怎么可能知道未来的东西。所以这个算法并没有具体使用。

8.3 LRU页面置换（最近最少使用页面算法）

8.2的最优页面置换算法的原理是向后看，观察哪个页面是最晚换入的，就把这个页面换出。

计算机是不知道后面的序列，但是计算机知道前面的序列，所以我们又来了老办法：如果我们使用最近的过去作为不远将来的近似，那么可以置换最长时间没有使用的页。这种方法称为最近最少使用算法LRU。

LRU算法就是把过去时间中最少使用的，当做未来也是最少使用的页面进来置换。

我们继续看例子：

前面3帧，是铁定缺页的，这个避免不了；然后到页面2，这时候有7,0,1三个页帧，到底换哪个？然后根据最近最少使用，是7（因为0,1刚好在前面使用了），所以置换了页面7。接下来是页面0，发现页面在，所以不需要换。然后到页面3，突然发现没有页面3，这时候又要换页了，根据LRU（也就是前面刚好有2,0）所以把1换掉，然后就一直这样换。。。。。

经过上面这一波操作，有12个缺页错误，还算是挺不错的了。

LRU是比较不错，但是它也有问题，就是实现起来有点困难。下面我们来讨论一下：

8.3.1 计数器

最简单的情况下，为每个页表条目关联一个使用时间域，并为CPU添加一个逻辑时钟或计数器。
这里我们就用计数器来模拟一下：

画这个图太累了，还是哈工大的老师聪明，选了一个少一点的来画，总体来说，左边是页面（我们一共有8个虚拟页面），右边是页面关联的一个计数器（时间戳），画这么多就是每个页面加载我们就需要改变一次时间戳，其中黄色是我们当时物理页帧中的页面，红色是缺页次数，一次缺页9次，加上前面3页必须缺，就12次，跟我们上面手动推导是一样的。

那我们就按这种方式实现？？

其实按这种方式实现是可以的，但是我们现在是操作系统，必须性能好，如果每次页面置换，都需要去遍历页帧，并且找到到最小的页帧，然后才换页，换页之后还需要更新计数器（或时间戳），还有计数器或时间戳有溢出风险（不过感觉这个还好，我们现在写软件基本都用时间戳和计数器，不过老师都这么说了，就这么说吧，哈哈哈）。这样效率会很低，这个低其实是跟CPU比较，因为我们进程加载到内存中，需要快速加载，然后进程可以快速运行，如果加载内存太久，进程就会卡。当然我们应用层代码就很多这种结构，比如最小堆红黑树等，都是实现这样的，就是由于使用的地方不一样，软件这种数据结构无法满足我们的需求。

8.3.2 堆栈

实现LRU置换的另一种方法是采用页码堆栈，每当页面被引用时，它就从堆栈中移除并放在顶部。（有点想最小堆）

实现是这样的：

过程如图所述，因为我们有3个物理页帧，所以栈的大小为3个，还有就是要保持栈顶是最近使用的页面。

详细过程：前面三帧（7,0,1）以此进栈，这个没啥问题，然后到页面2，页面2进栈，最低的页面7被弹出，然后到页面0，虽然现在页面0存在，但是也需要维护栈顶是最近使用的页面，所以页面0，被移到了栈顶，其他的元素跟着下沉，以此循环。

这种方式，是把主要工作集中在更新页面的情况，每执行一条指令，都需要调整指针的值，但是置换的时候才不需要，因为直接删除最低部的结点即可。但是这样也比较耗时，不符合操作系统的预期设定。

8.5 近似LRU页面置换

虽然LRU算法比较完美，但是实现起来其实也不算复杂，就是效率比较低，因为都要访问内存并且修改内存的数据，我们的目标还是要使用硬件寄存器，这样效率提高很多。

许多系统都通过引用位的形式提供一定的支持。每当引用一个页面时，它的页面引用位就被硬件置位，页表内的每个条目都关联着一个引用位。

近似LRU的思想：进程执行的时候，所有页面的引用位都清0，每当引用到一个页面的时候，引用位就置1，我们通过定时器去访问引用位，就可以哪些页面是使用过的，哪些是没有使用过的。这种操作就可以近似LRU。

后面可以通过几个具体算法，来学习一下。

8.5.1 额外引用位算法（8位）

这种算法会把引用位扩展到8位，这样就可以记录8个时间周期下的历史记录。

这是根据8位引用位和fifo的算法画出来的，我也不知道有没有问题，如果写个代码测试一下可能就更清楚了，不过就不写了，反正这个算法页少用。

过程：假设3帧就一个滴答，前面3帧很简单，但到页面2的时候，这时候前面3帧都是一样的，那就使用FIFO，在最前面的进行淘汰，然后就置换了2，然后页面3过来，就可以比较引用位了，0,1，2的引用位进行比较，明显是1的少，所以页面3把页面1置换了，后面也是这样。

这种算法看着感觉性能也不错，就是位数可能有限制，这个可能需要具体去跑模拟程序才知道，滴答多久选多少位，才是合理的。

8.5.2 第二次机会算法（时钟算法）

我们上面也提到了，如果两个引用位相等，还是需要FIFO出马，那我们把上面引用位是8位，缩减位一位，我们就记当前这时候是否使用，不记录历史时刻了，这就是第二次机会算法。

我们可以通过动图看到，前面3帧，因为没有缺页中断，可以直接加载，从第4帧开始，指针就需要遍历整个对列，如果遇到R=1，就清0，如果遇到R=0，就替换它，这就是第二次机会算法。

R=1的时候，会先被清0，然后再次遇到R=0的时候，才替换，所以叫第二次机会算法。

其实我画图的时候，就画的是循环对列，看图就明白，从最后一个，下一次就回到第一个，这是循环对列，所以这种算法也叫时钟算法。

8.5.3 增强型第二次机会算法

增强型引入了引用位和修改位，分别如下：

1. 当页面被访问（读或写）时设置R位
2. 当页面被写入（即修改）时设置M位

这个图想了想不太好画，那就直接介绍把。

当启动一个进程的时候，所以页面的R位，M位都置0，一旦进程需要访问那个页面的时候，就会引发一次缺页中断，并且设置R位（表示这个页面被访问了），如果随后会对这个页面进行修改，就会把M位也置位，那啥时候清除？这个就需要一个定时器，定期去检查，如果遇到R位为1的，就直接清除，如果下次再遇到R位为0，就说明这个不是最近使用的，通过这种方式来判断那个页面不是最近使用页面。

当需要置换的时候，需要通过M位来判断，是否需要写入磁盘，如果M位为0就不用写。

这种算法是比较粗糙，但是也勉强够用了。

8.5.4 快慢指针

这个在书上是没有的，是哈工大老师介绍的，也不知道是不是在linux内核中实现的？还是？

在第二次机会算法中，如果缺页很少，也就是所有页面都是R=1,包括转了几圈都是R=1,这样算法就退化成FIFO了。

解决方案是：一个快指针：专门清除R位，一个慢指针：专门用来淘汰页。

这样就可以找到最近未使用的，这个就记录一下，等到时候看看是不是这样实现的。

8.6 工作集页面置换算法

在《操作系统概念》这本书中，是没有后面两种算法的，可能这是新的页面置换算法。

通过前面的学习，我们知道，程序的运行时有局限性的，也就是说进程运行的任何阶段，都访问较少的一部分页面。所以我们把当前正在使用的页面集合称为工作集。

不少分页系统都会设法跟踪进程的工作集，以确保在进程运行之前，它的工作集就已在内存中。该方法称为工作集模型。其目的大大减少缺页中断，在进程运行前预先装入其工作集页面也被称为预先调页。

书中说了很多废话，我们这里直接上例子：

其实也不难理解，R位还是原来的R位，如果进程使用到了这个页面，这个R位就置位，如果滴答时钟经过，会把R=1清0，如果这时候R=0，就会那左边的时间来判断，当前实际时间-左边的时间（上次使用的时间），如果大于生存时间（就是我们定的一个时间内，都属于一个工作集），所以不在这个工作集中，就置换，如果小于生存时间，就记录下来，如果所有页面都小于生存时间，就拿一个最长的置换。

这个工作集页面置换，有点像LRU和时钟算法的综合。因为都记了时间戳了。

8.7 工作集时钟页面置换算法

分析了这么久了，工作集页面置换算法的缺点也知道了吧，就是需要扫描整个页表才能确定被淘汰的页面，所以我们这里要改进，改进成时钟算法（时钟算法是基于物理页帧的）。

这个图我是在时钟算法的基础上改的，其实这个工作集时钟算法和时钟算法是差不多的，只不多工作集算法是增加了一个上次使用时间，通过这个使用时间来计算出生存时间，然后根据生存时间判断是否淘汰这个页面。

跟时钟算法是一样的，需要置换页面的时间，指针会往下走，遇到R=1,时清0，遇到R=0时，就判断生存时间，如果这个页面的生存时间大于生存时间，就淘汰这个算法。

这个感觉是时钟算法的进化版，时间算法记录不了那个页面先换入的，但是这个工作集引入了时间，通过时间就很明确的知道了这个页面是啥时候引进的，有点LRU的感觉。

8.8 总结

想不到一个页面置换算法，既然有这么多东西，只要是也要跟实际应用场景相结合，不能只看理论，有时候理论行的通的，实际上行不通。

这么多页面置换算法，那操作系统最后用的是那种呢？其实我也不知道，哈哈哈，这个需要我们到源码篇，去仔细分析一下，看了这么多理论了，总要去证明一下，我们学习的这些算法有没有用。