FIFO页面调度算法处理缺页中断要点

实验四 用先进先出（FIFO ）页面调度算法处理缺页中断1．实验目的深入了解页式存储管理如何实现地址转换；进一步认识页式虚拟存储管理中如何处理缺页中断。

2．实验预备知识页式存储管理中的地址转换的方法；页式虚拟存储的缺页中断处理方法。

3．实验内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。

实验具体包括：首先对给定的地址进行地址转换工作，若发生缺页则先进行缺页中断处理，然后再进行地址转换；最后编写主函数对所作工作进程测试。

假定主存64KB ，每个主存块1024字节，作业最大支持到64KB ，系统中每个作业分得主存块4块。

4．提示与讲解页式存储管理中地址转换过程很简单，假定主存块的大小为2n 字节，主存大小为2m'字节和逻辑地址m 位，则进行地址转换时，首先从逻辑地址中的高m-n 位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高m'-n 位，最后从逻辑地址中取得低n 位放入物理地址的低n 位就得到了物理地址，过程如图1所示。

图1 页式存储管理系统地址转换示意图地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程，模拟地址转换的流程图如图2所示（实验中假定主存64KB ，每个主存块1024字节，逻辑地址即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB，即m=16，逻辑地址中页号6位、页内地址10位）。

在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。

页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存），磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过）。

【算法】页⾯置换算法FIFO、LRU和LFU的概述以及实现⽅式【算法】页⾯置换算法FIFO、LRU和LFU的概述以及实现⽅式页⾯置换算法，我们最常⽤的页⾯置换算法包括FIFO先来先服务，LRU最近最久未被使⽤，LFU最近最少被使⽤以及我们的时钟置换算法。

⼀、FIFO算法——先来先服务1、简述FIFO算法FIFO算法是我们⽐较简单的置换算法，就是先来先服务或者说是先进先出。

也就是说在进⾏页⾯置换的时候，最先来的那个会被最先置换出去。

先进⼊的指令先完成并引退，跟着才执⾏第⼆条指令。

2、FIFO算法的简单实现FIFO算法的简单实现：可以通过维护⼀个链表结构去存储当前调⼊的页⾯；将最先进⼊的页⾯维护在链表的最前，最后进⼊的页⾯维护在链表的最后；这样，当发⽣缺页中断时，需要进⾏置换的时候，淘汰表头的页⾯并将新调⼊的页⾯加到链表的尾部；当然除了链表以外我们还可以采⽤数组或者队列等来进⾏实现。

3、FIFO算法的特点（1）FIFO算法实现简单，易于理解易于编程。

FIFO算法实现简单，⽆须硬件⽀持，只需要⽤循环数组管理物理块即可。

（2）FIFO算法可能会出现Belady现象。

也就是在FIFO算法中，如果未分配够⼀个进程所要求的页⾯，有时就会出现分配的页⾯数增多，却也率反⽽增加Belady现象。

（3）FIFO算法可能会置换调重要的页⾯，其效率不⾼。

（4）在FIFO算法可能中会导致多次的页⾯置换。

当页⾯置换的时间⼤于所要操作的时间的时候，这时候其效率就会很低。

当其不停的进⾏页⾯置换的时候会出现⼤量的系统抖动现象。

⼆、LRU算法——最近最久未被使⽤1、简述LRU算法LRU算法是最近最久未被使⽤的⼀种置换算法。

也就是说LRU是向前查看。

在进⾏页⾯置换的时候，查找到当前最近最久未被使⽤的那个页⾯，将其剔除在内存中，并将新来的页⾯加载进来。

2、LRU算法的实现LRU的实现就相对于FIFO的实现复杂⼀点。

我们可以采⽤哈希映射和链表相结合。

目录1 需求分析 (2)1.1 目的和要求 (2)1.2 研究内容 (2)2 概要设计 (2)2．1 FIFO算法 (3)2．2 LRU算法 (3)2．3 OPT算法 (3)2．4 输入新的页面引用串 (3)3 详细设计 (4)3．1 FIFO（先进先出）页面置换算法： (4)3．2 LRU（最近最久未使用）置换算法： (4)3．3 OPT（最优页）置换算法 (4)4 测试 (5)5 运行结果 (5)6 课程设计总结 (9)7 参考文献 (10)8 附录：源程序清单 (10)1 需求分析1.1 目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

1.2 研究内容模拟实现页式虚拟存储管理的三种页面置换算法（FIFO(先进先出)、LRU （最近最久未使用）和OPT（最长时间不使用）），并通过比较性能得出结论。

前提：（1）页面分配采用固定分配局部置换。

（2）作业的页面走向和分得的物理块数预先指定。

可以从键盘输入也可以从文件读入。

（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。

2 概要设计本程序主要划分为4个功能模块，分别是应用FIFO算法、应用LRU算法、应用OPT算法和页面引用串的插入。

1.1各模块之间的结构图2．1 FIFO 算法该模块的主要功能是对相应页面引用串进行处理，输出经过FIFO 算法处理之后的结果。

2．2 LRU 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过LRU 算法处理之后的结果。

2．3 OPT 算法该模块的主要功功能是对相应的页面引用串进行处理，输出经过OPT 算法处理之后的结果。

2．4 输入新的页面引用串该模块的主要功能是用户自己输入新的页面引用串，系统默认的字符串是0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0，用户可以自定义全新的20个数字页面引用串。

缺页中断的处理流程
一、缺页中断的检测阶段
1.检测缺页中断
（1）CPU访问内存发现缺页
（2）操作系统接收到缺页异常信号
2.确认缺页类型
（1）缺页是否为无效页
（2）缺页是否为合法但不在内存中的页
二、缺页中断的处理阶段
1.选择缺页置换算法
（1）FIFO算法
（2）最近最久未使用算法（LRU）
2.确定置换页
（1）选择待替换的页
（2）检查待替换页的修改位
3.选择加载页
（1）确定需加载的页
（2）从磁盘读取页到内存
三、缺页中断的恢复阶段
1.更新页表
（1）将新加载的页添加到页表
（2）更新页表中的相关信息
2.恢复进程执行
（1）恢复进程执行的指令
（2）将控制权返回给用户程序
四、缺页中断的优化阶段
1.页面预调度
（1）提前将可能被访问的页面加载到内存（2）减少缺页中断的发生频率
2.页面置换算法优化
（1）评估不同置换算法的性能
（2）根据系统负载动态调整置换算法。

页式虚拟FIFO存储管理缺页中断的模拟算法FIFO一课程设计目的与功能1目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标——缺页次数和缺页率，来对各种替换算法进行评价比较。

设计并实现出的结果程序要能够很好地显示页面调入和替换详细信息。

2初始条件（1）预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。

（2）实践准备：掌握一种计算机高级语言的使用3 开发环境（1）使用系统：Windows XP（2）使用语言：C++（3）开发工具：Visual C++ 6.04功能设计的结果程序能实现OPT、FIFO、随机淘汰算法模拟页式存储管理缺页中断，主要能够处理以下的情形：(1) 用户能够输入给作业分配的内存块数；(2) 用户能够输入给定的页面，并计算发生缺页的次数以及缺页率；(3) 程序可随机生成页面序列，替代用户输入；(4) 缺页时，如果发生页面置换，输出淘汰的页号。

二需求分析，整体功能及设计数据结构或模块说明1 需求分析在纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。

即用户程序将受到物理内存大小的限制。

为了解决这个问题，人们提出了能提供虚存的存储管理技术——请求分页存储管理技术和请求分段技术。

本设计实现请求分页管理技术。

请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。

它允许只装入部分页面的程序和数据，便启动运行。

以后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上。

置换时以页面为单位，为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。

考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少?
答：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。

当内存块数量为3时：
发生缺页中断的次数为16。

在FIFO算法中，先进入内存的页面被先换出。

当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5、1、2、4，可见4为最先进入内存的，本次应换出，然后把页6调入内存。

发生缺页中断的次数为15。

在LRU算法中，最近最少使用的页面被先换出。

当页6要调入时，内存的状态为5、2、1，考查页6之前调入的页面，分别为5、1、2，可见2为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。

发生缺页中断的次数为11。

在OPT算法中，在最远的将来才被访问的页面被先换出。

当页6要调入时，内存的状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时间内使用最少的，本次应换出，然
后把页6调入内存。

F I F O页面调度算法处理缺页中断源代码及结果一、源代码#include <cstdio>#include <cstring>#define SizeOfPage 100#define SizeOfBlock 128#define M 4struct info//页表{long textNumber;//页号bool flag; //标志long block;//块号long disk;//在磁盘上的位置bool dirty;//修改标志}pagelist[SizeOfPage];long po;//队列标记long P[M];int num;void init(){memset(pagelist,0,sizeof(pagelist));//根据实验数据初始化pagelist[0].textNumber=0;pagelist[0].flag=1;pagelist[0].block=5;pagelist[0].dirty=0;pagelist[0].disk=11;pagelist[1].textNumber=1;pagelist[1].flag=1;pagelist[1].block=8;pagelist[1].dirty=0;pagelist[1].disk=12;pagelist[2].textNumber=2;pagelist[2].flag=1;pagelist[2].block=9;pagelist[2].disk=13;pagelist[3].textNumber=3;pagelist[3].flag=1;pagelist[3].block=1;pagelist[3].dirty=0;pagelist[3].disk=21;pagelist[4].textNumber=4;pagelist[4].flag=0;pagelist[4].dirty=0;pagelist[4].disk=22;pagelist[5].textNumber=5;pagelist[5].flag=0;pagelist[5].dirty=0;pagelist[5].disk=23;pagelist[6].textNumber=6;pagelist[6].flag=0;pagelist[6].dirty=0;pagelist[6].disk=121;num=6;}void init_ex2(){po=0;P[0]=0;P[1]=1;P[2]=2;P[3]=3;init();}void work(){long p,q,i;char s[100];bool stop=0;do{printf("请输入指令的页号、单元号，以及是否为存指令（输入exit 结束循环）：\n");if (scanf("%ld%ld",&p,&q)!=2){scanf("%s",s);if (strcmp(s,"exit")==0){stop=1;}}else if(q>128){printf("注意!所输入的地址单元已经越界!\n请继续......\n");q=-1;}else{scanf("%s",s);if (pagelist[p].flag){printf("绝对地址=%ld\n",pagelist[p].block*SizeOfBlock+q);if (s[0]=='Y' || s[0]=='y'){pagelist[p].dirty=1;//已修改过}}else{if (pagelist[P[po]].dirty){//将更新后的内容写回外存pagelist[P[po]].dirty=0;}pagelist[P[po]].flag=0;//修改要调出的页标志printf("调出 %ld 调入%ld\n",P[po],p); //显示调出调入页面pagelist[p].block=pagelist[P[po]].block;pagelist[p].flag=1;//该页被调入内存P[po]=p;po=(po+1)%M;}}}while (!stop);printf("数组P 的值为：\n");for (i=0;i<M;i++){printf("P[%ld]=%ld\n",i,P[i]);}}void printInit(){int i;printf("____________________________________________________________________\n");printf("| 页号 | 标志 | 主存块号 | 修改标志 |在磁盘上的位置\n");for(i=0;i<=num;i++){if(pagelist[i].flag==1)printf("| %ld | %d | %ld | %d| %ld \n",pagelist[i].textNumber,pagelist[i].flag,pagelist[i].block,pagelist[i].dirty,pagelist[i].disk);elseprintf("| %ld | %d | | %d | %ld \n",pagelist[i].textNumber,pagelist[i].flag,pagelist[i].dirty,pagelist[i].disk);}printf("___________________________________________________________ _________\n");}int main(){printf("初始化页表：\n");init();//打印页表printInit();init_ex2();work(); //算法分析return 0;}二、结果如下：A、初始化页表B、测试数据I、未发生缺页中断时2、发生缺页中断时3、退出时显示现在主存中的页面号（即数组的值）。

课程设计题目请求页式管理缺页中断模拟设计--FIFO、OPT学院计算机科学与技术专业班级姓名指导教师吴利军2013 年 1 月16 日课程设计任务书学生姓名：指导教师：吴利军_ 工作单位：计算机科学与技术学院题目: 请求页式管理缺页中断模拟设计--FIFO、OPT初始条件：1．预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．实现指定淘汰算法。

能够处理以下的情形：⑴能够输入给作业分配的内存块数；⑵能够输入给定的页面，并计算发生缺页的次数以及缺页率；⑶缺页时，如果发生页面置换，输出淘汰的页号。

2．设计报告内容应说明：⑴需求分析；⑵功能设计（数据结构及模块说明）；⑶开发平台及源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。

周2、周3：完成程序调试及测试。

周4、周5：验收、撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日请求页式管理缺页中断模拟设计——FIFO、OPT1课程设计目的与功能1.1设计目的结合《操作系统》所学内存页式管理章节，掌握虚拟内存设计的重要性，熟悉和掌握请求分页式存储管理的实现原理，通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法（主要通过FIFO和OPT实现），并考察替换算法的评价指标——缺页次数和缺页率，得到淘汰的页面次序。

实验六虚拟存储器一、实验内容模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二、实验目的在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。

用这种办法扩充的主存储器称为虚拟存储器。

通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。

三、实验题目本实验有三道题目，其中第一题必做，第二，三题中可任选一个。

第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中断。

[提示]（1）分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。

为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：其中，标志----用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。

主存块号----用来表示已经装入主存的页所占的块号。

在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。

（2）作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：绝对地址=块号×块长+单元号计算出欲访问的主存单元地址。

如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。

若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

（3）设计一个“地址转换”程序来模拟硬件的地址转换工作。

当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。

当访问的页不在主存时，则输出“* 该页页号”，表示产生了一次缺页中断。

对⽤LRU和FIFO算法计算“缺页中断”的理解输⼊缺页次数页⾯流：0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2 FIFO分析：012發別調⼊內存，則內存：012(3次缺⾴)調⼊3逃汰最先進⼊的0,則內存：123(4次缺⾴)調⼊2來命中,則內存：123(內存中有2不缺⾴)調⼊1來命中,則內存：123(內存中有1不缺⾴)調⼊3來命中,則內存：123(內存中有3不缺⾴)調⼊5逃汰最先進⼊的1,則內存：235(5次缺⾴)2，3別別命中，則內存：235調⼊6逃汰最先進⼊的,則內存：356(6次缺⾴)調⼊2逃汰最先進⼊的,則內存：562(7次缺⾴)調⼊1逃汰最先進⼊的,則內存：621(8次缺⾴)最后2命中，所以缺页8次=============================在LRU算法中，最近最少使⽤的页⾯被先换出输⼊:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0写出LRU算法实现页⾯更换，并给出缺页次数.(设在内存中占四个页架）分析：1题⽬给了访问串7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 02题⽬给了内存中占四个页架3题⽬给了⽤LRU算法来实现。

要求：画出算法实现。

LRU给出⾏ 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0头-----> 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 01 2 0 3 0 4 2 3 0 3 2 1 2 0 1 70 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1底-----> 7 7 1 1 2 3 0 4 4 4 0 0 3 3 2 2淘汰出内存的页⾯： 7 1 4 3整个的表格是怎么来的呢？请注意：题⽬给了7, 写7；题⽬给了0，写0, 7下⼀格；题⽬给了1, 写1，0下⼀格；题⽬给了2, 写2，1下⼀格；注意：已经四个了从上到下是：2107达到了2的要求：内存中占四个页架。

缺页中断及页⾯置换算法1. 缺页中断 在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页⾯是否存在于内存中。

每当所要访问的页⾯不在内存时，会产⽣⼀次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的⼀页，将其调⼊内存。

缺页本⾝是⼀种中断，与⼀般的中断⼀样，需要经过4个处理步骤： 1. 保护CPU现场 2. 分析中断原因 3. 转⼊缺页中断处理程序进⾏处理 4. 恢复CPU现场，继续执⾏ 但是缺页中断时由于所要访问的页⾯不存在与内存时，有硬件所产⽣的⼀种特殊的中断，因此，与⼀般的中断存在区别： 1. 在指令执⾏期间产⽣和处理缺页中断信号 2. ⼀条指令在执⾏期间，可能产⽣多次缺页中断 3. 缺页中断返回时，执⾏产⽣中断的那⼀条指令，⽽⼀般的中断返回时，执⾏下⼀条指令2. 页⾯置换算法 进程运⾏过程中，如果发⽣缺页中断，⽽此时内存中有没有空闲的物理块是，为了能够把所缺的页⾯装⼊内存，系统必须从内存中选择⼀页调出到磁盘的对换区。

但此时应该把那个页⾯换出，则需要根据⼀定的页⾯置换算法（Page Replacement Algorithm)来确定。

2.1 最佳置换（Optimal， OPT)2.1.1 基本思想 置换以后不再被访问，或者在将来最迟才回被访问的页⾯，缺页中断率最低。

但是该算法需要依据以后各业的使⽤情况，⽽当⼀个进程还未运⾏完成是，很难估计哪⼀个页⾯是以后不再使⽤或在最长时间以后才会⽤到的页⾯。

所以该算法是不能实现的。

但该算法仍然有意义，作为很亮其他算法优劣的⼀个标准。

2.1.2 算例 采⽤固定分配局部置换的策略，嘉定系统为某进程在内存中分配了3个物理块，页⾯访问顺序为2、3、2、1、5、2、4、5、3、2、5、2。

假定系统未采⽤预调页策略，即未事先调⼊任何页⾯。

进程运⾏时，⼀次将2、3、1三个页⾯调⼊内存，发⽣3次缺页中断。

当第⼀次访问页⾯5时，产⽣第4次缺页中断，根据OPT算法，淘汰页⾯1，因为它在以后不会在使⽤了；第5次缺页中断时，淘汰页⾯2，因为它在5、3、2三个页⾯中，是在将来最迟才会被页⾯访问的页⾯。

//页面调度算法（FIFO）#include<stdio.h>#define TRUE 1#define FALSE 0#define MAX 7 // 页的最大数#define IN 4 // 在主存中的页数#define count 13 // 指令数量int P[IN]; // 表示已在主存中的页面int k; // 表示P数组中最先进入内存的页的位置typedef struct{int num; // 页号bool pre; // 标志int random; // 主存块号bool revise; // 修改标志int location; // 在磁盘上的位置}Page_Item;Page_Item Page_Record[MAX];// 指令数据结构typedef struct{char oper; // 操作符int Page_Num; // 页号int Unit_Num; // 单元号}Instruction;Instruction IC[count];// 初始化指令和页表void Init(){k=0; // 指向最先进入内存的页// 初始化页表Page_Record[0].num=0;Page_Record[0].pre=TRUE;Page_Record[0].random=5;Page_Record[0].revise=FALSE;Page_Record[0].location=011;Page_Record[1].num=1;Page_Record[1].pre=TRUE;Page_Record[1].random=8;Page_Record[1].revise=FALSE;Page_Record[1].location=012; Page_Record[2].num=2;Page_Record[2].pre=TRUE; Page_Record[2].random=9; Page_Record[2].revise=FALSE; Page_Record[2].location=013;Page_Record[3].num=3;Page_Record[3].pre=TRUE; Page_Record[3].random=1; Page_Record[3].revise=FALSE; Page_Record[3].location=021;Page_Record[4].num=4;Page_Record[4].pre=FALSE; Page_Record[4].random=0; Page_Record[4].revise=FALSE; Page_Record[4].location=022;Page_Record[5].num=5;Page_Record[5].pre=FALSE; Page_Record[5].random=0; Page_Record[5].revise=FALSE; Page_Record[5].location=023;Page_Record[6].num=6;Page_Record[6].pre=FALSE; Page_Record[6].random=0; Page_Record[6].revise=FALSE; Page_Record[6].location=121;// 初始化指令序列IC[0].oper='+';IC[0].Page_Num=0;IC[0].Unit_Num=70;IC[1].oper='+';IC[1].Page_Num=1;IC[1].Unit_Num=50;IC[2].oper='*';IC[2].Page_Num=2;IC[2].Unit_Num=15;IC[3].oper='w';IC[3].Page_Num=3;IC[3].Unit_Num=21;IC[4].oper='r';IC[4].Page_Num=0;IC[4].Unit_Num=56;IC[5].oper='-';IC[5].Page_Num=6;IC[5].Unit_Num=40;IC[6].oper='>';IC[6].Page_Num=4;IC[6].Unit_Num=53;IC[7].oper='+';IC[7].Page_Num=5;IC[7].Unit_Num=23;IC[8].oper='w';IC[8].Page_Num=1;IC[8].Unit_Num=37;IC[9].oper='r';IC[9].Page_Num=2;IC[9].Unit_Num=78;IC[10].oper='+';IC[10].Page_Num=4;IC[10].Unit_Num=1;IC[11].oper='r';IC[11].Page_Num=6;IC[11].Unit_Num=84;IC[12].oper='#';IC[12].Page_Num=0;IC[12].Unit_Num=0;}// 根据FIFO算法替换页,所需要的参数是被调入页的页结构体void replace(Page_Item page){// 被替换的页已经修改了if(TRUE==Page_Record[P[k]].revise){// 修改被调出页的存在标志Page_Record[P[k]].pre=FALSE;// 修改被调出页的修改标志Page_Record[P[k]].revise=FALSE;printf("调出%d页\n",P[k]);}// 将调入页的存在标志修改为TRUEpage.pre=TRUE;// 将被调出页的主存块号赋给调入页的主存块号page.random=Page_Record[P[k]].random;// 将调入页的页号赋给P[k]P[k]=page.num;printf("调入%d页\n",page.num);// 修改k指针k=(k+1)%IN;}// 指令执行过程void excute(){int i=0; // 指向当前正在执行的指令while('#'!=IC[i].oper){printf("执行%c指令,需%d页\n",IC[i].oper,IC[i].Page_Num);// 若正在执行的指令所需的页不在内存中if(FALSE==Page_Record[IC[i].Page_Num].pre){printf("该页不在内存中,请求调入.........\n");// 调用替换函数，调入所需的页replace(Page_Record[IC[i].Page_Num]);}// 修改指令对该页的操作if('+'==IC[i].oper||'*'==IC[i].oper||'-'==IC[i].oper||'>'==IC[i].oper){printf("%c指令修改了%d页\n",IC[i].oper,IC[i].Page_Num);// 修改该页的修改标志Page_Record[IC[i].Page_Num].revise=TRUE;}i++; // 指向下一条指令}for(i=0;i<IN;i++){if(TRUE==Page_Record[P[i]].revise){printf("%d页写回外存!\n",P[i]);}}}void main(){Init();excute();}。

计算机操作系统上机教案学院名称：河北政法职业学院系部名称：计算机系课程名称：计算机操作系统任课教师：张敏丽授课题目：操作系统实训1 授课序号：12 授课班级：司法信息2003级教学方法：讲授，实训课时：2学时教学目的：通过这一章的学习，使学生掌握该计算机系统的使用方法。

教学重点：界面的使用。

教学难点：熟悉该系统的操作命令。

作业布置：教学内容：一、实习内容选择一个计算机系统，熟悉该系统的操作命令，且掌握该计算机系统的使用方法。

二、实习目的配合操作系统课程的学习，模拟实现操作系统的功能，有助于对操作系统的理解。

操作系统功能的模拟实现可以在计算机系统的终端上进行，也可以在一台微型计算机上进行。

根据您的学习条件，选择一个计算机系统，熟悉对该系统的使用，那么您可以顺利地完成本课程的实习。

为了尽快地熟悉计算机系统，可编辑一个源程序，且对编辑好的源程序编译、运行、显示/打印运行结果等。

三、实习题目1打开:"开始"-"程序"-"附件"-"系统工具",①进行磁盘清理,②进行磁盘碎片整理,③进行磁盘扫描,④进行磁盘维护向导的操作,⑤进行"系统信息"中启动过程的设置.2浏览"控制面板"-"系统"---"设备管理器"信息的查看及"控制面板"-"网络"-的配置信息的作用.在"控制面板"-"电源管理"-中修改电源管理选项和,在"控制面板"-"日期/时间"-中修改日期和时间.2 按大纲模式建立一"培训练习"文档,文档内容为本本书目录的前三章,每章节只取两个标题,然后在普通视图下输入每节的前两行文字,并在页面视图下排版出满意的文档,最后存于"Word文档练习"中.4 根据"简历向导"建立一个人建立资料,用文件名"简历"存于"Word文档练习"文件夹中.授课题目：操作系统实训2 授课序号：14 授课班级：司法信息2003级教学方法：讲授，实训课时：2学时教学目的：通过这一章的学习，使学生掌握处理机的调度方法。

先进先出(FIFO)页面置换算法一、设计思想该算法总是淘汰最先进入内存的页面，既选择内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需要把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。

但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO 算法并不能保证这些页面不被淘汰。

这里，我们用下面的例子，采用FIFO 算法进行页面置换。

当进程第一次访问页面2时，将把第七页换出，因为它是最先被调入内存的；在第一次范文页面3时，又将把第零页换出，因为他在现有的2，0，1三个页面中是最老的页。

由下图可以看出，利用FIFO 算法时进行了十二次页面置换，比最佳置换算法正好多一倍。

引用率0 1二、运行结果1、输入分配的物理块数和页面号引用串，执行算法。

2、执行FIFO算法过程如下：三、源程序代码#include <iostream>#include <iomanip> //使用setw()时用到的头文件#include <stdio.h>#include <stdlib.h>#include <conio.h> //使用getchar()时用到的头文件using namespace std;#define Max 30 //某进程调入内存中的最大页面数#define Size 10 //系统为某进程分配的最大物理块数void Init(int Block[],int m) //初始化物理块{ int i;for(i=0;i<m;i++){Block[i]=-1;}}void creat(int Page[],int n) //输入页面串引用号{ int i;for(i=0;i<n;i++){cin>>Page[i];}void FIFO(int Page[],int Block[],int n,int m){//max_stay:比较当前内存中页面驻留的最久时间,count:统计页面置换次数//get:某物理块是否等待驻入新页面(-1:否)//flag:标记当前序号页面是否已驻入内存(-1:否)//block_num:驻留内存时间最长的页面所在的物理块序号//time[]标记对应序号的物理块中页面驻留时间int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int time[Size];for(i=0;i<m;i++) //初始化time[]{ time[i]=0;}for(i=0;i<n;i++){ for(j=0;j<m;j++) //有空闲物理块时，页面直接驻入内存空闲块{ if(Block[j]==-1){get=j; //物理块j即将(/等待)驻入新页面break;}}for(j=0;j<m;j++) //查找序号相同的页面{ if(Block[j]==Page[i])//物理块j中页面与当前期望调入内存的页面相同{flag=j;break;}}for(j=0;j<m;j++) //找到驻留内存时间最久的页面置换出{if(time[j]>max_stay){max_stay=time[j];block_num=j; //block_num标记当前序号物理块中页面驻留时间最久}}if(flag==-1) //不存在相同页面{ if(get!=-1) //物理块即将(/等待)驻入新页面{Block[get]=Page[i]; //存入页面time[get]=0; //当前物理块重新计时for(j=0;j<=get;j++) //已驻入页面的驻留时间加1{time[j]++;}get=-1;}else //页面调度置换，序号block_num的物理块是驻留时间最久的{Block[block_num]=Page[i];time[block_num]=0;for(j=0;j<Size;j++){time[j]++;}block_num=-1;max_stay=0;count++;}}else //待调入页面与序号flag的物理块中页面相同{for(j=0;j<m;j++){time[j]++;}flag=-1;}for(j=0;j<m;j++) //输出物理块中的页面驻入情况{cout<<setw(3)<<Block[j];}cout<<endl;}if(n>m)count=count+m-3;cout<<"缺页中断次数为:"<<count<<endl;}void main(){ int n,m,Page[Max],Block[Size];cout<<"*******先进先出FIFO页面置换算法*******"<<endl;cout<<"--------------------------------------"<<endl;cout<<"*******(默认:-1表示物理块空闲)*******"<<endl;cout<<endl<<"请输入系统为进程分配的物理块数(m<=10):";while(1){cin>>m;if(m>Size||m<1){cout<<"警告：输入的数据错误！"<<endl;cout<<"请重新输入物理块数:";}else break;}Init(Block,m);cout<<"请输入总页面数(n<=30):";cin>>n;cout<<"\n请输入页面号引用串:";creat(Page,n);cout<<"FIFO算法过程如下:"<<endl;FIFO(Page,Block,n,m);getchar(); //直接执行exe文件时做停留查看结果之用getchar();}。

请求页式管理缺页中断模拟设计--FIFO、OPT1.程设计目的与功能2.1 目的实现请求页式管理缺页中断FIFO、OPT算法，掌握页式存储管理系统的相关理论知识。

2.2 功能实现指定淘汰算法。

能够处理一下情形：2.2.1能够输入给作业分配的内存块数；2.2.2 能够输入给定的页面，并计算发生缺页的次数以及缺页率；2.2.3 缺页时，如果发生页面置换，输出淘汰的页号。

2.需求分析，数据结构或模块说明(功能与框图)2.1算法的原理描述:2.1.1先进先出页面置换（FIFO）FIFO法基本思想：选择在内存驻留时间最长的页将其淘汰。

FIFO 算法认为先调入内存的页不再被访问的可能性要比其他页大，因而选择最先调入内存的页换出。

2.1.2理想型淘汰页面置换算法（OPT）OPT法基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。

这样，淘汰掉该页将不会造成因需要访问该页而又立即把它调入的现象。

该算法无法实现，因为，它要求必须预先知道每一个进程的访问串。

2.2 本次课程设计中的算法流程图2.2.1 FIFO算法的流程图如下图所示：2.2.2 OPT算法的流程图如下图所示：3.源程序的主要部分3.1 程序中要到的全局变量说明#define M 40//最大的访问页面序列数目int N;//内存页面块数3.2 结构体说明struct Pro{int num;//num 记录页面序列号};3.3主函数说明及注释void main(){ cin>>N;// 请输入可用内存物理块数:";Pro p[M];//最大的访问页面序列数目Pro *page=new Pro[N];char c;int m=0,t=0;float n=0;int fifoout[M];//记录FIFO算法淘汰的页面int optout[M];//记录OPT算法淘汰的页面int f=0,o=0;m=Input(m,p);//m返回输入的访问页面总书目do{for(int i=0;i<N;i++){page[i].num=0;//初试化内存页面}i=0;cout<<"****请选择页面置换的(f代表FIFO,o代表OPT)****策略"<<endl;cout<<"f:FIFO页面置换"<<endl;cout<<"o:OPT页面置换"<<endl;cout<<"其他键退出"<<endl;cin>>c;if(c=='f')//FIFO页面置换{n=0;cout<<"******FIFO页面置换算法运行结果如下:******"<<endl;cout<<"FIFO页面置换情况为: "<<endl;while(i<m)//i为当前页面在输入序列中的位置{if(Search(p[i].num,page)>=0)//判断当前输入页面p[i].num 是否已经在内存中,若在则返回其在内存页面块中的位置{i++;//找到相同的页面}else{if(t==N)//N为内存页面数目，t记录是那个页面最先进入内存页面，用来判断内存页面块是否已满t=0;else{n++;//记录缺页次数fifoout[f]=page[t].num;//记录淘汰页面f++;page[t].num=p[i].num;//换入print(page);//输出当前内存页面分配情况t++;}}}cout<<"采用FIFO算法时依次淘汰的页面为：";for(i=0;i<f;i++)//输出淘汰页面号{if(fifoout[i]==0)continue;elsecout<<fifoout[i]<<" ";}cout<<"采用FIFO算法时的缺页次数为："<<n<<endl;cout<<"采用FIFO算法时的缺页率为: "<<(double)n/m<<endl;}if(c=='o')//OPT算法页面置换情况{n=0;cout<<"******OPT页面置换算法运行结果如下:******"<<endl;cout<<"OPT页面置换情况为: "<<endl;int count=0;while(i<m)//i为当前页面在输入序列中的位置{if(Search(p[i].num,page)>=0)//判断当前输入页面p[i].num 是否已经在内存中,若在则返回其在内存页面块中的位置{i++;}else{count++;if(count<=N)//判断内存页面是否有空空闲页面{page[count-1].num=p[i].num;//进入空闲内存n++;print(page);continue;}int temp=0,cn;for(t=0;t<N;t++)//t记录是那个页面最先进入内存页面{if(temp<Compfu(page,i,t,p))//在以后不回访问内存{temp=Compfu(page,i,t,p);cn=t;}}optout[o]=page[cn].num;//输出淘汰页面o++;page[cn].num=p[i].num;//页面置换n++;print(page);i++;}}cout<<"采用OPT算法时依次淘汰的页面为：";for(i=0;i<o;i++){if(optout[i]==0)continue;elsecout<<optout[i]<<" ";}cout<<"采用OPT算法时的缺页次数为："<<n<<endl;cout<<"采用OPT算法时的缺页率："<<(double)n/m<<endl;}else{exit;}}while(c=='f'||c=='o');}3.4输入函数Input(int m,Pro p[M])int Input(int m,Pro p[M]){ cout<<"请输入访问页面目数：";do{cin>>m;//访问页面数目if(m>M)cout<<"数目太多，请重试"<<endl;elsebreak;}while(1);cout<<"请输入访问页面号序列:";for(int i=0;i<m;i++){cin>>p[i].num;//依次输入页面访问顺序}return m;//返回输入的访问页面总数目}3.5输出函数print(Pro *page1)void print(Pro *page1)//输出当前内存块中的访问页面{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)cout<<page[i].num<<" ";cout<<endl;}3.6 Search(int e,Pro *page1 ) 函数int Search(int e,Pro *page1 )// 用于查找当前页面是否已在内存块中{Pro *page=new Pro[N];page=page1;for(int i=0;i<N;i++)if(e==page[i].num)return i;//返回页面号为e的页面在那个内存页面中return -1;//若不在则返回-1}3.7 Compfu(Pro *page1,int i,int t,Pro p[M]) 函数int Compfu(Pro *page1,int i,int t,Pro p[M])//i为当前页面在输入序列中的位置，t记录页面进入内存的顺序,此函数判断内存快中的页面page[t]在后续访问序列中出现的次数{Pro *page=new Pro[N];page=page1;int count=0;//记录当前页面的未来访问的次数for(int j=i;j<M;j++)//{if(page[t].num==p[j].num )break;//页面已经在内存中else count++;}return count;//返回当前页面在未来还要出现的次数}4、测试用例，运行结果与运行情况分析4.1测试用例设计4.1.1用例1设计：内存物理块数：N=3页面引用序列中总页面个数为：m=12页面引用序列为：4、3、2、1、4、3、5、4、3、2、1、54.1.2用例2设计：内存物理块数：N=4页面引用序列中总页面个数为：m=15页面引用序列为：3、7、4、8、3、1、6、7、8、3、1、2、9、3、5 4.2运行结果及运行情况分析4.2.1测试用例1运行结果如下：4.2.1.1 FIFO算法的运行结果：缺页率＝缺页次数/ 总访问次数＝9 / 12＝75%依次淘汰的页面号为：4、3、2、1、4、34.2.1.2 OPT算法的运行结果为：缺页率＝缺页次数/ 总访问次数＝7 / 12＝58.33%依次淘汰的页面号为：2、1、4、24.2.2测试用例2运行结果如下：4.2.2.1 FIFO算法运行结果如下：缺页率＝缺页次数/ 总访问次数＝12/ 15＝80%依次淘汰的页面号为：3、7、4、8、1、6、7、3 4.2.2.2 OPT算法运行结果缺页率＝缺页次数/ 总访问次数＝10/ 15＝66.67%以此淘汰的页面号为：4、1、7、4、2、35、自我评价与总结本周我们进行了《操作系统》的课程设计，在拿到题目以后便着手准备，通过查阅课本和相关的资料，对本次课程设计要实现的功能有了深刻的了解，在此基础上写起实验代码变得心应手。

计算机科学与技术系实验报告专业名称网络工程课程名称操作系统原理项目名称FIFO页面调度算法处理缺页中断班级 12网络工程（1）班学号 1204031030姓名方彬同组人员朱佳宝、王卫、凌含涛、胡星瑞实验日期 2014.12.02一、实验目的与要求：（1）熟悉、掌握先进先出FIFO算法，并实现用先进先出FIFO算法页面调度算法处理缺页中断.（2）理解基于先进先出FIFO的内存管理调度算法，更好的掌握算法的思想，结合实验理解算法更直观，深刻具体。

通过对先进先出FIFO的调度算法的模拟实验可以清楚的了解内存管理是如何调度的，以及加深对内存管理的了解。

二、实验内容1）任务分析：以无歧义的陈述说明实验任务，并明确规定：(a)输入的形式和输入值的范围；在输入文本框中输入，输入值的范围在0~6之间(b) 输出的形式；输出为缺页序列的表格(c) 程序所能达到的功能；输入页号，输出缺页序列，实现先进先出算法的模拟(d) 测试数据：包括正确的输入及其输出结果和错误的输入及其输出结果。

①输入值为空：②输入值越界：③正确的输入值：2）概要设计：说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

本程序中定义了一个数组int[] mainstore = {3,2,1,0 };用于模拟主存存放页；此外还定义了一个数组int[] flag = {0,0,0,0,0,0,0 };用于表明页号的修改标志位，便于之后的操作。

该程序的只要流程如下：3）详细设计：实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。

using System;using System.Collections.Generic;using ponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Windows.Forms;using lru;using change;namespace 操作系统{public partial class Form1 : Form{public Form1(){InitializeComponent();}//定义一个窗口类，在类里面定义一个窗口int[] mainstore = {3,2,1,0 };//定义数组用于存放页int[] flag = {0,0,0,0,0,0,0 };//定义修改标志位的数组int blo = 0;//用来控制在表格的哪一列输出页号序列private void button1_Click(object sender, EventArgs e)//定义一个事件响应，即对输入进行操作{if (string.IsNullOrEmpty(txt.Text))MessageBox.Show("请输入页号！");else if (int.Parse(txt.Text) > 6 || int.Parse(txt.Text) < 0)MessageBox.Show("输入页号不合法，请重新输入！");//判断输入是否合法else{int page = int.Parse(txt.Text);int i=0;if (page != mainstore[0] && page != mainstore[1] && page != mainstore[2] && page != mainstore[3])//插入页内存中不存在，进行FIFO算法{int lll;lll = mainstore[0];if (flag[mainstore[0]] == 0)//修改标志位为0，直接覆盖{mainstore[0] = page;flag[lll] = 1;}Else//修改标志位为1，数组执行FIFO{for (i = 0; i < 3; i++)mainstore[i] = mainstore[i + 1];mainstore[3] = page;}MessageBox.Show("当前调走页号"+lll.ToString ()+"\n存入页号为"+page.ToString ());l0.Text = "0";l1.Text = "0";l2.Text = "0";l3.Text = "0";l4.Text = "0";l5.Text = "0";l6.Text = "0";//标志位初始化；for (int j = 0; j < 4; j++){if (mainstore[j] == 0)l0.Text = "1";if (mainstore[j] == 1)l1.Text = "1";if (mainstore[j] == 2)l2.Text = "1";if (mainstore[j] == 3)l3.Text = "1";if (mainstore[j] == 4)l4.Text = "1";if (mainstore[j] == 5)l5.Text = "1";if (mainstore[j] == 6)l6.Text = "1";}//根据插入页号，将标志位置1for (int k = 0;k < 7; k++){if (lll == 0)ll0.Text = "1";if (lll == 1)ll1.Text = "1";if (lll == 2)ll2.Text = "1";if (lll == 3)ll3.Text = "1";if (lll == 4)ll4.Text = "1";if (lll == 5)ll5.Text = "1";if (lll == 6)ll6.Text = "1";}//根据情况，将修改标志位置1}else{MessageBox.Show("该页已在主存中！" );}blo++;if(blo==1){txt10.Text = mainstore[0].ToString();txt11.Text = mainstore[1].ToString();txt12.Text = mainstore[2].ToString();txt13.Text = mainstore[3].ToString();}else if(blo==2){txt20.Text = mainstore[0].ToString();txt21.Text = mainstore[1].ToString();txt22.Text = mainstore[2].ToString();txt23.Text = mainstore[3].ToString();}else if(blo==3){txt30.Text = mainstore[0].ToString();txt31.Text = mainstore[1].ToString();txt32.Text = mainstore[2].ToString();txt33.Text = mainstore[3].ToString();}else if(blo==4){txt40.Text = mainstore[0].ToString();txt41.Text = mainstore[1].ToString();txt42.Text = mainstore[2].ToString();txt43.Text = mainstore[3].ToString();}else if(blo==5){txt50.Text = mainstore[0].ToString();txt51.Text = mainstore[1].ToString();txt52.Text = mainstore[2].ToString();txt53.Text = mainstore[3].ToString();}else if(blo==6){txt60.Text = mainstore[0].ToString();txt61.Text = mainstore[1].ToString();txt62.Text = mainstore[2].ToString();txt63.Text = mainstore[3].ToString();}else if(blo==7){txt70.Text = mainstore[0].ToString();txt71.Text = mainstore[1].ToString();txt72.Text = mainstore[2].ToString();txt73.Text = mainstore[3].ToString();}else if(blo==8){txt80.Text = mainstore[0].ToString();txt81.Text = mainstore[1].ToString();txt82.Text = mainstore[2].ToString();txt83.Text = mainstore[3].ToString();}//根据插入数量，决定在输出表的指定列输出}}private void 刷新ToolStripMenuItem_Click(object sender, EventArgs e){Form1 the_new = new Form1();the_new.Show();}private void 退出ToolStripMenuItem_Click(object sender, EventArgs e){this.Close();}4）调试分析：(a)调试过程中遇到哪些问题，是如何解决的；Q1：一开始的程序只能输入9个页号序列，超过之后就不能够再显示新的页号序列；（定义了一个变量BLO，用于记录输入页号数量，做求模运算mod 9,这样当超过九个之后又会从第一列开始覆盖）Q2：考虑到程序的用户友好性，增加了序列刷新功能，刷新输出区域；（定义了一个button，点击后将输出区域初始化）Q3：开始没有理解修改标志位的作用，所以功能没有实现；（经过与同学的讨论，定义了一个数组flag[]，将页号作为flag[]的下标选择置1或置0）(b) 算法的时空分析：算法的时间复杂度和空间复杂度分析；5）测试结果：包括输入和输出，测试数据应该完整和严格。

网络教育学院《操作系统》课程设计题目：页面置换算法FIFO算法学习中心：层次：专业：年级：年春/秋季学号：学生：井杰辅导教师：龙珠完成日期： 2016 年 1 月 28 日页面置换算法FIFO算法在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。

当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

而用来选择淘汰哪一页的规则叫做页面置换算法。

在请求分页存储器管理系统中，我们需要一个页面置换算法，而先进先出算法就是最早出现的一种算法，利用该算法可以实现页面的置换，实现内存的充分利用，使进程可以执行。

先进先出置换算法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。

这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。

理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。

建立一个FIFO队列，收容所有在内存中的页。

被置换页面总是在队列头上进行。

当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。

因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。

当然，导致这种异常现象的页面走向实际上是很少见的。

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。

该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。

但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

1．先进先出（FIFO）该算法实现简单，只需把一个进程已调入内存的页面，按先后顺序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

1、输入当前要调用的页面号2、判断该页面是否已在队列内，若在队列内，不执行任何操作若不在队列内。

fifo页面淘汰算法总结第1篇假设虚拟内存的地址是16位，页面大小为1K，则进程的大小为 2 16 = 64 K B2^{16}=64KB 216=64KB分页个数 = 进程的大小页面的大小 = 逻辑地址表示的大小页面的大小 = 2 16 B 1 K B = 2 6 页分页个数=\frac{进程的大小}{页面的大小}=\frac{逻辑地址表示的大小}{页面的大小}=\ frac{2^{16B}}{1KB}=2^{6}页分页个数=页面的大小进程的大小=页面的大小逻辑地址表示的大小=1KB216B=26页因此页号P占用前6位，页内偏移量W=16-6=10位。

每一个页表项占用2B,因此页表存储空间需要 2 6 ∗ 2 B = 128 B 2^6*2B=128B 26∗2B=128B页面结构以及页表项设计如下：算法流程如下：具体实现如下：算法流程如下：具体实现如下：算法流程如下：其中调用了randBool()函数，随机的生成0或者1，其具体实现如下算法规则：选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。

假定系统为某进程分配了三个物理块，并考虑有以下页面访问序列： [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] 进程运行时，先将7, 0,1三个页面依次装入内存。

进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。

然后，访问页面0时，因为已在内存中所以不必产生缺页中断。

访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推。

算法流程图如下：OPT算法具体实现如下：算法规则：在发生页面替换时，被替换的对象应该是最早进入内存的。

仍然采用上述的例子，此时页面置换过程如下表所示FIFO算法流程图如下所示：FIFO页面置换算法具体实现如下：初始化设置m=8,e=8,s=10; 页框数=3，访问序列长度=20；选择算法2：先进先出淘汰算法置换过程算法规则：在发生页面替换时，被替换的页面应该满足，在之前的访问队列中，该对象截止目前未被访问的时间最长。