Program for Least Recently Used ( LRU ) Page Replacement algorithm | C ++ implementation of above algorithm ; Function 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 ; insert the current page ; Increment page faults ; Update the current page index ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int pageFaults ( int pages [ ] , int n , int capacity ) { unordered_set < int > s ; unordered_map < int , int > indexes ; int page_faults = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . size ( ) < capacity ) { if ( s . find ( pages [ i ] ) == s . end ( ) ) { s . insert ( pages [ i ] ) ; page_faults ++ ; } indexes [ pages [ i ] ] = i ; } else { if ( s . find ( pages [ i ] ) == s . end ( ) ) { int lru = INT_MAX , val ; for ( auto it = s . begin ( ) ; it != s . end ( ) ; it ++ ) { if ( indexes [ * it ] < lru ) { lru = indexes [ * it ] ; val = * it ; } } s . erase ( val ) ; s . insert ( pages [ i ] ) ; page_faults ++ ; } indexes [ pages [ i ] ] = i ; } } return page_faults ; } int main ( ) { int pages [ ] = { 7 , 0 , 1 , 2 , 0 , 3 , 0 , 4 , 2 , 3 , 0 , 3 , 2 } ; int n = sizeof ( pages ) / sizeof ( pages [ 0 ] ) ; int capacity = 4 ; cout << pageFaults ( pages , n , capacity ) ; return 0 ; }