[gclist] Re: gclist-digest V2 #142

[Marc Shapiro]

 || Date: Mon, 10 Aug 1998 04:58:14 -0700 (PDT)
 || From: Patrick Panke <panke@rocketmail.com>
 || Subject: [gclist] DSM and GC 
 || 
 || [I] have to implement a distributed garbage
 || collection algorithm that collects objects in a
 || shared memory environment.
 || 
 || Ideally it should have the following prperties:
 ||  - collect most garbage fast and 
 ||    without expensive commonication
 ||  - eventually collect all garbage
 ||  - run concurrently to the mutators
 ||  - do not use read/write locks on objects
 ||  - collect unneeded replicas of objects

Very few authors have looked at this problem.  The work I am aware of is
the following:
 - Ferreira and Shapiro, INRIA
 - Yu and Cox, Rice University
 - Gruber and Amsaleg, INRIA
 - Schuster, Technion
I am providing citations for all the above at the end of this message
(except Schuster, but you can look at his Web page
http://www.cs.technion.ac.il/Labs/Millipede)

For background, you should also know about GC algorithms for
multiprocessors. However they do not have the right properties for a DSM
(specifically they assume memory coherence and take locks).

The closest you will find to your requirements is Larchant.  Larchant
does not promise to eventually collect all garbage, and indeed I think
this is appropriate, because as your system scales up in size you will
find that any complete collector will slow down.  (I am one of the
authors of the Larchant algorithm.)

I'm not sure what you mean by "collect unneeded replicas"; if any
replica is reachable, then all replicas of this object are equally
reachable.  Suppose on some node there is no path to the local replica
of object X.  If X is reachable at another node, then there is a path to
X, which the coherence algorithm may make available at this node
sometime in the future.

I don't know where you got the impression that Larchant is not
efficient.  Indeed Paulo Ferreira's thesis contains performance
measurements that show it has almost identical performance (at every
site) to a local, single-site collector.  In other words its distributed
nature carries virtually no overhead.

I am including citations for all the above.

@InProceedings{prs:1080,
  author = 	 "Gruber, Olivier and Amsaleg, Laurent",
  title = 	 "Object Grouping in {EOS}",
  pages = 	 "184--201",
  booktitle = "Proc.\ Int.\  Workshop on
		  Distributed Object Management",
  year = 	 1992,
  address = 	 "Edmonton ({C}anada)",
  month = 	 aug,
  note =         "\url{ftp://rodin.inria.fr/pub/publications/conferences/IWDOM.92.ps.gz}"
}

@InProceedings{fic:prs:1159bis,
  author = 	 "Ferreira, Paulo and Shapiro, Marc",
  title = 	 "Distribution and Persistence in Multiple and
		  Heterogeneous Address Spaces",
  booktitle =	 "Proc.\ Int.\ Workshop on Object-Orientation in
		  Operating Systems",
  year =	 1993,
  address =	 "Asheville NC {(USA)}",
  month =	 dec
}

@InProceedings{gc:rep:sor:1223,
  author = 	 "Ferreira, Paulo and Shapiro, Marc",
  title = 	 "Garbage Collection of Persistent Objects in
		  Distributed Shared Memory",
  pages =	 "176--191",
  booktitle =	 "Proc.\ of the 6th Int.\ Workshop on Persistent
		  Object Systems",
  year =	 1994,
  publisher =	 "Springer-Verlag",
  address =	 "Tarascon (France)",
  month =	 sep,
  note =         "\url{http://www-sor.inria.fr/publi/GC-PERS-DSM_POS94.html}"
}

@InProceedings{gc:mv:rep:sor:1227ter,
  author = 	 "Shapiro, Marc and Ferreira, Paulo",
  title = 	 "Larchant-{RDOSS}: a Distributed Shared Persistent
		  Memory and its Garbage Collector",
  booktitle = 	 "Workshop on Distributed Algorithms (WDAG)",
  year = 	 1995,
  editor =	 "J.-M. H\'elary and M. Raynal",
  number =	 972,
  series =	 "Springer-Verlag LNCS",
  pages =	 "198--214",
  address =	 "Le Mont Saint-Michel (France)",
  month =	 sep,
  note =         "\url{http://www-sor.inria.fr/publi/LRDSPMGC_wdag95.html}"
}

@InProceedings{sos:gc:dsm:1356,
  author = 	 "Ferreira, Paulo and Shapiro, Marc",
  title = 	 "Larchant: Persistence by Reachability in Distributed
                  Shared Memory through Garbage Collection",
  booktitle = 	 "Proc.\ 16th Int.\ Conf.\ on Dist.\ Comp.\ Syst.\ (ICDCS)",
  year = 	 1996,
  address =	 "Hong Kong",
  month =	 may,
  note  =	 "\url{http://www-sor.inria.fr/publi/LPRDSMGC:icdcs96.html}"
}

@PhdThesis{gc:rep:1371,
  author = 	 "Ferreira, Paulo",
  title = 	 "{L}archant: ramasse-miettes dans une m\'{e}moire partag\'{e}e r\'{e}partie avec persistance par atteignabilit{\'{e}}",
  school = 	 "Universit\'{e} Paris 6, Pierre et Marie Curie",
  year = 	 1996,
  address =	 "Paris (France)",
  type =	 "Th\`{e}se de doctorat",
  month =	 may,
  note =         "\url{http://www-sor.inria.fr/publi/ferreira_thesis96.html}"
}

@InProceedings{gc:dsm:1380,
  author = 	 {Weimin Yu and Alan Cox},
  title = 	 {Conservative Garbage Collection on Distributed Shared Memory
                  Systems},
  booktitle = 	 icdcs,
  year = 	 1996,
  organization = {IEEE Computer Society},
  address =	 {Hong Kong},
  month =	 may,
  pages =	 {402--410}
}

@InProceedings{gc:mv:rep:1406,
  author =       {Paulo Ferreira and Marc Shapiro},
  title =        {Modelling a Distributed Cached Store for Garbage Collection},
  booktitle =    {12th Euro.\ Conf.\ on Object-Oriented Prog.\ (ECOOP)},
  year =         1998,
  address =      {Brussels (Belgium)},
  month =        jul,
  note =         {\url{http://www-sor.inria.fr/publi/MDCSGC_ecoop98.html}}
}