页面置换算法代码实现(完整版)

实验原理：在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将那个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法成为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。实验目的：1．熟悉FIFO，OPT和LRU算法2．比较三种算法的性能优劣实验内容：写出FIFO，OPT和LRU算法的程序代码，并比较它们的算法性能。实验步骤：代码如下：#includestdio.h#defineM4//物理页数#defineN20//需要调入的页数typedefstructpage{intnum;inttime;}Page;//物理页项，包括调入的页号和时间Pagemm[M];//4个物理页intqueue1[20],queue2[20],queue3[20];//记录置换的页intK=0,S=0,T=0;//置换页数组的标识intpos=0;//记录存在最长时间项//初始化内存页表项及存储内存情况的空间voidINIT(){inti;for(i=0;iM;i++){mm[i].num=-1;mm[i].time=0;}}//取得内存中存在时间最久的位置intGetMax(){intmax=-1;inti;for(i=0;iM;i++){if(mm[i].timemax){max=mm[i].time;pos=i;}}returnpos;}//检查最长时间不使用页面intlongesttime(intfold){inti;intmax=-1;for(i=fold;iN;i++){if(mm[0].num!=i){mm[0].time++;}if(mm[1].num!=i){mm[1].time++;}if(mm[2].num!=i){mm[2].time++;}if(mm[3].num!=i){mm[3].time++;}}for(i=0;iM;i++){if(mm[i].timemax){max=mm[i].time;pos=i;}}returnpos;}//检查某页是否在内存intEquation(intfold){inti;for(i=0;iM;i++){if(mm[i].num==fold)returni;}return-1;}//检查物理内存是否已满,-1表满，其他不满intCheck(){inti;for(i=0;iM;i++){if(mm[i].num==-1)returni;}return-1;}//先进先出voidFIFO(intfold){inti;inta,b,c;a=Equation(fold);//页已存在if(a!=-1){}//页不存在else{b=Check();//内存还有空闲if(b!=-1){mm[b].num=fold;}//内存已满，需要置换else{c=GetMax();mm[c].num=fold;mm[c].time=0;}queue1[K++]=fold;}for(i=0;iM;i++){if(mm[i].num!=-1){mm[i].time++;}}}voidOPT(intfold){inta,b,c;a=Equation(fold);if(a==-1){//页不在内存b=Check();//内存还有空闲if(b!=-1){mm[b].num=fold;}//内存已满，需要置换else{c=longesttime(fold);mm[c].num=fold;mm[c].time=0;}queue3[T++]=fold;}}voidLRU(intfold){inti;inta,b;intp;a=Equation(fold);if(a!=-1)//页已在内存{//把此项移动到链表最后一项if(a==3)//此项已经在最后，不需要做任何改动return;else{p=Equation(-1);if(p==-1)//链表是满的{for(;a3;a++)mm[a].num=mm[a+1].num;mm[3].num=fold;}elseif(p=3)//链表不满{for(;ap-1;a++)mm[a].num=mm[a+1].num;mm[a].num=fold;}}}else{b=Check();if(b!=-1)//不满mm[b].num=fold;else{for(i=0;i3;i++)mm[i].num=mm[i+1].num;mm[3].num=fold;}queue2[S++]=fold;}}voidmain(){intA[N],B[N];inti;INIT();printf(请依次输入%d个页面号：\n,N);for(i=0;iN;i++){scanf(%d,&A[i]);}//FIFOfor(i=0;iN;i++){B[i]=A[i];}for(i=0;iN;i++){FIFO(B[i]);}printf(FIFO的);printf(调入队列为：);for(i=0;iK;i++)printf(%3d,queue1[i]);printf(\n缺页次数为：%6d\n缺页率：%16.6f\n\n,K,(float)K/N);//LRUINIT();for(i=0;iN;i++){B[i]=A[i];}for(i=0;iN;i++){LRU(B[i]);}printf(LRU的);printf(调入队列为：);for(i=0;iS;i++)printf(%3d,queue2[i]);printf(\n缺页次数为：%6d\n缺页率：%16.6f\n\n,S,(float)S/N);//OPTINIT();for(i=0;iN;i++){B[i]=A[i];}for(i=0;iN;i++){OPT(B[i]);}printf(OPT的);printf(调入队列为：);for(i=0;iT;i++)printf(%3d,queue3[i]);printf(\n缺页次数为：%6d\n缺页率：%16.6f\n\n,T,(float)T/N);}