实验六-请求分页存储管理.doc

实验六:请求分页存储管理
一．实验目的
深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的地址变换、缺页中断、置换算法等实现思想。
二．实验属性
该实验为综合性、设计性实验.
三．实验仪器设备及器材
普通PC386以上微机
四．实验要求
本实验要求2学时完成.
本实验要求完成如下任务：
（1） 建立相关的数据结构：页表、页表寄存器、存储块表等；
（2） 指定分配给进程的内存物理块数，设定进程的页面访问顺序；
（3）设计页面置换算法,可以选择OPT、FIFO、LRU等，并计算相应的缺页率，以比较它们的优劣;
（4) 编写地址转换函数，实现通过查找页表完成逻辑地址到物理地址的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU等）完成页面的交换；
（5） 将整个过程可视化显示出来。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告(参见附录A）,并要求用正规的实验报告纸和封面装订整齐，按时上交。
三、设计过程
3。1算法原理分析
OPT算法是未来最远出现，当当前内存中没有正要访问的页面时,置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。
FIFO算法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。
LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。
3.2数据定义
int length，num_page,count，seed; //length记录访问串的长度，num_page页面数，count记录缺页次数
int result[20］［30］，order［30］，a[10］； //result记录结果,order存储访问串,a存储当前页面中的值
int pos1，flag1，flag2，flag3； //pos1位置变量，flag1等为标志变量
char result1［30］; //记录缺页数组void opt() //最佳
void fifo() //先进先出
bool search（int n） //查找当前内存中是否已存在该页
3.3流程图与运行截图
否
是
是
否
开始
得到执行的指令
指令是否在内存中
最先存入指令被淘汰
下面是否还有指令
结束
得出命中率

图6.1 FIFO(）函数流程图；
开始

输入内存中分配页数

据第一个访问页初始化第一列值

还有请求访问页？

直接复制前一列内容

内存中是否已存在？

内存有空页？

直接插入

替换内存中将来不出现或离当前最远的页

输出全部页面变化情况

结束

否
是
否
是
否
是

图2.2 OPT算法流程图
四、小结
本次课程设计目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。要求设计随机页面产生程序，并说明随机的性能和其性能可能对算法的影响，对随机性要有一定的参数控制能力；计算并输出FIFO及LRU算法在不同内存容量下的命中率。
由于上学期做过页面置换的实验,内容包括先进先出算法(FIFO）、最近最久未使用页面置换算法（LRU）和理想淘汰算法（OPT），3种算法思想简单明确，选好数据结构，思路清晰便基本没问题了。所以相对来说，这次操作系统的课程设计容易许多，只是在之前实验基础上，要附加设计随机页面产生程序，对随机性要有一定的参数控制能力。对于随机页面产生程序,我们之前没做过,在网上查阅资料，使用了库函数srand（）和rand()，实现了简单的随机页面产生程序，功能基本完成。我们知识所限，没有使用漂亮可视化界面编程实现功能，用简单的C语言编程实现的.不管怎么样，最终还是实现的本次课程设计要求的。
五、源程序
＃include〈iostream〉
＃include<stdlib.h〉
using namespace std;
int length,num_page,count,seed；
int result［20］［30］，order[30］，a[10］；
int pos1，flag1,flag2，flag3；
char result1[30］；
void init（）
｛ memset(a，—1,sizeof(a））； int i;
cout〈〈”输入访问串的长度:”; cin〉〉length;
cout<<"输入种子数控制产生的随机值：”； cin>〉seed；
srand（seed）; cout<<”产生的随机访问串：";
for(i=0；i<length；i++）
｛ order［i]=rand（)%10；
cout〈〈order［i］〈<” "〈〈endl；
｝
cout<〈”输入页面的个数：”; cin〉〉num_page；
}
void print()
{ int i，j； cout〈〈"表示缺页”<〈endl；
for（ j=0;j<length；j++)
printf（”％2d ”，order［j]）； cout〈〈endl;
for( i=0;i〈num_page；i++）
｛ for( j=0;j〈length;j++）
｛ if(result［i］［j］==—1）
｛ printf（” ”)；
}
else printf（"％2d "，result[i］［j]）;
} cout<<endl；
}
for（ j=0；j〈length；j++）
｛ printf(”％2c ”，result1[j］）；
｝cout<〈endl；
cout<<”缺页率："〈〈count〈〈”/”<<length；
printf（”=％.1lf”，（count＊1.0）/（length*1。0)＊100)；
cout<<"%”<〈endl;
｝
bool search（int n) //查找当期内存是否已存在
｛ int i；
for（i=0；i〈num_page;i++)
｛ if（a［i]==n） return true； ｝
return false;
｝
void opt（) //最佳
{ int i，pos［10］，flag［10］;
while（1） ｛
flag1=flag2=0；
for（i=0；i〈length；i++）
{ if(!search(order［i］）)
｛ count++；
result1［i]='＊’；
if（a［num_page—1］！=-1） //表示当前页面已满要淘汰一个
｛ memset(pos，—1,sizeof（pos））；
memset（flag，0，sizeof（flag));
int j，k;
for( j=i;j〈length；j++)//找出当前页中的值在将来访问串中对应的最近位置
｛ for（ k=0;k〈num_page；k++）
｛ if（order［j]==a［k]＆＆flag［k］==0)
｛ pos［k］=j； flag［k］=1； ｝
｝
｝
cout<〈endl;
int max=—10，max_pos；
for（ k=0；k<num_page;k++）//找出位置最远的那个值
{ if(pos［k］==-1)//未出现则跳出，替换该值
｛ max_pos=k； break； }
else if（max<pos［k］）
{ max=pos[k］; max_pos=k；｝
}
a［max_pos］=order［i];
｝
else //还有空页
｛ for（int j=0;j〈num_page;j++）
｛ if（a［j］==—1）
{ a［j］=order［i]； break；｝
｝
}
｝
else result1［i］=’ ’；
for（int j=0;j〈num_page;j++）
｛ result［j]［i]=a［j］；}
｝
print（);
if（flag1==0＆&flag2==0) break；
}
｝
void fifo（） //先进先出
｛ int i，thisn=0；
while（1）
｛ count=0； flag1=flag2=0；
for(i=pos1；i〈length；i++）
{ if(！search(order［i］））
｛ count++; result1［i］=’＊’；
if(a[num_page-1］!=-1） //表示当前页面已满要淘汰一个
{ a［thisn］= order［i］； thisn++；
if（thisn〉=num_page） thisn=0；
｝
else
｛ for(int j=0；j〈num_page;j++）
｛ if(a［j］==-1）
｛ a[j］=order［i]； break； ｝
}
}
}
else result1[i］=’ ’;
for(int j=0;j〈num_page；j++）
｛ result［j]［i]=a［j］；}
｝
print（）； if(flag1==0＆＆flag2==0) break;
｝
｝
void main（) //主函数
｛
int m；
printf（" 1.OPT。\n”）;
printf(” 2.FIFO。\n”）；
printf（” 0.退出.\n”)；
printf（” 选择所要操作："）;
scanf（”%d”，&m)；
switch（m)
{ case 1: init()； fifo（ ）; main（)； break；
case 2： init（）; lru( ）; main（)； break；
case 0: break；
default： printf（”选择错误，重新选择。”)； main(）;
｝
｝