朱文涛分页系统模拟实验

1、 操作系统课程设计任务书题目：模拟分页系统的实现学生姓名： 朱文涛 学号： 班级： 物联网工程一班 题目类型：软件工程（R） 指导教师： 贾娟娟 / 杨书鸿 一、设计目的学生通过该题目的设计过程，掌握虚拟存储器管理的原理、软件开发方法并提高解决实际问题的能力。二、设计任务1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。2、模拟请求分页虚拟存储管理中的硬件地址变化过程，并采用先进现出或LRU算法实现分页管理的缺页调度。三、设计要求1、 分析设计要求，给出解决方案（要说明设计实现所用的

2、原理、采用的数据结构）。2、 设计合适的测试用例，对得到的运行结果要有分析。3、 设计中遇到的问题，设计的心得体会。4、文档：课程设计打印文档每个学生一份，并装在统一的资料袋中。 5、光盘：每个学生的文档和程序资料建在一个以自己学号和姓名命名的文件夹下，刻录一张光盘，装入资料袋中。四、 提交的成果1. 设计说明书一份，内容包括：1) 中文摘要100字；关键词3-5个；2) 设计思想；3）各模块的伪码算法；4）函数的调用关系图；5）测试结果；6）源程序（带注释）；7）设计总结；8) 参考文献、致谢等。2. 刻制光盘一张。五、 主要参考文献1. 汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出

3、版社.2. 王清，李光明.计算机操作系统.冶金工业出版社.3.孙钟秀等. 操作系统教程. 高等教育出版社4.曾明. Linux操作系统应用教程. 陕西科学技术出版社. 5. 张丽芬，刘利雄.操作系统实验教程. 清华大学出版社.6. 孟静，操作系统教程原理和实例分析. 高等教育出版社7. 周长林，计算机操作系统教程. 高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出版社10.张坤.操作系统实验教程，清华大学出版社六、 各阶段时间安排（共2周）周次日期内容地点第1周星期一二教师讲解设计要求查找参考资料教室图书馆星期三五算法设计，编程实现教

4、室第2周星期一三调试测试，撰写文档教室星期四五检查程序，答辩教室 2015年12月9日 摘 要 为配合计算机操作系统课程的教学，加深对整个课程体系的理解，领会操作系统工作原理和理解操作系统的实现方法，提高学生的实践动手能力，提高学生科技论文写作能力，特开设此课程设计。本模拟系统是先进先出页面淘汰算法FIFO，最近最少使用LRU页面淘汰算法.同时系统可以随意设置当前分配给作业的物理块数。系统运行时任意输入一个页面访问序列可以设置不同的页面置换算法和物理块数，输出其页面淘汰的的情况，计算其缺页次数和缺页率。系统结束后，比较同一个页面访问序列，可以都处在不同的页面置换算法和物理块数的情况下，其产生的

5、缺页次数和缺页率。使用FIFO算法，由于测试数据相同的页面比较少，所以采用FIFO算法时，需要置换的页面多，比较繁琐，因此说FIFO算法的性能不是很好。使用LRU的算法，此算法显示LRU算法的使用比较繁琐，总的来说，LRU算法优于FIFO算法。在实际应用中一般使用LRU算法实现其页面的置换。关键词：FIFO;LRU;页面置换算法；缺页次数；缺页率目 录 1绪 论11.2设计思想21.2.1先进先出法21.2.2最近最久未使用2 1.3基础知识2 1.3.1请求分页中的硬件支持3 1.3.2内存分配策略和分配算法3 1.3.3请求分页策略4 1.3.4硬件地址的变换过程4 2相关的各模块的伪码算

6、法6 2.1 void changeaddr(struct Page p,int logaddr) 6 2.2 void chushihua()7 2.3 FIFO算法的实现8 2.4 LRU算法的实现11 3函数的调用关系图14 4调试结果15 4.1分页系统主界面15 4.2硬件地址变换算法界面15 4.3选择输入指令16 4.4逻辑地址向物理地址转换16 4.5由于缺页而产生的中断17 4.6进入页面置换算法界面18 4.7页面置换算法(FIFO、LRU)M=318 4.8页面置换算法(FIFO、LRU)M=4195源程序代码216总 结33参考文献34致 谢351绪 论 分页式虚拟存储

7、系统将作业信息的副本存放在磁盘中，不把作业的程序和数据全部装入主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再把它们动态地装入。虚拟存储的基本思想是基于程序的局部性原理，仅把目前需要的部分程序加载到内存，其余暂时不用的程序及数据还保留在辅存中。在进程运行过程中，如果所要执行的程序不在内存，系统要将要执行的程序段自动调入内存。 此时如果内存已满，则要通过置换操作将暂时不用的程序段先调出到辅存，然后将所需的程序段调入内存，继续执行该进程。 虚拟存储器的引入，实际上是利用了存储管理中逻辑地址空间和物理地址空间的关系，将计算机的内存和辅存结合起来，使得用户感觉具有大容量

8、的内存，虚拟内存在将逻辑地址转换成物理地址时，必须通过一个内存管理单元MMU（Memory Management Unit）来完成。 存储管理一直是操作系统中的重要组成部分，因为冯诺依曼体系结构就是建立在存储程序概念上的，访问存储器的操作占CPU时间的70%左右。计算机系统中的存储器一般分为主存储器（简称主存、内存）和辅助存储器（简称辅存）。由于CPU只能直接与内存进行通信，因此计算机系统的程序以及与该程序相关的数据，只有被装入到内存中才能有效地执行。计算机系统能否高效地管理内存空间，不仅直接反映存储器的利用率，还会影响整个操作系统的性能。1.1设计任务 1了解UNIX的命令及使用格式，熟悉U

9、NIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。模拟请求分页虚拟存储管理中的硬件地址变化过程，并采用先进现出或LRU算法实现分页管理的缺页调度。1.2设计思想1.2.1先进先出法（FIFO）该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容都依次向底移一位，需要访问的内容存入数组0号单元，即最顶部，这时缺页数加1；当不需要进行页面置换，即所需访问的内容在内存中时，不需要操作，继续读下一条指令。这样就实现了总是淘汰最先进入内存的

10、页面，选择了在内存中驻留时间最久的页面予以淘汰。1.2.2最近最久未使用（LRU） 该算法将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容们都依次向底移一位，需要访问的内容存入数组0号单元，即最顶部，这时缺页数加1；当不需要进行页面置换，即所需访问的内容在内存中时，将要访问的指令移到内存顶部，其他指令依次向下移一位，这样就把最久不用的指令沉到了底部，有必要时淘汰，即实现了总是淘汰最近最久未使用的指令。1.3基础知识1.3.1请求分页中的硬件支持1.页表机制用于地址转换；增加页表项：页号、页架号、状态位、访问字段、修改位、外存地址

11、2.缺页中断机构所要访问的页不在内存时，便引发一次缺页中断；3.与常规中断的不同之处：在指令执行期间产生和处理中断信号；一条指令在执行期间，可能产生多次缺页中断。4.地址变换机构首先检索快表，若找到，修改页表项中的访问位，然后利用页表项中给出的页架号和页内地址，形成物理地址。如果在快表中未找到相应的页表项，检索内存中的页表，察看页表中的状态位，若该页已经调入内存，填写快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，产生缺页中断，请求OS把该页调入。1.3.2内存分配策略和分配算法最小物理块（页架）数的确定保证进程正常运行所需的最少页架数；与指令的格式、功能和寻址方式有关。1.页架的分配

12、策略固定分配局部置换：进程占据的内存页架数不变；但分配时，难于确定某个进程的页架数。可变分配全部置换：空闲页架由OS管理。可变分配局部置换：当进程缺页率较高或较低时，能由OS对其占据的页架数加以调整。2.页架的分配算法平均分配算法将系统中所有可供分配的页架，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配页架的算法。考虑优先权的分配算法优先权高的一次分得的页架数多。1.3.3请求分页策略何时调入页面的问题预调页策略：首次调入内存时请求调页策略：运行中的发生缺页现象时从何处调入页面的问题“文件区”与“对换区”：页面的调入过程响应中断、保存CPU环境、查找页表（快表），得到该页在外存中的

13、块号，启动磁盘IO读入；如果内存已满，先置换，在调入；最后修改页表（快表）对应项的内容。1.3.4硬件地址的变换过程(1)请求分页虚拟存储管理技术是把作业地址空间的全部信息存放在磁盘上。当作业被选中运行时,先把作业的开始几页装入主存并启动运行。为此在为作业建立页表时,应说明哪些页已在主存,哪些页不在主存。“状态位”用于指示该页是否已经调入了内存。该位一般由操作系统软件来管理，每当操作系统把一页调人物理内存中时，置位。相反，当操作系统把该页从物理内存调出时，复位。CPU对内存进行引用时，根据该位判断要访问的页是否在内存中，若不在内存之中，则产生缺页中断。“修改位”表示该页调入内存后是否被修改过。

14、当CPU以写的方式访问页面时，对该页表项中的修改位置位。该位也可由操作系统软件来修改，例如，当操作系统将修改过页面保存在磁盘上后，可将该位复位。“外存地址”用于指出该页在外存上的地址，供调人该页时使用。“访问字段”用于记录本页在一定时间内被访问的次数，或最近已经有多长时间未被访问。(2)作业执行时,指令中的逻辑地址指出参加运算的操作数(或指令)地址中的页号和页内偏移量.硬件地址转换机构按页号查页表。若该页的标志为1,则表示该页已在主存,从而找到该页对应的主存块号。根据关系式:绝对地址=块号*块的长度+页内偏移量；计算出欲访问的主存地址。由于页号为2的整次幂,所以只要将块号与页内偏移量相拼接,放

15、入主存地址寄存器即可。按照该地址取指令或取操作数,完成指定的操作.(3)设计一个”地址变换”程序,模拟硬件地址变化过程。当访问的页在主存时,则形成绝对地址后,不去模拟指令的执行,而是输出被转换的地址。当访问的页不在主存时,输出”该页不在主存,产生缺页中断”,以表示产生一次缺页中断。(4) 进行缺页中断处理.中断返回后,重新执行该指令。假定主存的每块长度为64个字节,现有一个具有8页的作业,系统为其分配了4个主存块(即m=4),且最多分4块。其中第0页至第3页已经装入主存。运行设计的地址变换程序,显示或打印运行结果。(5)先进先出算法(FIFO)。选择装入最早的页面置换。可以通过链表来表示各页的

16、装入时间先后。FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，如果对个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。(6)最近最久未使用算法(LRU)。选择内存中最久未使用的页面被置换，这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。LRU可用如下的硬件机构帮助实现：一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。2相关的各模块的伪

17、码算法2.1 void changeaddr(struct Page p,int logaddr) /地址变换并实现模拟请求分页虚拟存储管理中的硬件地址变化过程。 logaddr比上64为页面号码 记为j logaddr对64取余为起始地址记为k for if（找到对应的页面号码） if（在内存中） 物理地址=对应页面的主存号*64+k 输出物理地址 输出此页面的对应信息Elsecout该页不在主存,产生缺页中断endl; 详细设计如下：void changeaddr(struct Page p,int logaddr) /地址变换 int j=logaddr/64;/对应的块号int k=l

18、ogaddr%64;/对应的偏移量int flag=0;int addr;for(int i=0;i8;i+)if(pi.pno=j)/找到对应的页号if(pi.flag=1)/页面标志为1addr=o*64+k;cout物理地址为: addrendl;cout详细信息: t页面号：pi.pnot主存号:ot偏移量：kendl;flag=1;break;if(flag=0)cout该页不在主存,产生缺页中断endl; 2.2 void chushihua（）函数 功能：先由Srand()和Rand()函数定义和随机产生指令序列，然后将指令序列变换成相应的页地址流存入地址流数

19、组里。void chushihua()/初始化函数int t;srand(time(0);/随机产生指令序列 p=12+rand()%32;cout地址流序列：;coutendl;for(int i=0;i=0;i-)coutyemianliui ;coutendl;2.3 FIFO算法的实现功能：实现FIFO算法，淘汰最先进入内存的页面并根据缺页数算出缺页率率。 FIFO算法实现时： 如M=4时 进入一个页面时 If（此页面在内存中） 则fifo32不变 else For循环 把fifok=fifok-1; 最后fifo0=yemianliue 详细设计如下： void FIFO(int n

20、) /FIFO算法，n是M的值int i;int q=p;int e;int queye=0;int flag;int fifo32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(fifoi=yemianliuq)flag=1;break;if(flag=0)int m=n-1;int k=m;while(m-)fifok=fifok-1;k-;fifo0=yemianliue;queye+;coutM=n时FIFO的缺页率为：(1-(double)queye/p)*100% ;FIFO（）函数流程图否是是否开始得到执行的指令指令是否在内存中queye加1，指令

21、存入内存，最先存入指令被淘汰下面是否还有指令 结束得出命中率否图2-4LRU函数流程图2.4 LRU算法的实现功能：实现LRU算法，淘汰最近最久未使用的页面并根据缺页数算出缺页率率。 LRU算法实现时： 如M=4时 进入一个页面时 If（此页面在内存中） 则flag=1，记录位置k else flag=0；if（flag=1）把k前面的依次后移一位，即：lruk=lruk-1; 最后lru0= yemianliue If(flag=0)For循环 把lruk=fifok-1; 最后lru0=yemianliue详细设计如下：void LRU(int n)/LRU算法int i;int q=p;

22、int e;int queye=0;int flag;int flag1;int y;int lru32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(lrui=yemianliuq)flag=1;flag1=i;break;if(flag=0)int m=n-1;int k=m;while(m-)lruk=lruk-1;k-;lru0=yemianliue;queye+;else if(flag=1) y=flag1;while(y-)lruflag1=lruflag1-1;flag1-;lru0=yemianliue;coutM=n时LRU的缺页率为：(1-

23、(double)queye/p)*100%endl; LRU（）函数流程图否是是否 开始得到执行的指令指令是否在内存中queye加1，指令存入内存，淘汰数组底部指令下面是否还有指令 结束 得出缺页率将到指令移数组顶部，其他依次下移一位是否 图2-4LRU函数流程图3 函数的调用关系图3-1函数的调用关系图4调试结果4.1分页系统主界面： 通过运行程序，进入主界面。选择1进入硬件地址变换算法，选择2进入页面置换算法。 图 4-1分页系统界面4.2 硬件地址变换算法界面： 在主界面选择1进入硬件地址变换算法界面。图4-2硬件地址转换界面4.3 选择输入指令： 在硬件地址变换算法主界面选择1进行输入

24、命令，选择2返回上一级。当输入命令为1时显示此界面： 图4-3硬件地址转换选择界面4.4 逻辑地址向物理地址转换： 输入指令的逻辑地址：12 得到物理地址及其详细的信息。 图4-4地址转换4.5 由于缺页而产生的中断： 输入逻辑地址1234产生中断，即所要访问的页不在内存时，便引发了缺页中断。 图4-5地址转换4.6 进入页面置换算法界面： 输入选择2进入返回主界面，选择2进入页面置换算法界面：选择1进入页面置换算法，输入2返回上一级。 图4-6页面置换算法界面4.7 页面置换算法(FIFO、LRU)M=3 输入 1进行页面置换，以下为其过程 图4-7-1 FIFO的算法 4.7.2当M=3时

25、LRU时的置换过程：图4-7-2LRU算法4.8 页面置换算法(FIFO、LRU)M=4 4.8.1当M=4时的置换过程： 图4-8-1 FIFO的算法4.8.2当M=4时的置换过程： 图4-8-2LRU算法5源程序代码#include#include#include#include #include using namespace std;void chushihua();/初始化函数void FIFO(int n) ; /FIFO算法，n是M的值void LRU(int n);/LRU算法void ymzh();void yemianzhihuan();void changeaddr(st

26、ruct Page p,int logaddr);void dizhizhuanhuan();void menu();int yemianliu32=0;/全局变量数组，地址流int p; struct Pageint pno;/页号int flag;/标志位int cno;/主存号int modf;/修改位int addr;/外存地址Page; /全局变量p是一共有多少地址流void chushihua()/初始化函数int t，i;srand(time(0);/随机产生指令序列 p=12+rand()%32;cout地址流序列：;coutendl;for(int i=0;i=0;i-)co

27、utyemianliui ;coutendl;void FIFO(int n) /FIFO算法，n是M的值 coutM=n时FIFO的页面置换详情;coutendl;int i;int j;int q=p;int e;int queye=0;int flag;int fifo32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(fifoi=yemianliuq)flag=1;for(j=0;jn&fifoj!=0;j+) coutfifoj; coutendl;break;if(flag=0)int m=n-1;int k=m;while(m-)fifok=fif

28、ok-1;k-;fifo0=yemianliue;for(j=0;jn&fifoj!=0;j+)coutfifoj;coutendl;queye+;coutM=n时FIFO的缺页率为：(1-(double)queye/p)*100% ;coutendl;coutendl;void LRU(int n)/LRU算法coutM=n时LRU的页面置换详情;coutendl;int i;int j;int q=p;int e;int queye=0;int flag;int flag1;int y;int lru32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(lru

29、i=yemianliuq)flag=1;flag1=i;break;if(flag=0)int m=n-1;int k=m;while(m-)lruk=lruk-1;k-;lru0=yemianliue;for(j=0;jn&lruj!=0;j+) coutlruj; coutendl;queye+;else if(flag=1) y=flag1;while(y-)lruflag1=lruflag1-1;flag1-;lru0=yemianliue;for(j=0;jn&lruj!=0;j+) coutlruj; coutendl;coutM=n时LRU的缺页率为：(1-(double)que

30、ye/p)*100%endlendl;void ymzh()chushihua();for(int i=3;i5;i+)FIFO(i);LRU(i); yemianzhihuan();void yemianzhihuan()int a;cout-欢迎使用页面置换模拟实验系统-endl;cout-tt1.进入页面置换算法tt-endl;cout-tt2.返回上一级tt-endl;cout-欢迎使用页面置换模拟实验系统-endl;coutendla;switch(a)case 1:ymzh();break;case 2: menu();break;default:cout输入有误，请重新输入！en

31、dl;break;void changeaddr(struct Page p,int logaddr)/地址变换int j=logaddr/64;/对应的块号int k=logaddr%64;/对应的偏移量int flag=0;int addr;for(int i=0;i8;i+)if(pi.pno=j)/找到对应的页号if(pi.flag=1)/页面标志为1addr=o*64+k;cout物理地址为: addrendl;cout详细信息: t页面号：pi.pnot主存号:ot偏移量：kendl;flag=1;break;if(flag=0)cout该页不在主存,产生缺页中

32、断endl; void dizhizhuanhuan()int a;int ins;/指令逻辑地址struct Page p8;p0.pno=0;p0.flag=1;o=5;p0.modf=1;p0.addr=011;p1.pno=1;p1.flag=1;o=8;p1.modf=1;p1.addr=012;p2.pno=2;p2.flag=1;o=9;p2.modf=0;p2.addr=013;p3.pno=3;p3.flag=1;o=10;p3.modf=0;p3.addr=015;p4.pno=4;p4.flag=0;p4.addr=017;p5.p

33、no=5;p5.flag=0;p5.addr=025;p6.pno=6;p6.flag=0;p6.addr=212;p7.pno=7;p7.flag=0;p7.addr=213;cout-欢迎使用硬件地址变换过程模拟系统-endl;cout-tt1.输入指令tt-endl;cout-tt2.返回上一级tt-endl;cout-欢迎使用硬件地址变换过程模拟系统-endl;coutendla;while(a) cout页号 标记位 外存地址 主存号endl; for(int i=0;i8;i+) coutpi.pnotpi.flagtpi.addrt;if(pi.flag)o;c

34、outendl; switch(a)case 1:coutins;changeaddr(p,ins);break;case 2: menu();break;default:cout输入有误，请重新输入！endl;break;coutendla;void menu()int a;cout-欢迎使用分页系统模拟实验系统-endl;cout-tt1.进入硬件地址变换算法tt-endl;cout-tt2.进入页面置换算法tt-endl;cout-欢迎使用分页系统模拟实验系统-endl;coutendla;switch(a)case 1:dizhizhuanhuan();break;case 2: yemianzhihuan();break;default:cout输入有误，请重新输入！endl;break;void main() menu();6总 结在两周的课程设计中，我针对页面模拟的有关资料进行了调查，分析。针对题目的要求我把任务先分成两大模块：一是地址转换，二是页面置换。地址转换：输入一个逻辑地址，求出此地址所在的页面号码以及偏移量。查表看其