CSC 262

Lab Exercise: Memory Allocation Policies and Fragmentation

Due Thursday, May 3

Overview

For this project, you will construct a simulation of a memory system that uses swapping with variable size partitions. You will use the simulation to collect empirical measurements of fragmentation under different placement policies (best fit, worst fit, first fit, and next fit). Note that although we have described this as a simulation of memory allocation, the same issues arise in other areas as well (such as disk space allocation).

Although this assignment will specifiy the parameters of the simulation in some detail, many of the implementation details will be left up to you. In particular, you will need to decide upon the data structures necessary to carry out the simulation. At the bottom of this document are some suggestions about how you might go about this, for those who aren't sure where to start.

The Simulation

We'll simulate memory policy on a hypothetical machine with a memory divided into 1024 pages. (Each page represents some fixed amount of memory, although the exact amount isn't important. We'll measure everything in pages.) Jobs on this hypothetical machine will request a partition of a given size. Upon being assigned a partition of the requested size, they will run for some period of time, eventually terminate, and thereupon release the memory in their assigned partition.

The simulation should create a loop in which the following steps are carried out repeatedly. Each time through the loop is referred to as a time step.

  1. A new job is generated (see below).
  2. If a hole exists that is large enough to accommodate a partition of the requested size, then the partition is created and assigned to the new job.
  3. Otherwise, one of the running jobs is chosen at random and removed from memory. (This can represent a swapping process, or more simply the natural termination of some job after an undefined length of time.) If this creates enough space, then the new job is run; otherwise, additional randomly chosen jobs are removed from memory until a sufficiently large hole has been created.
  4. The degree of fragmentation (fraction of memory occupied by holes) is calculated and stored for later reference.

A simulation will normally pass through several phases. Initially, the entire memory is empty, and the first few jobs generated will fit entirely in memory, without any holes between them. This will probably be the largest number of jobs in memory during the entire simulation. Once the memory has been filled, it will become necessary to remove processes periodically before adding others. However, it may take some time before a state of equilibrium is reached, such that the average number of jobs in memory is steady over long periods of time. Therefore you should allow the simulation to run for a long time (say 1000 time steps) before starting to take any measurements.

To Do

Your job is to write a program that carries out the simulation described above, under a variety of experimental conditions. The first condition to vary is the average size of the job (in blocks). The class GenJob.java contains two static methods that generate job sizes from two different size distribution profiles. When run, your program should allow the user to choose which of these two profiles to use.

The second condition to vary is the replacement policy. Again, your program should allow the user to choose. The four choices are best fit, worst fit, first fit, and next fit. These were described in class, but for your convenience a synopsis is provided below.

Best Fit
Use the smallest hole that will fit the requested partition. (In case of ties, use the hole that is lowest in memory, i.e., has the lowest address.)
Worst Fit
Use the largest hole that will fit the requested partition. (In case of ties, use the hole that is lowest in memory, i.e., has the lowest address.)
First Fit
Searching upward from the bottom of memory, use the first hole found that will fit the requested partition.
Next Fit
Searching upward from the last hole filled, use the first hole found that will fit the requested partition. Wrap around to zero when the top of the memory is reached.

In all there are eight experimental conditions (2 job profiles times 4 policies). Run a simulation of each condition, recording the following information over 1000 time steps (don't forget that you must run the simulation for 1000 steps before starting to record, making 2000 time steps in all):

Note that to compute the average, you should compute these values for each frame, add them to a running sum over all 1000 frames, and divide by the number of frames. For extra credit, your program can also record the following additional information:

When you've done the simulation under all eight conditions, you should assemble your results in a text file named summary.txt. This should include tables that allow all eight conditions to be compared based upon each of the statistics described above. (Don't just give me the raw program output unless you have set the program up to produce such tabular data.) In addition, you should provide an analysis of your results. Do they confirm what we said about the different policies in class? How does the average job size affect the results, if at all? Do they uphold Knuth's 50% rule, or cast doubt upon it? What about Denning's rule?

The care you take with your summary will make up a significant portion of your grade, so please don't stint on it. The analysis should comprise at least a handful of well-written paragraphs addressing all of the above questions. It should summarize all that you have learned from the simulation, and anything else of interest that you may note.

Additional Investigations

If you're interested in pursuing the simulation farther, there are interesting questions that can be asked about non-equilibrium behavior. How long does the system take to reach equilibrium at the start? (Probably the number is much less than 1000 time steps.) If you implement memory compaction (disturbing equilibrium), how many time steps does it take before equilibrium is again reached? These are the questions that would have to be asked by someone designing a system that seeks to avoid fragmentation through periodic memory compaction.

To Submit

You should submit source code for your program, a transcript of it running, and a summary of the results.

Implementation Hints

As we said in class, there are two standard ways to keep track of holes and partitions in memory: bit maps, and linked lists. Although it may seem that the bit map implementation is easiest, you may find the linked list more powerful for this exercise. Each node in the list must keep track of its size and whether the block represented is a hole or a partition. Thus you will have a vector of objects of class MemBlock. The order of the blocks represents their order in memory. Some starter code is provided below.

A number of functions will prove to be useful tools. You'll want one to assign partition to a hole, either replacing the hole (if a perfect fit) or creating a new partition block and shrinking the hole. You'll want another one to remove a partition, converting it to a hole, and combining it with any holes that may exist on either side. You'll want a function to count the partitions currently in memory and choose a random one to evict, and another to choose a hole in which to place a new partition of a specified size according to the policy in effect. If there is no hole large enough, the placement function may evict partitions itself, or return a failure code to the calling function, which will do the eviction and then retry placement. Finally, you will want statistics-gathering functions to scan the list of blocks and count up the number of holes and their size. As a sanity check, you may wish to ensure that your program maintains the same total number of pages in the system throughout!

Remember that your program should demonstrate good coding practices. Include comments before each function and wherever else they can help clarify the code. Try to avoid unnecessary convolutions. Write beautiful code!

One final hint: choose long and descriptive variable names for the statistics your program will compute. That will make it easier to keep them straight (since there are quite a few of them).

Here is some code to start you off: MemSim.java