Least Recently Used (LRU) Page Replacement Algorithm

 

Least Recently Used (LRU) Page Replacement Algorithm

---

1. Aim

To implement the Least Recently Used (LRU) Page Replacement Algorithm and display the frame contents after each page arrival.

---

2. Objective

• To understand how LRU selects a victim page

• To implement LRU using time (recency) tracking

• To analyze page hits and page faults

---

3. Theory

The LRU algorithm replaces the page that has not been used for the longest time in the past.

Key Idea:

“The page that was least recently accessed is least likely to be used again.”

LRU approximates optimal behavior better than FIFO but requires tracking past usage.

---

4. Data Structures Used

Structure	Purpose
frames[]	Stores pages in memory
time[]	Stores last-used time of each frame
counter	Global time counter

---

5. Algorithm

1. Initialize frames as empty (-1)

2. For each page reference:

   • If page is present → Hit, update its time

   • Else:

     • If empty frame exists → place page

     • Else → replace page with minimum last-used time

3. Display frame table after each reference

4. Count page faults

---

6. Modular C Program (LRU)

#include <stdio.h>

#define MAX_PAGES 50
#define MAX_FRAMES 10

int frames[MAX_FRAMES];
int time[MAX_FRAMES];
int counter = 0;
int faults = 0;

/* Initialize frames and time */
void initializeFrames(int f) {
    for (int i = 0; i < f; i++) {
        frames[i] = -1;
        time[i] = 0;
    }
}

/* Check if page exists */
int findPage(int page, int f) {
    for (int i = 0; i < f; i++) {
        if (frames[i] == page)
            return i;
    }
    return -1;
}

/* Find index of least recently used page */
int findLRU(int f) {
    int min = time[0], pos = 0;
    for (int i = 1; i < f; i++) {
        if (time[i] < min) {
            min = time[i];
            pos = i;
        }
    }
    return pos;
}

/* Display frame table */
void displayTable(int page, int f, int hit) {
    printf("%d\t", page);
    for (int i = 0; i < f; i++) {
        if (frames[i] == -1)
            printf("-\t");
        else
            printf("%d\t", frames[i]);
    }
    printf("%s\n", hit ? "Hit" : "Fault");
}

int main() {
    int pages[MAX_PAGES];
    int n, f;

    printf("Enter number of pages: ");
    scanf("%d", &n);

    printf("Enter page reference string:\n");
    for (int i = 0; i < n; i++)
        scanf("%d", &pages[i]);

    printf("Enter number of frames: ");
    scanf("%d", &f);

    initializeFrames(f);

    /* Print table header */
    printf("\nPage\t");
    for (int i = 0; i < f; i++)
        printf("Frame%d\t", i + 1);
    printf("Status\n");

    /* LRU Simulation */
    for (int i = 0; i < n; i++) {
        counter++;
        int pos = findPage(pages[i], f);

        if (pos != -1) {
            time[pos] = counter;
            displayTable(pages[i], f, 1);
        } else {
            int replaceIndex;
            if (i < f) {
                replaceIndex = i;
            } else {
                replaceIndex = findLRU(f);
            }
            frames[replaceIndex] = pages[i];
            time[replaceIndex] = counter;
            faults++;
            displayTable(pages[i], f, 0);
        }
    }

    printf("\nTotal Page Faults = %d\n", faults);
    return 0;
}

---

7. Sample Input

Enter number of pages: 8
Enter page reference string:
7 0 1 2 0 3 0 4
Enter number of frames: 3

---

8. Sample Output (Frame Table)

Page    Frame1  Frame2  Frame3  Status
7       7       -       -       Fault
0       7       0       -       Fault
1       7       0       1       Fault
2       2       0       1       Fault
0       2       0       1       Hit
3       2       0       3       Fault
0       2       0       3       Hit
4       4       0       3       Fault

Total Page Faults = 6

---

9. Observations

• LRU produces fewer page faults than FIFO

• Recently used pages remain in memory

• Requires additional tracking (time/counters)

---

10. Advantages

✔ Better performance than FIFO
✔ Approximates optimal algorithm
✔ No Belady’s anomaly

---

11. Disadvantages

❌ Overhead of tracking usage
❌ Hard to implement perfectly in hardware

---

12. Result

The LRU page replacement algorithm was successfully implemented  and the frame contents were displayed after each page reference.