Assignment 11 Solutions

Part of the homework for 22C:50, Summer 2004
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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

    6. Figure 14.6 illustrates only one example of the initial layout of free blocks using the binary buddy system in a memory region that does not start at location zero or has a size that is not a power of two. For an arbitrary block of size n, where n is an arbitrary integer, what is the largest size of free block that is guaranteed to be available?

    First find i such that 2i < n < 2i+1. It may be possible to find a block of size 2i, but you are guaranteed to be able to find a block of size 2i-1.

  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.

    Here, we assume everything is in RAM to avoid questions about registers, except that we assume the return value is passed in a register.

    • the return address
    • the parameter i
    • the variable f1
    • the variable f2

    It may also be necessary to save a pointer to the previous activation record in order to simplify popping the entire mess off the stack in one instruction. It is possible for an optimizing compiler to shrink this by one word, since the variable f2 is not needed prior to the second recursive call, and the variable i is not needed after that call, so they can be stored in the same memory address.

    If we assume that parameters are passed in registers and that local variables are allocated in registers, the activation record can be the same size, except that instead of holding variables and parameters, the activation record will hold saved values of registers.