操作系统课程设计 FIFO OPT.docx
- 文档编号:18289510
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:16
- 大小:219.37KB
操作系统课程设计 FIFO OPT.docx
《操作系统课程设计 FIFO OPT.docx》由会员分享,可在线阅读,更多相关《操作系统课程设计 FIFO OPT.docx(16页珍藏版)》请在冰点文库上搜索。
操作系统课程设计FIFOOPT
课程设计(大作业)任务书
姓名:
院(系):
信息技术学院
专业:
计算机科学与技术学号:
任务起止日期:
2011年12月22日至12月26日
课程设计题目:
Linux环境下几种内存调度算法模拟
课程设计要求及任务描述:
设计内容:
1.理解FIFO、OPT等常见内存调度算法的原理。
2.模拟实现其中任意两种调度算法。
3.采用这两种调度算法,对同一访问序列进行命中率计算和输出,并比较结果。
注:
命中率=1-缺页率。
实验环境及工具:
1.实验环境:
Linux
2.文本编辑工具:
Vi
3.编译器:
GCC
工作计划及安排:
12月26日:
安排任务
12月27日:
算法分析
12月28日:
编译、调试程序,得出结果
12月29日:
分析结果,分析原因,写报告
指导教师签字
年月日
课程设计(大作业)成绩
学号:
姓名:
指导教师:
课程设计题目:
Linux环境下几种内存调度算法模拟
完成情况总结:
操作系统课程设计中我们理解FIFO、OPT等常见内存调度算法的原理。
模拟实现其中FIFO、OPT两种调度算法。
采用这两种调度算法,对同一访问序列进行命中率计算和输出,并比较结果。
并能熟悉运用各种命令,并理解各种命令的功能和执行方式以及结果,并能熟练运用。
指导并了解FIFO、OPT命令的各种功能和作用等等。
实验过程中我们遇到了很多困难,比如在实验过程当中怎样熟练使用实验环境:
Linux,文本编辑工具:
Vi,编译器:
GCC等等.
使用命令时不知道怎么操作,不知道怎么运行命令,但后来在老师的指导下,同学们的相互讨论交流中,还是解决了问题。
一开始不知道怎么使用配置环境等等,后来在不断学习中,终于解决了问题,完成试验。
通过这次试验我深刻认识到团队合作的重要性,同学之间相互讨论学习的重要性,老师画龙点睛的作用,以及我们自己动手能力的重要等等。
本次实验做得很成功,其中还要多感谢老师的细心指导及同学们的热心帮助。
学习是一个积累的过程,没有平时课内基础知识的学习是很难完成此次实验的,重点在于对这门课程理解的深度。
学习工具的使用亦是一个很重要的因素,包括以前学习的编程语言及Linux虚拟机的使用,由于没有勤加练习,在修改调试程序的过程中出现了很多问题,但在老师和同学的帮助下都一一解决了,感觉自己又查缺补漏了许多重要有用的东西。
感谢学院给我们组织这次课程设计的机会,在这个过程中真是受益匪浅。
指导教师评语:
成绩:
填表时间:
指导教师签名:
课程设计(大作业)报告
一、两种算法的原理分析
1.FIFO内存调度算法的原理
该算法总是淘汰最先进入内存的页面,即选择内存中主流时间最久的页面给予淘汰。
(1)在分配内存页面数(AP)大于进程页面数(PP)时,所有进程需要的页面(PP个页面)按提出请求的先后次序放入内存。
(2)在分配内存页面数(AP)小于进程页面数(PP)时,当然进程是按提出请求的次序将最先的AP个页面放入内存。
(3)这时有需要处理新的页面,则将内存中的AP个页面最先进入的调出(称为FIFO),然后放入新页面。
(4)在以后如果有新的页面需要调入,按3的规则进行。
2.OPT内存调度算法的原理
当发生缺页时,有些页面在内存中,其中有一页将很快被访问(也包含紧接着的下一条指令的那页),而其他页面则可能要到10、100或者1000条指令后才会被访问,每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。
标记最大的页应该被置换。
如果某页在八百万条指令内不会被使用,另一页在600万条指令内不会被使用,则置换前一个页面,从而把因需要调回这一页发生的缺页推到将来,越远越好。
二、两种算法的流程图表示
1.FIFO算法的流程图
2.OPT内存调度算法的流程图
三、两种算法的实现代码
FIFO内存调度算法的代码
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineINVALID-1
#definetotal_instruction320
#definetotal_vp32
#defineclear_period50
typedefstruct
{
intpn,pfn,counter,time;
}pl_type;
pl_typepl[total_vp];
structpfc_struct{
intpn,pfn;
structpfc_struct*next;
};
typedefstructpfc_structpfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect,a[total_instruction];
intpage[total_instruction],offset[total_instruction];
intinitialize(int);
intFIFO(int);
intmain()
{
ints,i;
srand(10*getpid());
s=(float)319*rand()/32767/32767/2+1;
for(i=0;i { if(s<0||s>319){ printf("Wheni==%d,Error,s==%d\n",i,s); exit(0); } a[i]=s; a[i+1]=a[i]+1; a[i+2]=a[i]*rand()/32767/32767/2; a[i+3]=a[i+2]+1; s=(float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2; if((a[i+2]>318)||(s>319)) printf("a[%d+2],anumberwhichis: %dands==%d\n",i,a[i+2],s); } for(i=0;i { page[i]=a[i]/10; offset[i]=a[i]%10; } for(i=4;i<=32;i++) { printf("---%2dpageframes---\n",i); FIFO(i); } return0; } intinitialize(total_pf) inttotal_pf; { inti; diseffect=0; for(i=0;i { pl[i].pn=i; pl[i].pfn=INVALID; pl[i].counter=0; pl[i].time=-1; } for(i=0;i { pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; return0; } intFIFO(total_pf) inttotal_pf; { inti; pfc_type*p; initialize(total_pf); busypf_head=busypf_tail=NULL; for(i=0;i { if(pl[page[i]].pfn==INVALID) { diseffect+=1; if(freepf_head==NULL) { p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head; freepf_head->next=NULL; busypf_head=p; } p=freepf_head->next; freepf_head->next=NULL; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL) busypf_head=busypf_tail=freepf_head; else { busypf_tail->next=freepf_head;busypf_tail=freepf_head; } freepf_head=p; } } printf("FIFO: %6.4f\n",1-(float)diseffect/320); return0; } OPT内存调度算法的代码 #include #include #include #defineTRUE1 #defineFALSE0 #defineINVALID-1 #definetotal_instruction320 #definetotal_vp32 #defineclear_period50 typedefstruct { intpn,pfn,counter,time; }pl_type; pl_typepl[total_vp]; structpfc_struct{ intpn,pfn; structpfc_struct*next; }; typedefstructpfc_structpfc_type; pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail; intdiseffect,a[total_instruction]; intpage[total_instruction],offset[total_instruction]; intinitialize(int); intOPT(int); intmain() { ints,i; srand(10*getpid()); s=(float)319*rand()/32767/32767/2+1; for(i=0;i { if(s<0||s>319){ printf("Wheni==%d,Error,s==%d\n",i,s); exit(0); } a[i]=s; a[i+1]=a[i]+1; a[i+2]=a[i]*rand()/32767/32767/2; a[i+3]=a[i+2]+1; s=(float)(318-a[i+2])*rand()/32767/32767/2+a[i+2]+2; if((a[i+2]>318)||(s>319)) printf("a[%d+2],anumberwhichis: %dands==%d\n",i,a[i+2],s); } for(i=0;i { page[i]=a[i]/10; offset[i]=a[i]%10; } for(i=4;i<=32;i++) { printf("---%2dpageframes---\n",i); OPT(i); } return0; } intinitialize(total_pf) inttotal_pf; { inti; diseffect=0; for(i=0;i { pl[i].pn=i; pl[i].pfn=INVALID; pl[i].counter=0; pl[i].time=-1; } for(i=0;i { pfc[i].next=&pfc[i+1]; pfc[i].pfn=i; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; return0; } intOPT(total_pf) inttotal_pf; { inti,j,max,maxpage,d,dist[total_vp]; initialize(total_pf); for(i=0;i { if(pl[page[i]].pfn==INVALID) { diseffect++; if(freepf_head==NULL) { for(j=0;j if(pl[j].pfn! =INVALID)dist[j]=32767; elsedist[j]=0; d=1; for(j=i+1;j { if(pl[page[j]].pfn! =INVALID) dist[page[j]]=d; d++; } max=-1; for(j=0;j if(max { max=dist[j]; maxpage=j; } freepf_head=&pfc[pl[maxpage].pfn]; //freepf_head->next=NULL; pl[maxpage].pfn=INVALID; }pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf("OPT: %6.4f\n",1-(float)diseffect/320); return0; } 四、结果分析 1.分析设计结果是否达到预期目标 2.针对同一访问序列比较两种算法的命中率 先进先出算法,即FIFO算法(First-In First-Out algorithm)。 这种算法选择最先调入主存储器的页面作为被替换的页面。 它的优点是比较容易实现,能够利用主存储器中页面调度情况的历史信息,但是,没有反映程序的局部性。 因为最先调入主存的页面,很可能也是经常要使用的页面。 最优替换算法,即OPT算法(OPTimal replacement algorithm)。 上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的,它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。 显然,这种假设不总是正确的。 最好的算法应该是选择将来最久不被访问的页面作为被替换的页面,这种替换算法的命中率一定是最高的,它就是最优替换算法。 五、实验总结及心得体会 操作系统课程设计中我们理解FIFO、OPT等常见内存调度算法的原理。 模拟实现其中FIFO、OPT两种调度算法。 采用这两种调度算法,对同一访问序列进行命中率计算和输出,并比较结果。 并能熟悉运用各种命令,并理解各种命令的功能和执行方式以及结果,并能熟练运用。 指导并了解FIFO、OPT命令的各种功能和作用等等。 实验过程中我们遇到了很多困难,比如在实验过程当中怎样熟练使用实验环境: Linux,文本编辑工具: Vi,编译器: GCC等等. 使用命令时不知道怎么操作,不知道怎么运行命令,但后来在老师的指导下,同学们的相互讨论交流中,还是解决了问题。 一开始不知道怎么使用配置环境等等,后来在不断学习中,终于解决了问题,完成试验。 通过这次试验我深刻认识到团队合作的重要性,同学之间相互讨论学习的重要性,老师画龙点睛的作用,以及我们自己动手能力的重要等等。 本次实验做得很成功,其中还要多感谢老师的细心指导及同学们的热心帮助。 学习是一个积累的过程,没有平时课内基础知识的学习是很难完成此次实验的,重点在于对这门课程理解的深度。 学习工具的使用亦是一个很重要的因素,包括以前学习的编程语言及Linux虚拟机的使用,由于没有勤加练习,在修改调试程序的过程中出现了很多问题,但在老师和同学的帮助下都一一解决了,感觉自己又查缺补漏了许多重要有用的东西。 感谢学院给我们组织这次课程设计的机会,在这个过程中真是受益匪浅。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统课程设计 FIFO OPT 操作系统 课程设计