操作系统课程第七次实验报告
姓名学号系计算机
教导指评阅教师贺辉贺辉任课教师贺辉师
实验地点 B102 综合楼
2012-9-26
实验时间
Q1（15+15出勤和个人表现得分：）（组长评分）=30分实 验课表现
实验总分
(Q1+Q2+Q3+Q4 )
（组分实验完成情况Q2（45长与教师评分的加权平得分：） ）均
实验七、常用页面置换算法模拟实验
实验目的：
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求 页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
实验内容及要求（详见实验讲义与实验指导书）：
要求：
1） 要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。
2） 实验报告中必须包括： 设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图） 源代码、运行结果、体会等部分。
3） 必须模拟本实验内容中提到的算法中的至少 2种页面置换算法。
4） 比较不同页面置换算法的效率
内容：编写一个程序，使用以下页面置换算法中的某 2种分别模拟一个分页系统， 并统计同一个页面访问
序列情况下不同页面置换算法引发的缺页中断次数。
1、 第二次机会算法（Seco nd Cha nee）
2、 最近最少使用算法（ Least Recently Used， LRU ）
3、 最不常用算法（Not Frequently Used ， NFU）
4、 最近未使用算法（ Not Recently Used ，NRU）
5、 时钟页面置换算法
6、 老化算法（aging）
页框的数量固定为 4，虚拟页面数为 8。实验输入为访问页面序列，比如 0，1 ，3，2， 1，7.
实验用到的软件（：）
DevC++,Visio
实验内容及关键步骤（代码）Q3
实验内容及关键步骤（代码）Q3 （15分）
得分:
流程图：输入页面访问序列
取访问的页号
查页表
否是
是否缺页？
为'*' flag置缺页标志 按算法不同淘汰一页面
调入所访问的页面
FIFO算法流程图
LRU算法流程图：
触贾面调度糧曲算去療豐圉云刨（2）
耙斬氏放莊枝頂?呵 啊自T略功体氽匪号
S^JSEAftTl. PI
时找陈灵号移岀
、卜畫曲命中宰
函数关系解释图:
主函数，入口 designB作者信息显示y()Main()01用fifo算法实现11LRU退出
EXIT()FIFO()算法实用lru现22PRINT()显示内存页框每次置换结果
实现结果：
*reh ￥ew 史
*reh ￥ew 史raject
pzintf（曲卜
I f
图2
,Vi WIIWM HPI
-IH
?I9 }
2.20
代码:
#include <stdio.h>
#include <stdlib.h>
*/
物理块数 /* #define MEMORY_SIZE 4
#define PROESS_SIZE 8 /* 页面号引用串个数 */#include <stdio.h>
#i nclude <stdlib.h>
/*全局变量*/
int mSIZE=4;
in t pSIZE=8;
static int memery[4]={0}; /* 物理块中的页号 */
static int page[8]={0}; /* 页面号引用串 */
static int temp[8][4]={0}; /* 辅助数组 */
/*置换算法函数*/
void FIFO();
void LRU();
void OPT();
void desig nBy();
/*辅助函数*/
void print(un sig ned int t);
/*主函数*/
int main()
{
int i,k,code;
desig nBy();
system(color 0A);
異獴尨请依次输入页面号(8个):);
for(i=0;ivpSIZE;i++)
sca nf(_x001D _，&page[i]);
system(cls);
system(color 0E);
do{
異獴尨输入的页面号引用串为：);
for(k=0;kv=(pSIZE -1)/20;k++)
{
for(i=20*k;(i<pSIZE )&&(i<20*(k+1));i++)
{
if(((i+1) ==0)||(((i+1) )&&(i==pSIZE -1)))
prin tf(%d\n,page[i]);
else
prin tf(%d ,page[i]);
}
}
printf(* * * * * * * * * * * * * * * * * * * * * * *\n)?
printf(*请选择页面置换算法：\t\t\t *\n);
printf(* *\n);
printf(* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *\n);
*\n);
退出 printf(* 3.
printf(* * * * * * * * * * * * * * * * * * * * * * *\n)? 牰湩晴尨请选择操作：[]\b\b); sea nf(%d,&code);
switch(code)
{ case 1:
FIFO(); break;
case 2: LRU(); break;
case 3:
system(cls); system(color OA);
exit(O);
default:
牰湩晴尨输入错误，请重新输入：);
}
牰湩晴尨按任意键重新选择置换算法：>>>);
getch(); system(cls);
}while (code!=3);
getch();
}
void print(un sig ned int t)
{
int i,j,k,l;
int flag;
for(k=0;kv=(pSIZE -1)/20;k++)
{
for(i=20*k;(i<pSIZE )&&(i<20*(k+1));i++)
{
if(((i+1) ==0)||(((i+1) )&&(i==pSIZE -1))) prin tf(%d\n,page[i]);
else
prin tf(%d ,page[i]);
}
for(j=0;j<mSIZE;j++)
{
for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++) {
if(i>=j) printf( |%d|,temp[i][j]);
else
printf( ||);
} for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++)
{
for(flag=0,l=0;l<mSIZE;l++)
if(temp[i][l]==temp[i -1][l]) flag++;
if(flag==mSIZE)/*页面在物理块中*/
printf( );
else
printf( |%d|,temp[i][j]);
}
/*每行显示20个*/
if(i ==0)
con ti nue;
);
}
}
printf( \n);
牰湩晴尨缺页次数：％d\t\t,t+mSIZE);
牰湩晴尨缺页率：％d/%d\n,t+mSIZE,pSIZE);
牰湩晴尨置换次数：%d\t\t,t);
牰湩晴尨访问命中率： %d%%\n,(pSIZE-(t+mSIZE))*100/pSIZE);
printf( \n);
}
/*先进先出页面置换算法*/
void FIFO()
{
int memery[10]={0};
int time[10]={0}; /*记录进入物理块的时间*/
int i,j,k,m;
int max=0; /*记录换出页*/
int count=0; /*记录置换次数*/
/*前mSIZE个数直接放入*/
for(i=0;i<mSIZE;i++)
{
memery[i]=page[i];
time[i]=i;
for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
}
for(i=mSIZE;i<pSIZE;i++)
*/
判断新页面号是否在物理块中/*
for(j=0,k=0;jvmSIZE;j++)
{
if(memery[j]!=page[i]) k++;
}
if(k==mSIZE) /*如果不在物理块中*/
{
coun t++;
/*计算换出页*/
max=time[0]<time[1]?0:1;
for(m=2;m<mSIZE;m++) if(time[m]<time[max])
max=m;
memery[max]=page[i];
time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
} else
{
for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
}
}
prin t(co un t);
}
/*最近最久未使用置换算法*/
void LRU()
{
int memery[10]={0};
int flag[10]={0}; /*记录页面的访问时间*/
int i,j,k,m;
int max=0; /*记录换出页*/
int count=0; /*记录置换次数*/
/*前mSIZE个数直接放入*/
for(i=0;i<mSIZE;i++)
{
memery[i]=page[i];
flag[i]=i;
for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
}
for(i=mSIZE;i<pSIZE;i++)
{
/*判断新页面号是否在物理块中*/
for(j=0,k=0;jvmSIZE;j++)
{
if(memery[j]!=page[i])
k++;
else
flag[j]=i; /*刷新该页的访问时间*/
}
if(k==mSIZE) /*如果不在物理块中*/
{
coun t++;
/*计算换出页*/
max=flag[0]vflag[1]?0:1;
for(m=2;m<mSIZE;m++)
if(flag[m]vflag[max])
max=m;
memery[max]=page[i];
flag[max]=i; /*记录该页的访问时间*/
for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
}
else
{
for(j=0;j<mSIZE;j++)
temp[i][j]=memery[j];
}
}
// compute。；
prin t(co un t);
}
/*显示设计者信息*/
void desig nBy()
{
牰湩晴尨 1 \n);
牰湩晴尨丨㊣ 实验七：页面置换算法 ㊣丨\n);
牰湩晴尨丨 学号：1001010042 | \n);
牰湩晴尨丨 姓名：黄浩全 <Dev-C++ 4.9.9.0>| \n);
牰湩晴尨 1 \n);
}
需手写，10Q4 （实验过程中遇到的问题解决办法与实验体会 分）
得分：
1、在FIFO算法可以很容易用数组实现，而 LRU算法可以用数组实现，不过用结 构体会更明显简单。结构体成员变量可以记录页号进入的时间，和最近使用的记录。
相对比数组更容易理解和实现。
2:首先，FIFO （先进先出）算法和LRU （最近未使用算法）两者之间，FIFO算法 明显会比LRU容易理解，而且比LRU算法较容易实现，但在性能方面，LRU的 确在优化方面做的比较理想。再且在考虑页框和页表号之间的问题用代码可以容易 模拟，但是真是在物理内存块中是如何实现， 那确实是很难以理解，需要真正理解 到内存内部的知识才知道这两个算法是怎么实现的。
评阅教师特殊评语:
评阅教师: 日 期: