实验报告书.docx
《实验报告书.docx》由会员分享，可在线阅读，更多相关《实验报告书.docx（15页珍藏版）》请在冰点文库上搜索。
实验报告书
实验报告书
学生姓名张伟
学号11101020228
班级计11-2
2013—2014学年第一学期
《计算机操作系统》实验报告
实验名称
存储管理实验
实验序号
2
实验日期
2013.11-2013.12
实验人
张伟
一、实验目的和要求
1．实验目的
请求页式存储管理是一种常用的虚拟存储管理技术。
本实验目的是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
2．实验要求及考核
（1）实验课与正常上课一样，要求按时出勤。
（2）实验须独立完成，可以查阅各种资料。
（3）实验完毕要求提交纸质实验报告，报告格式参照所提供的模板。
（4）本次实验的验机时间为13周周三，实验报告应在13周周三统一提交。
（5）实验成绩由平时出勤、验机情况和实验报告三部分构成。
二、相关背景知识
1．请求页式管理
Linux系统中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。
这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：
页表、页帧（框）号、访问位、修改位、有效位、保护位等。
页表：
表2-1页表
流程图：
图2-1流程图
中断位和外存始址用于标识出所缺页在外存的地址，改变位标识该页在内存时是否被修改过。
2．请求页式管理中的置换算法（主要介绍本次试验中的两种）
（1）先进先出页面淘汰算法（FIFO）
FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。
实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。
这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。
Belady现象:
一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。
在极限情况下，这个推论是成立的。
因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。
但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。
这种现象称为Belady现象。
（2）最近最久未使用页面淘汰法（LRU）
选择内存中最久未使用的页面被置换。
这是局部性原理的合理近似，性能接近最佳算法。
但由于需要记录页面使用时间的先后关系，硬件开销太大。
硬件机构如：
A．一个特殊的栈：
把被访问的页面移到栈顶，于是栈底的是最久未使用页面。
B．每个页面设立移位寄存器：
被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。
3.随机数产生办法
关于随机数产生办法，Linux或UNIX系统提供函数srand（）和rand（），分别进行初始化和产生随机数。
例如：
srand（）;
语句可初始化一个随机数；
a[0]=10*rand（）/65535*319+1;
a[1]=10*rand（）/65535*a[0];
语句可用来产生a[0]与a[1]中的随机数。
三、实验内容
1．通过随机数产生一个指令序列，共320条指令。
指令的地址按下述原则生成：
（1）50%的指令是顺序执行的；
（2）25%的指令是均匀分布在前地址部分；
（3）25%的指令是均匀分布在后地址部分；
具体的实施方法是：
（1）在[0，319]的指令地址之间随机选取一起点m；
（2）顺序执行一条指令，即执行地址为m+1的指令；
（3）在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；
（4）顺序执行一条指令，其地址为m’+1；
（5）在后地址[m’+2,319]中随机选取一条指令并执行；
（6）重复上述步骤1~5，直到执行320次指令。
2．将指令序列变换成页地址流，设
（1）页面大小为1K；
（2）用户内存容量为4页到32页；
（3）用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中存放的方式为：
第0条至第9条指令为第0页（对应虚存地址为[0，9]）；
第10条至第19条指令为第1页（对应虚存地址为[10，19]）；
……
第310条至第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可以组成32页。
3．计算并输出下述各种算法在不同内存容量下的命中率。
（1）先进先出页面淘汰算法（FIFO）
（2）最近最久未使用页面淘汰法（LRU）
命中率=1-页面失效次数/页地址流长度
在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。
四、关键数据结构与函数的说明
1．srand（）与rand（）
函数rand（）是真正的随机数生成器，而srand（）会设置供rand（）使用的随机数种子。
如果你在第一次调用rand（）之前没有调用srand（），那么系统会为你自动调用srand（）。
而使用同种子相同的数调用srand（）会导致相同的随机数序列被生成。
srand（（unsigned）time（NULL））则使用系统定时/计数器的值做为随机种子。
每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同的，相应的，若将srand（unsigned）time（NULL）改为srand（TP）（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。
库函数中系统提供了两个函数用于产生随机数：
srand（）和rand（）。
原型为：
函数一：
intrand（void）；
从srand（seed）中指定的seed开始，返回一个[seed,RAND_MAX（0x7fff）]间的随机整数。
函数二：
voidsrand（unsignedseed）；
参数seed是rand（）的种子，用来初始化rand（）的起始值。
但是，要注意的是所谓的“伪随机数”指的并不是假的随机数。
其实绝对的随机数只是一种理想状态的随机数，计算机只能生成相对的随机数即伪随机数。
计算机生成的伪随机数既是随机的又是有规律的：
一部份遵守一定的规律，一部份则不遵守任何规律。
比如“世上没有两片形状完全相同的树叶”，这体现到了事物的特性：
差异性；但是每种树的叶子都有近似的形状，这正是事物的共性：
规律性。
从这个角度讲，我们就可以接受这样的事实了：
计算机只能产生伪随机数而不是绝对的随机数。
系统在调用rand（）之前都会自动调用srand（），如果用户在rand（）之前曾调用过srand（）给参数seed指定了一个值，那么rand（）就会将seed的值作为产生伪随机数的初始值；而如果用户在rand（）前没有调用过srand（），那么系统默认将1作为伪随机数的初始值。
如果给了一个定值，那么每次rand（）产生的随机数序列都是一样的。
所以为了避免上述情况的发生我们通常用srand（（unsigned）time（0））或者srand（（unsigned）time（NULL））来产生种子。
如果仍然觉得时间间隔太小，可以在（unsigned）time（0）或者（unsigned）time（NULL）后面乘上某个合适的整数。
例如,srand（（unsigned）time（NULL）*10）
另外，关于time_ttime（0）：
time_t被定义为长整型，它返回从1970年1月1日零时零分零秒到目前为止所经过的时间，单位为秒。
2．定义结构体
typedefstruct//页面结构
{
intpn,//页面序号
pfn,//页面所在内存区的帧号
time;//上次访问的时间
}pl_type;
structpfc_struct
{//页面控制结构
intpn,//页面号
pfn;//内存区页面的帧号
structpfc_struct*next;//页面指针，用于维护内存缓冲区的链式结构
};
typedefstructpfc_structpfc_type;//主存区页面控制结构别名
3．定义常量、变量
#definetotals320//指令流长
#definetotal_page32//虚页长
pl_typepl[total_page];//页面结构数组
pfc_typepfc[total_page],//主存区页面控制结构数组
*free_head;//主存区页面控制结构的空闲页面头指针
intdiseffect;//页错误计数器，初次把页面载入主存时也当做页错误
inta[totals];//随即指令流数组
intpage[totals];//指令对应的页面号
intoffset[totals];//指令所在页面中的偏移量
4．功能函数声明
intinitialize（int）;//初始化页面结构数组和页面控制结构数组
intFIFO（int）;//先进先出算法
intLRU（int）;//最近最久未使用算法
五、编译与执行过程截图
执行后出现了随机指令序列，总共320条指令，如图5-1所示。
图5-1
然后调用FIFO函数与LRU函数计算命中率，显示其结果，如图5-2所示。
图5-2
六、实验结果与分析
结果：
由执行现象可得知，增加作业的内存块数，可以降低缺页率，对于不同的算法，增加物理块数都能降低缺页率，只是效果有所不同。
理论上，LRU具有比FIFO更好的性能，可是实验中在内存块数量相对少时，现象反应FIFO的性能比LRU好，当内存块数量越来越多时，LRU性能明显比FIFO更好。
分析：
指令流的产生方式要能体现局部性原理，本实验中指令流设计方式能否最佳地体现局部性原理，还有待验证，并且指令的数量相对较少。
一般情况下，LRU具有比FIFO更好的性能。
FIFO置换算法设计简单，容易理解。
但它的效率并不是总能达到令人满意的效果。
这种算法只有在顺序访问地址空间时才能达到理想效果，但根据程序的局部性原理，那些常被访问的页面，往往要在主存中停留得最久，FIFO算法却将会将其换出页面，留下的只是一些新调入的指令，这将导致内存频繁换页。
而LRU则选择在最近一段时间里最久没有使用过的页面予以置换，LRU算法是与每个页面最后使用的时间有关的。
当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
这种算法以“最近的过去”作为“最近的将来”的近似，较好地利用了程序的局部性原理。
一般情况下，能取得较好的效果，是经常采用的页面置换算法。
七、调试时遇到的问题及解决方法（提供BUG截屏）
1．指针赋值时出错。
解决办法：
程序中定义的指针变量子在赋值时取得是地址，故需要加上取地址符“&”。
2．结果未达到预定效果，不正确，如图7-1，32page时命中率>0.9。
图7-1
解决办法：
在LRU算法中，CurrentTime应该自增，可是在代码中并没有，加上CurrentTime++，而且在FIFO算法中，指针的调用出现了问题，修改赋值即可。
八、调试后的程序源代码
#include
#include
#include//在window操作系统下要屏蔽此条指令
#include
#ifndef_UNISTD_H
#define_UNISTD_H
#include
#include
#endif
#definetotals320//指令流长
#definetotal_page32//虚页长
typedefstruct//页面结构
{
intpn,//页面序号
pfn,//页面所在内存区的帧号
time;//上次访问的时间
}pl_type;
pl_typepl[total_page];//页面结构数组
structpfc_struct{//页面控制结构
intpn,//页面号
pfn;//内存区页面的帧号
structpfc_struct*next;//页面指针，用于维护内存缓冲区的链式结构
};
typedefstructpfc_structpfc_type;//主存区页面控制结构别名
pfc_typepfc[total_page],//主存区页面控制结构数组
*free_head;//主存区页面控制结构的空闲页面头指针
intdiseffect;//页错误计数器，初次把页面载入主存时也当做页错误
inta[totals];//随即指令流数组
intpage[totals];//指令对应的页面号
intoffset[totals];//指令所在页面中的偏移量
intinitialize（int）;//初始化页面结构数组和页面控制结构数组
intFIFO（int）;//先进先出算法
intLRU（int）;//最近最久未使用算法
intmain（）
{
ints;//随机数
inti;
srand（10*getpid（））;//每次运行时进程号不同，用来作为初始化随机数队列的"种子"
s=（int）（（float）（totals-1）*（rand（）/（RAND_MAX+1.0）））;
printf（"\n----------------Randing---------------\n"）;
for（i=0;i{
a[i]=s;//任选一指令访问点m
a[i+1]=a[i]+1;//顺序执行一条指令
a[i+2]=（int）（（float）a[i]*（rand（）/（RAND_MAX+1.0）））;//执行前地址指令m'
a[i+3]=a[i+2]+1;//顺序执行一条指令
printf（"%6d%6d%6d%6d\n",a[i],a[i+1],a[i+2],a[i+3]）;
s=（int）（（float）（（totals-1）-a[i+2]）*（rand（）/（RAND_MAX+1.0）））+a[i+2];
}
printf（"--------------------------------------\n"）;
for（i=0;i{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
printf（"\n---------------DisplayingHit-----------\n"）;
printf（"Page\tFIFO\tLRU\n"）;
for（i=4;i<=32;i++）//用户内存工作区从个页面到个页面
{
printf（"%2d\t",i）;
FIFO（i）;
LRU（i）;
printf（"\n"）;
}
return0;
}
//初始化页面结构数组和页面控制结构数组
intinitialize（inttotal_pf）
{
inti;
diseffect=0;
for（i=0;i{
pl[i].pn=i;
pl[i].pfn=-1;//置页面所在主存区的帧号为-1.表示该页不在主存中
pl[i].time=-1;//置页面结构中的上次访问的时间为-1
}
for（i=0;i{
pfc[i].next=&pfc[i+1];//建立pfc[i-1]和pfc[i]之间的链接
pfc[i].pfn=i;//初始化主存区页面的帧号
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
free_head=&pfc[0];//主存区页面控制结构的空闲页面头指针指向pfc[0]
return0;
}
//先进先出算法版本
intFIFO（inttotal_pf）
{
inti;
intuse[total_page];
intswap=0;
initialize（total_pf）;
pfc_type*pnext,*head;
pnext=free_head;
head=free_head;
for（i=0;idiseffect=0;
for（i=0;i{
if（pl[page[i]].pfn==-1）//页面失效,不在主存中
{
diseffect++;
if（free_head==NULL）//无空闲页面
{
while（use[pnext->pfn]==1）
{
use[pnext->pfn]=0;
pnext=pnext->next;
if（pnext==NULL）pnext=head;
}
//换出被替换的页
pl[pnext->pn].pfn=-1;
swap=1;
}
if（use[pnext->pfn]==0）//如果使用位为0，则换入相应的页
{
pl[page[i]].pfn=pnext->pfn;//页面结构中要标记帧号
pnext->pn=page[i];//页面控制结构中要标记页号
use[pnext->pfn]=1;//重置使用位为
pnext=pnext->next;
if（pnext==NULL）pnext=head;
if（swap==0）{free_head=free_head->next;}
}
}
}
printf（"%6.3f\t",1-（float）diseffect/320）;
return0;
}
//最近最久未使用算法
intLRU（inttotal_pf）
{
intMinT;//最小的访问时间，即很久没被访问过
intMinPn;//拥有最小的访问时间的页的页号
inti,j;
intCurrentTime;//系统当前时间
initialize（total_pf）;//初始化页面结构数组和页面控制结构数组
CurrentTime=0;
diseffect=0;
for（i=0;i{
if（pl[page[i]].pfn==-1）//页面失效
{
diseffect++;//页错误次数加
if（free_head==NULL）//无空闲页面
{
MinT=100000;
for（j=0;j{//找出time的最小值，表明该页很久没被访问过
if（MinT>pl[j].time&&pl[j].pfn!
=-1）
{
MinT=pl[j].time;
MinPn=j;
}
}
free_head=&pfc[pl[MinPn].pfn];//最久没被访问过的页被释放
pl[MinPn].pfn=-1;//最久没被访问过的页被换出主存
pl[MinPn].time=-1;//最久没被访问过的页的访问时间置为无效
free_head->next=NULL;
}
pl[page[i]].pfn=free_head->pfn;
//有空闲页面,把相应的页面换入主存，并把pfn改为相应的帧号
pl[page[i]].time=CurrentTime;//令访问时间为当前系统时间
free_head=free_head->next;//减少一个空闲页面
}
else
pl[page[i]].time=CurrentTime;//命中则刷新该单元的访问时间
CurrentTime++;//系统当前时间加
}
printf（"%6.3f\t",1-（float）diseffect/320）;
return0;
}
九、实验体会
1．通过本次操作系统存储实验，使我对操作系统这门课程有了更进一步的认识和了解，通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
2．在本次实验过程中，用到了许多C语言的基本知识和操作系统的基本原理，是对平时所学知识的一次考验，尽管这些知识都学过，但运用到实际时，却不知从何下手，而且错误不断，往往为了找一个错误而花了大量的时间，这是专业知识掌握不够，缺乏实践动手能力的表现。
通过不断的纠正错误，上网查找相关资料，以及请教老师，终于完成了本次实验。
在实验的过程中我发现了许多自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，以后还要多加努力。
升级会员 