Assignment 9, due Apr 11

Solutions

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

Background: In the notes for lecture 27, code is given for the binary buddy system.
a) Discuss the performance benefits of rewriting this code so that it is lazy. (0.5 points)

It should run faster, on average. Popular sizes of free blocks will frequently be available, so most of the time, allocation of blocks will not involve splitting blocks, and only when the heap is exhausted will there be any need to merge free blocks into larger blocks.

b) Discuss the performance penalties of rewriting this code so that it is lazy. (0.5 points)

First, the worst-case time for allocation goes up. The average time per allocation gets better with the move to lazy deallocation, but the cost is an occasional reorganization of the entire heap when an allocation request cannot be filled.
Background: The binary buddy system is subject to both internal and external fragmentation.
a) Identify the two distinct causes of internal fragmentation in the binary buddy system. (0.5 points)

First, there is a minimum block size set by the size of a pointer. If an application requests blocks smaller than this, internal fragmentation fragments will result from allocating the minimum instead of the actual request.
Second, block sizes are quantized at powers of two. If an applicaton requests other block sizes, they will be rounded up to the next permitted size, leading to internal fragmentation.

b) Of the above, one of them is eliminated in boundary-tag heap mangers, while the other may become worse. Explain. (0.5 points)

Boundary tag heap managers may have larger minimum block sizes, for example, because of the use of doubly linked free lists.
Boundary tag heap managers allow far wider range of block sizes. The sizes are still typically quantized (you cannot allocate fractional bytes or even fractional words with most implementations), but quantization to integers is far more generous than quantization to powers of two. This is the dominant factor, all of the others are insignificant.
As an aside, boundary tags introduce a new source of internal fragmentation. When it comes time to split a free block, there must be enough extra memory for a tag plus the minimum block size. If there is less than this, the block won't be split, leading to internal fragmentation.
Background: Consider an operating system using virtual memory, where the heap manager for a user process allocated memory in the virtual memory address space of that process. On this system, the MMU is turned off during execution of trap service routines. The operating system, mostly trap service routines, also needs a heap for its own data structures.
A question: Which of these differences suggests the need for using a different heap manager for application heaps and heaps used within the operating system. Explain. (0.5 points)

Locality of reference is a minor issue in real memory, but it is a major issue with virtual memory. Therefore, heap lanagers used in real memory, for example, within trap service routines in system given, can ignore locality, while heap managers used in the virtual address space of user processes should try to keep a compact heap.
Background: In the lectures, the notation memory(addr) was occasionally used, where addr was the integer memory address of a word in memory, and this notation allowed addressing the contents of that word as an integer.
A question: Write a C #define for memory() that makes this actually work as a legal notation within a C program. Your solution will involve casting integer to pointer, and it should work on both the left-hand side of an assignment and on the right-hand side of an assignment. (0.5 points)
```
#define memory(addr) ((int *)(addr))
```