LRU/最佳/FIFO页面置换算法

一.先了解一下几种算法的定义：

1. 最佳(Optimal)置换算法：　
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。
2. 先进先出(FIFO)页面置换算法：
FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
3. LRU(Least Recently Used)置换算法：
最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。

二.根据例题进一步了解几种算法：

1、题目：
在一个请求分页系统中，采用LRU/最佳/FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果
2、计算过程：

LRU：
M=3时缺页次数10，缺页率5/6；
M=4时缺页次数8，缺页率2/3；

*注：个人理解的LRU置换算法最早调入的数并且最近没有被使用，最先换出去。可能这么理解不是很准确。

最佳：
M=3时缺页次数7，缺页率7/12；
M=4时缺页次数6，缺页率1/2；

*注：个人理解的最佳置换算法：最先替换掉，在未来一段时间内不会被用到的数。可能这么理解不是很准确。

FIFO：
M=3时缺页次数9，缺页率3/4；
M=4时缺页次数10，缺页率5/6；

*注：个人理解的最佳置换算法：最先进来的最早被替换掉，先进先出。可能这么理解不是很准确。

注：如果写的有什么不对的还请指正出来。
定义以及题目（稍微有点改动，多添加了两种算法）来自操作系统课本。