操作系统基础41-LRU页面置换

2021-01-06 11:53·重学IT的老猫

如果最优算法不可行，那么最优算法的近似或许成为可能。FIFO和最优页面置换(OPT)算法的关键区别在于，除了在时间上向后或向前看之外，FIFO算法使用的是页面调入内存的时间，OPT算法使用的是页面将来使用的时间。如果我们使用最近的过去作为不远将来的近似，那么可以置换最长时间没有使用的页。这种方法称为最近最少使用(LRU)算法。 LRU置换将每个页面与它的上次使用的时间关联起来。当需要置换页面时，LRU选择最长时间没有使用的页面。这种策略可当作在时间上向后看而不是向前看的最优页面置换算法。

仍然假设有3个帧并且引用串为：

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

LRU页面置换算法

将 LRU置换应用于样例引用串的结果，如上图所示。LRU算法产生12次缺页错误。注意，头5个缺页错误与最优置换一样。然而，当页面4的引用出现时，由于在内存的3个帧中，页面2最近最少使用，因此，LRU算法置换页面2，而并不知道页面2即将要用。接着，当页面2出错时，LRU算法置换页面3，因为位于内存的3个页中，页面3最近最少使用。尽管会有这些问题，有12个缺页错误的LRU置换仍然要好于有15个缺页错误的 FIFO 置换。

奇怪的是，如果SR表示引用串S的倒转，那么针对S的OPT算法的缺页错误率与针对SR的OPT算法的缺页错误率是相同的。类似地，针对S的LRU算法的缺页错误率与针对SR的LRU算法的缺页错误率相同。

LRU策略通常用作页面置换算法，并被认为是不错的策略。它的主要问题是如何实现LRU置换。LRU页面置换算法可能需要重要的硬件辅助。它的问题是，确定由上次使用时间定义的帧的顺序。两个实现是可行的。第一种方法是使用计数器：在最简单的情况下，为每个页表条目关联一个使用时间域，并为CPU 添加一个逻辑时钟或计数器。每次内存引用都会递增时钟。每当进行页面引用时，时钟寄存器的内容会复制到相应页面的页表条目的使用时间域。这样，我们总是有每个页面的最后引用的“时间”，我们置换具有最小时间的页面。这种方案需要搜索页表以查找LRU页面，而且每次内存访问都要写到内存（到页表的使用时间域）。当页表更改时（由于CPU调度），还必须保留时间。时钟溢出也要考虑。实现LRU置换的另一种方法是采用页码堆栈。每当页面被引用时，它就从堆栈中移除并放在顶部。这样，最近使用的页面总是在堆栈的顶部，最近最少使用的页面总是在底部（如下图）。因为必须从堆栈的中间删除条目，所以最好通过使用具有首指针和尾指针的双向链表来实现这种方法。

采用堆栈记录最近页面引用

这样，删除一个页面并放在堆栈顶部，在最坏情况下需要改变6个指针。虽说每次更新有点费时，但是置换不需要搜索；指针指向堆栈的底部，这是LRU页面。这种方法特别适用于LRU置换的软件或微代码实现。像最优置换一样，LRU置换没有Belady异常。这两个都属于同一类算法，称为堆栈算法，都绝不可能有Belady异常。堆栈算法可以证明，帧数为w的内存页面集合是帧数为n+1的内存页面集合的子集。对于LRU置换，内存中的页面集合为最近引用的n个页面。如果帧数增加，那么这n个页面仍然是最近被引用的，因此仍然在内存中。注意，除了标准的TLB寄存器没有其他辅助硬件，这两种LRU实现都是不可能的。每次内存引用，都应更新时钟域或堆栈。如果每次引用都釆用中断以便允许软件更新这些数据结构，那么它会使内存引用至少慢10倍，进而使用户进程运行慢10倍。很少有系统可以容忍这种级别的内存管理开销。

参考：《操作系统概念》