Question

Why will the standard replacement algorithms (LRU, FIFO, clock) not be effective in handling this workload for a page allocation that is less than the sequence length? (b) If this program were allocated 500 page frames, describe a page replacement approach that would perform much better than the LRU, FIFO, or clock algorithms.

Answer 1

Answer:

These algorithm keeps an eye on which page was used when. LRU assumes that the page that was recently used has more probability  

of being used or requested by the user. Thus, it keeps the pages that were recently used, when a new page is requested. If page  

fault occurs, the requested page is fetched and it replaces the page in cache which was last referenced earlier than any other page  

in the cache (or frame).The LRU associates a time with each page in the memory and the ones with the greatest value are replaced.  

It does not suffer from Belady’s anomaly. The page fault will be referred when 512 page frame are reached. This is the total length of the complete sequence.

FIFO replaces pages that come in cache firstly. FIFO stands for First in first out.  

(b) The FIFO replacement algorithm replaces the page which was first brought into the memory followed by the next and soon.  

This algorithm suffers from Belady’s anomaly. In First In First out (FIFO) page replacement scheme of page replacement, the requests  

are executed as they are received. When a new request is made of a page which is not available in the existing frames, then the requested  

page is acquired from the memory. The page in the first frame is replaced by the requested page. If again a request is made of a page not  

yet available in the frames, it is fetched from the memory and it replaces the second frame's page, and so on.  

There are total 500 frames given. The alternative approach which is better than clock algorithm, FIFO, and LRU is that the pages  

from 0 to 498 are set to the fixed frames. Thus, 499 frames are fixed and only one frame can vary.

Explanation: