操作系统课程设计内存调度算法模拟.doc

《操作系统课程设计内存调度算法模拟.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计内存调度算法模拟.doc（17页珍藏版）》请在三一办公上搜索。

1、课程设计（大作业）报告课程名称： 操作系统 设计题目： 内存调度算法模拟 院 系： 信息技术学院 班 级：x设 计 者： 学 号： x 指导教师： x 设计时间：x昆明学院昆明学院课程设计（大作业）任务书姓 名：x 院（系）：x专 业：x 学 号：x任务起止日期2016年 1 月 4 日至 2016 年 1 月 8 日课程设计题目： 内存调度算法模拟课程设计要求及任务描述：要求：（1）按指定时间及地点参加课程设计。（2）通过本次课程设计，能加深理解设计项目使用的相关原理。（3）根据项目内容完成课程设计。（4）在指定时间内提交设计结果及设计报告。任务：（1）选择其中两种算法的原理进行分析 FIF

2、O内存调度算法的原理 （其他任选一个算法）内存调度算法的原理（2）设计两种算法的流程图设计FIFO算法的流程图。 其他任选一个算法设计流程图。（3）使用Vi编写实现两种算法的程序FIFO内存调度算法的代码。（其他任选一个算法）内存调度算法的代码。（4）结果分析分析设计结果是否达到预期目标。 针对同一访问序列比较两种算法的缺页率。工作计划及安排：第一天上午：教师讲解原理及课程设计要求和任务。第一天下午：原理学习、任务分析、资料查阅。第二天： 流程图设计。第三天： 代码编写。第四天： 代码编写。第五天： 提交设计结果及设计报告。指导教师签字 年 月 日 课程设计（大作业）成绩学号：x 姓名：x 指

3、导教师：x课程设计题目： 内存调度算法模拟完成情况总结：在这次的实训过程中，我觉得我最大的收获就是更加熟析（FIFO）和（LRU）算法，因为首先我们所要设计的两个算法中，我对于第一个算法（FIFO）思想还能了解透彻一些，第二个算法(LFU)思想就有些模糊，因为这个算法思想其实它是从算法（LRU）延伸出去的，它们之间还是有一定的联系，但是其算法思想还是不一样的，我就一直在纠结它们的使用时间和使用次数万一在遇到一些比较特殊的情况下，我们要怎样调度，比如说一串数据在整个调度过程中仅仅只出现一次的情况下，而又要求只能用LFU算法实现，那么此刻LFU算法和LRU算法根本就没有区别，这个问题在实训的最后我

4、还是没有想通，而在我的程序实现过程中，纠结于这个问题，我只能做出次数比较后，如果次数相同，则默认淘汰放于首位的数。但是在整个编译的过程中因为这个算法的原因也无数次的出错，总是无法调试出正确的结果，最后是参考了同学的思想后，才完成的。 每次实训涉及到程序编译我是最苦恼的，因为我并不擅长于程序编写，但是又不想草草了事，所以就会不停地去网上看别人的程序，之后又要不断请教同学，最后还不一定能够完成任务，但是我还是挺愿意这样去做的，因为最后我还是能学到好多东西，还有就是很感谢班上热心的小伙伴，总是很耐心，热心地帮我。指导教师评语：成绩：填表时间：指导教师签名：目录一、 题目分析（原理说明）- 1 -1.

5、1先进先出算法（FIFO算法）基本思想- 1 -1.2最不经常使用页面淘汰算法（LFU算法）基本思想- 1 -1.3页面淘汰算法优劣的衡量标准及Belady异常现象- 1 -二、 程序设计- 2 -2.1 流程图- 2 -2.2 数据结构说明- 5 -2.3 代码- 5 -三、 结果分析- 10 -四、 实验总结及心得体会- 12 -参考文献- 13 -课程设计（大作业）报告一、 题目分析（原理说明）在进程运行过程中，若其访问的页面不在内存而需要将其调入，但内存已无空闲空间时，需要从内存中调出(淘汰)一页程序或数据，送入磁盘的对换区。用来选择淘汰哪一页的算法叫做置换算法，也称为淘汰算法。淘汰算

6、 某一序列直接影响系统的性能。一个好的置换算法应具有较低的页面置换频率，置换时应将以后不再会访问，或是在较长时间内不再访问的页面淘汰。1.1先进先出算法（FIFO算法）基本思想先进先出算法选择在内存中驻留时间最长的页面予以淘汰，即先进入内存的页面先淘汰。其优点是算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，使该指针总是指向最先进入内存的页面。缺点是算法与进程的实际运行规律不相适应，因为进程中的某些页面经常被访问，但先进先出置换算法不能保证这些页面不被淘汰。1.2最不经常使用页面淘汰算法（LFU算法）基本思想最不经常使用页面淘汰算法，淘汰那些到当前时间为

7、止访问次数最少的页。页表中增加一个访问记数器。1.3页面淘汰算法优劣的衡量标准及Belady异常现象页面淘汰算法优劣的衡量标准：操作系统采用请求分页方式管理内存时，可以使用缺页中断率衡量页面淘汰算法的优劣，缺页中断率f，ffa （a是总的页面访问次数，f是缺页中断次数）。对于一个给定内存页面数和给定的进程页面访问序列，如果某算法的缺页中断率最小，则该算法对于该页面访问序列而言是最好的。Belady异常现象：缺页中断率还与系统设定的内存页面数有关系，通常情况下，内存页面数越大，缺页中断也越小。但在采用FIFO算法时，有时会出现当内存页面数越大，缺页次数不减少反而增加的现象，称之为Belady异常

8、现象。二、 程序设计2.1 流程图图2.1.1总体功能流程图在整个内存调度算法模拟过程中，我们主要运用了FIFO先进先出算法和LFU最不经常使用页面淘汰算法，所以页面的设计比较单一，因为是运用Microsoft Visual C+ 6.0，然后又是因为以前也学过一点相关的程序，所以在实现功能的同时，我也把自己的一些信息，还有文字的颜色做了美化，界面也显得丰富些。图2.1.2 FIFO功能实现分析流程图 在理解了FIFO的算法之后，我们就把其算法流程图细化出来，方便我们写程序。因为我的程序在设计过程中开始就将物理模块还有要存放的数据就先设置并输入测试数据。然后再进行选择哪个算法分析。当选择FIF

9、O算法时，我利用一维及二维数组，循环判断语句来进行算法的分析实现。图2.1.3 LFU功能实现分析流程图在进行次算法的时候，我是在上一个算法的基础上增加一条判断语句，因为该算法的设计思想是在一定时间内根据数据出现的频率来进行调度的，所以这个算法的实现变得有些复杂，就是需要我们首先看数据首次出现的时间（这利用FIFO的思想），之后就要记录这些数据出现的次数，根据他们出现的数次的多少来进行淘汰。2.2 数据结构说明#include /*函数头部的定义和声明*/ #include /* C+中标准库函数的定义/*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串

10、个数*/static int memery10=0; /*物理块中的页号*/static int page100=0; /*页面号引用串*/static int temp10020=0; /*辅助数组*/char flag100= ;/*出现置换时的标志*/*置换算法函数*/void FIFO();/*完成先进先出算法的整个置换过程*/ void LFU();/*完成最不经常使用页面淘汰算法的整个置换过程*/ /*辅助函数*/void print(unsigned int t);/*功能界面显示及性能分析结果输出*/void designBy();/*程序运行时初始界面及退出界面*/void

11、download();/*数据加载界面*/void mDelay(unsigned int Delay);/*数据分析计算延迟界面*/2.3 代码/*主函数*/void main() int i,code;system(color 0A);designBy();printf(请按任意键进行初始化操作. n);printf(n);printf( );getchar();system(cls);system(color 0B);printf(请输入物理块的个数(M=10)：);scanf(%d,&mSIZE);printf(请输入页面号引用串的个数(P=100)：);scanf(%d,&pSIZE

12、);puts(请依次输入页面号引用串(连续输入，无需隔开)：);for(i=0;ipSIZE;i+) scanf(%1d,&pagei);download();system(cls);system(color 0E); do puts(输入的页面号引用串为：);for(i=0;i);getchar();system(cls); while (code!=3);getchar();/*载入数据*/void download()int i;system(color 0D);printf(n);printf(正在载入数据，请稍候 !n);printf(n);printf(Loading.n);pri

13、ntf( O);for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.n载入成功，按任意键进入置换算法选择界面：);getchar();/*设置延迟*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*显示设计者信息*/ void designBy()printf(n);printf( 页面置换算法 n);printf( 学号：151101210005 n);printf( 姓名：张永辉 n);pri

14、ntf(n);void print(unsigned int t)int i,j;for(i=0;ipSIZE;i+)printf(%d ,pagei);putchar(10);for(j=0;jmSIZE;j+)for(i=0;ipSIZE;i+) printf( |%d|,tempji);putchar(10);for(i=0;ipSIZE;i+)printf(%3c,flagi);printf(n-n);printf(缺页次数：%dtt,t);printf(缺页率：%d/%dn,t,pSIZE);printf(置换次数：%dtt,t);printf(访问命中率：%f%n,100.0*(p

15、SIZE-t)/pSIZE);printf(-n);/*计算过程延迟*/void compute()int i;printf(正在进行相关计算，请稍候);for(i=1;i20;i+)mDelay(15);if(i%4=0)printf(bbbbbb bbbbbb);elseprintf();for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先进先出页面置换算法*/void FIFO() int i,j,k; int counter=0; intmemery100=0;for(i=0;ipSIZE;i+

16、)j=0;while(j0;k-)memeryk=memeryk-1;memeryk=pagei;counter+;for(j=0;jmSIZE;j+)tempji=memeryj;compute();print(counter);void LFU()int i,j,replace; int counter=0,sum=0; int use_time100;int memery100=0;for(i=0;ipSIZE;i+)use_timepagei+;sum+;j=0;while(jmSIZE & memeryj!=pagei)j+;if(j=mSIZE)flagi=+;counter+;i

17、f(sum=mSIZE)for(j=0;jmSIZE;j+)if(memeryj=0 ) memeryj=pagei;break;else use_time0=100;for(j=0;jmSIZE;j+)if(use_timememeryjuse_time0)use_time0=use_timememeryj;replace=j;memeryreplace=pagei;for(j=0;jmSIZE;j+)tempji=memeryj;compute();print(counter); 三、 结果分析在程序完成之前出现了很多错误，修改了无数次，下面这些是程序完全无误是的结果图3.1程序运行初始界

18、面图3.2程序在进入算法前设置物理块及存入数据图3.3程序功能界面选择图3.4FIFO功能实现及结果分析图3.5LFU功能实现及结果分析图3.6退出界面 而通过对此组数据的分析，从其中断率我们可以知道LFU算法对于该页面访问序列而言是最好的。四、 实验总结及心得体会 在这次的实训过程中，我刚开始的时候其实挺不知所措的，因为首先我们所要设计的两个算法中，我对于第一个算法（FIFO）思想还能了解透彻一些，第二个算法(LFU)思想就有些模糊，因为这个算法思想其实它是从算法（LRU）延伸出去的，它们之间还是有一定的联系，但是其算法思想还是不一样的，我就一直在纠结它们的使用时间和使用次数万一在遇到一些比

19、较特殊的情况下，我们要怎样调度，比如说一串数据在整个调度过程中仅仅只出现一次的情况下，而又要求只能用LFU算法实现，那么此刻LFU算法和LRU算法根本就没有区别，这个问题在实训的最后我还是没有想通，而在我的程序实现过程中，纠结于这个问题，我只能做出次数比较后，如果次数相同，则默认淘汰放于首位的数。但是在整个编译的过程中因为这个算法的原因也无数次的出错，总是无法调试出正确的结果，最后是参考了同学的思想后，才完成的。 其次，在程序设计的过程中，刚刚开始的时候是想着用C#语言来编写程序的，但是在网上看了好多程序之后，发现用这种语言简单但是转的弯有点大，而我对于C#语言的运用不是很熟练，因为我的程序是

20、参考了网上一些写的比较好的网友的，所以最后是采用了C语言来写的，在编译的过程中还是遇到了好多自己不会的，请教了同学不少，对局部变量和全局变量的使用错误，导致程序在运行完一个算法后就无法实现第二个算法的正确运行分析，改了好久终于将程序能够正确运行完成。每次实训涉及到程序编译我是最苦恼的，因为我并不擅长于程序编写，但是又不想草草了事，所以就会不停地去网上看别人的程序，之后又要不断请教同学，最后还不一定能够完成任务，但是我还是挺愿意这样去做的，因为最后我还是能学到好多东西，还有就是很感谢班上热心的小伙伴，总是很耐心，热心地帮我。参考文献1. 严蔚敏, 吴伟民. 数据结构. 清华大学出版社, 2005.112. 谭浩强. C语言程序设计. 清华大学出版社, 2005.113. 于帆, 赵妮. 程序设计基础(C语言版). 清华大学出版社, 2006.114. 汤小丹, 梁红兵, 哲凤屏, 汤子瀛. 计算机操作系统. 西安电子科技大学出版社, 2007.5