CMPSC 473 - Project #3 - Heap Memory Management

Due Date: April 8, 2008. 100 points

Single person project. Do your own work!

In this project, you will implement some memory allocation/deallocation mechanisms (or parts of them) that can be used for heap memory. The ideas behind these mechanisms were discussed in the March 6 lecture and are described in the OSC book in Sections 8.3 (worst-fit and first-fit) and 9.8 (buddy systems and slab allocation).

This project will require you to implement parts of some of these mechanisms from some existing code that I provide. You will then have to run some test cases and analyze the behavior of the mechanisms against the results to evaluate the resulting behavior.

The project will consist of the following tasks:

  1. Download the following tarball Project 3 Code to your CSE account file space. You should have one file p3-memory.tgz.

    Your tasks are summarized as follows:

  2. The first step is to build the code (via make) which generates one program cse473-p3. This initial code provides an implementation of the first-fit memory allocation/deallocation mechanism (in the file cse473-heap.c). The function first_fit does allocation and the function list_free does deallocation according to the first-fit semantics.

    The initial code also includes a test mechanism that exercises memory allocation/deallocation (called run_suite in cse473-p3.c). By running the cse473-p3 program, this function will be invoked, which generates allocation/deallocation requests and collects statistics regarding the processing of these requests which are printed when the program completes.

    To run the cse473-p3, enter the following command:

  3. Next, you will need to take the first-fit code, and implement a worst-fit allocation mechanism. The function prototype worst_fit is provided for this function. Note that the implementation of first_fit should provide useful guidance for worst_fit.

    To evaluate worst-first, you need to run cse473-p3 (build it with your code) again. The protocol identifier for worst-fit is 1. Please run worst-fit for the same cases as first-fit (i.e., 6 runs total -- on heaps of sizes 10,000, 100,000, and 1,000,000 with limits turned on and off), and collect the results in files (you will need to redirect). We will use these to compare worst-fit with other mechanisms later.

  4. Also, you will need to implement the creation and coalescing of buddies in a buddy system implementation. I am providing you with the code to initialize, allocate, and free memory using the buddy system, but a key part of the buddy system is the decomposition of memory into buddies (on allocation) and the coalescing of memory with buddies (on deallocation). There are three functions that you need to implement: buddy_create and buddy_decompose for allocation and buddy_coalesce for deallocation.

    Like project 2, there is a bit of code to learn to figure out how to do these tasks. The data structures are defined in cse473-heap.h and there are some macros defined at the top of cse473-heap.c. Overall, the challenges are:

    To evaluate your buddy system, you need to run cse473-p3 (build it with your code) again. The protocol identifier for buddy allocation is 2. Please run the buddy system for the same cases as first-fit (i.e., 6 runs total -- on heaps of sizes 10,000, 100,000, and 1,000,000 with limits turned on and off), and collect the results in files (you will need to redirect). We will use these to compare the buddy system with other mechanisms later.

  5. Finally, you will need to compare the performance of first-fit, worst-fit, and the buddy system allocation. The program prints various statistics on the runtime behavior of the allocation mechanism. This includes the following fields:

  6. Based on the statistics, please answer the following questions:

  7. Grading:

    Here is example output for the programs. I got the same output on schuylkill (Linux 2.4) and crosby (my Linux 2.6 machine -- sorry, you can't use it).


Trent Jaeger