User Tools

Site Tools


cs330_f2016:lab14

Objective:

To better understand how basic garbage collection algorithms work by simulating their operation by hand.


Preparation:

Before beginning this assignment, you should download (to Excel) or make a copy (Google sheets) of the assignment spreadsheet.


Deliverable:

You must submit through LearningSuite an Excel .xlsx file that contains your results:

  • If you download the spreadsheet and edit it using your own copy of Excel, just upload that file.
  • If you use Google sheets to edit a copy of the spreadsheet, download that as an Excel file once you're done, and upload that.

Description:

Unlike your earlier assignments, this one doesn't require you to write any code. Instead, you will simulate the operation of the mark-and-sweep and stop-and-copy algorithms by hand.

An assignment spreadsheet is provided that shows the state of a very small (60 addresses) heap prior to garbage collection. An additional column shows the interpretation of each of the addresses according to the tables given at the bottom of the page, but this is for information only and is not actually stored anywhere in the heap. At the top of the page is the root set, showing two identifiers that are associated with objects shown at the indicated addresses.

Your results go in the greyed areas of the spreadsheet.

Mark and Sweep

For the mark-and-sweep part of the assignment, you should fill in the state of the heap after the marking phase and again after the sweep phase.

During the marking phase, start with the root set and traverse out in a recursive depth-first fashion marking each block that can be eventually reached.

During the sweep phase, turn all unmarked blocks into free blocks by labeling them as such, storing the length of the free block, and storing a pointer to the next free block. All newly freed blocks should be added at the head of the free list. You must have a free list stored within the heap itself!

Stop and Copy

For the stop-and-copy part of the assignment, you are given the initial fromspace, which is identical to the original heap for the mark-and-sweep part. However, the interpretation is slightly different: for mark-and-sweep, you have to identify blocks as free and maintain a free-block list. For stop-and-copy, there are no free blocks or a list of such. Instead, all memory above the single free pointer is unused and can be allocated.

During collection, the stop-and-copy method copies live objects from the fromspace to the tospace. (You can just do this manually by copying blocks from the fromspace and pasting them to the tospace.) You must use Cheney's algorithm as discussed in class, which means there is a set order in which the live objects must be copied to the tospace.

First copy the objects in the root set over to the tospace, then begin scanning these objects. As you encounter a pointer, you copy that object to the tospace and make sure to do both of the following:

  1. update the pointer you just scanned, and
  2. leave a forwarding address in the fromspace should you revisit that object again.

Continue this process until you've scanned everything that's been copied over and the scan pointer catches up with the free pointer.


Notes:

  1. Address 0 is intentionally not used and a reference with value = 0 should be taken as a NULL pointer.
  2. Use the “Interpretation” column for your own notes, but all necessary information must be in the heap contents, not this column!

Hints:

Since both methods should result in the same set of live objects, try comparing which blocks still remain after each approach. The order in which they appear in memory will be different, but the set of live objects should be the same.

cs330_f2016/lab14.txt · Last modified: 2016/11/15 14:32 by morse