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 ro|lw|hw
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 three 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 and the last parameter indicates how many write operations are part of this pattern if any. More details about these parameters are 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 same page should never be accessed twice in a row, so if your random number generator produces the same number in a row, add a simple function to correct this (e.g., simply add or subtract 1 in such a case).
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 generate a page reference and then choose the next N page references (N randomly selected from 1 to 10) no further than M pages away from that initial page reference (M randomly selected from 20-50). After these N page references have been generated, the next page can again be chosen randomly from all pages and the process repeats.
  • When hl is specified, your simulator will generate a page reference and limit subsequent references as described above, but N is randomly selected from 10 to 30 and M is randomly selected from 5 to 20.

The final parameter indicates the likelihood of a page access to be a write access (leading to a "dirty" page): 
ro = read only
lw = low write
hw = high write
When ro is specified, all page references are read accesses only. When lw is specified, each page reference should have a probability of 10% to be a write operation. Finally, when hw is specified, each page reference should have a probability of 20% to be a write operation.

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. Your page table also needs to keep track of write accesses, i.e., your simulator needs to have some sort of "dirty bit" that indicates if a page has been modified. When completed, your simulator will report the number of page faults, the number of dirty pages that had to be written back to disk, and the number of empty frames in physical memory, e.g.: 
% ./virtmem 200 50 rand 500 ml hw
Total number of page faults: 339
Total number of disk writes: 69
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 two 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, the same page should never be accessed twice in sequence, 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 30th. Late assignments will not be accepted.