操作系统课程设计-内存FIFO,LRU页面置换算法设计

漳州师范学院操作系统课程设计内存FIFO、LRU页面置换算法设计姓名：学号：系别：计算机科学与工程系专业：年级：指导教师：一、课程设计项目介绍（含项目介绍及设计目的）1.实验目的：1.1通过这些算法的设计，深入理解虚拟存储器管理的原理；1.2理解内存分页管理策略，以及页面与物理块之间的关系；1.3掌握内存调页策略；1.4理解常用的页面置换算法，如LRU、FIFO等置换算法，并选取LRU、FIFO算法模拟实现；1.5通过统计比较算法的运行结果，了解各种置换算法的命中率高低，以加深对算法本身的认识。2.实验项目介绍：项目程序是用C语言实现LRU、FIFO页面置换算法，可运行在VC，C-FREE等编译环境下。本程序是在假设系统采用固定分配局部置换策略的基础上，来模拟内存的调页策略和置换算法。FIFO算法主要是考虑页面进入内存的时间长短，当缺页时把进入最久的页面置换掉；LRU算法以最近的过去作为最近的将来的参考，当产生缺页时，把最近最久未使用的页面置换掉。由于两个算法的相似性，所以进行统一处理，并加以区分。二、总体设计（含系统的总体结构、原理框图或各模块介绍等）1.确定LRU、FIFO算法中的数据结构 定义了一个结构体structpage{intpagenum;intpagetime;};(pagenum为页面号码，pagetime为进入时间或者上次使用的时间)来模拟内存的页面；用page定义一个结构体数组p_age[10],表示可供使用的内存页面为10；定义一个整形数组intb[N]用来存放要访问的内存页面串，串的长度不要超过N，本程序N=100。 定义整形变量pagecount，num，time分别表示要申请的内存页数和要访问的内存页面串的长度；整形变量time用来表示时间，初始化为1，当p_age[i]页面进入时，p_age[i].pagetime=time++,此后每进入一个页面，或者更新一个页面，都把time赋给该内存页面的时间对象，然后自加1。页面的时间对象pagetime最大的那个页面是刚访问过或者刚进入的，pagetime最小的那个页面当产生缺页时将被替换掉； 变量misspage，missrate分别用来记录缺页数和缺页率；变量flag用来标记要访问的页面是否在内存中，label用来标记已在内存中且pagetime最小的页面；FIFO[]，LRU[]数组用来记录每一次执行算法的缺页率。2.核心算法的实现申请的内存页数为pagecount,p_age[i]为内存中页面,b[]为输入的页面串，num为b[]的长度；(1)初始化内存页面(2)FIFO算法从i=0开始逐个调入页面，查找b[]页面串第i个页面是否已经存在在内存当中，如果已经存在则用flag=1来做标记，i++并开始下个循环；如果不存在则flag=0，并查找已在内存中p_age[k]页面的成员pagetime最小的页面，并用label=k标记，查找到之后用b[i]页面替换p_age[label]，并且p_age[lable].pagetime=time++；继续循环，直到i=num，执行完之后输出缺页数和缺页率。(3)LRU算法从i=0开始逐个调入页面，查找b[]页面串第i个页面是否已经存在在内存当中，如果已经存在则用flag=1来做标记，并更新该内存页面的pagetime(访问时间)对象，i++开始下个循环；如果不存在则flag=0，并查找已在内存中p_age[k]页面的成员pagetime最小的页面，并用label=k标记，查找到之后用b[i]页面替换p_age[label],并且p_age[lable].pagetime=time++；继续循环，直到i=num，执行完之后输出缺页数和缺页率。重新调用主程序，开始另一个实例的输入（option==4）统计缺页率，计算平均缺页率（option==3）执行最近最久未使用LRU算法（option==2）重新调用主程序，开始另一个实例的输入（option==4）统计缺页率，计算平均缺页率（option==3）执行最近最久未使用LRU算法（option==2）执行先进先出FIFO算法（option==1）主程序3．程序结构图三、详细设计（含主要的数据结构、程序流程图、关键代码段及注释等）入口入口startstart输入申请的内存页数N、页面串的长度、输入页面串输入申请的内存页数N、页面串的长度、输入页面串OOption==1||2输入option输入optionOption==5初始化内存及变量Option==5初始化内存及变量退出 Y退出Option==4NOption==4逐个读入页面Y 逐个读入页面N页面是否在内存中Option==3N页面是否在内存中Option==3 Y统计缺页率、计算平均缺页率并输出结果NY统计缺页率、计算平均缺页率并输出结果在内存中第一次查找到pagetime最小的页面在内存中第一次查找到pagetime最小的页面Kp_age[k]LRU算法?Y将存在在内存中的页面p_age[k].pagetime=time+++++置换页面将存在在内存中的页面p_age[k].pagetime=time+++++置换页面p_age[k].pagenum=b[i]p_age[k].pagetime=time++N输出缺页数和缺页率Y是否还有未读页面N输出缺页数和缺页率Y是否还有未读页面程序代码：structpage //用结构体模拟内存{intpagenum; //内存页号intpagetime; //对FIFO算法是进入时间，LRU是访问时间};#include<stdio.h>voidmain(){pagep_age[10]; //定义一个10个页面的内存结构intb[100]; //用来保存要访问的页面序列intpagecount,num,time,mintime,misspage;//pagecount是要申请的内存页数，num为要访问的页面序列的长度，time变量是//用来模拟时间inti,j,k,option,flag,lable; //option是选项，用来调用程序功能floatmissrate;staticfloatFIFO[100]={0},LRU[100]={0}; //用来记录每次的缺页率staticintf=0,l=0; //f,l分别代表FIFO[]和LRU[]的长度printf("**************************************************\n");printf(" WELCOMETOHERE!\n");printf("***************************************************\n");printf("请输入模拟的内存页数！\n");scanf("%d",&pagecount);printf("请输入要输入的页面数！\n");scanf("%d",&num);printf("请输入页面序列！\n");for(i=0;i<num;i++){scanf("%d",&b[i]);}printf("************************************************\n");printf(" 选择FIFO算法请输入1! \n");printf(" 选择LRU算法请输入2! \n");printf(" 缺页率统计请输入3!\n");printf(" 重新输入序列请输入4! \n");printf(" 选择退出输入5! \n");printf("************************************************\n");while(scanf("%d",&option)){if(option==5) //输入5则退出程序{ break;}else if(option==4) //输入4返回重新输入内存页数和页面序列 { main(); break; } else if(option==3) //统计缺页率，计算平均缺页率 { missrate=0; //统计FIFO算法的缺页率 for(i=0;i<f;i++) { printf("%f",FIFO[i]); missrate=missrate+FIFO[i]; } if(f==0) //FIFO[]中还没有记录时 { missrate=0; } else { missrate=missrate/f; } printf("FIFO算法的平均缺页率是:%f\n\n",missrate); missrate=0; //统计LRU算法的缺页率 for(i=0;i<l;i++) { missrate=missrate+LRU[i]; printf("%f",LRU[i]); } if(l==0) { missrate=0; } else { missrate=missrate/l; } printf("LRU算法的平均缺页率是:%f\n\n\n",missrate); }//开始执行FIFO和LRU算法，两个算法类似，所以用同一个函数，并进行控制区分elseif(option==1||option==2) { misspage=0; time=1; for(k=0;k<pagecount;k++) //初始化申请的内存 { p_age[k].pagenum=-1; p_age[k].pagetime=-1; } for(i=0;i<num;i++) //逐个调入页面 { flag=0; for(k=0;k<pagecount;k++) //查找要调入的页面是否已在内存 { if(p_age[k].pagenum==b[i]) { flag=1; //flag==1标记要读入的页面已在内存中 if(option==2) //如果是LRU算法,则更新页面的访问时间 { p_age[k].pagetime=time++; } for(j=0;j<pagecount;j++) //不缺页时输出内存中的页面 {if(p_age[j].pagenum>=0) printf("%d",p_age[j].pagenum); } printf("\n"); } } if(flag==0) //要访问的页面不在内存中，产生缺页 { mintime=p_age[0].pagetime; lable=0; for(k=1;k<pagecount;k++)//查找已在内存中且时间最小的页面 { if(p_age[k].pagetime<mintime) { mintime=p_age[k].pagetime; lable=k; //label标记第一次找到的时间最小的页面 } } p_age[lable].pagenum=b[i]; //将时间最小的页面置换出 p_age[lable].pagetime=time++; //记录进入时间 printf("第%d页缺页\n",i+1); misspage++; //缺页数加1 } } missrate=float(misspage)/num; //计算缺页率 if(option==1) //记录FIFO算法的缺页率 { FIFO[f]=missrate; f++; } elseif(option==2) //记录LRU算法的缺页率 { LRU[l]=missrate; l++; } printf("缺页数是%d,缺页率是%f\n",misspage,missrate); printf("\n\n\n"); }}}四、运行结果（含运行及测试结果和用户使用说明书）1.运行结果1.1程序运行提示输入1.2输入1执行FIFO算法1.3输入2执行LRU算法1.4输入3统计缺页率1.5输入4重新输入内存页数和页面序列1.6输入5退出程序2.使用说明书 运行程序，在DOS界面中将显示欢迎界面，提示输入内存页数和页面序列的长度以及页面序列；回车后出现选项提示：输入1则执行FIFO算法,输入2执行LRU算法,输入3进行缺页率统计并计算平均缺页率，输入4返回main()函数，重新执行程序，此时可以再次输入内存页数和页面序列，输入5的话则退出程序。五、课程设计小结与心得体会（不小于300字）（四号宋体） 本次课程设计主要可以分为两个阶段，一个算法的理解和设计，一个是程序的编制和算法的改进执行。第一个阶段是要了解内存的分配策略、内存调页策略以及FIFO和LRU算法的执行原理。程序中采用的分配策略是固定分配局部置换，即为进程分配一定书面的物理块，在整个运行期间都不再改变，采用该策略时，如果进程在运行过程中发现缺页，则只能从该进程在内存中的n个页面中选出一个页换出，然后再调入一个页，以保证分配给该进程的内存空间不变。采用的调页策略是请求调页策略，他的原理是当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。程序中的FIFO算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，但是算法