CSC 2/456 Virtual Memory Assignment

For this assignment you will emulate, at user level, the behavior of several virtual memory policies. Your write-up will consist largely of a quantitative comparison of these policies.

256 version

When a process takes a page fault while running on an operating system that implements virtual memory, the kernel identifies the missing page, reads it in from disk, updates the process's page table, and re-starts the faulting instruction.

To obtain a frame into which to write the missing page, the kernel must in general evict something else. There are many possible policies that can be used to select a page (victim) to evict. For this assignment, you are to implement and evaluate random, FIFO, LRU, and NUR policies. (To minimize delays, most operating systems do page-out in the background, and maintain a pool of available frames. We will ignore this optimization for the purposes of this assignment. Instead, we will pretend that the kernel chooses a victim page at page fault time.)

For the sake of uniformity across groups, you are to write user-level programs that implement two standard algorithms: quicksort and heapsort, both working on a large array of randomly-chosen integers (see the man page for random). You will implement paging on only the portion of your process's address space occupied by the array. To do so you must write your program to perform all accesses to the array (after initialization) through special load and store functions:

      int load (int *p);
      void store (int n, int *p);
  

The load and store functions (which you must write) will keep track of which portions of the array are currently “paged in”. Initially, you should arrange for the lower, say, 1MB of the array to be present, and the rest to be “paged out”. When load or store needs to access a word on a paged-out page, it must choose a victim to page out and change some data structure (static to load and store) to indicate that the first page has become accessible and the second has become inaccessible.

Most operating systems use some variant of NUR. They are supported in this choice by hardware that sets a “used” bit in the TLB or page table every time a page is read or written. (There's also a “dirty” bit that is set each time the page is written, but you won't be needing that.) Since you don't have access to the used bit in user space, you'll have to emulate it inside load and store. In fact, given that you'll be emulating, you can do better than real hardware, and maintain a true LRU list for your pages. This is what will allow you to implement an LRU policy, something real OSes usually can't do.

The random replacement policy can make use of the standard library's random function. The FIFO policy should always choose as victim the next currently paged-in page, in circular memory order, after the most recent previous victim. The LRU policy should choose a page that has gone unaccessed longest. The NUR policy should choose the next candidate page, in circular memory order, after the most recent previous victim, where a page is considered a candidate if it is among, say, the N/4 least recently-accessed pages, where N is the number of paged-in pages. (This is not how NUR is actually implemented in practice, but it has the same effect.)

Your load and store functions should keep track of the number of page faults incurred. Your write-up should present, explain, and discuss the numbers of faults over a three-dimensional parameter space:

You should also run a few experiments to see how sensitive your results are to the distribution of numbers to be sorted. Try more than one seed for the random number generator, and try some “non-random” sequences as well, such as already sorted, or sorted in reverse order. (Be sure to use the same set of numbers when making any direct comparison across algorithms or policies; otherwise you may be measuring differences in workload rather than overhead.) Finally, you should run your program without using the load and store functions, and time it to see how long it runs. (Only time the sort phase of the algorithm; we'll assume that initialization pulls the whole array into memory, and that Solaris doesn't doesn't page it afterwards.) If the average page fault takes 5ms to service, what impact would real paging have on overall program run times?

456 version

Your assignment consists of the 256 assignment plus an additional evaluation of local v. global replacement policies.

You will need to emulate a collection of programs sharing a common set of page frames. The easiest way to do this is probably to run multiple threads within a single Solaris process. The threads should be doing unrelated work (independent sorts, for example), but should call the same load and store routines (those routines will of course have to be properly synchronized).

Under a local page-out policy the kernel chooses a victim page from among the pages of the faulting process. Under a global policy the kernel chooses the “best” victim on a system-wide basis. In general, global policies tend to maximize throughput, but local policies are better at guaranteeing at least a minimum level of service to each process.

Experiment with collections of 2 or 3 processes (threads) that have different memory needs (e.g. that sort arrays of different sizes). If every thread is given the same number of pages to work with, you should see noticeably different system behavior for local and global policies. You should count the number of global page faults, the number of faults incurred by each individual thread and, in the global case, the fraction of page faults that cause the eviction og a page belonging to some other thread. Discuss your results.

Extra Credit Suggestions

  1. If you're in 256, try the 456 assignment.
  2. Try some other memory-intensive user-level programs, with different memory access patterns. Potentially interesting possibilities include matrix multiplication and manipulation of a very large hash table.
  3. See if you can invent a replacement algorithm that minimizes page faults for your particular program.

Trivia assignment

By the date shown below, e-mail a postscript document to cs456 containing:

  1. The names of the members of your team. (They need not necessarily be the same as last time.)
  2. The size, in bytes, of pages and integers in C on Solaris. (Hint: see the man page for ddi_btop, or hunt through files in /usr/include.)
  3. Computer-generated bar and line graphs for the function y = x2, where x is an integer in the range [1..10].
You may generate your document using Word, LaTeX and Mathematica, or whatever other tool(s) you find convenient. Ascii or hand-written documents are not acceptable.

DUE DATE:

Remember: No extensions.


Back to the assignments and grading page

Back to the course home page

Last Change: 8 February 2000 / Michael Scott's email address