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

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

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

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

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

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

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

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置换的另一种方法是采用页码堆栈。每当页面被引用时,它就从堆栈中移除并放在顶部。这样,最近使用的页面总是在堆栈的顶部,最近最少使用的页面总是在底部(如下图)。因为必须从堆栈的中间删除条目,所以最好通过使用具有首指针和尾指针的双向链表来实现这种方法。

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

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

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

参考:《操作系统概念》

-------------本文结束 感谢阅读-------------