Path: utzoo!attcan!uunet!cs.utexas.edu!hellgate.utah.edu!mailrus!ncar!gatech!hubcap!billwolf%hazel.cs.clemson.edu
From: billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu (William Thomas Wolfe, 2847 )
Newsgroups: comp.sw.components
Subject: Re: Real-time Garbage Collection
Message-ID: <6554@hubcap.clemson.edu>
Date: 23 Sep 89 20:48:04 GMT
References: <901@scaup.cl.cam.ac.uk>
Sender: news@hubcap.clemson.edu
Reply-To: billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu
Lines: 60

From scc@cl.cam.ac.uk (Stephen Crawley):
> Bill Wolfe proposes a scheme for getting around the need for garbage 
> collection by storing objects in a database, using object expiration 
> times to avoid proper garbage collection.  Unfortunately this scheme
> doesn't achieve its aim. 
>
>   "Where objects can have an infinite lifetime, a protocol can be devised 
>    whereby the database must be checked at least once per some arbitrary 
>    time period by all users, which will permit identification numbers 
>    to be recycled after one full time period of nonexistence."
>
> Exactly.  In order to check each object that it still refers to, each 
> "user" (actually application) must traverse the graph of its objects in 
> the database.  This process is exactly equivalent to the mark phase of 
> a garbage collection, except that the application is doing it!!!

   Not exactly.  To start with, the user does not have to do any work
   at all if the identification number's expiration period is also used
   as the period over which the user will lose interest in the object if
   it is not further utilized.  In this case, the identification number
   will be allowed to expire and the user need only throw it away.

   If the user does make use of the number within the expiration period,
   then the number is automatically revalidated for another period unless
   the database replies that the object has been destroyed, in which case
   the identification number expires as well.

   In the worst case, the user will have to do a database access just to
   verify that the object still exists and that the identification number
   remains valid for another expiration period.  Since many objects have
   a finite lifetime, this burden is borne only by those users who make
   use of infinite-lifetime objects.  The task of maintaining the validity
   of the identification number can be done automatically if desired using
   a suitably designed identification-number abstraction which carries a 
   user-settable automatic revalidation on-off switch.  

   There are no reference counts kept at the database; the database only
   maintains the object, the associated identification number, and any
   authorization protocols which may be required of users who wish to
   create, read, modify, or destroy.  The expiration period protocol
   allows identification numbers to be distributed without limitation
   (to systems which are unknown to the database, possibly not even
   reachable).  It is fault-tolerant, allowing users to die with their
   identification numbers intact without interfering with the destruction
   of the associated object.  If the user wakes up, the user can either
   continue to utilize the identification number (if it has not expired),
   or throw it away due to its expiration. 

> One other point that Bill Wolfe misses is that the CPU overheads of 
> managing objects in this way can be orders of magnitude greater
> than the cost of using ordinary pointers.

   Where the situation permits (as it usually does), pointers which are
   encapsulated within ADT implementations will give better performance.
 
   We are managing objects in this way because they present worst-case
   properties which do not permit us to use more efficient techniques.

 
   Bill Wolfe, wtwolfe@hubcap.clemson.edu