LRU Page Replacement Algorithm in C
Least Recently Used (LRU) Algorithm
The operating system uses a set of instructions to execute different programs. These instructions are present in blocks of data called pages. The operating system uses these pages to fetch data and instructions.
In most of the cases, it is said that pages that have been heavily used during information processing, will again be used in the next few instructions.So, in this section we will learn about the LRU Page replacement algorithm in C in detail.
LRU Page Replacement Algorithm in C
In this algorithm, we replace the element which is the current least recently used element in the current stack.
That is, when we look to the left of the table, that we have created we choose the further most page to get replaced.
LRU Program in C (Method 1 : Better)
#include<stdio.h> #include<limits.h> int checkHit(int incomingPage, int queue[], int occupied){ for(int i = 0; i < occupied; i++){ if(incomingPage == queue[i]) return 1; } return 0; } void printFrame(int queue[], int occupied) { for(int i = 0; i < occupied; i++) printf("%d\t\t\t",queue[i]); } int main() { // int incomingStream[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1}; // int incomingStream[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3, 6, 1, 2, 4, 3}; int incomingStream[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3}; int n = sizeof(incomingStream)/sizeof(incomingStream[0]); int frames = 3; int queue[n]; int distance[n]; int occupied = 0; int pagefault = 0; printf("Page\t Frame1 \t Frame2 \t Frame3\n"); for(int i = 0;i < n; i++) { printf("%d: \t\t",incomingStream[i]); // what if currently in frame 7 // next item that appears also 7 // didnt write condition for HIT if(checkHit(incomingStream[i], queue, occupied)){ printFrame(queue, occupied); } // filling when frame(s) is/are empty else if(occupied < frames){ queue[occupied] = incomingStream[i]; pagefault++; occupied++; printFrame(queue, occupied); } else{ int max = INT_MIN; int index; // get LRU distance for each item in frame for (int j = 0; j < frames; j++) { distance[j] = 0; // traverse in reverse direction to find // at what distance frame item occurred last for(int k = i - 1; k >= 0; k--) { ++distance[j]; if(queue[j] == incomingStream[k]) break; } // find frame item with max distance for LRU // also notes the index of frame item in queue // which appears furthest(max distance) if(distance[j] > max){ max = distance[j]; index = j; } } queue[index] = incomingStream[i]; printFrame(queue, occupied); pagefault++; } printf("\n"); } printf("Page Fault: %d",pagefault); return 0; }
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
LRU program in C (Method 2)
#include<stdio.h> int main() { int m, n, position, k, l; int a = 0, b = 0, page_fault = 0; int total_frames = 3; int frames[total_frames]; int temp[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 = sizeof(pages)/sizeof(pages[0]); for(m = 0; m < total_frames; m++){ frames[m] = -1; } for(n = 0; n < total_pages; n++) { printf("%d: ", 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) { for(m = 0; m < total_frames; m++) { temp[m] = 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++) { printf("%d\t", frames[m]); } printf("\n"); } printf("\nTotal Number of Page Faults:\t%d\n", page_fault); return 0; }
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
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