clock-置换算法

//#includeStdAfx.h#includestdio.h#includetime.h#includestdlib.h#defineM3//内存物理块数#defineN20//虚拟内存尺寸intP;//工作集的起始位置intnin;//记录缺页次数//用于CLOCK算法的页面定义typedefstructpage_clock{intnum;intvisit;}Page_clock;//用于改进的CLOCK算法的页面定义typedefstructpage{intnum;//页面号intvisit;//是否访问intmodify;//是否修改}Page;Page_clockb_clock[M];//内存单元数//ClockPageb[M];//updating_clockintopt[M];//optintran[M];//randomreplacementintfifo[M];//FIFOintc[M][N];//存储每个阶段状态//访问序列随机生成e个，e是工作集中包含的页数，m是工作集移动率voidgenerate_list(int*list,inte,intm,intt){inti,j=0,q=P,r;srand((unsigned)time(NULL));while(je){for(i=j;ij+m;i++){if(i==e)break;list[i]=(q+rand()%e)%N;/*保证在虚拟内存的页号内*/}j=i;r=rand()%100;if(rt)q=rand()%N;elseq=(q+1)%N;}}//随机生产是否被修改的情况，prop(0...100)，prop/100的概率未被修改voidgenerate_modify(int*mo,inte,intprop){inti,t;for(i=0;ie;i++){t=rand()%100;if(tprop)mo[i]=0;elsemo[i]=1;}}//格式输出voidprint_format(inte){inti;printf();for(i=1;ie;i++)printf();printf(\n);}//Clock算法voidClock(intfold,Page_clock*b_clock){inti,val=-1,p=0;//p为查询指针for(i=0;iM;i++){if(fold==b_clock[i].num)val=i;}//页面在内存中if(val=0){b_clock[val].visit=1;for(i=0;iM;i++){if(i!=val){b_clock[i].visit=0;}}}else{nin++;//初始化内存for(i=0;iM;i++){if(b_clock[i].num==-1){val=i;break;}}while(val0){if(b_clock[p].visit==0)val=p;elseb_clock[p].visit=0;p=(p+1)%M;}b_clock[val].num=fold;b_clock[val].visit=1;for(i=0;iM;i++){if(i!=val){b_clock[i].visit=0;}}}}//改进的Clock算法voidUpdating_Clock(intfold,intmodiff,Page*b){inti,p=-1;//p是查询指针intval=-1;//找是否在内存中for(i=0;iM;i++){if(fold==b[i].num)val=i;}if(val=0){b[val].visit=1;//被访问b[val].modify=modiff;for(i=0;iM;i++){if(i!=val){b[i].visit=0;}}}else{nin++;//初始化内存for(i=0;iM;i++){if(b[i].num==-1){val=i;break;}}while(val0){//第一步扫描for(i=0;iM;i++){p=(p+1)%M;if((b[p].modify==0)&&(b[p].visit==0)){val=p;break;}}//第二步扫描if(val0){for(i=0;iM;i++){p=(p+1)%M;if((b[p].modify==1)&&(b[p].visit==0)){val=p;break;}else{b[p].visit=0;}}}}//找到后，其他设置为未访问b[val].num=fold;b[val].modify=modiff;b[val].visit=1;for(i=0;iM;i++){if(i!=val){b[i].visit=0;}}}}//主程序voidmain(){inta[N];intmo[N];inti,j;//产生随机访问串及是否修改串P=1;inte,m,prop,t;printf(请输入工作集中包含的页数e和工作集移动率m:\n);scanf(%d%d,&e,&m);t=50;generate_list(a,e,m,t);printf(请输入页面被修改的概率(*100):\n);scanf(%d,&prop);generate_modify(mo,e,prop);//Clock算法实现Init_Clock(b_clock);for(i=0;ie;i++){Clock(a[i],b_clock);for(j=0;jM;j++){c[j][i]=b_clock[j].num;}}printf(Clock算法的内存状态为：\n);print(e,a);nin=nin-M;printf(缺页次数为：%d\n缺页率：%.2f\n,nin,nin*1.0/e);printf(\n);/改的Clock算法实现Init_updatingClock(b);for(i=0;ie;i++){Updating_Clock(a[i],mo[i],b);for(j=0;jM;j++){c[j][i]=b[j].num;}}printf(改进的Clock算法的内存状态为：\n);print(e,a);for(j=0;je;j++){printf(%2d,mo[j]);//是否修改序列串}printf(\n);print_format(e);nin=nin-M;printf(缺页次数为：%d\n缺页率：%.2f\n,nin,nin*1.0/e);printf(\n);}