|
最近最久未使用算法（Least Recently Used，LRU）
|
|
|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 存储管理 > 虚拟存储技术（程序局部性原理、虚拟页式存储管理、页面置换算法等） > 虚拟存储管理 > 页面置换算法 >
|
|
考试要求：掌握
相关知识点：5个
|
|
|
|
|
最近最久未使用算法的基本思路是：当一个缺页中断发生时，从内存中选择最近最久没有被使用的那个页面，把它淘汰出局。LRU算法实质上是对最优页面置换算法的一个近似，它的理论依据就是程序的局部性原理。也就是说，如果在最近一小段时间内，某些页面被频繁地访问，那么在将来的一小段时间内，这些页面可能会再次被频繁地访问。反之，如果在过去一段时间内，某些页面长时间没有被访问，那么在将来，它们还可能会长时间得不到访问。OPT算法寻找的是将来长时间内得不到访问的那个页面，而LRU算法寻找的是过去长时间内没有被访问的那个页面。
|
|
|
|
LRU算法需要记录各个页面在使用时间上的先后顺序，因此系统的开销比较大。在具体实现上，主要有两种方法。
|
|
|
|
.链表法：由系统来维护一个页面链表，把最近刚刚使用过的页面作为首结点，把最久没有使用的页面作为尾结点。在每一次访问内存的时候，找到相应的逻辑页面，把它从链表中摘下来，移动到链表的开头，成为新的首结点。然后，当发生缺页中断的时候，总是淘汰链表末尾的那个页面，因为它就是最久未使用的。
|
|
|
|
.栈方法：由系统来设置一个页面栈，每当访问一个逻辑页面时，就把相应的页面号压入到栈顶，然后考察栈内是否有与之相同的页面号，如果有就把它抽出来。当需要淘汰一个页面时，总是选择栈底的页面，因为它就是最久未使用的。
|
|
|
