Project IV: Virtual Memory

The goals of this project are:
  • To demonstrate mastery of the virtual memory concept.
  • To learn the code mechanics of operating system fault handlers.
  • To develop skills in quantitative system evaluation.
  • To gain further experience in writing short technical reports.

Project Overview


In this project, you will build a simulator to evaluate different page replacement techniques for a demand paged virtual memory system. The following figure gives an overview of the components: the system simulates a process with a given size of virtual memory (number of pages) and a physical memory (number of frames) that is typically smaller in size than the virtual memory. A page fault handler is invoked each time a page is referenced that is not present in physical memory. The handler is responsible for adding the missing page to physical memory, possibly evicting a page to make room for the new page, and maintaining a page table that keeps track of page-to-frame allocations.
Your simulator will take several input parameters such as the number of pages (of the simulated virtual process), the number of frames (of the simulated RAM), the desired page replacement strategy, and parameters that determine the page reference pattern. Your simulator will create a page table and allocate pages to frames on demand, i.e., each time we experience a page fault (the page is not in physical memory), the missing page has to be added to the physical memory into an available frame. If the simulator runs out of available frames, the page replacement strategy determines which frame to free up, i.e., which page to remove from physical memory to make room for the missing page. Once your system is working correctly, you will evaluate the performance of several page replacement algorithms across a range of systems with different numbers of pages and frames. You will write a short lab report that explains the experiments, describes your results, and draws conclusions about the behavior of each algorithm.

Simulator Functionality


The simulator will generate a page reference pattern (as shown in the examples in class) and then use this pattern to manage the virtual memory, the physical memory, and the page table. Your program must be invoked as follows: 
./virtmem npages nframes rand|fifo|lru nrefs ll|ml|hl
The first parameter npages indicates the number of pages in the simulated process. Your simulator should be able to support up to 1000 pages. Pages are numbered [0..npages-1] (e.g., if npages is specified as 5, the system has pages 0, 1, 2, 3, and 4). The second parameter nframes is the number of frames to create in the system ([0..nframes-1]). Your simulator must be able to support systems with up to 500 frames. The third argument is the page replacement algorithm. You must implement rand (random replacement), fifo (first-in-first-out), and lru (least recently used). The last two parameters will be used to build a page reference pattern. The parameter nrefs indicates how many page references your page reference pattern will include; your simulator should be able to support up to 5000 references. The next parameter indicates the locality of page references in the page reference pattern (more details about this parameter is provided below).

Page Reference Pattern


Before simulating the virtual and physical memory, your simulator needs to generate a page reference pattern, i.e., a sequence of pages that the simulated process accesses. For this, you will need to use a random number generator, e.g., the rand() library call can be used as follows: 
srand(time(NULL));
randomnumber = rand()%10;
This example first initializes ("seeds") the random number generator using the time function (you only need to call this once in your program). With rand you can generate a new random number (integer); if you want to constrain the number within a certain range, you can use the modulo operator (%) as shown in the example (the example will yield a number from 0 to 9 each time the function is called). You will generate a sequence of integers (representing the pages accessed) of length nrefs.
The fifth parameter to virtmem indicates the level of "locality" as follows: 
ll = low locality
ml = medium locality
hl = high locality
This parameter indicates how likely it will be that the next page reference will be in close proximity to the previous one. This parameter identifies three different situations that your simulator needs to implement as follows:
  • When ll is specified, your simulator will generate page references completely random as described above, i.e., any page from 0 to npages has the same probability of being accessed. This would simulate a very random pattern of instruction and data accesses in a process.
  • When ml is specified, your simulator will first generate a random page reference as before, but every subsequent page reference is constrained within about +-5% (of the total number of pages) from the previous one. For example, if there are 100 pages and your simulator chose page 40 as the first page, the next page should be chosen in the range of 35-45 (the lower and upper limits are 0 and npages-1). If the next chosen page is 32, the next allowable interval would be 27-37, and so forth.
  • When hl is specified, your simulator will behave exactly as in the previous scenario, but the range is even smaller, i.e., each subsequent page reference is constrained within +-3%.


Simulator Operation


Your job is to build a simulator that first determines a page reference pattern as described above and then simulates one of three different page replacement strategies. You will need to implement a data structure that serves as a page table that translates the virtual addresses of the process to physical addresses. Each time a page reference is simulated, your simulator will check this table. If the page is already in physical memory, nothing needs to be done. If it is not in physical memory, your simulator will call a page fault handler function that adds the missing page into physical memory. You can assume that initially frames will be filled in increasing order (i.e., first frame 0, then frame 1, etc.). Once there are no more frames available, the page fault handler has to determine a victim frame that is being cleared to make room for the missing page. When completed, your simulator will report the number of page faults and the number of empty frames in physical memory, e.g.: 
% ./virtmem 200 50 rand 500 ml 
Total number of page faults: 339
Number of empty frames: 0
You may certainly add some printfs while testing and debugging your program, but the final version should not have any extraneous output.

You will also turn in a lab report that discusses the experimental comparison of the three replacement strategies for different page access scenarios and that has the following elements:

  • In your own words, briefly explain the purpose of the experiments and the experimental setup, i.e., what do you expect to see from the comparison of the different strategies and how you perform this comparison.
  • Measure and graph the number of page faults for the following scenarios:
    • npages = 100, nframes = 50, nrefs = [50..250] in steps of 50
    • npages = 100, nframes = 10, nrefs = [50..250] in steps of 50
    First, use the "rand" page replacement strategy and for each scenario above plot a graph for page faults (with nrefs on the x-axis and page faults on the y-axis) for two different locality settings (ll, hl), i.e., this will result in one figure with four graphs (scenario 1 with ll, scenario 1 with hl, scenario 2 with ll and scenario 2 with hl). Repeat this for the "fifo" and "lru" page replacement strategies, i.e., you will have three figures in total (each figure showing four graphs). Spend some time to make sure that your graphs are nicely laid out, correctly labelled, and easy to read. Do not use colored backgrounds. You may connect data points with straight lines, but not with splines or curves.
  • Explain the nature of the results. If one algorithm performs better than another under certain conditions, then point that out, explain the conditions, and explain why it performs better.

Hints


  • Use a random number generator (e.g., rand() or lrand48()) to generate random numbers for your page access pattern generator and for your rand page fault handler. Make sure to properly seed your random number generator to make sure that each time you execute the simulator, there will be a new number sequence.
  • For the fifo strategy, you can just select the next frame in a circular fashion.
  • For the lru strategy, you can either use actual times (where you will have to store the timestamps of page accesses, e.g., you can use the clock_gettime() library call, which returns time in a structure in seconds and nanoseconds), you can implement the stack approach, you can implement the second-chance algorithm, or you can use reference bits (use a minimum of two bits). The choice is yours.
  • Carefully test your page access pattern generator, i.e., make sure it generates exactly the required number of page accesses, and that the probability requirements mentioned above are met for the different access pattern scenarios (degrees of locality). If the number of pages and frames are the same, each page should have at most one page fault.

Grading


Your grade on this assignment will be based on the following:
  • Correct implementation of demand paging with any arbitrary access pattern and amount of virtual and physical memory. (50%)
  • A lab report which is clearly written using correct English, contains an appropriate description of your experiments, contains correct results that are clearly presented, and draws appropriate conclusions. (30%)
  • Thorough attention to and handling of all possible error conditions, including user error. (10%)
  • Good coding style, including clear formatting, sensible variable names, and useful comments. (10%)

Turning In


Turn in all of your source code and a Makefile that builds virtmem when the user types make. Turn in a lab report named report.doc or report.pdf; the report should include the graphs mentioned above (do not submit the graphs as separate files!). Submission is via Canvas. This assignment is due at 5PM on Wednesday, November 29th. Late assignments will not be accepted.