The Treadmill: Real-Time Garbage Collection Without Motion Sickness
📜 Abstract
A simple real-time garbage collection algorithm is presented which does not copy, thereby avoiding some of the problems caused by the asynchronous motion of objects. This in-place "treadmill" garbage collection scheme has approximately the same complexity as other non-moving garbage collectors, thus making it usable in a high-level language implementation where some pointers cannot be traced. The treadmill is currently being used in a Lisp system built in Ada.
✨ Summary
The paper presents the Treadmill, an incremental real-time garbage collector that avoids physically moving objects. It combines tricolor marking with circular doubly linked lists whose contiguous regions represent free, grey, black, and newly allocated objects. Allocation and collector progress are advanced by moving list-boundary pointers, while a read barrier ensures that the mutator does not access unmarked objects. The design preserves bounded-time collection operations and is suitable for systems in which some pointers cannot be traced, including conservative environments. Its principal limitation is storage management for differently sized immobile objects: free-list search and fragmentation can weaken worst-case allocation guarantees. The paper reports use in a Lisp system implemented in Ada. (plover.com)
Subsequent research treated the Treadmill as a standard non-copying real-time collection technique. Later work developed memory-efficient variants based on the Treadmill and deployed such a collector in the SPIN operating-system kernel and Modula-3 programs, while also addressing fragmentation and space utilization. (citeseerx.ist.psu.edu) The algorithm is also documented in modern garbage-collection surveys and textbooks as a representative real-time, non-moving collector, indicating continuing influence on research, teaching, and collector design discussions. (doi.org) There is evidence of later implementations and engineering discussions referring to the technique, but the sources reviewed do not establish broad commercial-industry adoption of Baker’s original implementation.