Question

在一个请求分页系统中，假定系统为某进程分配了3个物理块，并考虑有以下的页面引用顺序：1、0、7、1、0、2

在一个请求分页系统中，假定系统为某进程分配了3个物理块，并考虑有以下的页面引用顺序：1、0、7、1、0、2、3、0、3、0、2、1、0、7请分别采用OPTIMAL、FIFO、LRU、LFU四种页面置换算法，（1）画出转换图并求出各自的缺页数和缺页率，（2）在这四种算法中哪种算法最优？为什么？
急！急！急！！！

Answer 1

OPTIMAL：
（1）1， ， （2）1，0，（3）1，0，7（4）1，0，7访问1（5）1，0，7访问0（6）1，0，2访问2替换7（7）3，0，2访问3替换1（8）3，0，2访问0（9）3，0，2访问3（10）3，0，2访问0（11）3，0，2访问2（12）1，0，2访问1替换3（13）1，0，2访问0（14）1，0，7访问7替换2
缺页率：7/14

FIFO：
（1）1， ， （2）1，0，（3）1，0，7（4）1，0，7访问1（5）1，0，7访问0（6）2，0，7访问2替换1（7）2，3，7访问3替换0（8）2，3，0访问0替换7（9）2，3，0访问3（10）2，3，0访问0（11）2，3，0访问2（12）1，3，0访问1替换2（13）1，3，0访问0（14）1，7，0访问7替换3
缺页率：8/14

LRU：
（1）1， ， （2）1，0，（3）1，0，7（4）1，0，7访问1（5）1，0，7访问0（6）1，0，2访问2替换7（7）3，0，2访问3替换1（8）3，0，2访问0（9）3，0，2访问3（10）3，0，2访问0（11）3，0，2访问2（12）1，0，2访问1替换3（13）1，0，2访问0（14）1，0，7访问7替换2
缺页率：7/14

LFU：
（1）1， ， （2）1，0，（3）1，0，7（4）1，0，7访问1（5）1，0，7访问0（6）1，0，2访问2替换7（7）3，0，2访问3替换1（8）3，0，2访问0（9）3，0，2访问3（10）3，0，2访问0（11）3，0，2访问2（12）1，0，2访问1替换3（13）1，0，2访问0（14）1，0，7访问7替换2
缺页率：7/14

总结：就本题而言，OPT、LRU、LFU三种算法的缺页率相同，且比FIFO要小；但是就一般情况来说，OPT的缺页率最低，也就是理想化的缺页率，即缺页率的最低值，FIFO缺页率相对LRU、LFU要高，而LRU、LFU的缺页率则相对较低，在某种情况下可能会达到OPT的低缺页率（即本题），也可能会达到FIFO的高缺页率。

Answer 2

Answer 3

根据算法的步骤做就可以了