<p>Unfortunately, I can't find any <em>freely available</em> text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation  $M(1+ \log 2 m)$ (where $M$ is total memory size need to allocate and $m$ is the longest allocated block) seems too pessimistic.  I'm almost sure that for $m=2$ the bound is about $M*(3/2)$.</p>

<p>I guess the answer is contained in the article:</p>

<p>Errol L. Lloyd and Michael C. Loui
On the worst case performance of buddy systems
Acta Informatica
Volume 22, Number 4, 451-473, DOI: 10.1007/BF00288778</p>

<p>but I wouldn't want to pay EUR 34.95 for my "general interest" :)</p>

<p>[this question is actually repost from stackoverflow.com
<a href="https://stackoverflow.com/questions/6295558/worst-case-external-fragmentation-in-buddy-memory-systems">https://stackoverflow.com/questions/6295558/worst-case-external-fragmentation-in-buddy-memory-systems</a>
where I got an answer about  $M(1+\log 2 m)$ formula;
but I still don't know the exact bound]</p>

CC BY-SA 3.0
2011-06-30T08:58:36.970Z
The scope of cstheory is research-level *theoretical* computer science. Please read the FAQ.
Kaveh
CC BY-SA 3.0
2011-06-30T09:22:30.470Z
@Kaven I have read the faq. If we consider _theoretical_ in narrow sense then many TCS tags such data-structures etc are totally offtopic (as data structures are rather practical). If we apply _theoretical_ to any statement that may be a theorem  (may be proved) then, I suppose, it is the right place to such questions. Maybe I'm wrong but I don't understand why graph algorithms or sorting ones  are "more theoretical" then memory management algorithms.
user396672
CC BY-SA 3.0
2011-06-30T09:24:26.053Z
@Kaveh: And why is this non-theoretical? After all, it seems to be about mathematically rigorous worst-case analysis of an algorithm. I have voted to re-open.
Jukka Suomela
CC BY-SA 3.0
2011-06-30T10:25:41.343Z
@Jukka, user396672, it seems more like a systems question to me than a DS question. Many branches of CS involve algorithms and mathematical reasoning about them, e.g. networks or computer graphics, but that doesn't make them theoretical computer science. I am reopening the question but I still think this is a borderline case in the best case.
Kaveh
<ds.algorithms><ds.data-structures>
worst case external fragmentation in buddy memory systems
user396672
# worst case external fragmentation in buddy memory systems

(Asked by: username_0 on 2011-06-30)

Unfortunately, I can't find any *freely available* text with an estimation of exact upper bound of (external) fragmentation overhead for (binary) buddy memory allocator. Estimation $M(1+ \log 2 m)$ (where $M$ is total memory size need to allocate and $m$ is the longest allocated block) seems too pessimistic. I'm almost sure that for $m=2$ the bound is about $M\*(3/2)$.

I guess the answer is contained in the article:

Errol L. Lloyd and Michael C. Loui
On the worst case performance of buddy systems
Acta Informatica
Volume 22, Number 4, 451-473, DOI: 10.1007/BF00288778

but I wouldn't want to pay EUR 34.95 for my "general interest" :)

[this question is actually repost from stackoverflow.com
<https://stackoverflow.com/questions/6295558/worst-case-external-fragmentation-in-buddy-memory-systems>
where I got an answer about $M(1+\log 2 m)$ formula;
but I still don't know the exact bound]

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: The scope of cstheory is research-level *theoretical* computer science. Please read the FAQ.  
> **username_0**: @Kaven I have read the faq. If we consider _theoretical_ in narrow sense then many TCS tags such data-structures etc are totally offtopic (as data structures are rather practical). If we apply _theoretical_ to any statement that may be a theorem  (may be proved) then, I suppose, it is the right place to such questions. Maybe I'm wrong but I don't understand why graph algorithms or sorting ones  are "more theoretical" then memory management algorithms.  
> **username_2**: @username_1: And why is this non-theoretical? After all, it seems to be about mathematically rigorous worst-case analysis of an algorithm. I have voted to re-open.  
> **username_1**: @Jukka, username_0, it seems more like a systems question to me than a DS question. Many branches of CS involve algorithms and mathematical reasoning about them, e.g. networks or computer graphics, but that doesn't make them theoretical computer science. I am reopening the question but I still think this is a borderline case in the best case.  

---

## 0 answers

