Assignment 8, due Apr. 9

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 these definitons for the structure of a free block and the the freelist declared in C:

   typedef struct freeblock {
           freeblock * next;
   } freeblock;
   freeblock * freelist = NULL;
   

   Assume we are using this to implement a heap manager where the block size is fixed at BLOCKSIZE with the C standard malloc() and free() user interface. You can assume that BLOCKSIZE is a multiple of sizeof(void*).

   a) Write the malloc() and free() routines that go with these declarations, assuming that initialization is done elsewhere. (0.5 points)

   b) Write an initializer for the free list that uses sbrk() to allocate NBLOCKS*BLOCKSIZE bytes of memory and puts NBLOCKS blocks onto the initial freelist. (0.5 points)

   c) Suppose you wanted to make the first call to malloc() automatically call your initializer. How could you do this using the above interface? (0.5 points)

2. Background: Consider implementing malloc() and free() using the buddy system. Recall that sizeof(void*) is the size of one pointer, in bytes, and recall that free() assumes that it can determine the size of the block to be freed from some attribute of the block itself, as the weak type checking of the C language does not provide any way for the size to be inferred from the context of the call to free().

   Assume that the heap manager guarantees that all pointers returned to users by malloc() will be aligned on a word boundary in memory, where the word size for this purpose is sizeof(void*).

   a) What is the minimum block size for this system. Give your answer from two different perspectives: The perspective of the buddy-system storage allocator and the perspective of the user calling malloc(). Note that the two answers will differ because of considerations introduced in the background section above. (0.5 points)

3. Background: Consider implementing a boundary-tag based storage allocator, where the structure of a boundary tag is:

   typedef struct boundary {
           boundary * next;
           boundary * prev;
   } boundary;
   

   a) If p is a pointer to a boundary tag, give a C expression that evaluates to the useful size of the block p points to -- that is, the size available for allocation to the user. (0.5 points)

   b) Obviously, the boundary tag must also include one bit to encode whether the block is allocated or free. Explain why and how this bit can be (with care) encoded in one of the pointers.r (Hint: On machines with byte addressing, sizeof(void*) is guaranteed to be greater than 1.) (0.5 points)