Memory Management
A. First edition
This is first edition of my memory management.
In the O.S. memory are just pieces of chunk of memory where several basic operations are implemented.
Allocate: a certain amount of memory are allocated by a certain searching policy. Release: memory are
returned to system and possibly needs to be merged with other consecutive free memory block.
Unused memory are chained up with doubly link list where a "tag" set at both beginning and end. Size
field appears at both ends, a pointer to previous and next unused memory.
C.Further improvement
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
const int MemLength=70;
const int MinFree=6;
const int MinUsed=3;
enum SearchPolicy
{FirstFit, WorstFit, BestFit};
enum MemType
{Free, Used};
class Mem
{
private:
int memory[MemLength];
int freeHead;
// int usedHead;
SearchPolicy searchPolicy;
void doPrint(int usedLength, int freeLength, int pos);
void initialize();
bool firstFit(int& index, int length);
bool worstFit(int& index, int length);
bool bestFit(int& index, int length);
bool findFree(int& index, int length);
void doAllocate(int index, int length);
int findNext(int index);
bool canMerge(int index);
void doMerge(int index);
void insert(int index);
void leftMerge(int index);
void rightMerge(int index);
void doubleMerge(int index);
public:
Mem(SearchPolicy search=FirstFit);
int allocate(int length);
void release(int index);
void print();
};
void doTest(Mem& M, int lst[], int index)
{
if (lst[index]!=-1)
{
M.release(lst[index]);
cout<<"\nnow print result after releasing "<<index<<endl;
M.print();
lst[index]=-1;
}
}
bool addTest(Mem& M, int lst[], int index)
{
int num=rand()%12+1;
if (lst[index]==-1)
{
lst[index]=M.allocate(num);
if (lst[index]==-1)
{
return false;
}
cout<<"\nnow print for add size of"<<num<<endl;
M.print();
return true;
}
return false;
}
const int Length=10;
int usedList[Length]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int main()
{
srand(time(0));
Mem M(BestFit);
for (int i=0; i<Length;i++)
{
addTest(M, usedList, i);
}
cout<<"\nnow release one by one\n";
doTest(M, usedList, 2);
doTest(M, usedList, 5);
doTest(M, usedList, 0);
cout<<"\nnow show the best fit\n";
while (!addTest(M, usedList, 2))
{
}
/*
for (i=0; i<15; i++)
{
int index=rand()%10;
doTest(M, usedList, index);
index=rand()%10;
addTest(M, usedList, index);
}
/*
for (i=Length; i>=0; i--)
{
int index=(i+4)%10;
if (usedList[index]!=-1)
{
M.release(usedList[index]);
cout<<"\nnow print for "<<i<<endl;
M.print();
}
}
*/
cout<<endl;
return 0;
}
void Mem::doubleMerge(int index)
{
int leftSize=memory[index-2];
int size=memory[index+1];
int rightSize=memory[index+size+1];
memory[index-leftSize+1]=memory[index+size+rightSize-2]=size+leftSize+rightSize;
memory[index-leftSize+3]=memory[index+size+3];
}
bool Mem::canMerge(int index)
{
bool result=false;
int size=memory[index+1];//actual size
if (index!=0)
{
result= result||memory[index-1]==Free;
}
if (index+size<MemLength-1)
{
result=result||memory[index+size]==Free;
}
return result;
}
void Mem::leftMerge(int index)
{
int size=memory[index+1];
int leftSize=memory[index-2];
memory[index-leftSize+1]=memory[index+size-2]=size+leftSize;
memory[index+size-1]=memory[index-leftSize]=Free;
}
void Mem::rightMerge(int index)
{
int size=memory[index+1];
int rightSize;
int prev, next;
index+=size;//pointing to right head
rightSize=memory[index+1];
if (memory[index-1]==Free)//already leftMerged!
{
size=memory[index-2];//in case leftmerged!
}
memory[index-size+1]=memory[index+rightSize-2]=size+rightSize;
memory[index+rightSize-1]=memory[index-size]=Free;
prev=memory[index+2];
next=memory[index+3];
memory[index-size+2]=prev;
memory[index-size+3]=next;
memory[prev+3]=index-size;
memory[next+2]=index-size;
if (index==freeHead)
{
freeHead-=size;
}
}
void Mem::doMerge(int index)
{
int size=memory[index+1];
if (index!=0)//possible of double merge
{
if (memory[index-1]==Free&&memory[index+size]==Free)
{
doubleMerge(index);
}
else
{
if (memory[index-1]==Free)
{
leftMerge(index);
}
if (memory[index+size]==Free)
{
rightMerge(index);
}
}
}
else//only possible of right merge
{
if (memory[index+size]==Free)
{
rightMerge(index);
}
}
}
void Mem::insert(int index)
{
int size=memory[index+1];
int start=freeHead;
int next;
//this won't change
memory[index]=memory[index+size-1]=Free;
memory[index+size-2]=size;
//empty list
if (freeHead==-1)
{
freeHead=index;
memory[index+2]=0;//no prev
memory[index+3]=0;
return ;
}
next=memory[start+3];
//right before everything
if (start>index)
{
freeHead=index;
memory[index+2]=0;//no prev
memory[index+3]=start;
memory[start+2]=index;
return;
}
while(start<index&&next<index&&next!=0)
{
start=next;
next=memory[start+3];
}
memory[start+3]=index;//next of prev
if (next!=0)
{
memory[next+2]=index;//prev of next
}
memory[index+2]=start;
memory[index+3]=next;
}
void Mem::release(int index)
{
if (canMerge(index))
{
doMerge(index);
}
else
{
insert(index);
}
}
int Mem::findNext(int index)
{
return memory[index+3];
}
Mem::Mem(SearchPolicy search)
{
searchPolicy = search;
initialize();
}
bool Mem::firstFit(int& index, int length)
{
index=freeHead;
do
{
if (memory[index+1]>length+MinUsed)
{
return true;
}
}while ((index=findNext(index))!=0);
return false;
}
bool Mem::findFree(int& index, int length)
{
switch (searchPolicy)
{
case FirstFit:
return firstFit(index, length);
case WorstFit:
return worstFit(index, length);
case BestFit:
return bestFit(index, length);
}
return false;
}
void Mem::doAllocate(int index, int length)
{
int prev, next, size;
size=memory[index+1];//old size
prev=memory[index+2];
next=memory[index+3];
//set up free old
if (size-length>MinFree)
{
memory[index+length]=Free;
memory[index+length+1]=memory[index+size-2]=size-length;
memory[index+length+2]=prev;
memory[index+length+3]=next;
memory[next+2]=index+length;//update next node
memory[index]=memory[index+length-1]=Used;
memory[index+1]=length;
if (index==freeHead)
{
freeHead+=length;
}
else
{
memory[prev+3]=index+length;
}
if (next!=0)
{
memory[next+2]=index+length;
}
}
else
{
//allocate all free mem
memory[index+1]=size;
memory[index]=memory[index+size-1]=Used;
if (next!=0)
{
memory[next+2]=prev;//next has no prev
if (index==freeHead)
{
freeHead=next;
}
}
else
{
if (index==freeHead)//empty list
{
freeHead=-1;
}
}
if (prev!=0)
{
memory[prev+3]=next;
}
}
}
bool Mem::bestFit(int& index, int length)
{
int min=-1, size, result=freeHead;
index=freeHead;
if (index==-1)
{
return false;
}
do
{
if ((size=memory[index+1]-length-MinUsed)>=0)
{
if (min>=0&&size<min)
{
min=size;
result=index;
}
else
{
if (min<0)//not initialized
{
min = size;//first time
result=index;
}
}
}
}while ((index=findNext(index))!=0);
if (min>=0)
{
index=result;
return true;
}
else
{
return false;
}
}
bool Mem::worstFit(int& index, int length)
{
int max=-1, size, result;
index=freeHead;
if (index==-1)
{
return false;
}
do
{
if ((size=memory[index+1]-length-MinUsed)>=0)
{
if (max>=0&&size>max)
{
max=size;
result=index;
}
else
{
if (max<0)//not initialized
{
max = size;//first time
result=index;
}
}
}
}while ((index=findNext(index))!=0);
if (max>=0)
{
index=result;
return true;
}
else
{
return false;
}
}
int Mem::allocate(int length)
{
int index=freeHead;
if (findFree(index, length))
{
doAllocate(index, length+MinUsed);//allocate more
return index;
}
else
{
return -1;
}
}
void Mem::doPrint(int usedLength, int freeLength, int pos)
{
int limit=pos+usedLength;
int length=memory[pos+1];
while (pos<limit)
{
cout<<setw(2)<<memory[pos+1];
for (int i=2; i<length; i++)
{
cout<<'*';
}
pos+=length;
length=memory[pos+1];
}
if (freeLength!=0)
{
cout<<setw(2)<<memory[pos+1];
for (int i=2; i<freeLength; i++)
{
cout<<' ';
}
}
}
void Mem::print()
{
int index=freeHead;
int pos=0;
int usedLength;
int freeLength;
if (freeHead==-1)
{
doPrint(MemLength, 0, 0);
return;
}
while (true)
{
usedLength=index-pos;
freeLength=memory[index+1];
doPrint(usedLength, freeLength, pos);
pos+=usedLength;
pos+=freeLength;
if (memory[index+3]==0||pos==MemLength)
{
if (pos<MemLength-1)//print extra used chunk
{
freeLength=0;
usedLength=MemLength-pos-1;
doPrint(usedLength, freeLength, pos);
}
return;
}
else
{
index=memory[index+3];
}
}
}
void Mem::initialize()
{
memory[0]=memory[MemLength-1]=Free;
memory[1]=memory[MemLength-2]=MemLength;
memory[2]=0;//the prev
memory[3]=0;//the next
freeHead=0;//pointing to the head;
}
Here is the result:(Note DFS and BFS gives almost opposite result.)
now print for add size of10 13***********57 now print for add size of2 13*********** 5***52 now print for add size of2 13*********** 5*** 5***47 now print for add size of10 13*********** 5*** 5***13***********34 now print for add size of2 13*********** 5*** 5***13*********** 5***29 now print for add size of5 13*********** 5*** 5***13*********** 5*** 8******21 now print for add size of3 13*********** 5*** 5***13*********** 5*** 8****** 6****15 now print for add size of7 13*********** 5*** 5***13*********** 5*** 8****** 6****15************* now release one by one now print result after releasing 2 13*********** 5*** 5 13*********** 5*** 8****** 6****15************* now print result after releasing 5 13*********** 5*** 5 13*********** 5*** 8 6****15************* now print result after releasing 0 13 5*** 5 13*********** 5*** 8 6****15************* now show the best fit now print for add size of4 13 5*** 5 13*********** 5*** 8****** 6****15************* Press any key to continue