第7次常用页面置换算法模拟实验.docx
《第7次常用页面置换算法模拟实验.docx》由会员分享,可在线阅读,更多相关《第7次常用页面置换算法模拟实验.docx(20页珍藏版)》请在冰点文库上搜索。
![第7次常用页面置换算法模拟实验.docx](https://file1.bingdoc.com/fileroot1/2023-5/5/2bd0daf3-6d6b-4ac4-948c-b0bf801301e3/2bd0daf3-6d6b-4ac4-948c-b0bf801301e31.gif)
第7次常用页面置换算法模拟实验
操作系统课程实验报告
姓名
学号
系
计算机科学与技术
任课教师
贺辉
指导教师
贺辉
评阅教师
贺辉
实验地点
实验时间
实验编号与实验名称:
第7次常用页面置换算法模拟实验
实验目的:
通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
实验内容及要求(详见实验讲义):
实验要求:
1)要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序;要求在主函数中测试。
2)实验报告中必须包括:
设计思想、数据定义(包括详细说明)、处理流程(详细算法描述和算法流程图)、源代码、运行结果、体会等部分。
3)必须模拟本实验内容中提到的算法中的至少2种页面置换算法。
4)比较不同页面置换算法的效率
实验内容
编写一个程序,使用以下页面置换算法中的某2种分别模拟一个分页系统,并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。
1、第二次机会算法(SecondChance)
2、最近最少使用算法(LeastRecentlyUsed,LRU)
3、最不常用算法(NotFrequentlyUsed,NFU)
4、最近未使用算法(NotRecentlyUsed,NRU)
5、时钟页面置换算法
6、老化算法(aging)
页框的数量固定为4,虚拟页面数为8。
实验输入为访问页面序列,比如0,1,3,2,7,1
实验用到的软件(:
)
Vs,word,processon
实验内容、关键步骤(流程图、代码等)及结果分析(70分)
一、先进先出页面置换算法
1、基本思想:
地址映射过程中,若在页面中发现所要访问的页面不再内存中,则产生缺页中断。
当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。
而用来选择淘汰哪一页的规则叫做页面置换算法。
最简单的页面置换算法是先入先出(FIFO)法。
2、算法流程图
3、步骤说明
(1)初始化
voidinit(){age_id=-1;
page_table[i].load_time=-1;
page_table[i].last_visit_time=-1;
}
}
(2)选择算法,输入插入页面号。
进入判断函数
intjudge(){age_id==-1||page_table[i].page_id==page_id)
returni;
}
return-2;
}
之后根据返回数的不同决定了不同类型
返回-2则说明页框满且页框里面没有存在要插入的页面。
返回-1则说明页框未满
返回其它数则说明页框里存在相同的页面
(3)age_id=page_id;
page_table[0].load_time=counter;
page_table[0].last_visit_time=counter;
page_interrupt_number++;
将页框号为0的页面置换成最新插入的页面。
intcmp(constvoid*p,constvoid*q){oad_time-(*(structPage_table*)q).load_time;
if(c>0)
return1;
else
return-1;
}
排序函数,将页面按装入时间从小到大排序
(4)age_id==-1){
page_table[j].page_id=page_id;
page_table[j].load_time=counter;
page_table[j].last_visit_time=counter;
page_interrupt_number++;
则将页面替换在页框号最小的空页框里
(5)ast_visit_time=counter;
则更新页面的最近访问时间
(6)qsort(page_table,page_frame_number,sizeof(structPage_table),cmp3);age_id,j,page_table[j].load_time,page_table[j].last_visit_time);
};break;
排序函数
intcmp3(constvoid*p,constvoid*q){age_id!
=-1&&(*(structPage_table*)q).page_id!
=-1){
intc=(*(structPage_table*)p).load_time-(*(structPage_table*)q).load_time;
if(c>0)
return1;
else
return-1;
}
}
(7)并计算出中断页面次数及命中概率,并打印页表出来
intsum;
sum=((virtual_page_number-page_interrupt_number)*100/virtual_page_number);
printf("缺页中断次数:
%d\n",page_interrupt_number);
printf("中断命中率:
%d%%\n",sum);
printf("打印出页面\n");
for(inti=0;i{
for(intg=1;g<=virtual_page_number;g++)
{
printf("%4d",pr[i][g]);
}
printf("\n");
}
4、实现
(1)选择FIFO算法
(2)输入页面号,列出页表详细信息
(3)输入-1,结束输入,显示统计结果及页表
二、最近最少使用页面置换算法
1、基本思想:
在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。
反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。
这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。
因此,我们只需要在每次调换时,找到最近最久使用的那个页面调出内存。
2、算法流程图
3、步骤说明:
(1)初始化
voidinit(){age_id=-1;
page_table[i].load_time=-1;
page_table[i].last_visit_time=-1;
}
}
(2)选择算法,输入插入页面号。
进入判断函数
intjudge(){age_id==-1||page_table[i].page_id==page_id)
returni;
}
return-2;
}
之后根据返回数的不同决定了不同类型
返回-2则说明页框满且页框里面没有存在要插入的页面。
返回-1则说明页框未满
返回其它数则说明页框里存在相同的页面
(3)age_id=page_id;
page_table[0].load_time=counter;
page_table[0].last_visit_time=counter;
page_interrupt_number++;
将页框号为0的页面置换成最新插入的页面。
intcmp1(constvoid*p,constvoid*q){ast_visit_time-(*(structPage_table*)q).last_visit_time;
if(c>0)
return1;
else
return-1;
}
排序函数,将页面按最后访问时间从小到大排序
(4)age_id==-1){
page_table[j].page_id=page_id;
page_table[j].load_time=counter;
page_table[j].last_visit_time=counter;
page_interrupt_number++;
则将页面替换在页框号最小的空页框里
(5)ast_visit_time=counter;
则更新页面的最近访问时间
(6)qsort(page_table,page_frame_number,sizeof(structPage_table),cmp2);age_id,j,page_table[j].load_time,page_table[j].last_visit_time);
};break;
排序函数
intcmp2(constvoid*p,constvoid*q){age_id!
=-1&&(*(structPage_table*)q).page_id!
=-1){
intc=(*(structPage_table*)p).last_visit_time-(*(structPage_table*)q).last_visit_time;
if(c>0)
return1;
else
return-1;
}
}
(7)并计算出中断页面次数及命中概率,并打印页表出来
intsum;
sum=((virtual_page_number-page_interrupt_number)*100/virtual_page_number);
printf("缺页中断次数:
%d\n",page_interrupt_number);
printf("中断命中率:
%d%%\n",sum);
printf("打印出页面\n");
for(inti=0;i{
for(intg=1;g<=virtual_page_number;g++)
{
printf("%4d",pr[i][g]);
}
printf("\n");
}
4、实现
(1)选择LRU算法
(2)输入页面号,并打印出详细页表
(3)输入-1,结束输入,显示统计结果及页表
三、代码
oad_time-(*(structPage_table*)q).load_time;
if(c>0)
return1;
else
return-1;
}
intcmp1(constvoid*p,constvoid*q){ast_visit_time-(*(structPage_table*)q).last_visit_time;
if(c>0)
return1;
else
return-1;
}
intcmp2(constvoid*p,constvoid*q){age_id!
=-1&&(*(structPage_table*)q).page_id!
=-1){
intc=(*(structPage_table*)p).last_visit_time-(*(structPage_table*)q).last_visit_time;
if(c>0)
return1;
else
return-1;
}
}
intcmp3(constvoid*p,constvoid*q){age_id!
=-1&&(*(structPage_table*)q).page_id!
=-1){
intc=(*(structPage_table*)p).load_time-(*(structPage_table*)q).load_time;
if(c>0)
return1;
else
return-1;
}
}
voidinit(){age_id=-1;
page_table[i].load_time=-1;
page_table[i].last_visit_time=-1;
}
}
voidprint(intx){age_id,j,page_table[j].load_time,page_table[j].last_visit_time);
};break;
case3:
for(i=0;i<80;i++)
printf("-");
printf("\t\tFIFO算法模拟过程\n");
for(i=0;i<80;i++)
printf("-");
printf("\n");break;
case4:
for(i=0;i<80;i++)
printf("-");
printf("\t\tLRU算法模拟过程\n");
for(i=0;i<80;i++)
printf("-");
printf("\n");
}
}
intjudge(){age_id==-1||page_table[i].page_id==page_id)
returni;
}
return-2;
}
voidfifo(){
intj;
print(3);
print
(1);
printf("请依次输入页面号(最多8个。
输入-1结束输入,统计出缺页次数):
");
while
(1){
cin>>page_id;
if(page_id==-1)
break;
j=judge();
if(j==-2){age_id=page_id;
page_table[0].load_time=counter;
page_table[0].last_visit_time=counter;
page_interrupt_number++;
}
else{age_id==-1){
page_table[j].page_id=page_id;
page_table[j].load_time=counter;
page_table[j].last_visit_time=counter;
page_interrupt_number++;
}
else{ast_visit_time=counter;
}
}
counter++;
qsort(page_table,page_frame_number,sizeof(structPage_table),cmp3);age_id;
}
}
intsum;
sum=((virtual_page_number-page_interrupt_number)*100/virtual_page_number);
printf("缺页中断次数:
%d\n",page_interrupt_number);
printf("中断命中率:
%d%%\n",sum);
printf("打印出页面\n");
for(inti=0;i{
for(intg=1;g<=virtual_page_number;g++)
{
printf("%4d",pr[i][g]);
}
printf("\n");
}
}
voidlru(){
intj;
print(4);
print
(1);
printf("请依次输入页面号(最多8个。
输入-1结束输入,统计出缺页次数):
");
while
(1){
cin>>page_id;
if(page_id==-1)
break;
j=judge();
if(j==-2){age_id=page_id;
page_table[0].load_time=counter;
page_table[0].last_visit_time=counter;
page_interrupt_number++;
}
else{
if(page_table[j].page_id==-1){age_id=page_id;
page_table[j].load_time=counter;
page_table[j].last_visit_time=counter;
page_interrupt_number++;
}
else{ast_visit_time=counter;
}
}
counter++;
qsort(page_table,page_frame_number,sizeof(structPage_table),cmp2);age_id;
}
}
intsum;
sum=((virtual_page_number-page_interrupt_number)*100/virtual_page_number);
printf("缺页中断次数:
%d\n",page_interrupt_number);
printf("中断命中率:
%d%%\n",sum);
printf("打印出页面\n");
for(inti=0;i{
for(intg=1;g<=virtual_page_number;g++)
{
printf("%4d",pr[i][g]);
}
printf("\n");
}
}
intmain(){
print(0);
init();
while
(1){
cin>>algorithm;
if(strcmp(algorithm,"F")==0||strcmp(algorithm,"L")==0)
break;
else
printf("输入出错,请重新输入\n");
}
if(strcmp(algorithm,"F")==0){
fifo();
}
else{
lru();
}
system("pause");
return0;
}
实验过程中遇到的问题解决办法与实验体会(10分)【请注意:
此处必须如实填写,为空或不适均扣10分】