==============================================================
  Experiment 14: Page Replacement Algorithms
==============================================================
  [Back to Index]
--------------------------------------------------------------

ALGORITHMS: FIFO, LRU, LFU, Optimal, Random
            + All-in-one comparison program

==============================================================
  PROGRAM 1: FIFO Page Replacement
==============================================================
#include <stdio.h>

int main() {
    int pages[50], frames[10];
    int n, f;
    int i, j;
    int next = 0;
    int found;
    int faults = 0;

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

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

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

    for (i = 0; i < f; i++)
        frames[i] = -1;

    printf("\nPage\t");
    for (i = 0; i < f; i++)
        printf("Frame%d\t", i + 1);
    printf("Status\n");

    for (i = 0; i < n; i++) {
        found = 0;
        for (j = 0; j < f; j++) {
            if (frames[j] == pages[i]) {
                found = 1;
                break;
            }
        }
        if (!found) {
            frames[next] = pages[i];
            next = (next + 1) % f;
            faults++;
        }
        printf("%d\t", pages[i]);
        for (j = 0; j < f; j++) {
            if (frames[j] == -1) printf("-\t");
            else printf("%d\t", frames[j]);
        }
        if (found) printf("Hit\n");
        else printf("Fault\n");
    }

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

==============================================================
  PROGRAM 2: LRU Page Replacement
==============================================================
#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;

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

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

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;
}

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);

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

    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;
}

==============================================================
  PROGRAM 3: LFU Page Replacement
==============================================================
#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;

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

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

int findLFU(int f) {
    int minFreq = freq[0], pos = 0;
    for (int i = 1; i < f; i++) {
        if (freq[i] < minFreq) { minFreq = freq[i]; pos = i; }
        else if (freq[i] == minFreq && time[i] < time[pos]) pos = i;
    }
    return pos;
}

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);

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

    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;
}

==============================================================
  PROGRAM 4: Optimal Page Replacement
==============================================================
#include <stdio.h>

#define MAX_PAGES 50
#define MAX_FRAMES 10

int frames[MAX_FRAMES];
int faults = 0;

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

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

int findOptimal(int pages[], int n, int index, int f) {
    int farthest = index, pos = -1;
    for (int i = 0; i < f; i++) {
        int j;
        for (j = index + 1; j < n; j++) {
            if (frames[i] == pages[j]) {
                if (j > farthest) { farthest = j; pos = i; }
                break;
            }
        }
        if (j == n) return i;
    }
    if (pos == -1) return 0;
    return pos;
}

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);

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

    for (int i = 0; i < n; i++) {
        int pos = findPage(pages[i], f);
        if (pos != -1) { 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 = findOptimal(pages, n, i, f);
            frames[replaceIndex] = pages[i];
            faults++;
            displayTable(pages[i], f, 0);
        }
    }
    printf("\nTotal Page Faults = %d\n", faults);
    return 0;
}

==============================================================
  PROGRAM 5: Random Page Replacement
==============================================================
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_PAGES 50
#define MAX_FRAMES 10

int frames[MAX_FRAMES];
int faults = 0;

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

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

int getRandomFrame(int f) { return rand() % f; }

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;
    srand(time(NULL));

    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);

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

    for (int i = 0; i < n; i++) {
        int pos = findPage(pages[i], f);
        if (pos != -1) { 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 = getRandomFrame(f);
            frames[replaceIndex] = pages[i];
            faults++;
            displayTable(pages[i], f, 0);
        }
    }
    printf("\nTotal Page Faults = %d\n", faults);
    return 0;
}

==============================================================
  PROGRAM 6: All-in-One Comparison
==============================================================
#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);
}

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);
}

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);
}

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);
}

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);
}

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;
}
--------------------------------------------------------------

==============================================================
  [Prev: Exp 13]  |  [Next: Exp 15]
==============================================================