22 Responses to “C Program for Optimal Page Replacement Algorithm” kiran March 14, 2016. Thank u so much. Reply; Doug May 15, 2017. I have been looking for a c implementation of the optimal page replace algorithm, but none of them really allowed me to understand how it works because the code was so hard to fully grasp. So, I made my own. All the programmes below are in 'C' and use file handling.There will be sub headings related to the Page replacement algorithms and below them are the corresponding code snippets.The code once compiled runs automatically using the data from text file and displays the output.Tested for DevCPP and codeblocks in Windows.Just be careful to keep the input text file in the same folder as programmes.
Active2 years, 4 months ago
I am writing a program that does 3 page replacement algorithms. FIFO, LRU, and OPTI am assuming 'demand' paging here.
I have FIFO, and LRU finished. But i have no idea on how to tackle OPT. I prompting for a file that i am reading in and parsing line by line into pid and a ref number thats in a class. I am also prompting for the frame size.
File is structured like this:
For the LRU i used a second array to keep track of the least recently used slot with a counter.
I am just not sure what to do for opt. Do i need to look ahead in file i am parsing?Do i need a second array?
I am parsing the file line by line and adding it to the class as follows. This is what i did for the other 2 algorithms and will need to parse the file line by line and prompt for frame size. I could store the file in an array and process the array i guess.
and in main()
im just not sure what to do when if im parsing the file and the cache is full and the number thats in the file is not in the cache how do i know where to put it? Can you explain in coding terms.
Whats the way to go about this in coding it with arrays? Do i keep a counter in a second array?Can someone please explain the easiest way of doing this?
Keep in mind that the file can be hundreds of lines long.
user249375
1 Answer
Not clear what you mean by 'optimum'. The most optimum replacement algorithm would be omniscient and would know in advance what order future pages will be referenced.
If you're assuming 'demand' paging, you'd pick for replacement the the page that will next be referenced the greatest distance in the future.
If you also assume omniscient predictive paging it probably gets more complicated -- I don't know if there's a simple rule or not.
If you don't assume omniscience, then 'optimum' would presumably be driven by paging statistics, and you'd pick for replacement the page that was statistically least likely to be referenced in the future.
Hot LicksHot Licks38.8k1515 gold badges8181 silver badges135135 bronze badges
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<<'tttt';
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<<'nnPage Address StreamttFrames' contentsn';
cout<<' tt';
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<<'nn';
for(int i =0;i<nFrames;++i)
{
cout<<'Frame #'<<i<<' : '<<frames[i]<<endl;
}
cout<<'Number of page faults: '<<nFaults<<endl;
}
// OptimalPageReplacement.cpp
#include 'stdafx.h'
#include <iostream>
using namespace std;
int nFrames=0;
int frames[10];
void display(int streamMember)
{
cout<<endl<<streamMember<<'tttt';
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<<'nnPage Address StreamttFrames' contentsn';
cout<<' tt';
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<<'nn';
for(int i =0;i<nFrames;++i)
{
cout<<'Frame #'<<i<<' : '<<frames[i]<<endl;
}
cout<<'Number of page faults: '<<nFaults<<endl;
}