Program for Least Recently Used ( LRU ) Page Replacement algorithm | Java 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 method
import java . util . HashMap ; import java . util . HashSet ; import java . util . Iterator ; class Test { static int pageFaults ( int pages [ ] , int n , int capacity ) { HashSet < Integer > s = new HashSet < > ( capacity ) ; HashMap < Integer , Integer > indexes = new HashMap < > ( ) ; int page_faults = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s . size ( ) < capacity ) { if ( ! s . contains ( pages [ i ] ) ) { s . add ( pages [ i ] ) ; page_faults ++ ; } indexes . put ( pages [ i ] , i ) ; } else { if ( ! s . contains ( pages [ i ] ) ) { int lru = Integer . MAX_VALUE , val = Integer . MIN_VALUE ; Iterator < Integer > itr = s . iterator ( ) ; while ( itr . hasNext ( ) ) { int temp = itr . next ( ) ; if ( indexes . get ( temp ) < lru ) { lru = indexes . get ( temp ) ; val = temp ; } } s . remove ( val ) ; indexes . remove ( val ) ; s . add ( pages [ i ] ) ; page_faults ++ ; } indexes . put ( 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 ; System . out . println ( pageFaults ( pages , pages . length , capacity ) ) ; } }