Talk:Buddy memory allocation

"Compared to the memory allocation techniques (such as paging) that modern operating systems such as Microsoft Windows and Linux use, the buddy memory allocation is relatively easy to implement, and does not have the hardware requirement of a memory management unit (MMU)."

The article suggests that Linux doesn't use the buddy system, although all papers and books discussing Linux memory allocation suggest otherwise. For example, a few sources: [1] [2] Even if the author didn't want to imply that buddy algorithm is not used in Linux, in my opinion the sentence has an awkward construction that suggests this.

Also, paging isn't a memory allocation technique.

"This method of freeing memory is rather efficient, as compaction is done relatively quickly, with the maximal number of compactions required equal to 2^u / 2^l (i.e. 2^u-l)."

I think this estimation isn't correct. The correct one is log₂(U)/log₂(I) (i.e. log₂(U-I).

For example, if U equals 8 and I equals 1, we have to do maximal number of compactions 3. If we use actual formula in the article we get 2⁷ what is obviously not correct. Thank you. 89.31.88.159 (talk) 09:13, 16 March 2008 (UTC)[reply]

Won't there (maximally) be a lot more than 3 (log₂(u-l)) compactions as you divide 2⁸ (256 byte) blocks down into (potentially) many, many, many 2¹ (2 byte) blocks?
199.204.56.17 (talk) 15:26, 28 June 2011 (UTC)[reply]

The implications of a lower limit of the "smallest possible block"[edit]

"However, a lower limit independent of hardware limitations may also be desirable, so that the overhead of storing used and free memory locations is minimized. If no lower limit existed at all, and many programs requested small blocks of memory like 1K or less, the system would waste a lot of space relative to the size of the blocks simply to keep track of which blocks are allocated and unallocated."

The above is WRONG. A lower limit (of the "smallest possible block") increases the computational overhead. It is the higher limit (again, of the "smallest possible block") that increases the waste of memory. Furthermore, the above conflicts with what follows:

"Typically the lower limit would be small enough to minimize wasted space, but large enough to avoid excessive overhead."

S00N(TM), I will correct this. — Preceding unsigned comment added by 84.2.109.111 (talk) 14:07, 3 September 2012 (UTC)[reply]

Assume you need 1 bit to store whether a block is free. If the smallest block is 1000 bits in size you waste at least 1/1000th of the total memory for keeping track of blocks of that size. If the smallest block is 100000 bits in size you only waste 1/100000th of the total memory for the same thing. So why is it wrong? CodeCat (talk) 15:42, 3 September 2012 (UTC)[reply]

We have several different terms:

computational (time) overhead
memory overhead
memory waste

It is correct that a lower limit not only increases the computational overhead, but also slightly increases the memory overhead. A larger limit decreases the computational overhead, slightly decreases the memory overhead, but drastically increases the memory waste: in case of a 1000000-bit smallest possible block, allocating 512 bits of memory comes with 1000000 - 512 = 999488 bits of waste.

Again, the quoted statement says it well: "Typically the lower limit would be small enough to minimize wasted space, but large enough to avoid excessive overhead.". — Preceding unsigned comment added by 78.92.70.174 (talk) 17:30, 4 September 2012 (UTC)[reply]