In this tutorial, we will look at C program for LRU Page Replacement Algorithm.
Least Recently Used (LRU) Page Replacement algorithm
It is an algorithm whose concept is based on the pages used in an instruction. The pages that are vigorously utilized in past instruction are probably going to be utilized intensely in the next instruction and the pages with used less are likely to be used less in the future. When a new page refereed is not present in the memory, a page fault occurs.
Whenever a page fault occurs, the page that is least used is removed from the memory frames.
Let us see an implementation of lru page replacement in c.
C program to implement LRU page replacement algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | //C program for LRU replacement algorithm implementation #include <stdio.h> //user-defined function int findLRU(int time[], int n) { int i, minimum = time[0], pos = 0; for (i = 1; i < n; ++i) { if (time[i] < minimum) { minimum = time[i]; pos = i; } } return pos; } //main function int main() { int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10], flag1, flag2, i, j, pos, faults = 0; printf("Enter number of frames: "); scanf("%d", &no_of_frames); printf("Enter number of pages: "); scanf("%d", &no_of_pages); printf("Enter reference string: "); for (i = 0; i < no_of_pages; ++i) { scanf("%d", &pages[i]); } for (i = 0; i < no_of_frames; ++i) { frames[i] = -1; } for (i = 0; i < no_of_pages; ++i) { flag1 = flag2 = 0; for (j = 0; j < no_of_frames; ++j) { if (frames[j] == pages[i]) { counter++; time[j] = counter; flag1 = flag2 = 1; break; } } if (flag1 == 0) { for (j = 0; j < no_of_frames; ++j) { if (frames[j] == -1) { counter++; faults++; frames[j] = pages[i]; time[j] = counter; flag2 = 1; break; } } } if (flag2 == 0) { pos = findLRU(time, no_of_frames); counter++; faults++; frames[pos] = pages[i]; time[pos] = counter; } printf("\n"); for (j = 0; j < no_of_frames; ++j) { printf("%d\t", frames[j]); } } printf("\nTotal Page Faults = %d", faults); return 0; } |
Output:
