| TR#: | CS0967 |
| Class: | CS |
| Title: | A Scalable Reference Counting Garbage Collector |
| Authors: | Yossi Levanoni and Erez Petrank |
| CS0967.pdf | |
| Abstract: | We study concurrent garbage collection via reference counting. While tracing variants of garbage collection have been well studied with respect to concurrency, the study of reference counting has been somewhat behind. The straightforward concurrent version of reference counting is not at all scalable. Furthermore, a more advanced study by DeTreville yielded an algorithm which acquires a single lock per update of a pointer, thus, executing all updates sequentially and hindering the scalability of the algorithm. In this paper we propose a new concurrent reference counting algorithm with several desired properties. First, the algorithm employs extremely fine synchronization. In particular, updates of pointers and creation of objects require no synchronization overhead whatsoever (even not a compare-and-swap type of operation). Furthermore, the algorithm is non-disruptive: the program threads are never stopped simultaneously to cooperate with the collector. Instead, each program thread cooperates with the collector at its own pace, infrequently, and for very short periods. Thus, the program can run with (almost) no concurrency overhead imposed by the collection. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1999/CS/CS0967), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1999
To the main CS technical reports page