Sunday, March 23, 2014

Next Fit (Memory Allocation) : OS Design

#include <iostream.h>
#include <conio.h>

//Implementing next fit memory management pattern

/*
*allocate method will be used to allocate the memory after taking user input in main
*/
void allocate(const int *blockSize, int &blocks, const int *procImageSize, int &processes)
{
int *allocVectorPro = new int[processes];
int *allocVectorMem = new int[blocks];
for(int i=0;i<processes;++i)
{
allocVectorPro[i] = -1;    //no process has yet been allocated
allocVectorMem[i] = -1; //no memory block has yet been allocated
}

int mem=0;
for(int pro=0;pro<processes;++pro)
{
for(;mem<blocks;)
{
if(blockSize[mem]>=procImageSize[pro])
{
allocVectorMem[mem]=1;
allocVectorPro[pro]=mem++;
break;
}
mem++;
}
}
cout<<"\n::::::\nAllocation complete\n::::::\n";

//displaying
for(int v5=0;v5<processes;++v5)
{
static int once=1;
if(v5>=blocks)
{
if(once)
{cout<<endl;once=0;}
cout<<"Process "<<v5+1<<" couldn't be allocated - No more memory blocks available!"<<endl;
continue;
}
if(allocVectorPro[v5]!=-1)
{
cout<<"\nProcess "<<v5+1<<" allocated to memory block "<<allocVectorPro[v5]+1;
}
else if(allocVectorPro[v5]==-1)
{
cout<<"\nProcess "<<v5+1<<" did not get into any memory block - what a shame";
}
}
}


int main()
{
clrscr();
int noBlocks = 0;
cout<<"Enter the number of memory blocks: ";
cin>>noBlocks;

int* blockSize = new int[noBlocks];
cout<<endl;
for(int v1=0; v1<noBlocks; ++v1)
{
cout<<"Enter the size of memory block "<<v1+1<<": ";
cin>>blockSize[v1];
}

int noProcs = 0;
cout<<"\nEnter the number of processes: ";
cin>>noProcs;

int* procImageSize = new int[noProcs];
cout<<endl;
for(int v2=0;v2<noProcs;++v2)
{
cout<<"Enter the size of the process image "<<v2+1<<" : ";
cin>>procImageSize[v2];
}

/*
*Dynamic resource allocation and user input code ended here
*
*
*Now call allocate to do the necessary allocation
*/

allocate(blockSize, noBlocks, procImageSize, noProcs);
getch();
return NULL;
}

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