search
Log In
19 votes
2.3k views
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__________.
in Operating System
edited by
2.3k views

4 Answers

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


edited by
0
after processing the requests completly page reference 3,6,4 are present in main memory.
  am i right ??
0

@ saurabh rai  3,6,4 or 6,2,4?

2
6,2,4 are in memory @jagmeet
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

0 votes
In optimal we go into the future and see which page will not be referred for the longest time.

we will get 7 page faults
Answer:

Related questions

15 votes
2 answers
1
2.4k views
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds. ... Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ____________________.
asked Sep 26, 2014 in Operating System jothee 2.4k views
27 votes
3 answers
2
4.1k views
Suppose a disk has $201$ cylinders, numbered from $0$ to $200$. At some time the disk arm is at cylinder $100$, and there is a queue of disk access requests for cylinders $30, 85, 90, 100, 105, 110, 135$ and $145$. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder $90$ is serviced after servicing ____________ number of requests.
asked Sep 26, 2014 in Operating System jothee 4.1k views
16 votes
3 answers
3
2k views
A system uses $3$ page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? $\text{4, 7, 6, 1, 7, 6, 1, 2, 7, 2}$
asked Sep 28, 2014 in Operating System jothee 2k views
33 votes
7 answers
4
7.7k views
Consider two processors $P_1$ and $P_2$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $P_2$ takes $\text{25%}$ less time but incurs $\text{20%}$ more CPI (clock cycles per instruction) as compared to the program ... $P_1$. If the clock frequency of $P_1$ is $\text{1GHZ}$, then the clock frequency of $P_2$ (in GHz) is ______.
asked Sep 28, 2014 in CO and Architecture jothee 7.7k views
...