08 操作系统内存分页机制之最优页面置换算法
最优页面置换算法
- 局部页面置换算法
- 全局页面置换算法
最优页面置换算法的功能与目标
- 功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。
- 目标：尽可能地减少页面的换进换出次数（即缺页中断的次数），因为硬盘的读写比内存的读写要慢一至两个数量级以上。具体来说，把未来不再使用的活着短期内较少使用的页面换出，通常只能在局部性原理的指导下依据过去的统计数据来进行预测。
页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程。实现的方法是：在页表中添加锁定标志位(lock bit).
基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长的时间，从中选择等待时间最长的那个物理页面，作为被置换的页面。这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会被再次访问。
- 上述算法思路可以用作其他算法的性能评价依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法），可以知晓在最优算法下，产生的缺页次数是多少，然后作为其他算法的一个参考标准。
先进先出算法（First-in First-out,FIFO）：
基本思路：选择在内存中驻留时间最长的页面并淘汰。具体来说，系统维护这一个链表，记录了所有位于内存当中逻辑页面。从链表的排列顺序来看，链首页的驻留时间最长，链尾页的驻留时间最短。当发生一次缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。
缺点：性能较差，调出的页面有可能是经常需要访问的页面，并且有 Belady现象（给程序的运行空间越大，产生缺页中断的次数越多），FIFO算法很少单独使用。
提示：为了更好的理解知识点，博主在微信公众号中将操作系统知识进行了重新排版和插入图片。感兴趣的朋友可以扫码进行关注。