操作系统课程设计存储管理

河南城建学院《操作系统》课程设计说明书设计题目：存储管理专业：计算机科学与技术指导教师：邵国金、薛冰、郭猛班级：0814102学号：081410219姓名：李二萌同组人：杨森林、杨鹏飞、王伟超计算机科学与工程系2013年01月10日2前言本模拟系统实现了先进先出页面淘汰算法（FIFO）、最近最少使用LRU页面淘汰算法、最近未使用算法NUR、最少访问页面算法LFU和最佳淘汰算法OPT。同时系统可以随意设置当前分配给作业的物理块数。系统运行时，任意输入一个页面访问序列，可以设定不同的页面置换算法和物理块数，输出其页面淘汰的情况，计算其缺页次数和缺页率。系统结束后，比较同一个页面访问序列，可以得出在不同的页面置换算法和物理块数的情况下，其产生的缺页次数和缺页率。使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，没有优化效果，所以FIFO算法性能不好。使用LRU的算法，此组数据显示LRU的算法使用比较繁琐，总的来说，NUR、LFU、LRU算法介于FIFO和Optimial之间。通过系统模拟得出，optimal算法的性能高，LRU、NUR、LRU算法的性能次之，FIFO的算法性能最差，较少应用；由于optimal算法在实际上难于实现，所以实际应用一般用LRU算法。本设计的目的是是熟悉存储管理的设计方法，加深对请求分页式存储管理的认识。设计中用到了数据结构中的相关知识，链表的操作，通过本设计可以加深的数据结构的理解。设计代码语言用到的是C语言，使用起来比较方便，可以在虚拟机和VC上直接运行。3目录目录................................................................................................................................3一、系统环境................................................................................................................41.1、硬件环境........................................................................................................41.2、软件环境........................................................................................................4二、设计目的................................................................................................................5三、总体设计................................................................................................................63.1、程序设计组成框图........................................................................................63.2、流程图............................................................................................................7四、详细设计..............................................................................................................114.1、数据结构......................................................................................................114.1.1页面类型...............................................................................................114.1.2页面控制结构.......................................................................................114.2.函数定义.........................................................................................................124.3.变量定义.........................................................................................................124.4.算法分析.........................................................................................................12五、调试与测试..........................................................................................................145.1、调试方法......................................................................................................145.2、测试结果的分析与讨论..............................................................................14六、设计中遇到的问题..............................................................................................15七、源程序清单..........................................................................................................16八、总结，收获与体会..............................................................................................25九、参考文献..............................................................................................................264一、系统环境1.1、硬件环境PC机一台，内存，2.0GHZ主频1.2、软件环境设计和实验将Windows环境下，gcc和虚拟机软件VMWare。5二、设计目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。要求：(1)通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分。具体的实施方法是：①在[0，319]的指令地址之间随机选取一起点m；②顺序执行一条指令，即执行地址为m+l的指令；③在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；④顺序执行一条指令，其地址为m’+1；⑤在后地址[m’+2，319]中随机选取一条指令并执行；⑥重复上述步骤①~⑤，直到执行320次指令。(2)将指令序列变换成为页地址流。设:①页面大小为1K；②用户内存容量为4页到32页；③用户虚存容量为32K。在用户虚存中，按每页存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页(对应虚存地址为[0，9])；第10条~第19条指令为第1页(对应虚存地址为[10，19])；………第310条~第319条指令为第31页(对应虚存地址为[310，319])。按以上方式，用户指令可组成32页。(3)计算并输出下述各种算法在不同内存容量下的命中率（要为以下各种算法定义数据结构）。①先进先出的算法(FIFO)；②最近最少使用算法(LRU)；③最近最不经常使用算法(NUR/NRU/CLOCK)。6三、总体设计3.1、程序设计组成框图程序设计组成框图Initialize()初始化函数Main()FIFO算法模块LRU算法模块LFU算法模块NUR算法模块OPT算法模块73.2、流程图FIFOLRUYYYN找到了吗找到了吗新页块压入栈顶，栈底页号移出开始还有指令吗计算出页号在实存队列查找该页号新页号按序加入实存队列计算出命中率结束开始计算出页号在实存堆栈中查找该页号计算出命中率结束Y把新页放入栈顶，同时向下移动其余页号还有指令吗8LRU算法NYY是否有空闲页面？找到？在面中查找是否存在开始还有指令吗？计算出页号count++将该页导入内存页面，count=1从内存页面找出使用最少的页面当空闲页面计算出命中率结束NYN9NUR算法NYY是否有空闲页面？找到？在页面中查找是否存在开始还有指令吗？计算出页号count=1将该页导入内存页面，count=1从内存页面找出最近未使用的页面当空闲页面计算出命中率结束NYN10OPT算法NY是否有空闲页面？按早指令队列查找以后指令出每一面命中的距离，找出最大的或没命中的当空闲页面找到？在面中查找是否存在开始还有指令吗？计算出页号将该页导入空闲页面计算出命中率结束NYYN11四、详细设计本程序设计基本按照题目的要求进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变成相应的页地址流，并针对不同的算法计算出相应的命中率。4.1、数据结构4.1.1页面类型Typedefstruct{Intpn,pfn,count,time;}pl_type;其中pn为页号,pfn为面号,count为个周期内访问该页面次数time为访问时间。4.1.2页面控制结构pfc_struct{intpn,pfn;structpfc_struct*next;}typedefstructpfc_structpfc_type;pfc_typepfc[xy],*free_head,*busy_head;pfc_type*busy_tail;其中：pfc[xy]定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针。124.2.函数定义(1)voidinitialize():初始化函数,给每个相关的页面赋值。(2)voidFIFO():计算使用FIFO算法时的命中率。(3)voidLRU():计算使用LRU算法时的命中率。(4)voidOPT():计算使用OPT算法时的命中率。(5)voidLFU():计算使用LFU算法时的命中率。(6)voi