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

《操作系统课程设计--内存FIFO,LRU页面置换算法设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、漳州师范学院操作系统课程设计内存FIFO、LRU页面置换算法设计姓名：学号：080811151系别：计算机科学与工程系专业：计算机工程年级：08级指导教师：2011年5月18日一、课程设计项目介绍（含项目介绍及设计目的）1.实验目的：1.1通过这些算法的设计，深入理解虚拟存储器管理的原理；1.2理解内存分页管理策略，以及页面与物理块之间的关系；1.3掌握内存调页策略；1.4理解常用的页面置换算法，如LRU、FIFO等置换算法，并选取LRU、FIFO算法模拟实现；1.5通过统计比较算法的运行结果，了解各种置换算法

2、的命中率高低，以加深对算法本身的认识。2.实验项目介绍：项目程序是用C语言实现LRU、FIFO页面置换算法，可运行在VC，C-FREE等编译环境下。本程序是在假设系统采用固定分配局部置换策略的基础上，来模拟内存的调页策略和置换算法。FIFO算法主要是考虑页面进入内存的时间长短，当缺页时把进入最久的页面置换掉；LRU算法以最近的过去作为最近的将来的参考，当产生缺页时，把最近最久未使用的页面置换掉。由于两个算法的相似性，所以进行统一处理，并加以区分。二、总体设计（含系统的总体结构、原理框图或各模块介绍等）1.确定L

3、RU、FIFO算法中的数据结构定义了一个结构体structpage{intpagenum;intpagetime;};(pagenum为页面号码，pagetime为进入时间或者上次使用的时间)来模拟内存的页面；用page定义一个结构体数组p_age[10],表示可供使用的内存页面为10；定义一个整形数组intb[N]用来存放要访问的内存页面串，串的长度不要超过N，本程序N=100。定义整形变量pagecount，num，time分别表示要申请的内存页数和要访问的内存页面串的长度；整形变量time用来表示时间，初

4、始化为1，当p_age[i]页面进入时，p_age[i].pagetime=time++,此后每进入一个页面，或者更新一个页面，都把time赋给该内存页面的时间对象，然后自加1。页面的时间对象pagetime最大的那个页面是刚访问过或者刚进入的，pagetime最小的那个页面当产生缺页时将被替换掉；变量misspage，missrate分别用来记录缺页数和缺页率；变量flag用来标记要访问的页面是否在内存中，label用来标记已在内存中且pagetime最小的页面；FIFO[]，LRU[]数组用来记录每一次执行

5、算法的缺页率。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

6、].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=

7、time++；继续循环，直到i=num，执行完之后输出缺页数和缺页率。重新调用主程序，开始另一个实例的输入（option==4）统计缺页率，计算平均缺页率（option==3）执行最近最久未使用LRU算法（option==2）执行先进先出FIFO算法（option==1）主程序3．程序结构图三、详细设计（含主要的数据结构、程序流程图、关键代码段及注释等）入口start输入申请的内存页数N、页面串的长度、输入页面串Option==1

8、

9、2输入optionOption==5初始化内存及变量Y退出YOption==4

10、N逐个读入页面YN页面是否在内存中Option==3NY统计缺页率、计算平均缺页率并输出结果NY在内存中第一次查找到pagetime最小的页面Kp_age[k]LRU算法?Y将存在在内存中的页面p_age[k].pagetime=time+++++置换页面p_age[k].pagenum=b[i]p_age[k].pagetime=time++N输出缺页数和缺页率Y是否还有未读页面程序