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.

LRU in Operating System

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.

Read AlsoLRU in C ++

Page Replacement Algorithm In OS LRU Example
Page Replacement Algorithm LRU Example detailed

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[0]);
    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

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[0]);

    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