详解页式管理置换算法FIFO_LRU_OPT

由天下分享时间：2024/12/16 1:04:40 加入收藏我要投稿点赞

页式管理

OPT、LRU、FIFO置换算法详解

指令： 1,2,3,4, 2,1,5,6, 2,1,2,3, 7,6,3,2, 1,2,3,6

若内存最多容纳4个页面，则……

一、OPT（理想型淘汰）算法

该算法无法实现。置换规则：

（1）淘汰内存中以后不再访问的页面；（2）如果没有（1），则淘汰将要访问指令之后的将来最迟被访问的指令的页面。指令页面1 页面2 页面3 页面4 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6 是否中断 Y Y Y Y N N Y Y N N N N Y N N N Y N N N 分析：

（1）当访问5时，内存1,2,3,4,发生第5次中断，淘汰不再访问的4，换入5，内存

1,2,3,5；

（2）当访问6时，内存1,2,3,5,发生第6次中断，淘汰不再访问的5，换入6，内存

1,2,3,6；

（3）当访问7时，内存1,2,3,6,发生第7次中断，由于之后的指令（1、2、3、6）都是

现在内存页面都存在的指令，无法淘汰，但可以根据指令访问顺序，先淘汰将来最迟被访问的1，换入7，置换后的内存7,2,3,6；

（4）当访问1时，内存7,2,3,6,发生第8次中断，淘汰不再访问的7，换入1，内存

1,2,3,6；

即OPT算法一共会出现8次缺页中断。

二、LRU（最近最久未使用）算法

该算法利用堆栈实现，每次访问都调整堆栈中页面顺序。把被访问页面从栈移出再压入栈顶。置换规则：

（1）栈顶始终为最新访问过的页面；

（2）栈底始终为最近最久未被访问的页面；（3）访问存在的页面要调到栈顶。指令页面1 页面2 页面3 页面4 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 1 2 3 4 2 1 5 6 6 1 2 3 7 6 3 3 1 2 1 1 3 4 2 1 5 5 6 1 2 2 7 6 6 6 1 是否中断 Y Y Y Y N N Y Y N N N Y Y Y N N Y N N N

分析：

（1）访问第5个指令2时，由于内存页面中已经存在2，所以不置换，但调整2在栈中

顺序，即将2调到栈顶，其它页面依次后置。调整前内存4,3,2,1,调整后内存2,4,3,1；

（2）访问第7个指令5时，发生第5次中断，原内存1,2,4,3,淘汰栈底3，栈顶调入5，

调整后内存5,1,2,4；

（3）访问第8个指令6时，发生第6次中断，原内存5,1,2,4,，淘汰栈底4，栈顶调入

6，调整后内存6,5,1,2；

……

即LRU算法一共会出现10次缺页中断。

三、FIFO（先进先出）算法

该算法利用队列实现。FIFO与LRU的区别是FIFO遇到内存中存在的页面不需要调换页面顺序。

置换规则：