UGC NET CSE | June 2014 | Part 3 | Question: 35

Question

Consider a program that consists of $8$ pages (from $0$ to $7$) and we have $4$ page frames in the physical memory for the pages. The page reference string is :

$1\; 2\; 3\; 2\; 5\; 6\; 3\; 4\; 6\; 3\; 7\; 3\; 1\; 5\; 3\; 6\; 3\; 4\; 2\; 4\; 3\; 4\; 5\; 1$ 

The number of page faults in LRU and optimal page replacement algorithms are respectively (without including initial page faults to fill available page frames with pages) :

• A. $9$ and $6$
• B. $10$ and $7$ 
• C. $9$ and $7$
• D. $10$ and $6$ 

Answer 1

LRU Page Replacement:-

1

2

3

2

5

6

3

4

6

3

7

3

1

5

3

6

3

4

2

4

3

4

5

1

				5	5	5	5	5	5	7	7	7	7	7	6	6	6	6	6	6	6	5	5
		3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
	2	2	2	2	2	2	4	4	4	4	4	1	1	1	1	1	4	4	4	4	4	4	4
1	1	1	1	1	6	6	6	6	6	6	6	6	5	5	5	5	5	2	2	2	2	2	1
					F		F			F		F	F		F		F	F				F	F

Number of Page Fault = 10

Optimal Page Replacement :- 

1

2

3

2

5

6

3

4

6

3

7

3

1

5

3

6

3

4

2

4

3

4

5

1

				5	5	5	4	4	4	7	7	7	5	5	5	5	5	5	5	5	5	5	1
		3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
	2	2	2	2	6	6	6	6	6	6	6	6	6	6	6	6	4	4	4	4	4	4	4
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	2	2	2	2	2
					F		F			F			F				F	F					F

Number of Page Fault = 7

Hence,Option(B)10 and 7 is the correct choice.

Answer 2

In LRU : it will replace the page which is least recently used 

1     2     3   2.   5  6 (r) 3   4(r)  6   3   7(r)  3 1(r)  5r 3   6(r)  3  4r     2r     4  3      5R 1R

				5	5	5	5	5	5	7	7	7	7	7	6	6	6	6	6	6. 6	5	1
		3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3. 3	3	3
	2	2	2	2	2	2	4	4	4	4	4	1	1	1	1	1	4	4	4	4. 4	4	4
1	1	1	1	1	6	6	6	6	6	6	6	6	5	5	5	5	5	2	2	2.  2	2	2

Therefore total replacement at LRU I s 10

optimal page replacement: Replace the page which is not used for longest duration of time in future

no of page fault occur : 7

b option

Answer 3

LRU 

no of page faults(without including initial page faults to fill available page frames with pages) is 10

Optimal Page replacement

no of page faults(without including initial page faults to fill available page frames with pages) is 7

Hence option is B