课程设计--页面置换算法模拟—最近最久未使用（LRU）

课程设计（论文） 题 目：页面置换算法模拟最近最久未使用（LRU） 院 （系）： 信息与控制工程系 专业班级： 计算机2012 姓 名： 孙奇 学 号： 201206060223 指导教师： 曾应员 2015年1月23日西安建筑科技大学华清学院课程设计（论文）任务书专业班级： 计算机1201班 学生姓名： 孙奇 指导教师（签名）： 曾应员 一、课程设计（论文）题目页面置换算法模拟-最近最久未使用（LRU）算法：编写一个页面置换算法程序，采用最近最久未使用（LRU）置换算法，在需要页面调出时，选择在最近时期使用最久未使用的页面作为淘汰页。二、本次课程设计（论文）应达到的目的操作系统课程实践性比较强。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等） 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：最近最久未使用（LRU）置换算法四、应收集的资料及主要参考文献： 操作系统经典算法的编程实现资料非常丰富，可以在图书馆找书籍或在因特网上找资料，都很容易找到，但是大部分代码是不全的，不能直接运行，希望大家只是把它当参考，编码还是自己做。 参考文献：【1】汤小丹、梁红兵、哲凤屏、汤子瀛 编著.计算机操作系统（第三版）.西安：西安电子科技大学出版社，2007.5【2】史美林编.计算机操作系统教程.北京：清华大学出版社，1999.11【3】徐甲同编著.操作系统教程.西安：西安电子科技大学出版社，1996.8【4】Clifford，A.Shaffer编著.数决结构与算法分析(C+版).北京：电子工业出版社，2005.7【5】蒋立翔编著.C+程序设计技能百练.北京：中国铁道出版社，2004.1五、审核批准意见教研室主任（签字） 设计总说明 本次课程设计是在学习完操作系统教程后，进行的一次全面的综合训练，通过课程设计，让计算机专业的学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。 课程设计要求是通过对页面，页表地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。同时此次课程设计的主要内容有以下三点：1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率 3）页面置换算法-最近最久未使用（LRU）算法关键字：页面置换，最近最久未使用，看未来等目录1.设计目的42.问题描述53.需求分析64.概要设计75.详细设计106.调试分析167.使用说明178.设计总结179.参考文献1810.程序源代码19 操作系统课程设计页面置换算法-最近最久未使用LRU算法1. 设计目的“操作系统”是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要的实践环节。 操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统基本理论与管理方式。在算法基础上，解决实际的管理功能的问题，提高学生实际应用、编程的能力。课程设计要求学生在完成程序设计的同时能够撰写比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用2.问题描述2.1作用 在进城过程中，若其访问的页面不在内存中，而需要把他们调入内存，但内存已经没有空闲空间，为了保证该进程正常的运行，系统必须从内存中调入一页程序或程序送到磁盘对换区中，但应将那个页面调出，需根据一定的算法来确定。LRU就是解决这样问题的。最近最久未使用（LRU）的页面置换算法是根据页面调入内存后的使用情况作出决策的，由于无法预测各页面将来的使用情况只能利用“最近的过去”作为“最近的将来”的近似，因此LRU算法是选择最近最久未使用的页面作为淘汰，该算法予以每个页面一个访问字段，用于记录一个页面自上次被访问以来所经历的时间T当需要淘汰一个页面时选择现有页面中其T值最大的，及最近最久未使用的页面予以淘汰，LRU算法是“向前看的”，即根据各页面以前的情况来判断，而页面的过去和未来走向之间并无必然的联系。2.2算法的局限LRU虽然是一个比较好的算法，但要求系统有较多的支持硬件，为了了解一个进程在内存中的各个页面有多少时间为被进程访问，以及如何快速的知道那一页是最近最久未使用的页面，须有寄存器和栈两类硬件之一的支持。3需求分析3.1数据需求1进程块数和物理块数要求是整形，2进程数要求有个限度，可以是户自定义，也可以填默认无限3缺页次数为整形4缺页率为浮点型3.2基本功能1.需要有菜单函数用于显示主菜单，显示操作内容比如进程数(随机显示)，物理块数等2必须有算法函数void LRU（最近最久未使用算法）：此函数是需要用户在程序中自己自定义填好的，此函数是主菜单中主要部分，即用户自定义的进程数和物理块数。3要有显示进程数和块数函数的函数，用于显示用户自定义的进程数和块数的情况。4显示函数，显示每次换页后的结果函数,，此函数是显示在LRU算法的执行过程中每次换页的情况。显示一定不用换页的函数、：此函数是显示最近使用过的页面，即不用换页的结果。5计算缺页次数，系统可以自动计算出缺页次数并记录，用显示函数显示出来。6计算缺页率，可以根据用户自己输入的进程数计算出缺页率。7退出程序3.3任务四采用最近最少使用页淘汰算法(LRU)实现。为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率。用户界面需求：简洁、易用、易懂、友好的用户界面3.4非功能需求硬件要求：装有VC+的计算机。可靠性需求：保证用户在正常使用本系统时，用户的操作或误操作不会产生数据的丢4概要设计 4.1数据结构typedef struct BLOCK/声明一种新类型-物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问 BLOCK; int pc;/程序计数器，用来记录指令的序号 int n;/缺页计数器，用来记录缺页的次数 static int temp320;/用来存储320条随机数 BLOCK blockBsize; /定义一大小为4的物理块数组 void init(); /程序初始化函数 int findExist(int curpage);/查找物理块中是否有该页面 int findSpace();/查找是否有空闲物理块 int findReplace();/查找应予置换的页面 void display();/显示 void suijishu();/产生320条随机数,显示并存储到temp320 void pagestring();/显示调用的页面队列 void LRU();/LRU算法 栈结构可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 遵从先进先出原则数组结构例如static int temp320;/用来存储320条随机数 BLOCK blockBsize; /定义一大小为4的物理块数组用于存放初始输入数据以及记录页面置换后的数据。4.2系统包含的函数1辅助函数辅助函数用来记录原始的用来页面置换的输入数据；使用的实数组，这样方便记录，以及可以根据数据的大小来动态的分配内存大小，以及记录页面号，记录调入内存时间 ，页面逻辑结构，结构为方便算法实现设计，内存单元数，暂保存内存当前的状态：缓冲区记录调入队列调入队列计数变量，初始化内存单元、缓冲区等2随机读取函数，3取得在内存中停留最久的页面,默认状态下为最早调入的函数4判断页面是否已在内存中函数5LRU核心部分函数6主程序函数7输出函数4.3函数之间的关系主函数LRU函数判断函数 显示 函数 调入函数 辅助函数 输出函数随机函数 是4-3 函数关系图4.4系统功能模块图开始主菜单调入数据模块进入显示模块判断是否进入队列进 n