Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

A question about memory management

Posted on 2009-05-06
19
Medium Priority
?
311 Views
Last Modified: 2012-05-06
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!
0
Comment
Question by:errang
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 11
  • 6
  • 2
19 Comments
 
LVL 40

Assisted Solution

by:mrjoltcola
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

by:errang
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

by:mrjoltcola
ID: 24320944
What data structure makes sense to track recursive pairs of things?
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Author Comment

by:errang
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

by:errang
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

by:Infinity08
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

by:errang
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

by:Infinity08
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

by:errang
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

by:errang
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

by:
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

by:errang
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

by:errang
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

by:Infinity08
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

by:errang
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

by:Infinity08
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

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

Author Comment

by:errang
ID: 24362737
what I thought I had to do**
0
 
LVL 53

Expert Comment

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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

604 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