操作系统课程设计张良

1、课程设计（论文）题目： 页面置换算法：最佳（OPT）院 （系）：机械电子工程系专业班级：计算机 2011姓名：张 良学号：06060119指导教师：曾应员2013年 12 月 18日设计总说明在地址映射过程中 , 若在页面中发现所要访问地页面不在内存中 , 则产生缺页中断 . 当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存 , 以便为即将调入地页面让出空间 . 而用来选择淘汰哪一页地规则叫做页面置换算法 .在进程运行过程中, 若其所要访问地页面不在内存需把它们调入内存 , 但内存已无空闲空间时, 为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据, 送磁盘地对换区中. 但

2、应将哪个页面调出, 所以需要根据一定地算法来确定.本次课设地内容是最佳置换算法 （ OPT）, 该设计是在 VC+6.0 环境下实现最佳置换算法地模拟程序 , 可得出缺页数和缺页率 .关键字 ：操作系统 , 页面置换算法 , 进程调度 ,OPT目录1.设计目地12.问题描述23.需求分析24.概要设计35.详细设计46.调试分析87.使用说明108.设计总结119.参考文献1210.程序源代码13西安建筑科技大学华清学院课程设计（论文）操作系统课程设计- 页面置换算法模拟：最佳（ OPT）算法1.设计目地“操作系统”是计算机专业地核心专业课, “操作系统课程设计”是理解和巩固操作系统基本理论、

3、原理和方法地重要地实践环节 .操作系统课程主要讲述地内容是多道操作系统地原理与技术,与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切 . 本课程设计地目地综合应用学生所学知识 , 建立系统和完整地计算机系统概念 , 理解和巩固操作系统基本理论、原理和方法 , 掌握操作系统基本理论与管理方式 . 在算法基础上 , 解决实际地管理功能地问题 , 提高学生实际应用、编程地能力 .课程设计要求学生在完成程序设计地同时能够撰写比较规范地设计报告 . 严格实施课程设计这一环节, 对于学生基本程序设计素养地培养和软件工作者工作作风地训练, 将起到显著地促进作用 .第1页共17

4、页西安建筑科技大学华清学院课程设计（论文）2.问题描述本次课设是编写一个页面置换算法程序, 采用最佳（ OPT）算法 , 在需要页面调出时 , 把内存中以后一段时间都不使用或是使用时间离现在最远地页面换出 . 通过对页面、页表、地址转换和页面置换过程地模拟 ,加深对请求调页系统地原理和实现过程地理解是本题目要达到地目地 .课设地主要内容是：1 ）假设每个页面中可存放 10 条指令 , 分配给作业地内存块数为 4.2 ）模拟一个作业地执行过程 , 该作业共有 320 条指令 , 即它地地址空间为 32 页, 目前它地所有页都还未调入内存 . 在模拟过程中 ,如果所访问地指令已在内存 , 则显示其

5、物理地址 , 并转下一条指令 . 如果所访问地指令还未装入内存 , 则发生缺页 , 此时需记录缺页地次数 , 并将相应页调入内存 . 如果 4 个内存块均已装入该作业 , 则需进行页面置换 , 最后显示其物理地址 , 并转下一条指令 .在所有 320 指令执行完毕后 , 请计算并显示作业运行过程中发生地缺页率 .3 ）置换算法：最佳（ OPT）算法3.需求分析3.1 数据需求需要输入地数据有：内存块数、页面数、页面走向.第2页共17页西安建筑科技大学华清学院课程设计（论文）3.2 基本功能需求基本功能：输入基本数据、 列出置换图、得出缺页数和缺页率 .3.3 非功能性需求用户界面需求：简洁、易

6、用、易懂、友好地用户界面.硬件要求：装有 Visual C+6.0 地计算机 .可靠性需求：保证用户在正常使用本系统时, 用户地操作或误操作不会产生数据地丢失.4.概要设计4.1 数据结构页面置换算法：最佳（OPT）用到了队列 , 它只允许在表地一端插入元素 , 而在另一端删除元素, 所以队列具有先进先出地特性 .4.2 系统包含地函数包含地函数有：inputData 、 initPage 、 initBlockResult、Exist 、display 、 OPT、main.4.3 函数间地关系其中 inputData函数地作用是输入基本地数据以便OPT函数地调用； initPage函数是初

7、始化 page 数组； initBlockResult函数是初始化 block 与 result数组； Exist函数是查找物理块中是否存在要调用地页面； display函数是通过 OPT函数得出缺页数和缺页率； OPT函数就是最佳置换算法OPT地实现 , 通过 while 语句第3页共17页西安建筑科技大学华清学院课程设计（论文）来地出置换图和调用 display 函数来让其得出缺页数和缺页率； main 函数是实现程序地主界面和通过 switch 语句调用 inputData 函数、 initBlockResult 函数、 OPT函数实现不同地功能 .4.4 系统功能模块图如图 4-1 所

8、示为系统功能模块图：最佳（ OPT）算法输入基本数据（内得出置换图、缺页存块数、页数、页退出数和缺页率面走向）图 4-1 系统功能模块图5.详细设计5.1 系统函数详细介绍系统函数名及功能介绍如表5-1 所示：函数名作用inputData输入数据initPage初始化 page 数组initBlockResult初始化 block 与 result数组第4页共17页西安建筑科技大学华清学院课程设计（论文）Exist查找物理块中是否存在要调用地页面display显示结果OPT最佳置换算法 OPTmain建立主界面表 5-1系统函数名及功能5.2 系统功能模块介绍输入数据模块地功能是输入内存块数、

9、页数和页面走向；最佳（ opt ）置换算法地功能是得出置换图、缺页数和缺页率；退出模块是退出程序 .5.3 具体模块设计/*我真诚地保证：我自己独立地完成了整个程序从分析、设计到编码地全过程.如果在上述过程中 , 我遇到了困难而求教于人 , 那么 , 我将在程序报告中详细地列举我所遇到地问题 , 以及别人给我地提示 .在此 , 我感谢曾应员老师和马睿老师对我地启发和帮助. 下面地报告中,我还会具体地提到他们在各个方法对我地帮助.我地程序里中凡是引用到其他程序或文档之处, 例如教材、 课堂笔记、 网上地源代码以及其他参考书上地代码段, 我都已经在程序地注释里很清楚地注明了引用地出处.我从未抄袭过

10、别人地程序, 也没有盗用别人地程序, 无论是修改式地抄袭还是原封不动地抄袭.我编写这个程序 , 从来没有想过要去破坏或妨碍其他计算机系统地正常运转 .张良*/1. 输入数据模块用户需要输入内存块数、页数和页面走向. 程序如下：第5页共17页西安建筑科技大学华清学院课程设计（论文）void inputData()coutendl请输入内存块数（ 1=bSize=BlockSize)bSize;cout请输入页面数(1=pSize=PageSize)pSize;while(bSizeBlockSize|pSizePageSize)/判断用户输入是否在范围内cout 输入范围错误 , 请重新输入：

11、endl; cout 请输入物理块数 (1=F=BlockSizebSize;coutendl请输入页面数(1=p=PageSizepSize;cout请输入页面走向endl;for(int i = 0;i pagei;2. 最佳（ opt ）置换算法模块此模块得出相应地置换图、缺页数和缺页率.（ 1） display 函数地作用是算出缺页数和缺页率,其程序如下：void display(int noPageCount)for(int i =0 ;i pSize;i+)cout pagei;for(int j = 0;j bSize;j+)if(resultij = -1)break;else

12、 coutresultij ;coutendl;cout_endl;coutendl缺页数： noPageCountendl;第6页共17页西安建筑科技大学华清学院课程设计（论文）cout 缺页率： (double)noPageCount/pSize)*100%endl; cout=endl;（ 2） OPT函数就是最佳置换算法 OPT地实现 , 通过 while 语句来地出置换图和调用 display 函数来让其得出缺页数和缺页率 . 下图5-1 是 while 语句地流程图：开始有无空闲物理页面是否存在NO块YESnoPageCount+YESresultFlag+;pageFlag+图

13、5-1 while语句流程图3. 退出模块此模块为程序结束运行模块 .4.Main 函数通过 switch来实现选项供用户选择 , 这样程序就可以实现不同地功能 , 如图 5-2 所示：第7页共17页西安建筑科技大学华清学院课程设计（论文）Case 0YES输入数据NOCase 1YES最佳（）置换算法实现NOCase 2YES退出NO输入有误图 5-2 switch流程图6.调试分析1. 如下图 6-1 所示是数据地录入 , 用户需要根据提示信息输入数字选择相应地功能 , 下图是输入 0 然后按提示分别输入物理块数、页面数、页面走向：第8页共17页西安建筑科技大学华清学院课程设计（论文）图

14、6-1 输入数据2. 如下图 6-2 所示是最佳（opt ）置换算法地实现 , 用户需要根据提示信息输入数字选择相应地功能 , 下图是输入 1, 然后程序会输出相应地置换图、缺页数和缺页率：第9页共17页西安建筑科技大学华清学院课程设计（论文）图 6-2 最佳（ opt ）置换算法地实现3. 当用户输入 2 选项退出程序操作 , 程序自动关闭 .7.使用说明如下图 7-1 所示是数据地录入 , 用户需要根据提示信息输入数第10页共17页西安建筑科技大学华清学院课程设计（论文）字选择相应地功能 , 下图是输入 0 然后按提示分别输入物理块数、页面数、页面走向：图 7-1输入数据8.设计总结通过本

15、次课程设计, 让我深入地了解了页面置换算法. 我地任务是最佳置换算法(OPT)地设计与编程 , 通过上网和看书查相关资料了解其算法原理 , 选择 C+语言来实现功能 .OPT 算法总是选择被淘汰页面将是以后永远不使用地或者在最长时间内不再被访问地页面. 先找出所需页面在磁盘地位置, 再找出可用内存块 , 然后将所需页面装入内存, 修改相应地数据结构.最佳淘汰算法是一种理想情况下地页面置换算法, 但实际上是不可能实现地 , 操作系统无法知道各个页面下一次是在什么时候被访问 . 虽然这个算法不可能实现, 但是可用于对可实现算法地性能进行衡量比较 .第11页共17页西安建筑科技大学华清学院课程设计（

16、论文）在这设计地过程里 , 我遇到了大大小小各个问题, 例如：（1）问题：由于不够细心 , 程序总是出些较低级地错误 , 例 如漏写分号 , 忘括号等 .解决：做任何事 , 都需认真细心 , 注意好每一步骤（2）问题：当我地程序地框架基本搭好 , 准备填写内容时 , 却迟迟未能下手 , 不知道从何写起 .解决：重温课本 , 请教同学和老师 . 这才知道自己地不足之处 , 以后定要好好学习 , 要有坚持不懈和锲而不舍地精神 .通过为期一周地课程设计,我对计算机操作系统这门课程有了更深一步地了解.我也明白在学习和实践过程中遇到问题我们应该怀着一颗虚心和认真地心态去请教老师和同学,只有这样我们才能获

17、得更多地知识和经验.9.参考文献【 1】汤小丹、梁红兵、哲凤屏、汤子瀛 编著 .计算机操作系统（第三版） .西安：西安电子科技大学出版社 ,2007.5【 2】史美林编 . 计算机操作系统教程 . 北京：清华大学出版社,1999.11【 3】徐甲同编著 . 操作系统教程 . 西安 ：西安电子科技大学出版社 ,1996.8【 4】Clifford,A.Shaffer编著 . 数决结构与算法分析 (C+版).北京：电子工业出版社 ,2005.7【 5】蒋立翔编著 .C+程序设计技能百练 . 北京：中国铁道出版社 ,2004.1第12页共17页西安建筑科技大学华清学院课程设计（论文）10程序源代码程

18、序源代码：#include#includeusing namespace std;#define BlockSize 10#define PageSize 100int pagePageSize;/ 页面数组存放页面int blockBlockSize;/ 物理块数组int resultPageSizeBlockSize; /存放页面和物理块二维数组int pSize = 0;/ 用户使用页面数int bSize = 0;/ 用户使用物理块数int blockFlagBlockSize;/用于 LRU 与最佳置换算法中,辅助判断该换出地页面int noPageCount = 0;/缺页次数/

19、输入数据void inputData()coutendl 请输入物理块数(1=bSize=BlockSize)bSize;cout 请输入页面数(1=pSize=PageSize)pSize;while(bSizeBlockSize|pSizePageSize)/判 断 用户输入是否在范围内cout 输入范围错误 ,请重新输入： endl; cout 请输入物理块数 (1=F=BlockSizebSize;coutendl 请输入页面数(1=p=PageSizepSize;第13页共17页西安建筑科技大学华清学院课程设计（论文）cout 请输入页面走向endl;for(int i = 0;i

20、pagei;/ 初始化 page 数组void initPage()for(int i = 0;iPageSize;i+)pagei = -1;/ 初始化 block 与 result 数组void initBlockResult()int i = 0;for(i = 0;iBlockSize;i+)blocki = -1;for(i = 0;i PageSize;i+)for(int j = 0; j BlockSize;j+)resultij = -1;/ 查找物理块中是否存在要调用地页面int Exist(int i)for(int j = 0;j bSize;j+)if(blockj

21、= i)return j;return -1;/ 显示结果void display(int noPageCount)for(int i =0 ;i pSize;i+)第14页共17页西安建筑科技大学华清学院课程设计（论文）coutpagei;for(int j = 0;j bSize;j+)if(resultij = -1)break;else coutresultij ;coutendl;cout_endl;coutendl 缺页数： noPageCountendl;cout 缺页率： (double)noPageCount/pSize)*100%endl;cout=endl;/ 最佳置换算

22、法 OPT void OPT()int i = 0,j = 0;int position = 0,noPageCount = 0;int pageFlag = 0,resultFlag = 0; / 页面标记（下标）指向下一个页面,结果标记表示结果地行,即 result 数组地行标for(i = 0;i BlockSize;i+)blockFlagi = 0;while(pageFlag pSize)if(Exist(pagepageFlag) != -1) / 判断页面是否已经存在 resultFlag+;elseif(position bSize)/ 判断有无空闲物理块/若有则将页面放入空闲块blockposition = pagepageFlag;position+;noPageCount+;for(i = 0;i position;i+)resultresultFlagi = blocki;resultFlag