Run-Time Systems

Mostly GC-related stuff.
(27.10.95) Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin ( (Papers on memory allocators, garbage collection, memory hierarchies, persistence and Scheme interpreters and compilers)
(26.10.95) Incremental Mature Garbage Collection Using the Train Algorithm, used for an implementation of the BETA language. Advanced non-disruptive generation-based collector. The algorithm is by Hudson & Moss (Richard L. Hudson and J. Eliot B. Moss: Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, September 1992, pp. 388-403)
I wish Henry Baker would use a different provider; netcom's ftp server is about the least reachable site I know. Anyway, Baker seems to have HTMLified some of his classic papers, chief amongst them the very first Real Time Garbage Collector, which was the forefather of today's generational GCs. (Also, I implemented a mark-and-sweep variant of this collector as part of my Studienarbeit. Those were the times ;-)
The Portable Common Runtime Approach to Interoperability: PCR offers four interrelated facilities: storage management (including universal garbage collection), symbol binding (including static and dynamic linking and loading), threads (lightweight processes), and low-level I/O (including network sockets).


>Also, I know that Chez Scheme, which is available as a commercial product,
>uses some sort of spiffy cutting-edge all-singing all-dancing GC algorithm,
>but I don't know the details.
Most of the features are described in an Indiana University tech report available via ftp:

Details about collector support for weak pointers and finalization using "guardians" can be found in the proceedings of the 1993 PLDI conference. The paper is also available via ftp:

Carl Bruggeman

Those interested in reliable garbage collection for hard real-time applications may be interested in:

K. Nilsen. Reliable Real-Time Garbage Collection of C++. Computing Systems. vol. 7, no. 4, (Fall 1994).

Though the title mentions C++, the techniques can be generalized to support other languages. The paper discusses "accurate" (as opposed to conservative) garbage collection techniques, and describes the performance constraints that characterize "real-time performance".

To summarize, our garbage collection technique supports worst-case memory allocation delays of 500 microseconds at predictable times and worst-case memory access delays of 2 microseconds. The amortized allocation and memory access costs are nearly indistinguishable from more traditional C++ techniques for memory management. We rely on a "small" amount of hardware support coupled with the memory system to achieve this performance. The general design of the memory subsystem is portable between CPU architectures. A FPGA prototype is currently under construction. Eventually, we intend to package all of the special circuitry on a single chip, the cost of which remains to be determined.

Additional reports are available by anonymous ftp from

Kelvin Nilsen/Dept. of Computer Science/Iowa State University/Ames, IA 50011
(515) 294-2259 uunet!!kelvin

(24.03.95) /pub/garbage is the place. A survey of GC, generation GC, distributed GC, all kinds of stuff.

(07.07.95) SFIO library
This page is part of the Trash Heap.