Assignment 3 : Losing Your Memory

Due :

13 November

Points : 

4

Teams :

You may do this assignment in teams of up to three people (total).

Description

At base, there is list of pages.   There is a fixed size for this list and all "processes" share memory in the list although  the pages in each process are distinct from the pages in all the other processes even if they have the same page number - that is, process 17 can have a page 6 and process 89 can have a page 6 and these are separate and may not be in page 6 in the page list. 

Each process executes a stream of some number of "instructions", each of which consists only of a page number (imagine that a page is only one word long, or alternatively, imagine that each of these instructions is actually many instructions) for the instruction and a page number for the data.   These are generated randomly (and you should not change the way they are generated in the project you hand in although building different ways to generate these streams may help with your debugging).     To run an instruction, both the instruction page and the datum page must be in the system page list.    When a page is needed by a process a page is removed (randomly!) from the page list and the requested page is added.   This is far from optimal.   Indeed, requesting the datum page for an instruction might result in the instruction page being removed.

You will probably want to add information to the Process class and to the Page class to assist in picking good pages to remove.

Purely for convenience there is an "idle process" which always fetches an instruction from address 0 and a datum from the same address.   The idea is that this process shouldn't block on any memory accesses and therefore there will always be one runnable process to advance the clock.  There is currently no logic in the code to guarantee this, this process can fault and end up unrunnable.    You should fix this so that once this process has read in location zero it never faults again. 

If you run it now and look at the results,  you'll see that the ratio of faults to instructions can be small (good) or large which means that several faults may be needed to handle a single instruction.    Notice that if every instruction is fetched exactly once, there would be two faults per instruction - one for the instruction address and one for the datum address.    If the same address/datum is used more than once, but does not need to be fetched each time the ratio gets better (smaller).  

There are a number of run time flags you can set.  the current defaults for these are set very small so that you can try running the program and get results relatively quickly.   They're really only for play and should be considered in that light.  For the experiments below, you should pick values like :

--process-count 

The total number of process to run at any given time (excluding the idle process) - 1000 is a good value here 

--clock-limit

Run the simulation until simulation clock reaches this time.   

--pages 

The  total number of pages in the system (shared among all processes).   This should be something like the total number of processes times 10

--average-instruction-count

The average number of instructions for each process to try to run.    This should be on the order of 1000-10000

--memory-limit 

The limit of memory that can be allocated for a single process.   Try a number of different values here if you can to see how things change.   Generally this should be somewhere less than the total number of pages divided by the total number of processes. 

--debug-level

The level of debugging you would like.   0 means no debugging output, 10 means everything is turned on.

--output-file

By default output is printed to standard output.   This allows you to get output into a file. 

What to do

Your assignment consists of three parts :

Make things worse

Change the page fetch algorithm to increase (if possible) the number of faults.   There is a simple way to do this, just always remove a page from memory when one is requested, so memory may not even fill up ever.   Don't do this.   Instead, just change the fetching algorithm so that when memory is full (and only when memory is full) it tries to pick out the worst page to remove.   Use a run time argument "--do-your-worst" to select this.

Make things better

Change the page fetch algorithm to decrease the number of faults.    Try to do as well as you can.   Use a run time argument "--do-your-best" to select this.

Make some plots

Run both options a number of times (say 100) with the same runtime flags and plot the results (gnuplot is good for this and has the virtue of being simple and running on almost every platform around).   You may have to think a bit about what to plot and how.  

Write it up

Write it all up.   Your write-up should look like the papers you read in assignment 1 and should include how you did both parts(in detail), why what you did improved things and why what you did made things worse.      Include (and explain) plots as necessary to explain your results.  
 

What to Submit

 Submit your source code and your write up (in PDF format).