Program for Least Recently Used ( LRU ) Page Replacement algorithm | C # implementation of above algorithm ; Method to find page faults using indexes ; To represent set of current pages . We use an unordered_set so that we quickly check if a page is present in set or not ; To store least recently used indexes of pages . ; Start from initial page ; Check if the set can hold more pages ; Insert it into set if not present already which represents page fault ; increment page fault ; Store the recently used index of each page ; If the set is full then need to perform lru i . e . remove the least recently used page and insert the current page ; Check if current page is not already present in the set ; Find the least recently used pages that is present in the set ; Remove the indexes page ; remove lru from hashmap ; insert the current page ; Increment page faults ; Update the current page index ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int pageFaults ( int [ ] pages , int n , int capacity ) { HashSet < int > s = new HashSet < int > ( capacity ) ; Dictionary < int , int > indexes = new Dictionary < int , int > ( ) ; int page_faults = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . Count < capacity ) { if ( ! s . Contains ( pages [ i ] ) ) { s . Add ( pages [ i ] ) ; page_faults ++ ; } if ( indexes . ContainsKey ( pages [ i ] ) ) indexes [ pages [ i ] ] = i ; else indexes . Add ( pages [ i ] , i ) ; } else { if ( ! s . Contains ( pages [ i ] ) ) { int lru = int . MaxValue , val = int . MinValue ; foreach ( int itr in s ) { int temp = itr ; if ( indexes [ temp ] < lru ) { lru = indexes [ temp ] ; val = temp ; } } s . Remove ( val ) ; indexes . Remove ( val ) ; s . Add ( pages [ i ] ) ; page_faults ++ ; } if ( indexes . ContainsKey ( pages [ i ] ) ) indexes [ pages [ i ] ] = i ; else indexes . Add ( pages [ i ] , i ) ; } } return page_faults ; } public static void Main ( String [ ] args ) { int [ ] pages = { 7 , 0 , 1 , 2 , 0 , 3 , 0 , 4 , 2 , 3 , 0 , 3 , 2 } ; int capacity = 4 ; Console . WriteLine ( pageFaults ( pages , pages . Length , capacity ) ) ; } }