《操作系统原理课程设计-页面置换算法模拟程序.doc》由会员分享，可在线阅读，更多相关《操作系统原理课程设计-页面置换算法模拟程序.doc（22页珍藏版）》请在三一文库上搜索。
1、数学与计算机学院 课程设计说明书 课 程 名 称: 操作系统原理-课程设计 课 程 代 码: 题 目: 页面置换算法模拟程序 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2010 年 月 日 完 成 时 间: 2011 年 月 日 课程设计成绩： 学习态度及平 时成绩（30） 技术水平与实际 能力（20） 创新（5）说明书撰写质量（45） 总 分 （100） 指导教师签名： 年 月 日 目 录 1 1 引引 言言1 页面置换算法模拟程序 1.1 问题的提出 .1 1.2 国内外研究的现状1 1.3 任务与分析2 2 需求分析需求分析.2 3 开发平台开发平台.2 3.1 开
2、发工具 .2 3.1 开发语言 .2 4 概要设计概要设计.3 4.1 总体设计框图 .3 5 5 详细设计详细设计.4 5.1 代码分析结果6 5.11 数据结构 6 5.12 FIFO 具体函数及设计实现 .6 5.13LRU 具体函数及设计实现.9 5.14 调用关系图.14 6 6 测试测试.14 6.1 进入界面及产生页面走向14 6.2FIFO 算法及查看结果 .15 6.3LRU 算法及查看结果16 6.4 继续进入主界面及产生页面走向16 6.5 调度算法及结果17 7 7 总结与体会总结与体会18 参考文献参考文献19 页面置换算法模拟程序 摘摘 要要 在地址映射过程中，若在
3、页面中发现所要访问的页面不再内存中，则产生缺页中断。 当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的 页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无 空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送 磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。 常用的算法有先进先出置换算法（FIFO）, 最近最久未使用置换算法（LRU）和最佳置 换算法（OPT），该设计是在 VC+6.0 环境下分别用 LRU 和 FIFO 来实现页面置换算法 的
4、模拟程序，并测试。 关键词：关键词：操作系统; 页面置换算法模拟; 进程调度; FIFO; LRU -1- 页面置换算法模拟程序 1 引引 言言 1.1 问题的提出问题的提出 随着硬件技术的发展，各式各样的大容量存储设备相继出现，一台计 算机上可能存在多种外存储设备。不同存储设备有着不同的读写速度，同 一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度 的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性 能会有很大的提高。 在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存， 但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中 调出一页程序或
5、数据，送磁盘的对换区中。但应将哪个页面调出，所以需 要根据一定的算法来确定。如果能够很好的使用页面置换将大大节省内存 的额外开销。 1.2 国内外研究的现状国内外研究的现状 1966 年 Belady 在理论上提出最优页面置换算法（OPT）,此外还有 先进先出（FIFO） ，最少使用置换算法（LRU） 。不同存储设备有着不 同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在 多种具有不同读写速度的外存储设备的环境下，选择一种合适的页面 淘汰算法，对整个系统的性能会有很大的提高。 -2- 页面置换算法模拟程序 1.3 任务与分析任务与分析 本课题主要的目的是编制页面置换算法 FIFO
6、和 LRU 的模拟程序,并模 拟其在内存的分配过程。同时根据页面走向，分别采用 FIFO 和 LRU 算法 进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页 表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。 2需求分析需求分析 本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算 法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现 的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调 入的现象。该程序能按要求随机确定内存大小，随机产生页面数，进程数， 每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个 进程进行计算缺页数，
7、缺页率，被淘汰的序列等功能。 3开发平台开发平台 3.1 开发工具开发工具 VC+6.0 3.1 开发语言开发语言 VC+语言 -3- 页面置换算法模拟程序 4概要设计概要设计 4.1 总体设计框图总体设计框图 进入程 序 输入页面数 页面走向 随即产生用户输入 先 进 先 出 置 换 最 少 使 用 置 换 -4- 页面置换算法模拟程序 5 5 详细设计详细设计 开始 输入页面数 0 手动输入 1 随机产生 (0)FIFO (1)OPT 输入数据输入个数 输出 FIFO 结果 输出 OPT 结果 是否输入 Y/y 结束 输出另外一 种结果 是否继续 (N/n) -5- 页面置换算法模拟程序
8、图 5.1 详细设计框图 开始 初始化数据，确定 页面走向 判断页号是否等 于页面流号 算出内存中各个页号相 对于当前位置，并置换 了学校,也不免想到自己 明年将要离开的情景,心 里也感觉到一种凄凉. 原来一直都想着要 考研的,经过几个月的考 虑,发现自己或许不适合 考研吧, 复习总是那么得不尽人 意。离开了老师的约束 和同学的相互促进，我 发现自己学 习总是静不下心来，效 率一直不高。而且我觉 得自己对本专业不是很 感兴趣，害 怕自己又浪费掉三年， 而学不到什么东西。一 直就这样犹豫着，从三 月到六月， 现在终于决定放弃我的 考研路。考研或许真的 就不适合我吧！ 决定不考研之后，我 就面临着
9、工作的问题， 可是我拿什么来面对工 作呢？回想 起这几年，感觉自己真 的学到的太少了。今天 和一个老同学聊天，他 也这么说， 感觉自己在大学又白混 了三年。暑假快要到了， 我想在学校学点东西， 可是具体 的又不知道学什么。又 怕武汉的天气太热，学 不了什么。不过怎么来 说，我一定 要为工作好好准备一下。 的距离 淘汰距离最大的那个页 号，并进行换页 距离是否相等 比较出现的次数 淘汰出现次数少的 页号，并进行换页 输出淘汰的页号 模块结束 否 是 是 否 -6- 页面置换算法模拟程序 图 5.2 为置换方法的流程图 5.1 代码分析结果代码分析结果 5.115.11 数据结构数据结构 int
10、m, int need,int n, result1020,int state,int count1; 5.125.12 FIFOFIFO 具体函数及设计实现具体函数及设计实现 FIFO 流程图流程图 有 不在 在 开始 页面大小 m， 页面走向放在 head 结果表 result 和状态表 count 赋值为-1 Result 是否为空 装入页表中，缺 页次数 count+ 替换出先进入结 果表中的页面 是否在页 表内 步数 page+ 统计缺页数和缺页率 输出过程及结果 结束 -7- 页面置换算法模拟程序 FIFOFIFO函数实现函数实现 void FIFO(int m, int need
11、,int n) /m分配物理页面大小，n需要页面数组的最大值 int p=0; /当前请求的页面 int del=0; /步数 int count120; double count=0;/缺页数 double que=0;/缺页率 int result1020;/结果表 for(int i =0;i=p) int k=needp; if(p0) for(int i=0;i min) k = j; min = statej; -11- 页面置换算法模拟程序 hsivek = result0i; statek = -1; counti = 1; num+; for(j = 1; j 9) cinf
12、lag; m=flag-0-1; flag= ; cout1) cinflag; choose =flag-0; flag= ; if(choose=0) cout9) if(flag=s) break; needn=flag-0; flag= ; n=n+1; flag= ; n=n-1; else coutn; -13- 页面置换算法模拟程序 n=n-1; for(int i=0;i1) cinflag; choose =flag-0; flag= ; if(choose=0) FIFO(m, need,n); else LRU(m, need,n); coutflag; if(flag=
13、Y|flag=y) system(“cls“); if(choose=0)LRU(m, need,n); else FIFO(m, need,n); else flag= ; coutflag; if(flag=N|flag=n) break; else system(“cls“);flag= ; return 0; -14- 页面置换算法模拟程序 5.145.14 调用关系图调用关系图 调用 调用 6 6 测试测试 6.1 进入界面及产生页面走向进入界面及产生页面走向 运行结果如下 图 6.1 进入管理界面 主方法模块 FIFO 模块 LRU 模块 -15- 页面置换算法模拟程序 图 6.2
14、 产生页面走向 6.2FIFO 算法及查看结果算法及查看结果 图 6.3 选择 FIFO 算法结果 -16- 页面置换算法模拟程序 6.3LRU 算法及查看结果算法及查看结果 图 6.4 选择 LRU 结果 6.4 继续进入主界面及产生页面走向继续进入主界面及产生页面走向 图 6.5 按 y 继续回到主界面设置页面为 4 -17- 页面置换算法模拟程序 6.5 调度算法及结果调度算法及结果 图 6.6 选择 LRU 算法结果 图 6.7 选择 FIFO 算法结果 -18- 页面置换算法模拟程序 7 总结与体会 这个程序的主要思想就是要实现换页、怎么样输出淘汰的序列、计算缺页次数和缺 页率。在程
15、序中主要就是将在访问串中将来再也不出现的或是在离当前最远的位置上 出现的页淘汰掉。当距离相等的时候就比较使用的次数，淘汰使用次数较少的那页。 该过程共有两个函数及实现 FIFO 的函数和实现 LRU 的函数，当主函数调用任意其中函 数时来实现其算法。 通过这次课程设计的实践，我能够熟练的掌握一些关于内存分配管理的一些算法。 而在实现 FIFO 算法后，由于没能掌握 LRU 算法的过程导致实现时花了很多时间。在调 试的过程中也出现的大多是关于内存分配和数组地址越界的问题，比如关于循环时各 个数的递增，还有就是显示给个数组的内容等问题。就因为这些问题，多次造成了淘 汰序列出错。在以后的实验中我会注意的。 -19- 页面置换算法模拟程序 参考文献参考文献 1 李善平等. Linux 内核 2.4 版源代码分析大全. 北京：机械工业出版社，2002.1 2 陈莉君. 深入分析 Linux 内核源代码. 北京：人民邮电出版社，2002.8 3 陈向群 编著.操作系统教程.北京：北京大学出版社，2007.01 4 罗宇 等编著.操作系统课程设计.北京：机械工业出版社，2005.9 5 Gary Nutt.Linux 操作系统内核实习. 北京：机械工业出版社，2002.1