am i right ??

19 votes

Assume that there are $3$ page frames which are initially empty. If the page reference string is $\text{1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6}$ the number of page faults using the optimal replacement policy is__________.

5 votes

Best answer

In Optimal page replacement a page which will be farthest accessed in future will be replaced first.

Here, we have $3$ page frames. Since, initially they are empty the first $3$ distinct page references will cause page faults.

After $3$ distinct page accesses we have $:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&3\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&1&3\\\hline\end{array}}.$

Based on the Next Use Order, the next replacement will be $3.$ Proceeding like this we get

$\overset{\text{Request}}{\boxed{4}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&1&4\\\hline\end{array}} - \text{Miss}.$

$\overset{\text{Request}}{\boxed{2}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&1&4\\\hline\end{array}} - \text{Hit}.$

$\overset{\text{Request}}{\boxed{1}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&4&1\\\hline\end{array}} - \text{Hit}.$

$\overset{\text{Request}}{\boxed{5}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline5&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&4&5\\\hline\end{array}} - \text{Miss}.$

$\overset{\text{Request}}{\boxed{3}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline3&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&4&3\\\hline\end{array}} - \text{Miss}.$

$\overset{\text{Request}}{\boxed{2}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline3&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline4&3&2\\\hline\end{array}} - \text{Hit}.$

$\overset{\text{Request}}{\boxed{4}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&4\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline4&3&2\\\hline\end{array}} - \text{Hit}.$

$\overset{\text{Request}}{\boxed{6}}:\overset{\text{Page Frames}}{\begin{array}{|c|c|c|}\hline1&2&6\\\hline\end{array}}\qquad \overset{\text{Next Use Order}}{\begin{array}{|c|c|c|}\hline2&1&6\\\hline\end{array}} - \text{Miss}.$

(When multiple pages are not going to be accessed again in future, replacing **any **of them is allowed in Optimal page replacement algorithm)

Now, counting the misses which includes the $3$ initial ones we get number of page faults as $3+4 = 7.$

Correct Answer: $7.$

23 votes

**Answer : initially all empty frames fill by $\mathbf{1,2,3}$ so all time page fault which is $\mathbf{3}$ .**

Then next $4$ was not available in frame set so, **we look at ahead of request which was coming last **we replace $4$ with that so, $3$ will be replace by $4$ and like wise next $2$ and $1$ is present already, so no. page fault and then next $5$ is not present so, replace with $1$ and then $3$ was not present and replace with $5$ and then $2$ and $4$ are present already so no page fault and then last $6^{th}$ was not already there so, page fault.

**So, total page fault at : $\mathbf{1 , 2 , 3 , 4 , 5 , 3 , 6}$ . so, total $\mathbf{7}$ page fault occur ... **

6 votes

In optimal page replacement replacement policy, we replace the place which is not used for longest duration in future.

Given three page frames.

Reference string is **1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6**

Initially, there are three page faults and entries are

1 2 3

Page 4 causes a page fault and replaces 3 (3 is the longest

distant in future), entries become

1 2 4

Total page faults = 3+1 = 4

Pages 2 and 1 don't cause any fault.

5 causes a page fault and replaces 1, entries become

5 2 4

Total page faults = 4 + 1 = 5

3 causes a page fault and replaces 1, entries become

3 2 4

Total page faults = 5 + 1 = 6

3, 2 and 4 don't cause any page fault.

6 causes a page fault.

Total page faults = 6 + 1 = 7