Solved

Buddy algorithm

Posted on 2004-10-19
7
1,815 Views
Last Modified: 2008-02-01
What is buddy algorithm for dynamic allocation of memory. Plz explain with a snippet of code
Thanks in advance
0
Comment
Question by:saurabhramya
  • 2
7 Comments
 
LVL 12

Accepted Solution

by:
OnegaZhang earned 168 total points
ID: 12355699
0
 
LVL 55

Expert Comment

by:Jaime Olivares
ID: 12357915
Here is an interesting application (and theory) about the buddy algorithm:
http://www.cse.seas.wustl.edu/techreportfiles/getreport.asp?269
0
 
LVL 55

Assisted Solution

by:Jaime Olivares
Jaime Olivares earned 166 total points
ID: 12357991
0
 

Assisted Solution

by:rraghu77
rraghu77 earned 166 total points
ID: 12443698
Have a look at the code below.....
Its very primitive....not robust(doesnt free memory)....but will demonstrate the algorithm
its implemented for only 16, 32 and 48 byte blocks.....
Warning: no stress test....it may bomb
Let me know if this helps.......

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

// Buddy Algorithm for 16, 32, 48 blocks
struct Memory_Chunk
{
   char * mem_ptr;
   int mem_size;
   Memory_Chunk * next;
};

// globals
Memory_Chunk * block_16_list = 0; // blocks of 16 bytes
Memory_Chunk * block_32_list = 0; // blocks of 32 bytes
Memory_Chunk * block_48_list = 0; // blocks of 48 bytes
const unsigned int NUM_BLOCKS = 2u; // number of blocks

Memory_Chunk * allocate_chunk(unsigned int chunk_size)
{
  Memory_Chunk * mem = (Memory_Chunk *)malloc(sizeof(Memory_Chunk));
  memset(mem, 0, sizeof(Memory_Chunk));
  mem->mem_ptr = (char*)malloc(chunk_size);
  mem->mem_size = chunk_size;

  return mem;
}

Memory_Chunk * make_mem_list(unsigned int mem_chunk_size,
                             unsigned int chunk_count)
{
   Memory_Chunk * head = allocate_chunk(mem_chunk_size);
   Memory_Chunk * cur_ptr = head;
   for(unsigned int i_chunk = 1u; i_chunk < chunk_count; i_chunk ++)
   {
      Memory_Chunk * ptr = allocate_chunk(mem_chunk_size);
      cur_ptr->next = ptr;
      cur_ptr = cur_ptr->next;
   }
   return head;
}
void add_to_list(Memory_Chunk* mem_chunk)
{
   Memory_Chunk ** list_ptr =
      (Memory_Chunk **) malloc(sizeof(Memory_Chunk *));

   switch(mem_chunk->mem_size)
   {
   case 16:
      list_ptr = &block_16_list;
      break;
   case 32:
      list_ptr = &block_32_list;
      break;
   case 48:
      list_ptr = &block_48_list;
      break;
   }
   if (!*list_ptr)
      *list_ptr = mem_chunk;
   else
   {
      Memory_Chunk * ptr = *list_ptr;
      while(ptr->next)
         ptr = ptr->next;
      ptr->next = mem_chunk;
   }
}

void* split_chunk(Memory_Chunk* mem_chunk)
{
   // To split the chunk, memory is freed and
   // reallocated accordingly
   void * ret_mem_ptr = 0;

   free(mem_chunk->mem_ptr);

   switch(mem_chunk->mem_size)
   {
   case 32:
      // split to 16 bytes chunk
      add_to_list(allocate_chunk(16));
      ret_mem_ptr = malloc(16);
      break;
   case 48:
      // split to 16 and 32 byte chunks
      add_to_list(allocate_chunk(16));
      ret_mem_ptr = malloc(32);
      break;
   }
   free(mem_chunk); // free the structure.
   return ret_mem_ptr;
}

void* request_memory(unsigned int chunk_size)
{
   Memory_Chunk * free_list_ptr = 0;
   Memory_Chunk ** list_ptr =
      (Memory_Chunk **) malloc(sizeof(Memory_Chunk *));
   Memory_Chunk * prev_ptr = 0;
   void * mem_chunk_ptr = 0;
   bool split_required = false;

   if ( (chunk_size <= 16) && block_16_list)
   {
      free_list_ptr = block_16_list;
      list_ptr = &block_16_list;
   }
   else
   if ( (((chunk_size > 16) && (chunk_size <= 32) && (block_32_list))) ||
         (!block_16_list && block_32_list) )
   {
      if ((!block_16_list && block_32_list))
         split_required = true;

      free_list_ptr = block_32_list;
      list_ptr = &block_32_list;
   }
   else
   if ( (((chunk_size > 32) && (chunk_size <= 48) && (block_48_list))) ||
         (!block_32_list && block_48_list) )
   {
      if (!block_32_list && block_48_list)
         split_required = true;

      free_list_ptr = block_48_list;
      list_ptr = &block_48_list;
   }
   else
   {
      printf("No free memory");
      return 0;
   }

   prev_ptr = free_list_ptr;
   while(free_list_ptr->next)
   {
      prev_ptr = free_list_ptr;
      free_list_ptr = free_list_ptr->next;
   }

   // get the address of the memory chunk
   mem_chunk_ptr = free_list_ptr->mem_ptr;

   if (prev_ptr->next)
   {
      prev_ptr->next = 0; // Remove the node
   }
   else
   {
      *list_ptr = 0; // end of the list
   }

   if (split_required)
   {
      mem_chunk_ptr = split_chunk(free_list_ptr);
   }
   else
   {  
      free(free_list_ptr); // free the structure.
      free_list_ptr = 0;
   }
   return mem_chunk_ptr; // return the memory chunk
}


void main()
{
   block_48_list = make_mem_list(48, NUM_BLOCKS);
   void * mem = request_memory(30); // 30 is number of bytes
}

0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

919 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

17 Experts available now in Live!

Get 1:1 Help Now