Question

Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string: \[ 7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 1, 5, 6, 1 \] The page fault rate, defined as the ratio of the number of page faults to the number of memory accesses (rounded off to one decimal place) is \(\underline{\hspace{1cm}}\).

Hint:

The page fault rate can be minimized using the LRU algorithm, which replaces the least recently used page in the memory.

Answer 1

Correct Answer: 0.6

To calculate the page fault rate, we first simulate the LRU page replacement algorithm for the given page reference string. The initial state of the page frames is empty. The page references and the corresponding page frames are as follows (denoted as the page frames in square brackets): \[ \begin{array}{|c|c|} \hline \text{Page Reference} & \text{Page Frames} \\ \hline 7 & [7] \, (\text{Page fault}) \\ 2 & [7, 2] \, (\text{Page fault}) \\ 7 & [7, 2] \, (\text{No page fault}) \\ 3 & [7, 2, 3] \, (\text{Page fault}) \\ 2 & [7, 2, 3] \, (\text{No page fault}) \\ 5 & [7, 2, 3, 5] \, (\text{Page fault}) \\ 3 & [7, 2, 3, 5] \, (\text{No page fault}) \\ 4 & [2, 3, 5, 4] \, (\text{Page fault}) \\ 6 & [3, 5, 4, 6] \, (\text{Page fault}) \\ 7 & [5, 4, 6, 7] \, (\text{Page fault}) \\ 1 & [4, 6, 7, 1] \, (\text{Page fault}) \\ 5 & [4, 6, 7, 1] \, (\text{No page fault}) \\ 6 & [4, 7, 1, 6] \, (\text{No page fault}) \\ 1 & [4, 7, 1, 6] \, (\text{No page fault}) \\ \hline \end{array} \] We have 10 page faults out of 14 memory accesses. The page fault rate is given by the formula: \[ \text{Page Fault Rate} = \frac{\text{Number of page faults}}{\text{Number of memory accesses}} = \frac{10}{14} \approx 0.6. \] Thus, the page fault rate is: \[ \boxed{0.6}. \]