The Gateway to Computer Science Excellence
0 votes
2.6k views

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) :

  1. $9$ and $6$
  2. $10$ and $7$ 
  3. $9$ and $7$
  4. $10$ and $6$ 
in Operating System by Boss (30.2k points) | 2.6k views

3 Answers

+1 vote
Best answer

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.

by Boss (41k points)
edited by
+1 vote

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

by Junior (951 points)
0 votes

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

by Active (1.9k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,696 users