[gclist] Read-Write locks (from gclist-digest V2 #135)

[Eliot Moss]

If your aim is performance, then doing ANY kind of locking on each use of a
reference seems to me to be a bad idea. Maurice Herlihy and I outlined a
concurrent, non-locking, collector in

Maurice P. Herlihy and J. Eliot B. Moss, ``Lock-Free Garbage Collection for
Multiprocessors'', IEEE Transactions on Parallel and Distributed Systems},
Volume 3, Number 3, May 1992, pp. 304-311.

You might find that interesting, but it relies on hardware primitives for
atomic update of at least two completely distinct words in memory. Only a few
processor have that capability. We propose a more RISC-like approach to
building the necessary hardware in

Maurice P. Herlihy and J. Eliot B. Moss, ``Transactional Memory: Architectural
Support for Lock-Free Data Structures,'' International Symposium on Computer
Architecture}, San Diego, CA, May 1993, pp. 289-300.

But again, that's probably not what you want. Here are a couple of approaches
I would consider:

1) You said "incremental", not "concurrent". You can gain incrementality by
doing gc work at each allocation, as in the original Baker proposal. (See the
Jones and Lins book on gc for good coverage of past schemes and developments.)

2) You can also avoid a read barrier by going to a Nettles and O'Toole style
collector, for which I offer these citations:

@InProceedings{gc:1094,
author = 	 "Nettles, S. and O'Toole, J. and Pierce, D. and
Haines, N.",
title = 	 "Replication-Based Incremental Copying Collection",
number = 	 637,
series = 	 "Lecture Notes in Computer Science",
pages = 	 "357--364",
booktitle = iwmm,
year = 	 1992,
publisher = "Springer-Verlag",
address = 	 "Saint-Malo (France)",
month = 	 sep
}

@InProceedings{Nettles:1993:RRG,
author =       "S. Nettles and J. O'Toole",
title =        "Real-time replication garbage collection",
crossref =     "ACM:1993:PAS",
journal =      j-SIGPLAN,
volume =       "28",
number =       "6",
pages =        "217--226",
month =        jun,
year =         "1993",
ISSN =         "0362-1340",
bibdate =      "Thu Dec 14 18:49:37 MST 1995",
abstract =     "A copying garbage collector has been implemented that
permits continuous unimpeded mutator access to the
original objects during copying. The garbage collector
incrementally replicates all accessible objects and
uses a mutation log to bring the replicas up-to-date
with changes made by the mutator. An experimental
implementation demonstrates that the costs of using the
algorithm are small and that bounded pause times of 50
milliseconds can be readily achieved. (20 Refs.)",
acknowledgement = ack-nhfb,
affiliation =  "Sch. of Comput. Sci., Carnegie Mellon Univ.,
Pittsburgh, PA, USA",
classification = "C6120 (File organisation); C6150J (Operating
systems); C6150C (Compilers, interpreters and other
processors)",
CODEN =        "SINOD",
confdate =     "23-25 June 1993",
conflocation = "Albuquerque, NM, USA",
confsponsor =  "ACM",
keywords =     "Real-time replication; Copying garbage collector;
Continuous unimpeded mutator access; Accessible
objects; Mutation log; Experimental implementation;
Bounded pause times; 50 Ms",
language =     "English",
numericalindex = "Time 5.0E-02 s",
pubcountry =   "USA",
thesaurus =    "Real-time systems; Storage allocation; Storage
management",
}

In hopes that these comments and pointers will help you in your quest ....
==============================================================================
J. Eliot B. Moss, Associate Professor      http://www.cs.umass.edu/~moss   www
Computer Science Department, LGRC          +1-413-545-4206               voice
University of Massachusetts, Box 34610     +1-413-545-1249                 fax
Amherst MA  01003-4610  USA                moss@cs.umass.edu             email
==============================================================================