Posted: October 9, 2015 in Research
Tags: , , , , ,

Authors: David Mulder, Curtis Welborn


This paper describes the implementation of a garbage collector as an undergraduate research project. The garbage collector is a continuation of a project where an Assembler, Virtual Machine and Compiler were implemented as a capstone project. The project required modifying the compiler to allocate memory compatible with a mark and sweep algorithm, and adding the mark and sweep algorithm to the virtual machine. Computer Science faculty should take note that this was all completed by an undergraduate student within a year’s time, and that such challenges can reasonably be accomplished by undergraduate seniors.


Challenges of the nature described in this paper are generally reserved for graduate students, and are considered outside the grasp of undergraduates. Computer Science faculty and students alike will be interested to note that the preceding project was completed entirely by an undergraduate senior. It is also interesting to note that the project was completed by an average student of little academic achievement, and that a Compiler, Assembler and Multi-Processed Virtual Machine with Garbage Collection were written within a year’s time.

As part of an undergraduate capstone, an Assembler, Virtual Machine and Compiler were implemented. The two-pass Compiler performs Lexical and Syntax analysis in the first pass, and Semantic analysis and Intermediate code generation in the second pass. Using Intermediate code as input, the Compiler then generates target code (assembly) that can be fed to the Assembler to generate byte-code. The byte-code can then be loaded into the Virtual Machine for execution [1]. Through independent study, a garbage collector was added to the virtual machine, which included extensive changes to the compiler.

The compiler had to be modified to place by-reference parameters onto the run-time stack first. An additional parameter is also added that counts the number of by-reference parameters. The counter is needed by the Mark and Sweep algorithm to determine the location of the by-reference parameters within an Activation Record.

To support the mark and sweep garbage collection algorithm, the virtual machine had to be modified to allocate memory from a list of available blocks. The mark and sweep algorithm is triggered when a call to allocate memory detects no free blocks. In the mark phase of the algorithm, the run-time stack is traversed searching for points that reference blocks allocated on the heap. Any block of memory reachable from the run-time stack must be marked as in use. During the sweep phase of the algorithm, the heap is searched looking for any blocks not marked as in use during the mark phase.
Screenshot from 2015-10-09 13:18:55


The compiler was originally written to pass parameters to a function call via an activation record in the order they were written in the source language (a language called KXI, which is similar to java). It was necessary for the compiler to segregate between by-reference and by-value parameters. The mark phase of the algorithm must know the location of every by-reference parameter within a function calls’ activation record. See the ordering of variables in the current Activation Record of Figure 1. Because the variables are segregated, references are easily located based on offsets. For example, the first reference is located by an offset of 4*sizeof(int) from the base of the activation record (the return address, previous activation record pointer and reference counters are all integers), and the second reference is offset 5*sizeof(int) from the base.

The mark phase of the algorithm needed a special field inserted in each activation record that counts the number of by-reference parameters. This field was added in the activation record in such a way that the mark phase could iterate over each by-reference parameter and set the mark bit in the corresponding block for each object allocated on the heap. The field is referred to as the Reference Counter in Figure 1. The reference counter in this activation record tells us that there are 2 references. If we decremented the reference counter to 1, for example, the second reference on the stack would be interpreted as an integer.


In order to make space allocation more efficient, the heap was separated into large and small blocks. Bit vectors were used to keep track of which blocks are allocated on the heap.

An instruction was added to the virtual machine for allocating memory. Prior to the instruction, memory allocation consisted of just moving a pointer within the heap. The new allocation instruction calls the mark and sweep algorithm. If there is space available on the heap, the instruction returns a pointer to that block and marks the block as unavailable within one of the vectors that tracks all blocks in the heap.

If no available space is found, garbage collection is started. The algorithm must calculate the location of the activation record for the current function call then calculates the offset to the by-reference counter field in the activation record. Now having the number of pass by-references parameters in the current activation record, the algorithm can calculate the offset to each allocated block on the heap and set its mark bit to in use.

The algorithm must recursively follow references allocated inside of each block. This was achieved by organizing objects within a block in a similar manner to how function calls are organized in an activation record. In this way, lists, trees and even recursive data structures allocated on the heap can all be traversed and marked. In Figure 1, the mark phase will follow all references inside of Small Block A, so Small Block B is also marked.

Once all objects (blocks) and descendant objects have been marked, the algorithm calculates the location of the previous activation record. The same process of following references and marking objects proceeds for each activation record until all function calls on the run-time stack have been searched.

The sweep phase of the algorithm now iterates over the entire heap, checking the mark bit. If the mark bit is set (the block is in use), it clears the bit and moves on. This means that the block has a live reference to it which originated in an activation record that is currently on the run-time stack. Blocks A, B and D in Figure 1 have references pointing to them. These blocks will be un-marked and will remain allocated.

If the mark bit is not set, the algorithm clears the relevant marker in the vector of available blocks, freeing the block for reuse (See Small Block C in Figure 1) [2]. This allocated block will be freed during the sweep phase because it has no references pointing to it on the run-time stack.


This method of garbage collection is effective, but did prove to be inefficient. Because the algorithm isn’t activated until there is no remaining free space, the algorithm isn’t suitable for real time applications. The algorithm could be modified to operate incrementally, but it would still cause an occasional lag. These are known problems of garbage collection.

The greatest achievement of this project was the recognition of what can be accomplished by undergraduate seniors. Computer Science faculty should recognize that computing projects of this caliber can reasonably be expected in an undergraduate senior project course.


The primary author has started work on an hp-ux pa-risc virtual machine. The first obstacle will be setting up the correct environment, based on descriptions in the pa-risc specifications. The second will be translating the pseudo code in the specification into C. A compiler/translator will be written to automatically convert the specification pseudo code into C.

A significant part of the project will be writing the loader, since it will need to include things such as run time linking. Ideally, the virtual machine will run at boot time and will include a boot loader. This would allow pa-risc software to run on virtually any hardware.


[1] Mulder, D., Welborn, C., Lessons in converting from python to c++, Journal of Computing Sciences in Colleges, 29(2), 49-57, December 2013, http://dl.acm.org/citation.cfm?id=253542
[2] Jones, R., Lins, R. D., Garbage collection: Algorithms for automatic dynamic memory management, West Sussex, England

© CCSC, (2014). This is the author’s version of the work. It is posted here by permission of CCSC for your personal use. Not for redistribution. The definitive version was published in The Journal of Computing Sciences in Colleges, {volume 30, number 2, December 2014}, http://dl.acm.org/.


Comments are closed.