Solved

A question about memory management

Posted on 2009-05-06
19
258 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
  • 11
  • 6
  • 2
19 Comments
 
LVL 40

Assisted Solution

by:mrjoltcola
mrjoltcola earned 100 total points
Comment Utility
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
Comment Utility
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
Comment Utility
What data structure makes sense to track recursive pairs of things?
0
 

Author Comment

by:errang
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
>>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
Comment Utility
>> 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
Comment Utility
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
What Security Threats Are You Missing?

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.

 

Author Comment

by:errang
Comment Utility
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 400 total points
Comment Utility
>> 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
Comment Utility
>>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
Comment Utility
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
Comment Utility
>> 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
Comment Utility
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 400 total points
Comment Utility
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
Comment Utility
Wow... now that... is so very much simpler than what I had to do... Thanks a lot!!!
0
 

Author Comment

by:errang
Comment Utility
what I thought I had to do**
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
If you want to, you can post the code you end up using here, so we can check it ...
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

Suggested Solutions

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…
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…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

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

7 Experts available now in Live!

Get 1:1 Help Now