搜索
操作系统功能模拟设计实验题目：lru置换算法（C编写）学生姓名：计号学号：1104032022专业：网络工程班级：11网络工程二班实验题目LRU页面调度算法处理缺页中断一、实验目的：了解和掌握寄存器分配和内存分配的有关技术二、实验内容（1）首先对LRU页面调度算法原理进行深刻的理解和掌握；（2）选择一种熟悉的编程语言来实现对一组访问序列进行内部的cache更新；（3）根据LRU页面调度算法算法的要求设计相应的数据结构，如：记录访问序列的数组、模拟内存cache的数组等等；（4）显示每个访问数进入cache的操作并显示出每次访问后内存中序列的状态。三、实验环境Windows系统，c语言四、实验主要步骤（包括使用的数据结构的说明）1、初始化及使用数据结构开始的阶段，产生随机的访问序列，并用了结构体：structpage{intpageframe[10];//表示页表intflag;//标记是否有页面置换intlength;//用来访问序列的长度intpage_count;//页框的数目intpage_serial[20];//存取随机产生的访问序列组intcount;//用来标识页框是否被装满intk;//用于记录访问页表的指针intpagetime[10];//用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间}p;并初始化这些量;voidinit(){//初始化所有页表inti;p.flag=0;for(i=0;i10;i++){p.pageframe[i]=-1;p.pagetime[i]=0;}for(i=0;i20;i++){p.page_serial[i]=-1;}}2、LRU页面调度算法原理LRU页面调度算法是对要访问cache的访问序列进行更新的，当页表还是空的时候，进来要访问的页如果页表里面有的话，就对它的访问记录加一，如果也表里面没有切页表么有填满，就像页表里面添加。如果在页表填满以后，再一次有也要访问的时候，在判断页表里面有没有要访问的页，如果没有则看页表里面的的序列哪一个页是最近最长时间都没有被访问的，就将此页给替换程现在要访问的页。3、创建访问的序列和页框voidcreate(){inti,s;printf(\n请输入页框数目:\n);scanf(%d,&p.page_count);printf(\n请输入要随机生成访问序列的长度:\n);//自定义随机生成访问序列的长度scanf(%d,&p.length);srand(rand());//初始化随机数队列的种子s=((float)rand()/32767)*50+p.length;//随机产生页面序列长度for(i=0;is;i++)//产生随机访问序列{p.page_serial[i]=((float)rand()/32767)*16;//随机数的大小在0-10之间}printf(\n\n\n\n);printf(访问序列为:\n);for(i=0;ip.length;i++){printf(%d,p.page_serial[i]);}printf(\n\n\n\n);printf(********************************);printf(\n\n\n);}4、在cache中查找要访问的页intfindpage(intk,intcount){//在这里k用于接收从lru函数传来的访问序列的数值intm=k;intn=count;inti;intj;//用来做标记for(i=0;ip.page_count;i++){if(p.pageframe[i]=0){p.pagetime[i]++;}if(p.pageframe[i]==m){p.pagetime[i]--;j=1;}else{if(i==p.page_count)j=0;}}if(j==1){if(p.count=p.page_count-1){p.flag=-3;return-3;//在这里表示页框里有要访问的页,但是页框没有填满，不需要置换所以返回-3}else{p.flag=-1;//表示在此时也表里有要访问的页，但是此时页表也满了，但是也不缺页，所以用flag来表示不缺页return-1;}}else{if(p.count=p.page_count-1){p.flag=0;return0;//在这里表示没有访问到页表里面的页，但是页表没有别填满，但不需要置换所以返回0}else{p.flag=-2;//在这里p.flag=-2表示没有访问到页表，且页框需要被置换所以返回-2return-2;}}}六、显示内存中的序列voiddisplayinfo(){intn;printf(访问%3d:内存,p.page_serial[t]);for(n=0;np.page_count;n++)//页框信息{if(p.pageframe[n]=0)printf(%3d,p.pageframe[n]);elseprintf();}printf();if(p.flag==-2||p.flag==0)//p.flag==-1表示也表里面有访问的页，但是页框没有满，p.flag==-2表示页表里面没有要访问的页，但是页框也被填满了{printf(==缺页);}printf(\n);}七、此实验的执行程序图无有否是否是开始初始化产生访问序列、并定义页框大小进行序列访问判断页框里是否有有要访问的页？则在此页的访问等待次数上减一判断页框是否被填满找到最长时间没有被访问的页，把此页给更新成新访问的页把此页添加进也表里面序列是否访问完结束五、设计不同实验数据，记录实验结果并分析。六、实验总结及体会通过这次的实验，我对LRU页面置换算法有了更深的了解，LRU置换算法是理想性的算法，因为使用LRU置换算法要花费很大的系统开销，所以在实际系统中并不会直接采用.通过这个LRU页面缺页调度算法的设计，我觉得对这个算法的原理理解的更加的深刻，虽然在设计的过程中也遇到了很多问题，例如怎么去判定内存cache中的每个数在访问后怎么去标记他的时间问题，还有怎样去表示开始时的内存cache中的页表没有被填满的缺页和页表被填满时候的缺页状态。七、源程序清单及注释。（打印一份源程序并附上注释。）#includestdio.h#includestdlib.hintt;structpage{intpageframe[10];//表示页表intvpage;intflag;//标记是否有页面置换intlength;//用来访问序列的长度intpage_count;//页框的数目intpage_serial[20];//存取随机产生的访问序列组intcount;//用来标识页框是否被装满intk;//用于记录访问页表的指针intpagetime[10];//用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间}p;voidinit(){//初始化所有页表inti;p.flag=0;for(i=0;i10;i++){p.pageframe[i]=-1;p.pagetime[i]=0;}for(i=0;i20;i++){p.page_serial[i]=-1;}}voidcreate(){inti,s;printf(\n请输入页框数目:\n);scanf(%d,&p.page_count);printf(\n请输入要随机生成访问序列的长度:\n);//自定义随机生成访问序列的长度scanf(%d,&p.length);srand(rand());//初始化随机数队列的种子s=((float)rand()/32767)*50+p.length;//随机产生页面序列长度for(i=0;is;i++)//产生随机访问序列{p.page_serial[i]=((float)rand()/32767)*16;//随机数的大小在0-10之间}printf(\n\n\n\n);printf(访问序列为:\n);for(i=0;ip.length;i++){printf(%d,p.page_serial[i]);}printf(\n\n\n\n);printf(********************************);printf(\n\n\n);}intfindpage(intk,intcount){//在这里k用于接收从lru函数传来的访问序列的数值intm=k;intn=count;inti;intj;//用来做标记for(i=0;ip.page_count;i++){if(p.pageframe[i]=0){p.pagetime[i]++;}if(p.pageframe[i]==m){p.pagetime[i]--;j=1;}else{if(i==p.page_count)j=0;}}if(j==1){if(p.count=p.page_count-1){p.flag=-3;return-3;//在这里表示页框里有要访问的页,但是页框没有填满，不需要置换所以返回-3}else{p.flag=-1;//表示在此时也表里有要访问的页，但是此时页表也满了，但是也不缺页，所以用flag来表示不缺页return-1;}}else{if(p.count=p.page_count-1){p.flag=0;return0;//在这里表示没有访问到页表里面的页，但是页表没有别填满，但不需要置换所以返回0}else{p.flag=-2;//在这里p.flag=-2表示没有访问到页表，且页框需要被置换所以返回-2return-2;}}}voiddisplayinfo(){intn;printf(访问%3d:内存,p.page_serial[t]);for(n=0;np.page_count;n++)//页框信息{if(p.pageframe[n]=0)printf(%3d,p.pageframe[n]);elseprintf();}printf();if(p.flag==-2||p.flag==0)//p.flag==-1表示也表里面有访问的页，但是页框没有满，p.flag==-2表示页表里面没有要访问的页，但是页框也被填满了{printf(==缺页);}printf(\n);}voidlru(){inti;inttime=0;intm;//用于接收findpage返回的标intcount1=0;//这个只是用来记录缺页的次数p.k=0;init();create();p.count=0;for(t=0;tp.length;t++){m=findpage(p.page_serial[t],p.count);if(p.count=p.page_count-1)//开始时不计算缺页{if(m==0)//页不存在则装入页面{p.pageframe[p.k]=p.page_serial[t];//把要调入的页面放入一个空的页框里//printf(%d,p.pageframe[p.k]);p.k=(p.k+1)%p.page_count;p.count++;}}else//正常缺页置换{if(m==-2)//页不存在则置换页面{for(i=0;ip.page_count;i++){if(p.pagetime[i]p.pagetime[time]){time=i;}}p.k=time;p.pagetime[p.k]=0;p.pageframe[p.k]=p.page_serial[t];//p.k=(p.k+1)%p.page_count;//count1++;//缺页次数加一次}}displayinfo();//显示当前页框里面的状态}}voidmain(){charch;printf(\n\n\n\n\n);printf(***********操作系统实验**********