Implementing LRU Page Replacement Algorithm in C

In computer science, memory management is a critical aspect of operating systems. One of the fundamental challenges in memory management is efficiently managing available memory by replacing pages when the memory becomes full. The Least Recently Used (LRU) page replacement algorithm is a widely used method that evicts the least recently used page when new pages need to be brought into memory. In this tutorial, we are going to write a Program for LRU Page Replacement Algorithm in C.

Understanding the LRU Algorithm

The LRU page replacement algorithm works on the principle that pages that have not been used for the longest period are the least likely to be used in the near future. When a new page needs to be loaded into memory and the memory is full, the LRU algorithm identifies the least recently used page for a replacement.

C Program for LRU Page Replacement Algorithm

Let’s delve into a C program that simulates the LRU page replacement algorithm:

#include <stdio.h>
#include <stdbool.h>

#define MAX_FRAMES 3 // Maximum number of frames

// Function to find the index of the least recently used frame
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;
}

// Function to perform LRU page replacement
void lruPageReplacement(int pages[], int n, int capacity) {
    int frames[MAX_FRAMES], time[MAX_FRAMES];
    int i, j, page_faults = 0;

    for (i = 0; i < MAX_FRAMES; ++i) {
        frames[i] = -1; // Initializing frames with -1 indicating empty frames
        time[i] = 0;
    }

    for (i = 0; i < n; ++i) {
        bool page_found = false;

        // Check if the page is already present in the frames
        for (j = 0; j < MAX_FRAMES; ++j) {
            if (frames[j] == pages[i]) {
                page_found = true;
                time[j] = i + 1; // Update time of last access for LRU
                break;
            }
        }

        // If the page is not present in frames, perform page fault
        if (!page_found) {
            int pos = findLRU(time, MAX_FRAMES);
            frames[pos] = pages[i];
            time[pos] = i + 1;
            page_faults++;

            // Display the current state of frames
            printf("Frames after page %d: ", pages[i]);
            for (j = 0; j < MAX_FRAMES; ++j) {
                if (frames[j] == -1) {
                    printf(" - ");
                } else {
                    printf("%d ", frames[j]);
                }
            }
            printf("\n");
        }
    }

    printf("\nTotal Page Faults: %d\n", page_faults);
}

void main() {
    int pages[] = {1, 2, 3, 4, 5, 3, 4, 1, 6, 7,11,23,45}; // Pages in memory reference sequence
    int n = sizeof(pages) / sizeof(pages[0]); // Number of pages
    int capacity = MAX_FRAMES; // Capacity of frames

    printf("LRU Page Replacement Algorithm Simulation\n\n");
    lruPageReplacement(pages, n, capacity);


}

Output

Explanation of the LRU Page Replacement Algorithm Program in C

1. Header Files and Definitions

#include <stdio.h>
#include <stdbool.h>

#define MAX_FRAMES 3 // Maximum number of frames

• The code begins by including the necessary header files: stdio.h for input/output operations and stdbool.h for using a boolean data type.
• MAX_FRAMES is defined as the maximum number of frames available in memory.

2. Function to Find Least Recently Used Frame

int findLRU(int time[], int n) {
    // ... (function implementation)
    return pos;
}

• findLRU function identifies the index of the least recently used frame based on the time of last access.
• It traverses the array time[] to find the frame with the smallest access time and return its index (pos).

3. LRU Page Replacement Function

void lruPageReplacement(int pages[], int n, int capacity) {
    // ... (function implementation)
}

• lruPageReplacement function simulates the LRU algorithm for page replacement.
• It maintains arrays frames[] and time[] to represent frames in memory and their last access time, respectively.
• The function iterates through the sequence of pages[], checking if each page is present in the frames. If not, it performs a page fault and replaces the least recently used frame with the current page.

4. Initialization and Page Replacement Simulation in the main Function

int main() {
    int pages[] = {1, 2, 3, 4, 5, 3, 4, 1, 6, 7,11,23,45}; // Pages in memory reference sequence
    int n = sizeof(pages) / sizeof(pages[0]); // Number of pages
    int capacity = MAX_FRAMES; // Capacity of frames

    printf("LRU Page Replacement Algorithm Simulation\n\n");
    lruPageReplacement(pages, n, capacity);

    return 0;
}

• main function initiates the simulation with a predefined sequence of pages stored in the pages[] array.
• It calculates the number of pages (n) and sets the capacity of frames.
• The simulation begins by calling the lruPageReplacement function with the page sequence, number of pages, and frame capacity as arguments. The function simulates page replacements and prints the state of frames after each page reference, along with the total number of page faults.

This code illustrates how the LRU page replacement algorithm works by simulating page replacement operations based on the order of page references in the input sequence. It demonstrates the process of managing memory by replacing the least recently used pages when the memory is full.

The LRU page replacement algorithm plays a crucial role in managing memory efficiently within operating systems. By evicting the least recently used pages from memory, it optimizes the usage of available resources. Understanding and implementing this algorithm in C provides valuable insights into memory management strategies, aiding in the development of robust and efficient systems.

Happy Coding

See Also

• C Program to Swap two numbers using Pointers
• Loops in C