Description
Introduction: This assignment is about the implementation of dynamic memory allocation and garbage
collection. Ideally, it would be nice to study these topics in the context of a real-world, practical implementation. However, even a fairly simple copying collector implementation for the AsmGen compiler requires
attention to more details than we have time for in this assignment, so we will make do instead with a less
realistic, but simpler implementation that, nevertheless, still illustrates some of the key ideas.
To start this assignment, you should download the file hw4.zip from the class web page. This file contains
the skeleton of an implementation for a two space, copying garbage collector that you will work with in
the rest of this assignment. The most important file is called Heap.java, and it contains the code for
a corresponding class called Heap. Roughly speaking, the Heap class provides the following interface,
details of which are explained in the following text:
class Heap {
public static Heap make(int size);
int alloc(int len);
public void garbageCollect();
public int load(int obj, int offs);
public void store(int obj, int offs, int val);
public void dump();
int freeSpace();
}
Some key points:
• A heap is used to store a set of objects, each of which spans one or more words. A new heap with the
capacity to store a total of S words can be created by calling the method Heap.make(S). The first
word in each object is a length, which specifies how many fields that object has. These fields are stored
in consecutive words immediately after the initial word. So an object that has len fields will span
(len+1) consecutive words in the heap.
• We can allocate heap space for a new object with len fields by calling the method alloc(len),
which also ensures that all of the fields in the new object are initialized to zero.
• If there is not enough room in the heap for an object with len fields, then alloc(len) will call the
garbageCollect() method in an attempt to recover and reclaim any portions of the heap that are
no longer in use. The garbageCollect() method can also be called directly to force a garbage
collection when the heap is not full. In fact, the version of this method in Heap.java simply displays
an error message that garbage collection is not supported and then terminates the program.
• The value of the ith field in an object at address obj can be read by calling load(obj, i). The
value of the ith field in an object at address obj can be set to val by calling store(obj, i, val).
These methods perform some limited checking on the validity of the obj and i arguments, and will
abort the program if the values appear to be incorrect.
• The values that are stored in heap objects are all integers, but negative integers in the range -S, . . . ,
-1 are interpreted specially as pointers to the individual locations (assuming a heap with S words).
Positive numbers are not interpreted in any special way.
• The dump() method can be used to print a description for each of the objects in the current heap; the
freeSpace() method can be used to determine the number of free (unused) words in the current
heap.
1
The following program shows how (most of) these operations can be used in simple example program (the
source code for this is included in hw4.zip as TestHeap1.java):
class TestHeap1 {
static final int S = 100;
public static void main(String[] args) {
Heap h = Heap.make(S);
int root = h.alloc(5);
h.store(root, 1, h.alloc(3));
h.store(root, 2, h.alloc(2));
h.dump();
System.out.println(“Free space remaining = ”
+ h.freeSpace());
}
}
The output from this program is as follows:
Object at address -100, length=5, data=[-94, -90, 0, 0, 0]
Object at address -94, length=3, data=[0, 0, 0]
Object at address -90, length=2, data=[0, 0]
Heap allocation pointer: 13
Free space remaining = 87
Before proceeding, be sure that you understand this output, checking with the source in Heap.java where
necessary for more details about the implementation of the heap operators. (You may also find it useful to
draw a diagram illustrating the structure of the heap that is constructed in the program above.)
Question 1: Consider the following program (source code in TestHeap2.java):
class TestHeap2 {
static final int S = 100;
static final int N = 6;
public static void main(String[] args) {
Heap h = Heap.make(S);
for (int i=0; iRelated products
