先进先出页面调度算法 处理缺页中断

1、合肥学院计算机科学与技术系实验报告20112012学年第一学期课程用先进先出（FIFO ）页面调度算法课程设计名称处理缺页中断学生姓名学号专业班级指导教师2011年11月实验目的：理解相关页面置换算法的含义并能分析其性能好坏；理解并掌握用先进 先出(FIFO)页面调度算法如何处理缺页中断。实验内容：在分页式虚拟存储系统中，当硬件发出缺页中断后，引出操作系统来处 理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作 业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该 块。实验步骤：任务分析：当输入了内存块个数和某一作业的页面走向时，要求结果能显示出使用先

2、 进先出(FIFO)页面置换算法工作的过程，要明确显示每次调出的页号和装入的页 号。而先进先出(FIFO)页面置换算法总是淘汰最先进入内存的页面。为实现上述功能的关键问题是如何判断哪个页面是最先装入的。解决该问题的 方法：使用index记录最先装入的页面所在块。初始时，index为0，随着页面装入并装满内 存块，发生页面替换时index所记录的位置被置换，然后index后移一位，直到移到内存块末 端重新置为0.概要设计：本程序包含四个函数，分别为：init()、fifo()、find()和 main()。其中在 main()函数中要调用init()函数和fifo()函数，在fifo()函数中要

3、调用find()函数。本程序先进行初始化操作，之后再调用先进先出fifo()函数，根据所给的 信息进行先进先出页面置换，并输出置换的过程。详细设计：1.初始化函数init()：该函数是为了输入内存块个数和作业的页面走向，为使用先进先出(FIFO)页面置换算法提供数据。代码如下：void init(void)coutmSize;memory=(int*)malloc(mSize*sizeof(int);coutpSize;process=(int*)malloc(pSize*sizeof(int);cout请输入”pSize”个作业的页号:”；memset(memory, -1, mSize*s

4、izeof(int);int i=0;for(;iprocessi;查找页号函数find()：内存memory中有该页号，则返回ture值，否则返回false值。 代码如下：bool find(int p)/在内存memory中查找有没有页号pint i = 0;for(i=0; imSize; i+)if(memoryi = p)break;if(i = mSize) / 没找到return false;return true;先进先出函数fifo()：FIFO算法的实质是最先进入内存的页，最先被调出内存。该函数将会 把FIFO算法进行的过程通过“调出页号 装入页号内存块”的显示出来。 代码

5、如下：void fifo()int i,j;cout”调出页号 装入页号 内存块”endl;for(i=0;ipSize;i+)if(!find(processi)/内存块中没有对应的页号if(memoryindex!=-1)coutleftsetw(10)memoryindex;elsecoutleftsetw(10)无”; coutsetw(10)processi;memoryindex = processi;/将新页号放入最先进入内存页面的那一块 index=(index+1) % mSize;/更 新索弓 Ielsecoutsetw(10)无vvsetw(10)vv”无”;for(j=

6、0;jmSize;j+)if(memoryj!=-1)coutmemoryj;coutendl;主函数main()void main(void)init();fifo();流程图(4)调试分析：理论上说，要实现“发生页面置换时总是置换先进入的页面”，就 要记录一下每个页面被装入的时间，在发生置换时比较这些时间，找 到时间最前的。但本程序没有这样做，因为本程序本着这样一个规则: 总是把新进入的页面放到内存最后面，内存满时就替换最久的，最久 的页面就是index位置的。本程序不能显示具体的错误或无意义的结果信息。有待改进。改进设想：是否能让内存块中的页号始终按照“在内存中驻留时 间最久的页面，在内

7、存中驻留时间第二久的页面，在内存中驻留时间 第三久的页面，在内存中驻留时间最短的页面”的顺序输出？(5)测试结果:正常正确的结果:Q：312 51 0入个作业的页号H 2 3页号-装入页号1230无1内存块11100QQ无0anj key to22221111Q3 3 22 2 2resscontinue内存块数为0的错误结果:内存块数与页面数相等的结果:皿FADebueXfifo-exe1请世M:3:3蜡-V 个页峭入W1 丽作拓号 74入入页内存块数大于页面数的结果:g F:Debugfifo.exe请请港块1存3内3 黑: 数数！ 个页峭入 丙作2-号 为入入页页面数为0的无意义结果:输

8、入得页号个数大于所要求的个数的结果:1:3:8罄 E 数数丹 个页峭入 番钊装1 内作R-7号 入入入页&无无5：1 303051410内存块11 313 013 013 05 3 0315 10(6)使用说明：输入的内存块的个数应为一个大于等于1的整数，输入的作业的页数也应 是一个大于等于1的整数，当依次输入作业的页号时，要特别注意输入的个数是 否与要求输入的个数相等。4.实验总结：本次的实验花费了我们整个小组不少的精力，虽然每个人的分工不同， 有轻有重，但我们每一个人都还是尽心尽力去完成自己的任务，实验的过程中， 让我们深刻体会到即使是再怎么简单的原理，要想写出一个完整且完美的程序也 还是

9、很困难的。我们都只能力所能及的去做到最好。5.附录：#include #include #include using namespace std;int *memory = NULL;/内存块数组（块数由用户输入决定）int *process = NULL;/ 进程页面数组（）int mSize = 0; /mSize表示内存物理块的个数int pSize = 0; /pSize表示作业的页面数int index = 0;/指向最先进入内存页面的块号void init(void)coutmSize;memory=(int*)malloc(mSize*sizeof(int); / 申请存储空间c

10、outpSize;process=(int*)malloc(pSize*sizeof(int);cout请输入pSize个作业的页号:；memset(memory, -1, mSize*sizeof(int);/对内存进行清零操作，并将内存置成-1 int i=0;for(;iprocessi;bool find(int p)/在内存memory中查找有没有页号pint i = 0;for(i=0; imSize; i+)if(memoryi = p) /内存memory中有页号p，则跳出循环，返回ture值break;if(i = mSize) /在内存memory中没找到页号p,则返回fa

11、lse值return false;return true;void fifo()int i,j;cout调出页号 装入页号 内存块endl;for(i=0;ipSize;i+)/遍历进程页面数组process，将进程页面装入内存先查找内存中有没有相同的页号，如果有则无需装入调出if(!find(processi)/内存块中没有对应的页号输出内存中应调出的页号（模拟调出内存中相应的页面）if(memoryindex!=-1)coutleftsetw(10)memoryindex;elsecoutleftsetw(10)无”；输出应装入内存的进程页号(模拟进程页面调入内存)coutsetw(10)processi;memoryindex = processi;/将新页号放入最先进入内存页面的那一