Random Page Replacement Algorithm

 

Random Page Replacement Algorithm

---

1. Aim

To implement the Random Page Replacement Algorithm and display the frame contents after each page reference.

---

2. Objective

• To understand the working of Random page replacement

• To replace a page using a random selection strategy

• To display the frame table after each page arrival

• To analyze page hits and page faults

• To compare its behavior with FIFO, LRU, and Optimal

---

3. Theory

The Random Page Replacement Algorithm replaces a page selected randomly from the available frames when a page fault occurs and no empty frame is available.

🔹 Key Idea:

“When replacement is needed, choose any frame randomly.”

Unlike:

• FIFO → replaces oldest page

• LRU → replaces least recently used page

• LFU → replaces least frequently used page

• Optimal → replaces page used farthest in future

Random replacement does not consider past or future information.

---

4. Characteristics

Feature	Description
Replacement Strategy	Random selection
Uses Past Information	❌ No
Uses Future Information	❌ No
Complexity	Very simple
Practical Use	Rare in real OS
Performance	Unpredictable

---

5. Algorithm

1. Initialize all frames as empty (-1)

2. For each page reference:

   • If page exists → Hit

   • Else:

     • If empty frame exists → place page

     • Else:

       • Generate random index between 0 and f-1

       • Replace page at that index

3. Display frame table after each reference

4. Count page faults

---

6. C Program (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;

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

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

/* Generate random frame index */
int getRandomFrame(int f) {
    return rand() % f;
}

/* 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;

    srand(time(NULL));  // Seed random generator

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

    /* Simulation */
    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;
}

---

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 (Example Run)

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       3       1       Fault
0       0       3       1       Fault
4       0       3       4       Fault

Total Page Faults = 7

⚠️ Note: Output varies because replacement is random.

---

9. Observations

• Page faults vary on each execution

• No tracking of recency or frequency

• Performance is unpredictable

---

10. Advantages

✔ Very simple to implement
✔ Low overhead
✔ No need to maintain extra data structures

---

11. Disadvantages

❌ Poor performance in many cases
❌ Unpredictable results
❌ Not suitable for real systems
❌ May replace frequently used pages randomly

---

12. Comparison with Other Algorithms

Algorithm	Basis of Replacement
FIFO	Oldest page
LRU	Least recently used
LFU	Least frequently used
Optimal	Farthest future use
Random	Random selection

---

13. Result

The Random Page Replacement Algorithm was successfully implemented and simulated. The frame table was displayed after each page reference, and total page faults were calculated.