第7次常用页面置换算法模拟实验Word格式文档下载.docx
《第7次常用页面置换算法模拟实验Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《第7次常用页面置换算法模拟实验Word格式文档下载.docx(20页珍藏版)》请在冰点文库上搜索。
要求在主函数中测试。
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>
return1;
else
return-1;
(7)并计算出中断页面次数及命中概率,并打印页表出来
intsum;
sum=((virtual_page_number-page_interrupt_number)*100/virtual_page_number);
printf("
缺页中断次数:
%d\n"
page_interrupt_number);
中断命中率:
%d%%\n"
sum);
打印出页面\n"
);
for(inti=0;
i<
page_frame_number;
i++)
{
for(intg=1;
g<
=virtual_page_number;
g++)
{
printf("
%4d"
pr[i][g]);
}
printf("
\n"
4、实现
(1)选择FIFO算法
(2)输入页面号,列出页表详细信息
(3)输入-1,结束输入,显示统计结果及页表
二、最近最少使用页面置换算法
在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。
反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。
这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。
因此,我们只需要在每次调换时,找到最近最久使用的那个页面调出内存。
3、步骤说明:
intcmp1(constvoid*p,constvoid*q){ast_visit_time-(*(structPage_table*)q).last_visit_time;
排序函数,将页面按最后访问时间从小到大排序
(6)qsort(page_table,page_frame_number,sizeof(structPage_table),cmp2);
intcmp2(constvoid*p,constvoid*q){age_id!
intc=(*(structPage_table*)p).last_visit_time-(*(structPage_table*)q).last_visit_time;
(1)选择LRU算法
(2)输入页面号,并打印出详细页表
三、代码
oad_time-(*(structPage_table*)q).load_time;
voidprint(intx){age_id,j,page_table[j].load_time,page_table[j].last_visit_time);
case3:
for(i=0;
80;
-"
\t\tFIFO算法模拟过程\n"
for(i=0;
case4:
\t\tLRU算法模拟过程\n"
voidfifo(){
intj;
print(3);
print
(1);
请依次输入页面号(最多8个。
输入-1结束输入,统计出缺页次数):
"
while
(1){
cin>
>
page_id;
if(page_id==-1)
break;
j=judge();
if(j==-2){age_id=page_id;
else{age_id==-1){
}
else{ast_visit_time=counter;
counter++;
qsort(page_table,page_frame_number,sizeof(structPage_table),cmp3);
age_id;
intsum;
pr[i][g]);
voidlru(){
print(4);
else{
if(page_table[j].page_id==-1){age_id=page_id;
qsort(page_table,page_frame_number,sizeof(structPage_table),cmp2);
}
intmain(){
print(0);
init();
algorithm;
if(strcmp(algorithm,"
F"
)==0||strcmp(algorithm,"
L"
)==0)
输入出错,请重新输入\n"
if(strcmp(algorithm,"
)==0){
fifo();
else{
lru();
system("
pause"
return0;
实验过程中遇到的问题解决办法与实验体会(10分)
【请注意:
此处必须如实填写,为空或不适均扣10分】