Assignment 10, due Nov. 8

Solutions

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

  1. Background: Consider the buddy system. In the in-class presentation, the discussion focused on a memory of only 32 words, with just 5 free lists (blocks of 2, 4, 8, 16 and 32 words. We did not use 1-word blocks because they were too small to hold both the block size and a single word of user data.

    Now, consider the real world on a 32-bit computer with byte-addressable memory. Initially, the heap is empty. The only memory allocated is an array of 28 null pointers. freelists[3] holds the free list of 8-byte blocks, the smallest size supported, while freelists[31] holds the list of 2-gigabyte blocks, the largest size supported. (There can be no 4-gigabyte blocks because at least one byte of the RAM must be occupied by the code of the heap manager, preventing the entire memory from ever being listed in the free list.)

    If this system is on a UNIX machine, the heap manager will add memory to the heap whenever the current heap does not have the free space needed to meet the demand of a call to malloc(). Memory is added to the heap by calling sbrk() to allocate a block sized to the next power of two greater than twice the size requested by malloc().

    a) Does this guarantee that the heap manager will be able to treat the new block as a single free block? Why or why not? (0.5 points)

    No. It guarantees that the block size will be a power of two, but it does not guarantee that the block will be aligned properly. The buddy system requires that a block of size 2i bytes begin at an address with i zeros at the least significant end. So, blocks of 16 bytes must have addresses of the form xxxx0000. sbrk(16) makes no guarantees about the alignment of the allocated block.

    b) It is always possible that a user program will call sbrk() directly between two different calls to malloc(). As a result, it is possible that the heap will not be a single contiguous block of free space, but will, instead, contain gaps that are not under the heap manager's control. Does this cause any problems under the buddy system as discussed in class? explain. (0.5 points)

    No, except that blocks on opposite sides of the gap caused by a user's call to sbrk() can never be merged. In effect, the gap caused by a user call to sbrk() behaves like an allocated block that will never be deallocated.

  2. Background: Consider an application where the heap is managed using the buddy system. We have two choices in implementing this system, lazy merger and eager merger. In the lazy system, free blocks are allowed to accumulate in the free lists, and the only time free blocks are merged is when an allocate cannot be completed. That is, when the free lists for the requested size and all larger sizes are null. At that point, all free lists are searched for free blocks that can be merged, and all possible mergers are done.

    Textbook presentations of the buddy system tend to use eager merger, where, each time a block is deallocated, a search is made of the appropriate free list to see if it can be merged with its buddy. In this case, we can guarantee that two buddies originally split from the same block will never both be included in any free list.

    a) If your primary concern was response time -- that is, the worst case time it takes to complete a single operation, which would work better. Why? (0.5 points)

    Eager merger gives better response time because there is a guarantee that, for an n-bit memory address, no single call to free() will involve more than n mergers, and no call to malloc() will involve more than n splits. In contrast, with lazy merger, merging free blocks is rare, it only occurs when malloc() finds no block big enough, and the number of mergers is bounded only by the heap size, that is, we move from O(n) to O(2n) in our worst-case response time.

    b) In a virtual memory syste, which is likely to lead to more page faults? (0.5 points)

    In a lazy system, we use up the entire heap before we do any mergers, so it is likely that the locality of reference will be worse. With eager merger, it is more likely that a small number of blocks will be repeatedly split and merged at the low end of the heap, improving locality of reference.

  3. Background: Consider the following general data structures for a boundary-tag heap manager: The list of blocks on the heap is doubly linked, so each boundary tag contains a pointer to its immediate predecessor and its immediate successor in the heap. The free list is doubly linked, so each free block contains a pointer to its successor and predecessor in the free list.

    When you deallocate a block, you check to see it its successor and predecessor are free. If either is free, you merge the free blocks into one block. When you allocate a block, you search the free list for a big enough block and then split off any excess, if possible.

    a) At what point in the above description of the algorithm do you actually need the back link within the free list? (0.5 points)

    To merge a block with its free successor b, you need to unlink b from the free list. The code to do this would be: 

    b->back->next = b->next; /* the first use of the back link */
b->next->back = b->back;

    b) If you always search the free list starting at the same point, is your search likely to be longer or shorter than if you search starting at a different point each time? Explain. (0.5 points)

    If you always search from the same point, all free blocks big enough to hold your popular block size will dissapear from the nearby portion of the free list. What remains will be a clutter of small fragments of sizes you don't need. In contrast, if you always search from a different point (for example, just beyond the block you most recently allocated), small fragments will end up uniformly distributed through the free list.