当缺页中断发生时，当你有很多内存时，可以从空闲页链表中取出一个空闲页映射到虚拟页。当内存不足时，会发生页面置换。由于访问磁盘的时间比访问内存的时间慢10万倍（磁盘时间：10ms，内存时间：100ns）,哪怕SSD也就只有普通磁盘的10倍速度以上。平均访问时间 = 访问RAM的时间+ 丢失率*访问DISK时间，而访问磁盘时间为内存时间的几万倍，所以降低丢失率，哪怕很小的比重，都对平均访问时间有个很大的提升。所以一个好的页面置换算法尤为重要。
一个比较理想的算法应该是，要置换出去的页面，最远的讲来才会用到的页面。但是因为无法预测未来所以我们的算法应该尽量往这个算法身上去靠拢接近这个算法的效率。
现在想引入的置换是LRU，这个算法的原来通过过去的行为来预测未来，意思就是过去很少用到的页面，讲来也很少用到，这个算法的根据就是“局部性原则”，如何量化“很少使用”这个概率，可以基于使用频率或者最远使用时间。所以就诞生了2中算法，LFU（Least-Frequently-Used）以及LRU（Least-RecentlyUsed ）算法。
可以观察图得出随着cache大小足够容纳所需要的内存时，就不会发生页面置换，不论哪个算法都是100%Hit的，但是其他的情况时，LRU时最接近理想算法（OPT）的。由于上面的平均访问时间的公式我们可以知道，哪怕稍微一点点的提升命中率都是对平均访问时间的提升都是巨大的。
也有些程序运行并不是按照局部性原则运行的，比如重复遍历一个数组，这个完全违法局部性原则，所以OPT类的算法反而性能最差。这个也说明了任何一种策略都是一定的适用场景的。
如何实现LRU
上述分析过了LRU的优劣势，现在谈谈如何实现LRU。如果要完美的实现LRU，必须要再每次内存访问的时候（指令获取，读以及写）都要把当前页移动到链表的头部来。这个做法毫无疑问的会消耗很大的性能。一种方式是获取硬件的某种支持，当要给一个物理页被访问时，会再某个存储再地方打上内存的标记。然后需要进行淘汰时，遍历下查找最晚访问的页面。这个遍历过程时很消耗性能的，尤其页面总数很大的时候。所以这两个方法都不合适。
很难实现准确的LRU算法，近似的LRU来替代，而且能解决掉LRU的性能热点问题，现代操作系统中也基本都是采用这个方法。这种想法需要一些硬件的支持，需要一些bit来表示，这个页面是否访问过，当这个物理页被访问时，这个use bit会标记1，清除为0的任务就交给操作系统。假设所有的物理页的使用位都被安排再一个环形的链表中，操作系统会周期性的清除use bit 从1到0，当发生需要页面置换时的场景时，如果遇到的下个页面如果不是0的话，也会按照逆时针方向去清除use bit位，直到遇到use bit为0.
考虑dirty位
当页面内容被修改（dirty）时，如果发生页面置换时，需要把页面内容写入磁盘，写入磁盘的速度是很慢的，所以有的系统会优先考虑没被修改的页面来置换。
其他置换策略
当然使用页表项里的use bit来实现LRU，并不是唯一的近似方法，还有比如多级链表等等方式。
手机操作系统的虚拟页面置换策略
手机操作系统IOS或者android系统，对延迟要求很高的，如果发生页面置换，一瞬间会有很大延迟。所以手机系统，再内存低于一定阀值时，会通知正在运行的系统去释放内存，如果释放的内存不够，就会直接终止内存占用高的应用程序，来满足系统的内存需求。而传统型的操作系统需要应用的面很广，所以需要做的满足的场景要广泛，不像手机操作系统，延迟性的高低直接带来体验的好差，所以延迟是手机系统设计中非常注重的一点。
参考资料
http://pages.cs.wisc.edu/~remzi/OSTEP/vm-beyondphys-policy.pdf
https://www.multicians.org/paging-experiment.pdf
网友评论