# GATE2007-82

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$

edited

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.

edited by
1
for page 1 2 3 7 4 5 6
2
0
Kindly correct your typo mam... it should be 7 at place of 6 at 4th position
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.

 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)

## Related questions

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