页式管理
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遇到内存中存在的页面不需要调换页面顺序。
置换规则：
（1）淘汰队尾；
（2）即将访问的页调入队头；
（3）访问存在的页面不用调到队头。 指令 页面1 页面2
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 1 2 3 4 4 4 5 6 2 1 1 3 7 6 6 2 1 1 3 3 1 2 3 3 3 4 5 6 2 2 1 3 7 7 6 2 2 1 1
详解页式管理置换算法FIFO_LRU_OPT
