Memory Management Algorithms for Hard Realtime

Memory Management Algorithms for Hard Realtime

[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

Re: Memory Management Algorithms for Hard Realtime

[Robert Dewar]

Joe said

<<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.
>>

That's a non-sequitur.

The book you talk about is, if we believe its title, about *automatic*
memory management. 

There are many algorithms for allocating variable sized blocks with
*manual* allocation/release control that have well defined worst
case behavior.

Nothing you summarize in the rest of your message even hints that
this is not the case!

Re: Memory Management Algorithms for Hard Realtime

[Joe Gwinn]

In article <dewar.887767452@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Joe said
> 
> <<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.
> >>
> 
> That's a non-sequitur.

Could you explain this?  I don't see your point.


> The book you talk about is, if we believe its title, about *automatic*
> memory management. 
> 
> There are many algorithms for allocating variable sized blocks with
> *manual* allocation/release control that have well defined worst
> case behavior.

I wasn't planning to come along in a missile running the memory management
system, so automatic seems best.  What am I missing?

 
> Nothing you summarize in the rest of your message even hints that
> this is not the case!

Dr. Dewar, I await your list of literature references.


Joe Gwinn

Re: Memory Management Algorithms for Hard Realtime

[Brian Rogoff]

On Wed, 18 Feb 1998, Joe Gwinn wrote:
> In article <dewar.887767452@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
> > The book you talk about is, if we believe its title, about *automatic*
> > memory management. 
> > 
> > There are many algorithms for allocating variable sized blocks with
> > *manual* allocation/release control that have well defined worst
> > case behavior.
> 
> I wasn't planning to come along in a missile running the memory management
> system, so automatic seems best.  What am I missing?

Automatic memory management = garbage collection, i.e., all freeing
operations are done by *implicitly* by the runtime, so there are no
explicit calls to free/Unchecked_Deallocation. Read the book, and this
will become clear.

Manual memory management is where you the programmer must explicitly
invoke some freeing operation to return memory that you've allocated.
It doesn't mean that you interactively free memory from a running program,
as you seem to suggest. Its what you're doing now, if you are using fixed 
size block allocators.

-- Brian

Re: Memory Management Algorithms for Hard Realtime

[Nick Roberts]

Joe Gwinn <gwinn@res.ray.com> wrote in article
<gwinn-1802981847520001@dh5055200.res.ray.com>...
> In article <dewar.887767452@merv>, dewar@merv.cs.nyu.edu (Robert Dewar)
wrote:
> > The book you talk about is, if we believe its title, about *automatic*
> > memory management. 
> > 
> > There are many algorithms for allocating variable sized blocks with
> > *manual* allocation/release control that have well defined worst
> > case behavior.
> 
> I wasn't planning to come along in a missile running the memory
management
> system, so automatic seems best.  What am I missing?

Surely you could really get to see the world, strapped to the back of a
cruise missile?

== Nick Roberts ================================================
== Croydon, UK                       ===========================