操作系统设计opt.docx
- 文档编号:15976037
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:14
- 大小:202.75KB
操作系统设计opt.docx
《操作系统设计opt.docx》由会员分享,可在线阅读,更多相关《操作系统设计opt.docx(14页珍藏版)》请在冰点文库上搜索。
操作系统设计opt
课程设计
课程设计名称:
《操作系统原理》课程设计
专业班级:
学生姓名:
学号:
指导教师:
课程设计时间:
2012年12月24日-28日
计算机科学专业课程设计任务书
学生姓名
专业班级
计科1005
学号
201046831108
题目
请求调页存储管理方式的模拟3
课题性质
其它
课题来源
自拟课题
指导教师
同组姓名
主要内容
1)假设每个页面中可存放10条指令,分配给作业的内存块数为4。
2)用C语言模拟一个作业的执行过程,该作业共有320条指令,即它的地址空间为32页,目前它的所有页都还未调入内存。
在模拟过程中,如果所访问的指令已在内存,则显示其物理地址,并转下一条指令。
如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。
如果4个内存块均已装入该作业,则需进行页面置换,最后显示其物理地址,并转下一条指令。
在所有320指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。
3)置换算法:
最佳置换(OPT)算法。
任务要求
通过对页面、页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。
参考文献
任满杰等《操作系统原理实用教程》电子工业出版社2006
汤子瀛《计算机操作系统》(修订版)西安电子科技大学出版社2001
张尧学史美林《计算机操作系统教程》实验指导清华大学出版社2000
罗宇等《操作系统课程设计》机械工业出版社2005
审查意见
指导教师签字:
教研室主任签字:
年月日
说明:
本表由指导教师填写,由教研室主任审核后下达给选题学生,装订在设计(论文)首页
1需求分析
1.1设计目的
通过对页面、页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。
1.2 设计内容
1)假设每个页面中可存放10条指令,分配给作业的内存块数为4。
2)用C语言模拟一个作业的执行过程,该作业共有320条指令,即它的地址空间为32页,目前它的所有页都还未调入内存。
在模拟过程中,如果所访问的指令已在内存,则显示其物理地址,并转下一条指令。
如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。
如果4个内存块均已装入该作业,则需进行页面置换,最后显示其物理地址,并转下一条指令。
在所有320指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。
3)置换算法:
最佳置换(OPT)算法。
1.3设计要求步骤
(1)通过随机数产生一个指令序列,共320条指令。
指令的地址按下述原则生成:
①50%的指令是顺序执行的;
②25%的指令是均匀分布在前地址部分;
③25%的指令是均匀分布在后地址部分;
具体的实施方法是:
①在[0,319]的指令地址之间随机选取一起点m;
②顺序执行一条指令,即执行地址为m+1的指令;
③在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m′;
④顺序执行一条指令,其地址为m′+1的指令;
⑤在后地址[m′+2,319]中随机选取一条指令并执行;
⑥重复上述步骤①~⑤,直到执行320次指令。
(2)将指令序列变换为页地址流
①设页面大小为1K;
②用户内存容量为4页到32页;
③用户虚存容里为32K。
在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
第0条~第9条指令为第0页(对应虚存地址为[0,9]);
第10条~第19条指令为第1页(对应虚存地址为[10,19]);
……
……
第310条~第319条指令为第31页(对应虚存地址为[310,319])。
按以上方式,用户指令可组成32页。
(3)计算最佳置换(OPT)算法在不同内存容量下的命中率。
其中,命中率=1-页面失效次数/页地址流长度
2概要设计
intpc;//程序计数器,用来记录指令的序号
intn;//缺页计数器,用来记录缺页的次数
staticinttemp[320];//用来存储320条随机数
typedefstructBLOCK//声明一种新类型--物理块类型
{
intpagenum;//存储页号
intaccessed;//访问字段,其值表示多久未被访问
}BLOCK;
BLOCKblock[Bsize];//定义一大小为4的物理块数组
voidinit();//程序初始化函数
intfindExist(intcurpage);//查找物理块中是否有该页面
intfindSpace();//查找是否有空闲物理块
intfindReplace();//查找应予置换的页面
voidprint();//缺一次页就打印四个物理块中的页号一次
voidrandom();//产生320条随机数,显示并存储到temp[320]
voidOPT();//OPT算法
3运行环境
软件:
MicrosoftVisualC++6.0
硬件:
CPU在512M内存以上的计算机
4开发工具和编程语言
开发工具:
MicrosoftVisualC++6.0
编程语言:
C++
5详细设计
5.1主函数:
voidmain()
{
//初始化程序
init();
//按照要求随即产生指令执行顺序
cout<<"请输入第一条指令号[0-319]:
"< random(); //依次显示调用的页面 cout< for(inti=0;i<320;i++) {printf("%02d",temp[i]/10); if((i+1)%10==0)cout< } //最佳置换算法OPT cout< "< OPT(); //计算命中率 cout<<"缺页次数: "< cout<<"命中率: "<<100-(n/320.0)*100<<"%"< } init()函数是将程序进行初始化,也就是pagenum=-1、assessed=0、pc=n=0;使四个物理块为空,计数器都为零; voidrandom() {intflag=0; while(true){ cin>>pc; if(pc>=0&&pc<=319) break; else cout<<"请从新输入: "; } cout<<"按照要求产生的320个随机数: "< for(inti=0;i<320;i++) { temp[i]=pc; if(flag%2==0)pc=++pc%319; if(flag==1)pc=rand()%(pc+1); if(flag==3)pc=pc+1+(rand()%(320-(pc+1))); flag=++flag%4; printf("%03d",temp[i]); if((i+1)%10==0)cout< } } 此函数是按照要求产生指令执行的先后顺序并存储在全局变量数组中; 然后主函数利用此数组计算出每条指令所在的页面并打印显示在屏幕上; 然后就是执行opt算法执行指令了: voidOPT() { intexist,space,position; intcurpage=0; for(inti=0;i<320;i++) { pc=temp[i]; if(pc! =0) curpage=(pc-1)/10; exist=findExist(curpage); //当该页不在四个块中 if(exist==-1) { space=findSpace(); //当该物理块有空闲时,用在初始缺页判断 if(space! =-1) { block[space].pagenum=curpage; print();n++; } //当物理块没有空闲,进行opt页面置换算法 else { for(intk=0;k { for(intj=i;j<320;j++) { if(block[k].pagenum! =temp[j]/10) { block[k].accessed=1000;//将来不会用,设置为一个很大数 } else { block[k].accessed=j; break; } } } //判断accessed最大的并置换掉,并修改物理块页号值和打印物理地址 position=findReplace(); block[position].pagenum=curpage; print(); n++; } } } } 此算法就是先将执行的指令页号计算出来,findExist(页号)判断是否存在四个物理块中,若不存在,findSpace()判断是否有空闲物理块,若有,修改返回物理块的pagenum,并调用print()打印四个物理块的信息,缺页次数加1;若没有空闲物理块,进行opt算法进行置换,计算每一个物理块中该页在以后执行出现最近的一次位置并赋值给accessed,然后调用findReplace()找到四个物理块中accessed值最大的也就是在以后的执行中访问时间间隔时间最长的,将其页号修改为将执行的指令所在的页号吉pagenum,并打印四个物理块页号信息,缺页次数加1; 当指令执行完之后,最后在主函数中打印却也次数并计算命中率显示; 6调试分析 调试过程中,由于对一些具体的算法逻辑掌握不够牢固,,导致实验过程中出现过一写或大或小的问题,导致程序出错,经过多次修改,实验还是顺利完成了。 比如在实验中在计算随机数时,最后的算法是下面的: for(inti=0;i<320;i++) { temp[i]=pc; if(flag%2==0)pc=++pc%319; if(flag==1)pc=rand()%(pc+1); if(flag==3)pc=pc+1+(rand()%(320-(pc+1))); flag=++flag%4; printf("%03d",temp[i]); if((i+1)%10==0)cout< } 实际上在实验中我一般优先多重循环,即两个for计算要求的随机数,但后来经过思考,多重循环效率低,另外还要另定义一些变量等浪费了一定的资源,这在程序很大要求比较严格内存利用率高的时候这是很大障碍,因此,经过不断调式思考,终确定算法如上,优化了算法。 7测试结果 测试结果如下,随机数指令顺序运行之后截图如图1,相应页面调用顺序截图如图2,执行opt算法部分截图如图3,命中率计算截图如图4 图1 图2 图3 图4 分析: 开始执行指令页面的顺序: 11、11、04、04、22、22、12、12、24、24、13、13、29…首先将11调入物理块,并打印信息正确,后面已经有11在物理块中,不需要调入或者置换,后面将04、22、12调入物理块中,这时四个物理块已经没有空闲,打印信息也正确,后面执行指令的页号是24,四个物理块中不存在且没有空闲,进行opt置换算法,将四个物理块中之后最久访问的页面置换出来,即将04页面置换出并打印,显示正确,缺页次数119次,经计算,命中率为62.8%,经多次测试,该算法无误。 思考题: 如果增加分配给作业的内存块数,将会对作业运行过程中的缺页率产生什么影响? 答: 如果不是什么苛刻的作业,分配作业的内存块数越多,也就说明改作业在内存中的指令就越多,极限是所有指令都在内存块中,极限命中率是1,这也就是说,分配的内存块数越多,缺页率也就越低。 参考文献: 任满杰等《操作系统原理实用教程》电子工业出版社2006 汤子瀛《计算机操作系统》(修订版)西安电子科技大学出版社2001 张尧学史美林《计算机操作系统教程》实验指导清华大学出版社2000 罗宇等《操作系统课程设计》机械工业出版社2005 心得体会 在整个实验中独立思考,首先规划整体结构,一个一个函数的往里加,首先随即指令,显示页面队列,最后就是执行opt算法,在opt中也是这种思想,核心算法就是怎么置换,其余就是逻辑完善,这次试验,对于opt页面置换有了进一步的理解,熟练掌握了其核心思想,对操作系统部分核心功能有了新的认识,总体来说,这次试验收获蛮大的,对编程的规范性,算法的效率等等都有考虑,在这方面成熟了许多。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 设计 opt