Population

Memory Management

    A. First edition

    This is first edition of my memory management.

    B.The problem

    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.The idea of program
¡¡
The manipulation of link list is a painful job! The simulation of memory is using an array. Actually
¡¡
memory is considered to be linear.
¡¡
The code is no good as there are countless "if else" which I hate most. And merge operation is a
¡¡
little bit tricky! Suppose you have one used chunk of memory that you want to be released. It should
¡¡
be merged with both side if they are free memory. Should I tell you the detail of each bugs I found?

    D.The major functions

    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