//
// main.cpp
// COS5
//
// Created by 杨 on 2018/11/8.
// Copyright © 2018 杨. All rights reserved.
//
#include <iostream>
#include<ctime>
#include<cstdlib>
#include <iomanip>
using namespace std;
int flag=0; //记录页面是否在内存中
int flag2=0; //内存中是否有空页面
int page[320]={0}; //指令页面
int pb[32]; //虚存容量
int t[32]; //页面停留时间
int distan[32]={0}; //记录距离
int random(int star,int end){ //产生随机数
return rand()%(end-star+1)+star;
}
void clear(){ //初始化虚存容量
for(int i=0;i<32;i++){
pb[i]=-1;
}
}
void clear2(){ //初始化距离记录数组
for(int i=0;i<32;i++){
distan[i]=0;
}
}
void init(){ //产生320条指令
int i=0;
int M,M1,M2;
M=M1=M2=0;
srand(unsigned(time(0)));
while(i<320){
M=random(1, 31998);
page[i]=M/1000; //指令流转变为页地址
page[++i]=(M+1)/1000;
M1=random(0, M-1);
page[++i]=M1/1000;
page[++i]=(M1+1)/1000;
M2=random(M1+2, 31998);
page[++i]=M2/1000;
page[++i]=(M2+1)/1000;
i++;
}
}
double FIFO(int i){ //先进先出页面置换算法
clear();
int k=0; //记录最先进入内存的页面
int count=0; //页面失效次数
for(int s=0;s<320;s++){
flag=0;
flag2=0;
for(int x=0;x<i;x++){ //查看页面是否在内存中
if(pb[x]==page[s]){
flag=1;
break;
}
}
if(flag==0){ //不在内存中
for(int x=0;x<i;x++){ //查看内存中是否有空白页面
if(pb[x]!=-1) flag2++;
}
if(flag2!=i){ //内存中有空白页面
pb[flag2]=page[s];
count++;
}
else{
pb[k]=page[s];
k=(k+1)%i; //下一个进入内存的页面
count++;
}
}
}
return 1-count/320.0;
}
double LRU(int i){ //最近最久未使用页面置换算法
clear();
int count=0;
int max_time=0;
int j=-1;
for(int x=0;x<320;x++) t[x]=-1;
for(int s=0;s<320;s++){
flag=0;
flag2=0;
max_time=0;
for(int x=0;x<i;x++){ //查看页面是否在内存中
if(pb[x]==page[s]){
t[x]=0;
flag=1;
break;
}
}
if(flag==0){ //不在内存中
for(int x=0;x<i;x++){ //查看内存中是否有空白页面
if(pb[x]!=-1) flag2++;
}
if(flag2!=i){ //内存中有空白页面
pb[flag2]=page[s];
count++;
}
else{
for(int y=0;y<i;y++){ //寻找内存中停留时间最长的页面
if(t[y]>max_time){
max_time=t[y];
j=y;
}
}
pb[j]=page[s];
t[j]=0;
count++;
}
}
for(int z=0;z<i;z++) t[z]++;
}
return 1-count/320.0;
}
double OPT(int i){ //最佳置换算法
clear();
int count=0;
int max_dis=0;
int j=0; //记录要替换的内存页块
for(int s=0;s<320;s++){
flag=0;
flag2=0;
max_dis=0;
clear2();
for(int x=0;x<i;x++){ //查看页面是否在内存中
if(pb[x]==page[s]){
flag=1;
break;
}
}
if(flag==0){ //不在内存中
for(int x=0;x<i;x++){ //查看内存中是否有空白页面
if(pb[x]!=-1) flag2++;
}
if(flag2!=i){ //内存中有空白页面
pb[flag2]=page[s];
count++;
}
else{
for(int y=0;y<i;y++){ //计算当前内存中页面之后再次出现的距离
for(int z=s;z<320;z++){
if(pb[y]!=page[z]) distan[y]++;
else break;
}
}
for(int y=0;y<i;y++){ //寻找内存中未来最久不会出现的页面
if(max_dis<distan[y]){
max_dis=distan[y];
j=y;
}
}
pb[j]=page[s];
count++;
}
}
}
return 1-count/320.0;
}
int main(){
init();
cout<<"内存页块数"<<" "<<"FIFO"<<" "<<"LRU"<<" "<<"OPT"<<endl;
for(int i=4;i<=32;i++){
if(i<10)cout<<"0";
cout<<i<<fixed<<setprecision(6)<<": "<<FIFO(i)<<" "<<LRU(i)<<" "<<OPT(i)<<endl;
}
return 0;
}
