[gclist] Real-Time GC for high-level languages

[Andrew Cheadle]

Hi

I would direct you to Richard Jones' garbage collection pages:
http://www.cs.ukc.ac.uk/people/staff/rej/gc.html - it's probably the
best resource around for all types of GC info.

> On Tue, 30 Jan 2001, Francois-Rene Rideau wrote:
> "soft real-time". What does that mean? When do they fail?

A hard realtime system is one which can guarantee that a certain action
will always be carried out in less than a certain time.

... in the context of gc:

My experiences result from ongoing work to implement an incremental
garbage collector into GHC, The Glasgow Haskell Compiler.

Whilst theoretically possible to bound gc pause times (the amount of time the
user program is paused while the garbage collector runs) it is actually
very difficult to achieve in practice. Hard real-time guarantees the
pause time to be no more than a specified time. Soft real-time whilst
attempting in the best case to achieve the bounded pauses times equated
with hard real-time cannot make the same guarantees in the worst case.

Our prototype compiler gave us pause times on average of the order of
microseconds... but we couldn't guarantee the pause times for collecting
large objects such as arrays (there is a trade off in the efficiency of
the array access implementation versus the how it is gc'd).

I seem to remember a theoretical paper:
 Guy E. Blelloch, Perry Cheng: On Bounding Time and Space for
Multiprocessor Garbage Collection. PLDI 1999: 104-117

which makes claims of bounded pause times. I believe, but I'm not sure,
that Perry Cheng was looking at implementing the techniques mentioned in
the above paper in the TILT ML compiler:

http://www.cs.cornell.edu/Info/People/jgm/tilt.html

I don't know how far he has got.

Apart from that I know that the Open-source Erlang provides only
soft real-time behaviour. I'm not sure I'm aware of any hard real-time
systems out there that use 'standard' gc techniques. I think I'd agree with
Neel Krishnaswami's suggestion that maybe a region based approach or
something closer to techniques used in emmbedded systems maybe what you
want, but I really don't know much about them, I'm just guessing!

Hope that helps!

Cheers

Andy

*********************************************************************
*  Andrew Cheadle                    email:  a.cheadle@doc.ic.ac.uk *
*  Department of Computing           http://www.doc.ic.ac.uk/~amc4/ *
*  Imperial College                                                 *
*  University of London                                             *
*********************************************************************