请求页式存储管理.doc

. ;. 软软 件件 学学 院院 操作系统实验报告操作系统实验报告 专专 业：业： 软件工程软件工程 班班 级：级： RB 软工互软工互 152 学学 号：号： 201560160226 学生姓名：学生姓名： 王泽华王泽华 指导教师：指导教师： 韩新超韩新超 . ;. 实验四：实验四：请求页式存储管理 一实验目的一实验目的 深入理解请求页式存储管理的原理，重点认识其中的地址变换、缺页中断、 置换算法等实现思想。 二实验属性二实验属性 该实验为综合性、设计性实验。 三实验仪器设备及器材三实验仪器设备及器材 普通 PC386 以上微机 四实验要求四实验要求 本实验要求 4 学时完成。 本实验要求完成如下任务： （1） 建立相关的数据结构：存储块表、页表等； （2） 实现基本分页存储管理，如分配、回收、地址变换； （3） 在基本分页的基础上实现请求分页存储管理； （4） 给定一批作业/进程，选择一个分配或回收模拟； （5） 将整个过程可视化显示出来。 实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代 码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并 分析实验结果。实验后认真书写符合规范格式的实验报告（参见附录 A） ，并要 求用正规的实验报告纸和封面装订整齐，按时上交。 五、实验提示五、实验提示 1、本实验虽然不以前面实验为基础，但建议在其界面中继续增加请求页式 存储管理功能。 2、数据结构：内存分配表、页表空间（用数组实现） ，修改 PCB 结构增加 页表指针、页表长度。 3、存储管理：编写内存分配、内存回收算法、页面置换算法。 4、主界面设计：在界面上增加一个请求分页内存分配按钮、请求分页内存 回收按钮、装入指定进程的指定页按钮。 触发请求分页内存分配按钮，弹出作业大小输入框，输入后调用内存分配 函数，在内存分配表和页表中看到分配的存储块。触发请求分页内存回收按钮， 弹出进程 ID 输入框，输入后调用内存回收函数，在内存分配表中看到回收后的 状态改变。 5、功能测试：从显示出的内存分配表和页表，可查看操作的正确与否。 六、实验步骤六、实验步骤 （1）任务分析： . ;. 1.最佳页面置换算法（OPT）：其所选择的被淘汰页面，将是以后永不使用 的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可 保证获得最低的缺页率。 2.最近最久未使用（LRU）算法：当需要置换一页时，选择在最近一段时间 里最久没有使用过的页面予以置换。 （2）程序设计： 程序功能模块图如下： （1）在同一进程中的各个线程，都可以共享该进程所拥有的资源，这表现 在：所有线程都具有相同的地址空间（进程的地址空间） 。此外我们应该还要用 控制语句，控制线程的同步执行。 2. 这个实验是要求我们采用算法模拟分页存 储管理技术的 FIFO 和 LRU 算法。所以我们 应该先生成地址序列，有了地址 序列，我们要找到它所在的虚页，然后通过查找实页，再判断下一步动作。假 如要访问的虚页不在内存中，不命中，我们要替换实页内容。根据 FIFO 算法， 直接替换最早进入内存中的那一页就可以了。所以可以设立一个循环指针，记 录那个最早进入内存中的那页。而对于 LRU 算法，我们要替换是到现在为止最 长时间没被访问的页，在这里我们可以用一个队列来表示内存。把最久没使用 的页放在队头，然后替换进去的页放在队尾就可以了。假如要访问的虚页在内 存中，明显是命中。对于 FIFO 算法，不处理，而对于 LRU 算法，我们还要把 他的权值置 0。 （2）系统功能流程图： N N Y Y 请求分页式储存 管理 最近 最久 未使 用算 法 先 进 先 出 算 法 开始 还有指令？ 开始 还有指令？ . ;. Y Y N N （3）算法分析 1.先进先出 定义一个队列存放页面，头指针记录最先进入队列的页面的位 置，每次替换头指针指向的页面。 2.最近最少使用 定义一个二维数组，一维用来记录页面号，一维用来记录 该页面被使用的次数，每次替换最近最少使用的页面 （3）程序结果：在运行界面选择某个算法，运行结果，如图 1，图 2 所示： 图 1 新页进入计算过程数组第 一 位，其余为一次下移 找到了吗？ 计算页号 计算命中率 结束 计算页号 找到了吗？ 比较现有页面计数项的大 小，新页面替换最大项页 面 计算命中率 结束 . ;. 图 2 （3） 调试与测试： 1.第一道涉及线程的题编译时总是发生错误，原来编译这类程序在原有的编 译语言后要加上-pthread. 2.第二个分页算法我们在系统结构课已经做过这个实验，所以有了一定的了 解，加上一点修改就能够使用了。所以没太花功夫。 七、实验总结七、实验总结 通过实现请求页式存储管理的几种基本页面置换算法，了解了虚拟存储技 术的特点。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求 调页系统的原理和实现过程的理解，也知道了几种算法的效率，也验证了 LRU 算法的命中率平均的比 FIFO 算法要高。 通过本次实验，我收获了很多。我了解到编写程序不是首要任务，而是一 种实现手段。我们最重要的是如何做好需求分析和理清思路，做出正确、简介 的流程设计，这样可以达到事半功倍的效果。 八、附录八、附录 /# include /# include #includestdio.h #include #include #define N 16 #define num 5 /*进程分配物理块数目*/ int AN=1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4; /*页表映像*/ . ;. typedef struct page int address; /*页面地址*/ struct page *next; page; struct page *head,*run,*rear; void jccreat() /*进程分配物理块*/ int i=1; page *p,*q; head=(page *)malloc(sizeof(page); p=head; for(i=1;inext=q; q-address=0; q-next=NULL; p=q; rear=p;int search(int n) page *p; int i=0; p=head; while(p-next) if(p-next-address=n) printf(Get it at the page %dn,i+1); run=p; return 1; p=p-next; i+; return 0; void changeOPT(int n,int position) int i; int total=0; int flag=1; int distancenum; . ;. int MAX; int order=0; page *p,*q; p=head-next; q=head-next; for(i=0;iaddress=0) flag=0; break; p=p-next; i+; if(!flag) p-address=n; printf(Change the page %dn,i+1); else while(q) for(i=position;iaddress=Ai) distancetotal=i-position; total+; q=q-next; MAX=distance0; for(i=0;iMAX) MAX=distancei; order=i; printf(Change the page %dn,order+1); i=0; while(p) if(i=order) p-address=n; i+; p=p-next; void changeLRU(int n) int i=0; int flag=1; page *p,*delect; p=head-next; while(p) if(p-address=0) flag=0; p-address=n; printf(Change the page %dn,i+1); break; p=p-next; i+; if(flag) . ;. delect=head-next; head-next=delect-next; printf(Delect from the head, and add new to the end.n); delect-address=n; rear-next=delect; rear=delect; rear-next=NULL; float OPT() int i; int lose=0; float losef; float percent; for(i=0;inext=p-next; rear-next=p; rear=p; rear-next=NULL; printf(Move it to end of queue.n); losef=lose; percent=1-(losef/N); return percent; main() /*主函数部分*/ float percent; int choice; printf(Select the arithmetic:n(1)OPTn(2)LRUnyour choice is:); scanf(%d,/*选择页面置换算法*/ jccreat(); /*创建进程*/ if(choice=1) /*采用 OPT 算法置换*/ percent=OPT(); /*计算 OPT 时