请求调页存储管理方式的模拟LFU(含源代码).doc

课 程 设 计课程设计名称：请求调页存储管理方式的模拟4 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间： 2012.12.24-2012.12.28 计算机科学 专业课程设计任务书学生姓名专业班级学号题 目请求调页存储管理方式的模拟4课题性质其它课题来源自拟课题指导教师同组姓名无主要内容1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：最少访问（LFU）算法。任务要求 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。参考文献任满杰等操作系统原理实用教程 电子工业出版社 2006汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 2001张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 罗宇等 操作系统课程设计机械工业出版社 2005审查意见指导教师签字：教研室主任签字： 年 月 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页填 表 说 明1“课题性质”一栏：A工程设计；B工程技术研究；C软件工程（如CAI课题等）；D文献型综述；E其它。2“课题来源”一栏：A自然科学基金与部、省、市级以上科研课题；B企、事业单位委托课题；C校、院（系、部）级基金课题；D自拟课题。201 需求分析1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：最少访问（LFU）算法。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。所有内容均为独立完成。2 概要设计本实验主要分为以下几个重要实现过程：（1） 首先由对应函数按照题目要求产生对应的320条随即指令。（2） 当指令到来时，首先查询4个物理模块中是否含有当前指令，如果有则直接下一条指令，若没有就进行判定查找物理块中是否还有空闲盘块，有该指令则直接调入，无则要发生页面置换。（3） 按照一定规则（LFU）进行页面置换，知道最后一条指令完成后，显示缺页次数和缺页率。程序中自定义的函数（函数名，参数，以及功能）及结构等如下：#define Bsize 4 定义一个全局的物理块大小4struct BLOCK 物理块类型的申明int pagenum; /用于存储页号int use; /用于计算最近使用次数;int num=0; /记录指令的序号int n=0; /记录缺页的次数static int temp320; /用来存储320条指令struct BLOCK block4; /大小为4的物理块数组int findExist(int curpage);/查找物理块中是否有该页面int findSpace(); /查找是否有空闲物理块int findReplace(); /查找应予置换的页面void display(); /显示置换过程void zhiling(); /产生320条指令,显示并存储到temp320,并调度页号队列void LFU(); /LFU算法3 运行环境软件：Windows 98及以上操作系统，Microsoft Visual C+ 6.0版本硬件： 512M CPU内存及以上的计算机4 开发工具和编程语言 开发工具：Microsoft Visual C+ 6.0编程语言：C语言5 详细设计（1）产生320条指令,显示并存储到temp320,并调度页号队列320条随即指令的产生规则如下： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。代码如下：void zhiling()int i;srand(int)time(NULL); 产生随机数必须调用printf(随机产生第一条指令号(0320)：);num=rand()%320; 产生第一条随机指令printf(%d,num);printf(nnt按照要求产生320个随机数：);printf(n*n);for(i=0;i320;i=i+5) 按产生规则产生tempi=num;tempi+1=num+1;tempi+2=rand()%(num+1);tempi+3=tempi+2+1;tempi+4=tempi+3+1+rand()%(320-tempi+3-1);num=rand()%320;for(i=0;i320;i+) 输出产生的320条指令printf( %03d,tempi);if(i+1)%10=0)printf(n);printf(nn 对应的调用页面队列);printf(n*n);for(i=0;i320;i+) 输出对应值指令的调用页面printf( %02d,tempi/10);if(i+1)%10=0)printf(n);（2）查找物理块中是否有该页面当指令页curpage到达时与当前物理块中存放的页面blocki.pagenum比较。int findExist(int curpage)int i;for(i=0; iBsize; i+)if(blocki.pagenum = curpage )return i;/检测到内存中有该页面，返回block中的位置return -1;（3）查找是否有空闲物理块在页面中没有该指令的页号时查找物理块中是否还有空闲块。int findSpace()int i;for(i=0; iBsize; i+)if(blocki.pagenum = -1)return i;/找到空闲的block，返回block中的位置return -1;（4）查找应予置换的页面当新的指令到达且物理块已无空闲时，将LFU算法传递过来的每个页面的使用计数进行比较，找出最小的min作为将被置换的页面。int findReplace()int i,min=0;for(i=0;iBsize;i+)if(blocki.useblockmin.use)min=i;/找到应予置换页面，返回BLOCK中位置return min;（5）显示置换过程按要求将物理块中所发生的所有变动（即空块进入和满块置换）的过程予以输出显示。void display()int i;for(i=0; iBsize; i+)if(blocki.pagenum != -1)printf( %02d,blocki.pagenum);printf(n);（6）LFU算法LFU算法部分为整个实验的核心，主要实现页面置换的过程。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。void LFU ()int exist,space,position ;int page,i,j,k;double pr;for(i=0;i320;i+)num=tempi; /指令记录号page=num/10; /页号exist = findExist(page); /是否有记录if(exist=-1) /没有space = findSpace(); /判断是否为空的标记if(space!= -1) /有空盘块blockspace.pagenum=page; display();n=n+1; /计算缺页次数else /没有空盘块for(k=0;kBsize;k+)for(j=i;ji+64;j+) /自行设定的访问时间段if(blockk.pagenum=tempj/10)/有使用记录blockk.use+; /记录使用次数 else /最近未使用;position=findReplace(); blockposition.pagenum=page; display();n+; /计算缺页次数pr=n/320.0;printf(缺页次数:%d n,n);printf(缺页率:%.3lfn,pr);printf(命中率:%.3lfn,1-pr);（7）main函数void main() int i;for(i=0;iBsize;i+) /物理块中变量的初始化blocki.pagenum=-1; /初始没有赋值blocki.use=0; /页面使用次数zhiling();printf(nn最少使用算法LFU实现:n);printf(*n);LFU ();6 调试分析本程序为一次性简易模式，不需要用户键入其他任何指令只需点击执行，程序便输出全部过程及结果。点击执行后程序首先自动产生第一条随机指令，然后依照要求产生后续4条，以此循环知道产生共计320条完整指令，并以每10条指令为一页的规则显示输出对应页面队列。经调试没有任何问题。在进行LFU算法的实现上很曲折。该算法选择在最近使用最少的页面作为淘汰页，由于存储器具有较高的访问速度，每毫秒可能对某个页面连续访问成千上万次，所以通常难以采用计数器，因为这样会访问量过大，每次都要进行比较，会影响执行速度。书上建议采用移位寄存器，但是由于在每一时间间隔内，只是用移位寄存器的一位来记录页的使用情况，访问一次和10000次是等效的。因此，LFU算法并不能真正反映页面的使用情况。考虑到这样的客观因素我询问了老师，老师也说这个事有争议的，我可以选择使用LRU实现。在综合考虑过过后，还是决定采用计数的方式完成。7 测试结果图1 随机指令1 图2 随机指令2 图3 页面队列1 图4 页面队列2 图5 结果图1 图6 结果图2 图7结果图3 图8 结果图4 图9结果图5 图10结果图6 图11结果图7 参考文献1 任满杰等，操作系统原理实用教程，电子工业出版社，20062 汤子瀛，计算机操作系统（修订版），西安电子科技大学出版社，20013 张尧学，计算机操作系统教程实验指导，清华大学出版社，2000 4 罗宇等，操作系统课程设，计机械工业出版社，20055 何钦铭，C语言程序设计，高等教出版社，2008心得体会一周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我独立去准备、去做成一件事的能力。在这次设计过程中，体现出了自己单独设计模拟算法的能力以及综合运用知识的能力，让我切身体会到了学以致用、突出自己劳动成果的喜悦心情，从中也发现自己平时学习中的不足之处和薄弱环节，同时也印证了一个道理“高山起微尘，千里始足下”。在此要感谢我们的于俊伟老师，虽说接触不多，但老师严谨细致、一丝不苟的作风深深影响了我；这次课程设计的最重要环节LFU，也离不开老师您的引导，正因为老师宽容的态度和不拘一格的教导，我才能够很顺利的完成了这次课程设计。另外也要特别感谢对我帮助过的同学们，谢谢你们对我的帮助和支持。由于本人的设计能力有限，在设计过程中难免会有瑕疵，恳请老师们多多指教,我十分乐意接受你们的批评与指正，因为这将会提升自我完善自我。信息科学与工程 学院课程设计成绩评价表课程名称：操作系统原理设计题目：请求调页存储管理方式的模拟4（LFU）专业：计算机科学与技术 班级： 姓名： 学号：序号评审项目分 数满分标准说明1内 容思路清晰，语言表达准确，概念清楚，论点正确；设计方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，工作量适中2创 新内容新颖，设计能反映新技术，对前人工作有改进或突破，或有独特见解3完整性、实用性整体构思后合理，理论依据充分，设计完整，实用性强4数据准确、可靠数据准确，算法设计合理5规 范 性设计格式、绘图、实验数据、标准的运用等符合有关标准和规定6纪 律 性遵守课程设计纪律，听从指导教师安排，设计过程态度认真7答 辩准备充分，思路清晰、论点正确、对设计方案理解深入，问题回答有理有据，简明正确总 分综合意见 在实验中思路清晰，语言表达准确，概念清楚，论点正确；课程设计设计方法科学，分析归纳合理；结论严谨。整体任务饱满，工作量适中。内容较为新颖，设计能反映新技术。整体构思前后后合理，理论依据充分，设计完整。数据准确，算法设计合理。设计格式、实验数据、标准的运用等符合有关标准和规定。遵守课程设计纪律，听从指导教师安排，设计过程态度认真。准备充分，思路清晰、论点正确、对设计方案理解深入，问题回答有理有据，简明正确。 指导教师 2013年 1 月 5 日附：源代码#include#include#include#include#define Bsize 4struct BLOCK /声明物理块类型int pagenum; /页号int use; /最近使用次数;int num=0; /记录指令的序号int n=0; /记录缺页的次数static int temp320; /用来存储320条指令struct BLOCK block4; /大小为4的物理块数组/*/int findExist(int curpage); /查找物理块中是否有该页面int findSpace(); /查找是否有空闲物理块int findReplace(); /查找应予置换的页面void display(); /显示置换过程void zhiling(); /产生320条指令,显示并存储到temp320,并调度页号队列void LFU(); /LFU算法/*/int findExist(int curpage)/查找物理块中是否有该页面int i;for(i=0; iBsize; i+)if(blocki.pagenum = curpage )return i;/检测到内存中有该页面，返回block中的位置return -1;/*/int findSpace()/查找是否有空闲物理块int i;for(i=0; iBsize; i+)if(blocki.pagenum = -1)return i;/找到空闲的block，返回block中的位置return -1;/*/int findReplace()/查找应予置换的页面int i,min=0;for(i=0;iBsize;i+)if(blocki.useblockmin.use)min=i;/找到应予置换页面，返回BLOCK中位置return min;/*/void display()/显示置换过程int i;for(i=0; iBsize; i+)if(blocki.pagenum != -1)printf( %02d,blocki.pagenum);printf(n);/*/void zhiling()/产生320条指令,显示并存储到temp320,并调度页号队列int i;srand(int)time(NULL);printf(随机产生第一条指令号(0320)：);num=rand()%320;printf(%d,num);printf(nnt按照要求产生320个随机数：);printf(n*n);for(i=0;i320;i=i+5) tempi=num;tempi+1=num+1;tempi+2=rand()%(num+1);tempi+3=tempi+2+1;tempi+4=tempi+3+1+rand()%(320-tempi+3-1);num=rand()%320;for(i=0;i320;i+)printf( %03d,tempi);if(i+1)%10=0)printf(n);printf(nn 对应的调用页面队列);pr