Monday, April 7, 2014

Optimal Page Replacement: C++

The optimal policy selects for replacement that page for which the time to the next reference is the longest. It can be shown that this policy results in the fewest number of page faults. Clearly, this policy is impossible to implement, because that would require the operating system to have the perfect knowledge of future events. However, we give it a try (assuming that we know the future page references).

// OptimalPageReplacement.cpp
#include "stdafx.h"
#include <iostream>

using namespace std;

int nFrames=0;
int frames[10];

void display(int streamMember)
{
cout<<endl<<streamMember<<"\t\t\t\t";
for(int i  =0;i<nFrames;++i)
{
cout<<frames[i]<<"\t";
}
}

void main()
{
cout<<"Enter the number of page frames: ";
cin>>nFrames;

for(int i =0;i<nFrames;++i)
{
frames[i] = -1;
}

cout<<"Enter the number of elements in page address stream: ";
int nStream = 0;
cin>>nStream;

cout<<"Input the page address stream: ";
int stream[50];
for(int i = 0;i<nStream;++i)
{
cin>>stream[i];
}

cout<<"\n\nPage Address Stream\t\tFrames' contents\n";
cout<<"                   \t\t";
for(int i=0;i<nFrames;++i)
{
cout<<i<<"\t";
}
cout<<endl<<endl;


int nFaults = 0;
int point = 0;
for(int i  =0;i<nStream;++i)
{
if(frames[point]==-1)
{
int flag = 1;
for(int j=0;j<nFrames;++j)
{
if(frames[j]==stream[i])
{
display(stream[i]);
flag = 0;
break;
}
}
if(flag)
{
frames[point] = stream[i];
display(stream[i]);
point = (point+1)%nFrames;
}
}
else
{
int flag = 1;
for(int j=0;j<nFrames;++j)
{
if(frames[j]==stream[i])
{
display(stream[i]);
flag = 0;
break;
}
}
if(flag)
{
nFaults++;
int *nextAccess = new int[nFrames];
for(int i = 0;i<nFrames;++i)
nextAccess[i] = -1;

int index = i;
for(int j=0;j<nFrames;++j)
{
for(;index<nStream;++index)
{
if(frames[j]!=stream[index])
{
nextAccess[j]++;
}
else
break;
}
}

int max = INT_MIN;
int indexMax = -1;
for(int j=0;j<nFrames;++j)
{
if(nextAccess[j]>max)
{
max = nextAccess[j];
indexMax = j;
}
}

frames[indexMax] = stream[i];
display(stream[i]);
}
}
}

cout<<"\n\n";
for(int i =0;i<nFrames;++i)
{
cout<<"Frame #"<<i<<" : "<<frames[i]<<endl;
}
cout<<"Number of page faults: "<<nFaults<<endl;
}

No comments:

Post a Comment