Solved

more questions about the buddy system

Posted on 2009-05-12
42
729 Views
Last Modified: 2012-05-06
Hey, I need to implement the buddy system in C, I understand that we allocate one big chunk of memory, and then take the address from that, and add to that, to allocate space to an application...

My question is... how do we get the starting address of the memory chunk?

I've written a small program that would allocate 8 MB and give me the starting address of the block, but I'm getting some weird error with the malloc call.

And, suppose I want to allocate 2 MB to an application... how would I go about doing that? take the starting address and add 2 million bytes to it?
0
Comment
Question by:errang
  • 26
  • 16
42 Comments
 

Author Comment

by:errang
Comment Utility
Sorry... don't know why it didn't attach the code... this is what I'm talking about

#include <stdio.h>
#include <stdlib.h>

void *mymemory = malloc(8 * 1024 * 1024);

int main(){

  void *s;
  int s_int;
  s = &mymemory;

  s_int = *(int *)s;

  printf("s = %d\n", s_int);

  return 0;

}

> cc test.c
"test.c", line 4: non-constant initializer: op "CALL"
cc: acomp failed for test.c
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> My question is... how do we get the starting address of the memory chunk?

malloc returns the start address.


>> but I'm getting some weird error with the malloc call.

Don't call malloc outside of the main - call it inside of the main.


>> And, suppose I want to allocate 2 MB to an application... how would I go about doing that? take the starting address and add 2 million bytes to it?

You have 8 MB available, in one big chunk. When you need to allocate 2 MB, you simply divide that 8 MB in two blocks of 4 MB, and the left-most block of 4 MB is split up again in two blocks of 2 MB. The left-most of those two blocks will be used to satisfy the allocation request.

Again, I'd like to refer to the example in the wiki page, which gives a much more detailed and complete description of what happens :

        http://en.wikipedia.org/wiki/Buddy_memory_allocation
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
For information to the other experts : this is a follow-up for :

        http://www.experts-exchange.com/Programming/Languages/C/Q_24386542.html
0
 

Author Comment

by:errang
Comment Utility
>>You have 8 MB available, in one big chunk. When you need to allocate 2 MB, you simply divide that 8 MB in two blocks of 4 MB, and the left-most block of 4 MB is split up again in two blocks of 2 MB. The left-most of those two blocks will be used to satisfy the allocation request.

I understand the theory behind it... I just have no clue as to how I would implement that in code.  And I'm getting contradicting replies from everyone I talk to... My instructor says, I need to take the start of the memory, and then add the size required to the offset and then give that address to the calling application.  Here, I keep hearing that we need to divide it into smaller chunks (which I do admit makes more sense) and allocate those chunks.

But I'm completely lost as to how I would go about doing that without using malloc again...

Could you please give a small example of what happens? Like the hello world type of program using the buddy system?
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>>  Here, I keep hearing that we need to divide it into smaller chunks (which I do admit makes more sense) and allocate those chunks.

Well, if you need to use the buddy system, then that's what you need to do, because that's how it works ;)


>> But I'm completely lost as to how I would go about doing that without using malloc again...

You already have all the memory you need in the big 8 MB block. That's your work space. If a user requests to allocate memory, it will be allocated FROM that workspace, so you don't use malloc again. You just pick the appropriate part of the big 8 MB block, and return that to the user.
Deciding which part is the appropriate part is done by the buddy algorithm.


>> Could you please give a small example of what happens?

I think this is the fifth time I've said it, but check the example in the wiki. It's very clear and complete.
0
 

Author Comment

by:errang
Comment Utility
>>I think this is the fifth time I've said it, but check the example in the wiki. It's very clear and complete.

I did check the example in the wiki page, this is what you want me to look at:

The buddy memory allocation technique allocates memory in powers of 2, i.e 2x, where x is an integer. Thus, the programmer has to decide on, or to write code to obtain, the upper limit of x. For instance, if the system had 2000K of physical memory, the upper limit on x would be 10, since 210 (1024K) is the biggest allocatable block. This results in making it impossible to allocate everything in as a single chunk; the remaining 976K of memory would have to be taken in smaller blocks.

After deciding on the upper limit (let's call the upper limit u), the programmer has to decide on the lower limit, i.e. the smallest memory block that can be allocated. This lower limit is necessary so that the overhead of storing used and free memory locations is minimized. If this lower limit did not exist, and many programs request small blocks of memory like 1K or 2K, the system would waste a lot of space trying to remember which blocks are allocated and unallocated. Typically this number would be a moderate number (like 2, so that memory is allocated in 2² = 4K blocks), small enough to minimize wasted space, but large enough to avoid excessive overhead. Let's call this lower limit l.

Now that we have our limits, let us see what happens when a program makes requests for memory. Let's say in this system, l = 6, which results in blocks 26 = 64K in size, and u = 10, which results in a largest possible allocatable block, 210 = 1024K in size. The following shows a possible state of the system after various memory requests.

correct?

I get the theory behind it, we split what we have into smaller chunks (in this case its 1024 KB), and they split it up into 2 512 KB chunks, and then they split one of the 512 KB chunks into smaller chunks to allocate memory for processes that require 33 KB memory, 128 KB memory, etc.  And the algorithm rounds it up to the closest power of 2 and allocates the memory to that process.

I get the theory... really, I do, what I don't get is how I would go about doing that in an actual C program... I don't understand how to implement that theory in actual code.

The rounding up part is simple enough to do, but I'm lost as to how I would select the memory chunk to begin with.

Any small code snippet of how we would "split" a chunk of memory that has been allocated would be greatly appreciated.
0
 

Author Comment

by:errang
Comment Utility
like... I wrote this to start with:

#include <stdio.h>
#include <stdlib.h>

int main(){
  void *mymemory = malloc(8 * 1024 * 1024);
  void *s;
  int s_int;
  s = &mymemory;

  s_int = *(int *)s;

  printf("s = %d\n", s_int);

  return 0;

}

And it compiles.

> cc test.c
> ./a.out
s = 134592
>

I'm thinking 134592 is the starting address of the 8 MB block... but how would I go about splitting it???
0
 

Author Comment

by:errang
Comment Utility
Originally, my idea of splitting the memory was going to be to have a loop doing 2 malloc's for each malloc it got... but you said we only needed to do malloc once, and I don't know how else we would go about trying to access memory or modify its bounds.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> correct?

More specifically the example that follows immediately after that ...


>> I get the theory... really, I do

Ok.


>> what I don't get is how I would go about doing that in an actual C program... I don't understand how to implement that theory in actual code.

well, we have been discussing just that in your previous question. For example, this post there :

        http://www.experts-exchange.com/Programming/Languages/C/Q_24386542.html#24362647


>> but I'm lost as to how I would select the memory chunk to begin with.

Just implement the buddy system. You can use a binary tree to help with that. If you need explanation of how to do that, then I refer back to your previous question, where this has already been answered. If anything there requires clarification, then ask about that :)


>> Any small code snippet of how we would "split" a chunk of memory that has been allocated would be greatly appreciated.

You basically start with a tree with one node in it. That node will correspond to the entire chunk of 8 MB. When an allocation request comes in, you'll find a free node of the appropriate size in the tree that satisfies the request. If no such node is currently in the tree, you split up a free bigger node into two smaller equally sized parts, and continue until a free node of the required size is available.

And again : splitting up a node does NOT require malloc calls, nor does it require any operation on the 8 MB block of memory. The only operations are done on the binary tree, and involve splitting up/joining nodes and changing the state of a node (free, used).

I've already explained that in the previous question though.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> and I don't know how else we would go about trying to access memory or modify its bounds.

Why would you modify its bounds ?
You don't even need to access the block of memory.

All you need is its start address and its size. The buddy algorithm takes care of the rest.
0
 

Author Comment

by:errang
Comment Utility
>>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 from the previous question...

>>You basically start with a tree with one node in it. That node will correspond to the entire chunk of 8 MB. When an allocation request comes in, you'll find a free node of the appropriate size in the tree that satisfies the request. If no such node is currently in the tree, you split up a free bigger node into two smaller equally sized parts, and continue until a free node of the required size is available.

Are you telling me that I would start building a binary tree, and I would magically find the blocks of memory???
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> and I would magically find the blocks of memory???

Not magically. Using the buddy algorithm.
0
 

Author Comment

by:errang
Comment Utility
Yes... I mean, I'll have a node to start out with... then I just make a tree out of it, and when I get a request for a certain block size, I would say it can use a certain node in that tree?

That's all I need to do?
0
 

Author Comment

by:errang
Comment Utility
So... let me get this straight.

I'll have a struct like this:

struct tree {

   void mem;
   struct tree *left;
   struct tree *right;
};

Then I'll do a malloc on the base node, like this?

struct tree {

   void mem = malloc(8 * 1024 * 1024); //to allocate 8 MB
   struct tree *left;
   struct tree *right;
};

And the left and right childs will be like...

struct tree {

   void mem; // Just keep this null?
   struct tree *left;
   struct tree *right;
};

And when we have a request for an application, we would see how far down the tree we need to go to get enough memory to give to the program?

Am I close?
0
 

Author Comment

by:errang
Comment Utility
This is what I got after modifying some of the sample code I got, does it look about right?:
void *mymalloc(int req) { // very simple memory allocation

	int i,f,n;

	printf("mymalloc()!");

	node *new;	

	//if request is too big

	if(req > SIZEOFWHOLEMEMORY){

	  printf("Size: %d, System dont have enough memory", req);

	}

	//Take the first available block from array_of_list 

	 for(i=0;i<5;i++){

		if(req < array_of_list[i]->number && req > (array_of_list[i]->number/2) && array_of_list[i]->allocation==1){

	if(array_of_list[i]->next != NULL){
 

new =(node*)(wholememory + (int)array_of_list[i]->number);

	new->allocation = 0; //this block is on use

	new->number = req;

	new->next = NULL;

	new->prev = NULL;

	array_of_list[i]->next = new;

	break;
 

}else if(i=0){

	

new =(node*)(wholememory + (int)array_of_list[i]->number);

	new->allocation = 0; //this block is on use

	new->number = req;

	new->next = NULL;

	new->prev = NULL;

	break;

}else{

if(array_of_list[i-1]->next==NULL){
 

array_of_list[i-1]=NULL; 

new =(node*)(wholememory + (int)array_of_list[i]->number); 

new->allocation = 0; //this block is on use

new->number = req;

new->next = NULL;

new->prev = NULL;

break;

}else {

      array_of_list[i-1]=NULL; 

      new =(node*)(wholememory + (int)array_of_list[i]->number); 

      new->allocation = 0; 

      new->number = req;

      new->next = NULL;

      new->prev = NULL;

      array_of_list[i]->next = new;

      break;

      }

}

}

}

if(array_of_list[i]->allocation == 0){

    printf("All memory is on use");

}

}

Open in new window

0
 

Author Comment

by:errang
Comment Utility
Actually... that piece of code isn't working... and I'm back to square one...

I did some more searching on google... and found this though:
http://students.mimuw.edu.pl/SO/Wyklady-html/04_pamiec/pagealloc.htm

Is that what I need? I've read the first half of that, and it talks about pages and bit shifts, but I just need to get a simple merging and splitting thing done.

Could you please tell me if I need all that? Or if my previous assumption in http:#24370787 is enough??
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
Comment Utility
>> Yes... I mean, I'll have a node to start out with... then I just make a tree out of it, and when I get a request for a certain block size, I would say it can use a certain node in that tree?
>>
>> That's all I need to do?

Pretty much, yes. But remember that the tree is separate from the actual memory block. Each tree node points to a part of the memory block, but the tree node is not inside the memory block.


>> struct tree {
>>    void mem;
>>    struct tree *left;
>>    struct tree *right;
>> };

Not sure what you intended to do with void mem, but you need two values to identify a block of memory : the start address, and the size.

>> Then I'll do a malloc on the base node, like this?

The malloc is done just to reserve a piece of memory for your personal allocation algorithm. It has nothing to do with the buddy algorithm.
So, you reserve a piece of memory, and then you create a tree with one node. This node will contain the start address of the allocated block of memory, and the size of that block. The node is marked as 'free'.
You're all set now to start the buddy algorithm whenever a user requests a block of memory.

>> And the left and right childs will be like...

There are no left and right childs (yet). Children are only created when a block is split up in two.
0
 

Author Comment

by:errang
Comment Utility
>>Pretty much, yes. But remember that the tree is separate from the actual memory block. Each tree node points to a part of the memory block, but the tree node is not inside the memory block.

Uh... could you please elaborate on this part? This is what I wasn't understanding.
0
 

Author Comment

by:errang
Comment Utility
>>Not sure what you intended to do with void mem, but you need two values to identify a block of memory : the start address, and the size.

Oh.. the void mem was actually where I was going to call malloc... I thought the behavior of this was similar to that of strtok... how you called it on a string and what you were looking for within a string, and then passed NULL as the first argument for every call to strtok after that...
0
 

Author Comment

by:errang
Comment Utility
So something like this would make more sense then?

struct tree{

   int start;
   int size;
   int used;
   struct tree *left;
   struct tree *right;
}
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> So something like this would make more sense then?

Except for the types, yes :) You probably want to change the type of 'start' to void* (pointer-to-void), to make it point to the memory block in question, and the type of 'size' to size_t (to make sure it can hold all possible values for memory sizes).


>> >>Pretty much, yes. But remember that the tree is separate from the actual memory block. Each tree node points to a part of the memory block, but the tree node is not inside the memory block.
>>
>> Uh... could you please elaborate on this part? This is what I wasn't understanding.

I'm not sure what to elaborate on.

Maybe an analogy will work. Consider a piece of land of 100m by 100m. The land is being sold to several buyers, but they all want pieces of different sizes. You can't actually split up the land itself (it's fixed), but what you can do, is draw a map, and then draw lines on that map to indicate how the land is divided among the buyers. Using the map, each of them knows which part of the land they own.

Now, for the memory, it's the same thing. You have a big block of memory, that is being used for several things. Each of these things requires a different amount of memory.
You can't really split up the block itself, but what you can do, is keep track of all the different smaller blocks within the big block, using a tree.
When a user requests a block of memory, the buddy algorithm will look for an appropriate block in the tree, and return it to the user.
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

Author Comment

by:errang
Comment Utility
>>Pretty much, yes. But remember that the tree is separate from the actual memory block. Each tree node points to a part of the memory block, but the tree node is not inside the memory block.
>>I'm not sure what to elaborate on.

The part I wasn't understanding is this one:  Each tree node points to a part of the memory block.

How exactly do I draw the line in the memory block to say what process gets what part of the block?
0
 

Author Comment

by:errang
Comment Utility
This is what I have so far:

It's not much, but it rounds up the entered value to the closest power of 2 and allocates that much memory.

Now, I guess I'll work on trying to create the tree and move through it?
#include "mymalloc.h"
 

void *memoryblock;

void roundup(int size);
 

int main(){
 

  int size;
 

  printf("Please enter the amount of memory you need (MB): ");

  scanf("%d", &size);
 

  roundup(size);
 

  return 0;

}
 

void roundup(int size){
 

  int two = 1;
 

  while(!(two >= size))

    two = two * 2;
 

  printf("Allocating %d MB.\n", two);
 

  

  memoryblock = malloc(two * 1024 * 1024);

}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> How exactly do I draw the line in the memory block to say what process gets what part of the block?

Start address and size is all you need to uniquely identify a small block within the large memory block.


>> Now, I guess I'll work on trying to create the tree and move through it?

Sure.
0
 

Author Comment

by:errang
Comment Utility
>>Start address and size is all you need to uniquely identify a small block within the large memory block.

So... I would convert the void * to an int, and then I would add as many bytes as I need?
0
 

Author Comment

by:errang
Comment Utility
This is where I'm at with the my_malloc function right now.

I kept the size as type int, because that was specified in our project.

I didn't get any compilation errors when doing this... I think I assigned the root of the tree the proper memory address.

Now, I just need to figure out how to separate the block into smaller pieces and how my_free is supposed to work.
#include "mymalloc.h"

#include <stdlib.h>

#include <stdio.h>
 

#define MAX_SIZE 512
 

void *mymemory;

struct tree{
 

   void *start;

   int size;

   int used;

   struct tree *left;

   struct tree *right;

};
 

typedef struct tree Tree;
 

int my_init(int memsize){

  int ret;
 

  if(memsize <= MAX_SIZE){

    mymemory = malloc(memsize * 1024 * 1024);

    ret = 1;

  }

  else{

    printf("Error: You have requested to much memory.\n");

    printf("Max memory that can be allocated is 512 MB.\n");

    ret = 0;

  }

  

  return ret;

}
 

void *my_malloc(int size){

  //printf("got in here\n");

  int succeeded;

  Tree *begin;
 

  succeeded = my_init(size);

  

  if(succeeded){

    //printf("Got inside the if statement.\n");

    begin->start = mymemory; //Memory allocated in my_init

    begin->size = size; //The size of the memory allocated.

    begin->used = 1; //0 - used, 1 - unused

    begin->left = NULL;

    begin->right= NULL;

  }
 

}
 

int   my_free(void *);

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> So... I would convert the void * to an int, and then I would add as many bytes as I need?

I'm not sure what you mean ... What do you mean ? Why would you need to do this ?


>> This is where I'm at with the my_malloc function right now.

You set the tree up only once, not inside the my_malloc function (which will be called every time a user requests a block of memory)
0
 

Author Comment

by:errang
Comment Utility
>>I'm not sure what you mean ... What do you mean ? Why would you need to do this ?

I thought we needed to do that to get the address within the huge block of memory?

>>You set the tree up only once, not inside the my_malloc function (which will be called every time a user requests a block of memory)

Yeah... realized that, I was just trying to setup the root.

This is what I have so far.  I (sorry about this) haven't used binary trees in over a year... and I'm really rusty...

Would it go something like:
Tree *temp;
 
    temp->start = (void *) ((int *) mymemory + ((size * 1024 * 1024)/2)); //To give it a memory address
    temp->size = size; //The size of the memory allocated.
    temp->used = 1; //0 - used, 1 - unused
    temp->left = NULL;
    temp->right= NULL;

I'm not exactly sure how we would link it back to the parent.

This question http://www.experts-exchange.com/Programming/Languages/C/Q_23114944.html answers that, right? Or is there another way to do this.
#include "mymalloc.h"

#include <stdlib.h>

#include <stdio.h>
 

#define MAX_SIZE 512
 

void *mymemory;

struct tree{
 

   void *start;

   int size;

   int used;

   struct tree *left;

   struct tree *right;

};
 

typedef struct tree Tree;
 

int my_init(int memsize){

  int ret;
 

  if(memsize <= MAX_SIZE){

    mymemory = malloc(memsize * 1024 * 1024);

    ret = 1;

  }

  else{

    printf("Error: You have requested to much memory.\n");

    printf("Max memory that can be allocated is 512 MB.\n");

    ret = 0;

  }
 

  return ret;

}
 

void *my_malloc(int size, int flag){

  //printf("got in here\n");

  int succeeded;

  int new_size;

  Tree *begin;
 

  succeeded = my_init(size);

  new_size = ((size * 1024 * 1024) / 2);
 

  if(succeeded){

    //printf("Got inside the if statement.\n");

    begin->start = mymemory; //Memory allocated in my_init

    begin->size = size; //The size of the memory allocated.

    begin->used = 1; //0 - used, 1 - unused

    begin->left = NULL;

    begin->right= NULL;

  }
 

  if(flag){

    //Add stuff here to make it link to the root.

  }
 

}
 

int   my_free(void *);

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
If you have a node of size x, with start address y, how would you split it up in two equally sized child nodes ? What would be their start addresses and sizes ?
0
 

Author Comment

by:errang
Comment Utility
>>If you have a node of size x, with start address y, how would you split it up in two equally sized child nodes ? What would be their start addresses and sizes ?

The start address of the left child would be y and the start address of the right child would be y + x/2?
Both of these child nodes would have a size of x/2.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> The start address of the left child would be y and the start address of the right child would be y + x/2?
>> Both of these child nodes would have a size of x/2.

Right. So, when you need to split up a node, you simply create these two child nodes.
0
 

Author Comment

by:errang
Comment Utility
Ok... I've made a bit of progress here... I've finally settled on using a linked list rather than a binary tree.  I know it is going to be complex keeping track of all the children and what not... but I think I'm better off trying to make that work than figure out how to get a recursive procedure to work on a tree for my_malloc and my_free.

This is what I have so far:

And this is how the linked list is going to look like inside the program:
> ./a.out
1----15
1----14
1----13
1----12
1----11
1----10
1----9
1----8
2----7
2----6
2----5
2----4
4----3
4----2
8----1

I haven't figured out how to make it print in order... but I figure that's the least of my worries as I'm in a bit of a time crunch...

Here's what I'm planning on doing:

1) The list will be made whenever a user enters a value for the big block of memory, since we aren't repeating that, I don't see building the list as a problem.
2) When I'm allocating memory, I could use a temp variable to see what's the latest memory with the size that will fit the requests. Like this loop here:
 while(curr){
    if(curr->size == 2){
      printf("%d----%d\n", curr->size, curr->number);
      new_head = (item *) malloc (sizeof(item));
      new_head->size = curr->size;
      new_head->number = curr->number;
      }
    curr = curr->next;
  }

In this case, the latest value of 2 will be in the new_head variable.

I've got a few questions though:
1) When a user asks for 1 MB of memory... would it be enough to give that memory to one of the 1 MB nodes? Or do I need to give it from top to bottom first?
2) Is there anything else I'm missing?

Sorry about the huge post... but could you please help me out? I'm already a day late... but I think I've almost got it =)
#include "mymalloc.h"

#include <stdlib.h>

#include <stdio.h>
 

#define MAX_SIZE 512
 

void *mymemory;

struct tree{
 

  void *start;

  int size;

  int number;

  int used;

  struct tree *next;

};
 

typedef struct tree Tree;
 

int my_init(int memsize){

  int ret;
 

  if(memsize <= MAX_SIZE){

    mymemory = malloc(memsize * 1024 * 1024);

    ret = 1;

  }

  else{

    printf("Error: You have requested to much memory.\n");

    printf("Max memory that can be allocated is 512 MB.\n");

    ret = 0;

  }
 

  return ret;

}
 

void *my_malloc(int size, int flag){

  //printf("got in here\n");

  Tree *curr, *head;

  int succeeded;

  int *temp;

  int new_size;

  int i, x, x1, newsize;
 

  succeeded = my_init(size);

 //printf("Got inside the if statement.\n");

    x1 = 0;

    for(i = size; i!=0; i = i/2){

      //printf("%d   ", i); //This prints out the size of the node.

      newsize = 0;

      x = 0;

      while(newsize!=size){

        newsize = newsize + i;

        x++;

        x1++;
 

        curr = (Tree *) malloc (sizeof(Tree));

        curr->size = i;

        curr->number = x1;

        curr->next = head;

        head = curr;

      }

      //printf("   %d.\n", x); //This prints out how many nodes there are.

    }
 

    curr = head;
 

    while(curr){

      //printf("%d----%d\n", curr->size, curr->number);

      if(curr->size == size){

        //***This part of the program selects the main block of memory and makes all nodes unused

        temp = (int *) mymemory;

        curr->used = 1;

        curr->start = mymemory;

        curr->size = size;

        //printf("%d----%d----%d----%d\n", curr->number, temp, curr->size, curr->used);

      }

      curr->used = 1;

      curr = curr->next;

    }

  }
 

  if(flag){

    //Add stuff here to look through the list.

 }
 

}
 

void nodeCreator(int size);
 

int   my_free(void *);

Open in new window

0
 

Author Comment

by:errang
Comment Utility
Oh... about the output here:

1----15
1----14
1----13
1----12
1----11
1----10
1----9
1----8
2----7
2----6
2----5
2----4
4----3
4----2
8----1

The numbers on the left are the size of the nodes and the numbers on the right is their number in the list.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> I've finally settled on using a linked list rather than a binary tree.

That's your choice. But you're making it unnecessarily hard on yourself.


>> And this is how the linked list is going to look like inside the program:

I'm not sure what that output represents ... You should start with only one node, which corresponds to the entire memory block. That node can then be split up as needed (and only when needed).


>> I could use a temp variable to see what's the latest memory with the size that will fit the requests.

Are you implementing the buddy algorithm or something else ?


>> 1) When a user asks for 1 MB of memory... would it be enough to give that memory to one of the 1 MB nodes? Or do I need to give it from top to bottom first?

I'm not sure what you mean ... When a user asks for a 1MB block, you use the buddy algorithm to find such a block that is free (and split up a bigger block if needed).
0
 

Author Comment

by:errang
Comment Utility
>>I'm not sure what that output represents ... You should start with only one node, which corresponds to the entire memory block. That node can then be split up as needed (and only when needed).

Yes, its printing the nodes in reverse order...

1----15
1----14
1----13
1----12
1----11
1----10
1----9
1----8
2----7
2----6
2----5
2----4
4----3
4----2
8----1

8 is the memory block I'm working with, and its the 1st block and goes onto 1 which is the last block.

>>I'm not sure what you mean ... When a user asks for a 1MB block, you use the buddy algorithm to find such a block that is free (and split up a bigger block if needed).

What I'm asking is, I've already got nodes for every size already made at the start of the program, when the user enters the size of the memory block, but I haven't assigned any addresses.

So I'm asking, if it is enough to go to the left most 1 MB block and give it an address.  Rather than going going from top to bottom, like, if the memory block was 4 MB:

I would have to first allocate the 2 MB.
Then I would have to allocate the 1 MB.

Or

If I could just give an address to the 1 MB block and be done with it.
0
 

Author Comment

by:errang
Comment Utility
I got really lazy when I realized I had to actually make my binary tree "smart"... so I figured making a linked list with every size and not giving them an address would be good enough.
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> What I'm asking is, I've already got nodes for every size already made at the start of the program,

Yes, that's what I figured. But there's no reason for that. The buddy algorithm handles this starting from one node.


>> I would have to first allocate the 2 MB.
>> Then I would have to allocate the 1 MB.

Once more : you only allocate the big block. The smaller blocks are within the big block, and don't require further allocation.


>> I got really lazy when I realized I had to actually make my binary tree "smart"... so I figured making a linked list with every size and not giving them an address would be good enough.

I'd say you make your life more complicated than it needs to be. A binary tree is the natural and easiest way of implementing the buddy algorithm. Anything else is likely more complicated.
0
 

Author Comment

by:errang
Comment Utility
Uh.... I clicked the wrong bubbles... =( I blame my lack of sleep.

Can anyone fix that?
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
What do you mean by bubbles ? If you want to re-open this question, simply click the "Request Attention" link, and explain what you want.
0
 

Author Comment

by:errang
Comment Utility
you know those 3 bubbles when we accept an answer....?

I misclicked a few of them and hit submit before looking...
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
0
 

Author Comment

by:errang
Comment Utility
lol, I saw, it, but I just got carried away when I got a response for my other question =)

I requested attention for this.
0

Featured Post

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.

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 is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

771 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

12 Experts available now in Live!

Get 1:1 Help Now