|
Abstract: Garbage
collection (GC) is the most popular method in list processing systems such as
Lisp to reclaim discarded cells. GC periodically suspends the execution
of the main list processing program. In order to avoid this problem,
real-time GC has been proposed, which runs in parallel with the main program
so that the time for each list processing primitive is bounded by some small
constant.
The snapshot GC, which is one of the most popular real-time GC methods, as to
mark all cells directly pointed to from the root area at the beginning of a
GC process. The suspension of the main program by this root
marking cannot be ignored when the root area is large.
We propose ``return barrier" in order to divide the process of root marking
into small chunks and to reduce the suspension time of the main program.
The root area on the stack is marked frame by frame each time
a new cell is required. When a function returns, the garbage collector checks
if cells pointed to from the frame of the caller function have been already
marked, and marks them if not. After marking all cells directly pointed to
from the root area, other cells are marked as in the original snapshot GC.
We implemented the snapshot GC equipped with the return barrier in several language
processors including a Common Lisp system, a multi-threaded Lisp system for
robot control, a Scheme system with conservative GC, and a JVM.
|