Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Buddy algorithm

Posted on 2004-10-19
Medium Priority
1,833 Views
What is buddy algorithm for dynamic allocation of memory. Plz explain with a snippet of code
0
Question by:saurabhramya
[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
• 2

LVL 12

Accepted Solution

OnegaZhang earned 672 total points
ID: 12355699
0

LVL 55

Expert Comment

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

Jaime Olivares earned 664 total points
ID: 12357991
0

Assisted Solution

rraghu77 earned 664 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)
{
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;
}
}
{
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
ret_mem_ptr = malloc(16);
break;
case 48:
// split to 16 and 32 byte chunks
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

Question has a verified solution.

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

Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
###### Suggested Courses
Course of the Month11 days, 17 hours left to enroll