Problem 4 - LRU Paging

Let $F(m)$ be the number of page faults in executing a page request sequence $R$ using $m$ pages $(m\geq 1)$ in main memory. Suppose that initially there is no page in the main memory, and only demand paging is performed. Answer the following questions.

1.

Suppose that LRU (Least Recently Used) is used for a page replacement algorithm. In requesting each page, sort the pages requested so far in the order of most recently requested ones, and count the number of times such that the requested page is in the $i$th position from the top of the list. Let $c(i)$ be the number of counts over all $R$. Show a formula to compute $F(m)$ using $c(i)$ and the length $r$ of $R$.

2.

For the following page request sequence

$$R=023102402314$$

for each $m$, find the value of $F(m)$ when the LRU algorithm is used, and find the minumun value of $F(m)$ when any algorithm is used for page replacements. Use case analysis in respect of $m$.

3.

Concerning the FIFO replacement algorithm, show that $F(m)<F(m+1)$ holds for some $m$ using the sequence in 2.

1.

$$F(m) = r - \sum_{k=0}^{m}c(k)$$

Indeed, we can suppose that you have a page fault for every reference made to the memory, minus all the times we have referenced a page that was already at the position of one of the $m$ physical pages.

2.

We have the following succession of memory states with LRU. A memory state is a stack on the top of which the least recently referenced page is put.

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...& 1 & 1 & 4 & 0 & 2 \\ & & & & & & & 3 & 3 & 3 & 1 & 4 & 0 \\ \end{tabular}$$

Thanks to the table above, we determine the number of page faults when using different number of frames.

$$\begin{tabular}{c\vert c\vert c} number of frames & LRU & Minimum... ...\ $m=3$ & 10 & 7 \\ $m=4$ & 8 & 6 \\ $m\geq 5$ & 5 & 5 \\ \end{tabular}$$

An optimal algorithm states that the page that should be replaced is the one that will not be used for the longest period of time.

For $m=2$:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...4 & 4 & 4 \\ & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 3 & 1 & 1 \\ \end{tabular}$$

For $m=3$:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...& 3 & 3 & 3 \\ & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{tabular}$$

For $m=4$:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...& 3 & 3 & 3 \\ & & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{tabular}$$

For $m\geq 5$:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...& 0 & 0 & 0 & 0 & 0 \\ & & & & & & & 4 & 4 & 4 & 4 & 4 & 4 \\ \end{tabular}$$

3.

FIFO (First In First Out) is the simplest page-replacement algorithm. When a page must be replaced, the oldest page in the queue is chosen. When a page must be brought, it is inserted at the tail of the queue.

For $m=3$:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...& 4 & 3 & 3 \\ & & & 0 & 2 & 3 & 1 & 0 & 0 & 0 & 2 & 4 & 4 \\ \end{tabular}$$

That is, $F(m)=9$

For m=4:

$$\begin{tabular}{c\vert c\vert c\vert c\vert c\vert c\vert c\vert ... ...4 & 0 & 2 & 3 \\ & & & & 0 & 0 & 0 & 2 & 3 & 1 & 4 & 0 & 2 \\ \end{tabular}$$

That is, $F(m)=10$.

Intuitively it seems that the more page frames the memory has, the fewer page faults a program will get. But this not always the case. This is the Belady's anomaly.