虚拟存储管理器的页面调度.doc

虚拟存储管理器的页面调度 YuChao 发布于 2010年11月24日 22时 (0评) 3人收藏此代码， 我要收藏(?) 页面调度算法主要有：FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU），最佳算法（OPT）1 输入： 页面流文件，其中存储的是一系列页面号（页面号用整数表示，用空格作为分隔符），用来模拟待换入的页面。 下面是一个示意： 1 2 3 4 1 2 5 1 2 3 4 5 2 处理要求： 程序运行时，首先提示“请输入页面流文件的文件名：”，输入一个文件名后，程序将读入该文件中的有关数据。 初始条件：采用三个页框，初始时均为空。 根据第二次机会算法对数据进行处理。 3 输出要求： 每换入一个页面（即：每读入一个页面号），判断是否有页面需要被换出。若有，把被换出的页面号输出到屏幕上； 若没有，则输出一个“*”号。 4 文件名约定 提交的源程序名字：sourceXXX.c或者sourceXXX.cpp（依据所用语言确定） 输入文件名字：可由用户指定 其中：XXX为账号。 5 测试说明：测试教师将事先准备好一组文件（格式为*.txt），从中为每个程序随机指定一至三个作为输入文件 （被测试者需从键盘输入指定文件的文件名），并查看程序输出结果。 6 第二次机会算法：对FIFO算法做如下简单的修改：发生替换时，先检查最老页面的R（访问）位。如果为0， 那么此页面是最早被换入的，而且近期没有被访问，可以立刻被替换掉；如果R位为1，就清除R位，并修改它的装入时间， 使它就像刚被装入的新页面一样，然后继续搜索可替换的最老页面。 我没做出来页面调度算法主要有：FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU），最佳算法（OPT） 这几种算法的调度都有可能在考试中碰到。 关于这一类型，大家还可以参看书本251页的实验指导。 如2001年考题： 要求：1。实现三种算法： FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU）2。页面序列从指定的文本文件（TXT文件）中取出3。输出：第一行：每次淘汰的页面号第二行：显示缺页的总次数本程序包括 :FIFO ，最近最少使用调度算法（ LRU ），最近最不常用调度算法（ LFU ） 第二次机会算法 #include #include #include const int MAXSIZE=1000;/定义最大页面数 const int MAXQUEUE=3;/定义页框数 typedef struct node int loaded; int hit; page; page pagesMAXQUEUE; /定义页框表 int queueMAXSIZE; int quantity; /初始化结构函数 void initial() int i; for(i=0;iMAXQUEUE;i+) pagesi.loaded=-1; pagesi.hit=0; for(i=0;iMAXSIZE;i+) queuei=-1; quantity=0; /初始化页框函数 void init() int i; for(i=0;iMAXQUEUE;i+) pagesi.loaded=-1; pagesi.hit=0; /读入页面流 void readData() FILE *fp; char fname20; int i; coutfname; if(fp=fopen(fname,r)=NULL) cout错误,文件打不开,请检查文件名; else while(!feof(fp) fscanf(fp,%d ,&queuequantity); quantity+; cout读入的页面流:; for(i=0;iquantity;i+) coutqueuei ; /FIFO调度算法 void FIFO() int i,j,p,flag; int absence=0; p=0; coutendl-endl; coutFIFO调度算法页面调出流:; for(i=0;iquantity;i+) flag=0; for(j=0;j=MAXQUEUE) coutpagesp.loaded ; pagesp.loaded=queuei; p=(p+1)%MAXQUEUE; absence+; absence-=MAXQUEUE; coutendl总缺页数:absenceendl; /最近最少使用调度算法（LRU） void LRU() int absence=0; int i,j; int flag; for(i=0;iMAXQUEUE;i+) pagesi.loaded=queuei; coutendl-endl; cout最近最少使用调度算法(LRU)页面流:; for(i=MAXQUEUE;iquantity;i+) flag=-1; for(j=0;jMAXQUEUE;j+) if(queuei=pagesj.loaded) flag=j; /CAUTION pages0是队列头 if(flag=-1) /缺页处理 coutpages0.loaded ; for(j=0;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1.loaded=queuei; absence+; else /页面已载入 pagesquantity=pagesflag; for(j=flag;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1=pagesquantity; coutendl总缺页数:absenceendl; /最近最不常用调度算法(LFU) void LFU() int i,j,p; int absence=0; int flag; for(i=0;iMAXQUEUE;i+) pagesi.loaded=queuei; coutendl-endl; cout最近最不常用调度算法(LFU)页面流:; for(i=MAXQUEUE;iquantity;i+) flag=-1; for(j=0;jMAXQUEUE;j+) if(pagesj.loaded=queuei) flag=1; pagesj.hit+; if(flag=-1) /缺页中断 p=0; for(j=0;jMAXQUEUE;j+) if(pagesj.hitpagesp.hit) p=j; coutpagesp.loaded ; pagesp.loaded=queuei; for(j=0;jMAXQUEUE;j+) pagesj.hit=0; absence+; coutendl总缺页数:absenceendl; /第二次机会算法 void second() int i,j,t; int absence=0; int flag,temp; for(i=0;iMAXQUEUE;i+) pagesi.loaded=queuei; coutendl-endl; cout第二次机会算法页面流:; for(i=MAXQUEUE;iquantity;i+) flag=-1; for(j=0;jMAXQUEUE;j+) if(pagesj.loaded=queuei) flag=1; pagesj.hit=1; if(flag=-1) /缺页处理 t=0; while(t=0) if(pages0.hit=0) coutpages0.loaded ; for(j=0;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1.loaded=queuei; pagesMAXQUEUE-1.hit=0; t=1; else temp=pages0.loaded; for(j=0;jMAXQUEUE-1;j+) pagesj=pagesj+1; pagesMAXQUEUE-1.loaded=temp; pagesMAXQUEUE-1.hit=0; absence+; coutendl总缺页数:absenceendl; /显示版权信息函数 void version() coutendlendl; cout endl; cout 虚拟存储管理器的页面调度 endl; cout endl; cout (c)All Right Reserved Neo endl; cou