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

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 Page Replacement Algorithm in OS

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

Prime Course Trailer

Related Banners

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

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

Checkout list of all the video courses in PrepInsta Prime Subscription