# 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)

Run
```#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);
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```

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## LRU program in C (Method 2)

Run
```#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);

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

## Checkout list of all the video courses in PrepInsta Prime Subscription 