Assignment 10, due Apr. 6

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: The code distributed for MP5 includes this bit of code, used to determine if a newly allocated block is big enough to split:

   /* we found a big enough block */
   if (GETSIZE( p ) > (size + TAGSIZE)) {
           /* the block is big enough to split */
           void * new = (void *)( (intptr_t)p + size + TAGSIZE );
   

   Here, p points to the block we found that is big enough to allocate, and if p is large enough to split, new points to the block that will be split off from it.

   a) Does this code ever produce any internal fragmentation? If so, when, and what can you say about the range of internal fragment sizes? (0.4 points)

   b) Why is TAGSIZE part of the consideration when a decision is made to split a block? (0.3 points)

   c) What is the minimum size of the block pointed to by new? (0.3 points)

2. Background: Look at the User-level thread manager. Specifically, look at Part II of threads.c.

   A question: Why can't thread_exit() simply call free(current) instead of doing elaborate things involving mem_to_free and longjmp in order to transfer control to the code go_free_it is linked to. (1 point)

3. Background: In the discussion of the mark-sweep algorithm on Mar. 30, the discussion used historical LISP object structure. Each lisp object had the following form, conceptually:

   • Each item has mark bit used only for the mark-sweep algorithm.

   • Each item has a tag field describing the rest of the object:

     • tag = pointers: The object contains two pointers to other objects named CAR and CDR.

     • tag = atom: The object contains regular data. There may be multiple atomic types, such as character, integer and float, each with its ownn atom value.

   All objects were exactly the same size and the heap manager could address the heap as an array of objects as easily as it could build linked lists of objects (typically linked through their CDR fields). If you want to build, in LISP, the equivalent of an object in a Java program or a struct in a C program, you end up having to build it as a linked list of fields, where each list element has its CAR point to the field value and its CDR point to the next element.

   Now consider the problem of building a garbage collector for a strongly typed language like Java, Simula-67, Pascal or Ada, where objects are represented by variable-sized records where each record contains a variety of fields, some of which are pointers. In all of these languages, you can assume that all objects of any particular type (or class) identically the same structure.

   a) What additional data does the garbage collector need to know about each object and about each word of each object? (0.4 points)

   b) Suggest an appropriate representation for this data in terms of the actual representation of objects in memory at run-time. (0.3 points)

   c) Now, what about garbage collectors for C. What is it about C that makes the problem more difficult? (You'll find ample examples of this problem hidden in the code for the heap manager you're working on for MP5.) (0.3 points)