【操作系统】 置换策略模拟实现
扫描二维码
随时随地手机看文章
【实现目标】
实现OPT,LRU,FIFO,CLOCK置换策略，并计算缺页次数和缺页率。
【算法分析】
1.OPT策略——最佳策略
即根据将来的结果选择替换的页，但实际是不可能实现的，因为未来是无法预知的。但是可以作为性能分析的参照。
2.LRU策略——最近最少使用
选出内存中离现在使用时间最久远的页进行替换。
3.FIFO策略——先进先出
如题，就是按照顺序进行替换。
4.CLOCL策略——时钟策略
每一个页框对应一个01状态位，若页框还未满，则放入，并将该位置为1。若已满，当页在内部时，不用替换。否则，循环扫描使用位，碰到为0的则替换，若为1则置为0。若全为1，则再次循环时，会自动替换第一个0。（每次循环是从上次替换的位置开始，若没发生替换，即在内存中，不会移动位置！）
【实验数据】
12 3
2 3 2 1 5 2 4 5 3 2 5 2
【实验结果】
【实验代码】
#include
#include
#include
#define inf 0x3f3f3f3f
#define seq_sz 50
#define frame_sz 50
using namespace std;
//序列数，叶框数
int amount,volume;
int min(int a,int b)
{
return a<b?a:b;
}
//序列，叶框
int seq[seq_sz],frame[frame_sz];
//OPT策略
void OPT()
{
int cnt=0;
printf("OPT:n");
memset(frame,-1,sizeof(frame));
//val数组状态位，表征下一次使用时间，初始值为无穷大
int val[frame_sz],p,maxx;
for(int i=0;i<amount;i++)
{
bool flag=0;
for(int j=0;j<volume;j++)
{
if(frame[j]==seq[i])
{
flag=1;
break;
}
}
if(!flag)
{
cnt++;
if(cnt>volume)
{
memset(val,inf,sizeof(val));
for(int j=i;j<amount;j++)
{
for(int k=0;k<volume;k++)
{
if(frame[k]==seq[j])
{
val[k]=min(val[k],j);
}
}
}
p=0;
maxx=val[0];
for(int j=1;j<volume;j++)
{
if(val[j]>maxx)
{
maxx=val[j];
p=j;
}
}
frame[p]=seq[i];
}
else
{
frame[cnt-1]=seq[i];
}
}
for(int j=0;j<volume;j++)
{
if(frame[j]!=-1)
printf("%6d ",frame[j]);
else
printf("Empty! ");
}
printf("n");
}
//输出缺页次数和缺页率
printf("Pages missed: %d Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//LRU策略
void LRU()
{
printf("LRU:n");
//cnt为缺页次数，val表征最近使用时间，也是选择标准
intcnt=0,val[frame_sz],p,minn;
memset(frame,-1,sizeof(frame));
for(int i=0;i<amount;i++)
{
bool flag=0;
for(int j=0;j<volume;j++)
{
if(frame[j]==seq[i])
{
flag=1;
val[j]=i;
break;
}
}
if(!flag)
{
cnt++;
if(cnt>volume)
{
minn=val[0];
p=0;
for(int j=1;j<volume;j++)
{
if(val[j]<minn)
{
minn=val[j];
p=j;
}
}
frame[p]=seq[i];
val[p]=i;
}
else
{
frame[cnt-1]=seq[i];
val[cnt-1]=i;
}
}
for(int j=0;j<volume;j++)
{
if(frame[j]!=-1)
printf("%6d ",frame[j]);
else
printf("Empty! ");
}
printf("n");
}
//输出缺页次数，缺页率
printf("Pages missed: %d Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//FIFO策略
void FIFO()
{
printf("FIFO:n");
//qe模拟队列，模除循环
int qe[frame_sz],p=0,cnt=0;
memset(frame,-1,sizeof(frame));
for(int i=0;i<amount;i++)
{
bool flag=0;
for(int j=0;j<volume;j++)
{
if(frame[j]==seq[i])
{
flag=1;
break;
}
}
if(!flag)
{
cnt++;
frame[p%volume]=seq[i];
p++;
}
for(int j=0;j<volume;j++)
{
if(frame[j]!=-1)
printf("%6d ",frame[j]);
else
printf("Empty! ");
}
printf("n");
}
printf("Pages missed: %d Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//CLOCK策略
void CLOCK()
{
printf("CLOCK:n");
//status状态位
bool status[frame_sz];
int p=0,cnt=0;
memset(frame,-1,sizeof(frame));
memset(status,0,sizeof(status));
for(int i=0;i<amount;i++)
{
bool flag=0;
for(int j=0;j<volume;j++)
{
if(frame[j]==seq[i])
{
flag=1;
status[j]=1;
break;
}
}
if(!flag)
{
cnt++;
while(1)
{
p%=volume;
bool sign=0;
for(;p<volume;p++)
{
if(status[p])
status[p]=0;
else
{
sign=1;
status[p]=1;
frame[p]=seq[i];
p++;
break;
}
}
if(sign)break;
}
}
for(int j=0;j<volume;j++)
{
if(frame[j]!=-1)
printf("%6d ",frame[j]);
else
printf("Empty! ");
}
printf("n");
}
printf("Pages missed: %d Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
int main()
{
while(~scanf("%d%d",&amount,&volume))
{
for(int i=0;i<amount;i++)
scanf("%d",&seq[i]);
for(int i=0;i<amount;i++)
printf(" %d",seq[i]);
printf("n");
//分别测试
OPT();
LRU();
FIFO();
CLOCK();
}
下载文档
