LRU Page Replacement Algorithm in Java
LRU Page Replacement Algorithm in Java
In memory management, page replacement algorithms play a very vital part of keeping the main memory filled with fresh pages. One of the algorithms called Least Recently Used (LRU) page replacement algorithm works on the concept that it replaces those pages first which are the oldest and have been least referred.
On this page,you will find LRU Page Replacement Algorithm in Java in detail.
LRU Page Replacement Algorithm in Java
To implement this, a counter called an “age bit” is maintained, which keeps track of which page is to be referred and when it is to be referred. It ensures that the page which was least recently used is discarded to make space for the new page. When the page requested by the user is not present in the RAM, then a page fault occurs. When the page requested by the user is already present in the RAM, then page hit occurs.
Let us understand LRU Algorithm in Java with an example.
LRU Program in Java (Method-1)
import java.util.Arrays; public class Main { static boolean checkHit(int incomingPage, int[] queue, int occupied) { for (int i = 0; i < occupied; i++) { if (incomingPage == queue[i]) return true; } return false; } static void printFrame(int[] queue, int occupied) { for (int i = 0; i < occupied; i++) System.out.print(queue[i] + "\t\t\t"); } public static void main(String[] args) { int[] incomingStream = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3}; int n = incomingStream.length; int frames = 3; int[] queue = new int[frames]; int[] distance = new int[frames]; int occupied = 0; int pagefault = 0; System.out.println("Page\t Frame1 \t Frame2 \t Frame3"); for (int i = 0; i < n; i++) { System.out.print(incomingStream[i] + ": \t\t"); if (checkHit(incomingStream[i], queue, occupied)) { printFrame(queue, occupied); } else if (occupied < frames) { queue[occupied] = incomingStream[i]; pagefault++; occupied++; printFrame(queue, occupied); } else { int max = Integer.MIN_VALUE; int index = -1; for (int j = 0; j < frames; j++) { distance[j] = 0; for (int k = i - 1; k >= 0; k--) { ++distance[j]; if (queue[j] == incomingStream[k]) break; } if (distance[j] > max) { max = distance[j]; index = j; } } queue[index] = incomingStream[i]; printFrame(queue, occupied); pagefault++; } System.out.println(); } System.out.println("Page Fault: " + pagefault); } }
Output
Page Frame1 Frame2 Frame3 1: 1 2: 1 2 3: 1 2 3 2: 1 2 3 1: 1 2 3 5: 1 2 5 2: 1 2 5 1: 1 2 5 6: 1 2 6 2: 1 2 6 5: 5 2 6 6: 5 2 6 3: 5 3 6 1: 1 3 6 3: 1 3 6 Page Fault: 8
LRU Program in Java (Method-2)
import java.util.Arrays; public class Main { public static void main(String[] args) { int m, n, position = 0, k, l; int a = 0, b = 0, page_fault = 0; int total_frames = 3; int[] frames = new int[total_frames]; int[] temp = new int[total_frames]; int[] pages = { 1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3, 6, 1, 2, 4, 3 }; int total_pages = pages.length; Arrays.fill(frames, -1); for (n = 0; n < total_pages; n++) { System.out.print(pages[n] + ": "); a = 0; b = 0; for (m = 0; m < total_frames; m++) { if (frames[m] == pages[n]) { a = 1; b = 1; break; } } if (a == 0) { for (m = 0; m < total_frames; m++) { if (frames[m] == -1) { frames[m] = pages[n]; b = 1; page_fault++; break; } } } if (b == 0) { Arrays.fill(temp, 0); for (k = n - 1, l = 1; l <= total_frames - 1; l++, k--) { for (m = 0; m < total_frames; m++) { if (frames[m] == pages[k]) { temp[m] = 1; } } } for (m = 0; m < total_frames; m++) { if (temp[m] == 0) position = m; } frames[position] = pages[n]; page_fault++; } for (m = 0; m < total_frames; m++) { System.out.print(frames[m] + "\t"); } System.out.println(); } System.out.println("\nTotal Number of Page Faults:\t" + page_fault); } }
Output
1: 1 -1 -1 2: 1 2 -1 3: 1 2 3 2: 1 2 3 1: 1 2 3 5: 1 2 5 2: 1 2 5 1: 1 2 5 6: 1 2 6 2: 1 2 6 5: 5 2 6 6: 5 2 6 3: 5 3 6 1: 1 3 6 3: 1 3 6 6: 1 3 6 1: 1 3 6 2: 1 2 6 4: 1 2 4 3: 3 2 4 Total Number of Page Faults: 11
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Read More
- Memory Management Introduction
- Partition Allocation Method
- Buddy- System Allocator
- Paging
- Types of Paging
- Fragmentation
- Mapping Virtual address to Physical Address.
- Virtual Memory
- Demand Paging
- Implementation of Demand paging and page fault
- Segmentation
- Page Replacement Algorithms
- Thrashing
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Swapping
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging
Login/Signup to comment