经典操作系统教材中的LRU算法介绍
经典操作系统教材中的LRU算法介绍
#include <iostream.h>
#include <string.h>
/*void setm(int a[][],int m,int n)
{ int i,j;
for(i=0;i<n;i++)
{a[m-1][i]=1;
}
for(j=0;j<n;j++)
{a[i][m-1]=0;}
};*/
int **martrix;
int i,j;
void setm(int m,int n)
{for(i=0;i<n;i++)
{martrix[m][i]=1;
martrix[i][m]=0;
}
}
char * current;
void print(int n)
{ int p,q;
for(p=0;p<n;p++)
{ for(q=0;q<n;q++)
{cout<<martrix[p][q]<<" ";}
cout<<"**"<<current[p];
cout<<"/n";
}
}
int mini(int *b)
{int i=0;
int n,m,flag;
n=0;
while(b[i]>=0&&b[i]<=9){n++;i++;}
m=b[0];flag=0;
for(j=1;j<n;j++)
{ if(m>b[j]) {m=b[j];flag=j;}
}
return flag;
}
void main()
{
int n;
char sequence[255];
cout<<"请输入页架数:";
cin>>n;
cout<<"请输入访问序列:";
cin>>sequence;
cout<<"*****ALL RIGHT RESERVED BY 英雄*****"<<endl;
martrix=new int * [n];
for( i=0;i<n;i++)
martrix[i]=new int[n];
current=new char [n];
for(i=0;i<n;i++)
current[i]=' ';
for(i=0;i<n;i++)
for(j=0;j<n;j++)
martrix[i][j]=0;
int k;
int len=strlen(sequence);
//setm(0,n);print(n);cout<<endl;
//setm(1,n);print(n);cout<<endl;
//setm(2,n);print(n);
//for(i=1;i<=len;i++)
//{ if(i<=n) {setm(i-1,n);print(n);cout<<endl;}
//}
int flag;
int f;
int *total;
int g;
int count=0;
char c;
total=new int[n];
for(i=0;i<n;i++)
total[i]=0;
for(k=1;k<=len;k++)
{ cout<<endl;
cout<<sequence[k-1]<<"要求进入"<<endl;
if(k<=n) {current[k-1]=sequence[k-1];setm(k-1,n);print(n);cout<<"缺页"<<endl;count++;}
else
{ for(i=0;i<n;i++)
{ if(current[i]==sequence[k-1]) {flag=i; break;}
}
if(i==n) {
for(f=0;f<n;f++)
{ for(g=0;g<n;g++)
{total[f]+=martrix[f][g];}
}
c=current[mini(total)];
current[mini(total)]=sequence[k-1];
setm(mini(total),n);print(n);cout<<"缺页,置换前一次"<<c<<"的那行"<<endl;
cout<<endl;
count++;
}
else
{setm(flag,n);print(n);cout<<endl;}
}
for(i=0;i<n;i++)
total[i]=0;
}
cout<<"总共有"<<count<<"次缺页"<<endl;
cout<<"请按任意键并回车退出"<<endl;
cin>>c;}
不妨用课本上的例子先测试下这个小东西哟!
课本上的例子是:页架数是:4;
访问序列是:0123010321;
执行结果是:
请输入页架数:4
请输入访问序列:0123010321
*****ALL RIGHT RESERVED BY 英雄**
0要求进入
0 1 1 1 **0
0 0 0 0 **
0 0 0 0 **
0 0 0 0 **
缺页
1要求进入
0 0 1 1 **0
1 0 1 1 **1
0 0 0 0 **
0 0 0 0 **
缺页
2要求进入
0 0 0 1 **0
1 0 0 1 **1
1 1 0 1 **2
0 0 0 0 **
缺页
3要求进入
0 0 0 0 **0
1 0 0 0 **1
1 1 0 0 **2
1 1 1 0 **3
缺页
0要求进入
0 1 1 1 **0
0 0 0 0 **1
0 1 0 0 **2
0 1 1 0 **3
1要求进入
0 0 1 1 **0
1 0 1 1 **1
0 0 0 0 **2
0 0 1 0 **3
0要求进入
0 1 1 1 **0
0 0 1 1 **1
0 0 0 0 **2
0 0 1 0 **3
3要求进入
0 1 1 0 **0
0 0 1 0 **1
0 0 0 0 **2
1 1 1 0 **3
2要求进入
0 1 0 0 **0
0 0 0 0 **1
1 1 0 1 **2
1 1 0 0 **3
1要求进入
0 0 0 0 **0
1 0 1 1 **1
1 0 0 1 **2
1 0 0 0 **3
总共有4次缺页
请按任意键并回车退出
这个与课本上的答案可是一样的哟!
其它的例子就大家去试了,比如说这次作业:
页架数是:4;
访问序列是:ABCDABEABCDE
你敲进去就可以出结果了.
请输入页架数:4
请输入访问序列:ABCDABEABCDE
*****ALL RIGHT RESERVED BY英雄
A要求进入
0 1 1 1 **A
0 0 0 0 **
0 0 0 0 **
0 0 0 0 **
缺页
B要求进入
0 0 1 1 **A
1 0 1 1 **B
0 0 0 0 **
0 0 0 0 **
缺页
C要求进入
0 0 0 1 **A
1 0 0 1 **B
1 1 0 1 **C
0 0 0 0 **
缺页
D要求进入
0 0 0 0 **A
1 0 0 0 **B
1 1 0 0 **C
1 1 1 0 **D
缺页
A要求进入
0 1 1 1 **A
0 0 0 0 **B
0 1 0 0 **C
0 1 1 0 **D
B要求进入
0 0 1 1 **A
1 0 1 1 **B
0 0 0 0 **C
0 0 1 0 **D
E要求进入
0 0 0 1 **A
1 0 0 1 **B
1 1 0 1 **E
0 0 0 0 **D
缺页,置换前一次C的那行
A要求进入
0 1 1 1 **A
0 0 0 1 **B
0 1 0 1 **E
0 0 0 0 **D
B要求进入
0 0 1 1 **A
1 0 1 1 **B
0 0 0 1 **E
0 0 0 0 **D
C要求进入
0 0 1 0 **A
1 0 1 0 **B
0 0 0 0 **E
1 1 1 0 **C
缺页,置换前一次D的那行
D要求进入
0 0 0 0 **A
1 0 0 0 **B
1 1 0 1 **D
1 1 0 0 **C
缺页,置换前一次E的那行
E要求进入
0 1 1 1 **E
0 0 0 0 **B
0 1 0 1 **D
0 1 0 0 **C
缺页,置换前一次A的那行
总共有8次缺页
请按任意键并回车退出