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:
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:
Build a run the first-fit allocation scheme using the test code (both are provided). You will need to evaluate the results generated using first-fit against others.
Implement a worst-fit allocation scheme (based on first-fit code). You will run the test code over this scheme to generate results. Again, you will need to evaluate the results generated using worst-fit against others.
Implement some code for creating and coalescing buddies in a buddy system implementation. The basic mechanism is provided for you, and you need to fill in these pieces.
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:
./cse473-p3 heap_size heap_protocol free_limit_p
heap_size is the size of the heap to use. Please run with heap sizes: 10,000, 100,000, and 1,000,000 (no commas in command).
heap_protocol is an integer identifier for the protocol. For first-fit, the heap protocol identifier is 0.
free_limit_p is a boolean indicating whether there is a limit to how much memory is freed when the heap is out of room for an allocation. Possible values are 0 and 1. If free_limit_p == 0, then we deallocate regions (emulating swapping of individual allocations) until there is a free hole big enough for the requested allocation. If free_limit_p == 1, then we free some percentage of the heap's memory (20%), and see if this permits allocation.
Note that we limit the size of an allocation to no larger than 5% of the size of the heap. Thus, even with a free limit, we have much more free space than the size of the allocation request. Nonetheless, some requests cannot be satisfied (see questions below).
Run the first-fit protocol for the 3 heap sizes and the 2 free option (limit or not), so you should have 6 runs for the first-fit data. Collect the results in files (you will need to redirect). We will use these to compare first-fit with other mechanisms later.
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.
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:
On allocation buddy_fit (provided) is invoked, and it calls buddy_create when there is no memory of the appropriate size (you should learn what this means from the previous lecture). In this case, buddy_create finds a larger memory chunk and decomposes it. You must also implement buddy_decompose to break the memory down to the right size.
On deallocation buddy_free (provided) is invoked, and it calls buddy_coalesce to determine if two free buddies can be composed into a larger memory chunk. Recall that we always compose buddies when both are free (although there are limitations on which memory elements are really buddies).
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.
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:
Operation statistics: Some of these stats are directly from the stats structure. See the structure definition in cse473-heap.h for info. These include Number of operations, Number of out_of_memory requests, Amount of memory allocated, Number of allocates, Number of frees.
External fragmentation statistics: Amount of free memory at end states the amount of external fragmentation is present in the heap. Percentage of free memory at end: provides the percentage of external fragmentation in the heap. Number of free blocks specifies how many free blocks (external fragments) there are.
Internal fragmentation statistics: Number of internal fragmentation in bytes: is a weakly-worded item that specifies the amount of internally-fragmented memory in the heap. Percentage of internal fragmentation:specifies the percentage of allocated memory that are internal fragments.
Based on the statistics, please answer the following questions:
Describe your approach for implementing buddy_coalesce and buddy_decompose.
Why is there only internal fragmentation for the buddy system results?
The first-fit and worst-fit mechanisms should allocate the same amount of memory when free_limit_p is off (set to 0). Why does the buddy system allocate more memory in this case?
Compare the amount of "free memory at end" between first-fit and worst-fit when free_limit_p is off. Why should worst-fit have less free memory?
The buddy system has a much smaller number of "out of memory requests" when free_limit_p is on. Why should that be the case?
The buddy system has a much lower "percentage of free memory at end" than worst-fit or first-fit. Why does that occur?
Grading:
Please turn in your code for cse473-heap.c (a printout, and we will have a dropbox for testing the code) and your answers to the project questions above. Points are distributed as follows:
A correct worst-fit implementation: 20 points
A correct implementation of buddy_create and buddy_decompose: 30 points
A correct implementation of buddy_coalesce: 20 points
Correct answers to the six project questions: 30 points, 5 points each
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).