Assignment 10, due July 25

Machine Problem 5

Ground rules: The ground rules distributed with MP1 hold for this assignment!

Background: Tests of a heap manager require building some kind of application that builds and deletes huge data structures in the heap. One such application is available on line at:

http://homepage.cs.uiowa.edu/~dwjones/syssoft/spring03/hw/alloctest.c

This program repeatedly calls myalloc() and myfree, and you can test the test program itself by writing trivial versions of these that call the standard C functions malloc() and free().

The Assignment: Write and test a lazy boundary tag storage allocator that uses first-fit allocation without free-list rotation to allocate word-aligned space from a statically allocated array of 10,000 bytes. Here is more detail:

It should be lazy; that means that myfree() does almost nothing. All it has to do is set the state field of the boundary tag to indicate that the block is free. It does not even need to put the block back on the free-list! Only when myalloc() reaches the end of the freelist does it need to search for and merge adjacent free blocks and rebuild the free list. It is easiest to do this if the old free-list is simply discarded and a new one is built from scratch!

It should use first-fit allocation; that is, as soon as it finds a free block that is big enough, it should split that block, if necessary, and then return the right-sized block.

It should not rotate the free list. That is, it should start its search from the same place each time. This eliminates the need for a doubly linked or circular free list and allows a simple linear list.

It should allocate word-aligned space. That is, the pointers returned by myalloc() should always be aligned to a word boundary and never point to an odd address. You can assume that your heap itself is initially word-aligned.

Turn In Your source code plus a transcript of your test. To make it clear that the test is yours, make your allocator print out a one-line header when the heap_init function is called, and make it print out a one line report each time the free list is rebuilt. The latter report should state how many free blocks were put in the new free list and how many free blocks were merged in order to build that free list.

Warning: There's lots of pointer management in this code. You must budget your time carefully, since you know well that pointer management is murderous code to debug!

Homework 10

1. The test program distributed with MP5 builds a randomized and constantly changing data structure.

   a) Very broadly, what kind of structure is this? (It's not a circularly linked list or a lexicographic search tree, but those are phrases that describe other kinds of data structures, in the sense this question refers to.)

   b) What limits the size o the data structure? (there are actually two limits involved here, and you ought to try to identify both.)

2. Consider a heap manager that uses the binary buddy system to allocate memory from an array that runs from memory locations 10 to 100. Assume word addresses, no bytes! How is this heap divided initially! Give the starting addres and size of each initial free block.

3. Suppose we further simplified the boundary tag allocation system from the above machine problem by complete elimination of the free list.

   a) Outline, in a few words or brief pseudocode, how the allocate function would go about finding a large-enough free block.

   b) Is there any distinction in this system between lazy and prompt allocation? If so, identify it! (It can't have anything to do with rebuilding the free list!)