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

1、实验原理：在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时， 为了保证该进程能正常运行， 系统必须从内存中调出一页程序或数据送磁盘的对换区中。 但应将那个页面调出， 需根据一定的算法来确定。通常，把选择换出页面的算法成为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法， 应具有较低的页面更换频率。 从理论上讲， 应将那些以后不再会访问的页面置换出， 或者把那些在较长时间内不会在访问的页面调出。目前存在着许多种置换算法（如 FIFO，OPT，LRU ），他们都试图更接近理论上的目标。实验目的：1熟悉 FIFO，OPT 和 LRU

2、 算法2比较三种算法的性能优劣实验内容：写出 FIFO，OPT 和 LRU 算法的程序代码，并比较它们的算法性能。实验步骤：代码如下：#include #define M 4/物理页数#define N 20/需要调入的页数typedef struct pageint num;int time;Page;/物理页项，包括调入的页号和时间Page mmM;/4 个物理页int queue120,queue220,queue320;/记录置换的页 int K=0,S=0,T=0; /置换页数组的标识 int pos=0;/记录存在最长时间项/初始化内存页表项及存储内存情况的空间.void INIT

3、()int i;for(i=0;iM;i+)mmi.num =-1;mmi.time =0;/取得内存中存在时间最久的位置int GetMax()int max=-1;int i;for(i=0;i max)max=mmi.time ;pos=i;return pos;/检查最长时间不使用页面int longesttime(int fold)int i;int max=-1;for(i=fold;iN;i+)if(mm0.num!=i)mm0.time+;if(mm1.num!=i)mm1.time+;.if(mm2.num!=i)mm2.time+;if(mm3.num!=i)mm3.tim

4、e+;for(i=0;imax)max=mmi.time;pos=i;return pos;/检查某页是否在内存int Equation(int fold)int i;for(i=0;iM;i+)if(mmi.num = fold)return i;return -1;/检查物理内存是否已满 ,-1 表满，其他不满int Check()int i;for(i=0;iM;i+)if(mmi.num = -1).return i;return -1;/先进先出void FIFO(int fold)int i;int a,b,c;a=Equation(fold);/页已存在if(a != -1)/页

5、不存在elseb=Check();/内存还有空闲if(b != -1)mmb.num = fold;/内存已满，需要置换else c=GetMax();mmc.num = fold;mmc.time = 0;queue1K+=fold;for(i=0;iM;i+)if(mmi.num != -1)mmi.time +;.void OPT(int fold)int a,b,c;a=Equation(fold);if(a = -1)/ 页不在内存b=Check();/内存还有空闲if(b != -1)mmb.num = fold;/内存已满，需要置换elsec=longesttime(fold);

6、mmc.num = fold;mmc.time = 0;queue3T+=fold;void LRU(int fold)int i;int a,b;int p;a=Equation(fold);if(a != -1)/ 页已在内存./把此项移动到链表最后一项if(a=3)/ 此项已经在最后，不需要做任何改动return;elsep=Equation(-1);if(p=-1)/ 链表是满的for(;a3;a+)mma.num=mma+1.num;mm3.num=fold;else if(p=3)/ 链表不满for(;ap-1;a+)mma.num=mma+1.num;mma.num=fold;e

7、lseb=Check();if(b!=-1)/ 不满mmb.num=fold;elsefor(i=0;i3;i+)mmi.num=mmi+1.num;mm3.num=fold;.queue2S+=fold;void main()int AN,BN;int i;INIT();printf( 请依次输入 %d 个页面号： n,N);for(i=0;iN;i+)scanf(%d,&Ai);/FIFOfor(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)FIFO( Bi );printf(FIFO 的);printf( 调入队列为： );for(i=0;iK;i+)printf(%3d,queue1i);printf(n 缺页次数为： %6dn 缺页率： %16.6fnn,K,(float)K/N);/LRUINIT();for(i=0;iN;i+)Bi=Ai;.for(i=0;iN;i+)LRU( Bi );printf(LRU 的 );printf( 调入队列为： );for(i=0;iS;i+)printf(%3d,queue2i);printf(n 缺页次数为： %6dn 缺页率： %16.6fnn,S,(float)S/N);/OPTINIT();for(i=0;iN;i+)Bi=Ai;for(i=0;iN;i+)O