详解页式管理置换算法FIFO-LRU-OPT.docx
版权申诉
85 浏览量
2022-11-29
14:00:59
上传
评论
收藏 81KB DOCX 举报
页式管理
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 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 次缺页中断。
资源评论
