湖南大学操作系统实验报告3.docx
《湖南大学操作系统实验报告3.docx》由会员分享，可在线阅读，更多相关《湖南大学操作系统实验报告3.docx（16页珍藏版）》请在冰点文库上搜索。
湖南大学操作系统实验报告3
实验三内存页面置换算法的设计
一、实习内容
实现最近最久未使用（LRU）置换算法
二、实习目的
LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分（段或页）调入内存便可运行，还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。
这种页面调入方式叫请求调页。
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。
该程序通过查找页表，得到该页所在外存的物理块号。
如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。
如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。
利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。
整个页面的调入过程对用户是透明的。
本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。
三、实习题目
实现最近最久未使用（LRU）置换算法
[提示]：
（1）最近最久未使用（LRU）置换算法原理就是：
当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。
例如:
分配给该进程的页块数为3，一个20位长的页面访问序列为:
12560,36536,56042,70435，则缺页次数和缺页率按表3-1给出:
缺页次数:
15
缺页率:
15/20=0.75
（2）假定分配给该进程的页块数为3，页面访问序列长度为20。
本实验可以采用数组
结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。
模拟程序的算法如图3-2。
四、源程序及程序中使用的数据结构、符号说明
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
voidshowState（intpage[][20],intvisit[][2],intt）;
intpick（intpage[][20],intvisit[][2],inttime,intuseTime[]）;
intmin（inta,intb,intc）;
intmain（）{
srand（time（NULL））;
intvisit[20][2];
memset（visit,-1,sizeof（visit））;
for（inti=0;i<20;i++）
visit[i][0]=rand（）%8;
cout<<"20位长的随机访问序列为:
"<for（inti=0;i<20;i++）
cout<（2）<cout<intpage[3][20];
memset（page,-1,sizeof（page））;
intuseTime[3];
memset（useTime,0,sizeof（useTime））;
for（intt=0;t<20;t++）{
intp=pick（page,visit,t,useTime）;//选中的页
if（p<0）{//命中第p+3页，设置此页命中，帧内容不变
visit[t][1]=1;
for（intx=0;x<3;x++）
page[x][t]=page[x][t-1];
useTime[p+3]=t;
}
else{//此页不命中，帧内容替换
visit[t][1]=0;
if（t==0）{
page[p][t]=visit[t][0];
}
else{
for（inty=0;y<3;y++）
page[y][t]=page[y][t-1];
page[p][t]=visit[t][0];
}
useTime[p]=t;
}
showState（page,visit,t）;
}
intmiss=0;
for（inti=0;i<20;i++）{
if（visit[i][1]==0）miss++;
}
doubleper=1-（double）miss/20;
intperi=per*100;
cout<<"共miss"<return0;
}
intpick（intpage[][20],intvisit[][2],inttime,intuseTime[]）{
//如果命中了，就返回下标-3，比如如果0帧命中，返回-3
//如果不命中，选择一个最久没有访问到的帧，返回帧下标
cout<<"输出usetime:
";
cout<for（inti=0;i<3;i++）{//先遍历一遍，看有没有命中的
if（page[i][time-1]==visit[time][0]）{
cout<<"time"<returni-3;
}
}
for（inti=0;i<3;i++）{//不存在命中，则从头开始选，先选帧空的情况
if（page[i][time-1]==-1）{
cout<<"time"<returni;
}
}
//都没有，就选最久没用过的
intm=min（useTime[0],useTime[1],useTime[2]）;
cout<<"time"<returnm;
}
voidshowState（intpage[][20],intvisit[][2],intt）{
cout<cout<<"时间";
for（inti=0;i<20;i++）
cout<cout<cout<<"序列";
for（inti=0;i<20;i++）{
cout<}
cout<cout<<"零帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"一帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"二帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"命中";
stringstr1="√";
stringstr2="×";
for（inti=0;i<=t;i++）{
stringx=（visit[i][1]==1）?
str1:
str2;
cout<}
cout<}
intmin（inta,intb,intc）
{
if（a<=b&a<=c）return0;
if（bif（c}
代码详细说明：
在本例中，我设定了页面调度页块数为3，要访问的页面序列长度为20.从随机数获取20个访问的页面后进行页面调度算法，并将每次调度完的结果打印到控制台面板上，页面调度的具体算法为：
维护一个useTime数组，其中存储着三个页块的上次使用时间，在每次向页块中调度内容/页块或页面访问命中页块时，更新被访问的页块的使用时间，如果页面访问不命中页块时，则选择useTime数组中最小的那一块，即最久没使用的页块，置换其中的内容。
下面是针对代码的说明：
srand（time（NULL））;
intvisit[20][2];
memset（visit,-1,sizeof（visit））;
for（inti=0;i<20;i++）
visit[i][0]=rand（）%8;
intpage[3][20];
memset（page,-1,sizeof（page））;
intuseTime[3];
memset（useTime,0,sizeof（useTime））;
以上几行代码的作用为生成一个随机的20位的页面访问序列，由于对8作了取余操作，所以生成的访问序列下标为0-7，并存储在visit数组的第0位中，且在visit数组的第1位中赋值-1。
同时生成page数组以实现对3个页块的随时间变化的追踪，维护useTime数组以保存3个页块的上次使用时间。
下面介绍代码的调度实现部分
intpick（intpage[][20],intvisit[][2],inttime,intuseTime[]）{
//如果命中了，就返回下标-3，比如如果0帧命中，返回-3
//如果不命中，选择一个最久没有访问到的帧，返回帧下标
cout<<"输出usetime:
";
cout<for（inti=0;i<3;i++）{//先遍历一遍，看有没有命中的
if（page[i][time-1]==visit[time][0]）{
cout<<"time"<returni-3;
}
}
for（inti=0;i<3;i++）{//不存在命中，则从头开始选，先选帧空的情况
if（page[i][time-1]==-1）{
cout<<"time"<returni;
}
}
//都没有，就选最久没用过的
intm=min（useTime[0],useTime[1],useTime[2]）;
cout<<"time"<returnm;
}
Pick函数传入的参数为page数组，visit数组，当前时间t和useTime数组，它会首先检查下一时刻的访问内容visit[t][0]是否出现在上一时刻的三个页块中，如果出现，则返回值为【块数-3】，以区别于调度的返回值。
如果下一时刻的访问没有出现在上一时刻的页块中，则对于下一时刻的访问，要首先判断是否有空块，即页块内容为-1的情况，如果有页块为空，则选择页号最小的页块，将要访问的内容置入该块。
如果以上情况均没有出现，则选择useTime中最小的那一块，替换该块中的内容。
该函数在main函数中的调用为：
for（intt=0;t<20;t++）{
intp=pick（page,visit,t,useTime）;//选中的页
if（p<0）{//命中第p+3页，设置此页命中，帧内容不变
visit[t][1]=1;
for（intx=0;x<3;x++）
page[x][t]=page[x][t-1];
useTime[p+3]=t;
}
else{//此页不命中，帧内容替换
visit[t][1]=0;
if（t==0）{
page[p][t]=visit[t][0];
}
else{
for（inty=0;y<3;y++）
page[y][t]=page[y][t-1];
page[p][t]=visit[t][0];
}
useTime[p]=t;
}
showState（page,visit,t）;
}
分别对于页面命中的情况和不命中的情况设置对应的输出，并更新页面的useTime数组，并在最后调用showState（page,visit,t）;函数来展示实时的页面内容
showState（page,visit,t）;函数的定义如下：
voidshowState（intpage[][20],intvisit[][2],intt）{
cout<cout<<"时间";
for（inti=0;i<20;i++）
cout<cout<cout<<"序列";
for（inti=0;i<20;i++）{
cout<}
cout<cout<<"零帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"一帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"二帧";
for（inti=0;i<=t;i++）{
cout<}
cout<cout<<"命中";
stringstr1="√";
stringstr2="×";
for（inti=0;i<=t;i++）{
stringx=（visit[i][1]==1）?
str1:
str2;
cout<}
cout<}
由于展示部分的代码较为简单，只是对于数组的输入输出，就不做赘述了。
最后，遍历一次page数组，求出总的缺页次数和缺页率。
intmiss=0;
for（inti=0;i<20;i++）{
if（visit[i][1]==0）miss++;
}
doubleper=1-（double）miss/20;
intperi=per*100;
cout<<"共miss"<以上为LRU调度算法的全部内容。
五、打印程序运行时的初值和运行结果
运行环境：
DevC++5.11
控制台运行结果：
由于内容较多，我将截取最后一帧作详细说明：
在本例中，随机生成的访问序列为（1，1，4，0，6，0，4，5，3，6，2，0，7，0，2，0，0，4，0，2）
在0时刻，三个页块均空，所以此时调度页面1进入第一个空块，此次访问不命中。
在1时刻，由于要访问的页面1命中第一块中的内容，所以此次访问命中，在2时刻，此次要访问的页面4不命中，所以选择调度进入第二个空块中，在3时刻，此次要访问的页面0不命中，所以选择调度进入第三个空块中，此时已经没有空块可以调度，所以后续的调度只会根据useTime数组的值来完成调度。
接下来的每次调度都是根据当前页判断，如果命中则不做更新，如果不命中，则选择一块最久没有使用的（即useTime数组内容最小的块）替换其中内容。
最后根据page数组的内容求得其总miss次数为11次，命中率为44%。
六实验心得
这是本学期的最后一次操作系统实验，我选择的这个实验应该来说还是较为简单的，因为LRU算法的复杂性不是很高，在编写代码的过程中也出现了一些问题，但是经过自己的思考也都能顺利的解决。
马上要期末考试了，自己应该在深入理解几次试验内容的基础上加以深入的复习，争取期末考个好成绩。
升级会员 