LRU Page Replacement Algorithm - C Program

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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151

/** * LRU (Least Recently Used) Page Replacement Algorithm - C program * @author Mangilal Sharma * Initial Edit: November 27, 2011 for OS lab * Last Modified: October 28, 2016 for http://world-of-c-programming.blogspot.in/ * * Description: * A page, memory page, or virtual page is a fixed-length contiguous block of virtual memory. * A page frame is the smallest fixed-length contiguous block of physical memory into which memory pages are mapped by the os. * A transfer of pages between main memory and an virtual memory happens. * The LRU page replacement algorithm, simply says that the page which used in least recent, should be replaced by required page. * * Example: * Given number of frames: 3 * Given number of pages: 12 * Required pages access sequence: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3 * 7 0 1 2 0 3 0 4 2 3 0 3 * Frame1 7 7 7 2 2 2 2 4 4 4 0 0 * Frame2 0 0 0 0 0 0 0 0 3 3 3 * Frame3 1 1 1 3 3 3 2 2 2 2 * Faults * * * * * * * * * * Number of page faults = 9 */ #include<stdio.h> #define MAX_PAGE 25 // Define a constant, program can support only this MAX_PAGE number of pages. #define MAX_FRAME 25 // Define a constant, program can support only this MAX_FRAME number of frames. /** * Function main returns 0 on success. */ int main() { // Declare arrays for pages and frames and distance_from_past_occurance int pages[MAX_PAGE], frames[MAX_FRAME], distances[MAX_FRAME]; // Number of pages, frames, page faults variables int numberPages, numberFrames, numberPageFaults = 0; // Other variables int i, j, temp, flag, found, lastFilledFrame, index, highestDistance; // Get number of frames from user printf("Enter number of frames (max limit is %d): ", MAX_FRAME); scanf("%d", &numberFrames); printf("You provided number of frames: %d\n", numberFrames); // Initialize frames array with -1 values and set lastFilledFrame value to -1 for(i = 0; i < numberFrames; i++) frames[i] = -1; lastFilledFrame = -1; // Get pages from user printf("Enter pages (enter -999 to exit, max number of pages limit is %d):\n", MAX_PAGE); numberPages = 0; for(i = 0; i < MAX_PAGE; i++) { scanf("%d", &temp); if(temp == -999 || numberPages == MAX_PAGE) break; pages[i] = temp; numberPages++; } printf("You provided number of pages: %d\n", numberPages); // Traverse the sequence of pages according LRU Page Replacement Algorithm for(i = 0; i < numberPages; i++) // For every page { flag = 0; // Flag to show availability of page in frame // Get the availability of required page in frame for(j = 0; j < numberFrames; j++) // For every frame { if(frames[j] == pages[i]) // If page found in frame { flag = 1; // Set flag to 1, showing that page is available in frame printf("\t"); // Print tab space instead "FAULT" word break; // Break the loop } } // If page is not available in frame, replace some page by required page and print "FAULT" word if(flag == 0) { if (lastFilledFrame == numberFrames-1) // If frames fully filled { // For every frame containing page, calculate distances to past occurance for(j = 0; j < numberFrames; j++) { for(temp = i - 1; temp > -1; temp--) // For every past page { distances[j] = 0; // Set this page_occurances_in_past to zero, showing no occurance if (frames[j] == pages[temp]) // If frame containing page matches to past occuring page { distances[j] = i - temp; // Store distance break; } } // For every past page loop ends here } // Loop for calculating distances ends here // Choose best candidate index for page replacement in frame, this best candidate is not occuring in past found = 0; for(j = 0; j < numberFrames; j++) // For every frame { if(distances[j] == 0) // If page's distance value is 0, means if no occurance in past { // Or if frame value is -1, means empty frame index = j; // Set this frame index to index variable found = 1; // Set to 1, means a page not occuring in past is found break; } } } else // If frames has not fully filled, best candidate is blank frame { index = ++lastFilledFrame; // Set blank frame's index to index variable found = 1; // Set to 1, means a suitable frame index found } // If still not choosed best candidate, get best candidate that is having highest distance in past if(found == 0) { highestDistance = distances[0]; index = 0; for(j = 1; j<numberFrames; j++) // For every frame { if(highestDistance < distances[j]) { highestDistance = distances[j]; index = j; // In last, index will contain farest distanced element's index in current frames } } } // Do the page replacement frames[index] = pages[i]; // Replace the identified index located page by required page printf("FAULT\t"); // Print "FAULT" numberPageFaults++; // Increment number of page faults } // Print the pages that are present in current frames for(j = 0; j < numberFrames; j++) { if(frames[j] != -1) printf("%d\t", frames[j]); } printf("\n"); } // Print number of page faults. printf("Number of page faults = %d\n", numberPageFaults); return 0; }

Snapshots