Memory Management Algorithms for Hard Realtime

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

Some time ago we had a sometimes heated debate about the practicality of
memory managers more complex than simple fixed-block list allocators for
use in realtime.  Since then, I have continued to dig.  

My major find is a book summarizing the literature:  "Garbage Collection
-- Algorithms for Automatic Dynamic Memory Management", Richard Jones and
Rafael Lins, 377 pages, Wiley 1996.  I stumbled on it in a local technical
bookstore.  Sometimes you just get lucky.

So, of course I looked in the index under "real-time", and found three
specific entries:

Page 11:  "The problem of garbage collection for hard real-time
programming has yet to be solved without the use of special hardware".

Page 184:  "Many incremental algorithms are described by their authors as
'real-time'.  Hard real-time systems demand that results be computed on
time: a late result is as useless as an incorrectly calculated one.  Such
systems require worst-case guarantees rather than average-case ones, and
these may need to be in the order of one millisecond."  [They have the
right idea, but a millisecond would be just intolerably slow.  Try ten to
at most one hundred microseconds, while handling worst-case load.]

Page 250:  "It is certainly true that current garbage collection
technology is not yet suitable for programs with hard real-time
constraints on stock hardware or for safety-critical applications."

The work of Kelvin Nilsen (not Nielsen), who was mentioned by some people
in the newsgroup as having solved the realtime memory management problem,
is heavily cited in this work.  By their titles, most of the cited Nilsen
articles involve hardware support for garbage collection.


The clear conclusion of this book is that there are no hard realtime
memory manager algorithms known, unless one resorts to special hardware. 
The authors are university professors who have studied the field, with a
377-page book to show for it.  This lack of suitable algorithms has
certainly been my personal experience as well, and is why I always
doggedly stuck to fixed-block allocators.


Joe Gwinn