Virtual Memory

Virtual Memory Concept

Virtual memory lets processes use more memory than is physically available by keeping only the currently needed pages in RAM and the rest on disk. It also supports memory-mapped files, copy-on-write, and strong isolation between processes.

Demand Paging

In demand paging, pages are loaded into RAM only when a process actually references them. Access to a page not in memory triggers a page fault:

1. CPU traps to the OS.
2. OS finds the page on disk.
3. OS picks a free frame (or replaces one).
4. OS schedules I/O to read the page.
5. Process resumes.

Effective Access Time

EAT = (1 - p) * memory_access + p * page_fault_time

where p is the page-fault rate. Even a small p explodes EAT because page-fault time includes disk I/O.

Page Replacement

When there is no free frame, the OS must evict a page. The choice is made by a page-replacement algorithm.

FIFO

Evict the page that entered memory first. Simple but suffers from Belady's anomaly: more frames can cause more faults.

Optimal (OPT)

Evict the page that will not be used for the longest time. Theoretically optimal but requires future knowledge; used as a benchmark.

Least Recently Used (LRU)

Evict the page that was used furthest in the past. Approximates OPT. Implemented via counters or stack.

LRU Approximations

• Reference bit — set by hardware on access. Clear periodically; evict a page with bit 0.
• Clock (Second-chance) — pages in a circular list; on eviction, if reference bit is 1, clear it and advance; if 0, evict. Cheap and effective.

Counting-Based

• LFU (Least Frequently Used) — evict page with the smallest reference count.
• MFU (Most Frequently Used) — evict page with the largest count (assumes newly loaded pages will be used more).

Allocation of Frames

Two questions: how many frames does each process get, and from where does a fault steal a frame?

• Equal allocation — every process gets the same.
• Proportional allocation — bigger processes get more.
• Global replacement — any frame can be stolen.
• Local replacement — only own frames can be replaced.

Thrashing

Thrashing occurs when a process spends more time paging than executing. Symptom: CPU utilization plummets and paging I/O soars. Caused by allocating too few frames for a process's working set.

Working Set Model

The working set W(t, Δ) of a process is the set of pages referenced in the last Δ references. If the sum of all working sets fits in memory, the system is stable; otherwise, thrashing.

Page Fault Frequency (PFF)

Monitor each process's fault rate. If it exceeds an upper threshold, give it more frames; if below a lower threshold, take some away.

Memory-Mapped Files

Modern OSes let a process map a file into its address space. Reads and writes become memory accesses, backed by the file. Very efficient for large files (mmap in Linux, MapViewOfFile in Windows).

Copy-on-Write

After fork(), parent and child initially share pages marked read-only. The first write triggers a fault and a copy of that page. Saves time and memory if the child quickly calls exec().

Example Comparison

Given reference string 7,0,1,2,0,3,0,4,2,3,0,3,2 and 3 frames:

• FIFO faults: 15
• OPT faults: 9
• LRU faults: 12

(exact numbers depend on algorithm variant)

Summary

Virtual memory decouples address space size from RAM and underlies modern multitasking. Demand paging combined with a good replacement algorithm (usually Clock or LRU approximation) keeps the system fast; the working-set model and PFF prevent thrashing.

Important Questions

1. Define virtual memory and list its benefits.
2. Explain demand paging and the page-fault handling steps.
3. Compute EAT for p=0.001 and page-fault time 8 ms.
4. Describe FIFO, LRU, and Optimal replacement with a string example.
5. What is Belady's anomaly?
6. Explain the clock (second-chance) algorithm.
7. Define thrashing and describe how to control it.
8. Explain the working set model.