Dark Mode

3,367 views

8 votes

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 _____________.

$$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 _____________.

4 votes

Best answer

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 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$

2 votes

GIVEN page reference string

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

2 votes

$\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)}$