Re: [MiNT] memory fragmentation

[joska@nuts.edu (Jo Even Skarstein)]

On Sun, 15 Aug 1999 16:22:25 +0200, Guido Flohr wrote:

> Apart from the need for VM I think that there are really some things
> that could at least reduce fragmentation.  My first idea shouldn't be
> that hard to implement: Under Magic the kernel evaluates a program
> flag that tells the kernel that the program has reserved space for
> the stack in the BSS.  This makes a big difference: If this flag is
[...]
> end that has the same effect as the Magic approach: The kernel could
> deduce the optimum size for the TPA at runtime, thus making more
> efficient use of smaller memory blocks.

I think we discussed this last year... Let me quote from Tanenbaum's
"Modern operating systems":

"Another well-known algorithm is best fit. Best fit searches the entire
list and takes the smallest hole that is adequate. Rather than breaking
up a big hole that might be needed later, best fit tries to find a hole
that is close to the actual size needed."
[...]
"Best fit is slower than first fit because it must search the entire list
every time it is called. Somewhat surprisingly, it also results in more
wasted memory than first fit or next fit because it tends to fill up
memory with tiny, useless holes. First fit generates larger holes on the
average.

To get around the problem of breaking nearly exact matches into a process
and a tiny hole, one could think about worst fit, that is, always take the
largest available hole, so that the hole broken off will be big enough to
be useful. Simulation has shown that worst fit is not a very good idea
either."

So it seems that the best way to do it is just to use the first block
you find that's large enough. A relatively easy way to see if this is the
case, one could modify the kernel's malloc to return the first large
anough block ("first fit") and then use a special version ("worst fit")
in pexec.

But ofcourse, this does not really solve any problems...


/*
** Jo Even Skarstein    http://www.stud.ntnu.no/~josk/
**
**    beer - maria mckee - atari falcon - babylon 5
*/