CODEWITHSUNDEEP
memorymemory-managementoperating-systemallocation
Druudik
Druudik

Reputation: 1015

Buddy memory allocation

I have the array of size n which represents my main memory. I can not use operator new, I have only access to that memory so every data structure must use only that array to store data. I am trying to build memory allocator which will be able to quickly find free portions of that memory (array) and also free them. I want to build tree structure over that array - buddy memory allocation - but I am struggling with understanding few concepts.

How exactly is buddy system looking for free chunk of memory using binary tree ?

How should I store this tree in the array ?

How can I create new nodes of that tree (should I just reserve enough space for my tree at the beginning of the program or "allocate" it dynamically - but how to do it simply) ?

I kinda have the answers to these questions but I am struggling with fully understanding it. I would appreciate every clear answer and help. Thank you.

Upvotes: 0

Views: 1209

Answers (1)

Minor Threat
Minor Threat

Reputation: 2095

  1. Take a look at binary heap. This structure represents a tree inside an array.
  2. Take a look at Aleksandrescu's small object allocator from his book. In the second chapter (AFAIR) he describes a practical approach to embed ~8-~128 bytes long structures inside an external byte array with no overhead.

Upvotes: 1

Related Questions