页面置换说明书.doc

西华大学数计学院课程设计说明书数学与计算机学院课程设计说明书课 程 名 称: 计算机操作系统-课程设计 课 程 代 码: 8404061 题 目: 页面置换模拟程序 年级/专业/班: 2009级计科4班 学 生 姓 名: X X X 学 号: 3120*5422 开 始 时 间: 2011 年 12 月 05 日完 成 时 间: 2011 年 12 月 25 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日I目 录1 引 言11.1 问题的提出11.2国内外研究的现状11.3任务与分析12.程序的主要功能22.1生成页表22.2 FIFO算法22.3 LRU算法22.4显示功能23.程序运行平台34 总体设计45 程序说明56 模块分析66.1 页表模块66.2 内存块模块66.3 先进先出（FIFO）算法模块76.4 最近未使用算法（LRU）106.5 显示模块148 结论19 西华大学数计学院课程设计说明书1 引 言1.1 问题的提出在传统的操作系统中，进程运行过程，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲时间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出换出的页面的称为页面置换算法。1.2国内外研究的现状 目前，普遍的计算机都用几种相同的页面置换算法，这些页面置换算法，都具有较低的页面更换率，都试图更接近于理论上的目标。将那些以后不再访问的页面换出，或把那些在较长时间内不会再访问的页面调出。目前最常用的有最佳置换算法和先进先出算法、最近未使用置换算法、CLOCK置换算法等。1.3任务与分析本课题主要的目的是编制页面置换算法的模拟程序,并测试。先进先出算法就是淘汰最先进入内存的页面，只要把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老页面。LRU算法当进程第一次对面2进行访问时，由于页面7是最近未被访问的，故将它置换出去。当进程第一次对页面3进行访问，第1页成为最近未使用的页，将它换出。2. 程序的主要功能2.1生成页表用随机数方法产生页面走向，页面走向长度为L，即一串随机页面号构成访问页表，页号可重复。 2.2 FIFO算法根据页面走向，用先进先出置换算法（FIFO算法）进行页面置换，统计缺页率，并显示出置换过程。2.3 LRU算法根据页面走向，用最近未使用置换算法（LRU算法）进行页面置换，统计缺页率，并显示出置换过程。2.4显示功能显示进程访问页表中的每个页面时的情况，包括缺页替换后内存块中的页面，显示缺页率以及标题和附加信息等。3. 程序运行平台VC+6.0。具体操作如下：新建文件C+Source File，编写代码，再编译，链接，执行等。4 总体设计主 函 数产生页表FIFO算法LRU 图4.1 系统总体框架图5 程序说明1.页表页表用数组存放，由随机数组成。代码如下：int ak; k代表页表长度 for (int i=0;ik;i+) ai=1+(int)(10.0*rand()/(RAND_MAX+1.0); 2.内存块内存块也存放在数组里。代码如下：m 代表内存块数 int bm;int i,j,l,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1总之，此程序的主要数据结构思想是数组，也可用链表，但是太过于繁复，数组比较简单而且比较清晰。6 模块分析6.1 页表模块用随机数方法产生页面走向，并存放在数组里面。用宏定义页面的长度，可以很方便被用户改动。关键代码：#define k 20 /用宏定义页面长度给定固定值方法：int ak=7,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0; 随机数分配方法：int ak; for (int i=0;ik;i+) ai=1+(int)(10.0*rand()/(RAND_MAX+1.0); 6.2 内存块模块内存块内装页面号，用数组来表示，并配置一个替换指针，以便缺页时替换所指页面 。用宏定义可用内存块数，方便整体改动。关键代码：#define m 4 /宏定义内存块数数组定义内存并初始化：int bm;int i,j,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1 在不同算法中的替换：if(bj=ai) /内存中有此页面则返回无需置换 并无需输出 break; else if(j=m-1) f=br; br=ai; r+; /替换指针指向下一个页面if(bj=ai) /命中内存中的页面的情况if(j!=m-1) /无需输出显示for( l=j;lm-1;l+)bl=bl+1; /未被访问的页面往前移bm-1=ai; /命中的页面替换到最后break;else if(j=m-1)f=b0;b0=ai; /替换最后的页面即最近很少用的页面for(l=0;lm;l+)bl=bl+1;bm-1=ai; 6.3 先进先出（FIFO）算法模块首先输入页表即一串页面号，然后系统把访问页面调入内存，如果内存中不存在此页面就用先进先出算法替换掉内存中一个页面。并统计缺页率。必须有一个替换指针，循环指向最先进入内存块的那个页面，在出现缺页时替换掉这个页面并指向下一个先进入的页面。关键代码：void FIFO(int ak) int bm;int i,j,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1int r=0; /替换指针int s=0; /缺页标记 for(i=0;ik;i+) cout ai ; /输出当前访问的页面 r=r%m; /控制替换指针循环 for(j=0;jm;j+) /* if(im) /前m个页面直接装入内存块 bi=ai; for(j=0;jm;j+) if(bj!=-1) coutbj ; break; else */ if(bj=ai) /内存中有此页面则返回无需置换 并无需输出 break; else if(j=m-1) f=br; br=ai; r+; /替换指针指向下一个页面 for(j=0;jm;j+) /输出替换后内存中的页面 if(bj!=-1) coutbj ; if(f!=-1) s+; /缺页标记加一 coutendl;cout*缺页率：100.0*s/k%endlendl;/统计缺页率FIFO 流程图结 束开 始页面aiAiai?=bj判断br=ai替换是i+ 否 i+i=kj+j=m-1bji!=kj=m-16.4 最近未使用算法（LRU）首先输入页表即一串页面号，然后系统把访问页面调入内存，如果内存中不存在此页面就用最近未使用算法替换掉内存中一个页面。并统计缺页率。必须找到那个最近未使用的页面，则每次访问页面时把该页面往最后放，那么最前面的页面就是最近未使用的页面，在出现缺页中断时替换掉这个页面。关键代码：void LRU(int ak)int bm;int i,j,l,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1int s=0; /缺页率for(i=0;ik;i+)cout ai ; /输出当前访问的页面for(j=0;jm;j+)/*if(im) /前m个页面直接装入内存块 bi=ai; for(j=0;jm;j+) if(bj!=-1) coutbj ; break; else*/if(bj=ai) /命中内存中的页面的情况if(j!=m-1) /无需输出显示for( l=j;lm-1;l+)bl=bl+1; /未被访问的页面往前移bm-1=ai; /命中的页面替换到最后break;else if(j=m-1)f=b0;b0=ai; /替换最后的页面即最近很少用的页面for(l=0;lm;l+)bl=bl+1;bm-1=ai; for(j=0;jm;j+)if(bj!=-1) coutbj ;if(f!=-1)s+;coutendl;cout*缺页率：100.0*s/k%endlendl;/统计缺页率LRU 流程图开 始页面ai内存bjai?=bjb0=ai往后放bm-1=ai替换i=0j=0是i+否j+i+j=m-1结 束i=k6.5 显示模块首先输出页表中的页面，然后每访问一个页面显示出内存中的替换情况，为了让显示结果更加清晰明了，如果没有出现缺页中断则不显示内存块中的页面，出现缺页中断时，显示替换后的结果，并统计缺页率。关键代码：FIFO算法中的显示模块for(i=0;ik;i+) cout ai ; /输出当前访问的页面for(j=0;jm;j+) if(bj=ai) /内存中有此页面则返回无需置换 并无需输出 break; else if(j=m-1) for(j=0;jm;j+) /输出替换后内存中的页面 if(bj!=-1) coutbj ; coutendl; cout*缺页率：100.0*s/k%endlendl; /统计缺页率LRU算法中的显示模块for(i=0;ik;i+)cout ai ;/输出当前访问的页面for(j=0;jm;j+)if(bj=ai) /命中内存中的页面的情况if(j!=m-1) /无需输出显示for( l=j;lm-1;l+)bl=bl+1; /未被访问的页面往前移bm-1=ai; /命中的页面替换到最后break;else if(j=m-1)f=b0;b0=ai; /替换最后的页面即最近很少用的页面for(l=0;lm;l+)bl=bl+1;bm-1=ai; for(j=0;jm;j+)if(bj!=-1) coutbj ;coutendl;cout*缺页率：100.0*s/k%endlendl;/统计缺页率7 系统测试首先进入VC+6.0，打开文件Source Flie 页面置换.cpp，然后进入源程序，接着编译、连接、显示结果。此次测试输入的页表长度为20，内存块为4。测试结果如下。 图 7.1 标题及页表数据 图 7.2 先进先出替换过程 图 7.3 最近未使用置换过程8 结论通过这个页面置换课程设计，不仅掌握了操作系统中页面置换的原理，还加深和巩固了对编写程序的能力，提高了解决问题的能力。这个程序给出了两个页面置换算法，先进先出和最近未使用算法。先进先出算法使用一个替换指针，指向最老的页面，发生缺页中断时替换掉，然后指向下一个，用i=imodm是为了控制替换指针循环。最近未使用算法则不用替换指针，只需每次把移动页面，把最近未使用的页面移动到特殊位置，缺页时直接替换就可以。用条件判断语句分别对有无命中页面进行处理，并同时记录缺页率。在输出显示上，有替换的情况下才输出，格式控制的很有层次，都是为了能够一目了然地看出缺页率。在内存块初始化-1后，开始先把前m 个页面直接依次存入，但发现这样做有漏洞，如果前m个页面有重复，则会出错，所以后面加上了条件判断是否为-1，如果有-1且未命中页面则直接存入下一个内存块中，如果没有-1则需要替换页面。程序其他地方问题不是很大，只是熟练程度不够，常出现一些不必要的错误，修改也比较简单。附 录（可选）附录1 源程序清单#include#include/#include/#include/using namespace std;#define m 4 /内存块m、#define k 20 /页表长度k/先进先出算法void FIFO(int ak) int bm;int i,j,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1int r=0; /替换指针int s=0; /缺页标记 for(i=0;ik;i+) cout ai ; /输出当前访问的页面 r=r%m; /控制替换指针循环 for(j=0;jm;j+) /* if(im) /前m个页面直接装入内存块 bi=ai; for(j=0;jm;j+) if(bj!=-1) coutbj ; break; else */ if(bj=ai) /内存中有此页面则返回无需置换 并无需输出 break; else if(j=m-1) f=br; br=ai; r+; /替换指针指向下一个页面 for(j=0;jm;j+) /输出替换后内存中的页面 if(bj!=-1) coutbj ; if(f!=-1) s+; /缺页标记加一 coutendl;cout*缺页率：100.0*s/k%endlendl;/统计缺页率/最近未使用法void LRU(int ak)int bm;int i,j,l,f;for(i=0;im;i+)bi=-1; /初始化页表全部置-1int s=0; /缺页率for(i=0;ik;i+)cout ai ;/输出当前访问的页面for(j=0;jm;j+)/*if(im) /前m个页面直接装入内存块 bi=ai; for(j=0;jm;j+) if(bj!=-1) coutbj ; break; else*/if(bj=ai) /命中内存中的页面的情况if(j!=m-1) /无需输出显示for( l=j;lm-1;l+)bl=bl+1; /未被访问的页面往前移bm-1=ai; /命中的页面替换到最后break;else if(j=m-1)f=b0;b0