in Operating System
407 views
5 votes
5 votes

Which of the following page replacement schemes is the toughest to implement from a hardware point of view?

  1. LRU
  2. FIFO
  3. MRU
  4. All have equal complexity
in Operating System
by
407 views

1 Answer

9 votes
9 votes
Best answer
Answer is - A) LRU.

For LRU, we need to keep track of the usage information of all the live pages. This is not so easy and hence pseudo-LRU schemes are quite common.

For FIFO, we need a queue to store the live pages to be replaced.

For MRU, we just need a variable which should be updated on every new page reference.
selected by

4 Comments

Is optimal page replacement more complexity than LRU ?
0
0

Optimal is very tough to implement, because it requires future knowledge of what pages will be accessed and which page to replace in case of page fault. But, Similarly, LRU is also tough hence we go for PLRU.

https://en.wikipedia.org/wiki/Pseudo-LRU

1
1
LRU can be implemented using Queue as given below :

Maintain queue as given below, which stores page numbers.

When a new page request arrives,

i) if it is already in queue then bring page number to front.

ii) If not in queue then remove page number from end of queue and insert new in front.

with such approach LRU hardware will do more work or same as FIFO's ?
1
1

Take a array ( size = no.of pages that main memory accommodate )

each element of the array is time stamp that when it is updated.

if you are using LRU then 

1. when hit then timestamp also update 

2. Which index of the array have the least Timestamp corresponding Page updated..

if you are using FIFO then 

1. when hit then timestamp not updated 

2. Which index of the array have the least Timestamp corresponding Page updated..

if you are using MRU then 

1. when hit then timestamp also update 

2. Which index of the array have the Highest Timestamp corresponding Page updated..

0
0
Answer:

Related questions