[gclist] Re: gclist-digest V3 #117
Thu, 19 Oct 2000 16:01:43 +0100 (BST)
|| Date: Wed, 18 Oct 2000 16:59:46 -0400
|| From: Andrew Shi-hwa Chen <firstname.lastname@example.org>
|| Subject: [gclist] Aging based garbage collection?
|| I remember seeing a while ago, on a web-site that I now can't find, a
|| description of a GC algorithm as follows:
|| 1) objects have an associated time-stamp
|| 2) a thread continuously does DFS from the root and updates the
|| 3) all objects are in a priority queue based on their age
|| 4) whenever an allocation request occurs, it can lazily sweep the
|| objects away - that is, those they are so old that it is impossible
|| they could be reachable because if they were, they would have been
|| updated by that thread that updates the time-stamps.
You are describing Hughes' algorithm:
author = "John Hughes",
title = "A Distributed Garbage Collection Algorithm",
editor = "Jouannaud, Jean-Pierre",
number = 201,
series = "Lecture Notes in Computer Science",
pages = "256--272",
booktitle = "Functional Languages and Computer Architectures",
year = 1985,
publisher = "Springer-Verlag",
address = "Nancy (France)",
month = sep
It is a beautifully elegant distributed algorithm. It relies on
a standard mark-and-sweep (no timestamps) at each site.
It sounds like you want to use it as a centralised algorithm. I don't
see the benefit, since you have to do the mark-and-sweep work anyway.
You could do lazy sweeping with just the single mark bit.