NONINTRUSIVE CLONING GARBAGE COLLECTION WITH STOCK OPERATING SYSTEM SUPPORT

It is well accepted that automatic garbage collection simplifies progr amming, promotes modularity, and reduces development effort. However i t is commonly believed that these advantages do not counteract the per ceived price: excessive overheads, possible long pause times while gar bage collections occur, and the need to modify existing code. Even tho ugh there are publically available garbage collector implementations t hat can be used in existing programs, they do not guarantee short paus es, and some modification of the application using them is still requi red. In this paper we describe a snapshot-at-beginning concurrent garb age collector algorithm and its implementation. This algorithm guarant ees short pauses, and can be easily implemented on stock UNIX-like ope rating systems. Our results show that our collector performs comparabl e to other garbage collection implementations on uniprocessor machines and outperforms similar collectors on multiprocessor machines. We als o show our collector to be competitive in performance with explicit de allocation. Our collector has the added advantage of being non-intrusi ve. Using a dynamic linking technique and effective root set inferenci ng, we have been able to successfully run our collector even in commer cial programs where only the binary executable and no source code is a vailable. In this paper we describe our algorithm, its implementation, and provide both an algorithmic and a performance comparison between our collector and other similar garbage collectors. (C) 1997 by John W hey gr Sons, Ltd.