Virtual Memory in Operating Systems: Paging, TLB and Page Replacement with Worked Examples

Virtual memory is easier when paging, page tables, TLBs, faults and replacement form one path. A CPU generates an address, hardware translates it, and disk matters only when a legal page is absent. Memory Hierarchy and Virtual Memory: paging, the TLB, and address translation connects this mechanism to caches and locality; virtual-memory calculations begin by tracing each transition and writing every assumption.

Virtual memory in an operating system: the complete concept map

Virtual memory gives each process an address space. The memory-management unit maps virtual pages to non-contiguous physical frames. It is not extra RAM: backing storage holds non-resident pages and RAM holds resident pages.

Legal non-present pages can be fetched; invalid or protected references are errors. The path is virtual address to TLB; page table on a miss; frame plus unchanged offset if present; otherwise fault, fetch or replacement, PTE and TLB update, then restart. The wider GATE category connects this concept to preparation across subjects.

Paging and address translation: a fully worked 32-bit example

With a 32-bit virtual address and 4 KiB = 2^12-byte pages, the offset needs 12 bits and the virtual page number (VPN) needs 32 - 12 = 20 bits. The virtual space has 2^20 pages. Translation replaces the VPN with a frame number and keeps the offset.

For virtual address 0x12345ABC:

1. Split it into VPN = 0x12345 and offset = 0xABC = 2748 decimal.

2. PTE[0x12345] is present and gives frame 0x02F7A = 12154 decimal.

3. The frame base is 0x02F7A000.

4. Hexadecimal concatenation gives 0x02F7A000 + 0xABC = 0x02F7AABC.

5. The decimal check is 12154 x 4096 + 2748 = 49,782,784 + 2748 = 49,785,532.

If the present bit were 0, translation would stop with a page fault; the CPU must not use a stale frame field. Before moving on, repeat the split with a fresh address and verify that only the VPN changes.

Page tables: size, levels and the bits inside a PTE

A single-level table in this model has 2^20 PTEs. At 4 bytes each, it occupies 2^20 x 4 = 4,194,304 bytes = 4 MiB per process; one hundred tables need 400 MiB. Real architectures vary.

A two-level split can use 10-bit directory | 10-bit second-level index | 12-bit offset. The directory and each lower table are 2^10 x 4 bytes = 4 KiB. With three lower tables, storage is 4 KiB + 3 x 4 KiB = 16 KiB, excluding metadata, instead of 4 MiB.

Multilevel tables avoid unused lower levels. An inverted table keeps roughly one entry per frame but complicates lookup. Larger pages extend TLB reach and shrink tables but may increase internal fragmentation. PTEs store frame number, present, permissions, referenced and dirty bits; layouts vary.

TLB hits, TLB misses and page-fault effective access time

Assume serial 10 ns TLB lookup, 100 ns memory access, 95% hit ratio, one-level table, no overlap or fault. A hit costs 10 + 100 = 110 ns; a resident miss costs 10 + 100 + 100 = 210 ns. Thus:

EAT = 0.95 x 110 + 0.05 x 210 = 104.5 + 10.5 = 115 ns.

Now add demand paging as a separate event. With normal access 115 ns, fault probability p = 10^-6, and total fault service 8 ms = 8,000,000 ns:

EAT = (1 - p) x 115 + p x 8,000,000 = 122.999885 ns, about 123 ns.

At p = 10^-4, it becomes 914.9885 ns, about 7.96 times 115 ns. A TLB miss can find a present PTE, so it is not a page fault. Virtual Memory & Demand Paging MCQs (GATE OS) reinforces the distinction.

Page faults and page replacement: trace FIFO, LRU and Optimal

When hardware finds present=0, it traps. The OS verifies the reference, locates the page on backing storage, and uses a free frame or chooses a victim. It writes a dirty victim, reads the requested page while the process blocks, updates the frame table and PTE, removes any stale TLB entry, then restarts the instruction. Invalid addresses and permission failures are errors, not demand-page fetches.

Now use 3 frames and reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Each three-character state lists the three frame slots; - is empty.

FIFO removes the oldest loaded page; LRU removes the least recently used. Optimal removes the page whose next use is farthest away, giving the benchmark 7 faults, but an online system cannot know future references. Clock, or Second Chance, uses the reference bit to approximate LRU. Practise with Page Replacement Algorithms MCQs: FIFO, LRU, Optimal.

Locality, frame allocation and thrashing

Temporal locality reuses recent items; spatial locality accesses nearby items. A resident set is a process's pages in RAM. Too few frames cause repeated eviction and sustained excessive paging, or thrashing. Admitting more processes can worsen it.

With working-set window Delta = 6, P's 1, 2, 3, 2, 4, 1 gives WSS(P) = {1,2,3,4}, needing 4 frames. Q's 5, 6, 5, 7, 6, 8 gives WSS(Q) = {5,6,7,8}, also needing 4. Demand is D = 4 + 4 = 8; 7 frames cannot hold both sets because D > 7.

Responses include reducing multiprogramming, adding frames, and using working-set or page-fault-frequency feedback. In an illustrative PFF policy, above 8 faults per 100 references is high and below 2 is low. P at 12/100 needs help; Q at 1/100 is a reclaim candidate. These thresholds are not universal.

How GATE-style and interview questions test virtual memory, plus common traps

Useful practice formats ask you to split addresses, size tables, calculate TLB effective access time, distinguish misses from faults, trace replacement, identify PTE bits or diagnose thrashing. Interviews also test the trade-offs behind a correct result.

Write sizes as powers of two; calculate offset bits = log2(page size); preserve the offset; convert units carefully; record every frame state; classify the event as a TLB miss, legal non-present page, invalid address or protection fault.

Virtual memory: the short version and next step

Paging splits the virtual address; the TLB and page table translate it; absent legal pages fault; replacement makes room; locality determines progress or thrashing. Keep four checks: 0x12345ABC -> 0x02F7AABC, TLB-only EAT = 115 ns, replacement faults 10 / 9 / 7, and working-set demand 8 > 7. For a wider sequence, use GATE Guidance by Sanchit Sir. Redraw the translation, then trace the string unaided.