计算机操作系统实验模拟比较页面置换页算法及缺页率(1).doc

成绩计算机操作系统实验模拟比较页面置换页算法及缺页率学 号200510020220姓 名乔 峰班 级信息052实验名称: 模拟比较页面置换页算法及缺页率实验目的: （1）掌握先进先出页面置换算法；（2）掌握最近未用页面置换算法；（3）了解最近最久未使用页面置换算法以及其他页面置换算法；（4）熟悉C/C+编程。实验学时： 6学时 实验内容: 编写程序，设置不同的页面数，使用不同的页面替换策略算法进行模拟页面替换。先进先出，最近未用页面置换算法等，并计算缺页率。实验环境:(1)PC微机(2)Windows 操作系统(3)C/C+开发环境实验原理及算法参考程序段:#include #include #include #include #include int add256/*地址*/,page256/*页面*/;int k,j,ram,t;float rate;/*缺页率*/struct s1 int page; int free; int tag; fifo33,opt33,lru33;struct s2 int time;void address();float FIFO(int ram);/*先进先出*/float LRU(int ram);/*最近最久未使用页面置换*/void address() /*产生指令地址*/ int i; add0=1000; for (i=1; i=0)&(x=512)&(x=768)&(x1024) addi=addi-1+random(30*1024-addi-1-1)+1; float FIFO(int ram) int absent=0,t=0,i,z,l,yn; for (i=0; iram; i+) fifoi.page=-1; fifoi.free=1; fifoi.tag=0; i=0; while (ij) yn=0; for (z=0; zram; z+) /*the page is in the ram?*/if (fifoz.page=pagei) yn=1; for (z=0; zram; z+) if (fifoz.free=0) fifoz.tag+=1; if (yn!=1) absent+=1; /*count the absent page*/ l=0; while (lram)&(fifol.free=0) l+; if (lram)&(fifol.free=1) /*any free ram?*/ fifol.page=pagei; fifol.free=0; for (l=0; lram; l+) if (fifol.free=0 ) fifol.tag+=1; else /*there is no free ram*/ t=0; for (l=0; lram; l+)if ( fifol.tagfifot.tag) t=l; fifot.page=pagei; fifot.free=0; fifot.tag=1; l=0; i+; rate=(float)absent/j*100; return rate;float LRU(int ram) int absent=0,yn,t,i,l,z,now=0; struct s2 P250; for (i=0;ij;i+) Pi.time=0; for (i=0; iram; i+) lrui.page=-1; lrui.free=1; i=0; while(ij) for(l=0; lram; l+) yn=0; for(z=0; zram; z+) if (lruz.page=pagei) now+=1; Plruz.page.time=now; yn=1; if (yn!=1) absent+=1; now+=1; l=0; while (l=ram)&(lrul.free=0) l+; if (l=ram)&(lrul.free=1) /*any free ram?*/ lrul.page=pagei; Plrul.page.time=now; lrul.free=0; else /*there is no ram*/ t=0; for (l=0; lram; l+) if ( Plrul.page.timePlrut.page.time) t=l; lrut.page=pagei; Plrut.page.time=now; i+; rate=(float)absent/j*100; return rate;void main() int i,p256;/*页号*/ clrscr(); address(); for (k=1; k=8;) /*页面大小: 1k,2k,4k,8K*/ printf(the size of a page is %d kn ,k); printf(the page num is .n); for (i=0; i256; i+) pi=addi/(k*1024);/*将指令地址生成相应的页号*/ printf(%d ,pi); j=0; for (i=0; i256; i+) while (pi=pi+1) i+; pagej=pi; j+; printf(nafter connect the same pages the page num is:n); for (i=0; ij; i+) printf(%d ,pagei); printf(n); getch(); for (ram=1; ramhead-nextpage;/当前页struct page * replacedpage;/要淘汰的页/在当前页中寻找要访问的页号while(currentpage¤tpage-number!=accesspage)currentpage=currentpage-nextpage;/找到页号则打印,并返回0if(currentpage!=NULL¤tpage-number=accesspage)printf();return 0;/没找到则判断页表是否已经满了,没满则调入新页并打印返回1else if(pt-pagenumpagetablesize)newpage=(struct page *)malloc(sizeof(struct page);newpage-number=accesspage;newpage-nextpage=newpage-priorpage=NULL;newpage-nextpage=pt-head-nextpage;if(pt-head-nextpage)pt-head-nextpage -priorpage=newpage;pt-head-nextpage=newpage;newpage-priorpage=pt-head;pt-pagenum+;printf();return 1;/如页表已经满,则采用fifo算法进行淘汰选择elsecurrentpage=pt-head-nextpage;replacedpage=NULL;while(currentpage-nextpage)currentpage=currentpage-nextpage;replacedpage=currentpage;if(replacedpage-nextpage)replacedpage-nextpage-priorpage=replacedpage-priorpage;replacedpage-priorpage-nextpage=replacedpage-nextpage;free(replacedpage);newpage=(struct page *)malloc(sizeof(struct page);newpage-number=accesspage;newpage-nextpage=newpage-priorpage=NULL;newpage-nextpage=pt-head-nextpage; if(pt-head-nextpage)pt-head-nextpage-priorpage=newpage;pt-head-nextpage=newpage;newpage-priorpage=pt-head;printf();return 1;main()struct pagetable pt;unsigned int totalabsence=0,totalpagenum=10;unsigned int restpage100;unsigned int i=0;pt.pagenum=0;pt.pagetablesize=3;pt.head=(struct page*)malloc(sizeof(struct page);pt.head-nextpage=pt.head-priorpage=NULL;/从文件获取要读入的页面流FILE *fp;fp=fopen(IN.dat,r);if(fp=NULL)printf(can not open file IN.DAT!);return;while(!feof(fp)fscanf(fp,%d,&restpagei);i+;fclose(fp);totalpagenum=i;printf(this program for fifo nn);/打印要访问的页for(i=0;itotalpagenum;i+)printf(%2d,restpagei);printf(