x
Solved

# A question about memory management

Posted on 2009-05-06
Medium Priority
323 Views
Hey, I need to implement a Memory Management program, using the buddy system... I get the part about allocating memory blocks to programs when they request it... but could someone please explain to me what I need to do?

Is it just as simple as rounding up the entered number to a permitted value and allocating that much memory? It's a project, so I'm thinking it can't be that simple... But I really don't see anything else... unless we'r supposed to write a malloc and free function.

0
Question by:errang
• 11
• 6
• 2

LVL 40

Assisted Solution

mrjoltcola earned 400 total points
ID: 24319494
Hi errang, good to see you again. Have you read about the buddy system in detail yet? Do that before starting?

It is an easy algorithm, in theory, but there are still details to be implemented.

http://en.wikipedia.org/wiki/Buddy_memory_allocation

Essentially, yes, you are to write a malloc/free pair.

1) You start out with a single large chunk of memory. How is that for help to get you started?? ;)
2) Common, simple approach is to track blocks with a binary tree, since it is the "buddy system"
0

Author Comment

ID: 24320237
Ok, I read the article about the Buddy system, and I get the part about selecting a lower limit and upper limit and allocating the necessary space to the program, just the nearest exponent of 2, right?

My question is, how do we actually keep track of the blocks in memory?

I barely know how to use malloc... lol, I'm not exactly sure how to write one.  Is there some kind of system call that tells us what memory blocks are free?
0

LVL 40

Expert Comment

ID: 24320944
What data structure makes sense to track recursive pairs of things?
0

Author Comment

ID: 24322954
hm... a binary tree would be best to keep track of pairs... right?

But... if that is the case, what kind of algorithm would we use to traverse the tree? If we split the tree evenly, its not exactly a sorted tree... is it? I mean after combining and splitting nodes...
0

Author Comment

ID: 24331801
There is no guarantee that the tree is sorted... Right? Or do we use some kinda algorithm that rotates the tree to keep it balanced? But is that the same as sorted?
0

LVL 53

Expert Comment

ID: 24352328
There's no need to keep the tree "sorted" or to re-balance it. In fact, that would break the algorithm.

The leaves of the tree from left to right would correspond to the blocks of memory from low to high address.
0

Author Comment

ID: 24360317
>>The leaves of the tree from left to right would correspond to the blocks of memory from low to high address.

How exactly does that happen? Is it automatic?

But I was wondering...Is there any way to do this without recursion? Like if I look where I'm going before I get there?

struct tree
{
int memory; //to allocate memory.
int bool_used; //to say if it is used or not.
struct tree *left; //left child
struct tree *right; //right child
};

And I have an if statement check if the bool_used variable is set to 1, and if it is, I don't go there and just restart my search?

I'm just trying to make it as simple as possible (granted it already is simple..).

0

LVL 53

Expert Comment

ID: 24362081
>> How exactly does that happen? Is it automatic?

It's the buddy system ;) It's how it works :)

Do you understand how the buddy system works ? The wiki mrjoltcola posted is a good start, so if you have any doubts about that, ask about it.
0

Author Comment

ID: 24362102
Here's what I understand about the buddy system... It breaks up memory into small chunks, following either the fibonacci sequence or the regular powers of 2.  We haven't been given any specific information, so I'm going with the powers of 2, since its easier than the fibonacci sequence.

And, you round up any memory request you get to the power of 2, and allocate that space.  And if there are 2 memory blocks right next to each other, you can merge them to service a request that might not otherwise be fulfilled.
0

Author Comment

ID: 24362123
I've actually been thinking about this... and was wondering... would a linked list work? I've not been given any specific information to the implementation of this, so I just need to get the splitting and unsplitting to work...

So, I was thinking, I'd start off with a huge block, right? When I get a memory request, I'll round it up to the closest power of 2, deallocate the original block of memory, and allocate 2 new blocks.. the small one for the request, the big one for... whats left of the original block of memory...

Would that work? I'm not trying to write the best buddy system here... I'm trying to get something to work, its due tomorrow... lol.
0

LVL 53

Accepted Solution

Infinity08 earned 1600 total points
ID: 24362435
>> And if there are 2 memory blocks right next to each other, you can merge them to service a request that might not otherwise be fulfilled.

Actually, you start with one big lump of memory, and you only split it up when needed.

There's a completely worked out example on that wiki page that should make things clear (in the paragraph "How it works"). Did you read and completely understand it ?

>> would a linked list work?

You could make it work with a linked list, yes. Although a binary tree is easier imo.

>> So, I was thinking, I'd start off with a huge block, right?

Right.

>> When I get a memory request, I'll round it up to the closest power of 2

Right.

>> deallocate the original block of memory, and allocate 2 new blocks..

No, you don't de-allocate the block. You simply split it up in two equally sized parts. And then repeat the same process with the left-most block, until you get a block of the requested size.

See the example on the wiki page.
0

Author Comment

ID: 24362498
>>No, you don't de-allocate the block. You simply split it up in two equally sized parts. And then repeat the same process with the left-most block, until you get a block of the requested size.

Right, but if you want to allocate two blocks each having half of what the original block had, you have to deallocate it, right? For a linked list implementation I mean.

So, to make it work with a linked list system, we would simply break up the block into smaller chunks till we get what we need... correct? How would the merging part work out? Just see what blocks aren't used and just mash them together?
0

Author Comment

ID: 24362503
I mean... if you allocated a block of 128 MB... and want to split it up into 2 64 MB blocks, wouldn't you be using 256 MB if you didn't deallocate the original 128 MB?
0

LVL 53

Expert Comment

ID: 24362569
>> Right, but if you want to allocate two blocks each having half of what the original block had, you have to deallocate it, right?

Why would you have to de-allocate it ?

If you have a linked list, then each node in the linked list corresponds to a block of memory WITHIN the big allocated block. It'll have a start address and a size, which is sufficient to identify it within the big allocated block.

You don't de-allocate or allocate any memory (other than the big block initially). All your operations work on the linked list nodes, never on the block of memory itself.

>> So, to make it work with a linked list system, we would simply break up the block into smaller chunks till we get what we need... correct?

conceptually, yes, but in practice the block of memory isn't touched. What you actually split up is one of the nodes in the linked list.
0

Author Comment

ID: 24362585
So... wait, let me see if I got this right, I just keep the huge block of memory as it is, and then I take a request to allocate memory, and round it up to the nearest power of 2, and just allocate that memory?

Like this:

Enter the amount of memory you need: 5
You have been allocated 8 MB of memory.

That's basically it?
0

LVL 53

Assisted Solution

Infinity08 earned 1600 total points
ID: 24362647
The big block of memory you allocate in the beginning (using malloc or calloc) is your work space, it is the amount of memory that can be used for your allocation code (which uses the buddy system).

Your allocation algorithm will allocate blocks within this big block, depending on the needs. You don't allocate or de-allocate anything (using malloc or calloc) any more, and you don't touch the big memory block.
All your algorithm does, is identify a free block of the requested size, and assign it to be used by the code that requested it. So, in your linked list (or tree), you look for a node that corresponds to such a free block of memory of the requested size, and set it to "used", and return it to the requester.

That's it. All operations happen on the linked list (or tree). And the only operations that do happen are splitting/joining nodes and changing the status of nodes (free or used). Nothing else.
0

Author Comment

ID: 24362734
Wow... now that... is so very much simpler than what I had to do... Thanks a lot!!!
0

Author Comment

ID: 24362737
what I thought I had to do**
0

LVL 53

Expert Comment

ID: 24362751
If you want to, you can post the code you end up using here, so we can check it ...
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.