Virtual Memory — Demand Paging, Page Replacement | Tutorials Logic

What is Virtual Memory?

Virtual memory is a memory management technique that allows a process to use more memory than is physically available in RAM. It uses disk space (swap space/page file) as an extension of RAM. The OS gives each process the illusion of having a large, contiguous address space.

Benefits:

Programs can be larger than physical memory
More processes can run simultaneously
Efficient memory use (only needed pages are in RAM)
Process isolation (each process has its own virtual address space)

Demand Paging

With demand paging, pages are loaded into memory only when they are needed (on demand), not all at once when the process starts. This reduces memory usage and startup time.

Each page table entry has a valid/invalid bit:

Valid (1): Page is in physical memory
Invalid (0): Page is on disk or doesn't exist

Page Fault

A page fault occurs when a process accesses a page that is not currently in physical memory (invalid bit = 0). The OS handles it:

CPU generates a page fault trap
OS checks if the access is valid (legal address?)
OS finds a free frame in physical memory
OS reads the required page from disk into the free frame
OS updates the page table (set valid bit = 1)
Restart the instruction that caused the page fault

Page Replacement Algorithms

When there are no free frames and a page fault occurs, the OS must replace an existing page. The goal is to minimize page faults.

FIFO (First In First Out): Replace the oldest page (the one that has been in memory the longest). Simple but may replace frequently used pages. Suffers from Belady's Anomaly (more frames can cause more page faults).

Optimal (OPT): Replace the page that will not be used for the longest time in the future. Theoretically optimal (minimum page faults) but impossible to implement in practice (requires future knowledge). Used as a benchmark.

LRU (Least Recently Used): Replace the page that has not been used for the longest time. Good approximation of optimal. Requires tracking when each page was last used. Expensive to implement exactly.

LFU (Least Frequently Used): Replace the page with the lowest access count. Pages that are rarely used are replaced first.

Clock (Second Chance): A practical approximation of LRU. Uses a circular list and a reference bit. When a page is accessed, its reference bit is set to 1. When replacing, scan pages: if reference bit = 1, clear it and move on; if reference bit = 0, replace it.

Page Replacement Comparison

Algorithm	Page Faults	Implementable	Overhead
FIFO	High	Yes	Low
Optimal	Minimum	No (theoretical)	N/A
LRU	Low	Yes (expensive)	High
LFU	Medium	Yes	Medium
Clock	Low	Yes	Low

Thrashing

Thrashing occurs when a process spends more time swapping pages in and out of memory than executing. It happens when there are too many processes competing for too little memory.

Symptoms: CPU utilization drops dramatically, disk I/O is very high, system becomes unresponsive.

Solutions:

Working Set Model: Track the set of pages a process actively uses (working set). Ensure each process has enough frames for its working set.
Page Fault Frequency: Monitor page fault rate. If too high, give the process more frames; if too low, take frames away.
Reduce the degree of multiprogramming (run fewer processes)