Mastering Virtual Memory: Page Tables and Replacement Algorithms in CSC369

Understanding Virtual Memory and Page Tables

Virtual memory is a cornerstone of modern operating systems, enabling programs to use more memory than physically available. In CSC369 Assignment 3, you simulate a virtual memory system with a two-level page table and implement page replacement algorithms. This tutorial breaks down the core concepts and provides practical guidance for your implementation.

Why Virtual Memory Matters in 2026

With the rise of AI workloads and large language models, efficient memory management is more critical than ever. Apps like ChatGPT and video games such as Cyberpunk 2077 rely on virtual memory to handle massive datasets. Understanding page tables helps you optimize performance in memory-constrained environments.

Task 1: Address Translation with Two-Level Page Tables

Your first task is to implement virtual-to-physical address translation and demand paging. The simulator uses a two-level page table: a page directory and second-level page tables. Each virtual address is split into three parts: page directory index, page table index, and offset.

Key Data Structures

• physmem: simulated physical memory (array of bytes)
• coremap: array of frame structs tracking physical frame usage
• pgdir: page directory (array of page directory entries)
• page tables: arrays of page table entries (PTEs) containing frame numbers or swap offsets

Implementing find_physpage

In pagetable.c, you must complete find_physpage. This function translates a virtual address to a physical address by walking the two-level page table. On a page fault, you allocate a frame (using the coremap), load the page from the swap file (demand paging), and update the PTE. Use the rand replacement algorithm initially to test translation independently.

// Pseudocode for find_physpage
pde_t *pde = &pgdir[VPN1];
if (!pde->valid) {
    // allocate second-level page table
}
pte_t *pte = &second_level[VPN2];
if (!pte->valid) {
    // page fault: allocate frame, read from swap, update PTE
}
physaddr = (pte->frame << PAGE_SHIFT) | offset;

Task 2: Page Replacement Algorithms

You will implement four algorithms: FIFO, exact LRU, CLOCK (with one reference bit), and OPT. Each algorithm chooses which frame to evict when memory is full. You'll add fields to struct frame in pagetable.h to support these algorithms.

FIFO (First-In, First-Out)

FIFO evicts the page that entered memory first. Use a queue (or timestamp) to track arrival order. Simple but can suffer from Belady's anomaly. Example: Like a checkout line at a grocery store—first person in line is first to leave.

Exact LRU (Least Recently Used)

LRU evicts the page that hasn't been used for the longest time. Maintain a timestamp or linked list to track access order. It's optimal in theory but expensive in practice. In 2026, LRU is used in database caches like Redis.

CLOCK (Second-Chance)

CLOCK approximates LRU using a single reference bit per frame. A clock hand sweeps through frames; if the reference bit is 1, it's cleared and the hand moves; if 0, the page is evicted. Efficient and widely used in Linux kernel.

OPT (Optimal Page Replacement)

OPT evicts the page that will be used farthest in the future. It's impossible to implement in real systems but serves as a benchmark. You'll simulate it by reading the entire trace in advance. Think of it as a perfect memory manager.

Performance Analysis: Tables and Write-Up

After implementing, run the provided trace programs (plus one of your choice) with memory sizes 50, 100, 150, 200 frames. Record hit rate, hit count, miss count, eviction counts (clean and dirty). Create a table like:

Memory Size | Hit Rate | Hit Count | Miss Count | Evictions (Clean/Dirty)
50          | 0.45     | 4500      | 5500       | 500 / 200

Comparing Algorithms

In your README, write a paragraph comparing results. Typically, OPT has the highest hit rate, followed by LRU, then CLOCK, then FIFO. However, LRU may degrade under certain access patterns. CLOCK often performs close to LRU with less overhead.

LRU as Memory Increases

As memory size increases, LRU's hit rate improves because more pages can be kept in memory. However, the rate of improvement diminishes—doubling memory might not double hit rate. This is due to the principle of locality: only a subset of pages is actively used.

Practical Tips and Common Pitfalls

• Ensure your code compiles without warnings. Use gcc -Wall -Wextra.
• Label all added fields clearly in pagetable.h with comments.
• Test with the rand algorithm first to verify translation works.
• For OPT, you need to precompute future references—store the trace in an array.
• Dirty evictions require writing the page back to swap; clean evictions do not.

Connecting to Current Trends

In 2026, virtual memory is vital for AI inference on edge devices. For example, running a large language model on a smartphone uses demand paging to load model weights on-the-fly. Understanding page replacement helps engineers optimize for limited memory. Similarly, video games like Elden Ring stream textures using similar algorithms.

"The way to gain a solid understanding of the theory is by applying the concepts in practice." — CSC369 instructor

Conclusion

By completing this assignment, you'll deeply understand how operating systems manage memory. You'll implement both address translation and replacement policies, gaining skills relevant to systems programming, cloud computing, and embedded AI. Good luck!