本文共 1106 字，大约阅读时间需要 3 分钟。

在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的页面序列是1，2，3，4，1，2，5，1，2，3，4，5.假定分配给该作业的页数为3且作业初始时未装载页面，那么采用FIFO调度算法产生的缺页中断数为多少，采用LRU调度算法产生的缺页中断数为多少？

 FIFO算法：(First In First Out)，先进先出，首先想到的数据结构应当是队列，但是我们这里最好是用vector，因为调页过程中需要遍历队列检查该页是否已存在，当算法的存储结构是队列或栈，但实现过程中需要经常遍历全队列或全栈的内容时，最好用vector。            访问序列：1，2，3，4，1，2，5，1，2，3，4，5                    1，2，3先调入内存，内存结构：3      2      1    缺页次数：3                      4调入内存，1调出，  内存结构：4      3      2    缺页次数：4                    1调入内存，2调出，  内存结构：1      4      3    缺页次数：5                    2调入内存，3调出，  内存结构：2      1      4    缺页次数：6                    5调入内存，4调出，  内存结构：5      2      1    缺页次数：7                    1存在，内存结构不改变                    2存在，内存结构不改变                    3调入内存，1调出，  内存结构：3      5      2    缺页次数：8                    4调入内存，2调出，  内存结构：4      3      5    缺页次数：9                    5存在，内存结构不改变             共缺页9次，缺页中断率 ＝ 缺页中断次数 / 总访问页数 ＝ 9 / 12    LRU算法：最近最少使用（Least Recently Used），先看一下调页过程            访问序列：1，2，3，4，1，2，5，1，2，3，4，5                 1，2，3先调入内存，内存结构：3      2      1    缺页次数：3                   4调入内存，1调出，  内存结构：4      3      2    缺页次数：4                 1调入内存，2调出，  内存结构：1      4      3    缺页次数：5                 2调入内存，3调出，  内存结构：2      1      4    缺页次数：6                 5调入内存，4调出，  内存结构：5      2      1    缺页次数：7            到这一步其实和FIFO并没有区别               1调入内存，由于内存中存在1，故没有缺页中断，但由于1最近被访问过，所以要将其位置调换，               使它最后一个被淘汰，内存结构：1      5      2               2调入内存，没有缺页中断，但内存位置要变化，内存结构：2      1      5                   3调入内存，5调出，  内存结构：3      2      1    缺页次数：8                   4调入内存，1调出，  内存结构：4      3      2    缺页次数：9                   5调入内存，2调出，  内存结构：5      4      3    缺页次数：10            共缺页10次，缺页中断率：10/12算法总结：数据结构应该还是一个队列，开始内存页面不满时按序把页面填入，之后如果调入的页不存在，则按照先进先出顺序，淘汰队头页面，如果调入的页存在，则将该页换至页尾，该页之后的元素前移。

转载地址：http://xqypi.baihongyu.com/