Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!mit-eddie!uw-beaver!tektronix!tekcrl!tekchips!allenw
From: allenw@tekchips.UUCP
Newsgroups: comp.lang.smalltalk
Subject: Re: Smalltalk for (embedded) real-time
Message-ID: <1697@tekchips.TEK.COM>
Date: Wed, 16-Sep-87 12:29:19 EDT
Article-I.D.: tekchips.1697
Posted: Wed Sep 16 12:29:19 1987
Date-Received: Sat, 19-Sep-87 07:11:21 EDT
References: <1881@tekig4.TEK.COM> <12100004@osiris.cso.uiuc.edu> <1320@pdn.UUCP>
Organization: Tektronix Inc., Beaverton, Or.
Lines: 54
Summary: Large objects aren't really a problem with generation scavenging, cross generation circularities are ...

In article <1320@pdn.UUCP>, ken@pdn.UUCP (Ken Auer) writes:
> take care of most small garbage objects for you.  If I'm not mistaken, 
> generation scavenging does not work at all for "large" objects (where the 
> definition of "large" may be different from implementation to implementation).  
> As a previous article states, eventually the "major garbage collection" must
> take place in order to get rid of large objects, and to compact your memory 
> due to its tendency to become extremely fragmented.  I'm not familiar with 
> every implementor's method for GC, but I don't think you can really totally 
> avoid it.  Keeping the number of large objects to a minimum can greatly
> ameliorate the frequency of "the garbage collection symbol" in most
> implementations.  

The reclaimation of "large objects" can be easily handled by
a generation scavenging storage manager.  The technique used
to accomplish this in Tektronix Smalltalk is described in
our OOPSLA'86 paper.  While the fragmentation of memory
used to store large objects could be a problem, in practice,
we have not observed it to be so.  Our implementations
reclaim but DO NOT compact the large object area.  Reclaimed
storage is placed on a free list which is available for future
large object allocations.  If free space is unavailable because
of fragmentation (or any other reason) we simply expand our
virtual address space.  This, of course, requires an underlying
virtual memory operating system which might not be present in
an embedded system implementation.  In such a situation we would
probably compact the large object area when necessary (or incrementally).
For current Smalltalk system, the main source of "large objects"
appears to be saved bitmaps used to refresh obscured windows.
I suspect that many embedded applications would not require them.

While large objects need not be a problem, cross-generation circularities
can be.  A cross-generations circularity is a circular data structure
which spans more than one generation.  If such a structure becomes
garbage, it can not be reclaimed until all the objects of the
structure have "graduated" to a common generation (the generaton of
the oldest object in the structure).  The worst case occurs when the
circular structure includes a object in the highest (longest lived)
generation.  All the objects of must then graduate to the oldest
generation and the oldest generation must be scavenged before any
of the objects can be reclaimed.  Since scavenging of the oldest
generation is essentially equivalent to a stop-and-copy garbage
collection of the entire object space it can be very expensive.
Such problems can often be avoided by breaking circularities
(via the #release message in Smalltalk-80).  Unfortunately, this
is the same problem that occurs with reference counting schemes
and the solution (breaking circularities) has the same undesirable
impact of requiring application programmers to worry about storage
management.


	Allen Wirfs-Brock
	Software Productivity Technologies
	Tektronix, Inc.
	allenw%spt.tek.com@relay.cs.net