Go backward to Thread Scheduling Go up to Implementation

Garbage Collection

The heap is partitioned into clusters each of which is itself partitioned into an equal number of blocks of equal size. These blocks are the units of parallelism in the sweeping phase of the garbage collector (see below). Initially the heap consists of only one cluster. If after garbage collection too little heap space is free or the free heap space is too fragmented to satisfy a memory request, a new cluster is allocated unless the shared memory bound of the program is reached.

Each process has an associated list of free heap space. When a thread executed by the process allocates heap space, this space is taken from the local list (which can be accessed without synchronization with other processes). When the process runs out of free heap space, it requests a new free list from the global free list (which must be protected by a locking mechanism from simultaneous access by multiple processes). If also the global free list runs out of space, garbage collection is triggered.

Garbage collection is performed by a conventional mark and sweep scheme where both phases are parallelized. In the first phase, all heap entities reachable from the root set of pointers are marked. In the second phase, all unmarked heap entities are reclaimed into the global free list. By default, the root set consists just of the pointer to the main thread of the RT++ program. If during the marking phase a not yet marked active thread is encountered, its stack is put into a pool; all processes in parallel take stacks from this pool and scan the contained heap references. Likewise, in the sweep phase all processes in parallel collect free space from the individual heap blocks(5). Threads are treated like all other heap objects; any thread not reachable by the root set is automatically reclaimed (together with its stack, if the thread has been already activated).  

The marking phase of the garbage collector is based on the C++ type system such that he RT++ garbage collector "knows" the location and type of each heap reference and can thus safely mark all reachable heap objects:

When a C++ variable is declared within some function of an RT++ program, this variable is pushed on the stack of the current thread. If this variable is declared using an RT++ type constructor, the address and type of this variable are registered by pushing the corresponding information on another stack. This "shadow" stack is allocated at the opposite end of the space reserved for the actual thread stack and grows into the opposite direction.

The registered information is the address of the scan function corresponding to the type of the allocated variable. This function recursively scans and marks all heap blocks reachable via the variable by calling the scan functions of the corresponding subtypes. All scan functions are declared via Ref declarations using the C++ mechanism of static members of template classes. Alternatively Atom declarations register a null pointer for the scan function of a non-reference type (thus avoiding the overhead of the call of an empty scan function). The purpose of the init function also registered by Ref/Atom declarations is to set the reference(s) contained in a variable initially to null. Thus at any time all heap references in an RT++ program have a well-defined state.