计算机操作系统试验模拟比较面置换算法及缺率

1、成绩计算机操作系统实验模拟比较页面置换页算法及缺页率200510020220乔峰信息052实验名称 : 模拟比较页面置换页算法及缺页率实验目的 : (1)掌握先进先出页面置换算法；(2)掌握最近未用页面置换算法；(3)了解 最近最久未使用页面置换算法以及其他页面置换算法 ； (4)熟悉C/C+编程。实验学时 ： 6 学时实验内容 : 编写程序，设置不同的页面数，使用不同的页面替换策略算法进行 模拟页面替换。先进先出，最近未用页面置换算法等，并计算缺页 率。实验环境 :.PC微机(2) Windows 操作系统(3) . C/C+开发环境实验原理及算法参考程序段 :#include <co

2、nio.h>#include <stdio.h>#include <dos.h>#include <stdlib.h>#include <math.h> 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);/* 先进先出 */floa

3、t LRU(int ram);/* 最近最久未使用页面置换 */void address()/* 产生指令地址 */ int i;add0=1000;for (i=1; i<=255; i+) int x=random(1024);if (x>=0)&&(x<512) addi=addi-1+1;if (x>=512)&&(x<768) addi=random(addi-1-1)+1;if (x>=768)&&(x<1024) addi=addi-1+random(30*1024-addi-1-1)+1;

4、float FIFO(int ram) int absent=0,t=0,i,z,l,yn;for (i=0; i<ram; i+) fifoi.page=-1; fifoi.free=1; fifoi.tag=0;i=0;while (i<j) yn=0;for (z=0; z<ram; z+) /*the page is in the ram?*/if (fifoz.page=pagei)yn=1;for (z=0; z<ram; z+)if (fifoz.free=0) fifoz.tag+=1; if (yn!=1) absent+=1; /*count the

5、 absent page*/l=0;while (l<ram)&&(fifol.free=0)l+;if (l<ram)&&(fifol.free=1) /*any free ram?*/ fifol.page=pagei;fifol.free=0;for (l=0; l<ram; l+)if (fifol.free=0 ) fifol.tag+=1;else /*there is no free ram*/ t=0;for (l=0; l<ram; l+)if ( fifol.tag<fifot.tag)t=l;fifot.pag

6、e=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;i<j;i+)Pi.time=0;for (i=0; i<ram; i+) lrui.page=-1;lrui.free=1;i=0;while(i<j) for(l=0; l<ram; l+)yn=0; for(z=0; z<ram; z+)if (lruz.page

7、=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; l<ram; l+)if ( Plrul.page.time<Plru

8、t.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; i<256; i+)

9、pi=addi/(k*1024);/* 将指令地址生成相应的页号 */ printf("%d ",pi);j=0;for (i=0; i<256; i+) while (pi=pi+1)i+;pagej=pi;j+;printf("nafter connect the same pages the page num is:n");for (i=0; i<j; i+)printf("%d ",pagei);printf("n");getch();for (ram=1; ram<=32; ram+)

10、if (ram=10) getch();printf("nblock=%d pages= %d,absent rate: ",ram,j); printf("FIFO=%0.2f%",FIFO(ram);printf("LRU =%0.2f%",LRU(ram);printf("OPT =%0.2f%",OPT(ram);k=k*2;getch();实验小结：通过本次实验掌握了先进先出和最近最久未使用页面置换算法， 同时也对其他的页面 置换算法也更加熟悉。在实验过程中熟悉了C 语言的编程环境 ,并能够用 C 编程模

11、拟比较也面置换算法，对编程也有一定的提高。代码：#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "ctype.h"/ 定义页 ,采用双向链表存储结构struct pageunsigned int number;/ 页号un sig ned int baseaddress;/页开始地址/其它信息struct page *nextpage,*priorpage;/ 下一页和前一页;/定义页表struct pagetableunsigned

12、int pid ;/进程号un sig ned int page num;/ 页表大小un sig ned int pagetablesize;/ 页表最大表目struct page *head;页表头指针，指向头结点，头结点指向第一页;/FIFO页面访问程序，函数调用时要传递过来页表pt，要访问的页面号 accesspage返回是否发生缺页中断（ 1 是 0 否）int access(struct pagetable *pt, unsigned int accesspage) struct page *newpage;/ 新页面struct page *currentpage=pt->

13、head->nextpage;/ 当前页struct page * replacedpage;/ 要淘汰的页/在当前页中寻找要访问的页号 while(currentpage&&currentpage->number!=accesspage) currentpage=currentpage->nextpage;找到页号则打印"并返回0if(currentpage!=NULL&&currentpage->number=accesspage) printf(” V”)； return 0;没找到则判断页表是否已经满了，没满则调入新页并

14、打印x返回1else if(pt->pagenum<pt->pagetablesize) 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=

15、newpage； pt->head->nextpage=newpage； newpage->priorpage=pt->head； pt->pagenum+；printf(" ")；xreturn 1;/如页表已经满 ,则采用 fifo 算法进行淘汰选择elsecurrentpage=pt->head->nextpage;replacedpage=NULL;while(currentpage->nextpage) currentpage=currentpage->nextpage;replacedpage=current

16、page;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-

17、>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(” ”);xreturn 1;main()struct pagetable pt;unsigned int totalabsence=0,totalpagenum=1

18、0;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;i<totalpag