C语言 页面淘汰算法 OPT FIFO LRU CLOCK.pdf

《操作系统原理》上机作业（报告）作业：页面淘汰算法1页作业编号6题目页面淘汰/置换算法【题目要求】通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。针对一个页框，根据实验数据，以OPT算法为参考，研究FIFO页面淘汰算法、LRU页面淘汰以及CLOCK算法针对同一批实验数据的缺页率，以及研究在不同页框设置下的各算法缺页率表现情况。页面引用序列为：4,3,2,1,4,3,5,4,3,2,1,5（1）固定分配局部置换情况下，驻留集大小为3，针对该内存页面引用序列模拟各算法的运行过程，并计算缺页率。（2）模拟驻留集大小为4和5的情况下各算法的运行过程和缺页率。其菜单如下：*************内存分配和回收***********=================================0.退出1.OPT算法实现2.LRU算法实现3.FIFO算法实现4.CLOCK算法作业5.显示缺页率对比表=================================要求【实习要求】可选编程语言：C/C++/Java/C#/Python；实现在同一个程序文件中（C/C++）；请适当注释；【实现提示】所需变量N：程序执行需要访问的页面数Msize：内存中可容纳的页数lack：在一次页面走向序列中用来统计缺页次数rate：缺页次数/总页数变量声明如下图所示：队列结构页面引用序列pages[N]和内存容量Memory[m]均用简单的数据结构线2页性表实现，其声明如图所示：【选做内容】改进型CLOCK算法实现。构造一个页面引用序列，并出现Belady现象。报告正文（运行屏幕截图及源代码）一．截图。3页4页二．附录。#defineN30//staticintMsize;//内存容页数staticintlacknum;//缺页数staticintpages[N]={4,3,2,1,4,3,5,4,3,2,1,5};staticintmemery[10];voidInitial(){inti;for(i=0;i<10;i++){memery[i]=0;}lacknum=0;}intTo_left(intindex,intpage)//计算之前的本页到现在已经多久了{inti=index-1;while(i>=0){if(pages[i]==page)5页{returnindex-i;}i--;}return-1;}intTo_right(intindex,intpage)//{inti=index+1;while(pages[i]!=0&&i<20){if(pages[i]==page){returni-index;}i++;}return10000;}intIs_Lack()//判断内存是否没装满页,并返回空位的index{inti;for(i=0;i<Msize;i++){if(memery[i]==0){returni;}}return-1;}intIs_exist(intpage)//判断改page是否已在内存中,若有返回index{inti;for(i=0;i<Msize;i++){if(memery[i]==page){returni;}}return-1;}6页voidOPT()//{inti,j,k,longest_page_index;for(i=0;pages[i]!=0;i++){if(Is_Lack()!=-1)//如果内存还没装满{j=Is_Lack();//取出memery里的空位indexif(Is_exist(pages[i])!=-1)//如果当前page已在memery中{continue;}else//并不在memery中{memery[j]=pages[i];continue;}}else//memery已装满，进行淘汰页面{if(Is_exist(pages[i])!=-1){continue;}intl,m,n;longest_page_index=0;n=0;for(l=0;l<Msize;l++)//找以后最久才会访问的page{m=To_right(i,memery[l]);if(m>n){n=m;longest_page_index=l;}}memery[longest_page_index]=pages[i];lacknum++;}}}voidLRU()//最近最久置换算法{7页inti,j,k,longest_page_index;for(i=0;pages[i]!=0;i++){if(Is_Lack()!=-1)//{j=I