3,437 views
Consider a demand paging system with four page frames (initially empty) and $\text{LRU}$ page replacement policy. For the following page reference string

$$7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1$$

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses $\textit{(rounded off to one decimal place)}$ is _____________.

Reference string : 7,2,7,3,2,5,3,4,6,7,7,1,5,6,1

Given that 4 page Frames and LRU page replacement policy.

Access 7 which leads Miss  --- 7, empty, empty, empty ------ Hits =0 , Miss = 1

Access 2 which leads Miss  --- 7, 2, empty, empty ------ Hits =0 , Miss = 2

Access 7 which leads Hit  --- 7, 2, empty, empty ------ Hits =1 , Miss = 2

Access 3 which leads Miss  --- 7, 2, 3, empty ------ Hits =1 , Miss = 3

Access 2 which leads Hit  --- 7, 2, 3, empty ------ Hits =2 , Miss = 3

Access 5 which leads Miss  --- 7, 2, 3, 5 ------ Hits =2 , Miss = 4

Access 3 which leads Hit  --- 7, 2, 3, 5 ------ Hits =3 , Miss = 4

Access 4 which leads Miss  --- 4, 2, 3, 5 ------ Hits =3 , Miss = 5 ( 7 is replaced with 4 by LRU algorithm )

Access 6 which leads Miss  --- 4, 6, 3, 5 ------ Hits =3 , Miss = 6 ( 2 is replaced with 6 by LRU algorithm )

Access 7 which leads Miss  --- 4, 6, 3, 7 ------ Hits =3 , Miss = 7 ( 5 is replaced with 7 by LRU algorithm )

Access 7 which leads Hit  --- 4, 6, 3, 7 ------ Hits =4 , Miss = 7

Access 1 which leads Miss  --- 4, 6, 1, 7 ------ Hits =4, Miss = 8 ( 3 is replaced with 1 by LRU algorithm )

Access 5 which leads Miss  --- 5, 6, 1, 7 ------ Hits =4 , Miss = 9 ( 4 is replaced with 5 by LRU algorithm )

Access 6 which leads Hit  ---  5, 6, 1, 7 ------ Hits =5 , Miss = 9

Access 1 which leads Hit  ---  5, 6, 1, 7 ------ Hits =6 , Miss = 9

$\therefore Pagefault\; rate = \frac{9}{15}=0.6$
GIVEN

page reference string 

## 7,2,7,3,2,5,3,4,6,7,7,1,5,6,1

given that four page frame in memory they are initially empty

page replacement policy =>LRU replace those page which is least Recent

 7 4 4 4 4 5 2 2 6 6 6 6 3 3 3 3 1 1 5 5 5 7 7 7

4M    1M    1M  1M   1M 1M

Total number of pagefault =4+1+1+1+1+1=9

pagefault rate = total number of PF/total references =9/15=0.6

$\underline{\mathbf{Answer: \mathbf{0.6}}}$

$\underline{\mathbf{Explanation: \mathbf{}}}$$\require{cancel}$ In $\textbf{ LRU (Least Recently Used)}$ algorithm, we can only replace the page which is $\color{red}{\textbf{Least}}$ recently used. That means, do not replace the page which is used recently or previously used.

$\underline{\textrm{ILLUSTRATION:}}$ We have pages in $\underline{order}$  $\mathbf{\;1, \;2, \; 3, 4}$, Now, let’s say a new page comes in, and we need to replace one page from all the four pages, therefore we can only replace $\mathbf 1$  first. This is because $\mathbf 1$ was used least recently, means pages $\mathbf{2, \;, 3\;, 4\;}$ pages are comparatively newer than $\mathbf 1$.

S.No. (Bottom to Top) Page Faults
$\mathbf{3^{rd}\;Frame}$ ${ \mathbf{\cancel{5}{7}}}$
$\mathbf{2^{nd}\;Frame}$ ${\mathbf{\cancel{3}{1}}}$
$\mathbf{1^{st}\;Frame}$ ${\mathbf{\cancel{2}{6}}}$ $\require{cancel}$
$\mathbf{0^{th}\; Frame}$ ${\mathbf{\cancel{7}{\cancel{4}}{5}}}$

So, the number of page faults $\mathbf{=9}$

Number of page hits $=\mathbf{=6}$

Total Memory accesses $\mathbf{=6+9 = 15}$

$\therefore$ Page fault rate $=\mathbf{\frac{9}{15}= 0.6}$

$\underline{\textbf{In more Detail}}$

$\mathbf{\color{red}{7(page fault)}, \color{red}{2(page fault)},7(page hit), \color{red}{3(page fault)}, 2(page hit), \color{red}{5(page fault)}, 3(page hit), \color{red}{4(page fault), 6(page fault), 7(page fault)}, 7 (page hit), \color{red}{1 (page fault)}, \color{red}{5 (page fault)}, 6 (page hit), 1(page hit)}$

by