分页虚拟存储管理——页面置换算法

最佳置换算法（Optimal，OPT）

最佳置换算法是一种理想化的算法。要求从内存中淘汰以后永远不使用的页，若无这样的页，则淘汰在最长时间内不再被访问的页。采用最佳置换算法，可以保证获得最低的缺页率。但是人们无法预知一个进程在内存的若干个页面，哪一个页面是未来最长时间不再被访问的，因此这种算法是无法实现的，只能作为其他置换算法的衡量标准。

【例题】在一个分页式虚拟存储管理的系统中，一个作业的页面走向为1,2,1,0,4,1,3,4,2,1,4,1。每调进一个新页就发生一次缺页中断。设分配给该作业的物理块数M=3，采用最佳置换算法求缺页中断次数F和缺页率f。
分析题目
页面走向为：1,2,1,0,4,1,3,4,2,1,4,1
缺页中断原则：每调进一个新页就发生一次缺页中断
分配给该作业的物理块数M=3，意思是：内存中最多可放置3页。
解：页面置换情况如下表所示。
为了好看，先写一个空表

访问顺序就是按照页面走向来排的，
当 1 进来时，内存尚为空，1 进来后占据1页。由于在 1 进来之前内存块中事先没有 1 的存在，所以此时 1 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=1。

当2进来时，内存已经被1占据了1块，此时内存剩余容量为2。当2进来后占据1页。由于在2进来之前内存中事先没有2的存在，所以此时 2 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=2。

当1进来时，内存已经被1和2占据了2块，此时内存剩余量为1。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当0进来时，内存已经被1、2、占据了2块，此时内存剩余量为1，0 是一个新页，所以缺页数应该加1，此时缺页数=3。

当4进来时，内存已经被1、2、0占据了3块，此时内存无剩余量，且4 是一个新页，4想要进来就必须替换掉1,2,0中的一个，替换的规则就是看4后面的访问顺序 1,3,4,2,1,4,1那么究竟要替换哪一个数呢？答案是0，最佳置换算法的原理是：淘汰在最长时间内不再被访问的页，4要替换掉1,2,0中的在最长时间内不再被访问的页，当然就是0啦，4后面的访问顺序里都没有0被访问了，所以就让4替换掉0，与此同时缺页数加1，此时缺页数=4。

当1进来时，内存已经被1,2,4占据了3块，此时内存剩余量为0。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当3进来时，内存已经被1,2,4占据了3块，此时内存剩余量为0。且3 是一个新页，3想要进来就必须替换掉1,2,4中的一个，替换的规则就是看3后面的访问顺序 4,2,1,4,1那么究竟要替换哪一个数呢？答案是1，最佳置换算法的原理是：淘汰在最长时间内不再被访问的页，3要替换掉1,2,4中的在最长时间内不再被访问的页，当然就是1啦，3后面的访问顺序相比较于4,2，1被访问的时候还早着呢！所以3要去置换1，与此同时缺页数加1，此时缺页数=5。

当4进来时，内存已经被3,2,4占据了3块，此时内存剩余量为0。当4进来后，由于在4进来之前内存中事先有4的存在。所以此时的4对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当2进来时，内存已经被3,2,4占据了3块，此时内存剩余量为0。当2进来后，由于在2进来之前内存中事先有2的存在。所以此时的2对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当1进来时，内存已经被3,2,4占据了3块，此时内存剩余量为0。且1 是一个新页，1想要进来就必须替换掉3,2,4中的一个，替换的规则就是看1后面的访问顺序 4,1那么究竟要替换哪一个数呢？答案是3，最佳置换算法的原理是：淘汰在最长时间内不再被访问的页，1要替换掉3,2,4中的在最长时间内不再被访问的页，我们发现在后续的访问顺序中3和2都不会被访问到了，那么究竟要替换它们两个中的哪一个呢答案是3，（通过上一步2进入内存的时候3就已经存在了，3比2来得更早，换句话说3比2更早访问，那么相比2，3再被访问的时间就会晚一点），与此同时缺页数加1，此时缺页数=6。

当4进来时，内存已经被1,2,4占据了3块，此时内存剩余量为0。当4进来后，由于在4进来之前内存中事先有4的存在。所以此时的4对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当1进来时，内存已经被1,2,4占据了3块，此时内存剩余量为0。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

至此所有的页面都访问完毕了，对应的页面置换情况表也成功出炉了：

缺页中断次数：F=6
缺页率：f=6/12=50%

先入先出置换算法（First-In First-Out，FIFO）

原理：淘汰最早进入内存的那个页面。因为，最早进入的页面，其不再使用的可能性比最近调入的页面要大。这种置换算法实现简单，只要把各个调入内存的页按其进入内存的现后顺序连成一个队列即可，总是淘汰队首的那一页。
【例题】在一个分页式虚拟存储管理的系统中，一个作业的页面走向为1,2,1,0,4,1,3,4,2,1,4,1。每调进一个新页就发生一次缺页中断。设分配给该作业的物理块数M=3时，采用先入先出置换算法求缺页中断次数F和缺页率f。
分析题目
页面走向为：1,2,1,0,4,1,3,4,2,1,4,1
缺页中断原则：每调进一个新页就发生一次缺页中断
分配给该作业的物理块数M=3，意思是：内存中最多可放置3页。
解：分配给该作业的物理块数M=3时，页面置换情况如下表所示。
为了好看，先写一个空表
访问顺序就是按照页面走向来排的，
当 1 进来时，内存尚为空，1 进来后占据1页。由于在 1 进来之前内存块中事先没有 1 的存在，所以此时 1 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=1。

当2进来时，内存已经被1占据了1块，此时内存剩余容量为2。当2进来后占据1页。由于在2进来之前内存中事先没有2的存在，所以此时 2 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=2。

当1进来时，内存已经被1和2占据了2块，此时内存剩余量为1。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当0进来时，内存已经被1、2、占据了2块，此时内存剩余量为1，0 是一个新页，所以缺页数应该加1，此时缺页数=3。

当4进来时，内存已经被1、2、0占据了3块，此时内存无剩余量，且4 是一个新页，4想要进来就必须替换掉1,2,0中的一个，替换的规则就是看1,2,0谁是最先进入内存的，答案是1，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，4要替换掉1,2,0中最早进入内存的页面，当然就是1啦，所以就让4替换掉1，与此同时缺页数加1，此时缺页数=4。

当1进来时，内存已经被4、2、0占据了3块，此时内存无剩余量，且1 是一个新页，1想要进来就必须替换掉4,2,0中的一个，替换的规则就是看4,2,0谁是最先进入内存的，答案是2，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，1要替换掉4,2,0中最早进入内存的页面，当然就是2啦，所以就让1替换掉2，与此同时缺页数加1，此时缺页数=5。

当3进来时，内存已经被4、1、0占据了3块，此时内存无剩余量，且 3 是一个新页，3想要进来就必须替换掉4,1,0中的一个，替换的规则就是看4,1,0谁是最先进入内存的，答案是0，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，3要替换掉4,1,0中最早进入内存的页面，当然就是0啦，所以就让3替换掉0，与此同时缺页数加1，此时缺页数=6。

当4进来时，内存已经被4,1,3占据了3块，此时内存剩余量为0。当4进来后，由于在4进来之前内存中事先有4的存在。所以此时的4对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当2进来时，内存已经被4、1、3占据了3块，此时内存无剩余量，且2 是一个新页，2想要进来就必须替换掉4,1,3中的一个，替换的规则就是看4,1,3谁是最先进入内存的，答案是4，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，2要替换掉4,1,3中最早进入内存的页面，当然就是4啦，所以就让2替换掉4，与此同时缺页数加1，此时缺页数=7。

当1进来时，内存已经被2,1,3占据了3块，此时内存剩余量为0。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当4进来时，内存已经被2、1、3占据了3块，此时内存无剩余量，且4 是一个新页，4想要进来就必须替换掉2,1,3中的一个，替换的规则就是看2,1,3谁是最先进入内存的，答案是1，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，4要替换掉2,1,3中最早进入内存的页面，当然就是1啦，所以就让4替换掉1，与此同时缺页数加1，此时缺页数=8。

当1进来时，内存已经被2、4、3占据了3块，此时内存无剩余量，且1 是一个新页，1想要进来就必须替换掉2,4,3中的一个，替换的规则就是看2,4,3谁是最先进入内存的，答案是3，先进先出置换算法的原理是：淘汰最早进入内存的那个页面，1要替换掉2,4,3中最早进入内存的页面，当然就是3啦，所以就让1替换掉3，与此同时缺页数加1，此时缺页数=9。

至此所有的页面都访问完毕了，对应的页面置换情况表也成功出炉了：

缺页中断次数：F=9
缺页率：f=9/12=75%

最近最久未使用置换算法（Least Recently Used，LRU）

原理：选择在最近一段时间内最久没有使用过的页，把它淘汰掉
【例题】在一个分页式虚拟存储管理的系统中，一个作业的页面走向为1,2,1,0,4,1,3,4,2,1,4,1。每调进一个新页就发生一次缺页中断。设分配给该作业的物理块数M=3时，采用最近最久未使用置换算法求缺页中断次数F和缺页率f。
分析题目
页面走向为：1,2,1,0,4,1,3,4,2,1,4,1
缺页中断原则：每调进一个新页就发生一次缺页中断
分配给该作业的物理块数M=3，意思是：内存中最多可放置3页。
解：分配给该作业的物理块数M=3时，页面置换情况如下表所示。
为了好看，先写一个空表
访问顺序就是按照页面走向来排的，
当 1 进来时，内存尚为空，1 进来后占据1页。由于在 1 进来之前内存块中事先没有 1 的存在，所以此时 1 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=1。

当2进来时，内存已经被1占据了1块，此时内存剩余容量为2。当2进来后占据1页。由于在2进来之前内存中事先没有2的存在，所以此时 2 对于内存而言是一个新页，按照题目缺页中断的原则每调进一个新页就发生一次缺页中断，那么缺页数相应的加1，此时缺页数=2。

当1进来时，内存已经被1和2占据了2块，此时内存剩余量为1。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当0进来时，内存已经被1、2、占据了2块，此时内存剩余量为1，0 是一个新页，所以缺页数应该加1，此时缺页数=3。

当4进来时，内存已经被1、2、0占据了3块，此时内存无剩余量，且4 是一个新页，4想要进来就必须替换掉1,2,0中的一个，替换的规则就是看4左边的访问过了的顺序 1,2,1,0，找到离4最近的要替换的数字1、2、0，那么究竟要替换哪一个数呢？答案是2最近最久未使用置换算法的原理是：淘汰在最近一段时间内最久没有使用的页，（可以给个度量来看，如：上一秒刚访问了0，上上一秒访问了1，上上上一秒访问了2）所以最近最久未使用的就是2，所以就让4替换掉2，与此同时缺页数加1，此时缺页数=4。

当1进来时，内存已经被1、4、0占据了3块，此时内存剩余量为0。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当3进来时，内存已经被1、4、0占据了3块，此时内存无剩余量，且3 是一个新页，3想要进来就必须替换掉1,4,0中的一个，替换的规则就是看3左边的访问过了的顺序 1,2,1,0,4,1，找到离3最近的要替换的数字1,4,0那么究竟要替换哪一个数呢？答案是0最近最久未使用置换算法的原理是：淘汰在最近一段时间内最久没有使用的页，（可以给个度量来看，如：上一秒刚访问了1，上上一秒访问了4，上上上一秒访问了0）所以最近最久未使用的就是0，所以就让3替换掉0，与此同时缺页数加1，此时缺页数=5。

当4进来时，内存已经被1、4、3占据了3块，此时内存剩余量为0。当4进来后，由于在4进来之前内存中事先有4的存在。所以此时的4对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当2进来时，内存已经被1、4、3占据了3块，此时内存无剩余量，且2 是一个新页，2想要进来就必须替换掉1,4,3中的一个，替换的规则就是看2左边的访问过了的顺序 1,2,1,0,4,1,3,4，找到离2最近的1,4,3那么究竟要替换哪一个数呢？答案是1最近最久未使用置换算法的原理是：淘汰在最近一段时间内最久没有使用的页，（可以给个度量来看，如：上一秒刚访问了4，上上一秒访问了3，上上上一秒访问了1）所以最近最久未使用的就是1，所以就让2替换掉1，与此同时缺页数加1，此时缺页数=6。

当1进来时，内存已经被2、4、3占据了3块，此时内存无剩余量，且** 1** 是一个新页，1想要进来就必须替换掉2,4,3中的一个，替换的规则就是看1左边的访问过了的顺序1,2,1,0,4,1,3,4,2，找到离1最近的2,4,3那么究竟要替换哪一个数呢？答案是3最近最久未使用置换算法的原理是：淘汰在最近一段时间内最久没有使用的页，（可以给个度量来看，如：上一秒刚访问了2，上上一秒访问了4，上上上一秒访问了3）所以最近最久未使用的就是3，所以就让1替换掉3，与此同时缺页数加1，此时缺页数=7。

当4进来时，内存已经被2、4、1占据了3块，此时内存剩余量为0。当4进来后，由于在4进来之前内存中事先有4的存在。所以此时的4对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

当1进来时，内存已经被2、4、1占据了3块，此时内存剩余量为0。当1进来后，由于在1进来之前内存中事先有1的存在。所以此时的1对于内存而言不是一个新页。内存块无需被多占据1页，相应的缺页数也无需变化。

至此所有的页面都访问完毕了，对应的页面置换情况表也成功出炉了：

缺页中断次数：F=7
缺页率：f=7/12=58%

相关拓展练习请转到：