ACM Transactions on Programming Languages and Systems · 2006 · 74 citations · 44 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureOperating SystemsParallel ComputingGarbage CollectionSynchronization PrimitivesVirtual MemoryCompare-and-swapGarbage Collection AlgorithmsGarbage Collection OverheadGarbage Collection Overhead AnalysisMultiprocessor SynchronizationOverhead AnalysisReference CountingSynchronization Overhead Reduction
Reference-counting is traditionally considered unsuitable for multiprocessor systems. According to conventional wisdom, the update of reference slots and reference-counts requires atomic or synchronized operations. In this work we demonstrate this is not the case by presenting a novel reference-counting algorithm suitable for a multiprocessor system that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). A second novelty of this algorithm is that it allows eliminating a large fraction of the reference-count updates, thus, drastically reducing the reference-counting traditional overhead. This article includes a full proof of the algorithm showing that it is safe (does not reclaim live objects) and live (eventually reclaims all unreachable objects).We have implemented our algorithm on Sun Microsystems' Java Virtual Machine (JVM) 1.2.2 and ran it on a four-way IBM Netfinity 8500R server with 550-MHz Intel Pentium III Xeon and 2 GB of physical memory. Our results show that the algorithm has an extremely low latency and throughput that is comparable to the stop-the-world mark and sweep algorithm used in the original JVM.
44
List processing in real time on a serial computer
Henry G. Baker · Communications of the ACM · 1978 · 592 citations · Full text
Edsger W. Dijkstra, Leslie Lamport, Alain J. Martin et al. · Communications of the ACM · 1978 · 559 citations · Full text
A method for overlapping and erasure of lists
George E. Collins · Communications of the ACM · 1960 · 314 citations · Full text