操作系统--页面置换算法

我们这里只学习局部页面置换算法！

功能：当缺页中断发生时，需要调入新的页面而内存已满时，选择内存当中那个物理页面被替换
目标：尽可能减少页面的换进换出次数（即缺页中断的次数）

一、最优页面置换算法

把未来不再使用的或短期内较少使用的页面换出

最优页面置换算法，是不可能实现的，因为它是需要知道未来的，所以最优页面置换算法，只能当作页面置换算法中的一个理想标准。

我们其他的页面置换算法是通过局部性原理的指导下通过过去的数据，对未来进行预测，可以通过和最优页面置换算法进行比较，来测评其他页面置换算法的效果。

二、先进先出算法（FIFO）

基本思路：选择在内存中驻留时间最长的页面并淘汰
缺点：性能较差，调出的页面有可能是经常需要被访问的页面，并且有Belady现象。FIFO算法很少单独使用。

FIFO的实例：
注意最开始的a、b、c、d进入内存的顺序！

三、最近最久未使用算法（LRU）

基本思路：当一个缺页中断发生时，选择最久未使用的那个页面并淘汰。
特点：它是对最优页面置换算法的一个近似，其依据还是程序的局部性原理。

LRU实例：

四、时钟页面置换算法

它是一种LRU的近似，对FIFO的一种改进
实例：
产生缺页中断，我们要在存在内存里的页中选一个，放入硬盘，所以存在位肯定都是1，最开始指向page0，最先进入内存那个，然后像时钟一样依次找到每个page，若used bit=1，则将其置为0，used bit=0，则将此页放入硬盘！

五、二次机会法

在原来的clock方法中，再加入一位dirty bit，标志这个页是否写入过，写入时，此位会置1，没写过的页，硬盘和此页内容一致，所以不需要再回写到磁盘，写过的页，需要回写到磁盘，开销较大。

二次机会法，意味着有两次机会，这两次机会是给最近被写入过的页的，只要used bit和dirty bit都为0，才能被替换。