常用页面置换算法模拟实验.doc

操作系统课程实验报告

实验地点

实验时间

实验课表现
出勤和个人表现Q1(15+15（组长评分）=30分)
得分：

实验
总分
(Q1+Q2+Q3+Q4)

实验完成情况Q2(45分(组长与教师评分的加权平均))
得分：
实验编号与实验名称：
第7次实验 常用页面置换算法模拟实验
实验目的：
1．实验目的
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
实验内容及要求（详见实验讲义与实验指导书）：
2.实验要求：
1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。
2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。
3）必须模拟本实验内容中提到的算法中的至少2种页面置换算法。
4） 比较不同页面置换算法的效率
3．实验内容
编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。

1、第二次机会算法（Second Chance）
2、最近最少使用算法（Least Recently Used，LRU ）
3、最不常用算法（Not Frequently Used，NFU）
4、最近未使用算法（Not Recently Used ，NRU）
5、时钟页面置换算法
6、老化算法（aging）
页框的数量固定为4，虚拟页面数为8。实验输入为访问页面序列，比如0，1 ，3 ，2，7，1
实验用到的软件（：）
C-Free 5
实验内容及关键步骤（代码）Q3（15分）
得分：

流程图：

代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define page_frame_number 4 //页框数
#define virtual_page_number 8 //虚拟页面数
int page_id, counter = 0;//输入id和计数器
char algorithm[20];//算法选择
int page_interrupt_number = 0;
struct Page_table{
int page_id; //页号
int load_time; //装入时间
int last_visit_time; //最后访问时间
}page_table[page_frame_number];
int cmp(const void *p,const void *q){
int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time;

if(c > 0)
return 1;
else
return -1;
}
int cmp1(const void *p,const void *q){
int c = (*(struct Page_table*)p).last_visit_time - (*(struct Page_table*)q).last_visit_time;
if(c > 0)
return 1;
else
return -1;
}
void init(){//初始化
int i;
for(i = 0; i < page_frame_number; i++){
page_table[i].page_id = -1;
page_table[i].load_time = -1;
page_table[i].last_visit_time = -1;
}
}
void print(int x){//打印信息
int i,j;
switch(x){
case 0: for(i = 0; i < 80; i++)
printf("-");
printf("\t\t试验七 常用页面置换算法模拟实验\n");
for(i = 0; i < 80; i++)
printf("-");
printf("\n");
printf("选择算法：F/L（FIFO算法/LRU算法）\n");break;
case 1:printf("请输入访问页面的顺序,以“-1”结束：\n");break;
case 2: printf("页表信息：\n页 号 页框号 装入时间 最近访问时间\n");
for(j = 0; j < page_frame_number; j++){
printf("%4d%8d%7d%7d\n",page_table[j].page_id,j,page_table[j].load_time,page_table[j].last_visit_time);
};break;
case 3:for(i = 0; i < 80; i++)
printf("-");
printf("\t\tFIFO算法模拟过程\n");
for(i = 0; i < 80; i++)
printf("-");

printf("\n");break;
case 4:for(i = 0; i < 80; i++)
printf("-");
printf("\t\tLRU算法模拟过程\n");
for(i = 0; i < 80; i++)
printf("-");
printf("\n");
}
}
int judge(){
int i;
for(i = 0; i < page_frame_number; i++){
if(page_table[i].page_id == -1||page_table[i].page_id == page_id)
return i;
}
return -1;
}
void fifo(){
int j;
print(3);
print(1);
while(1){
scanf("%d",&page_id);
if(page_id == -1)
break;
j = judge();
if(j == -1){
qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp);//按照最后访问时间从小到大排序
page_table[0].page_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){
page_table[j].page_id = page_id;
page_table[j].load_time = counter;
page_table[j].last_visit_time = counter;
page_interrupt_number++;
}
else{
page_table[j].last_visit_time = counter;
}

}
counter++;
print(2);
}
printf("缺页中断次数：%d\n",page_interrupt_number);
}
void lru(){
int j;
print(4);
print(1);
while(1){
scanf("%d",&page_id);
if(page_id == -1)
break;
j = judge();
if(j == -1){
qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp1);//按照装入时间从小到大排序
page_table[0].page_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){
page_table[j].page_id = page_id;
page_table[j].load_time = counter;
page_table[j].last_visit_time = counter;
page_interrupt_number++;
}
else{
page_table[j].last_visit_time = counter;
}
}
counter++;
print(2);
}
printf("缺页中断次数：%d\n",page_interrupt_number);
}
int main(){
print(0);
init();
while(1){
scanf("%s",algorithm);

if(strcmp(algorithm,"F") == 0||strcmp(algorithm,"L") == 0)
break;
else
printf("输入出错，请重新输入\n");
}
if(strcmp(algorithm,"F") == 0){
fifo();
}
else{
lru();
}
system("pause");
return 0;
}

FIFO算法运行结果

LRU算法运行结果

实验过程中遇到的问题解决办法与实验体会Q4（需手写，10分）
得分：
这次实验让我了解了内存页面置换的几种算法，通过代码，让我更加深刻了了解了fifo，lru，算法的核心思想。对于其他页面替换算法，也有初步的学习理解。
评阅教师特殊评语：

评阅教师：

日 期：

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）