搜索
#includestdlib.h#includestdio.h#definepagesize8//页面尺寸大小typedefstructBLOCK//声明一种新类型--物理块类型{intpagenum;//页号intaccessed;//访问量，其值表示多久未被访问}BLOCK;intpc;//程序计数器，用来记录对应的页号intn;//缺页计数器，用来记录缺页的次数staticintnum[320];//用来存储320条随机数BLOCKblock[pagesize];//定义一大小为8的物理块数组voidinit();//程序初始化函数intfindExist(intcurpage);//查找物理块中是否有该页面intfindSpace();//查找是否有空闲物理块intfindReplace();//查找应予置换的页面voiddisplay();//显示voidrandam();//产生320条随机数,显示并存储到num[320]voidpagestring();//显示调用的页面队列voidOPT();voidLRU();voidFIFO();voidmain(){intselect;printf(请输入第一个随机数(0~320):);randam();printf(*****对应的调用页面队列*******\n);pagestring();do{printf(****************************************\n);printf(------1:OPT2:LRU3:FIFO4:退出-----\n);printf(****************************************\n);printf(请选择一种页面置换算法:);scanf(%d,&select);printf(*******************************\n);init();switch(select){case1:printf(最佳置换算法OPT:\n);printf(*****************\n);OPT();break;case2:printf(最近最久未使用置换算法LRU:\n);printf(*************************\n*);LRU();break;case3:printf(先进先出置换算法FIFO:\n);printf(*********************\n);FIFO();break;}}while(select!=4);}voidinit(){for(inti=0;ipagesize;i++){block[i].pagenum=-1;block[i].accessed=0;pc=n=0;}}intfindExist(intcurpage){for(inti=0;ipagesize;i++){if(block[i].pagenum==curpage)returni;//检测到内存中有该页面，返回block中的位置}return-1;}intfindSpace(){for(inti=0;ipagesize;i++){if(block[i].pagenum==-1)returni;//找到空闲的block，返回block中的位置}return-1;}intfindReplace(){intpos=0;for(inti=0;ipagesize;i++){if(block[i].accessedblock[pos].accessed)pos=i;//找到应该置换页面，返回BLOCK中位置}returnpos;}voiddisplay(){for(inti=0;ipagesize;i++){if(block[i].pagenum!=-1){printf(%02d,block[i].pagenum);}}printf(\n);}voidrandam(){intflag=0;scanf(%d,&pc);printf(******按照要求产生的320个随机数：*******\n);for(inti=0;i320;i++){num[i]=pc;if(flag%2==0)pc=++pc%320;if(flag==1)pc=rand()%(pc-1);if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));flag=++flag%4;printf(%03d,num[i]);if((i+1)%10==0)printf(\n);}}voidpagestring()//显示调用的页面队列,页面号取法为随机数除10取整{for(inti=0;i320;i++){printf(%02d,num[i]/10);if((i+1)%10==0)printf(\n);}}voidOPT()//最佳替换算法{intexist,space,position;intcurpage;for(inti=0;i320;i++){pc=num[i];curpage=pc/10;exist=findExist(curpage);if(exist==-1){space=findSpace();if(space!=-1){block[space].pagenum=curpage;display();n=n+1;}else{for(intk=0;kpagesize;k++){for(intj=i;j320;j++){if(block[k].pagenum!=num[j]/10){block[k].accessed=1000;}//将来不会用，设置为一个很大数else{block[k].accessed=j;break;}}}position=findReplace();block[position].pagenum=curpage;display();n++;}}}printf(缺页次数:%d\n,n);printf(缺页率:%f%%\n,(n/320.0)*100);}voidLRU()//最近最久未使用算法{intexist,space,position;intcurpage;for(inti=0;i320;i++){pc=num[i];curpage=pc/10;exist=findExist(curpage);if(exist==-1){space=findSpace();if(space!=-1){block[space].pagenum=curpage;display();n=n+1;}else{position=findReplace();block[position].pagenum=curpage;display();n++;}}elseblock[exist].accessed=-1;//恢复存在的并刚访问过的BLOCK中页面accessed为-1for(intj=0;jpagesize;j++){block[j].accessed++;}}printf(缺页次数:%d\n,n);printf(缺页率:%f%%\n,(n/320.0)*100);}voidFIFO()//先进先出算法{intexist,space,position;intcurpage;for(inti=0;i320;i++){pc=num[i];curpage=pc/10;//转换为页面号exist=findExist(curpage);//查找物理块中是否有该页面,没有的话，置为-1if(exist==-1){space=findSpace();//查找是否有空的物理块，没有的话，置为-1；有的话，把位置返回if(space!=-1){block[space].pagenum=curpage;display();n=n+1;}else{position=findReplace();//没有空闲物理块，进行置换block[position].pagenum=curpage;display();n++;block[position].accessed--;}}for(intj=0;jpagesize;j++)//把所有在页面里的页面号的访问次数加1block[j].accessed++;}printf(缺页次数:%d\n,n);printf(缺页率:%f%%\n,(n/320.0)*100);}