x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1872

# Buddy algorithm

What is buddy algorithm for dynamic allocation of memory. Plz explain with a snippet of code
0
saurabhramya
• 2
3 Solutions

Commented:
0

Software ArchitectCommented:
Here is an interesting application (and theory) about the buddy algorithm:
http://www.cse.seas.wustl.edu/techreportfiles/getreport.asp?269
0

Software ArchitectCommented:
0

Commented:
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;
}
}
{
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 2
Tackle projects and never again get stuck behind a technical roadblock.