Assignment 11, due July 23

Machine Problem 5, due July 28

A Heap Manager

You are to write a heap manager supporting the following interface:

heap_init();

called to initialize your heap data structures; your heap should be a static array of 10,000 void* pointers (call them words for convenience).

void * myalloc(int s);

returns a newly allocated a block of s consecutive bytes. If the heap is full, it should return a null pointer.

myfree(void * p, int s);

called to deallocate the block of s consecutive bytes pointed to by p.

A main program to test your heap manager is provided in:

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

If you change the name myalloc to malloc and you change the name myfree to free in this test program and eliminate the second parameter to myfree, you can test the test program using the built-in heap manager.

Your storage manager should use the buddy system (see figures 14.3 and 14.4 in the notes). Since this much code is already given, the real assignment is as follows:

• Initialize the heap! You have no control of where in memory that array of 10,000 words will start, so you've got to find, somewhere in it, either one block of 8192 words (if you're lucky) or two blocks of 4096 words (more likely), plus a collection of smaller blocks that fill that 10,000 word array, having done this, your next job is to write code to pad things at either end of this block (these blocks) with smaller blocks that fill things out to the required 10,000 words.

  Strong advice: Do this incrementally. First solve the problem of finding one block or blocks. Then get the heap manager working with that block, then try to get the rest of the memory into the heap.

• Get rid of the recursion in the code for allocate and free! Strong advice: Don't do this until you have the thing working with a heap that's initialized to at least one block of 4096 words.

Assignment 11, due July 23

1. Do problem 6, from chapter 14 of the notes.

2. Consider this little bit of code:

      int fibonacci(int i);
      {
         int f1,f2;
         if (i < 2) return i;
         f1 = fibonacci(i-1);
         f2 = fibonacci(i-2);
         return f1 + f2;
      }
   

   Describe the contents and structure of the activation record for fibonacci() taking into account everything you know about assembly language programming. State any assumptions you made; for example, you will get a different result if you assume f1 and f2 are stored in RAM or are temporarily assigned to registers.