2022年C实现操作系统的OptimalFIFOLRU算法 .pdf
/zzzzz.cpp:定义控制台应用程序的入口点。/#include#define M 4/物理页数#define N 15/需要调入的页数#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-|n)/表格控制typedef struct page int num;int time;Page;/物理页项，包括调入的页号和时间Page mmM;/4 个物理页int aaMN;/用于存储每次置换后内存的情况int queue20;/记录置换的页int K=0;/置换页数组的标识int pos=0;/记录存在最长时间项int AN=1,0,1,0,2,4,1,0,0,5,4,3,2,3,4;/15个数/初始化内存页表项及存储内存情况的空间void INIT()int i,j;for(i=0;iM;i+)mmi.num=-1;mmi.time=0;for(i=0;iM;i+)for(j=0;jN;j+)aaij=-1;/取得内存中存在时间最久的位置int GetMax()int max=-1;int i,j;for(i=0;i max)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -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;/内存已满/求最长时间将不会被使用的页面int distance(int a)int x=0,y;int i,j,k=a;int Max4;/存放最大的距离，下标表示要返回的页面for(i=0;iM;i+)for(j=k;jN;j+)if(j=14)return i;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -if(mmi.num=Aj)Maxi=j;break;for(i=0;i4;i+)if(xMaxi)x=Maxi;y=i;return y;/先进先出void FIFO(int fold)int i;int a,b,c;a=Equation(fold);/页已存在if(a!=-1)/一次调度完成后时间加1 /return a;/页不存在else b=Check();/内存还有空闲if(b!=-1)mmb.num=fold;/内存已满，需要置换else c=GetMax();名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -mmc.num=fold;mmc.time=0;queueK+=fold;/记录缺页次数，存在于页不在内存的情况下。for(i=0;iM;i+)/每次置换完成之后所有存在的页时间加1 if(mmi.num!=-1)mmi.time+;void LRU(int fold)int i;int a,b;int temp,p;a=Equation(fold);if(a!=-1)/页已在内存/把此项移动到链表最后一项if(a=3)/此项已经在最后，不需要做任何改动return;else p=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;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -else/页不在内存 b=Check();if(b!=-1)/不满mmb.num=fold;else for(i=0;i3;i+)mmi.num=mmi+1.num;mm3.num=fold;queueK+=fold;void Optimal(int fold,int x)int a,b,c,y;y=x;a=Equation(fold);/页已存在if(a!=-1)/页不存在else b=Check();/内存还有空闲if(b!=-1)mmb.num=fold;/内存已满，需要置换else c=distance(y);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -mmc.num=fold;queueK+=fold;/记录缺页次数，存在于页不在内存的情况下。void main()int i,j;char s;INIT();printf(请选择：F/f-FIFO置换算法 n);printf(L/l-LRU置换算法 n);printf(O/o-LRU置换算法 n);scanf(%c,&s);if(s=F|s=f)for(i=0;iN;i+)FIFO(Ai);aa0i=Ai;for(j=0;jM;j+)aaji=mmj.num;/页面号 else if(s=L|s=l)for(i=0;iN;i+)LRU(Ai);aa0i=Ai;for(j=0;jM;j+)aaji=mmj.num;else if(s=O|s=o)/optimal 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -for(i=0;iN;i+)Optimal(Ai,i);aa0i=Ai;for(j=0;jM;j+)aaji=mmj.num;/页面号 else return;/输出结果printf(内存状态为：n);Myprintf;for(j=0;jN;j+)printf(|%2d,Aj);printf(|n);Myprintf;for(i=0;iM;i+)for(j=0;jN;j+)if(aaij=-1)printf(|%2c,32);else printf(|%2d,aaij);printf(|n);Myprintf;printf(n 调入队列为：);for(i=0;iK;i+)printf(%3d,queuei);printf(n 缺页次数为：%6dn 缺页率：%16.6f,K,(float)K/N);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -
