页面置换
在内存分配页面的时候，不仅用于保存程序页面，用于I/O 的缓冲也需要消耗大量的内存，这种使用会增加内存置换算法的压力。确定多少内存给用户程序，多少内存给I/O缓冲去是个很棘手的问题，有的系统给I/O缓冲分配了固定百分比的内存，有些系统则允许用户进程和I/O子系统进行竞争所有内存。
基本概念
当用户进程在执行时，可能发生缺页错误。操作系统确定所需要页面的磁盘位置，但是却发现内存上没有空闲的帧。所有内存都在使用。这时，操作系统不能终止一个进程来释放，因此这样太不友好了。此时，它会选择交换出一个进程，以释放它在所有帧并降低多道程序。这种技术就是页面置换。
需要页面置换的情况.png
页面置换
在没有空闲帧的情况下，那么就要查找当前不在使用的一个帧，并释放它，它就是哪个牺牲帧，他被换出到交换空间，并修改它的页表。
可以看到当没有空闲帧的情况下，需要两个页面传输（一个传入，一个传出）。这种情况世界加倍了缺页错误处理时间，并增加了有效的访问时间。
为了减少置换的时间，系统提供了一个修改位。
在这种方案中，每个页面或者帧都有一个修改位，两者的关联采用硬件。每当一个页面内的任何字节被写入时，它的页面修改位会由硬件来设置，以表示该页面被修改过。
当要选择一个页面置换时，它会先看这个页面或者帧有没有被修改过，如果没有修改过就不用将它换出，直接进行换入，将它的空间覆盖。
为了实现请求调页，那么就要涉及两个重要问题，帧分配算法和页面置换算法。
FIFO 页面置换算法
在置换算法中，FIFO 是最简单的算法。
FIFO页面置换算法为每个页面记录了调用的时间。当必须置换页面是，选择最旧的页面，而不需要记录调入页面的确切时间。可以创建一个FIFO队列来管理所有的内存页面。置换的每次都是队首。
FIFO置换算法.png
FIFO页面置换算法易于理解和编程，但是它的性能并不是总是十分理想的。
最优页面置换（OPT）
最优页面置换：指的是置换最长时间不会使用的页面。
最优页面置换.png
注意看： 第五个和第6个数之间的， 0，3，0，4。 这里0刚一执行就被换出去了，这个是和下面LRU算法的区别。
这种方法会产生最低的可能缺页错误率。然而，最优置换算法难以实现，因为需要应用直到引用串的未来推算。
LRU页面置换算法
如果最优算法不可行，那么最优算法的近似或许可以。FIFO和OPT算法的关键区别在于，一个是页面调入内存的时间，一个是页面将来可能使用的时间。两者都不是最可控的。那么我们使用了最近的过去作为将来的近似，那么可以置换最长时间没有使用的页。
最近最少使用(LRU)的算法：LRU 置换将每个页面与它的上次使用的时间关联起来。
注意看两个概念： OPT的算法是最长时间不会使用，而LRU是最长时间没有使用。细细的思考，就会发现一个是未来时间，一个是过去时间。
如果还没看懂，就来看看两个图的比较。
最优页面置换.png
LRU置换算法.png
看出来区别了吗？OPT算法的在第五次置换的时候把刚执行过的0页面换出去了。这个它虽然名字是最优置换，但是不一定就是最优的解法了。
LRU算法通常被人们认为是不错的策略，也是被很多系统用到的页面置换算法。
LRU的具体实现
LRU算法可能需要硬件辅助；它的问题是：确定由上次使用时间定义的帧的顺序：
- 方案一：计数器
在简单的情况下，为每个页表条目关联一个使用的时间域，并为CPU添加一个逻辑时钟。每次内存引用都会有递增时钟。每当进行页面引用的时候，时钟寄存器（硬件支持）的内容会复制到相应页表条目的时间域。然后在需要置换的时候，扫描整个页表，查找LRU页面。 -
方案二： 堆栈
每当页面被引用时，它就从堆栈中移除并放在顶部。这样最近使用的页面总会在堆栈的顶部，最近最少使用的页面总会在页面的底部。
因为会有频繁的删除和插入操作，所以最好使用双向链表来实现。
堆栈实现LRU算法.png
页面置换算法还有很多其他的变种。比如：最不经常使用（LFU），最经常使用（MFU），但是这些算法的实现时昂贵的。而且还不是最优的。
页面缓冲池
除了特定的页面置换算法外，还经常有其他的措施。比如在系统中，会保留一个空闲帧缓冲池。当出现缺页终端时，它会首先在缓冲池中读取空闲帧。这允许进程快速启动。
网友评论