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;
}

Best Fit Memory Management : C++ (v2)

// BestFitMemMan.cpp

#include "stdafx.h"
#include <iostream>

using namespace std;

void main()
{
//INFORMATION ABOUT THE PROCESSES
cout<<"Enter the number of processes: ";
int nProc = 0;
cin>>nProc;

cout<<"Enter the size of each process: ";
int data[10][3]; //we assume at most 10 processes

for(int i = 0;i<nProc;++i)
{
cin>>data[i][0]; //size of the process
data[i][1] = 0;  //0 means unallocated
data[i][2] = i;  //id of the process
}

//INFORMATION ABOUT THE MEMORY BLOCKS
cout<<"Enter the number of memory blocks: ";
int nBlocks = 0;
cin>>nBlocks;

cout<<"Enter the size of each block: ";
int dataBlocks[10][2];

for(int i =0;i<nProc;++i)
{
cin>>dataBlocks[i][0];
dataBlocks[i][1] = 0; //0 means unallocated
}

int smallAvail=0, size=0;
//ALLOCATION TO BE DONE HERE
for(int i = 0;i<nProc;++i)
{
for(int j = 0;j<nBlocks;++j)
{
if(data[i][1]==0&&dataBlocks[j][1]==0 /*these test if the block and image are free*/ &&data[i][0]<=dataBlocks[j][0])
{
smallAvail=j;
size=dataBlocks[j][0];
for(int l=j;l<nBlocks;++l)
{
if(dataBlocks[l][0]<size&&dataBlocks[l][0]>=data[i][0]&&dataBlocks[l][1]==0)
{
smallAvail=l;
size=dataBlocks[l][0];
}
}
data[i][1] = 1; //allocated
dataBlocks[smallAvail][1] = 1; //allocated
cout<<"Process id "<<i<<" allocated to memory block: "<<smallAvail<<endl;
}
}
}

for(int i = 0;i<nBlocks;++i)
{
if(data[i][1]==0)
{
cout<<"Process id "<<i<<" unallocated\n";
}
}
}

Worst Fit Memory Management: C++

// WorstFitMemMan.cpp

#include "stdafx.h"
#include <iostream>

using namespace std;

void main()
{
//INFORMATION ABOUT THE PROCESSES
cout<<"Enter the number of processes: ";
int nProc = 0;
cin>>nProc;

cout<<"Enter the size of each process: ";
int data[10][3]; //we assume at most 10 processes

for(int i = 0;i<nProc;++i)
{
cin>>data[i][0]; //size of the process
data[i][1] = 0;  //0 means unallocated
data[i][2] = i;  //id of the process
}

//INFORMATION ABOUT THE MEMORY BLOCKS
cout<<"Enter the number of memory blocks: ";
int nBlocks = 0;
cin>>nBlocks;

cout<<"Enter the size of each block: ";
int dataBlocks[10][2];

for(int i =0;i<nProc;++i)
{
cin>>dataBlocks[i][0];
dataBlocks[i][1] = 0; //0 means unallocated
}

int bigAvail=0, size=0;
//ALLOCATION TO BE DONE HERE
for(int i = 0;i<nProc;++i)
{
for(int j = 0;j<nBlocks;++j)
{
if(data[i][1]==0&&dataBlocks[j][1]==0 /*these test if the block and image are free*/&&data[i][0]<=dataBlocks[j][0])
{
bigAvail=j;
size=dataBlocks[j][0];
for(int l=j;l<nBlocks;++l)
{
if(dataBlocks[l][0]>size&&dataBlocks[l][1]==0)
{
bigAvail=l;
size=dataBlocks[l][0];
}
}
data[i][1] = 1; //allocated
dataBlocks[bigAvail][1] = 1; //allocated
cout<<"Process id "<<i<<" allocated to memory block: "<<bigAvail<<endl;
}
}
}

for(int i = 0;i<nBlocks;++i)
{
if(data[i][1]==0)
{
cout<<"Process id "<<i<<" unallocated\n";
}
}
}

Next Fit Memory Management : C++

// NextFitMemMan.cpp

#include "stdafx.h"
#include <iostream>

using namespace std;

void main()
{
//INFORMATION ABOUT THE PROCESSES
cout<<"Enter the number of processes: ";
int nProc = 0;
cin>>nProc;

cout<<"Enter the size of each process: ";
int data[10][3]; //we assume at most 10 processes

for(int i = 0;i<nProc;++i)
{
cin>>data[i][0]; //size of the process
data[i][1] = 0;  //0 means unallocated
data[i][2] = i;  //id of the process
}

//INFORMATION ABOUT THE MEMORY BLOCKS
cout<<"Enter the number of memory blocks: ";
int nBlocks = 0;
cin>>nBlocks;

cout<<"Enter the size of each block: ";
int dataBlocks[10][2];

for(int i =0;i<nProc;++i)
{
cin>>dataBlocks[i][0];
dataBlocks[i][1] = 0; //0 means unallocated
}

//ALLOCATION TO BE DONE HERE
int j = 0;
for(int i = 0;i<nProc;++i)
{
for(;j<nBlocks;++j)
{
if(dataBlocks[j][1]==0&&data[i][0]<=dataBlocks[j][0])
{
data[i][1] = 1; //allocated
dataBlocks[j][1] = 1; //allocated
cout<<"Process id "<<i<<" allocated to memory block: "<<j<<endl;
break;
}
}
}

for(int i = 0;i<nBlocks;++i)
{
if(data[i][1]==0)
{
cout<<"Process id "<<i<<" unallocated\n";
}
}
}

First Fit Memory Allocation : C++ (v2)

// FirstFitMemMan.cpp

#include "stdafx.h"
#include <iostream>

using namespace std;

void main()
{
//INFORMATION ABOUT THE PROCESSES
cout<<"Enter the number of processes: ";
int nProc = 0;
cin>>nProc;

cout<<"Enter the size of each process: ";
int data[10][3]; //we assume at most 10 processes

for(int i = 0;i<nProc;++i)
{
cin>>data[i][0]; //size of the process
data[i][1] = 0;  //0 means unallocated
data[i][2] = i;  //id of the process
}

//INFORMATION ABOUT THE MEMORY BLOCKS
cout<<"Enter the number of memory blocks: ";
int nBlocks = 0;
cin>>nBlocks;

cout<<"Enter the size of each block: ";
int dataBlocks[10][2];

for(int i =0;i<nProc;++i)
{
cin>>dataBlocks[i][0];
dataBlocks[i][1] = 0; //0 means unallocated
}

//ALLOCATION TO BE DONE HERE
for(int i = 0;i<nProc;++i)
{
for(int j=0;j<nBlocks;++j)
{
if(dataBlocks[j][1]==0&&data[i][1]==0&&data[i][0]<=dataBlocks[j][0])
{
data[i][1] = 1; //allocated
dataBlocks[j][1] = 1; //allocated
cout<<"Process id "<<i<<" allocated to memory block: "<<j<<endl;
}
}
}

for(int i = 0;i<nBlocks;++i)
{
if(data[i][1]==0)
{
cout<<"Process id "<<i<<" unallocated\n";
}
}
}

LRU (Least Recently Used) Page Replacement (Memory Mangement) code : C++

#include "stdafx.h"
#include <iostream>
#define FFOR(i, j) for(int i=0;i<j;++i)
using namespace std;

/*Understandable, at least.*/

class LRU
{
public :
LRU()
{
FFOR(i, 10)
frames[i] = -1;
FFOR(i, 50)
pages[i]=0;

cout<<"Enter the number of pages: ";
cin>>nPages;

cout<<"Enter the number of frames: ";
cin>>nFrames;

cout<<"Enter the page numbers: ";
FFOR(i, nPages)
cin>>pages[i];

FFOR(i, nPages)
timeArr[i][0]=-1;
allocate();
}

void allocate()
{
int avail = 0;
int toReplace = 0;
static int time=0;
FFOR(i, nPages)
{
avail = 0;
time++;
timeArr[pages[i]][0] = time;

FFOR(j, nFrames)
{
if(frames[j] == pages[i])
{
avail = 1;
break;
}
}

if(avail==0)
{
if(frames[toReplace]==-1)
{
frames[toReplace] = pages[i];
toReplace = (toReplace+1) % nFrames;
}
else
{
//calculate toReplace
int min = INT_MAX;

FFOR(j, nFrames)
{
int pageNumber = frames[j];
if(timeArr[frames[j]][0]<min)
{
min=timeArr[frames[j]][0];
toReplace = j;
}
}
frames[toReplace] = pages[i];
}
}
}
display();
}

void display()
{
FFOR(i, nFrames)
{
cout<<frames[i]<<" ";
}
}

private:
int nFrames;
int timeArr[50][1];
int nPages;
int frames[10];
int pages[50];
};

int main()
{
LRU l;
}

FIFO Page Replacement Code (Memory Management) : C++

#include "stdafx.h"
#include <iostream>
/* Warning: Write Only Code : Don't try to understand */
using namespace std;

class Input
{
public:
Input()
{
pageStream = new int[100];
elementsInStream = 0;

cout<<"Number of page frames to be allocated to this process: ";
cin>>nFrames;
pageFrames = new int[nFrames];
for(int i =0;i<nFrames;++i)
{
pageFrames[i] = 0; //need to set explicity, otherwise garbage values prevail
}

getInput();
}

void getInput()
{

cout<<"\nEnter the number of page addresses in stream: ";
cin>>elementsInStream;
cout<<"\nInput Page Address Stream: ";
for(int i =0;i<elementsInStream;++i)
{
cin>>pageStream[i];
}
}

protected:
int *pageStream;
int nFrames;
int *pageFrames;
int elementsInStream;
};

class Allocator:public Input
{
public:
Allocator()
{
age = new int[nFrames];
for(int i= 0;i<nFrames;++i)
age[i]=0;

computation = new int * [elementsInStream];

for(int i = 0;i<elementsInStream;++i)
{
computation[i] = new int[nFrames];
for(int j = 0;j<nFrames;++j)
computation[i][j] = 0;
}

}

bool alreadyPresent(int pageNumber)
{
for(int i =0;i<nFrames;++i)
{
if(pageFrames[i]==pageNumber)
{
return true;
}
}
return false;
}

void allocate()
{

int pageNumber=-1;

int j = 0; //j variable for intialization of blocks (with value 0) in the start

for(int i = 0;i<elementsInStream;++i)
{
pageNumber = pageStream[i];

if(pageFrames[j]==0)
{
if(alreadyPresent(pageNumber))
{
for(int k=0;k<j;++k) //increment the age of previously allocated frames
{
age[k]++;
}

updateComputation(0, 0);
}
else
{
pageFrames[j] = pageNumber;
for(int k=0;k<=j;++k) //increment the age of all allocated frames till now
{
age[k]++;
}
updateComputation(j, pageNumber);
j++;
if(j==nFrames)
j=0; //no page will have number 0 so the check if(pageFrames[j]==0) will be false

}
}

else if(alreadyPresent(pageNumber))
{
for(int i =0;i<nFrames;++i)
age[i]++;

updateComputation(0, 0);
continue;
}

else
{
int toReplace = replaceLongest();
pageFrames[toReplace] = pageNumber;
for(int i =0;i<nFrames;++i)
{
if(i==toReplace)
{
age[toReplace] = 1;
continue;
}
age[i]++;
}

updateComputation(toReplace, pageNumber);
}
}
}

int replaceLongest()
{
int maxAge = -1;
int toReturn = -11; //program halts if incorrect
for(int i =0;i<nFrames;++i)
{
if(age[i]>maxAge)
{
maxAge = age[i];
toReturn = i;
}
}
return toReturn;
}

void updateComputation(int position, int value)
{
static int number = 0;

for(int i = 0;i<nFrames;++i)
{
if(number!=0)
computation[number][i] = computation[number-1][i];
}

if(value!=0) //we want the new column to just be a copy, we don't want any change
computation[number][position] = value;
number++;
}

void display()
{
cout<<endl;
for(int i = 0;i<nFrames;++i)
cout<<pageFrames[i]<<endl;
cout<<endl;
}

void displayComputation()
{
cout<<"\nPage Replacement : First in first out behaviour ->\n";
cout<<endl;
for(int k=0;k<nFrames;++k)
{
cout<<"Frame #"<<k<<" states: ";
for(int i = 0;i<elementsInStream;++i)
{
cout<<computation[i][k]<<" ";
}
cout<<endl<<endl;
}
}

void displayAge()
{
cout<<endl;
for(int i =0;i<nFrames;++i)
cout<<age[i]<<endl;
cout<<endl;
}

private:
int *age;
int **computation;
};

int main()
{
Allocator allocator;

allocator.allocate();
allocator.displayComputation();
return NULL;
}