Assignment 8, due Apr. 1

On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

1. Background: Consider the following implementaton of the C library malloc() function:

   #include <unistd.h>
   void * malloc( int size ) {
           void * p = sbrk( size );
           if (p = -1) {
                   p = NULL;
                   errno = ENOMEM;
           }
           return p;
   }
   

   a) Explain how this works. (0.5 points)

   b) Give at least two completely different reasons why this is a bad idea. One reason will become clear if you read the man page for sbrk(). The other reason depends on information in the man page for malloc(). (0.5 points)

2. Background: The buddy system requires that all memory blocks begin on an address that is a multiple of the block size. This makes it easy to initialize a heap where the heap begins on an address that is a multiple of the heap size. Consider a heap of size 2ⁿ bytes beginning at address i×2ⁿ. In this case, freelists[n] is set to i×2ⁿ and all of the other entries in freelists[] are set to null.

   The Problem Suppose you are on a 32-bit machine with 4-byte pointers and the heap begins at address 50 and runs to address 100. Divide this heap into blocks that meet the constraints of the buddy system and give a plausible set of initial values for the array freelists[], indicating, for each free list, which blocks are in that list. (one point)

   Background: Consider the problem of exercising a heap implementation. To do this, you need to perform large numbers of allocations and deallocations. Consider the following test program:

   #include <stdio.h>
   #include <stdlib.h>
   
   int main() {
           void * blocks[1000];
           int i;
           for (i = 0; i < 1000; i++) blocks[i] = NULL;
           for (i = 0; i < 100000; i++) {
                   int b = random() % 1000;
                   if (blocks[b] == NULL) {
                           int s = (random() % 1000) + 1;
                           blocks[b] = malloc( s );
                   } else {
                           free( blocks[b] );
                           blocks[b] = NULL
                   }
           }
   }
   

   a) How many bytes, on average, does this test program use from the heap? (0.5 points) b) This test program exercises the heap manager, but it does not test the heap manager. To test it, you need to do some computation to prove that each block of memory returned by malloc() is distinct and that, between the time a block of memory is allocated and the time it is deallocated, nothing the heap manager does damages the contents of that block. Suggest how the heap manager could be expanded to demonstrate this. (Don't write code, just outline in a sentence or two what that code would do.) (0.5 points)

MACHINE PROBLEM 4

Write a heap manager, using the heap implementation of your choice. The interface to your heap manager will be mymalloc() and myfree() with calling sequences that are fully compatible with the calling sequences of the heap manager in the C library. Your heap manager should use static initializaiton of global variables on startup, so there is no need for a separate initializer -- although you may need to write an initializer routine that mymalloc() calls the first time it is called.