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!
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)
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)
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)