Virtual Memory Page Replacement Algorithms
Question: I have a project where I am asked to develop an application to simulate how
different page replacement algorithms perform (with varying working set size
and stability period). My results:

![](http://i.imgur.com/7nZhV.png)

![](http://i.imgur.com/mfIpW.png)

![](http://i.imgur.com/J9kbB.png)

![](http://i.imgur.com/YbJom.png)

  * Vertical axis: page faults
  * Horizontal axis: working set size
  * Depth axis: stable period

Are my results reasonable? I expected LRU to have better results than FIFO.
Here, they are approximately the same.

For random, stability period and working set size doesnt seem to affect the
performance at all? I expected similar graphs as FIFO & LRU just worst
performance? If the reference string is highly stable (little branches) and
have a small working set size, it should still have less page faults that an
application with many branches and big working set size?

**More Info**

**[My Python Code](https://gist.github.com/2259298)** | **[The Project Question](https://docs.google.com/viewer?a=v&q=cache%3aN4txsyBvve8J%3aics.uci.edu/~bic/courses/OS-2012/Lectures-on-line/VM-proj-NUS.pptx+&hl=en&gl=sg&pid=bl&srcid=ADGEESjy7SHm-YBMJ9kHJXbjILI751xst7xTEWnnhabelNMgn0WHSI-1hkFintnO7htxdmvPazAqQ73XtgzUG05dU1g9duZCfTyfFHRrBhqrtWz7ZUdFYRkkNErT-t6vdty8cMnnpQBd&sig=AHIEtbSZ7JrKOoDJhyGsy8F5dDETDwGNQA)**

  * Length of reference string (RS): 200,000
  * Size of virtual memory (P): 1000
  * Size of main memory (F): 100
  * number of time page referenced (m): 100
  * Size of working set (e): 2 - 100
  * Stability (t): 0 - 1

Working set size (e) & stable period (t) affects how reference string are
generated.

    
    
    |-----------|--------|------------------------------------|
    0           p        p+e                                  P-1
    

So assume the above the the virtual memory of size P. To generate reference
strings, the following algorithm is used:

  * Repeat until reference string generated 
    * pick `m` numbers in [p, p+e]. `m` simulates or refers to number of times page is referenced
    * pick random number, 0 <= r < 1
    * if r < t 
      * generate new p 
      * else (++p)%P

**UPDATE (In response to @MrGomez's answer)**

> However, recall how you seeded your input data: using random.random, thus
> giving you a uniform distribution of data with your controllable level of
> entropy. Because of this, all values are equally likely to occur, and
> because you've constructed this in floating point space, recurrences are
> highly improbable.

I am using `random`, but it is not totally random either, references are
generated with some locality though the use of working set size and number
page referenced parameters?

I tried increasing the `numPageReferenced` relative with `numFrames` in hope
that it will reference a page currently in memory more, thus showing the
performance benefit of LRU over FIFO, but that didn't give me a clear result
tho. Just FYI, I tried the same app with the following parameters
(Pages/Frames ratio is still kept the same, I reduced the size of data to make
things faster).

    
    
    --numReferences 1000 --numPages 100 --numFrames 10 --numPageReferenced 20
    

The result is

![enter image description here](http://i.stack.imgur.com/fyhZd.png)

Still not such a big difference. Am I right to say if I increase
`numPageReferenced` relative to `numFrames`, LRU should have a better
performance as it is referencing pages in memory more? Or perhaps I am mis-
understanding something?

For random, I am thinking along the lines of:

  * Suppose theres high stability and small working set. It means that the pages referenced are very likely to be in memory. So the need for the page replacement algorithm to run is lower? 

Hmm maybe I got to think about this more :)

**UPDATE: Trashing less obvious on lower stablity**

![enter image description here](http://i.stack.imgur.com/2fqVQ.png)

Here, I am trying to show the trashing as working set size exceeds the number
of frames (100) in memory. However, notice thrashing appears less obvious with
lower stability (high `t`), why might that be? Is the explanation that as
stability becomes low, page faults approaches maximum thus it does not matter
as much what the working set size is?


Answer: **These results are reasonable given your current implementation.** The
rationale behind that, however, bears some discussion.

When considering algorithms in general, it's most important to consider the
_properties_ of the algorithms currently under inspection. Specifically, note
their [_corner cases_](http://en.wikipedia.org/wiki/Corner_case) and best and
worst case conditions. You're probably already familiar with this terse method
of evaluation, so this is mostly for the benefit of those reading here whom
may not have an algorithmic background.

Let's break your question down by algorithm and explore their component
properties in context:

  1. _FIFO_ shows an increase in page faults as the size of your working set (length axis) increases. 

This is correct behavior, consistent with [Bélády's
anomaly](http://en.wikipedia.org/wiki/B%C3%A9l%C3%A1dy%27s_anomaly) for FIFO
replacement. As the size of your working page set increases, the number of
page faults should also increase.

  2. _FIFO_ shows an increase in page faults as system stability (_1 - depth axis_) _decreases_.

Noting your algorithm for seeding stability (`if random.random() <
stability`), your results become _less_ stable as stability (_S_) approaches
1. As you sharply increase the
[entropy](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29) in
your data, the number of page faults, too, sharply increases and propagates
the Bélády's anomaly.

So far, so good.

  3. _LRU_ shows consistency with _FIFO_. Why?

Note your seeding algorithm. [Standard
_LRU_](http://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used)
is most optimal when you have paging requests that are structured to smaller
operational frames. For ordered, predictable lookups, it improves upon FIFO
_by aging off results that no longer exist in the current execution frame,_
which is a very useful property for staged execution and encapsulated, modal
operation. Again, so far, so good.

However, recall how you seeded your input data: using `random.random`, thus
giving you a _[uniform
distribution](http://en.wikipedia.org/wiki/Uniform_distribution_%28continuous%29)_
of data with your controllable level of entropy. Because of this, all values
are equally likely to occur, and because you've constructed this in [floating
point space](http://en.wikipedia.org/wiki/IEEE_754-2008), recurrences are
highly improbable.

As a result, your _LRU_ is perceiving each element to occur a small number of
times, then to be completely discarded when the next value was calculated. It
thus correctly pages each value as it falls out of the window, giving you
performance exactly comparable to _FIFO_. If your system properly accounted
for recurrence or a compressed character space, you would see markedly
different results.

  4. For _random,_ stability period and working set size doesn't seem to affect the performance at all. Why are we seeing this scribble all over the graph instead of giving us a relatively [smooth manifold](http://en.wikipedia.org/wiki/Manifold)?

In the case of a _random_ paging scheme, you age off each entry
[stochastically](http://en.wikipedia.org/wiki/Stochastic_process).
Purportedly, this should give us some form of a manifold bound to the entropy
and size of our working set... right?

Or should it? For each set of entries, you randomly assign a subset to page
out as a function of time. This should give relatively even paging
performance, regardless of stability and regardless of your working set, as
long as your access profile is again uniformly random.

So, based on the conditions you are checking, this is entirely correct
behavior [consistent with what we'd
expect](http://en.wikipedia.org/wiki/Page_replacement_algorithm#Random). You
get an even paging performance that doesn't degrade with other factors (but,
conversely, isn't improved by them) that's suitable for high load, efficient
operation. Not bad, just not what you might intuitively expect.

So, in a nutshell, that's the breakdown as your project is currently
implemented.

As an exercise in further exploring the properties of these algorithms in the
context of different dispositions and distributions of input data, I highly
recommend digging into
[`scipy.stats`](http://docs.scipy.org/doc/scipy/reference/stats.html) to see
what, for example, a Gaussian or logistic distribution might do to each graph.
Then, I would come back to [the documented expectations of each
algorithm](http://en.wikipedia.org/wiki/Page_replacement_algorithm) and draft
cases where each is uniquely most and least appropriate.

All in all, I think your teacher will be proud. :)

