页式虚拟存储管理缺页中断的模拟系统的设计.docx

操作系统课程设计报告书燕山大学课程设计说明书课程设计名称：操作系统OS 题目：页式存储管理中页面置换（淘汰）的模拟程序 班级：计算机应用二班开发小组名称：CAMPUS课题负责人： 课题组成员：姓名 学号 班级 自评成绩 课题开发日期：2011-1-10至2011-1-14一概述1目的通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标缺页次数和缺页率，来对各种替换算法进行评价比较。2.主要完成的任务自行输入实际页数、内存可用页面数、存取内存时间、存取快表时间及缺页中断时间，然后由用户随机输入各页面号，模拟系统自动运行出FIFO、LRU、OPT、LFU四种算法的缺页次数、缺页率、命中率、总存取时间、存取平均时间等结果。 3 使用的开发工具（1）使用系统：Windows7（2）使用语言：C+（3）开发工具：Visual C+ 6.04 解决的主要问题设计的结果程序能实现FIFO、OPT、LRU、LFU算法模拟页式存储管理缺页中断，主要能够处理以下的问题：(1) 用户能够输入给作业分配的内存块数；(2) 用户能够输入给定的页面，并计算发生缺页的次数以及缺页率；(3) 程序可由用户输入页面序列；(4) 系统自动计算总存取时间及平均存取时间。二 使用的基本概念和原理1.概念FIFO 即先进先出页面置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。LRU 即最近最久未使用页面置换算法，该算法选择最近最久未使用的页面予以淘汰。OPT 即最佳值换算法，其选择淘汰的页面是在最长时间内不再被访问的页面。LFU 即最近使用最少页面置换算法，其淘汰的页面是最近一段时间内使用最少的页面。缺页中断 存取页面时页面不在内存中需从外存调入的现象。缺页次数 即在存取页面过程中发生缺页中断的次数。命中率 在存取过程中页面在内存中次数占页面存取总次数的百分比。总存取时间 即存取所有页面所消耗的总时间。存取平均时间 即存取一次页面平均所用的时间。2.原理页式存储管理把内存分割成大小相等位置固定的若干区域，叫内存页面，内存的分配以“页”为单位，一个程序可以占用不连续的页面，逻辑页面的大小和内存页面的大小相同，内外存的交换也以页为单位进行，页面交换时，先查询快表，若快表中找不到所需页面再去查询页表，若页表中仍未找到说明发生了缺页中断，需先将所需页面调入内存再进行存取。三总体设计通过对所解决的问题的实质的分析，即使用不同的算法对页表进行查询，分查到和查不到两种情况进行处理，主要是采用面向过程的技术路线，把解决问题的方法进行分步处理。软件主要采用函数调用的总体结构，把各种替换算法分别用函数实现，在主函数中进行调用，各函数之间相互独立。整个程序的主要流程就是先输入问题中需要用到的各种数据，如页面序列，实际页数，内存中的页数和存取时间等等。然后我们可以选择相应的替换算法进行分析替换，得到相应的存取时间和缺页情况。具体的流程图如下：图1请求分页流程图四详细设计 具体的设计使用的函数除了主函数中的输入输出函数外，大部分使用函数调用，所用的函数主要有四种替换算法函数FIFO,LRU,OPT,LFU以及所有替换算法中都要用到的查询函数Search,LFU中的使用次数最少函数 Min,OPT中计算使用距离的函数 Compfu, LRU中的最久未使用时间函数Max，各算法使用函数具体如下： void main()int m=0,t=0,N=0;coutm; Pro *p=new Prom;/p是用来放页面的地方 cout可用内存页面数N; Pro *page=new ProN;/page是放物理块的地方char c;int x,y,z;cout请输入存取内存时间(ns)x;cout请输入访问快表时间(ns)y; cout请输入缺页中断时间(ns)z;float n=0;Input(m,N,p,page);/m是页面的总长，N是物理块的长度do coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;coutu:LFU页面置换endl;cout按其它键结束c;if(c=f)/FIFO页面置换FIFO(p,page,m,N,x,y,z); if(c=l)/LRU页面置换LRU(p,page,m,N,x,y,z);if(c=o)/OPT页面置换OPT(p,page,m,N,x,y,z); if(c=u)/OPT页面置换LFU(p,page,m,N,x,y,z); while(c=f|c=l|c=o|c=u); 以上为主函数的内容。下面为所调用的函数int Search(int e, Pro *page ,int N) for(int i=0;iN;i+)if(e=pagei.num)return i;return -1;查询函数Search的参数为所要查询的页号e，快表中的页号page、以及快表中页数N，最后的返回值为所要查询页号在快表中的位置i或查不到的返回值-1.void FIFO(Pro p ,Pro page ,int m, int N, int x ,int y, int z) int a=0;float n=0; int i=0; int t=0; for(i=0;iN;i+)pagei.num=0;cout页面置换情况: endl;for(i=0;i=0) a+=(x+y);continue;else t=t%N;n+;paget.num=pi.num; t+;a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; FIFO替换算法中使用的参数有实际页表 p ,快表 page ,实际页数 m, 内存可用页面数N,快表存取时间 x ,内存存取时间y, 缺页中断时间 z，最后的返回值是缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。void LRU(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0; float n=0; int i=0; int t=0; for(i=0;iN;i+)pagei.num=0;pagei.time=N+2-i;cout页面置换情况: endl; while(i=0)a+=(x+y);paget.time=0; Else n+; t=Max(page,N); paget.num=pi.num; paget.time=0; a+=(3*x+z); for(int j=0;jN;j+)if(j=t)continue;paget.time+; i+; cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; LRU置换算法中的参数有实际页号 p,快表中的页号 page,实际页数 m, 内存可用页面数 N, 快表存取时间x, 内存存取时间 y, 缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。int Max(Pro *page,int N) int e=page0.time,i=0;int k=0;while(iN) if(epagei.time) k=i;i+;return k; Max函数中的参数有快表中页号page,内存可用页数N。返回值是最近最久未使用的页面位置k。void OPT(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0; float n=0; int i=0; int t=0; for(i=0;iN;i+) pagei.num=0; while(i=0)i+;else int temp=0,cn; for(t=0;tN;t+) if(tempCompfu(page,i,t,p,m) temp=Compfu(page,i,t,p,m);cn=t;pagecn=pi;n=n+1;i+;a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; OPT置换算法中的参数有实际页号 p,快表中的页号 page,实际页数 m, 内存可用页面数 N, 快表存取时间x, 内存存取时间 y, 缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。int Compfu(Pro *page,int i,int t,Pro p,int m) int count=0; for(int j=i;jm;j+)if(paget.num=pj.num )break; else count+;return count; Compfu函数中参数为快表中页号page,页面位置 i,页面在快表中位置 t,实际页表 p,实际页数m，返回值为下次使用的步数count。void LFU(Pro p,Pro page,int m,int N,int x,int y,int z) int a=0;float n=0;int i=0;int t=0;for(i=0;iN;i+) pagei.num=0;for(i=0;iN;i+)pagei.time=0;cout页面置换情况: endl;for(i=0;i=0)a+=(x+y);pagei.time+;continue;/else t=Min(page,N); tpaget.num=pi.num;paget.time=0; n+;a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; LFU置换算法中的参数有实际页号 p,快表中的页号 page,实际页数 m, 内存可用页面数 N, 快表存取时间x, 内存存取时间 y, 缺页中断时间z。返回值为缺页次数n，缺页率，命中率，总存取时间以及平均存取时间。int Min(Pro page,int N) int k=0;int min=page0.time;for(int i=0;ipagei.time)k=i;return k; Min函数使用的参数为实际页号page,内存可用页数N，返回值为置换位置k。五编码设计1. 开发环境的设置和建立本程序所使用的开发环境为Visual C+ 6.0，在Windows7系统中建立一个Win32 Console Application的工程，然后在工程里建立一个C+ source file的文件。2. 程序设计时需要注意的问题程序设计时需要注意调用函数的嵌套，各种替换算法中替换的位置确认，函数调用的实现3. 主要程序的代码设计及注释；#include #include #include struct Pro int num,time;/num存放具体的内容，time在不同算法里面有不同的意义; /它们是物理块和页面的数据结构int Input(int m,int N,Pro *p,Pro *page)/完成p数组和page的初始化工作/p数组是存放页面的空间，m是页面的长度，page是可以使用的物理块，N是物理块的大小 coutendl请输入各页面号endl; int *p1=new intm;for(int j=0;jp1j; for(int i=0;im;i+)pi.num=p1i;pi.time=0;return m;int Search(int e,Pro *page,int N)/算法里面都要用到它，它是找e页是否在page物理块中，N是物理块的大小for(int i=0;iN;i+)if(e=pagei.num)return i;/如果找到，就返回在物理块中的位置给Searchreturn -1;/找不到，就返回-1int Max(Pro *page,int N)/LRU算法用到的/找出在page块中，time最大的值和位置，同时位置返回，time最大，就代表了最久没被使用的int e=page0.time,i=0;int k=0;while(iN)/找出离现在时间最长的页面if(epagei.time) k=i;i+;return k; int Compfu(Pro *page,int i,int t,Pro p,int m)/OPT算法用到的，找出如果paget要等于p，并且在pipm这个区间内，走的次数，最大的数int count=0;/count是保存走的步数for(int j=i;jm;j+)if(paget.num=pj.num )break;/如果相等，跳出循环else count+;/不等就步数加1return count; int Min(Pro page,int N)/LFU算法用到的，page是可以使用的物理块，N是物理块的大小，找到出现次数最小的的数，并把位置返回 int k=0;int min=page0.time;for(int i=0;ipagei.time)k=i;return k;void FIFO(Pro p,Pro page,int m,int N,int x,int y,int z)/p数组是存放页面的空间，m是页面的长度，page是可以使用的物理块，N是物理块的大小 int a=0;float n=0;/n用来保存缺页的次数int i=0;/i是循环变量，它是表示走到页面的位置。int t=0;/t是用来表示物理块走到的位置for(i=0;iN;i+)/初试化页面基本情况pagei.num=0;cout页面置换情况: endl;for(i=0;i=0) a+=(x+y);continue;/找到相同的页面，就跳到下一次循环，不做处理。else /在找不到的时候，通过t=t%N,求出这次来替换物理块的位置 t=t%N;n+;/缺页数加1paget.num=pi.num; t+;/位置加1a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; void LFU(Pro p,Pro page,int m,int N,int x,int y,int z)/p数组是存放页面的空间，m是页面的长度，page是可以使用的物理块，N是物理块的大小， int a=0;float n=0;int i=0;int t=0;for(i=0;iN;i+)/初始化页面基本情况pagei.num=0;for(i=0;iN;i+)pagei.time=0;cout页面置换情况: endl;for(i=0;i=0)a+=(x+y);pagei.time+;/找到相同的页面，time加1continue;/else /找出使用最少的页面进行调换t=Min(page,N);/找到出现次数最小的的数，并把位置返回tpaget.num=pi.num;paget.time=0;/该页time清零n+;/缺页数加1a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl;void OPT(Pro p,Pro page,int m,int N,int x,int y,int z)/p数组是存放页面的空间，m是页面的长度 int a=0; /page是可以使用的物理块，N是物理块的大小 float n=0;/n用来保存缺页的次数 int i=0;/i是循环变量，它是表示走到页面的位置。 int t=0; /t是用来表示物理块走到的位置 for(i=0;iN;i+)/初始化页面基本情况pagei.num=0; while(i=0)i+;/如果找到了，就不做处理。else/如果找不到int temp=0,cn;/cn用来保存离后面最远的数for(t=0;tN;t+)/对物理块里面的每个数进行遍历if(tempCompfu(page,i,t,p,m)/temp用来保存/paget= pipm这个区间内，走的次数，最大的数temp=Compfu(page,i,t,p,m);cn=t;pagecn=pi;/把当前的值放要发生要走最远的数，也就最不可能最近出现的数n=n+1;/缺页数加1i+;/跳到下一次循环a+=(3*x+z);cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; void LRU(Pro p,Pro page,int m,int N,int x,int y,int z)/p数组是存放页面的空间，m是页面的长度 int a=0;/page是可以使用的物理块，N是物理块的大小 float n=0;/n用来保存缺页的次数int i=0;/i是循环变量，它是表示走到页面的位置。int t=0; /t是用来表示物理块走到的位置for(i=0;iN;i+)/初始化页面基本情况pagei.num=0;pagei.time=N+2-i;cout页面置换情况: endl; while(i=0)a+=(x+y);paget.time=0;/如果找到，就要把当前的paget.time次数清零 else/找不到的时候，发生缺页 n+; /缺页数加1t=Max(page,N);/找出page物理块里面，最久没被时候的数，同时把最久没被时候的数在物理块里的位置传给t paget.num=pi.num;/最久没被使用的是被现在的数代替paget.time=0;/同时清零a+=(3*x+z); for(int j=0;jN;j+)/把缺页以外的数，把它没被使用的次数加1if(j=t)continue;paget.time+; i+;/跳到下一次循环 cout缺页次数：n 缺页率：n/m 命中率：1-n/m 总存取时间：ans 存取平均时间：a/mnsendl; void main()int m=0,t=0,N=0;coutm; Pro *p=new Prom;/p是用来放页面的地方 cout可用内存页面数N; Pro *page=new ProN;/page是放物理块的地方char c;int x,y,z;cout请输入存取内存时间(ns)x;cout请输入访问快表时间(ns)y; cout请输入缺页中断时间(ns)z;float n=0;Input(m,N,p,page);/m是页面的总长，N是物理块的长度do coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;coutu:LFU页面置换endl;cout按其它键结束c;if(c=f)/FIFO页面置换FIFO(p,page,m,N,x,y,z); if(c=l)/LRU页面置换LRU(p,page,m,N,x,y,z);if(c=o)/OPT页面置换OPT(p,page,m,N,x,y,z); if(c=u)/OPT页面置换LFU(p,page,m,N,x,y,z); while(c=f|c=l|c=o|c=u); 4. 解决的技术难点、经常犯的错误。主要技术难点四种置换算法实现，经常犯的错误就是算法实现出现错误，计算结果和实际结果不一致，以及函数调用出现问题。六 测试时出现过的问题及其解决方法主要问题是页面置换时出现问题，程序计算出来的结果和实际结果不一致，缺页次数计算出现错误，后来经过坚持不懈的调试修改和分析，成功的解决了这个计算错误的问题。七程序测试结果八软件使用说明基本功能：在页式存储管理方式中实现四种算法的页面置换以及存取时间，缺页次数，命中率等的输出。需要运行的环境：Visual C+ 6.0安装：在Windows7系统中建立一个Win32 Console Application的工程，然后在工程里建立一个C+ source file的文