LRU Page Replacement Program in C++[How to]

Least Recently Used  Page Replacement

Goal:- Program for LRU page replacement Method.

Method:-  Replace the page that has not been used for the longest period of time.

Explanation:- As we seen in FIFO page Replacement Algorithm the problem is Belady's Anomaly and this lead us to discovery of an Optimal Page Replacement method that will have minimum page fault rate.But the problem in Optimal Page Replacement is that it requires the future knowledge. So in the place of optimal we can take a approximation of optimal in which we look for the pages that has not been used for a long time and predict that they will not be used in near future.

So whenever a replacement request comes then we replace the new page with the page which has not been used for a long time and this method page replacement is known as Least Recently used(LRU) method.

For evaluating an algorithm we take a particular string of memory references ,called reference string.

The LRU method is often used and considered to be good.

The problem with this algorithm that how to implement LRU and there are several methods of implementing LRU. To know you can check my post(about to come).

Page Fault:-  Page Fault is a interrput that occurs when a program request page that is not in real memory.Then this interrput sends signal to OS to fetch that page from Virtual memory and load it into RAM.

**Program explained here counts the no. of page fault occurs  when a input reference string is implemented onto Memory according to LRU replacement method.

Example:-

               Reference string- 7,0,1,2,0,3,0,4

                 No. of frames: 3

Frame NO.	Reference String(Page Values)
	Initially	7	0	1	2	0	3	0	4
1	-1	7	7	7	2	2	2	2	4
2	-1	-1	0	0	0	0	0	0	0
3	-1	-1	-1	1	1	1	3	3	3

When any page value already presented in frames then no page fault will occur.

Program:-

Output:-

If you want to share more information about topic discussed above or find anything incorrect Please do comments.  

For more Programs Stay Connected..Like us on Facebook.