Least Recently Used (LRU) in C

LRU in Operating System

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.

Therefore, the operating system removes the unused pages from the main memory and sends them to the secondary memory. The concept behind this is, the pages that have not been used in the processing, will not be used in the next few instructions.

The operating system implements the page fault mechanism through an algorithm. This algorithm maintains a linked list of all the pages in the memory. The most recently used pages are kept in the front, while the pages which are not used are placed at the rear position. It generates the need of page replacement algorithm which can lessen the waiting time for pages in. The Least Recently Used (LRU) page replacement algorithm, needs to decide which page is to be replaced when the new page comes in.

Read AlsoLRU in C ++

LRU program in C

    #include<stdio.h>
    
    int main()
    {
        int frames[10], temp[10], pages[10];
        int total_pages, m, n, position, k, l, total_frames;
        int a = 0, b = 0, page_fault = 0;
        printf(\nEnter Total Number of Frames:\t);
        scanf(“%d”, &total_frames);
        for(m = 0; m < total_frames; m++)
        {
                frames[m] = –1;
        }
        printf(“Enter Total Number of Pages:\t);
        scanf(“%d”, &total_pages);
        printf(“Enter Values for Reference String:\n);
        for(m = 0; m < total_pages; m++)
        {
                printf(“Value No.[%d]:\t, m + 1);
                scanf(“%d”, &pages[m]);
        }
        for(n = 0; n < total_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;
                                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++;
                }
                printf(\n);
                for(m = 0; m < total_frames; m++)
                {
                    printf(“%d\tframes[m]);
                }
        }
        printf(\nTotal Number of Page Faults:\t%d\n, page_fault);
        return 0;
    }

Output –

 
    Enter Total Number of Frames:   4                                      
    Enter Total Number of Pages:    5                                      
    Enter Values for Reference String:                                     
    Value No.[1]:   5                                                      
    Value No.[2]:   3                                                      
    Value No.[3]:   1                                                      
    Value No.[4]:   2                                                      
    Value No.[5]:   4                                                      
                                                                        
    5       –1      –1      –1                                             
    5       3       –1      –1                                             
    5       3       1       –1                                             
    5       3       1       2                                              
    4       3       1       2                                              
    Total Number of Page Faults:    1