Assignment 10, due Nov. 8
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)
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.
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.
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.