A question about memory management
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.
Thanks in advance!
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.
Thanks in advance!
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
What data structure makes sense to track recursive pairs of things?
ASKER
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...
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...
ASKER
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?
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.
The leaves of the tree from left to right would correspond to the blocks of memory from low to high address.
ASKER
>>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..).
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..).
>> 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.
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.
ASKER
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.
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.
ASKER
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
>>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?
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?
ASKER
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?
>> 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.
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.
ASKER
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?
Like this:
Enter the amount of memory you need: 5
You have been allocated 8 MB of memory.
That's basically it?
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Wow... now that... is so very much simpler than what I had to do... Thanks a lot!!!
ASKER
what I thought I had to do**
If you want to, you can post the code you end up using here, so we can check it ...
ASKER
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?