#include <iostream>
#include <fstream>
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#define PF 4
#define GPNO 200
#define STRLN 5000
#define LEFT 0
#define RIGHT 1
#define TOTSTR 1
#define LRU 1
#define LFU 2
#define GENERATIONS 100
/*GLOBAL VARIABLES..*/
unsigned int mask[4]={0x07,0x0b,0x0d,0x0e};
unsigned int current_depth=1;
unsigned int tot_nodes=PF;
unsigned int index=0;
class pageframe{
public:
bool r;//reference bit
unsigned int ldtm;//load time
unsigned int time;//time counter
unsigned int frq;
unsigned int pageno;//which page is mapped on this pageframe
pageframe(){
time=frq=pageno=ldtm=0;
r=false;
}
};
class RAM{
int tot_pf;//total no of pageframes
pageframe* pf;
public:
RAM(int no)
{
tot_pf=no;
pf=new pageframe[no];
}
bool isPageThere(unsigned int,unsigned int);
void insertPage_at(int,unsigned int,unsigned int);
void removePage_at(int);
void display();
void reset();
void refresh(int);
int time(int index)
{
return(pf[index].time);
}
int frq(int index)
{
return(pf[index].frq);
}
};
bool RAM::isPageThere(unsigned int index,unsigned int ct)
{
for(int i=0;i<tot_pf;i++)
if((pf[i].pageno)==index)
{
pf[i].frq/=2;
if(pf[i].r)
pf[i].frq+=(unsigned int)pow(2,2*PF-1);
pf[i].r=true;//reference bit is made true
pf[i].ldtm=ct;//load time is changed
pf[i].time=mask[i];
//cout<<i<<"'s time..."<<pf[i].time<<endl;
for(int j=0;j<tot_pf;j++)
if(j!=i)
{
pf[j].frq/=2;
if(pf[j].r)
pf[j].frq+=(unsigned int)pow(2,2*PF-1);
pf[j].time &=mask[i];
// cout<<j<<"'s time..."<<pf[i].time<<endl;
}
return true;
}
return false;
}
/*bool RAM::insert(int pno)
{
for(int i=0;i<tot_pf;i++)
if((pf[i].pageno)==-1)
{
pf[i].pageno=pno;
return true;
}
return false;
}*/
void RAM::insertPage_at(int index,unsigned int pno,unsigned int ct)
{
pf[index].pageno=pno;
pf[index].frq=(unsigned int)pow(2,2*PF-1);
pf[index].r=true;
pf[index].time=mask[index];
pf[index].ldtm=ct;
for(int i=0;i<tot_pf;i++)
if(i!=index)
{
pf[i].time &=mask[index];
pf[i].frq/=2;
if(pf[i].r)
pf[i].frq+=(unsigned int)pow(2,2*PF-1);
}
}
void RAM::removePage_at(int index)
{
pf[index].pageno=0;
}
void RAM::display()
{
cout<<"page no"<<" "<<"frq."<<" "<<"time"<<endl;
for(int i=0;i<tot_pf;i++)
cout<<pf[i].pageno<<" "<<pf[i].frq<<" "<<pf[i].time<<endl;
cout<<endl;
}
void RAM::reset()
{
for(int i=0;i<tot_pf;i++)
{
pf[i].frq=pf[i].time=pf[i].pageno=pf[i].ldtm=0;
pf[i].r=false;
}
}
void RAM::refresh(int tm)
{
for(int i=0;i<tot_pf;i++)
if((tm-pf[i].ldtm)==(2*PF))
{
pf[i].frq=0;
pf[i].r=false;
}
}
pageframe pf[PF];
RAM ram(PF);
template<class t>
class tree;
template<class t>
class node
{
friend class tree<t>;
public:
t* data;
node<t>* left;
node<t>* right;
node()
{
data=new t;
left=right=0;
}
friend ostream& operator <<(ostream& o,node<t>& n);
unsigned int evaluate();
void setvalues(int fl=0)
{
data->setvalues(fl);
}
void cp(node<t>*);
};
template<class t>
unsigned int node<t>::evaluate ()
{
if(!left)//leaf node
{
unsigned int tmp=index;
if((*data)*index<(*data)*(index+1))
tmp=index;
else
tmp=index+1;
index+=2;//next 2 nos.
return tmp;
}
unsigned int tmp_left;
unsigned int tmp_right;
tmp_left=left->evaluate();
tmp_right=right->evaluate();
return(((*data)*(tmp_left)<(*data)*(tmp_right))?tmp_left:tmp_right);
}
template<class t>
void node<t>::cp (node<t>* s)
{
if(!s)
return ;
*(s->data)=*(this->data);
(this->left)->cp(s->left);
(this->right)->cp(s->right);
}
template<class t>
ostream& operator <<(ostream& o,node<t>& n)
{
o<<(*(n.data));
return o;
}
template <class t>
class tree
{
protected:
unsigned int depth;
void generate(node<t>*);
node<t>* root;
/* temp variables used in generation of trees */
public:
tree()
{
root=0;
}
tree(unsigned int d)
{
root=new node<t>;
depth=d;
generate(root);
tot_nodes=PF;
current_depth=1;
}
void inorder();
void inorder(node<t>*);
unsigned int evaluate();
};
template<class t>
void tree<t>::generate(node<t>* p)
{
if(current_depth<depth && tot_nodes>2)
{
p->left=new node<t>;
current_depth++;
generate(p->left);
current_depth--;//backtrack
}
else
{
tot_nodes-=2;//1 leaf node will (operator node) operate on max. 2 PF's
return;
}
if(tot_nodes>0)
{
p->right=new node<t>;
current_depth++;
generate(p->right);
current_depth--;
}
}
template<class t>
void tree<t>::inorder ()
{
inorder(root);
}
template<class t>
void tree<t>::inorder (node<t>* p)
{
if(!p)
return;
inorder(p->left);
best<<(*p);
inorder(p->right);
}
/*CLASS GPTREE*/
template<class t>
class gptree:public tree<t>
{
public:
gptree(unsigned int d):tree<t>(d)
{
pf=new unsigned int[TOTSTR];
}
unsigned int *pf;
double fitness;
unsigned int evaluate();
void crossover(gptree*);
void calc_fit();
void mycopy(gptree<t>*);
void makelru();
void makelru(node<t>*);
void makelfu();
void makelfu(node<t>*);
};
template<class t>
unsigned int gptree<t>::evaluate()
{
return (root->evaluate());
}
template<class t>
void gptree<t>::crossover (gptree<t>* tr)
{
unsigned int d=0;
while(!d)
d=rand()%depth;//DEPTH AT WHICH THE CUT WILL BE PUT
node<t>* p1=root;
node<t>* p2=tr->root;
node<t>*ptr;
if(!d)
return;
for(unsigned int i=1;i<d;i++)
if(rand()%2==LEFT)
{
p1=p1->left;
p2=p2->left;
}
else
{
p1=p1->right;
p2=p2->right;
}
p1->setvalues();//RANDOMLY SETTING THE WTs AND WFs
p2->setvalues();
if(rand()%2==LEFT)
{
ptr=p1->left;
p1->left=p2 ->left;
p2->left =ptr;
}
else
{
ptr=p1->right;
p1->right=p2 ->right;
p2->right =ptr;
}
}
template<class t>
void gptree<t>::calc_fit ()
{
double sd=0,mean=0;
for(int i=0;i<TOTSTR;i++)
mean+=pf[i];
mean/=TOTSTR;
//cout<<"mean is... "<<mean<<" ";
for(i=0;i<TOTSTR;i++)
sd+=pow((pf[i]-mean),2);
sd=sqrt(sd);
//cout<<"sd is... "<<sd;
fitness=mean;//(STRLN-mean)/sd;
//cout<<"fit is... "<<fitness<<endl;
}
template<class t>
void gptree<t>::mycopy(gptree<t>* rt)
{
(rt->fitness)=(this->fitness);
root->cp(rt->root);
}
template<class t>
void gptree<t>::makelru ()
{
makelru(root);
}
template<class t>
void gptree<t>::makelru(node<t>*p)
{
if(!p)
return;
makelru(p->left);
p->setvalues (LRU);
makelru(p->right);
}
template<class t>
void gptree<t>::makelfu ()
{
makelfu(root);
}
template<class t>
void gptree<t>::makelfu(node<t>*p)
{
if(!p)
return;
makelfu(p->left);
p->setvalues (LFU);
makelfu(p->right);
}
class weight
{
public:
double wt;
double wf;
weight()
{
wt=(double)(rand())/RAND_MAX;
wf=(double)(rand())/RAND_MAX;
}
void setvalues(int fl=0)
{
switch(fl)
{
case 0:
wt=(double)(rand())/RAND_MAX;
wf=(double)(rand())/RAND_MAX;
break;
case LRU:
wt=1;
wf=0;
break;
case LFU:
wt=0;
wf=1;
break;
}
}
friend ostream& operator <<(ostream& o,weight& n);
friend double operator *(weight&,unsigned int);
};
ostream& operator<<(ostream& o,weight& n)
{
o<<"wf = "<<n.wf<<"wt = "<<n.wt <<endl;
return o;
}
double operator *(weight& w,unsigned int index)
{
return(w.wt * ram.time (index)/(pow(2,PF)-1)+w.wf * ram.frq (index)/(pow(2,2*PF)-1));
}
unsigned int curtime=0,tmp_depth;
unsigned int *refstring;
float cross_prob;
fstream report,best;
gptree<weight>* gp[GPNO];
gptree<weight>* lru,*lfu;
void crossover()
{
unsigned int no;
no=(unsigned int) (GPNO*cross_prob);
if((no%2)!=0)
no--;
gptree<weight>* tmp;
tmp=new gptree<weight>(tmp_depth);
for(unsigned int i=0;i<GPNO;i++) //SORTING ACCORDING TO FITNESS
for(unsigned int j=i+1;j<GPNO;j++)
if((gp[i]->fitness)>(gp[j]->fitness))
{
gp[i]->mycopy(tmp);
gp[j]->mycopy(gp[i]);
tmp->mycopy(gp[j]);
}
for(i=1;i<=no;i++)
{
gp[i]->mycopy(gp[GPNO-i]);
}
delete tmp;
for(i=1;i<no;i+=2)
gp[GPNO-i]->crossover(gp[GPNO-i-1]);
}
/*EVALUATES EACH GPTREE*/
unsigned int evaluate()
{
double ave=0;
for(int k=0;k<TOTSTR;k++)
{
unsigned int min;
min=STRLN;
for(int j=0;j<GPNO;j++)
{
unsigned int pagefaults,victim;
pagefaults=0;
ram.reset(); //RESETS THE COUNTERS FOR THE NEW GPTREE
curtime=0;
for(int i=(k*STRLN);i<(k*STRLN+STRLN);i++)
{
curtime++;
ram.refresh(curtime);//UPDATES THE TIME COUNTER
if(ram.isPageThere(refstring[i],curtime))
continue;
else
{
pagefaults++;
victim=gp[j]->evaluate ();
index=0;
ram.insertPage_at(victim,refstring[i],curtime);
}
} //NEXT PAGEREFRENCE
(gp[j]->pf[k])=pagefaults;
//if(pagefaults<min)
// min=pagefaults;
} //NEXT GPTREE
//cout<<"minimum no. of pagefaults for refstr... "<<k<<" "<<min<<endl;
} //NEXT REFSTRING
double min;
unsigned int mini;
min=STRLN;
for(int i=0;i<GPNO;i++)
{
gp[i]->calc_fit();
if((gp[i]->fitness)<min)
{
min=gp[i]->fitness ;
mini=i;
}
ave+=gp[i]->fitness ;
}
ave/=GPNO;
cout<<"average fitness..."<<ave<<endl<<endl;
cout<<"best fitness..."<<min<<endl<<endl;
report<<"average fitness..."<<ave<<endl<<endl;
report<<"best fitness..."<<min<<endl<<endl;
return mini;
} //EVALUATE
void Lru()
{
double ave=0;
for(int k=0;k<TOTSTR;k++)
{
unsigned int pagefaults=0,victim;
ram.reset(); //RESETS THE COUNTERS FOR THE NEW GPTREE
curtime=0;
for(int i=(k*STRLN);i<(k*STRLN+STRLN);i++)
{
curtime++;
ram.refresh(curtime);//UPDATES THE TIME COUNTER
if(ram.isPageThere(refstring[i],curtime))
continue;
else
{
pagefaults++;
victim=lru->evaluate ();
index=0;
ram.insertPage_at(victim,refstring[i],curtime);
}
} //NEXT PAGEREFRENCE
lru->pf[k]=pagefaults;
cout<<"No. of pagefaults for LRU... "<<pagefaults<<" "<<pagefaults<<endl;
} //NEXT REFSTRING
lru->calc_fit();
report<<"LRU's fitness (Ave. no of pagefaults)..."<<(lru->fitness)<<endl<<endl;
}
void Lfu()
{
double ave=0;
for(int k=0;k<TOTSTR;k++)
{
unsigned int pagefaults=0,victim;
ram.reset(); //RESETS THE COUNTERS FOR THE NEW GPTREE
curtime=0;
for(int i=(k*STRLN);i<(k*STRLN+STRLN);i++)
{
curtime++;
ram.refresh(curtime);//UPDATES THE TIME COUNTER
if(ram.isPageThere(refstring[i],curtime))
continue;
else
{
pagefaults++;
victim=lfu->evaluate ();
index=0;
ram.insertPage_at(victim,refstring[i],curtime);
}
} //NEXT PAGEREFRENCE
lfu->pf[k]=pagefaults;
cout<<"No. of pagefaults for LFU... "<<pagefaults<<" "<<pagefaults<<endl;
} //NEXT REFSTRING
lfu->calc_fit();
report<<"LFU's fitness (Ave. no of pagefaults)..."<<(lfu->fitness)<<endl<<endl;
}
void main()
{
report.open("gp.txt",ios::out);
best.open("best.txt",ios::out);
tmp_depth=unsigned int(ceil(log(PF)/log(2)));//CALCULATES THE MAX. DEPTH FOR THE GPTREE
//cout<<"depth is..."<<tmp_depth<<endl;
cross_prob=2;
while(cross_prob>1)
{
cout<<"cross-over prob. is ... ";
cin>>cross_prob;
}
unsigned int tmp=STRLN*TOTSTR,bestgp;
refstring=new unsigned int[tmp];
for(int i=0;i<(STRLN*TOTSTR);i++)
refstring[i]=((rand()%10)+1);
for(i=0;i<GPNO;i++)
gp[i]=new gptree<weight>(tmp_depth);
lru=new gptree<weight>(tmp_depth);
lfu=new gptree<weight>(tmp_depth);
lru->makelru();//CONVERTS THE GP TREE IN AN LRU TREE
lfu->makelfu();
Lru();
Lfu();
getch();
for(int n=0;n<GENERATIONS;n++)
{
cout<<"GENERATION : "<<n+1<<endl<<endl;
report<<"GENERATION : "<<n+1<<endl<<endl;
bestgp=evaluate();
best<<"BEST OF GENERATION : "<<n+1<<endl<<endl;
gp[bestgp]->inorder();
crossover();
}
for(n=0;n<GPNO;n++)
best<<(gp[n]->fitness)<<endl;
report.close();
best.close();
}//MAIN
/*for(j=0;j<GPNO;j++)
{
unsigned int pagefaults=0,victim;
gp[j]=new gptree<weight>(tmp_depth);
ram.reset();
// ram.display();
//getch();
for(i=0;i<STRLN;i++)
{
curtime++;
ram.refresh(curtime);
if(ram.isPageThere(refstring[i],curtime))
continue;
else
{
pagefaults++;
//ram.display();
victim=gp[j]->evaluate ();
index=0;
//cout<<"victim is..."<<victim<<endl;
//getch();
ram.insertPage_at(victim,refstring[i],curtime);
}
}
cout<<"no of pf..."<<pagefaults<<endl;
ram.reset();
}*/