Assignment 11 Solutions

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 2ⁱ < n < 2ⁱ⁺¹. It may be possible to find a block of size 2ⁱ, but you are guaranteed to be able to find a block of size 2^i-1.

   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.