Memory Management

Purpose

The main goal for this project is to modify the Linux memory system to implement several different allocation strategies: first fit (done), next fit and best fit. You must implement:

A system call to select the allocation algorithm. 

The various allocation algorithms. 

A user process to collect and process statistics. 

You will run a synthetic workload to evaluate the performance of the allocation algorithms that you have developed. 

Just like the previous project you will experiment with operating system kernels, and to do work in such a way that may very well crash the (simulated) computer. You'll get experience with modifying a kernel, and may end up with an OS that doesn't work, so you'll learn how to manage multiple kernels, at least one of which works. 

You should also read over the general project information page before you start this project. In them, you will find information about Linux as well as general guidelines and hints for projects in this class. 

Basics

The goal of this assignment is to give you additional experience in modifying Linux and to gain some familiarity with memory management. In this assignment you are to implement at least three allocation policies: first fit (which is already done, but will need to be made to live peacefully with the new algorithms), next fit and best fit. An ambitious student (one who wants extra credit, perhaps) would also implement random fit, worst fit and perhaps a policy of their own creation. 

You can find discussions of these algorithms in either Tanenbaum text (indeed, in any operating systems text). Briefly, first fit chooses the first hole in which a segment will fit; next fit, like first fit chooses the first hole where a segment will fit, but beginning its search where it left off the last time (so you will need some persistent state), and best fit chooses the hole that is the tightest fit. 

You need to implement a system call that will allow the selection of the allocation policy. Note that the policy has a global affect on the system, since it applies to all processes. Such a system call should only be executable by root, so you should check the effective uid of the process making the call. The default policy should be first fit. Each time next fit is selected by a system call, the next memory allocation will start at the front of the list (in other words, the next pointer is reset). Subsequent allocations using next fit pick up where the previous one left off until a new policy is selected by the system call. 

Details

In this project, you will modify the memory allocation policy for Linux. The current Linux allocation policy is simple: it implements first fit only. Changing this policy should mostly involve modifying code in servers/pm/alloc.c (All of the source code, except where specified explicitly, is in /usr/src). 

There needs to be a system call to select the allocation policy. You may create your own system call or modify an existing system call. Your design document should contain the details of how you're going to implement this. 

You will implement a user process that will gather statistics regarding the number and the size of the holes. You can get this information via the system call getsysinfo (see servers/pm/misc.c). You should gather this information once per second and compute the number of holes as well as cumulative statistics on their average size and the standard deviation of their size. This information will be printed to a file in the following format: 

"%d\t%d\t%.2f\t%.2f\n", t, nholes, avg_size_in_mb, std_dev_size_in_mb

Your program should take one argument: the name of a file to print to. You should use fopen and fprintf to print the lines to the log file. The value for t should start at 0, and increment each time a line is printed. 

This experiment wouldn't be much fun without a workload. Since memory allocation in Linux is pretty much static (pre-allocated data segment sizes), we've created a set of programs for you that will use differing amounts of memory. The main program, memuse, will fork off a bunch of other processes that use memory in differing amounts for varying amounts of time. Feel free to modify the code if you like. Further details on specific experiments to run will follow shortly; we will supply specific workloads for you to run against all three (or more) memory allocation algorithms. 

Deliverables

You must hand in a compressed tar file of your project directory, including your design document. You must do a "make clean" before creating the tar file. In addition, you should include a README file to explain anything unusual to the teaching assistant. Your code and other associated files must be in a single directory; the TA will copy them to his Linux installation and compile and run them there. You should have two subdirectories in your tar file below your main directory: one containing the kernel source files from the servers/pm directory, and the other containing your user program. 

Do not submit object files, assembler files, or executables. Every file in the tar file that could be generated automatically by the compiler or assembler will result in a 5 point deduction from your programming assignment grade.

Your design document should be called design.txt (if plain ASCII text, with a maximum line length of 75 characters) or design.pdf (if in Adobe PDF), and should reside in the project directory with the rest of your code. Formats other than plain text or PDF are not acceptable; please convert other formats (MS Word, LaTeX, HTML, etc.) to PDF. Your design document should describe the design of your assignment in enough detail that a knowledgeable programmer could duplicate your work. This includes descriptions of the data structures you use, all non-trivial algorithms and formulas, and a description of each function including its purpose, inputs, outputs, and assumptions it makes about the inputs or outputs. 

Hints

START EARLY! You should start with your design, and check it over with the course staff. 

Experiment! You're running in an emulated system—you can't crash the whole computer (and if you can, let us know...). 

You may want to edit your code outside of Linux (using your favorite text editor) and copy it into Linux to compile and run it. This has several advantages: 

Crashes in Linux don't harm your source code (by not writing changes to disk, perhaps). 

Most OSes have better editors than what's available in Linux.