🚀 go-pugleaf

On 24 Sep 1995 18:20:19 -0700, Kazimir Kylheku (c2a192@ugrad.cs.ubc.ca) wrote:
: In article <DFBHIv.8F2@wombat.hanse.de>,
: Bernd "Bernie" Meyer <root@wombat.hanse.de> wrote:
: >BTW, I just had to learn about fragmentation for an exam --- there is
: >the so called "Knuth's 50% rule" which says that, after extended usage,
: >only 2/3 of the memory will hold meaningful data and the rest is lost
: >to fragmentation. 
: 
: I'm going to have to dig up that Knuth!

"The Art of Computer Programming, vol. 1, (2ed)", p. 445.

   The rule applies to systems that use first-fit allocation and merging of
adjacent blocks on deallocation, and when allocations of partial blocks are
made (i.e., if we need 197 bytes, and the first free block has 800 bytes,
we return, say 200 bytes, and keep a 600-byte block in the free list.

    Assuming that blocks have random lifetimes, (which may or may not
be a reasonable assumption), when the system is near equilibrium, and when 
we are rounding up allocations by a small amount, and when block sizes are
infrequently equal to one another, we end up with approximately half as
many free blocks as we have allocated blocks in the list.

    I'm not certain that these assumptions have any value when considering
the behavior of an individual program, and with VM, this rule might _ONLY_ 
apply to an individual program's heap.  Allocation of pages from the OS
are always done in even multiples of the page size, which invalidates the
rule.  Even within a single program's heap, the random lifetime assumption
is questionable, as is the infrequently equal size assumption.  

    In any case, Knuth does _NOT_ imply that said free blocks are lost to
fragmentation.  They are very much available, and will be used, if necessary.

-- 
the Windows API has done more to retard skill development
than anything since COBOL maintenance.
                           --Larry O'Brien