©2020-2024 ioDraw All rights reserved,
Privacy Policy
继续重温操作系统系列知识，页面置换的三种常见算法为：LRU（最近最久未使用）、FIFO（先进先出）、最佳置换。
部分公司的面试会考到LRU的知识。
LRU置换算法
所谓LRU置换算法，单看字面意思较为麻烦，实际上在进行页面置换的过程中，被替换的页面块只需要按照“很久之前使用了，但最近没有使用”的规则进行选取就可以了。不需要考虑后续页面走向是否又需要读入符合上述规则的页面，因为这正是LRU的缺点。
最佳置换算法
这种算法选取被替换页面的时候，遵循以下两点
1.某个页面后续走向永远不会访问到，所以它可以直接被置换。
2.某个页面需要过很久才会访问到，优先替换它。
这种算法的优点是理论上缺页率比较低。
先进先出算法
替换规则为替换当前走向所有的物理块中那个最早进入的页面。
例题
假设存在一个走向，4，1，2，5，3，4，6，3，1，2。当分配的物理块M=5时，分别求FIFO、LRU、最佳置换算法的页面走向（假设初始时为空块）。
例题LRU解法
LRU表
走向4125346312
块14444333333
块2111144442
块322226666
块45555511
缺页√√√√√√√√√
置换√√√√√
（1）.对于LRU，首先按照顺序填好走向，并填满前面的物理块，与其他算法一样。
很显然在一开始每次都需要调入所需页面。因此，前面几次都是缺页，但没有产生置换。
（2）.开始进入置换过程。
对于接下来的走向页面3而言，块中无3说明缺页，块中已满调入3则说明需要置换。
通过观察我们可以得知最近的页面，无论是4、1、2、5，都只是调用了一次，因此我们需要替换最久未使用的4。
但有的时候并不会这么简单，那如果走向不再是4125，而是是4、1、4、5呢？有2个4，还要不要替换4？
那么答案是：则应该替换1，因为虽然4是最早入块的，但是最近4使用过，所以不再是最久未使用的。排除4后1最久未使用，5刚刚使用过。
本题走向为4、1、2、5，因此走向3的块序列为3、1、2、5.
对于接下来的走向页面4而言，因为上一次的序列为3、1、2、5很显然没有4，但又满物理块，所以既置换又缺页。
按照刚刚的示例，在前面的走向4、1、2、5、3中，很显然最久未使用的是1，所以需要替换1.
因此走向4的块序列为3、4、2、5.
对于接下来的走向6而言，最近最久未使用的是2（其实可以观察2和5的长度，在3、4、2、5中，又无重复项目，而2是最久未使用的）。所以替换2.
结果是3、4、6、5，很显然缺页6又置换2。
对于接下来的走向3而言，存在3，所以不需要置换、也不缺页。
对于1而言，最近的序列为（3、4、6、5），观察发现5和3的序列横向一样长，然而3刚刚调用过，所以需要替换5.
结果为3、4、6、1
对于接下来的走向2而言，我们发现最近的序列为（3、4、6、1），通过观察可以发现4-3-6-1走向中4最久未使用，所以替换4.
结果为3、2、6、1.
最终我们填写了整个LRU的置换表。
例题FIFO算法
走向4125346312
块14444333332
块2111144444
块322226666
块45555511
缺页√√√√√√√√√
置换√√√√√
按照先进的先被替换，雷打不动，就可以做出了，这道题答案基本上和LRU一样，就是最后一个走向有些区别。
解题时候遇到重复性的走向容易出错，规避即可。
例题最佳置换算法
页面
4
1
2
5
3
4
6
3
1
2
块1
4
4
4
4
4
4
6
块2
1
1
1
1
1
1
块3
2
2
2
2
2
块4
5
3
3
3
缺页否
√
√
√
√
√
√
置换否
√
√
对于走向3而言，我们可以看到后面的走向46312，3、2、1是最久会再次调用的，可以替换2，因为2是最后要访问的，但由于块4的5在后面是永远不会被再次调用的，所以不替换2，要替换5.
结果为4、1、2、3.
下一个走向含有4，因此不缺页也不置换。
接下来的走向6，很显然走向4的页面已经不再需要了（后续走向无4），所以替换走向4，最终结果很巧妙，完全不缺页也不置换。
以上就是三种常见的解法