search
Log In
15 votes
3.3k views

A process has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $\mathbf{1, 2, 1, 3, 7, 4, 5, 6, 3, 1}$

If optimal page replacement policy is used, how many page faults occur for the above reference string?

  1. $7$
  2. $8$
  3. $9$
  4. $10$
in Operating System
edited by
3.3k views

5 Answers

16 votes
 
Best answer

Optimal replacement policy means a page which is "farthest" in the future to be accessed will be replaced next.

$$\require{cancel}\begin{array}{c|c}\hline
\text{Frame 0}&1\\\hline
\text{Frame 1}&\cancel{2} \quad\cancel7\quad \cancel4 \quad \cancel5 \quad 6\\\hline
\text{Frame 2}&3\\ \hline
\end{array}$$

$3$ initial page faults for pages $1,2,3$ and then for pages $7,4,5,6 \implies 7$ page faults occur.

Answer is (A).


edited by
1
for page 1 2 3 7 4 5 6
2
Please write clearly. total 7 page faults and answer is A.
0
Kindly correct your typo mam... it should be 7 at place of 6 at 4th position
5 votes
1 2 1 3 7 4 5 6 3 1

In optimal scheduling we schedule page in place of that page which is not used for scheduling in future .........

If initially memory is empty so 3 page faults

1,2 , (1) ,3 so initially 3 pages are there now - 3 faults

7 in place of (2) because 2 is not in future - 1 fault

4 in place of 7 - 1 fault

5 in place of 4 - 1 fault

6 in place of 5 - 1 fault

so total faults = 3+1+1+1+1 = 7

so option A
1 vote

Initially, Page fault Count =0

     

After first 3 pages ,i.e 1,2,1 Page Fault count=2.

1 2  

After 4 pages i.e 1,2,1,3 Page Fault count =3.

1 2 3

After 5 pages i.e.1,2,1,3,7 ,we have to replace one page out 3 from above situation ,candidate for page replacement is 1,2,3 we choose page No.2 .reason=we use optimal page replacement ,so we see the future reference of page and came to conclusion that  page No=2  have No reference in future or if they have reference in future ,which is late bit as compare to page no.1 and 3 .

Page fault count=4

1 7 3

 After 6 pages i.e.1,2,1,3,7,4. we choose page 7 for replacement with same logic as above. Page Fault Count =5

1 4 3

After 7 pages i.e.1,2,1,3,7,4,5 we choose page 4 for replacement.Page Fault count=6

1 5 3

 After 8 pages i.e.1,2,1,3,7,4,5,6 .we choose page 5 for replacement.page fault count=7

1 6 3

After 10 pages i.e.1,2,1,3,7,4,5,6,3,3. page No=3 and page No=3 already present so no page fault hence page fault count=7.

Answer 7

0 votes
1 2 1 3 7 4 5 6 3 1
      3 3 3 3 3 3 3
  2 2 2 7 4 5 6 6 6
1 1 1 1 1 1 1 1 1 1
F F $\times$ F F F F F $\times$ $\times$

$Ans:$ 7 faults

–1 vote
82. A)
Answer:

Related questions

15 votes
4 answers
1
2.5k views
A process, has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $1, 2, 1, 3, 7, 4, 5, 6, 3, 1$ Least Recently Used ... the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy? $0$ $1$ $2$ $3$
asked Apr 23, 2016 in Operating System jothee 2.5k views
27 votes
3 answers
2
6.7k views
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Q: Some programs do not ... and Q are true, but Q is not the reason for P. P is false but Q is true Both P and Q are false.
asked Sep 22, 2014 in Operating System Kathleen 6.7k views
34 votes
7 answers
3
8.5k views
Two processes, $P1$ and $P2$, need to access a critical section of code. Consider the following synchronization construct used by the processes: /* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ ... ensure bounded waiting. It requires that processes enter the critical section in strict alteration. It does not prevent deadlocks, but ensures mutual exclusion.
asked Sep 22, 2014 in Operating System Kathleen 8.5k views
15 votes
1 answer
4
3.7k views
A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column ... $P0$ $P1$ $P2$ None of the above, since the system is in a deadlock
asked Sep 22, 2014 in Operating System Kathleen 3.7k views
...