Virtual memory and demand paging
Virtual memory allows a program to use more memory than physical RAM by presenting a uniform virtual address space mapped to physical frames and loading pages on demand (demand paging).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Virtual memory and demand paging let engineers run large programs, support memory protection and simplify programming by giving each process its own large virtual address space even when physical RAM is smaller. An operating-system engineer implements and tunes demand-paging and page replacement to improve performance, reduce I/O, and avoid thrashing. Common page-replacement algorithms to know: Optimal (MIN), Least Recently Used (LRU), First-In First-Out (FIFO), and Clock/Second-Chance; be able to state that Belady’s anomaly (more frames can increase faults) can occur with FIFO but not with stack algorithms like LRU and OPT.
Key ideas
Page table: a per-process data structure that maps each virtual page number (VPN) to either a physical frame number (PFN) and status bits, or to an indication that the page is not resident (on disk). Each page table entry (PTE) contains at least: valid/invalid (present) bit, frame number (if valid), protection bits (read/write/execute), and dirty/reference bits used by replacement algorithms.
Translation Lookaside Buffer (TLB): a small, fast hardware cache that holds recent virtual-to-physical translations (VPN→PFN) to avoid a full page-table lookup each memory reference. A TLB hit means translation found in the TLB; a TLB miss means it must consult the page table (and possibly update the TLB).
Demand paging: do not load pages into physical memory until the process actually references them. A page is loaded from secondary storage (swap or file) only when a memory reference causes a page fault.
Page fault: an exception raised by the CPU when a referenced virtual page is not resident (invalid PTE). The OS handles the fault: select a free frame (or choose a victim frame and write it back if dirty), read the needed page from disk into the frame, update the page table and TLB, then resume the process. If the reference is illegal (e.g., access to an invalid address), the OS may terminate the process. Distinguish minor (soft) faults, which can be satisfied without disk I/O (e.g., zero-fill-on-demand or page already cached), from major (hard) faults, which require disk I/O.
Swap space (swap area): reserved secondary storage (disk) area used to store pages that are not in RAM. A page may also be backed by a file (memory-mapped file).
Resident set: the set of pages of a process currently in physical memory. The working set (W(t, Δ)) of a process is the set of pages referenced in the time window (t - Δ, t]; the working-set model helps limit resident set size and reduce thrashing. In practice Δ is often measured in a number of recent memory references rather than wall-clock time; related policies include working-set allocation and page-fault frequency (PFF) control, and frame allocation can be local or global.
Copy-on-write (COW): an optimization for process creation (fork). Parent and child share read-only pages. On the first write to a shared page, the OS makes a private copy (page fault triggers copy) and updates mappings.
Thrashing: when a process or the system spends most CPU time handling page faults rather than doing useful work. Thrashing occurs when the working set does not fit in RAM.
Exact statements and derivations commonly required in exams
Page number and offset extraction (for an address space of size 2^m and page size 2^p):
- A virtual address of m bits is divided: high (m - p) bits = Virtual Page Number (VPN), low p bits = page offset. Assumption: page size is a power of two.
- Draw: a horizontal rectangle labelled "virtual address (m bits)". Split into two fields left: "VPN (m-p bits)" and right: "offset (p bits)". Similarly draw physical address with "PFN" and "offset" aligned.
Page table size calculation (definition):
- If virtual address space has V bytes and page size is P bytes, number of virtual pages = V / P. If each PTE is S bytes, page table size = (V / P) · S. State assumptions: single-level page table; no multi-level or inverted page tables.
Effective access time (EAT) derivation with demand paging and TLB:
- Define: memory access time = m (time to read/write one word from RAM). TLB lookup time = t_tlb (often part of m or small additional). Page-fault rate = p (fraction of memory references that cause page faults). Page-fault service time = s (time to handle a page fault, including I/O). Then EAT = (1 - p)·(cost when page is resident) + p·(cost when page fault). For simple model without TLB: resident cost = m; fault cost = s + m (after service, memory access completes). So: EAT = (1 - p)·m + p·(s + m) = m + p·s. If TLB is present, include TLB hit/miss effects: further derivation depends on whether page is resident (TLB hits reduce cost). Clearly state assumptions when using formula.
Demand paging sequence diagram to draw and label (for exams):
- Draw boxes left to right: CPU -> MMU/TLB -> Page table -> RAM; also draw OS page-fault handler that talks to Disk (swap). On a page fault path, label steps: trap → OS chooses victim → if victim dirty write to disk → read faulting page from disk → update PTE → invalidate any stale TLB entries for affected VPN(s) and insert/update the new mapping → return to user.
Assumptions to state in answers: page size power-of-two; single-level page table unless multi-level asked; disk service times may be given; TLB associative behavior (full, set-associative) if relevant.
Formulas
Number_of_pages = V / P where V = virtual address space size (bytes), P = page size (bytes). Applies to single-level paging.
Page_table_size = (V / P) * S where S = size of one PTE (bytes). Units: bytes. Applies to single-level page table.
VPN = floor(virtual_address / P) offset = virtual_address mod P where P in bytes.
Effective_access_time = m + p * s where m = memory access time (seconds), p = page-fault rate (0 ≤ p ≤ 1), s = average page-fault service time (seconds). Assumes when a page fault occurs the cost is s plus the normal memory access cost; assumes no TLB or TLB costs included.
If TLB present and TLB lookup time is t_tlb, memory access time per reference when page resident and TLB hit is t_tlb + m. For TLB hit ratio h, simplified EAT (no page faults) is:
EAT_no_fault = h*(t_tlb + m) + (1-h)*(t_tlb + m + extra_page_table_walk_cost)
Including page faults, a common combined model is: EAT = (1-p)*[ h*(t_tlb + m) + (1-h)*(t_tlb + w + m) ] + p*(t_tlb + s + m), where w is the page-table-walk cost (e.g., w = k*m for a k-level page table).
Explain symbols and units after each formula in text of answer where used.
Worked examples
Example 1 — Effective access time with demand paging (numerical)
Given: memory access time m = 100 ns; page-fault service time s = 8 ms (8 × 10^6 ns); page-fault rate p = 10^-6 (one in a million references). Compute EAT.
- Write formula: EAT = m + p·s.
- Substitute numbers (convert to ns): m = 100 ns, s = 8,000,000 ns.
- Compute p·s = 10^-6 × 8,000,000 ns = 8 ns.
- EAT = 100 ns + 8 ns = 108 ns.
Final answer: EAT = 108 ns. This shows that with a very small page-fault rate, the large disk cost is amortized.
Example 2 — Page table size (numerical)
Given: 32-bit virtual address space (V = 2^32 bytes), page size P = 4 KB = 2^12 bytes, PTE size S = 4 bytes. Find number of pages and size of single-level page table.
- Number_of_pages = V / P = 2^32 / 2^12 = 2^(32-12) = 2^20 pages = 1,048,576 pages.
- Page_table_size = (number_of_pages) × S = 1,048,576 × 4 bytes = 4,194,304 bytes = 4 MB.
Final answer: 1,048,576 pages and a page table of 4 MB. Note: this is why multi-level paging or inverted page tables are used.
Common mistakes
- Omitting units when computing EAT (convert ms to ns or vice versa) leading to incorrect results by orders of magnitude.
- Not including the page-table-walk cost or TLB behavior when the question explicitly includes a TLB.
- Treating dirty and clean victim pages the same in service-time calculations; dirty pages require write-back time.
- Drawing translations: students forget to show the offset preserved when mapping VPN→PFN on diagrams.
For your exam
Common question types
- Definitions: define virtual memory, page, page fault, demand paging, working set, copy-on-write.
- Short notes: explain TLB, swap space, advantages of demand paging, thrashing and how working set model mitigates it.
- Derivations: derive EAT formula; show bit fields for VPN and offset; compute page-table size.
- Numericals: compute EAT given m, s, p; compute number of pages and page-table memory; compute memory required for multilevel page tables if asked.
- Diagrams: draw the page-fault handling sequence and label each step; draw layout of virtual and physical addresses with VPN/PFN and offset.
What a full-marks answer includes
- Clear definitions of all bolded terms used.
- Explicit statement of assumptions (page size, level of page table, whether TLB included). For derivations, show every algebraic step and unit conversions.
- For diagrams, draw boxes and arrows and label fields (VPN, offset, PFN) and the OS/disk interactions on a page fault.
- For numericals, show formula, substitute numbers with units, intermediate arithmetic, and final answer with unit and bolded result.
Quick check
- What two fields divide a virtual address for paged memory and why?
- Write the simple effective-access-time formula that includes page-fault rate p.
- Why does a 32-bit single-level page table with 4 KB pages often require multi-level paging?
Answers: 1) VPN (virtual page number) and offset — VPN selects the page; offset locates byte within page. 2) EAT = m + p·s (m = memory time, p = page-fault rate, s = page-fault service time). 3) Because number_of_pages = 2^20 (1,048,576) and with 4-byte PTEs the page table is 4 MB per process, which is large for RAM and motivates multi-level or inverted tables.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?