The Gateway to Computer Science Excellence
+13 votes
1.2k views

The following page addresses, in the given sequence, were generated by a program:

$\text{1 2 3 4 1 3 5 2 1 5 4 3 2 3}$

This program is run on a demand paged virtual memory system, with main memory size equal to $4$ pages. Indicate the page references for which page faults occur for the following page replacement algorithms.

  1. LRU
  2. FIFO

Assume that the main memory is initially empty

in Operating System by
edited by | 1.2k views

2 Answers

+15 votes
Best answer
LRU :  $1,2,3,4,5,2,4,3,2$
FIFO : $1,2,3,4,5,1,2,3$
by
edited by
+11

Also the number of page faults:

LRU: 9

FIFO: 8

+3
$(A)LRU:$ miss rate$=\dfrac{9}{14}$

$(B)FIFO:$ miss rate$=\dfrac{8}{14}$
+1 vote

LRU=9

1 2 3 4 1 3 5 2 1 5 4 3 2 3
      4 4 4 4 2 2 2 2 3 3 3
    3 3 3 3 3 3 3 3 4 4 4 4
  2 2 2 2 2 5 5 5 5 5 5 5 5
1 1 1 1 1 1 1 1 1 1 1 1 2 2
F F F F     F F     F F F  

FIFO=8

1 2 3 4 1 3 5 2 1 5 4 3 2 3
      4 4 4 4 4 4 4 4 4 4 3
    3 3 3 3 3 3 3 3 3 3 2 2
  2 2 2 2 2 2 2 1 1 1 1 1 1
1 1 1 1 1 1 5 5 5 5 5 5 5 5
F F F F     F   F       F F

 

by
0

@Kushagra गुप्ता Do we always count page faults right from the beginning or should we start counting once main memory frames are full?
PS: The snapshot is from William Stallings, page-369
 

+1
Difficult for me to comment anything on that as I am not sure. But if we go through PY questions on page replacement and follow the approach given in my answer we end up getting the right answer.

I suggest that you might have started solving questions and if you find another question do apply both approach and see which is giving the right answer. And if you found that my approach is wrong do inform me. Thanks.

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
52,375 questions
60,615 answers
202,051 comments
95,433 users