Variable-block memory managers bad in realtime

[gwinn@res.ray.com (Joe Gwinn)]

Robert Dewar said:

> This is an over-generalization, there are algorithms known that provide
> variable size allocation with constant performance. These algorithms are
> the ones that should be used for real time performance.

The historical problem with such algorithms, many of which are quite good,
is that they aren't *perfect*, and there is always a spectrum of
allocations and deallocations that will cause failure, because their
design depends on statistical regularities of one kind or another.  

Another reason we have always avoided such algorithms is that they were
too complex for us to prove that they would *never* jam, even after months
of continuous heavy field use without a system reset.  Even the slightest
memory leakage or fragmentation will accumulate and become a problem under
such a scenario.

With UNIX X/Windows systems, we have found it necessary to periodically
reset the platform to reclaim the leaked memory (at various levels in the
system).  If one provides enough memory, and presses hard enough on
finding the leaks, resets may be done as part of standard scheduled
preventive maintenace.

I have repaired my share of systems that used something other than a
simple fixed-block memory manager; the fix was always to revert to a
linked-list fixed-block memory manager with something like six different
sizes of block.


That said, I would be curious for references to your favorite memory
management algorithms.  


As for malloc() and free() in VxWorks, I talked to Wind River today, and
they said that their malloc uses a standard first-fit algorithm, and they
do not claim that it is absolutely fragmentation proof.  Most mallocs use
first-fit, actually, so the point of there being a VxWorks malloc is to
tie it to VxWorks' underlying OS memory allocator, just as UNIX systems'
malloc calls on the UNIX kernel to get more memory for the calling UNIX
process when the process heap is exhausted.  All in all, Wind River made
no claim of special realtime abilities for their malloc.


Joe Gwinn