《[计算机软件及应用]操作系统页面置换算法和磁盘调度算法.doc》由会员分享,可在线阅读,更多相关《[计算机软件及应用]操作系统页面置换算法和磁盘调度算法.doc(33页珍藏版)》请在三一文库上搜索。
1、物理与电子信息工程学院操作系统课程设计报告题目:1、 页面淘汰算法 2、 磁盘调度算法 班级: 10计本 完成日期: 2012-9-14 指导教师: 曾令华 目 录一、页面淘汰算法 (一) 11.1 实验目的 31.2 概念原理 31.3 总体设计41.4 详细设计 61.5 心得总结 18二、磁盘调度算法 (二) 192.1 实验目的 192.2 概念原理 192.3 总体设计 202.4 详细设计 212.5 心得总结 32一、 页面淘汰算法 (一)1.1 实验目的加深对操作系统原理的进一步认识,加强实践动手能力和程序开发能力的培养,提高分析问题解决问题的能力,培养合作精神,以巩固和加深页
2、面置换的概念。这次课程设计,就是通过模拟页面置换来加深对操作系统中页面置换概念的理解通过对页面置换算法的设计,深入理解页面淘汰算法的优劣性。1.2 概念原理(1) 先进先出页面置换算法(FIFO)FIFO算法这是最早出现的置换算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如含有全局变量、常用函数、例程等的页面,FIFO算法并不能保证这些页面不被淘汰。(2) 最佳置
3、换算法(OPT)它是由Belady于1966 年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用此算法来评价其它算法。(3)最近最久未使用置换算法(LRU)最近最久未使用(LRU)置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU 置换算法是选择最近最久未使用的页面予以淘
4、汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。1.3 总体设计1、 根据要求设计页面淘汰算法的流程 运行程序进入主页面,选择输入模式,随机和手动输入两种模式 (1)随机模式l 输入物理块和页面号引用串长度的随机范围l 按要求随机生成页面号引用串l 进入页面置换算法选择模式l 1为FIFO,2为LRU,3为OPT,4为退出l 产生结果,分析数据正确型,完成后可以再次选择,进行不同的模式来计算l 退出关闭程序 (2)手动模式l 手机输入物理块和页面号引用串长度的数值l 按要求生成
5、页面号引用串l 进入页面置换算法选择模式l 1为FIFO,2为LRU,3为OPT,4为退出l 产生结果,分析数据正确型,完成可以再次选择,进行不同的模式来计算l 退出关闭程序FIFO算法流程图:OPT算法流程图:LRU算法流程图:1.4 详细设计流程截图:初始化欢迎说明随机生成物理块跟页面号引用串个数,选择算法选择1.FIFO算法选择3.OPT算法手动输入选择算法源代码:#include #include #include#include #define L 20/页面走向长度最大为20/*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/stat
6、ic int memery10=0; /*物理块中的页号*/static int page100=0; /*页面号引用串*/static int temp10010=0; /*辅助数组*/*置换算法函数*/void FIFO();void LRU();void OPT();void Hwi();/*辅助函数*/void print(unsigned int t);void zinstruction();void sinstruction();void mDelay(unsigned int Delay);/*主函数*/void main() int eneration; int code; s
7、ystem(color 0D); cout|*|endl; cout|欢迎: |endl; cout| 页面置换算法 |endl; cout| 包含FIFO/OPT/LRU |endl; cout| by-王力&王运 |endl; cout|*|endl; cout|*|endl; cout|说明: |endl; cout| 选择物理块与页面号引用串个数生成方式 |endl; cout| 生成物理块与页面号引用串个数 |endl; cout| 选择何种算法 |endl; cout| |endl; cout|*|endl; system(pause); system(cls);printf(请选
8、择物理块与页面号引用串个数的生成方式n);printf((1随机生成,2手动输入):); do /判断输入是否正确scanf(%d,&eneration);if(eneration!=1&eneration!=2)printf(请选择1或者2:);while(eneration!=1&eneration!=2);switch(eneration)case 2:system(cls);sinstruction();getchar();system(color 0B);printf(请输入物理块的个数(M=10):);scanf(%d,&mSIZE);printf(请输入页面号引用串的个数(P=1
9、00):);scanf(%d,&pSIZE);puts(请依次输入页面号引用串(连续输入,需用空格隔开):);for(int i=0;i10)printf(实际物理块必须小于10(即后者不得大于10),请重新输入:);if(a=b)printf(输入的后者不得大于或等于前者,请重新输入:);/else break;while(b10|a=b);mSIZE=rand()%(b-a)+a;/*产生a-b(包括a和b)的随机数*/srand(time(NULL);printf(请输入页面号引用串的随机范围,两个数之间请用空格隔开(前者大于后者):);do /判断psize不大于100 scanf(%
10、d %d,&f,&h);/*产生f-h(包括f和h)的随机数*/ if(h100) printf(实际页面长度须小于100(即后者不得大于100),请重新输入: ); if(f=h) printf(输入的后者不得大于或等于前者,请重新输入: );/ else break;while(h100|f=h); pSIZE=rand()%(h-f)+f; printf(n);printf(随机产生的物理块数x=%d 和页面号引用串长度y=%d n,mSIZE,pSIZE);getchar();j=time(NULL);/取时钟时间srand(j);/以时钟时间x为种子,初始化随机数发生器for(i=0
11、;ipSIZE;i+) /产生随机数组pagei=rand( )%10;/产生1到9之间的随即数放到pagei中 printf(n);system(pause);break;/system(cls);/功能选择后的执行do printf(n);printf(随机产生页面号引用串:);for(int i=0;ipSIZE;i+) /显示随机数组printf(%d ,pagei);printf(n);printf(|*|n);printf(|请选择何种算法: |n);printf(| 1.先进先出(FIFO) |n);printf(| 2.最近最久未使用(LRU) |n);printf(| 3.最
12、佳(OPT) |n);printf(| 4.清楚界面 |n);printf(| 0.退出 |n);printf(|*|n); printf(请选择操作: bb);scanf(%d,&code);printf(n);/算法的选用if(code!=1&code!=2&code!=3&code!=4&code!=0) printf(输入错误,请看清选择n);elseswitch(code)case 1:FIFO();printf(n);system(pause);break;case 2:LRU();printf(n);system(pause);break;case 3:OPT();printf(
13、n);system(pause);break;case 4:system(cls); break;case 0:system(cls);system(color 0A);printf(|*|n*);printf(| 感谢使用页面置换算法演示器! |n*);printf(| 如遇bug或有疑问联系 |n*);printf(| 本人不负任何责任 |n*);printf(| by-王力&王运! |n*);printf(|*|n*);exit(0);while (code!=0);/功能选择后的执行end/*显示程序的注意事项*/void zinstruction()printf(说明:n);prin
14、tf( 1、你选择的是随机输入,系统将随机生成页面号引用串n);printf( 2、选择页面面置换算法FIFO/OPT/LRUn);printf( 3、得出结果,关闭程序n);void sinstruction()printf(说明:n);printf( 1、你选择的是手动输入页面号引用串n);printf( 2、选择页面面置换算法有FIFO/OPT/LRUn);printf( 3、得出结果,关闭程序n);void print(unsigned int t)int i,j,k,l;int flag;printf(置换顺序依次为:n);for(k=0;k=(pSIZE-1)/20;k+)for(
15、i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf( %dn,pagei);elseprintf( %d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页
16、面在物理块中*/printf( );elseprintf( |%d|,tempij);/*每行显示20个*/if(i%20=0)continue;printf(n);printf(输出结果: n);printf(缺页次数:%dtt,t+mSIZE);printf(缺页率:%d/%dtt,t+mSIZE,pSIZE);printf(置换次数:%dtt,t);getchar();/*FIFO算法*/void FIFO() int memery10=0; int time10=0; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=
17、0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memer
18、ymax=pagei; timemax=i; /*记录该页进入物理块的时间*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; print(count);/*LRU算法*/void LRU() int memery10=0; int flag10=0; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; fla
19、gi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; elseflagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*记录该页的访问时间*/ fo
20、r(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; print(count);/*OPT算法*/void OPT() int memery10=0; int next10=0; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE
21、;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*得到物理快中各页下一次访问时间*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memerymax=pagei;for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=m
22、emeryj; print(count);1.5 心得总结通过本次课程设计,让我对页面淘汰算法有了充分的了解,我不仅对我们常用的算法进行了编写,还对一些理想的算法也进行了编写,并且通过适当的方法,得以了验证。就该程序而言,随机性使得程序出现了更多的可能性,为我们验证算法提供很大的方便,电脑自动分配,大大的节约了我们的时间,但是我们通过实验不难发现,如果所设的页面项目过大,也会影响我们算法的性能执行效率。对我们所涉及的算法,让我有很大的感触。在FIFO 算法中,无论有无发生缺页或者置换,都需要对每个在内存中的页面的time 值进行增加操作,以保持最先进入的那个页面的time 值是最大的;一个新进
23、来的页面,其time值设置为0。当然,该算法也可以通过队列结构来实现,利用队列的先进先出(FIFO)特性完成,无需设置time字段。distance 用于记录内存物理块集合中每个页面距离再次被使用的页面跨度,缺省值为9999,如果某个页面在后续指令集合中不再出现,则用最大值9999 缺省取代;如果页面再次被使用,则两次使用所跨的页面数,为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。在LRU 算法中,无论是否发生缺页或者置换,除了命中(刚刚被访问过的页面)页面time 值清零之外,其它所有内存中的页面的time 值都加一,以保证最近刚刚被访问的页面的time 值最小,相应
24、time 值最大的页面就是最近最久没有被访问的页面。二、磁盘调度算法 (二)2.1 实验目的加深对操作系统原理的进一步认识,加强实践动手能力和程序开发能力的培养,提高分析问题解决问题的能力,培养合作精神,以巩固和加深磁盘调度的概念。这次课程设计,就是通过模拟磁盘调度来加深对操作系统中磁盘调度概念的理解通过对磁盘调度算法的设计,深入理解提高磁盘访问速度的原理。2.2 概念原理(1)先来先服务算法(FCFS)如果早就绪的进程排在就绪队列的前面,迟就绪的进程排在就绪队列的后面,那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行
25、状态。也就说,它只考虑进程进入就绪队列的先后,而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行,但性能却不大好。(2)最短寻道时间算法(SSTF)该算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,但这种调度算法却不能保证平均寻道时间最短。SSTF算法的平均每次磁头移动距离,明显低于FCFS的距离。SSTF较之FCFS有更好的寻道性能,故过去一度被广泛采用过。(3)扫描算法(SCAN)该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是
26、其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样自里向外的访问,直至再无更外的磁道需要访问时,才将磁道换向自外向里移动。这时,同样也是每次选择这样的进程来调度,即要访问的当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现像。由于在这种算法中磁头移动的规律颇似电梯的运行,因而又常称为电梯调度算法。2.3 总体设计流程图:按递增排序生成磁道号功能列表输入磁道个数说明选择生成方式手动输入随机生成输入磁道个数的范围输入磁道号的范围输入磁道号得出结果1.先来先服务2.最短寻道时间算法3.扫描算法3.清除界面4.退出输入当前磁道号2.4 详细设
27、计流程截图欢迎界面随机生成磁道个数跟磁道号选择1.FCFS算法得出结果选择2.SSTF算法得出结果手动输入磁道个数跟磁道号选择3.算法的结果退出界面源代码#include#include#include stdlib.husing namespace std;void welcome();void byauto();void FCFS(int a,int n);void SSTF(int a,int n);void SCAN(int a,int n);int main() int n;/磁道的个数 /int s;/选择键 int w;/磁道号生成方式 int *a=new intn;/磁道号 int e,f,c,d; welcome(); coutendl; cout请选择磁道个数以及磁道号的生成方式endlw; if(w!=1&w!=2) cout请选择1或2:; if(w=1) cout请输入磁道的个数的范围(0ab10)printf(实际物理块必须小于10(即后者不得大于10),请重新输入:);if(c=d)printf(输入的前者不得大于或等于后者,请重新输入:);if(d10|c=d|d0); n=rand()%(d-c)+c;/*产生a-b(包括a和b)的随机数*/cout生成磁道的个数:nendl;cout请输入磁道号的范围(0ab):;do
链接地址:https://www.31doc.com/p-1991952.html