|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 存储管理 > 虚拟存储技术（程序局部性原理、虚拟页式存储管理、页面置换算法等） > 虚拟存储管理 >
|
|
考试要求：掌握
相关知识点：4个
|
|
|
|
|
如前所述，系统在处理缺页中断时，需要调入新的页面。如果此时内存已满，就要采用某种页面置换算法，从内存中选择某一个页面，把它置换出去。最简单的做法是随机地进行选择，但这显然不是一个令人满意的方法。例如，假设随机选中的是一个经常要访问的页面，当它被置换出去后，可能马上又得把它换进来，而这种换进换出是需要开销的。所以，对于一个好的页面置换算法来说，它应该尽可能地减少页面的换进换出次数，或者说，尽可能地减少缺页中断的次数，从而减少系统在这方面的开销。具体来说，它应该把那些将来不再使用的，或者短期内较少使用的页面换出去，而把那些经常要访问的页面保留下来。不过，在通常的情形下，我们不可能完全做到这一点。因此，通常的做法，就是在程序局部性原理的指导下，依据过去的统计数据来对将来进行预测。
|
|
|
|
常用的页面置换算法包括：最优页面置换算法、最近最久未使用算法、最不常用算法、先进先出算法和时钟页面置换算法。
|
|
|
|
最优页面置换算法（optimal page replacement algorithm，OPT）
|
|
|
|
最优页面置换算法的基本思路是：当一个缺页中断发生时，对于内存中的每一个逻辑页面，计算在它的下一次访问之前，还要等待多长的时间，然后从中选择等待时间最长的那个，来作为被置换的页面。从算法本身来看，这的确是一个最优算法，它能保证缺页中断的发生次数是最少的。但是，这个算法只是一种理想化的算法，在实际的系统中是无法实现的，因为操作系统无从知道，每一个页面还要等待多长的时间，才会被再次地访问。因此，该算法通常是用作其他算法的性能评价依据。
|
|
|
|
最近最久未使用算法（Least Recently Used，LRU）
|
|
|
|
最近最久未使用算法的基本思路是：当一个缺页中断发生时，从内存中选择最近最久没有被使用的那个页面，把它淘汰出局。LRU算法实质上是对最优页面置换算法的一个近似，它的理论依据就是程序的局部性原理。也就是说，如果在最近一小段时间内，某些页面被频繁地访问，那么在将来的一小段时间内，这些页面可能会再次被频繁地访问。反之，如果在过去一段时间内，某些页面长时间没有被访问，那么在将来，它们还可能会长时间得不到访问。OPT算法寻找的是将来长时间内得不到访问的那个页面，而LRU算法寻找的是过去长时间内没有被访问的那个页面。
|
|
|
|
LRU算法需要记录各个页面在使用时间上的先后顺序，因此系统的开销比较大。在具体实现上，主要有两种方法。
|
|
|
|
.链表法：由系统来维护一个页面链表，把最近刚刚使用过的页面作为首结点，把最久没有使用的页面作为尾结点。在每一次访问内存的时候，找到相应的逻辑页面，把它从链表中摘下来，移动到链表的开头，成为新的首结点。然后，当发生缺页中断的时候，总是淘汰链表末尾的那个页面，因为它就是最久未使用的。
|
|
|
|
.栈方法：由系统来设置一个页面栈，每当访问一个逻辑页面时，就把相应的页面号压入到栈顶，然后考察栈内是否有与之相同的页面号，如果有就把它抽出来。当需要淘汰一个页面时，总是选择栈底的页面，因为它就是最久未使用的。
|
|
|
|
最不常用算法（Least Frequently Used，LFU）
|
|
|
|
最不常用算法的基本思路是：当一个缺页中断发生时，选择访问次数最少的那个页面，把它淘汰出局。在具体实现上，需要对每一个页面都设置一个访问计数器。每当一个页面被访问时，就把它的计数器的值加1。然后在发生缺页中断的时候，选择计数值最小的那个页面，把它置换出去。LFU算法和LRU算法类似，都是基于程序的局部性原理，通过分析过去的访问情况来预测将来的访问情况。两者的区别在于：LRU考察的是访问的时间间隔，即对于每一个页面，从它的上一次访问到现在，经历了多长的时间。而LFU考察的是访问的频度，即对于每一个页面，在最近一段时间内，它总共被访问了多少次。
|
|
|
|
先进先出算法（First In First Out，FIFO）
|
|
|
|
先进先出算法的基本思路是：选择在内存中驻留时间最长的页面，把它淘汰出局。在具体实现上，系统会维护一个链表，里面记录了内存当中的所有页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首的页面淘汰出局，然后把新来的页面添加到链表的末尾。FIFO算法的性能比较差，因为它每次淘汰的都是驻留时间最长的页面，而这样的页面并不一定就是不受欢迎的页面，相反，可能是一些经常要访问的页面。如果现在把它们置换出去，将来可能还要把它们再换回来。
|
|
|
|
|
|
FIFO算法的缺点在于：它是根据页面的驻留时间来做出选择，而没有去考虑页面的访问情况。时钟页面置换算法对此进行了改进，把页面的访问情况也作为淘汰页面的一个依据。Clock算法需要用到页表项当中的访问位。当一个页面在内存当中的时候，如果它被访问了（不管是读操作还是写操作），那么它的访问位就会被CPU设置为1。算法的基本思路是：把各个页面组织成环形链表的形式，类似于一个时钟的表面，然后把指针指向最古老的那个页面，即最先进来的那个页面。当发生一个缺页中断的时候，考察指针所指向的那个页面。如果它的访问位的值等于0，说明这个页面的驻留时间最长，而且没有被访问过，因此理所当然地把它淘汰出局。如果访问位的值等于1，这说明这个页面的驻留时间虽然是最长的，但是在这一段时间内，它曾经被访问过了。因此，在这种情形下，就暂不淘汰这个页面，但要把它的访问位的值设置为0。然后把指针往下移动一格，去考察下一个页面。就这样一直进展下去，直到发现某一个页面，它的访问位的值等于0，因此就把它淘汰掉。
|
|
|
