塔娜操作系统课设报告

操作系统课程设计PAGEPAGE16实习题目指导教师职称学生姓名学号日期实习题目指导教师职称学生姓名学号日期内蒙古师范大学计算机与信息工程学院《操作系统》课程设计报告实习题目指导教师职称学生姓名学号日期设计题目课题三设计一个虚拟存储区和内存工作区，编程序演示下述置换算法的具体实现过程,并计算访问命中率：指导教师职称姓名学号日期

1设计任务设计一个虚拟存储区和内存工作区，编程序演示下述置换算法的具体实现过程,并计算访问命中率。2设计的功能目标要求从主界面选择某算法，且以下算法都要实现：1、先进先出算法（FIFO）2、最近最久未使用算法（LRU）3、随机淘汰算法（RAND）3设计的思想、方法和技术（含数据结构、算法）3.1设计的思想通过键盘选择后实现三种页面置换算法（包括：先进先出算法，最近最久未使用和随机选择算法）：1.输入进程划分的页数，给进程分配的页面数和访问串的长度2.通过随机产生访问串序列（或者可以由试验者手动输入自己想要测试的访问串序列）3.选择要演示的置换算法（1）最近最少使用算法（LRU）

（2）随机置换算法

（3）进先出的算法（FIFO）4.显示三种置换算法的置换流程5.将访问串序列转换成为进入内存页面的页号流输出。6.计算输出各种置换算法的缺页次数，缺页率和命中率7.显示要调出内存的页号8.选择重新输入还是继续演示3.2数据结构3.2.1structpage{intpage_num;//页号intmemory_num;//页面号intflag;//页状态};其中page_num表示页号（处于0~页数之间）memory_num表示页面号（处于0~页面数之间）flag表示页号为page_num的页是否在内存中（0无1有）pagepage_table[100]；//实验中固定的定义了100个page形数据3.2.2定义的数据intpage_size,memory_size，page_s;//表示访问串的长度，分配的页面数和进程分为的页数int*page_array,*memory;//访问串数组的头指针和存放页面内容的头指针3.2.3LackTime//表示缺页次数Page//计算调出的页数Is_full//计算页面数Save[]//存放要换出的页号（在随机置换算法和先进先出算法中）Change_page//存放要换出的页号（在最近最久未使用置换算法中）Weight[]//在最近最久未使用算法中求最近最久未使用的页3.2.voiddisplay();//显示输出函数，用于在调用三种算法来输出页面内容voiderror();//返回出错信息voidFIFO();//先进先出算法实现函数voidsuiji（）；//随机淘汰算法实现函数voidlru（）//最近最久未使用算法实现函数voidadvance（）//对页状态的初始化3.3流程图3.开始开始输入给定进程的页数输入页面数产生访问串序列手动输入访问串？随机产生？调用FIFO置换算法退出1.lru2.随机3.FIFO转到开始01使用随机函数产生调用随机淘汰算法调用Lru置换算法123Y．以之前的数据试验其他算法N．重新输入数据下一轮YN图3.1总程序的流程图3.3.2FIFO算法开始FIFO算法开始数据初始化i=0数据初始化i=0查看page_array[i]页的页状态里flag后看内存中是否存在该页NY缺页次数加一，直接调入内存，不发生置换算法，i++;进入的页数小于等于页面数？Ni++Y查看page_array[i]页的页状态里flag后看内存中是否存在该页YN循环比较已经进入到页面的页的页状态中memory_num的大小，每次将最小的memory_num所对应的页换为page_array[i]并将换出的页还原初始化。i++i是否等于页数-1？Y结束FIFO调用N图3.2FIFO算法流程3.3.3数据初始化i=0数据初始化i=0查看page_array[i]页的页状态里flag后看内存中是否存在该页NY缺页次数加一，直接调入内存，不发生置换算法，i++;进入的页数小于等于页面数？Ni++Y查看page_array[i]页的页状态里flag后看内存中是否存在该页YN通过rand（）%memory_size函数产生0~memory_size之间的随机数，循环的与页状态中的memory_size相比，相等时换出该页面的内容，并将换出的页还原初始化，调入page_array[i]，并将该页对应的页状态置相应数。

大小，每次将最小的memory_num所对应的页换为page_array[i]并将换出的页还原初始化。i++i是否等于页数-1？Y结束随即淘汰算法调用N随即淘汰算法开始图3.3随机淘汰算法图3.3.4LLru算法开始各种变量初始化，i=0输出当内存中页面中没有调入页时的状态，初始化位各页-1判断page_array[i]页是否存在于页面中N缺页次数加一，直接将页调入而不发生置换算法，i++；Yi++++i=页面数？YN从page_array[i-1]开始循环的和之间已经在页面里面的页号比较，比较的同时加一找到最大的数对应的内存页面后将该页面的东西置换成page_array[i]的内容，并更改相关状态，且i++；i=页面数-1？NYLru算法结束图3.4LRU算法流程4设计的主要代码及注释4.1先进先出算法主要代码 for(inti=0;i<page_size;i++)//最外层循环，挨个控制访问串{in=0;//初始化，做标志位if(page_table[page_array[i]].flag==1)//查看i号页的状态位判断是否在内存中{cout<<"【"<<page_array[i]<<"】号页已经在内存中，不需调入!所以内存中页面内容为："<<endl;//在内存中则输出提示信息in=1;//并置有关状态位}if(in==0&&memory[memory_size-1]!=-1)//内存中没有将要调用的页且没有空闲的内存页面{lackTime++;//缺页次数加一for(intj=0;j<page_s;j++)//循环页面号选出相匹配的后实现置换{if(page_table[j].memory_num==n){cout<<"【"<<page_array[i]<<"】号页不在内存中，所以要发生置换，并换掉页"<<j<<endl;save[page++]=j;//将要调出的页号记录page_table[j].memory_num=-1;//将调出的页的相关状态还原page_table[j].flag=0;break;}}memory[n]=page_array[i];//将新页号调入内存页面数组中储存并更改对应页的状态page_table[page_array[i]].flag=1;page_table[page_array[i]].memory_num=n;++n;if(n==memory_size)n=0;//当n的值等于页面数时，置零后开始下一组页的调入}if(in==0&&memory[memory_size-1]==-1)//当内存中无对应的页且内存中有空闲页面时{cout<<"【"<<page_array[i]<<"】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:"<<endl;lackTime++;memory[is_full]=page_array[i];修改相应的页状态和页面内容，用于显示输出page_table[page_array[i]].flag=1;page_table[page_array[i]].memory_num=is_full;is_full++;}for(intq=0;q<memory_size;q++)//输出内存页面的内容cout<<memory[q]<<"";cout<<endl;}4.2随机淘汰算法主要代码： for(inti=0;i<page_size;i++)//最外层循环，挨个控制访问串{in=0;//初始化，做标志位if(page_table[page_array[i]].flag==1)//查看i号页的状态位判断是否在内存中{cout<<"【"<<page_array[i]<<"】号页已经在内存中，不需调入!所以内存中页面内容为："<<endl;//在内存中则输出提示信息in=1;//并置有关状态位}if(in==0&&memory[memory_size-1]!=-1)//内存中没有将要调用的页且没有空闲的内存页面{lackTime++;//缺页次数加一replace=rand（）%memory_size；//通过随机函数产生0~memory_size之间的随机数for(intj=0;j<page_s;j++)//循环页面号后选出与产生的随机数相匹配的页面号后实现置换{if(page_table[j].memory_num==replace){cout<<"【"<<page_array[i]<<"】号页不在内存中，所以要发生置换，并换掉页"<<j<<endl;save[page++]=j;//将要调出的页号记录page_table[j].memory_num=-1;//将调出的页的相关状态还原page_table[j].flag=0;break;}}memory[replace]=page_array[i];//将新页号调入内存页面数组中储存并更改对应页的状态page_table[page_array[i]].flag=1;page_table[page_array[i]].memory_num=replace;}if(in==0&&memory[memory_size-1]==-1)//当内存中无对应的页且内存中有空闲页面时{cout<<"【"<<page_array[i]<<"】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:"<<endl;lackTime++;memory[is_full]=page_array[i];//修改相应的页状态和页面内容，用于显示输出page_table[page_array[i]].flag=1;page_table[page_array[i]].memory_num=is_full;is_full++;}for(intq=0;q<memory_size;q++)//输出内存页面的内容cout<<memory[q]<<"";cout<<endl;}}4.3最近最久未使用算法主要代码for(i=0;i<page_size;i++)//外层循环，顺序调入访问串{ in=0;//初始化相应的标志位 for(q=0;q<memory_size;q++)//循环比较内存页面的内容和将要调入的页，看是否内存中已有 { if(page_array[i]==memory[q])//当该页已经在内存中时 { cout<<"【"<<memory[q]<<"】号页已经存在内存中，此处不用调入，即保持上次调入的状态:"<<endl;;//在此处没有发生缺页，由于内存中已经存在该页。in=1;break; //改变状态为并退出当前for循环 } } if(in==0&&memory[memory_size-1]!=-1)//当内存中无该页面且内存无空闲页面时 { lackTime++; //缺页次数加一 for(q=0;q<memory_size;q++)//循环初始化为0 weight[q]=0; for(q=0;q<memory_size;q++)//计算寻找在最近一段时间内最久没有使用过的页所处的页面号 { for(intp=i-1;p>=0;p--) { weight[q]++;//计算页面中各页到其余页的权重，加一 if(memory[q]==page_array[p])break;//当有相同的页时推出此层循环 } } max=0; for(q=0;q<memory_size;q++) { if(weight[q]>max) max=weight[q];//找出最大的weight[q]中的q值 } for(q=0;q<memory_size;q++) if(max==weight[q])break;//找到要置换的页面号且将要进入的页换进cout<<"【"<<page_array[i]<<"】号页不在内存中,发生置换算法,并换掉页"<<memory[q]<<endl; change_page[k++]=memory[q]; memory[q]=page_array[i]; } if(in==0&&memory[memory_size-1]==-1)//内存中没有相应的页且内存有空闲页面 { cout<<"【"<<page_array[i]<<"】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:"<<endl; lackTime++; memory[l++]=page_array[i];//将要进入的页调入页面中 } for(intq=0;q<memory_size;q++)//输出每次调页后页面的内容 cout<<memory[q]<<"";cout<<endl; }5结果分析（含实现中出错原因分析）5.1运行结果模拟缺页时的置换算法：请输入给定进程的页数：7输入给该进程分配内存的物理块数（即页面数）3请输入程序访问内存的访问串的长度9请输入数字0或1其中：0.用户自己输入访问串序列1.随机生成访问串序列1随机生成访问的访问串序列为616532505请选择使用那种替换算法：0、退出1、LRU2、随机3、FIFO1LRU分配给此进程的内存页面数为3:当内存中没有调入页时用-1表示-1-1-1缺页产生的序列如下：【6】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:6-1-1【1】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:61-1【6】号页已经存在内存中，此处不用调入，即保持上次调入的状态:61-1【5】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:615【3】号页不在内存中,发生置换算法,并换掉页1635【2】号页不在内存中,发生置换算法,并换掉页6235【5】号页已经存在内存中，此处不用调入，即保持上次调入的状态:235【0】号页不在内存中,发生置换算法,并换掉页3205【5】号页已经存在内存中，此处不用调入，即保持上次调入的状态:205缺页次数：6缺页率：66.6667%命中率：33.3333%淘汰页号：1->6->3->结束LRU以之前的数据继续模拟其他算法（Y/y）？重新输入各项参数模拟（N/n）？退出（y、n之外的任意键）y请选择使用那种替换算法：0、退出1、LRU2、随机3、FIFO2随机淘汰置换算法随即淘汰置换算法步骤:分配给此进程的内存页面数为3:当内存中没有调入页时用-1表示-1-1-1缺页产生的序列如下：【6】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:6-1-1【1】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:61-1【6】号页已经在内存中，不需调入!所以内存中页面内容为：61-1【5】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:615【3】号页不在内存中，所以要发生置换，并换掉页5613【2】号页不在内存中，所以要发生置换，并换掉页3612【5】号页不在内存中，所以要发生置换，并换掉页2615【0】号页不在内存中，所以要发生置换，并换掉页1605【5】号页已经在内存中，不需调入!所以内存中页面内容为：605缺页次数：7缺页率：77.7778%命中率：22.2222%淘汰页号的序列为：5->3->2->1->结束以之前的数据继续模拟其他算法（Y/y）？重新输入各项参数模拟（N/n）？退出（y、n之外的任意键）y请选择使用那种替换算法：0、退出1、LRU2、随机3、FIFO3FIFOFIFO算法步骤:分配给此进程的内存页面数为3:当内存中没有调入页时用-1表示-1-1-1缺页产生的序列如下：【6】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:6-1-1【1】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:61-1【6】号页已经在内存中，不需调入!所以内存中页面内容为：61-1【5】号页不在内存中且内存有空闲页面，不发生置换算法直接调入该页后页面内容如下:615【3】号页不在内存中，所以要发生置换，并换掉页6315【2】号页不在内存中，所以要发生置换，并换掉页1325【5】号页已经在内存中，不需调入!所以内存中页面内容为：325【0】号页不在内存中，所以要发生置换，并换掉页5320【5】号页不在内存中，所以要发生置换，并换掉页3520缺页次数：7缺页率：77.7778%命中率：22.2222%淘汰页号的序列为：6->1->5->3->结束以之前的数据继续模拟其他算法（Y/y）？重新输入各项参数模拟（N/n）？退出（y、n之外的任意键）n模拟缺页时的置换算法：请输入给定进程的页数：7输入给该进程分配内存的物理块数（即页面数）8请输入程序访问内存的访问串的长度9由于