实验三页面置换算法实验
- 格式：doc
- 大小：238.50 KB
- 文档页数：12
实验三页面置换算法实验
-CAL-FENGHAI.-(YICAI)-Company One1 《操作系统原理》
实验报告
实验三 页面置换算法实验
专业：计算机科学与技术
学号：030840204
姓名：简郸
实验日期：2010-5-22
一、实验目的
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
二、实验要求
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。
1．最佳淘汰算法（OPT）
2．先进先出的算法（FIFO）
3．最近最久未使用算法（LRU）
三、实验方法内容
1. 算法设计思路
1．假设分给一作业的内存块数为 4 ，每条指令占一个存储单元，每个页面中可存放 10 条指令；
2．设计一个程序，模拟一作业的执行过程。设该作业共有 160 条指令，即它的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果 4 个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有 160条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
3 ．作业中指令的访问次序要求按下述原则生成：
具体的实施办法是：
(1)在[0，159]之间随机选取一条起始执行指令，其序号为 m ；
(2)顺序执行两条指令，即序号为 m+1、m+2 的指令；
(3)通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为 m1 ；
(4)顺序执行两条指令，即序号为 m1+1 ，m1+2的指令；
(5)通过随机数，跳转到后地址部分 [m1+3，159] 中的某条指令处，其序号为 m2 ；
(6)顺序执行两条指令，即序号为 m2+1，m2+2 的指令；若m2+2>159只执行一条指令；
(7)重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部160条指令
2. 算法流程图
3. 算法中用到的数据结构
4. 主要的常量变量
5. 主要模块
四、实验代码 #include
#include
#include
#include
#define total_instruction 200 /*指令流长*/
#define M 16 /*实际页数*/
#define N 4 //可用页面数
struct Pro
{int num,time;
};
int a[total_instruction];
int page[N];
void Input(Pro p[total_instruction])
{
int m,i,m1,m2;
srand( (unsigned int )time(NULL));
m=rand( )%160; //
for(i=0;i
{
if(m<0||m>159)
{
printf("When i==%d,Error,m==%d\n",i,m);
exit(0);
}
a[i]=m; /*任选一指令访问点m*/
a[i+1]=a[i]+1;
a[i+2]=a[i]+2; /*顺序执行两条指令*/
int m1=rand( )%m; /*执行前地址指令m1 */
a[i+3]=m1;
a[i+4]=m1+1;
a[i+5]=m1 + 2;/*顺序执行两条指令*/
// s=(158-a[i+5])*rand( )/32767/32767/2+a[i+5]+2;
m2 = rand()%(157-m1)+m1+3;
a[i+6]=m2;
if( (m2+2) > 159 ) {
a[i+7] = m2+1;
i +=8;
}
else
{
a[i+7] = m2+1;
a[i+8] = m2+2;
i = i+9;
}
m = rand()%m2;
}
for (i=0;i
{
p[i].num=a[i]/10;
p[i].time = 0;
}
}
void print(Pro *page1)//打印当前的页面
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i
cout<
cout<
}
int Search(int e,Pro *page1 )
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i
return -1;
}
int Max(Pro *page1)
{
Pro *page=new Pro[N];
page=page1;
int e=page[0].time,i=0;
while(i
{
if(e
}
for( i=0;i
return -1;
}
int Compfu(Pro *page1,int i,int t,Pro p[M])
{
Pro *page=new Pro[N];
page=page1;
int count=0;
for(int j=i;j
{
if(page[t].num==p[j].num )break;
else count++;
}
return count;
}
int main()
{
Pro p[total_instruction];
Pro *page=new Pro[N];
char c;
int t=0;
float n=0;
Input(p);
do{
for(int i=0;i
{
page[i].num=0;
page[i].time=2-i;
}
i=0;
cout<<"f:FIFO页面置换"<
cout<<"l:LRU页面置换"<
cout<<"o:OPT页面置换"<
cout<<"按其它键结束"<
cin>>c;
if(c=='f')//FIFO页面置换 {
n=0;
cout<<"页面置换情况: "<
while( i< total_instruction)
{
if(Search(p[i].num,page)>=0)
i++;//找到相同的页面
else
{
if(t==N)t=0;
else
{
n++;//
page[t].num=p[i].num;
print(page);
t++;
}
}
}
cout<<"缺页次数："<
}
if(c=='l')//LRU页面置换
{
n=0;
cout<<"页面置换情况: "<
while(i
{
int k;
k=t=Search(p[i].num,page);
if(t>=0)
page[t].time=0;
else
{
n++;
t=Max(page);
page[t].num=p[i].num;
page[t].time=0;
}
if(t==0){page[t+1].time++;page[t+2].time++;}
