操作系统课程设计实验报告模板

操作系统课程设计实验报告书题目：页面置换算法之先进先出题目编号：18院系：信息科学与技术学院班级：12级1班小组成员：组长：张海洋学号：12051004组员：李奔学号：120510052014-12-31

目录一、课程设计任务划分 1二、基本原理 2（一）页面置换算法定义（二）所使用的算法

（三）设计思想三、基本思路 3（一）流程图（二）变量（三）所用函数四、调试及实验结果 4五、个人体会 5PAGEPAGE1一、课程设计任务划分成员具体分工张海洋设计项目流程程序合并实验报告书书写李奔程序调试网上搜索程序资料心得体会二、基本原理（题目所涉及课程内容，用到了那种算法，该算法的基本原理是什么？500字以上，可加页，下同）（一）页面置换算法定义在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内

存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

（二）所使用的算法

1)最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。2)先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。3)最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。（三）设计思想选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。LRU基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。三、基本思路（1）流程图将页号放入物理块中，编号加1将页号放入物理块中，编号加1引用串编号大于物理块数?载入页号序列，从第0个得到页号开始页号在物理块中?根据选择的置换算法完成置换页号序列载完?结束是否是是是是变量/*全局变量*/intmSIZE;/*物理块数*/intpSIZE;/*页面号引用串个数*/staticintmemery[10]={0};/*物理块中的页号*/staticintpage[100]={0};/*页面号引用串*/staticinttemp[100][10]={0};/*辅助数组*/inttime[10]={0};/*记录进入物理块的时间*/intnext[10]={0};/*记录下一次访问时间*/intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/所用函数/*置换算法函数*/voidFIFO();/*先进先出页面置换算法*/函数原型：voidFIFO(){intmemery[10]={0};inttime[10]={0};/*记录进入物理块的时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理块中*/{count++; /*计算换出页*/max=time[0]<time[1]?0:1; for(m=2;m<mSIZE;m++) if(time[m]<time[max]) max=m;memery[max]=page[i];time[max]=i;/*记录该页进入物理块的时间*/for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}voidLRU();/*最近最久未使用置换算法*/函数原型：voidLRU(){intmemery[10]={0};intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;else flag[j]=i;/*刷新该页的访问时间*/}if(k==mSIZE)/*如果不在物理块中*/{count++; /*计算换出页*/max=flag[0]<flag[1]?0:1; for(m=2;m<mSIZE;m++) if(flag[m]<flag[max]) max=m;memery[max]=page[i];flag[max]=i;/*记录该页的访问时间*/for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}voidOPT();/*最佳置换算法*/函数原型：voidOPT(){intmemery[10]={0};intnext[10]={0};/*记录下一次访问时间*/inti,j,k,l,m;intmax;/*记录换出页*/intcount=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理块中*/{ count++; /*得到物理快中各页下一次访问时间*/ for(m=0;m<mSIZE;m++) { for(l=i+1;l<pSIZE;l++) if(memery[m]==page[l]) break; next[m]=l; } /*计算换出页*/ max=next[0]>=next[1]?0:1; for(m=2;m<mSIZE;m++) if(next[m]>next[max]) max=m; /*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i]; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}2./*辅助函数*/voiddesignBy();/*显示设计者信息*/函数原型：voiddesignBy(){ printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃页面置换算法┃\n"); printf("┃班级：┃\n"); printf("┃姓名：同学┃\n"); printf("┣━━━━━━━━━━━━━━━━━━━━┫\n");}voiddownload();/*载入数据*/函数原型：voiddownload(){ inti; system("color0D"); printf("╔════════════╗\n"); printf("║正在载入数据，请稍候!!!║\n"); printf("╚════════════╝\n"); printf("Loading...\n"); printf("O"); for(i=0;i<51;i++) printf("\b"); for(i=0;i<50;i++) { mDelay((pSIZE+mSIZE)/2); printf(">"); } printf("\nFinish.\n载入成功，按任意键进入置换算法选择界面：>>>"); getchar();}voidmDelay(unsignedintDelay);/*设置延迟*/函数原型：voidmDelay(unsignedintDelay){unsignedinti;for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf("\b"); } }voidcompute();/*计算过程延迟*/函数原型：voidcompute(){ inti; printf("正在进行相关计算，请稍候"); for(i=1;i<20;i++) { mDelay(15); if(i%4==0) printf("\b\b\b\b\b\b\b\b\b\b\b\b"); else printf("Θ"); } for(i=0;i++<30;printf("\b")); for(i=0;i++<30;printf("")); for(i=0;i++<30;printf("\b"));}3./*主函数*/voidmain()四、调试及实验结果第一组数据：1.开始运行2.按任意键进行初始化：3.载入数据：4.进入置换算法选择界面：5.运算中延迟操作：6.三种算法运行结果7.退出算法第二组数据：1.开始运行2．按任意键进行初始化：3.载入数据：4.进入置换算法选择界面：5.运算中延迟操作：6.三种算法运行结果