请求调页存储管理方式的模拟实验报告.docx
《请求调页存储管理方式的模拟实验报告.docx》由会员分享，可在线阅读，更多相关《请求调页存储管理方式的模拟实验报告.docx（20页珍藏版）》请在冰点文库上搜索。
请求调页存储管理方式的模拟实验报告
《网络操作系统》
课程设计报告书
目:
请求调页存储管理方式的模拟题学号:
学生姓名:
指导教师:
2010年12月9日目录
一.实验内容.................................................错误
～未定义书签。
1二.实验目
的.................................................错误～未定义书签。
1
三.设计思想.................................................错误～未
定义书签。
2四.程序流程
图...............................................错误～未定义书签。
3
五.程序清单.................................................错误～未
定义书签。
4六.运行结果及分析
错误～未定义书签。
10七.总
结 错误～未定义书
签。
14
一、实验内容
1（假设每个页面中可存放10条指令，分配给作业的内存块数为4。
2（用C语言或C++语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。
在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。
如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。
如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。
在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
3（置换算法:
请分别考虑最佳置换算法（OPT）、先进先出（FIFO）算法和最近最久
未使用（LRU）算法。
4（作业中指令的访问次序按下述原则生成;
50%的指令是顺序执行的;
25%的指令是均匀分布在前地址部分;
25%的指令均匀分布在后地址部分。
具体的实现办法是:
（1）在[0，319]之间随机选取一条起始执行指令，其序号为m;
（2）顺序执行下一条指令，其序号为m+1条指令;
（3）通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1;（4）顺序执行下一条指令，即序号为m1+1的指令;
（5）通过随机数，跳转到后地址部分[m1+2,319]中的某条指令处，其序号为m2;（6）顺序执行下一条指令，则序号为m2+1的指令;
（7）重复跳转到前地址部分，顺序执行，跳转到后地址部分;顺序执行的过程，直至执行320条指令。
二、实验目的
1（通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。
2（通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实
现过程的理解。
3（掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比
较它们的效率。
三、设计思想
在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。
但应将哪个页面调出，所以需要根据一定的算法来确定。
在这一过程中，选择换出页面的算法称为页面置换算法。
一个好的页面置换算法，应具有较低的页面更换频率。
页面置换算法的好坏，将直接影响到系统的性能。
以下分别是实验要求的两个页面置换算法的介
绍及设计思想。
（1）先进先出法（FirstInFirstOut）:
该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。
在该算法的模拟过程中，每当页面被置换进入内存时，将置换页面所在的物理块中访问标记设为-1;并且每执行一次指令，便将物理块的访问标记自动加1，需要置换时将访问标记最大的物理块中的页面置换出去，这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法;
（2）最近最久未使用（LeastRecentlyUsed）:
该算法以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。
在该算法的模拟过程中，每当物理块中的页面被访问时（包括原先存在的和后来置换进入的页面），便将其物理块访问标记置为,1。
以后每执行一条指令，便将物理块中各页面的访问标记加1，需置换时访问标记最大的便是将要被置换的。
（3）最佳置换算法（OPT）:
发生缺页时，有些页面在内存中，其中有一页见很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。
最佳页面置换算法只是简单地规定:
标记最大的页应该被置换。
如果某页在八百万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面，从而把因需要调回这一页发生的缺页推到将来，越远越好。
这个算法唯一的一个问题就是它无法实现。
当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。
虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。
四、程序流程图及数据结构内存物理块320条待执行指令
输入一个随机数1-319
显示随机产生的指令执行顺序和页面的调用顺序选择调页存储算法
OPTLRU算法FIFO算法程序结束
数据结构:
typedefstructBLOCK//声明一种新类型——物理块类型{intpagenum;//页号
intaccessed;//访问字段，其值表示多久未被访问
}BLOCK;
intcount;//程序计数器，用来记录指令的序号intn;//缺页计数器，用来记录缺页的次数
staticinttemp[320];//用来存储320条随机数
BLOCKblock[size];//定义一大小为4的物理块数组voidinit（）;//程序初始化函数
intfindExist（intcurpage）;//查找物理块中是否有该页面intfindSpace（）;//查找是否有空闲物理块
intfindReplace（）;//查找应予置换的页面voiddisplay（）;//显示
voidRandom（）;//产生320条随机数,显示并存储到temp[320]voidpagestring（）;//显示调用的页面队列
voidOPT（）;//OPT算法voidLRU（）;//LRU算法voidFIFO（）;//FIFO算法
五、程序清单#include#include#include
#include#definesize4
typedefstructBLOCK//声明一种新类型——物理块类型{
intpagenum;//页号
intaccessed;//访问字段，其值表示多久未被访问
}BLOCK;
intcount;//程序计数器，用来记录指令的序号intn;//缺页计数器，用来记录缺页的次数staticinttemp[320];//用来存储320条随机数BLOCKblock[size];//定义一大小为4的物理块数组voidinit（）;//程序初始化函数
intfindExist（intcurpage）;//查找物理块中是否有该页面intfindSpace（）;//查找是否有空闲物理块intfindReplace（）;//查找应予置换的页面voiddisplay（）;//显示
voidRandom（）;//产生320条随机数,显示并存储到temp[320]voidpagestring（）;//显示调用的页面队列
voidOPT（）;//OPT算法voidLRU（）;//LRU算法voidFIFO（）;//FIFO算法voidinit（）
{
for（inti=0;i{
block[i].pagenum=-1;block[i].accessed=0;count=n=0;
}
}
intfindExist（intcurpage）//查找物理块中是否有该页面{
for（inti=0;i{
if（block[i].pagenum==curpage）
returni;//检测到内存中有该页面，返回block中的位置
}
return-1;
}
intfindSpace（）//查找是否有空闲物理块
{
for（inti=0;i{
if（block[i].pagenum==-1）
returni;//找到空闲的block，返回block中的位置
}
return-1;
}
intfindReplace（）//查找应予置换的页面
{
intpos=0;
for（inti=0;i{
if（block[i].accessed>block[pos].accessed）pos=i;//找到应予置换页面，返回BLOCK中位置
}
returnpos;
}
voiddisplay（）
{
for（inti=0;i{
if（block[i].pagenum!
=-1）//物理块不空
{
printf（"%02d",block[i].pagenum）;
}
}cout<}
voidRandom（）
{intflag=0;cin>>count;
cout<<"******按照要求产生的320个随机数:
*******"<{temp[i]=count;
if（flag%2==0）count=++count%320;//产生50%的顺序执行指令（flag=0或2时
顺
序执行）
if（flag==1）count=rand（）%（count-1）;//产生25%的均匀分布在前地址部分指
令
if（flag==3）count=count+1+（rand（）%（320-（count+1）））;//产生25%的均匀分布在后地址部分指令
flag=++flag%4;
printf（"%03d",temp[i]）;if（（i+1）%10==0）cout<}
}
voidpagestring（）//显示调用的页面队列
{
for（inti=0;i<320;i++）
{
printf（"%02d",temp[i]/10）;if（（i+1）%10==0）cout<}
}
// 最佳置换算法voidOPT（）
{
intexist,space,position;intcurpage;
for（inti=0;i<320;i++）
{
if（i%100==0）getch（）;count=temp[i];curpage=count/10;
exist=findExist（curpage）;if（exist==-1）
{
space=findSpace（）;if（space!
=-1）
{
block[space].pagenum=curpage;display（）;
n=n+1;
}else
{
for（intk=0;k{
for（intj=i;j<320;j++）
{
if（block[k].pagenum!
=temp[j]/10）
{
block[k].accessed=1000;
}//将来不会用，设置为一个很大数
else
{
block[k].accessed=j;break;
}
}
}
position=findReplace（）;block[position].pagenum=curpage;display（）;
n++;
}
}
}
cout<<"缺页次数:
"<cout<<"缺页率:
"<<（n/320.0）*100<<"%"<}
// 最近最少使用算法voidLRU（）{intexist,space,position;
intcurpage;
for（inti=0;i<320;i++）
{
if（i%100==0）getch（）;//getch直接从键盘获取键值count=temp[i];//指令在数组中的位置
curpage=count/10;//指令所在页面
exist=findExist（curpage）;//查找物理块中是否有该页面,若有返回物理块号
if（exist==-1）//物理块中不存在该页
{
space=findSpace（）;//查找是否有空闲物理块if（space!
=-1）//有空闲物理块
{
block[space].pagenum=curpage;display（）;
n=n+1;
}
else//无空闲物理块，则寻找置换页面
{
position=findReplace（）;//查找应予置换的页面block[position].pagenum=curpage;
block[position].accessed=-1;//恢复刚调入的BLOCK中页面accessed为
-1
display（）;n++;
}
}
elseblock[exist].accessed=-1;//恢复存在的并刚访问过的BLOCK中页面
accessed为-1
for（intj=0;j<4;j++）
{block[j].accessed++;}
}
cout<<"缺页次数:
"<cout<<"缺页率:
"<<（n/320.0）*100<<"%"<//--- 先进先出算法voidFIFO（）
{
intexist,space,position;intcurpage;
for（inti=0;i<320;i++）
{
if（i%100==0）getch（）;//getch直接从键盘获取键值count=temp[i];
curpage=count/10;
exist=findExist（curpage）;//查找物理块中是否有该页面if（exist==-1）
{
space=findSpace（）;//查找是否有空闲物理块if（space!
=-1）//有空闲物理块
{
block[space].pagenum=curpage;display（）;
n=n+1;
}
else//无空闲物理块，则寻找置换页面
{
position=findReplace（）;//查找应予置换的页面block[position].pagenum=curpage;
display（）;n++;
block[position].accessed--;//置换页面所在的物理块中访问标记设为-1
}
}
else//若存在该页
{
for（inti=0;i{if（block[i].pagenum!
=-1）//物理块不空printf（"%02d",block[i].pagenum）;
}
cout<<"指令已经存在!
其物理块地址为:
"<<&block[exist]<}
for（intj=0;j}
cout<<"缺页次数:
"<cout<<"缺页率:
"<<（n/320.0）*100<<"%"<{
intselect;
cout<<"请输入第一条指令号（1~320）:
";Random（）;
cout<<"*****对应的调用页面队列*******"<do
{cout<<"****************************************"<OPT2:
LRU3:
FIFO4:
退出*"<";
cin>>select;cout<<"****************************************"<switch（select）
{
case1:
cout<<"最佳置换算法OPT:
"<OPT（）;break;
case2:
cout<<"最近最久未使用置换算法LRU:
"<LRU（）;
break;
case3:
cout<<"先进先出置换算法FIFO:
"<FIFO（）;break;default:
;
}
}while（select!
=4）;
}
六、使用说明及运行结果分析运行程序依次测试相应的算法:
1、先输入一个指令号（1-319）随意输入;
2、然后选择测试算法;
本程序能通过输入第一条指令号（用3位整数代表指令号），产生320个随机
数，并以每行10个显示出来。
再把这320个随机数转换成对应的页面号，并以每
行10个显示出来。
然后，通过输入选择键，分别执行两个置换算法。
各个置换算法能显示页面置换的情况，如果所访问的指令已在内存，则显示“该指令已经存在”并显示其物理地址;如果所访问的指令还未装入内存，则显示“调入的页面
是。
。
。
”，并显示其调入后的物理地址。
所有指令执行完毕后显示缺页次数，和缺页率。
基本实现了对请求调页存储器管理方式的模拟。
本程序的另一个亮点是使用getch（）使程序的执行过程能够暂停。
本程序基本实现了实验要求，但是仍有一定的不足之处。
七、总结
通过本次操作系统实验，使我们对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
本实验的难点之一在于如何用c语言按要求模拟生成随机指令，即50%的指令是顺序执行的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分，小组花了大量时间讨论和研究该算法，并参考了相关的资料、运用了随机函数，最终通过一个函数Random（）予以实现。
第二，如何较好地模拟出先进先出算法（FIFO）、最近最少使用算法（LRU）也花费了较多时间。
在本次设计过程中，用到了许多C++的基本知识和操作系统的基本原理，是对平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。
在设计的过程中我们发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。
总之，通过该实验，使我学到很多知识以及认识到实践的重要性。
也使我了解到编写程序不是首要任务，而是一种实现手段。
我们最重要的是如何做好需求分析和理清思路，做出正确、简洁的流程设计，这样可以达到事半功倍的效果。
教师评语成绩:
年月日
升级会员 