第7次常用页面置换算法模拟实验
- 格式:doc
- 大小:504.00 KB
- 文档页数:14
操作系统课程实验报告
断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出(FIFO)法。
2、算法流程图
3、步骤说明
(1)初始化
void init(){age_id = -1;
page_table[i].load_time = -1;
page_table[i].last_visit_time = -1;
}
}
(2)选择算法,输入插入页面号。进入判断函数
int judge(){age_id == -1 || page_table[i].page_id == page_id)
return i;
}
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的页面置换成最新插入的页面。
int cmp(const void *p, const void *q){oad_time - (*(struct Page_table*)q).load_time;
if (c > 0)
return 1;
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(struct Page_table), cmp3);age_id, j, page_table[j].load_time, page_table[j].last_visit_time);
}; break;
排序函数
int cmp3(const void *p, const void *q){age_id != -1 && (*(struct Page_table*)q).page_id != -1){
int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time;
if (c > 0)
return 1;
else
return -1;
}
}
(7)并计算出中断页面次数及命中概率,并打印页表出来
int sum;
sum = ((virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);
printf("缺页中断次数:%d\n", page_interrupt_number);
printf("中断命中率:%d%%\n", sum);
printf("打印出页面\n");
for (int i = 0; i < page_frame_number; i++)
{
for (int g = 1; g <= virtual_page_number; g++)
{
printf("%4d", pr[i][g]);
}
printf("\n");
}
4、实现
(1)选择FIFO算法
(2)输入页面号,列出页表详细信息
(3)输入-1,结束输入,显示统计结果及页表
二、最近最少使用页面置换算法
1、基本思想:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理——比内存速度还要快的cache,也是基于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最久使用的那个页面调出内存。
2、算法流程图
3、步骤说明:
(1)初始化
void init(){age_id = -1;
page_table[i].load_time = -1;
page_table[i].last_visit_time = -1;
}
}
(2)选择算法,输入插入页面号。进入判断函数
int judge(){age_id == -1 || page_table[i].page_id == page_id)
return i;
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的页面置换成最新插入的页面。
int cmp1(const void *p, const void *q){ast_visit_time - (*(struct
Page_table*)q).last_visit_time;
if (c > 0)
return 1;
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(struct Page_table), cmp2);age_id, j, page_table[j].load_time, page_table[j].last_visit_time);
}; break;
排序函数
int cmp2(const void *p, const void *q){age_id != -1 && (*(struct Page_table*)q).page_id != -1){
int c = (*(struct Page_table*)p).last_visit_time - (*(struct
Page_table*)q).last_visit_time;
if (c > 0)
return 1;
else
return -1;
}
}
(7)并计算出中断页面次数及命中概率,并打印页表出来