Assignment 10, due Nov. 8

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

   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)

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)

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

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)

   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)