Comparative Study - Simulation of Page Replacement Algorithms

 

Comparative Simulation of Page Replacement Algorithms

---

1. Aim

To simulate and compare the performance of:

• FIFO

• LRU

• LFU

• Random

• Optimal

using a randomly generated page reference string with 3 page frames, and to calculate:

• Total Hits

• Total Misses

• Hit Rate

---

2. Objective

• To understand different page replacement strategies

• To compare performance of various algorithms

• To observe that Optimal gives minimum page faults

• To analyze hit rate differences

---

3. Theory

When a process executes, pages are loaded into memory frames. If a page is not in memory, a page fault occurs.

Different page replacement algorithms decide which page to remove when memory is full.

Algorithms Used:

1️⃣ FIFO (First In First Out)

• Replaces the oldest page in memory.

• Simple queue-based approach.

• May suffer from Belady’s anomaly.

2️⃣ LRU (Least Recently Used)

• Replaces the page that has not been used for the longest time.

• Uses past reference information.

• Does not suffer from Belady’s anomaly.

3️⃣ LFU (Least Frequently Used)

• Replaces the page with lowest usage frequency.

• Requires frequency counting.

4️⃣ Random

• Replaces any frame randomly.

• Simple but unpredictable.

5️⃣ Optimal

• Replaces the page that will not be used for the longest time in the future.

• Produces minimum page faults.

• Theoretical (future knowledge required).

4. Algorithm (General Simulation Procedure)

1. Generate a random page reference string.

2. For each algorithm:

   • Initialize frames as empty.

   • Traverse page reference string.

   • Check for hit or miss.

   • Apply replacement policy if needed.

3. Count:

   • Total hits

   • Total misses

4. Calculate:

   • Hit Rate = (Hits / Total Pages) × 100

---

5. Program

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FRAMES 3
#define MAX_PAGES 50
#define PAGE_RANGE 10

int find(int frames[], int page) {
    for (int i = 0; i < FRAMES; i++)
        if (frames[i] == page)
            return i;
    return -1;
}

void printResult(char name[], int hits, int misses, int n) {
    printf("\nAlgorithm: %s\n", name);
    printf("Total Hits   = %d\n", hits);
    printf("Total Misses = %d\n", misses);
    printf("Hit Rate     = %.2f%%\n", (hits * 100.0) / n);
}

/* FIFO */
void simulateFIFO(int pages[], int n) {
    int frames[FRAMES] = {-1, -1, -1};
    int pointer = 0, hits = 0, misses = 0;

    for (int i = 0; i < n; i++) {
        if (find(frames, pages[i]) != -1)
            hits++;
        else {
            frames[pointer] = pages[i];
            pointer = (pointer + 1) % FRAMES;
            misses++;
        }
    }

    printResult("FIFO", hits, misses, n);
}

/* LRU */
void simulateLRU(int pages[], int n) {
    int frames[FRAMES] = {-1, -1, -1};
    int recent[FRAMES] = {0};
    int hits = 0, misses = 0, time = 0;

    for (int i = 0; i < n; i++) {
        time++;
        int pos = find(frames, pages[i]);

        if (pos != -1) {
            hits++;
            recent[pos] = time;
        } else {
            int lru = 0;
            for (int j = 1; j < FRAMES; j++)
                if (recent[j] < recent[lru])
                    lru = j;

            frames[lru] = pages[i];
            recent[lru] = time;
            misses++;
        }
    }

    printResult("LRU", hits, misses, n);
}

/* LFU */
void simulateLFU(int pages[], int n) {
    int frames[FRAMES] = {-1, -1, -1};
    int freq[FRAMES] = {0};
    int hits = 0, misses = 0;

    for (int i = 0; i < n; i++) {
        int pos = find(frames, pages[i]);

        if (pos != -1) {
            hits++;
            freq[pos]++;
        } else {
            int lfu = 0;
            for (int j = 1; j < FRAMES; j++)
                if (freq[j] < freq[lfu])
                    lfu = j;

            frames[lfu] = pages[i];
            freq[lfu] = 1;
            misses++;
        }
    }

    printResult("LFU", hits, misses, n);
}

/* Random */
void simulateRandom(int pages[], int n) {
    int frames[FRAMES] = {-1, -1, -1};
    int hits = 0, misses = 0;

    for (int i = 0; i < n; i++) {
        if (find(frames, pages[i]) != -1)
            hits++;
        else {
            int r = rand() % FRAMES;
            frames[r] = pages[i];
            misses++;
        }
    }

    printResult("Random", hits, misses, n);
}

/* Optimal */
void simulateOptimal(int pages[], int n) {
    int frames[FRAMES] = {-1, -1, -1};
    int hits = 0, misses = 0;

    for (int i = 0; i < n; i++) {
        if (find(frames, pages[i]) != -1) {
            hits++;
        } else {
            int farthest = i, pos = -1;

            for (int j = 0; j < FRAMES; j++) {
                int k;
                for (k = i + 1; k < n; k++)
                    if (frames[j] == pages[k])
                        break;

                if (k == n) {
                    pos = j;
                    break;
                }

                if (k > farthest) {
                    farthest = k;
                    pos = j;
                }
            }

            if (pos == -1)
                pos = 0;

            frames[pos] = pages[i];
            misses++;
        }
    }

    printResult("Optimal", hits, misses, n);
}

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

    printf("Enter length of  page reference: ");
    scanf("%d", &n);

    srand(time(NULL));

    printf("\nGenerated Page Reference String:\n");
    for (int i = 0; i < n; i++) {
        pages[i] = rand() % PAGE_RANGE;
        printf("%d ", pages[i]);
    }
    printf("\n");

    simulateFIFO(pages, n);
    simulateLRU(pages, n);
    simulateLFU(pages, n);
    simulateRandom(pages, n);
    simulateOptimal(pages, n);

    return 0;
}

---

Sample Output

Enter length of page reference: 20

Generated Page Reference String:
7 1 0 3 2 1 4 5 1 2 7 8 3 1 9 4 2 6 0 1

Algorithm: FIFO
Total Hits   = 5
Total Misses = 15
Hit Rate     = 25.00%

Algorithm: LRU
Total Hits   = 7
Total Misses = 13
Hit Rate     = 35.00%

Algorithm: LFU
Total Hits   = 6
Total Misses = 14
Hit Rate     = 30.00%

Algorithm: Random
Total Hits   = 4
Total Misses = 16
Hit Rate     = 20.00%

Algorithm: Optimal
Total Hits   = 9
Total Misses = 11
Hit Rate     = 45.00%

(Note: Output varies because of random generation.)

---

6. Observations

• Optimal gives minimum misses.

• LRU usually performs close to Optimal.

• FIFO may perform poorly.

• Random gives inconsistent results.

• LFU performance depends on access pattern.

---

7. Result

The simulation of FIFO, LRU, LFU, Random and Optimal page replacement algorithms was successfully implemented and their performance was compared using total hits, total misses and hit rate.