LRU Page Replacement Algorithm in C with Output of Program

LRU Page Replacement Algorithm in C with Output of Program

by

The processes in an operating system occupy dedicated memory and the memory is divided into smaller parts called pages. On demand of the CPU, these pages are brought from secondary memory to primary memory and this is done using an algorithm which is discussed elaborately in this article. Paging is primarily used for memory management and the algorithm decides which page needs to be replaced when a new page comes in.

LRU , Least Recently Used algorithm is a greedy algorithm in which the page to be replaced with the new one is recently used. Pages that are used heavily in the previous set of instructions are most likely to be used in the next set of instructions too.

Let’s understand this with an example. Let’s suppose the page reference string is :
7 2 0 4 5 0 7 6 0 8 2 0 2 and we have 4 empty page slots.

Initially we have all the slots are empty and we allocate 7 2 0 4 to the empty slots. (4 Page faults)
When 5 comes up, it will take the place of 7 because 7 is least recently used here (1 page fault).
Next we have 0, which is already there in the memory , so no replacement is required. (0 page fault). Same goes for the next number i.e 7.

When 6 hits up, it will be replaced with 2’s place because now 2 is the least recently used memory.

This process continues.

Let’s now write the code for this algorithm.

LRU Page Replacement Program in C

#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 of the code is:

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

Hope you have understood how the LRU algorithm works. Hit up the comment section in case you have any doubt.

Leave a Comment