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.
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
implement two standard algorithms: quicksort and heapsort, both working
on a large array of randomly-chosen integers (see
man page for
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
int load (int *p); void store (int n, int *p);
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
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
indicate that the first page has become accessible and the second has
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
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
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
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.)
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:
storefunctions, 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?
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
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.
By the date shown below, e-mail a postscript document to
ddi_btop, or hunt through files in
Back to the course home page