Solved

Buddy Memory Allocation Program how to delete

Posted on 2011-02-15
9
952 Views
Last Modified: 2012-05-11
Hello Everyone,

I am writing a Linked List Buddy Memory Allocation Program.  It is more of a simulation of a buddy memory allocation program there is no actual memory tampering.  I have a list the size of 8 blocks.  One block is initialized to 256 which is the largest allocatable block.  I have two lists one is FreeList which is the block initialized with 256 and AllocatedList which will hold the numerical value that is allocated from the FreeList. Also the blocks are allocated by 2 to the power 0 - 2 to the power of 7(That is why there are 8 blocks).   If the user enter in some value the AllocatedList class will find the block in FreeList which has the closest value to the user input.  For example, if the user enter a value of 52 the allocated block size will be 64.  What I am stuck on is how can I let the user enter in a value to delete memory and free up the block size that is closest to the value and combine any other blocks that are free with the newly free block.  The thing is all of the blocks must have a number ranging from 1-32, 33-65.  For every block that is getting split the numbers should keep on increasing.  So the only values that can be combined are the numbers that are sequential next to each other.  I am confused on how I can implement this into my code.  Any help would be greatly appreciated.
FreeList.h-------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
	FreeList(int, int);
	FreeList(int);
	FreeList();
	int getBlockSize();
	void setBlockSize(int);
	void setOrderNumber(int);
	int getOrderNumber();

	void setLeftBlock(int);
	void setRightBlock(int);

	int getLeftBlock();
	int getRightBlock();
	
	bool operator<(FreeList&);
	bool operator<=(FreeList&);
	bool operator==(FreeList&);
	bool operator==(int);


private:
	
	int sizeOfBlock;
	int orderNumber;
	int leftBlock;
	int rightBlock;
	


};
#endif

Freelist.cpp---------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber)
{
	setBlockSize(size);
	setOrderNumber(seqNumber);

	setLeftBlock(size);
	setRightBlock(0);

}

FreeList::FreeList(int size)
{
	sizeOfBlock = size;


}

FreeList::FreeList()
{
	sizeOfBlock =0;

}


bool FreeList::operator<=(FreeList &list)
{

	return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
	return getBlockSize() == list.getBlockSize();

}


bool FreeList::operator==(int amountOfMemory)
{

	return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
	return getBlockSize() < list.getBlockSize();
}


void FreeList::setBlockSize(int amountOfMemory)
{
	sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
	return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
	orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
	return orderNumber;
}

void FreeList::setLeftBlock(int size)
{
	leftBlock = size;
}

void FreeList::setRightBlock(int size)
{
	rightBlock = size;
}

int FreeList::getLeftBlock()
{
	return leftBlock;
}

int FreeList::getRightBlock()
{
	return rightBlock;
}


 

AllocatedList.h--------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
	friend ostream &operator<<(ostream&,FreeList&);
public:
	AllocatedList();
	void checkMemory(int);
	void deleteMemory(int);
	static bool compareSizeOfBlocks(int&, FreeList&);

	bool greater_than_amountOfMemory(int,FreeList);


private:
	list<int>listOfMemory;
	list<FreeList> listOfFreeList;
	int totalMemory;
	int memoryAllocated;
	list<FreeList>allocatedList;
	
};
#endif


AllocatedList.cpp------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"

AllocatedList::AllocatedList()
{
	totalMemory = 256;
	memoryAllocated = 0;
	//Defining the Free List
	FreeList twoPow7(256,0);
	FreeList twoPow6(0,1);
	FreeList twoPow5(0,2);
	FreeList twoPow4(0,3);
	FreeList twoPow3(0,4);
	FreeList twoPow2(0,5);
	FreeList twoPow1(0,6);
	FreeList twoPow0(0,7);

	


	//Add each element to the Linked List
	listOfFreeList.push_back(twoPow7);
	listOfFreeList.push_back(twoPow6);
	listOfFreeList.push_back(twoPow5);
	listOfFreeList.push_back(twoPow4);
	listOfFreeList.push_back(twoPow3);
	listOfFreeList.push_back(twoPow2);
	listOfFreeList.push_back(twoPow1);
	listOfFreeList.push_back(twoPow0);


	allocatedList.assign(8,0);

}

 bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{
	
	return amountOfMemory <= listOfFreeList.getBlockSize();

}

 


void AllocatedList::checkMemory(int amountOfMemory)
{
	list<FreeList>::iterator current;
	list<FreeList>::iterator next;
	vector<int> vectorFreeList;
	


	
	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getLeftBlock() >= amountOfMemory || IterFreeList->getRightBlock() >= amountOfMemory)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			//Add the memory to the allocated list
			listOfMemory.push_back(amountOfMemory);
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = listOfFreeList.begin();
			
			advance(current, vectorFreeList[0]);
			next = current;
			advance(next, 1);
			

			for(;next != listOfFreeList.end(); next++, current++)
			{
			
				if(current->getLeftBlock()> amountOfMemory && current->getRightBlock() < amountOfMemory)
				{
					//left side of the nodes

					if((current->getLeftBlock()/2) >= amountOfMemory)
					{
						//current is pointing to the first object with an amount
						//greater than amountOfMemory
						current->setLeftBlock((current->getLeftBlock()/2));
						current->setRightBlock((current->getLeftBlock()));
						
						if(current->getRightBlock()/2 >= amountOfMemory)
						{
						 next->setLeftBlock(current->getRightBlock());
						 next->setRightBlock(current->getRightBlock());
						 current->setRightBlock(0);
						}

					
					}


					else if ((current->getLeftBlock()/2) < amountOfMemory)
					{
						memoryAllocated = current->getLeftBlock();

						list<FreeList>::iterator iterAllocatedList=allocatedList.begin();

						advance(iterAllocatedList, current->getOrderNumber());

						iterAllocatedList ->setLeftBlock(current->getLeftBlock());

						current->setLeftBlock(0);

						break;

					}

					
				
			
				}

				//Right values for the nodes

				if(current->getRightBlock()>= amountOfMemory)
				{

					if((current->getRightBlock()/2) >= amountOfMemory)
					{
						//current is pointing to the first object with an amount
						//greater than amountOfMemory
						current->setLeftBlock(current->getRightBlock()/2);
						current->setRightBlock((current->getLeftBlock()));

						if(current->getRightBlock()/2 >= amountOfMemory)
						{
						 next->setLeftBlock(current->getRightBlock());
						 next->setRightBlock(current->getRightBlock());
						 current->setRightBlock(0);
						}
				
					}


					else if ((current->getRightBlock()/2) < amountOfMemory)
					{
						memoryAllocated = current->getRightBlock();

						list<FreeList>::iterator iterAllocatedList=allocatedList.begin();

						advance(iterAllocatedList, current->getOrderNumber());

						iterAllocatedList ->setBlockSize(current->getRightBlock());

						current->setRightBlock(0);

						break;

					}
				
			
				}
				
				else
				{continue;}

				

			

			
			}//END OF FOR


			if(totalMemory != 0)
			{
				totalMemory -= memoryAllocated;
			}

			else
			{
				cout<<"You Must Free Up Some Memory!!!"<<endl;
			}

			vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
	}//end of function



void AllocatedList:: deleteMemory(int amountOfMemory)
{
	list<FreeList>::iterator deleteIterator = listOfFreeList.begin();

	
}




ostream &operator<<(ostream& output , FreeList &list)
{
	output<<list.getBlockSize()<<endl;
	
	return output;

}

 bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
 {
	 return amountOfMemory<= list.getBlockSize();
 
 }

 /*bool AllocatedList::compare_Order_Numbers(FreeList item1, FreeList item2)
 {
	 return item1.getOrderNumber() < item2.getOrderNumber();

 }*/

Main.cpp-------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
	string response;

	AllocatedList allocatedList;

	int memory;

	

	cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;	
	

	while(response != "NO")
	{	

		cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

		cin>>memory;

		if((memory <= 0) || (memory > 256))
		{
			while((memory <= 0) || (memory > 256))
			{
				cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

				cin>>memory;

			}//End Of While

		}//End Of If 

		 allocatedList.checkMemory(memory);

		cout<<"Would You Like To Continue?\n"<<endl;

		cout<<"Enter 'YES' Or 'NO'\n"<<endl;

		cin>>response;

	}//End of While


	return 0;
}//End Of Main

Open in new window

0
Comment
Question by:brich744
  • 5
  • 4
9 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 34904235
Your description of the assignment is quite confusing. Could you post the exact text of the assignment please ?

For what follows, I'll assume the normal buddy allocation algorithm with a pool of 256 blocks of size 8kB (or whichever unit it is)

>> What I am stuck on is how can I let the user enter in a value to delete memory and free up the block size that is closest to the value and combine any other blocks that are free with the newly free block.

You don't have to calculate the block size that is closest.

Instead, the user will give you the IDENTIFIER of the allocated block. You can see that identifier as the address of the memory block. Using the identifier, you can easily retrieve it in the allocated list, and can easily figure out which block it corresponds to in the free list.

Btw : is having two separate lists a requirement that you were given ? Or can you keep everything in one list ? I think I'd prefer the latter.


>> The thing is all of the blocks must have a number ranging from 1-32, 33-65.

That's one of the confusing aspects in your description. It doesn't seem to match the values you gave earlier. So it would be good to post the exact text of the assignment here.
0
 

Author Comment

by:brich744
ID: 34911046
Here is the actual assignment description:


Buddy Memory Allocation Algorithm

In this programming assignment we will implement a variant of the buddy memory allocation algorithm/technique. The buddy memory allocation technique is one of the memory allocation techniques used by operating systems to allocate memory to programs for storing variables, etc. You can read more about the buddy memory allocation technique in any operating systems textbook. Some websites discussing this topic are:
•      http://www.memorymanagement.org/articles/alloc.html
•      http://en.wikipedia.org/wiki/Buddy_memory_allocation
•      http://www.economicexpert.com/a/Memory:allocation.htm
•      https://umdrive.memphis.edu/blstuart/htdocs/excerpt3.pdf

The buddy memory allocation technique allocates memory in blocks of sizes in powers of 2. If the system has 300KB of physical memory, then the largest allocatable block size is 256KB.Therefore, for the purposes of this homework, we will assume that when the program starts there is a single block of memory of size 256KB which is the largest allocatable block size. Let the smallest allocatable block size be 2KB. Block sizes will be in powers of 2.

Usually the buddy memory allocation algorithm is implemented using binary trees. However, in this homework we will implement the buddy memory allocation algorithm using an array of free lists having one entry for each allowable block size. Therefore the size of this array is 8. Similarly, we will also have an array of allocated lists. Array entry at index i in the array of free lists points to a linked list of free blocks of size 2i+1; array entry at index i in the array of allocated lists points to a linked list of allocated blocks of size 2i+1.
 
If a program requests memory of size x KB, find the smallest k such that x < 2k. If such a block is free, allocate it. If not, find the next larger block that is free and split it. If the split block is of size 2k allocate it, otherwise repeat the steps until you get a free block of size 2k. If a block of size 2k cannot be allocated print an appropriate message. When blocks are split, add them to the appropriate linked list in the array.

Your program must ask the user to input the request for memory in the range 1-256KB – be forgiving of erroneous input from the user. You must custom-design your own linked list class and any additional classes that you wish; however, you may refer to the author’s implementation for guidance. Before the user enters his/her request, output the array of free lists and after processing the user’s request output the array of allocated lists. Your display format should be user friendly. The user must be allowed to enter as many requests as (s)he wishes – one at a time.

Extra Credit (100 points): Allow for blocks to be coalesced when the requesting programs free the memory allotted to them. For additional details on this part, talk to the instructor.  
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34911261
Ok, that's slightly different from how your initial post described it :)

So, you have a total memory size of 256kB, and a minimal block size of 2kB.

Other than those values, the advice in my first post is still valid.

For de-allocating a block of allocated memory, ask the user for the identifier for that block of memory, and then move it back to the free list.
0
 

Author Comment

by:brich744
ID: 34912946
I have changed the code around but I am still having a hard time figuring out how to give each block a numerical range of 32  for each block of memory allocated.  I am trying to do this so when the user delete memory that the blocks can be combined if the numerical range of 32 are in sequential order.  I have figured out the worst case of different numerical range of 32 blocks are need.  The number range is 1-80,167.  For every node in the linked list I have already put the range  of each node.

FreeList twoPow7(256,0, 256,1, 32 );
      FreeList twoPow6(0,1, 128, 33, 97 );
      FreeList twoPow5(0,2, 64, 98, 226);
      FreeList twoPow4(0,3,32, 227, 483 );
      FreeList twoPow3(0,4,16, 484, 996 );
      FreeList twoPow2(0,5,8,997, 2021 );
      FreeList twoPow1(0,6,4,2022, 4070);
      FreeList twoPow0(0,7,2,4076, 80167);

The last two parameters are the ranges that I am talking about.  I am stuck on this part I am trying to figure out how to get past this part.  It is the extra credit in the description.
FreeList.h---------------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
	FreeList(int, int, int, int, int);
	FreeList(int);
	FreeList();
	int getBlockSize();
	void setBlockSize(int);
	void setOrderNumber(int);
	int getOrderNumber();

	void setBlockValue(int);
	int getBlockValue();
	int getSizeOfList();
	void setSizeOfList(int);

	static void setBlockRange();

	
	bool operator<(FreeList&);
	bool operator<=(FreeList&);
	bool operator==(FreeList&);
	bool operator==(int);

	list<FreeList> quantiyOfValue;

private:
	
	int sizeOfBlock;
	int orderNumber;
	int blockValue;

	 int begin_rangeOfBlocks;
	 int end_rangeOfBlocks;
	


};
#endif

FreeList.cpp-----------------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber, int value, int begin, int end)
{
	setBlockSize(size);
	setOrderNumber(seqNumber);

	setBlockValue(value);

	begin_rangeOfBlocks = begin;
	end_rangeOfBlocks = end;
	
	

}

FreeList::FreeList(int size)
{
	sizeOfBlock = size;


}

FreeList::FreeList()
{
	sizeOfBlock =0;

}


bool FreeList::operator<=(FreeList &list)
{

	return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
	return getBlockSize() == list.getBlockSize();

}


bool FreeList::operator==(int amountOfMemory)
{

	return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
	return getBlockSize() < list.getBlockSize();
}


void FreeList::setBlockSize(int amountOfMemory)
{
	sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
	return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
	orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
	return orderNumber;
}

void FreeList::setBlockValue(int value)
{
	blockValue = value;

}

int FreeList::getBlockValue()
{

	return blockValue;
}


int FreeList::getSizeOfList()
{

	return quantiyOfValue.size();
}


 void FreeList::setBlockRange()
{

	

}

AllocatedList.h-------------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
	friend ostream &operator<<(ostream&,FreeList&);
public:
	AllocatedList();
	void checkMemory(int);
	void deleteMemory(int);
	static bool compareSizeOfBlocks(int&, FreeList&);
	bool availableMemory(int);
	bool greater_than_amountOfMemory(int,FreeList);


private:
	list<int>listOfMemory;
	list<FreeList> listOfFreeList;
	int totalMemory;
	int memoryAllocated;
	list<FreeList>allocatedList;
	
};
#endif



AllocatedList.cpp----------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"

AllocatedList::AllocatedList()
{
	totalMemory = 256;
	memoryAllocated = 0;
	//Defining the Free List
	FreeList twoPow7(256,0, 256,1, 32 );
	FreeList twoPow6(0,1, 128, 33, 97 );
	FreeList twoPow5(0,2, 64, 98, 226);
	FreeList twoPow4(0,3,32, 227, 483 );
	FreeList twoPow3(0,4,16, 484, 996 );
	FreeList twoPow2(0,5,8,997, 2021 );
	FreeList twoPow1(0,6,4,2022, 4070);
	FreeList twoPow0(0,7,2,4076, 80167);

	


	//Add each element to the Linked List
	listOfFreeList.push_back(twoPow7);
	listOfFreeList.push_back(twoPow6);
	listOfFreeList.push_back(twoPow5);
	listOfFreeList.push_back(twoPow4);
	listOfFreeList.push_back(twoPow3);
	listOfFreeList.push_back(twoPow2);
	listOfFreeList.push_back(twoPow1);
	listOfFreeList.push_back(twoPow0);


	allocatedList.assign(8,0);

}

 bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{
	
	return amountOfMemory <= listOfFreeList.getBlockSize();

}

 


void AllocatedList::checkMemory(int amountOfMemory)
{
	list<FreeList>::iterator current;
	list<FreeList>::iterator next;
	vector<int> vectorFreeList;
	

	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getBlockValue() >= amountOfMemory)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			//Add the memory to the allocated list
			listOfMemory.push_back(amountOfMemory);
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = listOfFreeList.begin();
			
			advance(current, vectorFreeList[0]);
			
		
			current->quantiyOfValue.push_back(current->getBlockValue());
		
			memoryAllocated = current->getBlockValue();

			
			list<FreeList>::iterator allocatedIter;
			allocatedIter = allocatedList.begin();

			advance(allocatedIter, current->getOrderNumber());
				
			allocatedIter->setBlockValue(current->getBlockValue());
			

			if(totalMemory != 0)
			{
				totalMemory -= memoryAllocated;
			}

			else
			{
				cout<<"You Must Free Up Some Memory!!!"<<endl;
			}

			vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
	}//end of function



		

ostream &operator<<(ostream& output , FreeList &list)
{
	output<<list.getBlockSize()<<endl;
	
	return output;

}

 bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
 {
	 return amountOfMemory<= list.getBlockSize();
 
 }

 bool AllocatedList::availableMemory(int memory)
 {
	 return totalMemory >= memory;
 }

 void AllocatedList::deleteMemory(int memory)
 {

	 list<FreeList>::iterator current;

	vector<int> vectorFreeList;
	

	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getBlockValue() >= memory)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = listOfFreeList.begin();
			
			advance(current, vectorFreeList[0]);
			
			if(current->quantiyOfValue.size() > 0)
				current->quantiyOfValue.pop_back();


			else
			{
				reverse(vectorFreeList.begin(), vectorFreeList.end());
				list<FreeList>::iterator deleteIterator = allocatedList.begin();

				advance(deleteIterator, vectorFreeList[0]);

				deleteIterator->setBlockValue(0);
					
				memoryAllocated = current->getBlockValue();
			
			
			

			if(totalMemory <= 256)
			{
				totalMemory += memoryAllocated;
			}

			}}

Main.cpp-------------------------------------------------------

#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
	string response;

	AllocatedList allocatedList;

	int memory;
	int choice;


	while(response != "NO")
	{	
		cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;	

		cout<<"1. Allocate Memory"<<endl;
		cout<<"2. Delete Memory"<<endl;
	    cout<<"Enter in corresponding number"<<endl;
		cin>>choice;
		
		if(choice == 1)
		{
		cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

		cin>>memory;
		
		if(allocatedList.availableMemory(memory))
		{
			allocatedList.checkMemory(memory);

		if((memory <= 0) || (memory > 256))
		{
			while((memory <= 0) || (memory > 256))
			{
				cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

				cin>>memory;

			}//End Of While

		}//End Of If 

		
		}

		else
		
		cout<<"You Must Free Up Space To Allocate A Block Size Of  "<<memory<<endl;
		}
	
	
		else if(choice==2)
		{
			cout<<"How Much Memory Would You Like To Delete"<<endl;
			cin>>memory;

			if((memory <= 0) || (memory > 256))
		    {
				while((memory <= 0) || (memory > 256))
				{
					cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

					cin>>memory;
				}}

				allocatedList.deleteMemory(memory);


		}
	

		cout<<"Would You Like To Continue?\n"<<endl;

		cout<<"Enter 'YES' Or 'NO'\n"<<endl;

		cin>>response;
	
	
	}//End of While


	return 0;
}//End Of Main

Open in new window

0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 53

Expert Comment

by:Infinity08
ID: 34914207
>> I have changed the code around but I am still having a hard time figuring out how to give each block a numerical range of 32  for each block of memory allocated.

Ok. Look at the identifiers as addresses eg.

So, if you split up the 256kB of memory into 2kB blocks, then you have 128 different blocks. You can give each of these blocks a numerical identifier (its address if you wish). The first would have identifier 0, the second 1, etc. until the last one which has identifier 127.

For bigger memory blocks, you can use the same addresses. For example :

    the blocks of 4kB would have identifiers 0, 2, 4, 6, etc. up till 126.
    the blocks of 8kB would have identifiers 0, 4, 8, 12, etc. up till 124.
    the blocks of 16kB would have identifiers 0, 8, 16, 24, etc. up till 120.
    etc.
    the two blocks of 128kB would have identifiers 0 and 64.
    the single block of 256kB would have identifier 0.

So, given two values (the identifier and the size of the block), you can uniquely identify which block it is. For example, you could say : the 8kB block with identifier 12.


I'm not sure whether that is what your instructor is referring to, but that's how I would do it. (actually I'd use a single tree rather than two lists, but that's clearly a constraint imposed by the assignment).
0
 

Author Comment

by:brich744
ID: 34923368
Ok, what I am having trouble with is how to dynamically allocate the identifiers to each blocks.  I could do it by brute force but I know my professor would take off considerably.  Here is my revised code.  I have changed the AllocatedList.cpp, and added a function called setBlockRange().
 
FreeList.h--------------------------------------------------------

#ifndef FREELIST_H
#define FREELIST_H

class FreeList
{

public:
	FreeList(int, int, int, int, int);
	FreeList(int, int, int);
	FreeList(int);
	FreeList();
	
	int getBlockSize();
	void setBlockSize(int);
	void setOrderNumber(int);
	int getOrderNumber();

	void setBlockValue(int);
	int getBlockValue();
	int getSizeOfList();
	void setSizeOfList(int);

	 int setBlockRange();

	
	bool operator<(FreeList&);
	bool operator<=(FreeList&);
	bool operator==(FreeList&);
	bool operator==(int);

	list<int> quantiyOfValue;

private:
	
	int sizeOfBlock;
	int orderNumber;
	int blockValue;

	 int begin_rangeOfBlocks;
	 int end_rangeOfBlocks;
	


};
#endif

FreeList.cpp-----------------------------------------------------

#include<iostream>
#include<string>
#include<list>
#include<vector>
#include<stack>

using namespace std;

#include"FreeList.h"

FreeList::FreeList(int size, int seqNumber, int value, int begin, int end)
{
	setBlockSize(size);
	setOrderNumber(seqNumber);

	setBlockValue(value);

	begin_rangeOfBlocks = begin;
	end_rangeOfBlocks = end;
	
	

}

FreeList::FreeList(int value, int begin, int end)
{
	begin_rangeOfBlocks = begin;
	end_rangeOfBlocks = end;

	setBlockValue(value);

	setBlockRange();
}

FreeList::FreeList(int size)
{
	sizeOfBlock = size;


}

FreeList::FreeList()
{
	sizeOfBlock =0;

}


bool FreeList::operator<=(FreeList &list)
{

	return getBlockSize() <= list.getBlockSize();
}

bool FreeList::operator==(FreeList &list)
{
	return getBlockSize() == list.getBlockSize();

}


bool FreeList::operator==(int amountOfMemory)
{

	return amountOfMemory == getBlockSize();

}

bool FreeList::operator<(FreeList &list)
{
	return getBlockSize() < list.getBlockSize();
}


void FreeList::setBlockSize(int amountOfMemory)
{
	sizeOfBlock = amountOfMemory;
}

int FreeList::getBlockSize()
{
	return sizeOfBlock;
}

void FreeList::setOrderNumber(int seqNumber)
{
	orderNumber = seqNumber;

}

int FreeList::getOrderNumber()
{
	return orderNumber;
}

void FreeList::setBlockValue(int value)
{
	blockValue = value;

}

int FreeList::getBlockValue()
{

	return blockValue;
}


int FreeList::getSizeOfList()
{

	return quantiyOfValue.size();
}


int FreeList::setBlockRange()
{
	begin_rangeOfBlocks += (32 * quantiyOfValue.size())-1;

	return begin_rangeOfBlocks;

}

AllocatedList.h-------------------------------------------------

#ifndef ALLOCATEDLIST_H
#define ALLOCATEDLIST_H

#include<iostream>
#include<string>
#include<list>

using namespace std;

#include"FreeList.h"

class AllocatedList
{
	friend ostream &operator<<(ostream&,FreeList&);
public:
	AllocatedList();
	void checkMemory(int);
	void deleteMemory(int);
	static bool compareSizeOfBlocks(int&, FreeList&);
	bool availableMemory(int);
	bool greater_than_amountOfMemory(int,FreeList);


private:
	list<int>listOfMemory;
	list<FreeList> listOfFreeList;
	int totalMemory;
	
	list<FreeList>allocatedList;
	
};
#endif


AllocatedList.cpp-------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"
#include"FreeList.h"

AllocatedList::AllocatedList()
{
	totalMemory = 256;

	//Defining the Free List
	FreeList twoPow7(256,0, 256,1, 32 );
	FreeList twoPow6(0,1, 128, 33, 97 );
	FreeList twoPow5(0,2, 64, 98, 226);
	FreeList twoPow4(0,3,32, 227, 483 );
	FreeList twoPow3(0,4,16, 484, 996 );
	FreeList twoPow2(0,5,8,997, 2021 );
	FreeList twoPow1(0,6,4,2022, 4070);
	FreeList twoPow0(0,7,2,4076, 80167);

	


	//Add each element to the Linked List
	listOfFreeList.push_back(twoPow7);
	listOfFreeList.push_back(twoPow6);
	listOfFreeList.push_back(twoPow5);
	listOfFreeList.push_back(twoPow4);
	listOfFreeList.push_back(twoPow3);
	listOfFreeList.push_back(twoPow2);
	listOfFreeList.push_back(twoPow1);
	listOfFreeList.push_back(twoPow0);


	allocatedList.push_back(twoPow7);
	allocatedList.push_back(twoPow6);
	allocatedList.push_back(twoPow5);
	allocatedList.push_back(twoPow4);
	allocatedList.push_back(twoPow3);
	allocatedList.push_back(twoPow2);
	allocatedList.push_back(twoPow1);
	allocatedList.push_back(twoPow0);

}

 bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{
	
	return amountOfMemory <= listOfFreeList.getBlockSize();

}

 


void AllocatedList::checkMemory(int amountOfMemory)
{
	list<FreeList>::iterator current;
	list<FreeList>::iterator next;
	vector<int> vectorFreeList;

	int memoryAllocated=0;
	

	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getBlockValue() >= amountOfMemory)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			//Add the memory to the allocated list
			listOfMemory.push_back(amountOfMemory);
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = listOfFreeList.begin();
			
			advance(current, vectorFreeList[0]);
			
			//Add to inner list
		
			current->quantiyOfValue.push_back(current->setBlockRange());

			

		
			memoryAllocated = current->getBlockValue();

			
			list<FreeList>::iterator allocatedIter;
			allocatedIter = allocatedList.begin();

			advance(allocatedIter, current->getOrderNumber());
				
			allocatedIter->setBlockValue(current->getBlockValue());
			

			if(totalMemory != 0)
			{
				totalMemory -= current->getBlockValue();
			}

			else
			{
				cout<<"You Must Free Up Some Memory!!!"<<endl;
			}

			vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
	}//end of function



		

ostream &operator<<(ostream& output , FreeList &list)
{
	output<<list.getBlockSize()<<endl;
	
	return output;

}

 bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
 {
	 return amountOfMemory<= list.getBlockSize();
 
 }

 bool AllocatedList::availableMemory(int memory)
 {
	 return totalMemory >= memory;
 }

 void AllocatedList::deleteMemory(int memory)
 {
	 int memoryAllocated = 0;

	 list<FreeList>::iterator current;

	vector<int> vectorFreeList;
	

	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getBlockValue() >= memory && IterFreeList->quantiyOfValue.size()!= 0)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = allocatedList.begin();
			
			advance(current, vectorFreeList[0]);
			
			if(current->quantiyOfValue.size() > 0)
				current->quantiyOfValue.pop_back();


			else
			{
				
				list<FreeList>::iterator deleteIterator = allocatedList.begin();

				advance(deleteIterator, vectorFreeList[0]);

				memoryAllocated = deleteIterator->getBlockValue();

				reverse(vectorFreeList.begin(), vectorFreeList.end());

				current = listOfFreeList.begin();

				advance(current, vectorFreeList[0]);

				current->quantiyOfValue.push_back(current->getBlockValue());

				deleteIterator->setBlockValue(0);
					

				totalMemory += memoryAllocated;

			}}

Main.cpp-----------------------------------------------------

#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>

using namespace std;

#include"FreeList.h"
#include"AllocatedList.h"

int main()
{
	string response;

	AllocatedList allocatedList;

	int memory;
	int choice;


	while(response != "NO")
	{	
		cout<<"***********BUDDY MEMORY PROGRAM**********\n"<<endl;	

		cout<<"1. Allocate Memory"<<endl;
		cout<<"2. Delete Memory"<<endl;
	    cout<<"Enter in corresponding number"<<endl;
		cin>>choice;
		
		if(choice == 1)
		{
		cout<<"Enter In The Amount Of Memory You Would Like To Allocate\n"<<endl;

		cin>>memory;
		
		if(allocatedList.availableMemory(memory))
		{
			allocatedList.checkMemory(memory);

		if((memory <= 0) || (memory > 256))
		{
			while((memory <= 0) || (memory > 256))
			{
				cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

				cin>>memory;

			}//End Of While

		}//End Of If 

		
		}

		else
		
		cout<<"You Must Free Up Space To Allocate A Block Size Of  "<<memory<<endl;
		}
	
	
		else if(choice==2)
		{
			cout<<"How Much Memory Would You Like To Delete"<<endl;
			cin>>memory;

			if((memory <= 0) || (memory > 256))
		    {
				while((memory <= 0) || (memory > 256))
				{
					cout<<"Oops, Please Enter In An Amount Between '2 - 256' \n"<<endl;

					cin>>memory;
				}}

				allocatedList.deleteMemory(memory);


		}
	

		cout<<"Would You Like To Continue?\n"<<endl;

		cout<<"Enter 'YES' Or 'NO'\n"<<endl;

		cin>>response;
	
	
	}//End of While


	return 0;
}//End Of Main

Open in new window

0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 34924108
>> Ok, what I am having trouble with is how to dynamically allocate the identifiers to each blocks.

What do you mean by that ?

If you follow the address approach I described earlier, you can easily calculate the identifier - there's no need to dynamically determine it.

For example, splitting up a 256kB block at address 0 would give two 128kB blocks at addresses 0 and 64 resp.
Splitting up a 128kB block at address 64 would give two 64kB blocks at addresses 64 and 96 resp.
0
 

Author Comment

by:brich744
ID: 34930312
Ok, so I am having a problem with current->quantiyOfValue.pop_back();.  It works just fine the first time that the user enter input.  But, on the second time of allocating memory the current->quantiyOfValue.pop_back(); throws an error. List iterator is not decrementable.  I debugged the code and the second time I allocated memory the current->quantiyOfValue.pop_back(); is still on the 256 block.  Therefore it has already been pop an nothing is in the quantiyOfValue list.  I cannot figure out why the current iterator is not moving.  Here is the code.
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<algorithm>

using namespace std;

#include"AllocatedList.h"
#include"FreeList.h"

AllocatedList::AllocatedList()
{
	totalMemory = 256;

	//Defining the Free List
	FreeList twoPow7(1,0, 256,1, 32 );	//Start out with 1 '256' in the quanity value
	FreeList twoPow6(0,1, 128, 33, 97 );	//0
	FreeList twoPow5(0,2, 64, 98, 226);		//0
	FreeList twoPow4(0,3,32, 227, 483 );	//0	
	FreeList twoPow3(0,4,16, 484, 996 );	//0
	FreeList twoPow2(0,5,8,997, 2021 );		//0
	FreeList twoPow1(0,6,4,2022, 4070);		//0
	FreeList twoPow0(0,7,2,4076, 80167);	//0

	


	//Add each element to the Linked List
	listOfFreeList.push_back(twoPow7);
	listOfFreeList.push_back(twoPow6);
	listOfFreeList.push_back(twoPow5);
	listOfFreeList.push_back(twoPow4);
	listOfFreeList.push_back(twoPow3);
	listOfFreeList.push_back(twoPow2);
	listOfFreeList.push_back(twoPow1);
	listOfFreeList.push_back(twoPow0);

	FreeList two_Pow_7(256,0);
	FreeList two_Pow_6(128,1);
	FreeList two_Pow_5(64,2);
	FreeList two_Pow_4(32,3);
	FreeList two_Pow_3(16,4);
	FreeList two_Pow_2(8,5);
	FreeList two_Pow_1(4,6);
	FreeList two_Pow_0(2,7);


	allocatedList.push_back(two_Pow_7);
	allocatedList.push_back(two_Pow_6);
	allocatedList.push_back(two_Pow_5);
	allocatedList.push_back(two_Pow_4);
	allocatedList.push_back(two_Pow_3);
	allocatedList.push_back(two_Pow_2);
	allocatedList.push_back(two_Pow_1);
	allocatedList.push_back(two_Pow_0);

}

 bool AllocatedList::compareSizeOfBlocks(int& amountOfMemory, FreeList& listOfFreeList)
{
	
	return amountOfMemory <= listOfFreeList.getBlockValue();

}

 


void AllocatedList::checkMemory(int amountOfMemory)
{
	list<FreeList>::iterator current;
	list<FreeList>::iterator next;
	vector<int> vectorFreeList;
	vector<int> anotherFreeList;

	int memoryAllocated=0;	
	

	list<FreeList>::iterator IterFreeList;
	//Check the values that the nodes hold
	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		//If the value that the node holds is greater than or equal to the
		//user input than store the node in vectorFreeList
		if(IterFreeList->getBlockValue() >= amountOfMemory && IterFreeList->getListSize()>0 )
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}


	list<FreeList>::iterator anotherIter;
	
	for(anotherIter=listOfFreeList.begin(); anotherIter!=listOfFreeList.end(); anotherIter++)
	{
		//If the value that the node holds is greater than or equal to the
		//user input than store the node in vectorFreeList
		if(anotherIter->getBlockValue() >= amountOfMemory)
			anotherFreeList.push_back(anotherIter->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}


			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());
			sort(anotherFreeList.begin(), anotherFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			reverse(anotherFreeList.begin(), anotherFreeList.end());
			//reverse so that the lowest block value will be first;
			
			//Test: purpose of this list -> it will hold all of the user input
			listOfMemory.push_back(amountOfMemory);
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = listOfFreeList.begin();
			
			advance(current, vectorFreeList[0]);

			next = listOfFreeList.begin();

			advance(next, anotherFreeList[0]);
			
			
			//Add a node to the list witin the current node
			//Set the number range for the new node
			//current->quantiyOfValue.push_back(current->getBlockRange());
			current->quantiyOfValue.pop_back(); //ERROR: No item to pop second time around
			
			//Divide the current and next values to get the temp to pushback the 
			//quantiy size
			int temp = current->getBlockValue()/next->getBlockValue();

			//Set memory Allocated to equal the block size
			memoryAllocated = current->getBlockValue();
			
			//Adding the block range to the quantiyOfValue
			for(int i =0; i< temp; i++)
			{
				next->setBlockRange();
				next->quantiyOfValue.push_back(next->getBlockRange());
			}

			//Create a new iterator to place the block range in the allocatedList
			list<FreeList>::iterator allocatedIter;
			allocatedIter = allocatedList.begin();

			advance(allocatedIter, next->getOrderNumber());
				
			allocatedIter->setBlockValue(next->getBlockValue());
			

			if(totalMemory != 0)
			{
				totalMemory -= next->getBlockValue();
			}

			else
			{
				cout<<"You Must Free Up Some Memory!!!"<<endl;
			}

			vectorFreeList.erase(vectorFreeList.begin(), vectorFreeList.end());
			anotherFreeList.erase(anotherFreeList.begin(), anotherFreeList.end());
	}//end of function



		

ostream &operator<<(ostream& output , FreeList &list)
{
	output<<list.getBlockValue()<<endl;
	
	return output;

}

 bool AllocatedList::greater_than_amountOfMemory(int amountOfMemory,FreeList list)
 {
	 return amountOfMemory<= list.getBlockValue();
 
 }

 bool AllocatedList::availableMemory(int memory)
 {
	 return totalMemory >= memory;
 }

 void AllocatedList::deleteMemory(int memory)
 {
	 int memoryAllocated = 0;

	 list<FreeList>::iterator current;

	vector<int> vectorFreeList;
	

	list<FreeList>::iterator IterFreeList;

	for(IterFreeList=listOfFreeList.begin(); IterFreeList!=listOfFreeList.end(); IterFreeList++)
	{
		if(IterFreeList->getBlockValue() >= memory && IterFreeList->quantiyOfValue.size()!= 0)
			vectorFreeList.push_back(IterFreeList->getOrderNumber()); 
			//Get the order number from the object


		else
			continue;
	}



			//sort vectorFreeList so the lowest order # object is first
			sort(vectorFreeList.begin(), vectorFreeList.end());

			reverse(vectorFreeList.begin(), vectorFreeList.end());
			
			
			
			//create a new iterator and advance it to the lowest
			//order number object
			
			current = allocatedList.begin();
			
			advance(current, vectorFreeList[0]);
			
			if(current->quantiyOfValue.size() > 0)
				current->quantiyOfValue.pop_back();


			else
			{
				
				list<FreeList>::iterator deleteIterator = allocatedList.begin();

				advance(deleteIterator, vectorFreeList[0]);

				memoryAllocated = deleteIterator->getBlockValue();

				reverse(vectorFreeList.begin(), vectorFreeList.end());

				current = listOfFreeList.begin();

				advance(current, vectorFreeList[0]);

				current->quantiyOfValue.push_back(current->getBlockValue());

				deleteIterator->setBlockValue(0);
					

				totalMemory += memoryAllocated;

			}}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 34938141
If there's an error that says that there are no items in it, then I guess there are no items in it ... Not sure what more can be said about that.

Look at the code where you expected items to be added to it, and then figure out why they're not (a debugger or print statements will be useful to track the flow of the code).
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now