Least Frequently Used (LFU) Page Replacement Algorithm

 

Least Frequently Used (LFU) Page Replacement Algorithm

---

1. Aim

To implement the Least Frequently Used (LFU) Page Replacement Algorithm and display the frame contents after each page reference.

---

2. Objective

• To understand the working of LFU page replacement

• To replace the page with the minimum access frequency

• To analyze page hits and page faults

---

3. Theory

The LFU algorithm replaces the page that has been used least often.

Key Idea:

“Pages with low access frequency are less likely to be used again.”

When two pages have the same frequency, FIFO order (or oldest) is commonly used as a tie-breaker.

---

4. Data Structures Used

Structure	Purpose
frames[]	Stores pages in memory
freq[]	Stores access frequency
time[]	Stores arrival time (tie-breaker)
counter	Global time counter

---

5. Algorithm

1. Initialize frames as empty

2. For each page reference:

   • If page exists → Hit, increment frequency

   • Else:

     • If empty frame exists → insert page

     • Else → replace page with lowest frequency

       • If tie → replace oldest page

3. Display frame contents after each step

4. Count page faults

---

6.  C Program (LFU)

#include <stdio.h>

#define MAX_PAGES 50
#define MAX_FRAMES 10

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

/* Initialize frames, frequency and time */
void initializeFrames(int f) {
    for (int i = 0; i < f; i++) {
        frames[i] = -1;
        freq[i] = 0;
        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 LFU page index (tie → FIFO) */
int findLFU(int f) {
    int minFreq = freq[0];
    int pos = 0;

    for (int i = 1; i < f; i++) {
        if (freq[i] < minFreq) {
            minFreq = freq[i];
            pos = i;
        } else if (freq[i] == minFreq) {
            if (time[i] < time[pos]) {
                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");

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

        if (pos != -1) {
            freq[pos]++;
            displayTable(pages[i], f, 1);
        } else {
            int replaceIndex = -1;

            for (int j = 0; j < f; j++) {
                if (frames[j] == -1) {
                    replaceIndex = j;
                    break;
                }
            }

            if (replaceIndex == -1)
                replaceIndex = findLFU(f);

            frames[replaceIndex] = pages[i];
            freq[replaceIndex] = 1;
            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

• LFU considers frequency instead of recency

• Tie-breaking is required ( use FIFO)

• Performance depends on access pattern

---

10. Advantages

✔ Useful for workloads with repeated access
✔ Avoids replacing frequently used pages

---

11. Disadvantages

❌ Old pages may remain forever (frequency aging problem)
❌ More overhead than FIFO
❌ Requires tie-breaking strategy

---

12. Result

The LFU page replacement algorithm was successfully implemented using a C program, and the frame contents were displayed after each page reference.