Assignment 07: Non-Contiguous Memory Management: Paging and Replacement

I. Objective & Theoretical Framework

In modern computer operating systems, paging is a memory management scheme that permits the physical address space of a process to be non-contiguous, eliminating external fragmentation. The operating system retrieves data from secondary storage in same-size blocks called pages, which are loaded into available physical memory blocks called frames.

When a process references a page not currently in physical memory, a page fault occurs. Page replacement algorithms are fundamental to demand paging, completing the separation between logical and physical memory and providing programmers with an enormous virtual memory space.

You will implement the address translation mechanism and simulate the following page replacement algorithms:

• First-In, First-Out (FIFO): Associates each page with the time it was brought into memory; the oldest page is chosen for replacement.
• Least Recently Used (LRU): Uses the recent past as an approximation of the near future, replacing the page that has not been used for the longest period of time.
• Least Frequently Used (LFU): Replaces the page with the smallest reference count, assuming an actively used page should have a large count.

II. Prerequisite Knowledge & Resources

• Address Translation Formula: To find a Physical Address (PA), you must map the logical page to its physical frame and add the offset. Formula: $PA = (Frame\_Number \times Page\_Size) + Offset$.
• Arrays and Initialization: You will heavily rely on parallel arrays to track frame contents, frequency counts (for LFU), and usage timestamps (for LRU).

#include <stdio.h>

int main() {
    int i, j, k, frames, pages, faults = 0, count = 0;
    int ref_string[25], m[10];

    printf("Enter the length of reference string: ");
    scanf("%d", &pages);
    printf("Enter the reference string: ");
    for(i = 0; i < pages; i++) {
        scanf("%d", &ref_string[i]);
    }
    printf("Enter no. of frames: ");
    scanf("%d", &frames);

    // Initialize frames to -1 to indicate they are empty
    for(i = 0; i < frames; i++) {
        m[i] = -1;
    }

    printf("\n The Page Replacement Process is -- \n");

    for(i = 0; i < pages; i++) {
        // [Insert logic to check if ref_string[i] is already in m[]]

        // [Insert logic to replace page at m[count] if a fault occurs]

        // [Insert logic to increment faults and manage the FIFO circular counter]
    }

    // [Insert Final Output Statements]

    return 0;
}

V. Common Pitfalls & Debugging Strategies

• Frame Initialization: Do not initialize your frame tracking arrays to 0. Logical page 0 is a valid page number. Always initialize empty frames to -1.

• LFU Tie-Breaking: In the LFU algorithm, it is highly common for multiple pages to have the same frequency count (especially a count of 1 for newly brought-in pages). Ensure your logic explicitly handles ties (often by defaulting to a FIFO replacement among the tied pages).

• Offset Validation: In the address translation task, ensure you validate the offset. If a user inputs an offset greater than or equal to the page size, the program must output an “Invalid Offset” error rather than calculating a false physical address.

• Mapping Virtual Memory: The paging you are simulating happens constantly. Run a C program that simply sleeps for 100 seconds. Find its PID, then run cat /proc/[PID]/maps or pmap [PID]. This exposes the actual virtual memory map the Linux kernel has constructed for your process, bridging the gap between textbook theory and real system architecture.

VI. Real-World Case Study

Page replacement is the bedrock of modern virtual memory. When you open too many browser tabs and your computer slows to a crawl, you are experiencing “thrashing”—a state where the OS is spending more CPU cycles swapping pages in and out of the physical RAM to the secondary storage (the pagefile or swap partition) than it is executing actual application code. While modern Solid State Drives (SSDs) make page faults drastically faster to resolve than older mechanical Hard Disk Drives (HDDs), efficient algorithms like LRU remain critical to maintaining system responsiveness.

VII. Advanced Variant Tasks

• Optimal Page Replacement: The Optimal algorithm replaces the page that will not be used for the longest period of time into the future, guaranteeing the lowest possible page fault rate. It is difficult to implement in reality because it requires future knowledge of the reference string. However, in our simulation, the full reference string is known. Write a C program to simulate the Optimal page replacement algorithm.

• Belady’s Anomaly: Write a script or specifically craft a reference string that demonstrates Belady’s Anomaly under the FIFO algorithm (where increasing the number of physical frames actually increases the number of page faults). Compare this against your Optimal algorithm simulation, which will never suffer from Belady’s Anomaly.

• The Thrashing Simulator: Stress-test the system. Simulate an environment with severely restricted physical frames (e.g., 3 frames) and a massively volatile reference string representing heavy concurrent workloads. Output a tabular graph proving that the page fault rate approaches 100%, demonstrating the catastrophic performance collapse known as “thrashing.”

VIII. Resources & Further Reading

• OSTEP - Paging: Read Chapter 18: Paging Introduction (PDF) to understand how to translate logical virtual addresses into physical frames.
• OSTEP - Page Replacement Policies: Read Chapter 22: Beyond Physical Memory (Policies) (PDF). This contains excellent diagrams mapping out LRU, LFU, and Optimal replacements, as well as an explanation of Belady’s Anomaly and Thrashing.