Assignment 10, due Apr. 10

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

1. Background:

   Consider the problem of writing a heap manager, equivalent to that behind the C malloc() and free() routines. On some machines, guaranteeing that all blocks in the heap begin on a word boundary can significantly improve performance.

   Note that in c, sizeof(int), sizeof(void *) and sizeof(char) can be used to find out the sizes of these data types on whatever machine you are using. On a machine where there is a significant performance advantage to using aligned data, you can assume that statically allocated arrays of int or void * will be aligned on word boundaries.

   a) If heap is a statically allocated array of char, how can you check to see whether heap[i] is aligned appropriately for storing the first byte of a pointer on a machine where such alignment matters? (0.5 points)

   b) If you know that your heap is likely to be used on a machine where alignment matters, and if you know that many of the heap management data structures will involve pointers back and forth in the heap, should you declare the heap so that all of your pointers will be aligned without needing to do any checking of the type discussed above. (0.5 points)

2. Background: In a boundary tag implementation of the heap, each block in the heap needs a one-bit field indicating whether it is currently allocated or free. If garbage collectio is used, there are additional one-bit fields needed. It seems a pity to allocate an extra byte or word for such information in each boundary tag, so we are looking for places to sneak these bits into some unused bits of an existing fields of the heap data structure. Assume that all blocks in your heap data structures are aligned on word boundaries.

   a) What bits of what fields in the boundary tag are available to store one-bit auxiliary flags? (0.5 points)

   b) Given that p points to a boundary tag, and p->f is a field where one bit of auxiliary data can be stored, give code to set the auxiliary bit, reset the auxiliary bit, and test the auxiliary bit. (0.5 points)

3. Background: Consider the choice between full-scale garbage collection, on the one hand, and maintaining reference counts for automatic deallocation on the other hand.

   a) Under what circumstances will reference counts fail to allow automatic reclamation of storage where garbage collection will succede. (The answer, curiously, is related to the fact that the Unix/Linux file system uses reference counts to determine when regular files can be deallocated, but directories must be explicitly deleted using rmdir.) (0.5 points)

   b) Describe the circumstances under which an application that uses garbage collection could still suffer from a memory leak. Your description should include a discussion of example data structures that could lead to this problem. (0.5 points)