Homework # 8
due Tuesday, March 29th, 3:30PM

In this Homework, you will implement mark-sweep garbage collection in Squeak. You will also implement first-fit allocation, with help from code developed in lecture.

First-Fit Allocation

Allocation (in the presence of a garbage collector) works as follows:

  1. Start with the first block in the free-list.
  2. If there are no more blocks (we're at a null pointer), skip ahead to step 6.
  3. If the current block is not big enough, go back to step 2 with the next block.
  4. If the block is more than 1 word bigger than what is requested, shave the requested number of words (plus one) from the end of the current block, and return that.
  5. Otherwise, unlink the whole block from the free list and return it.
  6. Perform garbage collection (which resets the free-list).
  7. Repeat the process from step 1, except if we run out of blocks (step 2), it should return null (not nil!) instead of doing garbage collection again.

Garbage Collection

Mark-sweep garbage collection works by marking all nodes accessible from a distinguished ``root'' pointer and then sweeping together unmarked words into blocks of a new free-list:

  1. Clear all marks.
  2. Mark starting at the root: 
    
mark(p) 

    
if p is a non-null pointer then

    
if p is NOT already marked then

    
mark all words of the block

    
call mark on the contents of every word in the block

    
endif

    
endif
  3. Set the free-list to null.
  4. Find all consecutive unmarked groups of words (of at least two words) and add them to the free list.

What You Need to Do

Start with the skeleton file for the homework, and implement the class ManagedHeap. It should accept the following messages (and other internal ones):

root
Return the current value of the root pointer (initially null).
root:$\,p$
Set the root pointer to $p$.
allocate:$\,n$
First-fit allocation of a block of $n$ words.
at:$\,p$
Return the contents of the location pointed to by $p$.
at:$\,p$ put:$\,v$
Change the contents of the location pointed to by $p$ to be $v$.
We have provided a few tests for you. You may need more.

Submitting Your Work

Leave your code in the directory homework8 in your AFS folder:

About this document


John Tang Boyland 2011-03-15