操作系统报告-最近最久未使用置换算法

操作系统课程报告最近最久未使用置换算法学号 姓名 班级 华侨大学电子工程系设计内容假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：3,5,1,2,3,1,5,1,2,3,4,1,3,1,5,2（按各自数据来填写）。模拟分页式存储管理中硬件地址转换和产生缺页中断，用最近最久未使用置换算法处理缺页中断，求出每次物理块的存储情况，并与“最优”置换算法进行置换次数的对比。报告内容1、算法的基本原理。答：1＞最近最久未使用置换算法最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有也面中t值最大的，即最近最久未使用的页面予以淘汰。2＞最佳（Optimal）置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。2、程序流程图。1＞最近最久未使用置换算法

开始页面是否存在物理块是否空闲式页面长度2＞最佳(Optimal)置换算法YNYY选择以后最长时间内不再被访问的页面作为淘汰页将页面放到空闲的物理块处输入页面序列输入物理块数N计算缺页率，并输出数据输出当前页面，i++开始页面是否存在物理块是否空闲式页面长度2＞最佳(Optimal)置换算法YNYY选择以后最长时间内不再被访问的页面作为淘汰页将页面放到空闲的物理块处输入页面序列输入物理块数N计算缺页率，并输出数据输出当前页面，i++i指向下一个页初始化数据结束3、程序及注释。1＞最近最久未使用置换算法ttinclude<stdio.h>ttinclude<conio.h>ttdeFineM3ttdefineN28ttdeFineMyprintfprtypedefstructpage<intnum;inttime;JPage;pageb[M];intc[M][N];intqueue[100];intK;表格控制*/*/内构*/当号久结计页调辑元内介录录逻单存调队/*-/*-页摩响嘴*/为-日才-Hn',存，状*/的*/量前列变，*初始化内存单元，缓存区*，uoidinit(Page*b,intC[M][N])inti,j;For(i=0;i<N;i++)b[i].num=-1;b[i].tinie=N-i-1;For(i=0;i<M;i++)For(j=0;j<N;j++)c[i][j]=-1；取得在内存中停留最久的页面，默认状态下为最早调入的页面*，intGeMax(Page*b)<inti;intmax=-1;inttag=O;for(i=0;i<M;i++)iF(b[i].time>max)max=b[i].time;tag=i;returntag;/共关断页面是否已在内存中关/intEquation(intFold,Page*b)<inti;For(i=8;i<M;i++)<if(Fold==b[i].nun)returni;>return-1;>/关LRU核心部分关/uoidLru(intFold,Page*b)<inti;intual;ual=Equation(Fold,b);iF(ual>=0)<b[ual].time=0;For(i=8;i<M;i++)if(i?=ual)b[i].time++;>else<queue[—K]=fol(l;/秫己录调入页面关/ual=GeMax(b);b[ual].num=Fold;b[ual].time=0;For(i=8;i<M;i++)if(i?=ual)b[i].time++;/关主程序关/uoidmain()inta[N]=<3,5,1,2,3,1,5,1,2,3,4,1,3,1,5,2,3,1,3,5};inti,j;start:K=-1;init(b,c);for(i=0;i<N;i++)Lru(a[i],b);c[0][i]=a[i];/航己录当前的内存单元中的页面卬For(j=8;j<M;j++)c[j][i]=b[j].num;)嗡出结星对人.斗prints,,内存状态数：\n");Myprintf;for(j=0;j<N;j++)printf("^2d",a[j]);printf("\n");Myprintf;for(i=0;i<M;i++)For(j=0;j<N;j++)if(c[i][j]==-1)printF("|^2c",32);elseprintf("|^2d",c[i][j]);printF("|\n");Myprintf;printf「\n调入的队列「);for(i=0;i<K+1;i++)printf("^3d",queue[i]);printf「\nLRU算法假页次数：制d'nLRU算法缺页率：%16.6f",K+1,(float)(K+1)/N)iF(getche()==1y')gotostart;2＞最佳(Optimal)置换算法〃选择距最近的最远的项置换最近一段时间最长时期S：〃3,5,1,2,3,1,5,1,2,3,4,1,3,1,5,2,3,1,3,5测试数据〃每次操作完之后重置队列^include<deque>^include<cstdio>^include<algorithm>usingnamespacestd;structopt<intvalue;〃值int｝；constintmaxn=105;inta[maxn];voidmain。<deque<opt>dq;deque<opt>::iteratorpos;intnumpkfnumqueye=O;printf(“请输入物理页框块数「);scanF("%d",&numyk);intn;inti;printf,请输入页面走向个数:“)；scanf("%d",&n);For(i=8;i<n;i++)scanf("%d",&a[i]);For(i=8;i<n;i++)intin;in=a[i];if(dq.size()<numyk)〃存在多余页框<intFlag=8;For(pos=dq.begin();pos?=dq.end();pos++)

if((*pos).ualue==in)〃存在元素和它相同Flag=1;break;>〃存在该元素—一if("lag)〃不存在此元素numqueye++;temp.ualue=in;intF=8;For(intj=i+1;j<n;j++)F=1；temp-time=j-i;break;temp-time=n;dq.pushback(temp);else〃不存在多余页框<intFlag=9;For(pos=dq.begin();pos*=dq.end();pos++)if((*pos),ualue==in)Flag=1;break;}〃存在该元素 _if"Flag)”不存在此兀素numque9e++缺页数+1intm=dq-Front()-time;“printfrm初始值为常;deque<opt>-iteratormp=dq-begin();〃注意此处千万注意初始化否则有可能erase找不到时象崩溃For(pos=dq.begin();pos!=dq.end();pos++)iF((*pos)-time>m)<mp=pos时间最大的元素的位置m=(*pos)-time;opttemp;temp.ualue=in;intF=8;dq.erase(mp);For(intj=i+1;j<n;j++)if(a[j]==in)temp.time=j-i;break;temp.time=n;〃每次之后重置for(pos=dq.begin();pos!=dq.end();pos++)intF=B;For(intj=i+1;j<n;j++)if(a[j]==(*P0S)-ualue){ f=1；(*pos).time=j-i;break;if(tf)(*pos).time=n;printf("(jpt缺页次数为:%d\n",numqueye);prints("(ipt缺页巾面率为：^lf\n",(double)numquei^e*1.0/n);

4、运行结果以及结论。如果发现上机考试结果有误，请解释原因并写出正确答案）1＞最近最久未使用置换算法内存状态数:35123151234131523135调入的队列：3512352