Virtual Memory Management

CSS Optional — Paper-II, Section-A · P-II.III.VI · Second-highest-yield numerical subtopic after Deadlocks — expect page-replacement, TLB, or multi-level page-table arithmetic almost every year.

1. Virtual Memory & Demand Paging

Virtual memory gives each process the illusion of a large, private, contiguous address space independent of installed RAM, by using disk (the swap area) as an extension of memory. Under demand paging, a page is loaded into a physical frame only when actually referenced; if a process accesses a page not currently resident, a page fault occurs: the OS traps, locates the page on disk, loads it into a free (or newly-evicted) frame, updates the page table, and resumes the process.

2. Page Replacement Algorithms

When memory is full and a new page must be brought in, a victim page must be evicted.

📐 FIFO/Optimal/LRU compared on one reference string, plus Belady's Anomaly, Clock, and frame-allocation numericals:

3. Thrashing

If the degree of multiprogramming is pushed too high, each process gets too few frames, so it page-faults almost continuously — the CPU spends nearly all its time swapping pages in/out and almost none executing real instructions. This collapse in useful throughput is thrashing, and it is precisely why "job size very low" or "page size very small" scenarios need careful trade-off analysis: smaller time slices/pages increase overhead relative to useful work.

4. Translation Lookaside Buffer (TLB)

The TLB is a small, fast associative cache inside the MMU holding recently used virtual-page → physical-frame translations, avoiding a full page-table walk on every memory access. On a TLB hit, translation is near-instant; on a TLB miss, the full (slower) page-table lookup happens, and the TLB is updated.

5. Multi-Level Page Tables

A single flat page table for a 32-bit address space with 4 KB pages needs 2^20 entries — wastefully large if most of a process's address space is unused. Multi-level (hierarchical) paging splits the VPN into multiple index fields, each indexing into a smaller table, and unused branches simply never get a second-level table allocated — trading one extra memory access per additional level for large space savings (a TLB is what makes this overhead acceptable in practice).

6. Page-Fault Handling — the Full Step-by-Step Sequence (a common "explain what happens on a page fault" essay question)

1. Hardware traps to the OS on referencing an invalid page-table entry.
2. OS checks whether the reference was valid (a legitimate page just not in memory) or truly illegal (out-of-bounds → terminate the process).
3. If valid, find a free frame (from a free-frame list, or by invoking a page-replacement algorithm to select a victim if none is free).
4. If the victim frame is "dirty" (modified), first write it back to disk.
5. Schedule a disk read to bring the needed page into the (now free) frame — this is a slow, blocking operation, so the OS context-switches to another ready process meanwhile.
6. When the disk I/O completes (an interrupt), update the page table (mark the page valid, record its new frame) and update the frame table.
7. Restart the instruction that caused the fault, this time succeeding.

Examiners sometimes ask you to name the hardware requirement this depends on: the CPU must be able to restart an interrupted instruction cleanly, which is non-trivial for instructions that modify several memory locations mid-execution (a worthwhile aside for a strong answer).

7. Copy-on-Write (COW) — how fork() is made cheap

Naively, fork() would need to copy the entire parent's address space for the child — expensive, and wasteful if the child immediately calls exec() anyway (see [Process Management]). Instead, COW lets parent and child initially share the same physical pages, marked read-only; only when either process attempts to WRITE to a shared page does the hardware trap, and the OS makes a private copy of just that one page for the writer. This is why fork() is cheap in practice despite conceptually duplicating an entire process.

8. Memory-Mapped Files

Rather than reading a file via explicit read()/write() system calls, a process can map a file directly into its virtual address space; ordinary memory reads/writes on that region are transparently translated by the OS into file I/O via the normal demand-paging machinery (a "page fault" on first access loads that part of the file; a "dirty" page is written back to the file, not swap). This unifies file I/O and memory management under one mechanism and is significantly faster for repeated access than repeated system calls.

9. Working Set Model (a rigorous framework for explaining/preventing thrashing)

A process's working set is the set of pages it has referenced in the most recent Δ (delta) time units — an approximation of "the pages it needs right now" based on the locality of reference. The OS tracks each process's working-set size; if the sum of all working sets exceeds available memory, the OS suspends a process (reducing the degree of multiprogramming) rather than let everyone thrash. This gives thrashing a precise, examinable definition: thrashing begins exactly when total working-set demand exceeds physical memory supply.

10. Inverted Page Table (an alternative to one page table per process)

Instead of one (potentially huge, mostly-empty) page table per process, an inverted page table keeps one system-wide table with one entry per physical frame, recording which (process-id, virtual page) currently occupies it. This dramatically reduces total page-table memory (proportional to physical RAM size, not to virtual address space size × number of processes) but makes lookups slower (a linear or hashed search is needed to find "which frame holds this process's page X," since the table is no longer indexed by virtual page number).

---

📐 Worked Numericals

Effective Memory Access Time with TLB (2021), LRU page-fault trace for a given reference string (2025 MCQ), multi-level page table sizing & translation (2025, 10 marks).

---

🎯 CSS Exam Angle

Whenever a question gives a reference string + frame count, examiners are testing whether you can maintain state correctly across both faults and hits — the #1 marks-losing mistake is forgetting to update recency/usage bookkeeping on a hit. For TLB/EMAT formulas, always state the formula explicitly before substituting numbers (partial marks are awarded for a correct formula even with an arithmetic slip).

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• Optimal needs future knowledge — impossible to implement live. Any option claiming Optimal is "used in real operating systems" is wrong; it is a benchmark only.
• FIFO can suffer Belady's Anomaly (more frames → more faults); LRU never does. This is a favourite true/false distractor.
• A TLB miss still requires the full page-table walk — the TLB doesn't replace the page table, it caches its results.
• Smaller pages reduce internal fragmentation but increase page-table size and page-fault/TLB-miss frequency — don't treat "smaller is always better."
• A page fault is not always an error — it's only illegal if the reference is outside the process's logical address space; otherwise it's the normal demand-paging mechanism working as designed.
• Copy-on-Write defers copying, it never avoids it entirely — the private copy still happens, just lazily, only for pages actually written to.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q2(c) · 6 marks

Q. Describe the functioning of virtual memory. Comment on the management of virtual and physical memory by an operating system.

Ans.

• Virtual memory lets programs use a large logical address space, larger than the physical RAM, by keeping only the needed parts in RAM and the rest on disk (swap space).
• Working: the program's address space is divided into pages, and RAM into frames. A page table maps pages to frames. When a program refers to a page that is not in RAM, a page fault occurs. The OS finds a free frame (or chooses a victim with a replacement policy such as LRU), loads the page from disk and restarts the instruction (demand paging).
• Management by the OS: page tables per process, a TLB to speed up translation, page replacement, frame allocation, a swap area, and protection and sharing between processes.
• Benefits: large programs can run, more programs fit in memory at once, and each process is isolated. Cost: thrashing if there are too many page faults.

2018 · Paper-II · Q4(B) · 6 marks

Q. In paging, memory addresses are 32 bits: 20 bits for the virtual page number and 12 bits for the offset. How many virtual pages are there and what is the size of each page? For the virtual address 0x7589 and a page table entry containing 0x900DF, find the virtual page number, offset and physical address.

Ans.

• Number of virtual pages = 2²⁰ = 1,048,576.
• Page size = 2¹² = 4096 bytes (4 KB).
• Virtual address 0x00007589: the low 12 bits are the offset, so offset = 0x589 and VPN = 0x00007 (the top 20 bits).
• Page table entry = 0x900DF is the physical frame number.
• Physical address = frame number followed by the offset = 0x900DF589.

2020 · Paper-II · Q3(b) · 6 marks

Q. What is the difference between simple and virtual memory paging? Also explain the purpose of the translation lookaside buffer.

Ans.

• Simple paging: the whole process must be loaded in memory (all its pages in frames) before it runs. Pages are not swapped out during execution.
• Virtual-memory paging (demand paging): only the needed pages are loaded, and others stay on disk. Page faults bring pages in on demand, so a process can be larger than physical memory.
• TLB: a small, fast associative cache of recent page-table entries. Every memory access would otherwise need two accesses (page table, then data). The TLB stores page → frame mappings, so on a hit the translation takes no extra memory access. A good hit ratio (about 98%) makes paging almost as fast as direct addressing.

2021 · Paper-II · Q4(a)(b) · 3 and 4 marks

Q. (a) Calculate the effective memory access time with TLB hit ratio 85%, TLB access 20 ns and memory access 115 ns. (b) A logical address of 31 bits and a physical address of 22 bits: what are the total logical and physical address spaces?

Ans.

• (a) Hit: TLB + memory = 20 + 115 = 135 ns. Miss: TLB + page table (in memory, 115 ns) + memory = 20 + 115 + 115 = 250 ns.

  EMAT = 0.85 × 135 + 0.15 × 250 = 114.75 + 37.5 = 152.25 ns.

• (b) Logical address space = 2³¹ bytes = 2 GB. Physical address space = 2²² bytes = 4 MB.

2025 · Paper-II · Q5(b) · 10 marks

Q. A multi-level scheme uses virtual addresses split into Virtual Page # (10 bits), Virtual Page # (10 bits) and Offset (12 bits). Physical addresses are Physical Page # (20 bits) and Offset (12 bits). Page table entries are 32 bits. (i) How big is a page? (ii) What is the maximum virtual address space? (iii) What is the maximum physical memory supported? (iv) Sketch the page-table format and the address resolution, with no TLB or cache.

Ans.

• (i) Page size = 2¹² = 4096 bytes (4 KB).
• (ii) Virtual address space = 2^(10+10+12) = 2³² = 4 GB.
• (iii) Physical memory = 2^(20+12) = 2³² = 4 GB.
• (iv) Page tables: each table has 2¹⁰ = 1024 entries × 4 bytes = 4 KB, exactly one page.

Virtual address:  | VPN1 (10) | VPN2 (10) | Offset (12) |
Step 1: page-directory base register + VPN1 → entry giving the address of a second-level table
Step 2: second-level table + VPN2 → PTE containing the 20-bit physical page number (and valid, dirty bits)
Step 3: physical address = physical page number (20) | offset (12)

• Memory accesses without a TLB: 3 (the first-level table, the second-level table, then the data). Only the tables that are in use need to be in memory, which saves space.

MCQs

2026 P-II · Q19. The part of the OS which decides what to do when main memory is full is:

• (A) Process Scheduler
• (B) Memory Manager ✅
• (C) File System
• (D) None of these
• Answer: (B) Memory Manager.
• Why: the memory manager allocates memory and, when it is full, decides which pages or processes to swap out to disk (page replacement). The scheduler chooses which process gets the CPU, and the file system manages files.