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!
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 holds the free list of 8-byte blocks, the smallest size supported, while freelists 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)
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)
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)