这个问题是在一个请求分页系统中，使用不同的页面置换算法fifo、lru和opt，假如有一个作业的页面走向为1、2、3、4、1、3、4、2、5、2、4、1，物理块为4，请问fifo算法与lru算法的表格与缺页率

先来解释一下什么是页面置换算法。在操作系统中，为了提高内存利用率，通常会将内存分为若干个大小相同的页框，每个进程都有自己的页表，页表中记录了该进程的每个虚拟页对应的物理页框号。当一个进程访问一个虚拟页时，如果这个虚拟页对应的物理页框已经分配给了该进程，则直接访问；否则就需要将该虚拟页调入内存中，并且选择一个物理页框将其占用，此时如果物理页框已经满了，则需要从中选择一个牺牲掉，以便为新的虚拟页腾出空间。这个过程就是页面置换，而选择哪个物理页框被替换掉的算法就是页面置换算法。

现在假设有一个作业的页面走向为1、2、3、4、1、3、4、2、5、2、4、1，物理块为4，下面分别来看fifo算法和lru算法的表格与缺页率。

首先是fifo算法，它的思路是按照页面调入内存的顺序进行替换，也就是说，当需要进行页面置换时，将最早调入内存的页面替换出去。下面是其表格和缺页率计算过程：

|访问页面|1|2|3|4|1|3|4|2|5|2|4|1|
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|1号框|1||||||||
|2号框|1|2|||||||
|3号框|1|2|3|||||||
|4号框|1|2|3|4|||||||
|1号框|1|2|3|4|1||||||
|2号框|1|2|3|4|1|2|||||
|3号框|1|2|3|4|1|2|3||||
|4号框|1|2|3|4|1|2|3|4|||
|5号框|5|2|3|4|1|2|3|4|5||
|2号框|5|2|3|4|1|3|2|4|5||
|4号框|5|2|3|4|1|3|2|4|5|4|
|1号框|5|2|3|4|1|3|2|4|5|4|

缺页率计算：共有12个页面，其中缺页次数为8，所以缺页率为8/12=0.67。

接下来是lru算法，它的思路是选择最近最久未使用的页面进行替换，也就是说，当需要进行页面置换时，选择最久未被访问的页面替换出去。下面是其表格和缺页率计算过程：

|访问页面|1|2|3|4|1|3|4|2|5|2|4|1|
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|1号框|1||||||||
|2号框|1|2|||||||
|3号框|1|2|3|||||||
|4号框|1|2|3|4|||||||
|1号框|1|2|3|4|||||||
|3号框|1|2|4|3|||||||
|4号框|1|2|4|3|||||||
|2号框|1|3|4|2|||||||
|5号框|1|3|4|2|5|||||
|2号框|1|3|4|5|2|||||
|4号框|1|3|2|5|4|||||
|1号框|3|2|5|4|1|||||

缺页率计算：共有12个页面，其中缺页次数为6，所以缺页率为6/12=0.5。

可以发现，lru算法的缺页率比fifo算法要低，这是因为lru算法能够更好地利用了页面的访问模式，选择了最近最久未使用的页面进行替换，所以相对来说，lru算法的性能更好。