Assignment 9, due Nov. 2

Part of the homework for 22C:112, Fall 2012
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

On every assignment, write your name legibly as it appears on your University ID and on the class list! 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 classic interface to a buddy system storage manager uses the following interface:
            void * buddyallocate( int i );
            void buddydeallocate( void * b, int i );
    

    These request a block of size s = 2i from the heap and return a block of that size to the heap.

    The classic interface to the heap manager required by C uses the following interface:

            void * malloc( int s );
            void free( void * b );
    

    There are two glaring incompatabilities between these:

    a) Give C code to solve the first problem. (This is code to compute i as a function of s. It can be done with one line of stylistically reasonable C code, assuming all variables are alread declared.) (0.3 points)

    b) Give C code to solve the second problem. (This will involve a fragment of code from the malloc() routine that communicates with a fragement of code from the free() routine, probably using space in the block of memory allocated by buddyallocate(). (0.3 points)

    c) Give the complete code for malloc() and free() incorporating your answers to parts a) and b). This problem does not involve implementing the buddy system, it involves code that calls buddyallocate() and buddydeallocate(), probably fewer than 15 lines of code total. (0.4 points)

  2. Background: In a boundary tag storage allocator, consider the following design options:
    linking of boundary tags
    Each tag may contain a pointer to just its successor or to both its successor and predecessor.
    linking of free blocks There may be no free list, or a singly linked free list, or a doubly linked free list; in the latter, each free block contains a pointer to both its successor and predecessor.

    Assume you are writing a boundary tag heap manager that uses prompt merger of free blocks. That is, when a block is freed, it is immediately merged with its neighbors if they are free. Also assume that if a free list is used, newly freed blocks (after merging with their free neighbors) are simply placed at the head end of the free list.

    a) Regardless of how the free list is organized, which of the above boundary tag structures will work for this heap manager? For the option that do not work, explain why. (0.3 points)

    b) Of the options for linking free blocks, which one or ones can be made to work with this heap manager? For the option or options that do not work, explain why. (0.3 points)

    c) (0.4 points) The options discussed above have an impact on internal fragmentation because they determine the minimum amount of memory that may be returned to the free list when splitting an oversize block. Assuming that you measure memory in units of one pointer, what is the largest internal fragment size for each of the tag and free list options outlined above -- note that there are 6 total options you must cosider, 2 times 3.

  3. Background: If all free blocks on the heap are aligned to a word boundary on a machine that supports byte addressing, the least significant bit (or bits) of each word pointer will always be zero. This allows us to store the status of each block on the heap in the least significant bit of one of the pointers in the boundary tag.

    Assume that p points to an aligned block of memory, and assume that status is an integer containing the status bit, so the values are either zero or one. Note that <stdint.h> contains a definition for the type intptr_t, an integer type that is able to hold one pointer.

    a) Give C code to pack status into the least significant bits of p. (0.3 points)

    b) Give C code to extract status from the least significant bits of p. (0.3 points)

    c) Give C code to erase the status bit from p so that it may be safely used as a pointer on a machine that does not ignore the least significant bits of pointers. (0.4 points)