Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!mcsun!ukc!icdoc!cam-cl!scc
From: scc@cl.cam.ac.uk (Stephen Crawley)
Newsgroups: comp.sw.components
Subject: Re: Real-time Garbage Collection
Message-ID: <890@scaup.cl.cam.ac.uk>
Date: 19 Sep 89 00:25:38 GMT
References: <91482@ti-csl.csc.ti.com> <6488@hubcap.clemson.edu>
Sender: news@cl.cam.ac.uk
Organization: U of Cambridge Comp Lab, UK
Lines: 67

The most important distinction between ordinary and real-time programs
is that the real-time programs need to execute in predictable time.  
An ordinary synchronous garbage collector that stops execution for a 
non-trivial amount of time is clearly not acceptable in this context.
But an asynchronous garbage collector that allows GC to be done in
short burst during periods of inactivity MAY be ok for real-time 
programming.  

The key question that determines whether or not asynch GC will work in
real-time is whether there is enough idle time to keep up with garbage 
collection.  In many cases the answer should be yes!  And if the answer 
is no, it may be possible to MAKE more idle time can be made by 1) using 
a faster processor or 2) moving the tasks of garbage collection onto a
second processor.  Only when we are pushing the limits of the hardware
will the answer be no. 

A second question that affects the viability of GC in a real-time program
is how much garbage gets generated.  I claim that for most of real-time 
program that are being written today, the answer is "not a lot".  If a 
programmer can decide to free a piece of dynamic on exiting a scope block, 
then a smart compiler could usually make the same decision in many cases.
Similarly a smart compiler should be able to optimise storage reclamation
in other cases.  [It is my guess that the main reason that compilers that 
optimise GC don't exist is that the industry is prejudiced against GC]

There are of courses the cases that cannot be solved by freeing stuff on 
scope exit, or by other static tricks.  In such cases, the non-GC'ed 
solution MUST handled by the application.  Bill Wolfe seems to be saying
that such situations almost never arise in real-time problems.  This may
be true right now, but it won't be long before the military start asking 
for real-time AI!

Finally, I'd like to rebut the idea that ADT's that do their own storage
management are appropriate for use in a GC'ed environment.  If a type 
does its own management, then in order to get it to do its stuff, it must
export an explicit destructor operation or its equivalent.  How / when does 
the destructor get called?  There are 2 options as I see it:

1)	A type that refers to a non-GC'ed type becomes non-GC'ed, and must
	have a destructor operation.  We soon find that large parts of our
	application have to understand storage management policy. 
	
2)	We arrange that the garbage collector provides hooks for calling
	an object's destructor operation when the object becomes garbage
	in the conventional sense.  This makes garbage collection more
	complicated.  For example, when the GC finds some garbage instances 
	of ADT's with a destructor, it must decide on the correct order to 
	destroy them.

In either case, we end up with the problems we were trying to avoid by 
using garbage collection; complication for the application, and lots of 
potential for storage leaks and other bugs. 

In summary, we need to recognise 3 things:

o  A GC'ed language is the only sane approach to many hard programming
   problems.  Some of these problems WILL also be real-time problems.

o  A GC'ed language is not necessarily inappropriate for real-time
   problems.  It depends on the problem, the tools (GC and compiler)
   and on the hardware.

o  GC'ed languages and non-GC'ed packages don't mix, so we should
   not try to mix them.  This is a case where software reuse is NOT
   appropriate.
   
-- Steve