文档介绍：目录
摘要 2
1、 关于页面置换算法的一些基本概念及思想 2
2、 页面置换算法的介绍 3
(FIFO)算法 3
2. 2最近最少使用页面置换(LRU)算法 4
2. 3最佳(Optimal )置换算用FIFO算法时进行了 12次页面置换。
引用率
70120304230321201701
7
7
7
2
2
2
4
4
4
0
0
0
7
7
7
0
0
0
3
3
3
2
2
2
1
1
1
0
0
1
1
1
0
0
0
3
3
3
2
2
2
1
图1利用FIFO置换算法时的置换图
2. 2最近最少使用页面置换(LRU)算法
最近最少使用(1east recently used，LRU)算法的基本思想是：依据物理 块中最近使用页面情况预测未来使用情况。
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内 存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用
（LRU ）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于 无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来” 的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋 予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其
t值最大的，即最近最久未使用的 页面予以淘汰。
利用LRU算法对上例进行页面置换算法的结果如图 2所示。当进程第一次 对页面2进行访问时，由于页面7是最近最久未访问的，故将它置换出去。当 进程第一次对页面3进行访问时，第1页成为最近最久未使用的页，将它换出。 根据各页以前的使用情况来判断，页面过去和未来的走向之间并无必然的关系。
引用率 70120304230321201701
7
7
7
2
2
4
4
4
0
1
1
1
0
0
0
0
0
0
3
3
3
0
0
1
1
3
3
2
2
2
2
2
7
页框
图2利用LRU置换算法时的置换图
选择最近最少使用的页面进行置换。即置换最长时间未被使用的页面。根 ，在将来被访问 的可能性会 很通过仿真实验结果以及对更多的数据进行测试的结果分析和比 较，得出如下结论：
（Optimal）置换算法
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择 的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访 问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目 前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内 不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。现 举例说明如下(图3)。
进程运行时，先将前三个页面装入内存。以后，当进程要访问页面 2时，
将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。这 是因为页面0将作为第