Virtual Memory in OS: Demand Paging, TLB, Thrashing

Virtual memory lets a process behave as if it had a large, private, contiguous memory of its own, while the operating system keeps only the parts currently in use in physical RAM and the rest on disk. It is built on paging, explained in Memory Management: because pages can live in any frame, they can also live in no frame at all until needed. This note covers how missing pages are brought in, what that costs, how the TLB and multi-level page tables keep translation fast and small, and what happens when memory runs short: thrashing.

Why virtual memory

Programs rarely need all their code and data at once. Error handlers, rarely used features and oversized arrays sit untouched. Virtual memory exploits this:

• A program can be larger than physical memory.
• More processes fit in memory at once, raising CPU utilization and throughput.
• Programs start faster, because less has to be read from disk.
• Sharing is cheap: shared libraries are mapped into many processes, and after fork() parent and child share pages copy-on-write until one of them writes.
• Files can be memory-mapped, read and written as ordinary memory.

It works because of locality of reference: in any short period a program touches a small set of pages (a loop's code, the array it is scanning, the top of the stack), and that set changes slowly.

Demand paging

With demand paging, a page is loaded only when it is first referenced. Each page-table entry has a valid-invalid bit: valid means the page is in memory, invalid means it is either not part of the process or not loaded yet. Pure demand paging starts a process with no pages at all and faults in every one as it is touched.

Handling a page fault

When a process touches a page marked invalid, the MMU raises a page fault trap and the OS brings the page in:

1. The process executes load M, and M lies in page 3. The MMU finds entry 3 marked invalid (i): the page is not in memory.
2. The invalid bit raises a page fault, a trap into the operating system. It checks the process's tables: page 3 is a legal page kept on the backing store, so this is not a segmentation fault.
3. The OS takes a free frame, frame 5. With none free, a replacement policy would choose a victim, written back to disk first if its dirty bit is set.
4. It schedules a disk read of page 3 into frame 5. The read takes milliseconds, so the process waits and the CPU runs another process meanwhile.
5. When the read completes, the OS writes frame 5 into entry 3 and sets its bit to valid (v).
6. The instruction that faulted is restarted from the beginning. This time entry 3 is valid, the translation gives frame 5, and the load completes as if nothing had happened.

If no frame is free, a replacement policy picks a victim frame first, and the victim is written back to disk only if it has been modified (its dirty bit is set). A fault that needs a disk read is a major fault; one resolved without I/O, for example a page already in memory for another process, is a minor fault. Choosing the victim is the subject of Page Replacement Algorithms.

Cost of a page fault

Let p be the page-fault rate (0 ≤ p ≤ 1). Then:

Effective access time = (1 − p) × memory access time + p × page-fault service time

Take a memory access of 200 ns and a page-fault service time of 8 ms (8,000,000 ns), dominated by the disk:

• EAT = (1 − p) × 200 + p × 8,000,000 = 200 + 7,999,800 × p ns.
• With one fault in every 1,000 accesses (p = 0.001): EAT = 200 + 7,999.8 = 8,199.8 ns, about 41 times slower than memory.
• To keep the slowdown under 10%, EAT must stay below 220 ns: 7,999,800 × p < 20, so p < 0.0000025, fewer than one fault in about 400,000 accesses.

The lesson interviewers want: the fault rate must be extremely low, so the replacement policy and the number of frames per process matter enormously.

The TLB and effective access time

The page table lives in memory, so a naive translation costs one memory access for the page-table entry and another for the data. The translation look-aside buffer (TLB) is a small, fast associative cache, typically tens to a few thousand entries, holding recent page → frame translations. On a TLB hit the frame number comes straight from the TLB; on a miss the hardware or the OS walks the page table and then caches the translation. Entries are tagged with an address-space identifier on many CPUs, so a context switch need not flush the whole TLB.

With TLB lookup time t, memory access time m and hit ratio h, for a single-level page table:

EAT = h × (t + m) + (1 − h) × (t + 2m)

1. Page 2 is in the TLB, a hit: the frame number, 6, comes straight out of the TLB and only the data itself is read from memory, 20 + 100 = 120 ns.
2. Page 7 is not in the TLB, a miss. The page table, itself in memory, is read for frame 3 (one access), the translation replaces page 5, the least recently used entry, and then the data is read: 220 ns.
3. On average, with 98% of lookups hitting, an access costs 122 ns: within 22% of a bare memory access, against 200 ns with no TLB at all.

Worked example, with t = 20 ns and m = 100 ns, so a hit costs 120 ns and a miss 220 ns:

A 98% hit ratio brings the cost within 22% of a bare memory access, and the deeper page table hardly matters because misses are rare. Some textbooks treat the TLB lookup as free (t = 0); then the 0.80 case is 0.80 × 100 + 0.20 × 200 = 120 ns. Read which convention a question uses.

Multi-level page tables

A 32-bit address space with 4 KB pages needs 2²⁰ page-table entries; at 4 bytes each that is 4 MB per process, nearly all describing addresses the process never uses. The fix is to page the page table itself.

In a two-level scheme, the 32-bit address splits into 10 + 10 + 12 bits: the top 10 index the outer table, the next 10 an inner table, and the low 12 are the offset in the page.

1. The 32-bit address splits into three fields: the top 10 bits index the outer table (p1 = 1), the next 10 an inner table (p2 = 3), and the low 12 are the offset in the 4 KB page (d = 0xABC = 2748).
2. Entry 1 of the outer table points to an inner table. The outer table has 1,024 entries of 4 bytes, so it fills exactly one 4 KB page.
3. Entry 3 of that inner table holds the frame, 9; the offset is appended unchanged, giving 39612. On a TLB miss that walk costs one memory access per level.
4. The saving: an inner table exists only where the process has memory. 8 MB of code and data use outer entries 0 and 1, the 4 MB stack entry 1023, so 3 inner tables plus the outer one cost 16 KB instead of 4 MB.

The outer table is 1,024 × 4 B = 4 KB, and each inner table is also 4 KB and maps 4 MB of address space. Inner tables are allocated only for regions in use. A process with 8 MB of code and data at the bottom of its space and a 4 MB stack at the top needs one outer table and 2 + 1 = 3 inner tables: 4 × 4 KB = 16 KB instead of 4 MB.

The price is one memory access per level on a TLB miss. x86-64 uses four levels of 9 bits each over 48-bit virtual addresses (4 × 9 + 12 = 48), and newer processors support five levels for 57-bit addresses, which is only practical because TLB hit ratios are high. Alternatives for very large address spaces are hashed page tables and inverted page tables, which keep one entry per physical frame instead of per virtual page.

Thrashing

If a process does not have enough frames for the pages it is actively using, it faults, evicts a page it needs again moments later, faults again, and so on. When the system as a whole spends more time servicing page faults than executing, it is thrashing.

The classic way it starts:

1. Processes have too few frames, so the page-fault rate rises.
2. They queue for the paging disk, so CPU utilization drops.
3. The long-term scheduler sees an idle CPU and admits more processes.
4. Each new process takes frames from the others, so the fault rate rises further.

Plotted against the degree of multiprogramming, CPU utilization climbs, peaks, then falls off sharply: that cliff is thrashing. The cure is to give each process the frames it needs, and to reduce the number of processes in memory, by suspending some, when there are not enough frames for all. Local replacement, where a process may evict only its own pages, keeps one thrashing process from dragging others down, though it does not cure that process.

The working-set model

The working set WS(t, Δ) of a process is the set of distinct pages it referenced in its last Δ references, the working-set window. It approximates the process's current locality.

Worked example with Δ = 4 and this reference string:

1. At time 4 the window holds 1 2 3 1: the working set is {1, 2, 3}, size 3. The process is still in its first locality, pages 1 to 3.
2. At time 5 the window holds 2 3 1 2: the working set is {1, 2, 3}, size 3.
3. At time 6 the window holds 3 1 2 4: the working set is {1, 2, 3, 4}, size 4. Page 4 enters, so the set grows while the old locality is still in the window.
4. At time 7 the window holds 1 2 4 4: the working set is {1, 2, 4}, size 3. It shrinks: page 3 fell out of the window.
5. At time 8 the window holds 2 4 4 4: the working set is {2, 4}, size 2. It shrinks: page 1 fell out of the window.
6. At time 9 the window holds 4 4 4 5: the working set is {4, 5}, size 2. Page 5 enters as page 2 leaves: the locality is moving.
7. At time 10 the window holds 4 4 5 5: the working set is {4, 5}, size 2.
8. At time 11 the window holds 4 5 5 4: the working set is {4, 5}, size 2.
9. At time 12 the window holds 5 5 4 5: the working set is {4, 5}, size 2. Frames for these pages are all it needs now.

The working set shrinks and moves as the process settles into a new locality. If the window is too small it misses part of the locality; if too large it spans several; an infinite window is every page ever touched.

Let WSSᵢ be the working-set size of process i and D = Σ WSSᵢ the total demand for frames. If D exceeds the number of available frames, some process lacks its working set and thrashing follows, so the OS suspends a process and gives its frames to the others. Keeping exact working sets is expensive, so systems approximate them with reference bits sampled on a timer.

A more direct control is page-fault frequency (PFF): set an upper and a lower bound on each process's fault rate. Above the upper bound, give the process more frames; below the lower bound, take some away; if no frames are free, suspend a process.

Common mistakes

• Treating every page fault as an error. Most are normal demand paging; only an access to an address outside the process ends in a segmentation fault.
• Forgetting the dirty bit: a clean victim page need not be written back, which halves the cost of that fault.
• Writing EAT with a TLB miss costing t + m instead of t + 2m for a single-level page table: a miss reads the page table and then the data.
• Saying multi-level page tables make translation faster. They save memory; a TLB miss gets slower, one access per level.
• Saying more processes always means better CPU utilization. Past the thrashing point, utilization falls.
• Confusing the working set with the resident set: the working set is what the process recently used, the resident set is what happens to be in memory.

Interview questions

What are the steps in handling a page fault? Trap to the OS, check the reference is legal, find a free frame or evict a victim (writing it back if dirty), read the page from disk while another process runs, update the page table and valid bit, then restart the faulting instruction.

How does the TLB reduce effective memory access time? It caches recent page-to-frame translations, so a hit skips the page-table read. With a 98% hit ratio, a 20 ns TLB and 100 ns memory, the average access is 122 ns instead of 200 ns without a TLB.

What causes thrashing and how do you stop it? The total working sets of the running processes exceed physical memory, so processes keep stealing each other's active pages. Stop it by reducing the degree of multiprogramming, using the working-set model or page-fault frequency to give each process enough frames, and using local replacement.

What is the difference between virtual memory and physical memory? Physical memory is the installed RAM. Virtual memory is the address space each process sees, which can be larger than RAM; it is mapped onto RAM page by page, with the rest kept on disk.

What is copy-on-write? After fork(), parent and child share the same physical pages, marked read-only. Only when one of them writes to a page does the kernel copy that page, so a child that immediately calls exec() copies almost nothing.

Why is the effective access time so sensitive to the page-fault rate? In the textbook figures a fault costs 8 ms against 200 ns for a memory access, 40,000 times more, so even one fault in a thousand accesses makes memory about 41 times slower on average. Only fault rates of a few per million accesses keep the overhead small.

Next, read Page Replacement Algorithms, or test yourself with the Operating Systems (Intermediate) skill test.