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]

  • $\begingroup$ The scope of cstheory is research-level theoretical computer science. Please read the FAQ. $\endgroup$ – Kaveh Jun 30 '11 at 8:58
  • 1
    $\begingroup$ @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. $\endgroup$ – user396672 Jun 30 '11 at 9:22
  • 3
    $\begingroup$ @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. $\endgroup$ – Jukka Suomela Jun 30 '11 at 9:24
  • $\begingroup$ @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. $\endgroup$ – Kaveh Jun 30 '11 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.