请求页式存储管理

1、软件学院操作系统实验报告专 业：软件工程班 级：RB软工互152学 号： 201560160226学生姓名：王泽华扌旨导教师：韩新超实验四：请求页式存储管理一. 实验目的深入理解请求页式存储管理的原理，重点认识其中的地址变换、缺页中断、 置换算法等实现思想。二. 实验属性该实验为综合性、设计性实验。三. 实验仪器设备及器材普通PC386以上微机四. 实验要求本实验要求4学时完成。本实验要求完成如下任务：(1) 建立相关的数据结构：存储块表、页表等；(2) 实现基本分页存储管理，如分配、回收、地址变换；(3) 在基本分页的基础上实现请求分页存储管理；(4) 给定一批作业/进程，选择一个分配或回收

2、模拟；(5) 将整个过程可视化显示出来。实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码 编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告(参见附录A)，并要求用正规的实验报告纸和封面装订整齐，按时上交。五. 实验提示1、本实验虽然不以前面实验为基础，但建议在其界面中继续增加请求页式 存储管理功能。2、 数据结构：内存分配表、页表空间(用数组实现)，修改PCB吉构增加页 表指针、页表长度。3、存储管理：编写内存分配、内存回收算法、页面置换算法。4、主界面设计：在界面上增加一个请求分页内存分配按钮、请求分页内存

3、 回收按钮、装入指定进程的指定页按钮。触发请求分页内存分配按钮，弹出作业大小输入框，输入后调用内存分配函 数，在内存分配表和页表中看到分配的存储块。 触发请求分页内存回收按钮，弹 出进程ID输入框，输入后调用内存回收函数，在内存分配表中看到回收后的状 态改变。5、功能测试：从显示出的内存分配表和页表，可查看操作的正确与否。六. 实验步骤(1)任务分析：1. 最佳页面置换算法（OPT：其所选择的被淘汰页面，将是以后永不使用的 或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证 获得最低的缺页率。2. 最近最久未使用（LRU算法：当需要置换一页时，选择在最近一段时间 里最久没

4、有使用过的页面予以置换。（2）程序设计：程序功能模块图如下:（进程的地址空间）。此外我们应该还要用2.这个实验是要求我们采用算法模拟分（1）在：所有线程都具有相同的地址空间 控制语句，控制线程的同步执行。页存储管理技术的FIFO和LRU算法。所以我们 应该先生成地址序列，有了地址序列，我们要找到它所在的虚页，然后通过查找实页，再判断下一步动作。假如 要访问的虚页不在内存中，不命中，我们要替换实页内容。根据FIFO算法，直（2）系统功能流程图:接替换最早进入内存中的那一页就可以了。 所以可以设立一个循环指针，记录那 个最早进入内存中的那页。而对于LRU算法，我们要替换是到现在为止最长时间 没被访

5、问的页，在这里我们可以用一个队列来表示内存。把最久没使用的页放在 队头，然后替换进去的页放在队尾就可以了。 假如要访问的虚页在内存中，明显 是命中。对于FIFO算法，不处理，而对于LRU算法，我们还要把他的权值置 0。(3)算法分析1.先进先出定义一个队列存放页面,面的位置，每次替换头指针指向的页面。2.最近最少使用定义一个二维数组，一维用来记录页面号，一维用 来记录该页面被使用的次数，每次替换最近最少使用的页面(3)程序结果：在运行界面选择某个算法，运行结果，如图 1,图2所示:图1凶艾二-口1孙昱疑锻也字班上卅缶!3*拓r宾三#起豐四”DjbU±|苔忍趣S&lMt the

6、 apithnee ic ：COOPTp>LNUyuur chuiuu is ：2R3lm>nr0t: the MM 1 整h血e即廿t ha pAtfD 2Chanfiie the page 3 k：haEg£： the page < MlAll!jllt I lw IltAblV Sftn 1 mFram thnnnrtnfiwtnflinri.Df* 11;fH>mi thr- h呼审臼“EHll«ildWtn* ta=cn dDe lac 匕from tbs：andaddneirftoGet itthe呂& 3Mum* itt

7、1;- e ii d uf*DclBCtfnit thesvndn.wtoCM«fld.Jf* 1-E« fcnndaddncuitsend.Get itA.C the pa驳臼 4it5 end of iueuB.Gi-L ita.t Lhe page 1和叶J. tI v l dl uf L|Utf .Gnt Itnt thfi肿沪1Nnue itto r nd nl' qiiifui5!,Dt； lac tfron the JiBddandaddr帕wto£屁«ind.llclcc-tI ram the hertd.andaddnewtot

8、 heendThfr 卩寸¥口 邮 L u! OFT0. Zb幅囲用(3)调试与测试：1. 第一道涉及线程的题编译时总是发生错误，原来编译这类程序在原有的编 译语言后要加上-pthread.2. 第二个分页算法我们在系统结构课已经做过这个实验，所以有了一定的了 解，加上一点修改就能够使用了。所以没太花功夫。七、实验总结通过实现请求页式存储管理的几种基本页面置换算法，了解了虚拟存储技术 的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页 系统的原理和实现过程的理解，也知道了几种算法的效率，也验证了 LRU算法的 命中率平均的比FIFO算法要高。通过本次实验，我收获了

9、很多。我了解到编写程序不是首要任务， 而是一种 实现手段。我们最重要的是如何做好需求分析和理清思路， 做出正确、简介的流 程设计，这样可以达到事半功倍的效果。八、附录/# in elude <win dows.h>/# in clude <iostream>#i nclude"stdio.h"#in clude<c oni o.h>#i nclude <malloc.h>#defi ne N 16#defi ne num 5 /*进程分配物理块数目*/页表映像*/int AN=1,2,3,4,5,6,7,8,5,2,3,2,7

10、,8,1,4; /*typedef struct page int address; /*页面地址 */struct page *n ext;page;struct page *head,*r un ,*rear;void jccreat() /*进程分配物理块*/ in t i=1;page *p,*q;head=(page *)malloc(sizeof(page); p=head;for(i=1;i<=n um;i+) q=(page *)malloc(sizeof(page);p_>n ext=q; q->address=O; q_>n ext=NULL; p=

11、q; rear=p; int search(i nt n)page *p;int i=0;p=head;while(p-> next)if(p->n ext->address=n)prin tf("Get it at the page %dn",i+1);run=p;return 1;p=p->n ext;i+;return 0;void cha ngeOPT(i nt n ,i nt positi on)int i;int total=0;int flag=1;int dista ncenu m;int MAX;int order=0;page *

12、p,*q;p=head->n ext;q=head->n ext;for(i=0;i< nu m;i+)dista ncei=100;i=0;while(p)if(p->address=O)flag=0;break;p=p->n ext;i+;if(!flag)p->address=n;prin tf("Cha nge the page %dn",i+1);elsewhile(q)for(i=positi on ;i<N;i+)if(q_>address=Ai)dista ncetotal=i-positi on;total+

13、;q=q_>n ext;MAX=dista nce0;for(i=0;i< nu m;i+)if(dista ncei>MAX)MAX=dista ncei;order=i;prin tf("Cha nge the page %dn ",order+1);i=0;while(p)if(i=order)p->address=n;i+;p=p->n ext;void cha ngeLRU(i nt n)int i=0;int flag=1;page *p,*delect;p=head->n ext;while(p)if(p->addre

14、ss=0)flag=0;p->address=n;prin tf("Cha nge the page %dn",i+1);break;p=p->n ext;i+;if(flag)delect=head->n ext;head->n ext=delect->n ext;prin tf("Delect from the head, and add new to the en d.n");delect->address=n;rear->n ext=delect;rear=delect;rear->n ext=NU

15、LL;float OPT()int i;in t lose=0;float losef;float perce nt;for(i=0;i<N;i+)if(search(Ai)=O)lose+;cha ngeOPT(Ai,i);losef=lose;perce nt=1-(losef/N);return perce nt;float LRU()int i;in t lose=0;float losef;float perce nt;page *p;for(i=0;i<N;i+)if(search(Ai)=O)lose+;cha ngeLRU(Ai);elsep=run->n e

16、xt;run->n ext=p->n ext;rear- >n ext=p;rear=p;rear- >n ext=NULL;prin tf("Move it to end of queue.' n");losef=lose;perce nt=1-(losef/N);retur n perce nt;main() /* 主函数部分*/float perce nt;int choice;prin tf("Select the arithmetic:n(1)OPT n(2)LRUnyour choice is:");scan f("%d", &choice);/*选择页面置换算法*/jccreat();/*创建进程*/if(choice=1)/*采用OPT算法置换*/per