Educative Site Free Online Academic Courses Tutorials, Books with enough questions and answers
Least Recently Used LRU Page Replacement Algorithm in C and C++ Program Code .
C++ Program Code:
|
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 |
#include<bits/stdc++.h> using namespace std; const int N=100005; int n; int frame_size; int pages[N]; void lru_page_replacement() { unordered_set<int> s; unordered_map<int, int> indexes; int page_faults = 0; for (int i=0; i<n; i++) { if(s.find(pages[i])!=s.end()) { cout<<"Reference to page "<<pages[i]<<" did not cause a page fault\n"; } else { if (s.size() < frame_size) { s.insert(pages[i]); page_faults++; } else { int lru = INT_MAX, val; for (auto it : s) { if (indexes[it] < lru) { lru = indexes[it]; val = it; } } s.erase(val); s.insert(pages[i]); page_faults++; } cout<<"Reference to page "<<pages[i]<<" caused a page fault\n"; } indexes[pages[i]] = i; } cout<<"\nTotal Page Faults: "<<page_faults; } int main() { cout<<"Number of Frames: "; cin>>frame_size; cout<<"Page Reference Stream Length: "; cin>>n; cout<<"Page Reference Stream:\n"; for(int i=0; i<n; i++) cin>>pages[i]; lru_page_replacement(); return 0; } |
C Program Code:
|
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 |
#include<stdio.h> 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; } 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("\n\nTotal Page Faults = %d", faults); return 0; } /* Output Enter number of frames: 3 Enter number of pages: 6 Enter reference string: 5 7 5 6 7 3 5 -1 -1 5 7 -1 5 7 -1 5 7 6 5 7 6 3 7 6 Total Page Faults = 4 */ |