还剩20页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
操作系统课程设计报告题目页面置换算法模拟程序设计专业软件工程院系信息管理学院年级大三软件Q___1学号11150038姓名李艳平指导教师李红艳职称副教授湖北经济学院教务处制目录第一部分概述第二部分设计的基本概念和原理第三部分总体设计
3.1算法流程图
3.2算法的简要实现方法
3.
2.1OPT页面置换算法
3.
2.2FIFO页面置换算法
3.
2.3LRU页面置换算法
3.
2.4LFU页面置换算法第四部分详细设计
4.1__in函数
4.2OPT函数
4.2FIFO函数
4.3LRU函数
4.5LFU函数
4.6辅助函数
4.
6.1Designer函数
4.
6.2mDelay函数
4.
6.3Download函数
4.
6.4Compute函数
4.
6.5showTable函数第五部分实现源代码第六部分简要的使用说明及主要运行界面第七部分总结第八部分____第一部分概述设计任务页面置换算法是虚拟存储管理实现的关键,通过本次课程设计理解内存页面调度的机制,在模拟实现OPT、FIFO、LRU和LFU几种经典页面置换算法的基础上,比较各种置换算法的效率及优缺点,从而了解虚拟存储实现的过程第二部分设计的基本概念和原理1.页面淘汰机制页面淘汰又称为页面置换若请求调页程序要调进一个页面,而此时该作业所分得的主存块已全部用完,则必须淘汰该作业已在主存中的一个页这时,就产生了在诸页面中淘汰哪个页面的问题,这就是淘汰算法(或称为置换算法)置换算法可描述为,当要索取一个页面并送入主存时,必须将该作业已在主存中的某一页面淘汰掉,用来选择淘汰哪一页的规则就叫做置换算法2.各种页面置换算法的实现思想OPT算法是当要调入一新页而必须先淘汰一旧业时,所淘汰的那一页应是以后不要再用的或是以后很长时间才会用到的页FIFO算法的实质是,总是选择在主存中居留时间最长(即最老)的一页淘汰其理由是最先调入主存的页面,其不再被使用的可能性比最近调入主存的页的可能性大LRU算法的实质是,当需要置换一页时,选择最长时间未被使用的那一页淘汰如果某一页被访问了,它很可能马上还要被访问;相反,如果它很长时间未曾用过,看起来在最近的未来是不大需要的LFU即最不经常使用页置换算法,要求在页置换时置换在一定时期内引用计数最小的页,因为经常使用的页应该有一个较大的引用次数本次设计取整个页面访问时期为计算周期,实际问题中应根据页面数量多少来确定周期第三部分总体设计
3.1算法流程图
3.2算法的简要实现方法选择置换算法,先输入所有页面号,为系统分配物理块,依次进行置换最佳置换算法(OPT)是用一维数组page[PSIZE]存储页面号序列,memery[MSIZE]是存储装入物理块中的页面,用pflag[PSIZE]数组标记缺页中断处数组next[MSIZE]记录物理块中对应页面的最后访问时间每当发生缺页时,就从物理块中找出最后访问时间最大的页面,调出该页,换入所缺的页面,然后初始化next[MSIZE],便于下次使用【特别声明】若物理块中的页面都不再使用,则每次都置换物理块中第一个位置的页面先进先出置换算法(FIFO)是用一维数组page[PSIZE]存储页面号序列,memery[MSIZE]是存储装入物理块中的页面,用pflag[PSIZE]数组标记缺页中断处采用队列的思想,总是把最先进入物理块中的页面放在第一个位置,当发生缺页时,就从队头删除一页,而从队尾加入缺页最久未使用置换算法(LRU)是用一维数组page[PSIZE]存储页面号序列,memery[mSIZE]是存储装入物理块中的页面,用pflag[PSIZE]数组标记缺页中断处总是把最长时间内未被使用的页放在最后一块,当发生缺页时,就删掉最后一页,将当前所缺页面放入第一块最不经常使用淘汰算法(LFU)是用一维数组page[PSIZE]存储页面号序列,memery[mSIZE]是存储装入物理块中的页面,用pflag[PSIZE]数组标记缺页中断处用use[MSIZE]数组记录当前各页已使用次数,其中use
[0]中存放使用次数最少的页的次数,当发生缺页时,就在已放入物理块的页中查找当前使用次数最少的页,将之删掉,并引入当前缺页页面第四部分详细设计__in函数void__in{intikcode;intmSizepSizepage[PSIZE];systemcolor0A;Designer;printf┃请按任意键继续...┃\n;printf┖─────────────────────────┚\n;printf;getchar;systemcls;//DOS命令,清除屏幕上的所有文字systemcolor0B;//改变控制台的前景和背景色printf请输入物理块的个数[mSize=10];scanf%dmSize;printf请输入页面数[pSize=50];scanf%dpSize;printf请输入页面序列[1~10之间]\n;fori=0;ipSize;i++scanf%dpage[i];DownloadpSizemSize;systemcls;systemcolor0E;do{printf即将进入物理块的页面序列为:\n;fori=0;ipSize;i++printf%3dpage[i];printf\n;printf*****************************\n;printf*请选择页面置换算法*\n;printf*━━━━━━━━━━━━━━━━━━━━━━━━━━━*\n;printf*
1.最佳OPT
2.先进先出FIFO
3.最近最久未使用LRU*\n;printf*
4.最不经常使用LFU当前使用次数最少
5.退出*\n;printf*****************************\n;printf请选择操作[]\b\b;scanf%dcode;switchcode{case1:OPTpagepSizemSize;break;case2:FIFOpagepSizemSize;break;case3:LRUpagepSizemSize;break;case4:LFUpagepSizemSize;break;case5:systemcls;systemcolor0A;Designer;//显示设计者信息后退出printf┃谢谢使用页面置换算法演示器!正版授权㊣┃\n;printf┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n;exit0;default:printf输入错误,请重新输入;}//printf按任意键重新选择置换算法;getchar;systempause;//冻结屏幕systemcls;}whilecode!=5;getchar;}OPT函数voidOPTintpage[]intpSizeintmSize{intijk;intcount=0;//计数器intmemery[MSIZE]={0};//存储装入物理块中的页面intnext[MSIZE]={0};//记录物理块中对应页面的最后访问时间sum=0;fori=0;ipSize;i++{j=0;whilejmSizepage[i]!=memery[j]//查页表,看是否缺页j++;ifj==mSize{flag=*;//缺页,则置标志flag为*sum+=1;//记录缺页次数ifsum=mSize//如果物理块中有空余,则将当前页面直接放入{forj=0;jmSize;j++{ifmemery[j]==0{memery[j]=page[i];break;}}}else//物理块已满的情况下{forj=i+1;jpSize;j++//查找以后不再使用或在最长时间以后才会用到的页{fork=0;kmSize;k++{ifpage[j]==memery[k]{next[k]+=1;//记录将被使用的次数,可以不用累加count++;//记录物理块中以后将即被使用的页面个数break;}}ifcount==mSize-1break;//如果已有mSize-1个页面即将被使用,则剩下最后一个页面一定是最长时间后才会用到的页}ifcount==0memery
[0]=page[i];else{count=0;fork=0;kmSize;k++{ifnext[k]==0//总是置换出第一个可以换出的页memery[k]=page[i];next[k]=0;//初始化next[]数组}}}}elseflag=;pflag[i]=flag;//记录当前页的缺页情况fork=0;kmSize;k++//记录每一次的置换情况table[k][i]=memery[k];}Compute;showTablepagepSizemSize;}FIFO函数voidFIFOintpage[]intpSizeintmSize{intij;intmemery[MSIZE]={0};//存储装入物理块中的页面sum=0;fori=0;ipSize;i++//查页表,看是否缺页{j=0;whilejmSizepage[i]!=memery[j]j++;ifj==mSize{flag=*;//缺页,则置标志flag为*sum+=1;forj=mSize-1;j0;j--//淘汰最先调入的页面,并调入当前页面memery[j]=memery[j-1];memery
[0]=page[i];}elseflag=;pflag[i]=flag;forj=0;jmSize;j++table[j][i]=memery[j];}Compute;showTablepagepSizemSize;}LRU函数voidLRUintpage[]intpSizeintmSize{intijk;intmemery[MSIZE]={0};//存储装入物理块中的页面sum=0;fori=0;ipSize;i++{j=0;whilejmSizepage[i]!=memery[j]//查页表,看是否缺页j++;ifj==mSize{flag=*;//缺页,则置标志flag为*sum+=1;k=j-1;}else{flag=;k=j;}pflag[i]=flag;//记录当前页的缺页情况whilek0//总是把最长时间内未被使用的页放在最后一页{memery[k]=memery[k-1];k--;}memery
[0]=page[i];//调入当前页面fork=0;kmSize;k++//记录每一次的置换情况table[k][i]=memery[k];}Compute;showTablepagepSizemSize;}LFU函数voidLFUintpage[]intpSizeintmSize{intijrepla__;//repla__标记使用次数最少的页intuse[MSIZE]={0};//记录当前各页已使用次数其中use
[0]中存放使用次数最少的页的次数intmemery[MSIZE]={0};//存储装入物理块中的页面sum=0;fori=0;ipSize;i++{use[page[i]]+=1;//下标即为页号j=0;whilejmSizepage[i]!=memery[j]//查页表,看是否缺页j++;ifj==mSize{flag=*;//缺页,则置标志flag为*sum+=1;ifsum=mSize//如果物理块中有空余,则将当前页面直接放入{forj=0;jmSize;j++{ifmemery[j]==0{memery[j]=page[i];break;}}}else//物理块已满的情况下{use
[0]=100;forj=0;jmSize;j++//在已放入物理块的页中查找当前使用次数最少的页{ifuse[memery[j]]use
[0]{use
[0]=use[memery[j]];repla__=j;//标记页号}}memery[repla__]=page[i];}}elseflag=;pflag[i]=flag;//记录当前页的缺页情况forj=0;jmSize;j++//记录每一次的置换情况table[j][i]=memery[j];}Compute;showTablepagepSizemSize;}辅助函数Designer函数voidDesigner{printf┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n;printf┃◎◎◎课题页面置换算法◎◎◎┃\n;printf┃◎◎◎学号11150038◎◎◎┃\n;printf┃◎◎◎姓名李艳平◎◎◎┃\n;printf┃◎◎◎VisualC++
6.0◎◎◎┃\n;printf┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n;}mDelay函数voidmDelayunsignedintDelay{unsignedinti;whileDelay0{fori=0;i125;i++printf\b;Delay--;}}Download函数voidDownloadintpSizeintmSize{inti;systemcolor0D;printf┏┅┅┅┅┅┅┅┅┅┅┅┅┓\n;printf┇正在载入数据,请稍后...┇\n;printf┗┅┅┅┅┅┅┅┅┅┅┅┅┛\n;printfLoading...\n;printf0\n;fori=0;i51;i++printf\b;fori=0;i50;i++{mDelaypSize+mSize/2;printf;}printf\nFinish.\n载入成功,按任意键进入置换算法选择界面;getchar;}Compute函数voidCompute{inti;printf正在进行相关计算,请稍候...\n;fori=1;i20;i++{mDelay15;ifi%4==0printf\b\b\b\b\b\b\b\b\b\b\b\b;elseprintf;}fori=0;i++30;printf\b;fori=0;i++30;printf;fori=0;i++30;printf\b;}showTable函数voidshowTableintpage[]intpSizeintmSize{intij;/*printf即将进入物理块的页面序列为:\n;fori=0;ipSize;i++printf%3dpage[i];printf\n输出置换过程,“*”标记缺页中断处\n;*/fori=0;imSize;i++{forj=0;jpSize;j++printf%3dtable[i][j];printf\n;}fori=0;ipSize;i++printf%3cpflag[i];printf\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n;printf总的缺页次数为%d\nsum;printf缺页中断率为%.2lf%%\n
100.0*sum/pSize;printf◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n;}第五部分实现源代码#includestdio.h#includestdlib.h/*宏定义*/#defineMSIZE10//最大物理块数#definePSIZE50//最大页面数/*全局变量*/charflagpflag[PSIZE];//缺页标志inttable[MSIZE][PSIZE];//存放置换记录intsum=0;//记录每个算法的缺页次数/*置换算法函数*/voidOPTintpage[]intpSizeintmSize;//最佳置换算法voidFIFOintpage[]intpSizeintmSize;//先进先出置换算法voidLRUintpage[]intpSizeintmSize;//最久未使用置换算法voidLFUintpage[]intpSizeintmSize;//最不经常使用淘汰算法当前使用次数最少/*辅助函数*/voidDesigner;//显示设计者信息voidmDelayunsignedintDelay;//设置延迟voidDownloadintpSizeintmSize;//载入数据voidCompute;//计算过程延迟voidshowTableintpage[]intpSizeintmSize;//输出置换过程【主函数及其他函数详见第四部分】第六部分简要的使用说明及主要运行界面主要运行界面【运行环境——VisualC++
6.0】1按任意键继续
(2)载入数据
(3)进入置换算法选择界面
(4)运算中延迟操作
(5)四种算法演示结果
(6)退出界面第七部分总结(特色、经验、教训和__)两周的课程设计结束了,在这次的课程设计中不仅检验了我所学习的知识,也培养了我如何去把握一件事情,如何去做一件事情,如何去坚持一件事情,又如何完成一件事情在这次设计过程中,体现出自己单独设计模具的能力以及综合运用知识的能力,体会了学以致用、突出自己劳动成果的喜悦心情,从中发现自己平时学习的不足和薄弱环节,从而加以弥补,同时对页面置换算法有了更深入的了解虽然在写算法的过程中遇到了一些麻烦,但经过我的坚持不懈最终解决了问题同时感谢对我帮助过的同学们,谢谢你们对我的帮助和支持,让我__到同学的友谊由于本人的设计能力有限,在设计过程中难免出现错误,恳请老师们多多指教我十分乐意接受你们的批评与指正,本人将万分感谢第八部分____C语言程序设计中国水利水电出版社计算机操作系统庞丽萍编著人民邮电出版社输入页面访问序列取访问的页号查页表是否缺页否是置缺页标志flag为’*’按算法不同淘汰一页面调入所访问的页面。