Word版可编辑-操作系统课程设计lru页面置换算法精心整理.doc

操作系统功能模拟设计实验 题 目： lru置换算法（C编写） 学生姓名： 计号 学号： 1104032022 专业： 网络工程 班级：11网络工程二班 实验题目LRU页面调度算法处理缺页中断一、 实验目的：了解和掌握寄存器分配和内存分配的有关技术二、 实验内容（1）首先对LRU页面调度算法原理进行深刻的理解和掌握；（2）选择一种熟悉的编程语言来实现对一组访问序列进行内部的cache更新；（3）根据LRU页面调度算法算法的要求设计相应的数据结构，如：记录访问序列的数组、模拟内存cache的数组等等；（4）显示每个访问数进入cache的操作并显示出每次访问后内存中序列的状态。三、 实验环境Windows系统，c语言四、 实验主要步骤（包括使用的数据结构的说明）1、 初始化及使用数据结构 开始的阶段，产生随机的访问序列，并用了结构体： struct pageint pageframe10; / 表示页表 int flag; /标记是否有页面置换 int length; /用来访问序列的长度int page_count; /页框的数目int page_serial20; /存取随机产生的访问序列组 int count; /用来标识页框是否被装满int k; /用于记录访问页表的指针int pagetime10; /用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间p;并初始化这些量;void init() /初始化所有页表int i;p.flag=0;for(i=0;i10;i+)p.pageframei=-1;p.pagetimei=0;for(i=0;i20;i+)p.page_seriali=-1;2、 LRU页面调度算法原理 LRU页面调度算法是对要访问cache的访问序列进行更新的，当页表还是空的时候，进来要访问的页如果页表里面有的话，就对它的访问记录加一，如果也表里面没有切页表么有填满，就像页表里面添加。如果在页表填满以后，再一次有也要访问的时候，在判断页表里面有没有要访问的页，如果没有则看页表里面的的序列哪一个页是最近最长时间都没有被访问的，就将此页给替换程现在要访问的页。3、 创建访问的序列和页框 void create()int i,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_seriali=(float) rand() / 32767) * 16 ; /随机数的大小在0-10之间 printf(nnnn);printf(:n);for(i=0;ip.length;i+) printf(%d ,p.page_seriali); printf(nnnn);printf(*);printf(nnn); 4、 在cache中查找要访问的页 int findpage(int k,int count) /在这里k用于接收从lru函数传来的访问序列的数值int m=k;int n=count;int i;int j; /用来做标记 for(i=0;i=0)p.pagetimei+;if(p.pageframei=m) p.pagetimei-; j=1;elseif(i=p.page_count) j=0; if(j=1) if(p.count=p.page_count-1) p.flag=-3; return -3; /在这里表示页框里有要访问的页,但是页框没有填满，不需要置换所以返回-3 elsep.flag=-1; /表示在此时也表里有要访问的页，但是此时页表也满了，但是也不缺页，所以用flag来表示不缺页 return -1;elseif(p.count=p.page_count-1)p.flag=0; return 0; /在这里表示没有访问到页表里面的页，但是页表没有别填满，但不需要置换所以返回0 else p.flag=-2; /在这里p.flag=-2表示没有访问到页表，且页框需要被置换所以返回-2return -2;6、 显示内存中的序列 void displayinfo() int n; printf(访问%3d : 内存,p.page_serialt); for(n=0;n=0) printf(%3d,p.pageframen); else printf( ); printf( ); if(p.flag=-2|p.flag=0) /p.flag=-1表示也表里面有访问的页，但是页框没有 满，p.flag=-2表示页表里面没有要访问的页，但是页框也被填满了 printf( =缺页 ); printf(n); 7、 此实验的执行程序图 开始 初始化 产生访问序列、并定义页框大小进行序列访问判断页框里是否有有要访问的页？ 无判断页框是否被填满 有则在此页的访问等待次数上减一 否 是 把此页添加进也表里面找到最长时间没有被访问的页，把此页给更新成新访问的页结束序列是否访问完否 是五、 设计不同实验数据，记录实验结果并分析。六、 实验总结及体会 通过这次的实验，我对LRU页面置换算法有了更深的了解，LRU置换算法是理想性的算法，因为使用LRU置换算法要花费很大的系统开销，所以在实际系统中并不会直接采用.通过这个LRU页面缺页调度算法的设计，我觉得对这个算法的原理理解的更加的深刻，虽然在设计的过程中也遇到了很多问题，例如怎么去判定内存cache中的每个数在访问后怎么去标记他的时间问题，还有怎样去表示开始时的内存cache中的页表没有被填满的缺页和页表被填满时候的缺页状态。七、 源程序清单及注释。（打印一份源程序并附上注释。）#include#includeint t;struct pageint pageframe10; / 表示页表 int vpage;int flag; /标记是否有页面置换 int length; /用来访问序列的长度int page_count; /页框的数目int page_serial20; /存取随机产生的访问序列组 int count; /用来标识页框是否被装满int k; /用于记录访问页表的指针int pagetime10; /用来记录页框里面的数被访问的过后到再一次被访问所经历的的时间p;void init() /初始化所有页表int i;p.flag=0;for(i=0;i10;i+)p.pageframei=-1;p.pagetimei=0;for(i=0;i20;i+)p.page_seriali=-1;void create()int i,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_seriali=(float) rand() / 32767) * 16 ; /随机数的大小在0-10之间 printf(nnnn);printf(:n);for(i=0;ip.length;i+) printf(%d ,p.page_seriali); printf(nnnn);printf(*);printf(nnn); int findpage(int k,int count) /在这里k用于接收从lru函数传来的访问序列的数值int m=k;int n=count;int i;int j; /用来做标记 for(i=0;i=0)p.pagetimei+;if(p.pageframei=m) p.pagetimei-; j=1;elseif(i=p.page_count) j=0; if(j=1) if(p.count=p.page_count-1) p.flag=-3; return -3; /在这里表示页框里有要访问的页,但是页框没有填满，不需要置换所以返回-3 elsep.flag=-1; /表示在此时也表里有要访问的页，但是此时页表也满了，但是也不缺页，所以用flag来表示不缺页 return -1;elseif(p.count=p.page_count-1)p.flag=0; return 0; /在这里表示没有访问到页表里面的页，但是页表没有别填满，但不需要置换所以返回0 else p.flag=-2; /在这里p.flag=-2表示没有访问到页表，且页框需要被置换所以返回-2return -2; void displayinfo()int n; printf(访问%3d : 内存,p.page_serialt); for(n=0;n=0) printf(%3d,p.pageframen); else printf( ); printf( ); if(p.flag=-2|p.flag=0) /p.flag=-1表示也表里面有访问的页，但是页框没有满，p.flag=-2表示页表里面没有要访问的页，但是页框也被填满了 printf( =缺页 ); printf(n); void lru() int i; int time=0;int m; /用于接收findpage返回的标int count1=0; /这个只是用来记录缺页的次数p.k=0;init();create();p.count=0;for(t=0;tp.length;t+) m=findpage(p.page_serialt,p.count);if(p.count=p.page_count-1) / 开始时不计算缺页 if(m=0) / 页不存在则装入页面 p.pageframep.k=p.page_serialt; /把要调入的页面放入一个空的页框里/printf(%d,p.pageframep.k);p.k=(p.k+1) % p.page_count;p.count+; else / 正常缺页置换 if(m=-2)/ 页不存在则置换页面 for(i=0;ip.pagetimetime) time=i; p.k=time; p.pagetimep.k=0; p.pageframep.k=p.page_serialt; /p.k=(p.k+1) % p.page_count; /count1+;/缺页次数加一次 displayinfo(); / 显示当前页框里面的状态 void main