页面置换算法

什么是缺页

缺页就是不存在内存的页，然后放到内存里面

先进先出（FIFO）页面置换算法

1.作用

最先进来最先淘汰（即选择在内存中驻留时间最久的页面予以淘汰）。
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。

例题：
假定系统为某进程分配了3个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
解析：

先进先出页面置换算法例1解.png
① 进程最开始运行时3个物理块没有页号，所以发送缺页中断从外存调入页号4，同理，调用页号3、页号2，这时资源都已被占用。此时页框内是432。
②当运行到页号1时，页面没有页号1，故而发送缺页中断，这时就需要考虑置换掉谁。根据先进先出(FIFO)页面置换算法。页号4是最先进，则淘汰页号4。此时页框内是321。
③当运行到页号4时，此时页框内是321，没有页号4，则发送缺页中断，并淘汰掉最先进的页号3,。此时页框内是214。
④当运行到页号3时，此时页框内是214，没有页号3，则发送缺页中断，并淘汰掉最先进的页号2。此时页框内是143。
⑤依次类推。

3.优缺点：

FIFO 页面置换算法易于理解和编程。然而，它的性能并不总是十分理想。一方面，所置换的页面可以是很久以前使用过但现已不再使用的初始化模块。另一方面，所置换的页面可以包含一个被大量使用的变量，它早就初始化了，但仍在不断使用。

（LRU）置换算法

1.作用

根据页面调入内存的使用情况进行决策，把最近一段时间最久未使用的页面予以淘汰。
详述：
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。因为根据程序的局部性原理，刚刚被访问过页面，可能很快还被访问到。由于无法预测各个页面将来的使用情况，只能利用“最近的的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

2.例题1：

假定系统为某进程分配了3个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
解析：

① 进程最开始运行时3个物理块没有页号，所以发送缺页中断从外存调入页号7，同理，调用页号0、页号1，这时资源都已被占用。此时页框内是701。
② 当运行到页号2时，内存没有页号2，故发送缺页中断，这时就需要考虑置换掉谁。根据最近一段时间最久未使用（LRU）置换算法，最近一段时间最久未使用的页面予以淘汰。页号7在最近一段时间内（也就是在页号之前运行的时间里）页号7最久没被使用，所以就淘汰页号7。此时页框内是201
③ 同理，运行到页号0时，内存中已有，即命中，继续往下运行。
④ 运行到页号3：页号0刚用过，页号2页用过不久，页号1不用的时间最久，可能很快还被访问到，所以将页号1替换。此时页框内是203。
⑤ 运行到页号0：命中，继续往下运行。此时页框内仍是203。
⑥ 运行到页号4：页号0刚用过，页号3页用过不久，可能很快还被访问到，所以将页号2替换。此时页框内是403。
依次类推，最后页框内为107。

3.优缺点：

① 命中率,当存在热点数据时LRU的效率很好；但偶发性的,周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重 。
② 实现相对简单。
③ 命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

参考链接：https://www.jianshu.com/p/474dd670d483