page.cpp

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>      // std::stringstream
#include <vector>
#include <queue>
#include <set>
#include <list>
#include <algorithm>
#include <fstream>

const int page_size=1;

using namespace std;

void generate_input(const int &n,const int &d,vector<int> &intput_address);
int FIFO(const vector<int> &input_address,const int &no_frames);
int LFU(const vector<int> &input_address,const int &no_frames);
int LRU(const vector<int> &input_address,const int &no_frames);
int second_chance(const vector<int> &input_address,const int &no_frames);
inline void set_to_str(const vector<int> &input_address,string &intput_string);

int main(int argc,char* argv[])
{
	vector<int> intput_address;
	string intput_string;
	int n=3,d=2,max_frame_size=14;
	string input;
	if(argc==3)
	{
		n=atoi(argv[1]);
		d=atoi(argv[2]);
	}
	
	generate_input(n,d,intput_address);
	set_to_str(intput_address,intput_string);
	
	cout<<"select a page replacement to use\n1. FIFO\n2. LFU \n3. LRU\n4. Second chance"<<endl;
	int choice;cin>>choice;
	int no_page_fault;

	ofstream fout;
	switch(choice)
	{
		case 1:
		    fout.open("FIFO.txt");
			fout<<"no. of frames vs no of page faults generated by FIFO Algorithm on ";
			fout<<"refrence seqence: \n"<<intput_string<<"\n";
			fout<<"no. of frames\tno of page faults\n";
			for(int i=1;i<=max_frame_size;i++)
			{
				no_page_fault=FIFO(intput_address,i);
				fout<<"    "<<i<<"\t\t   "<<no_page_fault<<endl;
			}
			break;
		case 2:
			fout.open("LFU.txt");
			fout<<"no. of frames vs no of page faults generated by LFU Algorithm on ";
			fout<<"refrence seqence: \n"<<intput_string<<"\n";
			fout<<"no. of frames\tno of page faults\n";
			for(int i=1;i<=max_frame_size;i++)
			{
				no_page_fault=LFU(intput_address,i);
				fout<<"    "<<i<<"\t\t   "<<no_page_fault<<endl;
			}
			break;		
		case 3:
			fout.open("LRU.txt");
			fout<<"no. of frames vs no of page faults generated by LRU Algorithm on ";
			fout<<"refrence seqence: \n"<<intput_string<<"\n";
			fout<<"no. of frames\tno of page faults\n";
			for(int i=1;i<=max_frame_size;i++)
			{
				no_page_fault=LRU(intput_address,i);
				fout<<"    "<<i<<"\t\t   "<<no_page_fault<<endl;
			}
			break;
		case 4:
			fout.open("second_chance.txt");
			fout<<"no. of frames vs no of page faults generated by second_chance Algorithm on ";
			fout<<"refrence seqence: \n"<<intput_string<<"\n";
			fout<<"no. of frames\tno of page faults\n";
			for(int i=1;i<=max_frame_size;i++)
			{
				no_page_fault=second_chance(intput_address,i);
				fout<<"    "<<i<<"\t\t   "<<no_page_fault<<endl;
			}
			break;				
	}
	

}	
inline void set_to_str(const vector<int> &input_address,string &intput_string)
{
	std::stringstream sstm;

	for(vector<int>::const_iterator it=input_address.begin();it!=input_address.end();it++)
	{
		sstm<<*it<<" ";
		
	}
	intput_string+=sstm.str();
}

void generate_input(const int &n,const int &d,vector<int> &intput_address)
{
	int prev1,prev2,prev3,count=0;
	int a[n][n];
	int b[n][n];
	int c[n][n];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i==0&&j==0){
			a[i][j]=101;
			b[i][j]=501;
			c[i][j]=1001;
			prev1=a[i][j];
			prev2=b[i][j];
			prev3=c[i][j];
			count++;
			}
			else if(count<d)
			{
				a[i][j]=prev1;
				b[i][j]=prev2;
				c[i][j]=prev3;
				prev1=a[i][j];
				prev2=b[i][j];
				prev3=c[i][j];
				count++;
			}
			else
			{
				a[i][j]=prev1+1;
				b[i][j]=prev2+1;
				c[i][j]=prev3+1;
				prev1=a[i][j];
				prev2=b[i][j];
				prev3=c[i][j];
				count=1;
			}

		}
	}

	int i,j,k;

	for (i = 0; i < n; i++) 
	{
		for (j = 0; j < n; j++) 
		{
			for (k = 0; k < n; k++) 
			{	
				if((intput_address.size()==0)?true:intput_address.back()!=a[i][k])
				 	intput_address.push_back(a[i][k]/page_size);	
				if((intput_address.size()==0)?true:intput_address.back()!=b[i][k])
				 	intput_address.push_back(b[k][j]/page_size);	
			}
			if((intput_address.size()==0)?true:intput_address.back()!=c[i][k])
			 	intput_address.push_back(c[i][j]/page_size);
		}
	}
}
int FIFO(const vector<int> &input_address,const int &no_frames)
{
	queue<int> queue_pages;
	set<int> set_pages;
	int no_page_fault=0;

	for(vector<int>::const_iterator it=input_address.begin();it!=input_address.end();it++)
	{
		if(set_pages.find(*it)==set_pages.end()) //  page is not in the memory
		{
			no_page_fault++;
			if(queue_pages.size()<no_frames) // current pages are smaller than that can be occupied
			{
				queue_pages.push(*it);
				set_pages.insert(*it);
			}
			else // replace top page
			{
				set_pages.erase(queue_pages.front());
				queue_pages.pop();
				queue_pages.push(*it);
				set_pages.insert(*it);
			}
		}
	}
	return no_page_fault;	

}
class CompareDist
{
public:
	   bool operator()(pair<int,int> n1,pair<int,int> n2)
	   {
	   	      if(n1.second>n2.second)
	   	      	return false;
	   	      else
	   	      	return true;	
	   }
};
int LFU(const vector<int> &input_address,const int &no_frames)
{
	// cout<<no_frames<<endl;
	vector<pair<int,int> > queue_pages;
	set<int> set_pages;
	int no_page_fault=0;
	CompareDist compobj;

	for(vector<int>::const_iterator it=input_address.begin();it!=input_address.end();it++)
	{
		if(set_pages.find(*it)==set_pages.end()) //  page is not in the memory
		{
			no_page_fault++;
			if(queue_pages.size()<no_frames) // current pages are smaller than that can be occupied
			{
				queue_pages.push_back(make_pair(*it,1));
				set_pages.insert(*it);
			}
			else // replace LFU page
			{
				// find element to be removed
				sort(queue_pages.begin(), queue_pages.end(),compobj);	
				set_pages.erase(queue_pages.front().first);
				queue_pages.erase(queue_pages.begin());
				queue_pages.push_back(make_pair(*it,1));
				set_pages.insert(*it);
			}
		}
		else
		{
			for(vector<pair<int,int> >::iterator it1=queue_pages.begin();it1!=queue_pages.end();it1++)
			{	
				if(it1->first==*it)
				{
					it1->second+=1; break;
				}
			}

		}
	}
	sort(queue_pages.begin(), queue_pages.end(),compobj);	
	return no_page_fault;
}
int LRU(const vector<int> &input_address,const int &no_frames)
{
	list<int>  queue_pages;
	set<int> set_pages;
	int no_page_fault=0;
	// CompareDist compobj;

	for(vector<int>::const_iterator it=input_address.begin();it!=input_address.end();it++)
	{
		if(set_pages.find(*it)==set_pages.end()) //  page is not in the memory
		{
			no_page_fault++;
			if(queue_pages.size()<no_frames) // current pages are smaller than that can be occupied
			{
				queue_pages.push_back(*it);
				set_pages.insert(*it);
			}
			else // replace LFU page
			{
				// find element to be removed
				set_pages.erase(queue_pages.front());
				queue_pages.pop_front();
				queue_pages.push_back(*it);
				set_pages.insert(*it);
			}
		}
		else
		{
			for(list<int>::iterator it1=queue_pages.begin();it1!=queue_pages.end();it1++)
			{	
				if(*it1==*it)
				{
					// it1->second+=1; break;
					queue_pages.erase(it1);
					queue_pages.push_back(*it1);
				}
			}

		}
	}
	return no_page_fault;
}

int second_chance(const vector<int> &input_address,const int &no_frames)
{

	list<pair<int,int> > queue_pages;
	set<int> set_pages;
	int no_page_fault=0;

	for(vector<int>::const_iterator it=input_address.begin();it!=input_address.end();it++)
	{
		if(set_pages.find(*it)==set_pages.end()) //  page is not in the memory
		{
			no_page_fault++;
			if(queue_pages.size()<no_frames) // current pages are smaller than that can be occupied
			{
				queue_pages.push_back(make_pair(*it,1));
				set_pages.insert(*it);
			}
			else // replace LFU page
			{
				// find element to be removed
				list<pair<int,int> >::iterator prev=queue_pages.end();
				for(list<pair<int,int> >::iterator it1=queue_pages.begin();it1!=queue_pages.end();it1++)
				{	
					if(prev!=queue_pages.end())
					{
						queue_pages.erase(prev);
					}
					if(it1->second==0)  // replace this
					{
						set_pages.erase(it1->first);
						queue_pages.erase(it1); //is_replaced=true;
						break;
					}
					else
					{
						// 
						queue_pages.push_back(make_pair(it1->first,0));
						prev=it1;
					}
				}
				queue_pages.push_back(make_pair(*it,1));
				set_pages.insert(*it);
			}
		}
		else
		{
			for(list<pair<int,int> >::iterator it1=queue_pages.begin();it1!=queue_pages.end();it1++)
			{	
				if(it1->first==*it)
				{
					it1->second=1; break;
				}
			}

		}
	}
	return no_page_fault;
}