CSE 303, Autumn 2007, Assignment 5

Memory Management

Due: Wednesday Thursday, November 28 29, 2007 at 9 pm

Turn-in here

Synopsis

In this assignment you will work with a partner to develop and benchmark a memory management package. You will also create a benchmark program to test your implementation and report statistics about it. You should work with a partner on this project. You and your partner should turn in a single assignment, and both partners will receive the same grade on the project. Be sure to have both of your names on the assignment, but only turn in a single copy under one of your names.

Step 0 - Pick a partner. Now!

As soon as possible, but no later than the beginning of the week of Nov. 19, you should pick a partner. One of you should send a note to Brian Ngo, the TA in charge of this assignment (brianngo at cs), with your names and your CSENetIDs. We will use this information to assign you and your partner to a Unix project group and set up a project directory where you can store the code repository and any other files you wish for this assignment.

While we will not specifically forbid you from working alone on this assignment, it is not to your advantage to do so. As an incentive, students who work in groups will receive a non-zero bonus in their overall score.

Assignment goals

This assignment continues our exploration of procedural programming, memory management, and software tools, as well as software development and working in groups. In particular, in this assignment you will

Please get started early. Even if you are working with a partner, there is enough to do that you will be in trouble if you wait to begin until the weekend before this assignment is due.

Requirements

The project consists of two main technical pieces: the memory management package, and a program to exercise it and report statistics. One of the members of your group should be in charge of the memory management package; the other should take responsibility for the benchmark program and testing. While ultimately both of you are responsible for, and should understand all of the code, it is very helpful if you separate the primary responsibilities for the two main parts of the project, and help each other as needed.

Memory Management

The memory management package should include a header file mem.h and a C implementation mem.c that specify and implement the following three functions.

Test and Benchmark

You should implement a program named bench, whose source code is stored in a file bench.c. When this program is run, it should execute a large number of calls to functions getmem and freemem to allocate and free blocks of random sizes and in random orders. This program should allow the user to specify parameters that control the test. The available parameters, and their default values are given below. Trailing parameters can be omitted, in which case default values are used.

Synopsis:   bench [ntrials [pctget [pctlarge [small_limit [large_limit [random_seed ]]]]]]

Parameters:

When bench is executed, it should perform ntrials memory operations. On each operation, it should randomly decide either to allocate a block using getmem or free a previously acquired block using freemem. It should make this choice by picking a random number with a pctget chance of picking getmem instead of freemem. If the choice is to free a block and all previously allocated blocks have already been freed, then there is nothing to do, but this choice should be counted against the ntrials total and execution should continue.

If the choice is to free a block, one of the previously allocated blocks should be picked randomly to be freed. The bench program must pick this block and update any associated data structures used to keep track of allocated blocks in amortized constant (O(1)) time so that the implementation of the bench program does not have unusual effects on the processor time needed for the test.

The next three parameters are used to control the size of the blocks that are allocated. In typical use, memory managers receive many requests for small blocks of storage interspersed with some larger ones. To model this behavior, each time a new block is allocated, it should be a large block with probability pctlarge; otherwise it should be a small block (use a random number generator to make this decision with the requested probability). If the decision is to allocate a small block, request a block who size is a random number between 1 and small_limit. If the decision is to allocate a large block, request a block whose size is is a random number between small_limit and large_limit.

While the test is running, the benchmark program should print the following statistics to stdout.

The program should print this 10 times during execution, evenly spaced during the test. In other words, the first report should appear after 10% of the total getmem/freemem calls have executed, then after 20%, 30%, etc., and finally after the entire test has run. You may format this information however you wish, but please keep it brief - one line for each set of output should be enough.

Additional Requirements

Besides the software specifications above, you should meet the following requirements for this assignment.

Memory Management

The above section describes what you need to do. This section gives some ideas about how to do it. We will talk about this further in class, and you should take advantage of the class discussion list to trade questions, ideas, and suggestions.

The basic idea behind the memory manager is fairly simple. At the core, the getmem and freemem functions share a single data structure, the free list, which is just a linked-list of free memory blocks that are available to satisfy memory allocation requests. Each block on the free list starts with an int that gives its size, and a pointer to the next block on the free list. To help keep data stored in dynamically allocated blocks properly aligned, we require that all of the blocks be a multiple of 8 bytes in size, and that their addresses also be a multiple of 8.

When a block is requested by getmem, it should go down this list looking for a block of storage that is at least as large as the amount requested, delete that block from the free list, and return a pointer to it to the caller. When freemem is called, it should return the given block to the free list, combining it first with any adjacent free blocks if possible to create a single, larger block instead of several smaller ones.

The actual implementation needs to be a bit more clever than this. In particular, if getmem finds a block on the free list that is substantially larger than the storage requested, it should divide that block and return a pointer to the portion that is large enough to satisfy the request, leaving the remainder on the free list. But if the block is only a little bit larger than the requested size, then it doesn't make sense to split it and leave a tiny chunk on the free list that is unlikely to be useful in satisfying future requests. You should experiment with this threshold and see what number is large enough to prevent excessive fragmentation, without wasting too much space that could have been used to satisfy small requests. The actual number should probably be a symbolic constant given in a #define in your code.

What if no block on the free list is large enough to satisfy a getmem request? In that case, getmem needs to acquire a good-sized block of storage from the underlying system, add it to the free list, then split it up, yielding a block that will satisfy the request, and leaving the remainder on the free list. Since requests to the underlying system are (normally) relatively expensive, they should yield a reasonably large chunk of storage, say 4K or 8K or so that is likely to be useful to satisfy several future getmem requests. Normally the same amount is acquired each time it is necessary to go to the underlying system for more memory. But watch out for really big getmem requests. If getmem is asked for, say, a block of 20K of storage, it needs to get at least that much in a single chunk since the underlying system cannot be relied on to return adjacent blocks of storage on successive calls.

So what is "the underlying system"? For our purposes, it is the standard malloc function! Your memory manager should acquire large blocks of storage from malloc when it needs to add to the free list. malloc guarantees that the storage it returns is allocated on 8-byte, 16-byte, or larger boundaries on modern systems, so we don't need to worry about whether the block we get from malloc is properly aligned.

Notice that a request for a large block will happen the very first time getmem is called(!). When a program that includes getmem and freemem begins execution, the free list should be initially empty. The first time getmem is executed, it will discover that the (empty) free list does not contain a block large enough for the request, so it will have to call the underlying system to acquire some storage to work with.

What about freemem? When it is called, it is passed a pointer to a block of storage and it needs to add this storage to the free list, combining it with any immediately adjacent blocks that are already on the list. What freemem isn't told is how big the block is(!). In order for this to work freemem somehow has to be able to find the size of the block. The usual way this is done is to have getmem actually allocate a block of memory that is a bit larger than the user's request, store the block size at the beginning of the block, then return a pointer that is actually a few beyond the actual start of the block. Then freemem can take the pointer it is given, subtract the appropriate number of bytes to get the actual beginning address of the block, and find the size of the block there.

How is freemem going to find nearby blocks and decide whether it can combine a newly freed block with one(s) adjacent to it? There are various ways to do this (as usual), but a good basic strategy is for getmem and freemem to keep the blocks on the free list sorted in order by ascending memory address. The block addresses plus the sizes stored in the blocks can be used to determine where a new block should be placed in the free list and whether it is, in fact, adjacent to another one.

It could happen that a request to freemem would result in one of the underlying blocks obtained from the system becoming totally free, making it possible to return that block to the system. But this is difficult to detect and not worth the trouble in normal use, so you shouldn't worry about this possibility.

One other wrinkle: If getmem always starts scanning the free list from the beginning when it is looking for a block of suitable size, it is likely to leave lots of little fragments of unused space at the beginning of the list. It can improve fragmentation, and speed things up, if each subsequent search starts from where the previous search left off, wrapping around to the front of the free list if the end is reached before finding a suitable block. Don't implement this at first, but once your code is running, you might experiment with this idea to see if, or how much it helps.

Implementation Suggestions

Here are a few ideas that you might find useful. Feel free to use or ignore them as you find them helpful or not.

The Benchmark Program

The command line may contain several integer parameters. These need to be converted from character strings ("500") to binary int values. There are various library functions that are useful: look at atoi and related ones.

The benchmark program relies heavily on random numbers. The standard library function rand can be used to generate sequences of pseudo-random numbers. Given a particular starting number (the seed), rand (or any random number generator) will always generate the same sequence of numbers on successive calls. This can be very helpful during testing (i.e., things are basically random, but the sequence is reproducible). If you want to generate a different sequence of numbers each time the program is executed, you can set the seed to some quantity that is different on each run - the system time is a good choice, and is the default if no seed is given on the benchmark program command line.

One of the benchmark quantities that should be printed is the processor time used. The clock library function can be used to measure this. Store the time right before starting the tests, then subtract this beginning time from the current clock time whenever you need to get the elapsed time.

Finally, the benchmark program needs to keep track of all of the pointers returned by getmem but not yet freed, and randomly pick one of these to free when the "coin flip" says to free some storage. The obvious way to handle this is to allocate a "big enough" array using malloc (not using getmem! Why?) and store the pointers there. When a pointer is picked randomly to be freed, you should move a pointer from the end of the list to the spot occupied by the freed pointer. That way picking the pointer and updating the list can be done in O(1) time, so the order in which the pointers are picked won't affect the time needed by the benchmark program itself to run the tests.

Developing and Testing

As with all projects, you should start (very) small and incrementally build up the final project. Here are some ideas:

Extra Credit

A small amount of extra credit, way less that it is worth in proportion to the amount of extra work and learning involved, will be awarded for the following extension. Modify the free list and memory allocation routines so that blocks can be added to the free list and combined with adjacent blocks in constant time. One way to do this is the following. In addition to the header information at the beginning of each block containing its size, every block, both allocated and on the free list, should contain an extra few bytes at the end with length information and/or extra pointers and/or "free/allocated" bits. The idea is that when a block is being freed, we can look at the immediately preceding and following storage to find the end and beginning of the previous and next blocks, and from there we can determine whether they are free or allocated and how big they are.

DO NOT ATTEMPT THIS until you have completed the basic assignment and turned it in.

For more information, in addition to Google and Wikipedia, an authoritative discussion is in Sec. 2.5, Dynamic Storage Allocation, in The Art of Computer Programming, Vol. I: Fundamental Algorithms, by Donald Knuth.