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

合肥学院计算机科学与技术系实验报告2009～2010学年第1学期课程操作系统原理实验名称FIFO页面调度算法处理缺页中断学生姓名孙玉祥何红生王洲良占馥春专业班级07计本（一）班指导教师屠菁2009年11月1．实验目的熟悉、掌握先进先出FIFO算法，并实现用先进先出FIFO算法页面调度算法处理缺页中断.理解基于先进先出FIFO的内存管理调度算法，更好的掌握算法的思想，结合实验理解算法更直观，深刻具体。通过对先进先出FIFO的调度算法的模拟实验可以清楚的了解内存管理是如何调度的，以及加深对内存管理的了解。2．实验内容在分页式虚拟系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已没有空闲块，则用FIFO页面调度算法把作业中最先进入主存的一页调出，存放在外存上，然后把要访问的页装入该块。调入和装入后都要修改页表中对应页的标志。假定：现有一个共有7页的作业，其中第0页到第3页已经装入主存，其余三页尚未装入主存，该作业的页表为：页号标志主存块号进入时间01541183219231114005006003．实验步骤任务分析当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已没有空闲块，则用FIFO页面调度算法把作业中最先进入主存的一页调出，存放在外存上，然后把要访问的页装入该块。调入和装入后都要修改页表中对应页的标志。Check(intp)用于实现判断是否发生缺页中断，diaohuanye(intp)用于实现处理缺页中断并调换页面，被调入页存入被调换页的主存中。详细设计流程图：初始化:list(),append()n=999？Nn7？Ym=-1？是否发生中断执行check(intp)N执行diaohuanye(intp)执行print()END开始输入nYN执行time()Y先定义两大类：item和ListList为item的友元类item为页面信息类，List为页面操作类classitem{public:friendclassList;//声明List是item的友元类，List类可以访问item中的成员private:item(intp=0,ints=0,intb=0,intt=0){page=p;sign=s;block=b;time=t;next=NULL;}item*next;intpage;//页号intsign;//标志intblock;//主存块号inttime;//调入主存时间};classList{public:List(intp=0,ints=0,intb=0,intt=0){list=newitem(p,s,b,t);}intcheck(intp);//检查是否发生缺页voidprint();//输出intappend(intp,ints,intb,intt);//为下一页申请新的空间，并赋值，将其链接到上一个页面的地址之后intdiaohuanye(intp);//调换页号voidtime();private:item*list;item*end();};item定义了list来定义第一页信息，end（）为最后进入主存的页面voidList::print();//输出append()为下一页申请新的空间，并赋值，将其链接到上一个页面的地址之后,已链表的形式链接起来。intList::append(intp,ints,intb){item*pt=newitem(p,s,b,t);(end())-next=pt;return1;}check()函数检查是否发生缺页，当sign等于1时表示该页在主存中，当输入的页号等于其中一个时表明该页在主存中，否则返回-1，表示发生缺页中断。intList::check(intp){item*pt=list;inta=-1;for(;pt;pt=pt-next){if(pt-sign==1&&pt-page==p)a=pt-block;}returna;}diaohuanye函数以time为标尺，时间最大的表示进入页面最早。将页表的各个time与max比较，再以max将pt指向被调换的页面。之后将被调换的页面的标志和进入时间置零。以p将pr指向被调入的页面，并将其标志置1。此时，pt指向被调换的页面，pr指向被调入的页面。将pt的主存块号赋值给pr的主存块号，将pt的主存块号置为NULL。最后返回y，为被调入页的主存块号。intList::diaohuanye(intp)//处理缺页中断，并调换页面{inty,max=0;item*pt=list;//pt运算结束后指向被调换的页面item*pr=list;//pr运算结束后指向被调入的页面for(pt;pt;pt=pt-next)//max为最大进入时间{if(pt-sign==1){if(pt-timemax)max=pt-time;}}pt=list;//pt返回listfor(pt;pt;pt=pt-next){if(pt-time==max)break;}//pt指向被调换页面pt-time=0;pt-sign=0;//标志置0cout被调换的页的页号为:pt-pageendl;cout被调入的页的页号为:pendl;for(pr;pr;pr=pr-next){if(pr-page==p)break;}//pr指向被调入的页面pr-sign=1;//标志置1pr-block=pt-block;pt-block=NULL;y=pr-block;returny;}调试与运行结果：输入的值：715346999（退出）运行结果：4．实验总结本次实验是通过模拟FIFO（先进先出）调度算法处理缺页中断，主要思想是先把进程调入页面，按次序链接成一个队列，并设置指针一直指向最先进入主存的页面。然后将该页面调出，调入输入的页面。通过对先进先出FIFO算法的模拟实现，加深了对内存管理调度的理解，理解了其如何分配内存的过程，本程序较简单但在实现过程中遇到很多问题，一开始总是出错，程序无法运行，通过调试后在运行过程中每发生缺页中断就发生错误无法继续运行。这次的程序是我们几个同学一起研究探讨出来的，在设计的过程中也出现了一些分歧，最后采用了谁最优最简的标准。为以后团队工作也算是一个基础。5．附录#includeiostream.h#includemath.h#includestdlib.hclassitem{public:friendclassList;//声明List是item的友元类，List类可以访问item中的成员private:item(intp=0,ints=0,intb=0,intt=0){page=p;sign=s;block=b;time=t;next=NULL;}item*next;intpage;//页号intsign;//标志intblock;//主存块号inttime;//调入主存时间};classList{public:List(intp=0,ints=0,intb=0,intt=0){list=newitem(p,s,b,t);}intcheck(intp);//检查是否发生缺页voidprint();//输出intappend(intp,ints,intb,intt);//为下一页申请新的空间，并赋值，将其链接到上一个页面的地址之后intdiaohuanye(intp);//调换页号voidtime();private:item*list;item*end();};voidList::time()//每输入一个页面所有页面的调入时间加1{item*pt=list;for(pt;pt;pt=pt-next)if(pt-sign==1)pt-time=pt-time+1;return;}intList::diaohuanye(intp)//处理缺页中断，并调换页面{inty,max=0;item*pt=list;//pt运算结束后指向被调换的页面item*pr=list;//pr运算结束后指向被调入的页面for(pt;pt;pt=pt-next)//max为最大进入时间{if(pt-sign==1){if(pt-timemax)max=pt-time;}}pt=list;//pt返回listfor(pt;pt;pt=pt-next){if(pt-time==max)break;}//pt指向被调换页面pt-time=0;pt-sign=0;//标志置0cout被调换的页的页号为:pt-pageendl;cout被调入的页的页号为:pendl;for(pr;pr;pr=pr-next){if(pr-page==p)break;}//pr指向被调入的页面pr-sign=1;//标志置1pr-block=pt-block;pt-block=NULL;y=pr-block;returny;}voidList::print()//输出{cout页号标志主存块号进入时间endl;item*pt=list;while(pt){if(pt-sign==1)coutpt-pagept-signpt-blockpt-timeendl;elsecoutpt-pagept-signpt-timeendl;pt=pt-next;}coutendl;}intList::append(intp,ints,intb,intt)//初始化{item*pt=newitem(p,s,b,t);(end())-next=pt;return1;}item*List::end()//最后输入的页面{item*q,*pt=list;for(q=list;pt;q=pt,pt=pt-next);returnq;}intList::check(intp)//检查是否发生缺页中断,返回-1发生中断{item*pt=list;inta=-1;for(;pt;pt=pt-next){if(pt-sign==1&&pt-page==p)a=pt-block;}returna;}voidmain(){Listlist(0,1,5,4);//第一页信息list.append(1,1,8,3);//第二页信息list.append(2,1,9,2);//第三页信息list.append(3,1,1,1);//第四页信息list.append(4,0,NULL,0);list.append(5,0,NULL,0);list.append(6,0,NULL,0);cout**********模拟FIFO页面调度算法处理缺页中断**********endl;cout+++++++++++++++++++页表初始状态如下+++++++++++++++++endl;list.print();intm=0,n;intc=0,flag=0;for(inti=0;;i++){intk=0;cout*****************第i+1步操作****************endl;cout请输入该操作对应的页号:;cinn;while(k==0){if((n0||n=7)&&n!=999){cout输入错误!重新输入:;k=0;cinn;}elseif(n==999){flag=1;k=1;}elsek=1;}if(flag==1)break;m=list.check(n);if(m!=-1)//没有中断{cout该页已在主存中，所在的主存块号:mendl;list.time();}elseif(m==-1)//发生中断{cout*缺页中断,页号:nendl;cout*******