Demand Paging in Operating Systems: Page Faults, Worked Examples and Exam Traps

Learn demand paging through a complete page-fault restart, a FIFO frame trace and effective access time calculations, then test yourself on common conceptual traps.

KnowledgeGate Team

Exam prep & CS education

Updated 15 Nov 20266 min read
Demand Paging in Operating Systems: Page Faults, Worked Examples and Exam Traps

Demand paging sounds like ordinary paging, but the key question is whether a legal virtual page is in RAM when referenced. An absent page causes a controlled trap that can load it and restart the instruction, not automatically an invalid-address error. For virtual address 13,572, 4 KiB pages produce page 3, which loads into frame 9; a 12-reference trace runs through three FIFO frames; and access time uses 100 ns memory and an 8 ms faulting reference. The broader CS Fundamentals for Exams & Placements category places this mechanism beside the rest of operating-systems memory management.

Demand paging: the idea that changes ordinary paging

Paging divides virtual space into fixed-size pages and physical memory into equal-size frames. Demand paging brings a page into RAM only when a reference needs it; eager loading tries to load pages earlier. A virtual page belongs to the process, a frame is a RAM slot, the page table stores mapping and status, backing store holds non-resident contents, and a page fault gives the OS control when a legal page is absent. Swapping can broadly mean moving memory contents, but demand paging normally works page by page instead of moving a whole process per fault. It can reduce startup I/O and initial RAM use, but faults may require allocation, replacement and storage I/O. The earlier Memory management in OS: paging and segmentation explained owns the foundation, including TLBs and multilevel tables. The narrower task here is to classify a recoverable fault, follow the page-in restart, and measure its cost.

Read page-table state before declaring a page fault

Ask three questions: is the page legal, is the attempted operation permitted, and is the page present in RAM? Textbooks overload names such as valid, so neutral labels are safer.

State

Example PTE information

Result

1

legal=yes, read=yes, present=yes, frame=9

Translate normally

2

legal=yes, read=yes, present=no, backing slot=B17

Recoverable page-fault path

3

legal=no

Invalid-address exception, not a demand load

4

legal=yes, write=no, attempted operation=write

Protection fault, even if resident

Here, a page fault means a legal page is absent, not that every page-table exception is one. A Translation Lookaside Buffer miss can resolve from a present page-table entry without storage I/O.

Worked example: fault on virtual address 13,572

Page size is 4 KiB = 4,096 bytes. The CPU reads virtual address 13,572. Page 3 is legal and readable but absent, its backing slot is B17, and frame 9 is free. The instruction can be safely restarted.

  1. Split the address: VPN = floor(13,572 / 4,096) = 3. The offset is 13,572 - (3 x 4,096) = 1,284, which satisfies 0 <= 1,284 < 4,096.

  2. The entry is legal and readable but absent. Hardware traps to the OS and saves state for a retry.

  3. The OS reads page 3 from B17 into frame 9. The process blocks, and another ready process may run. After I/O, the OS records page 3 -> frame 9, marks it present, updates translation-cache state, and makes the process ready.

  4. The instruction restarts. Physical address = 9 x 4,096 + 1,284 = 36,864 + 1,284 = 38,148.

Without a free frame, replacement selects a victim, and a dirty victim may need write-back. With legal=no, the OS must not load B17.

Flow diagram: virtual address 13,572 splits into page 3 and offset 1,284, faults, loads into frame 9, then restarts at address 38,148.

Worked FIFO trace: nine faults in three frames

Use three empty frames F0, F1, F2, FIFO, and reference string 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2. Every page is legal and clean, with no pre-paging. Hits do not refresh FIFO order.

Step

1

2

3

4

5

6

7

8

9

10

11

12

Reference

2

3

2

1

5

2

4

5

3

2

5

2

H/F

F

F

H

F

F

F

F

H

F

H

F

F

Frames after reference

[2,-,-]

[2,3,-]

[2,3,-]

[2,3,1]

[5,3,1]

[5,2,1]

[5,2,4]

[5,2,4]

[3,2,4]

[3,2,4]

[3,5,4]

[3,5,2]

Evicted

none

none

none

none

2

3

1

none

5

none

2

4

There are 9 faults and 3 hits, so this trace has a 75% fault rate and 25% hit rate. Three faults fill the frames; later ones replace pages. Page 5 shows that a first touch can also cause replacement. Next, try the Virtual Memory and Demand Paging MCQs.

FIFO trace table for references 2,3,2,1,5,2,4,5,3,2,5,2 in three frames, showing 9 faults, 3 hits and the page evicted at each step.

Effective access time: align milliseconds and nanoseconds

This is an illustrative model. A normal reference takes 100 ns; a complete faulting reference takes 8 ms, including restart. Convert once: 8 ms = 8,000,000 ns. With p = 10^-6:

EAT = (1-p)(100) + p(8,000,000) = 0.999999 x 100 + 0.000001 x 8,000,000 = 99.9999 + 8 = 107.9999 ns, approximately 108 ns. That is about 8% above 100 ns.

For EAT <= 110 ns, 100(1-p) + 8,000,000p <= 110, so p <= 10 / 7,999,900 = 1.250016 x 10^-6, roughly one fault per 800,000 references.

If a clean fault totals 8 ms, a dirty-victim fault 14 ms, and 20% choose dirty victims, average fault time is 0.8 x 8 + 0.2 x 14 = 9.2 ms. At the same p, EAT = 99.9999 + 9.2 = 109.1999 ns. Real timing depends on the OS and hardware.

Locality, frame allocation and thrashing

Programs usually revisit a locality. Demand paging works when active pages fit in allocated frames. Repeatedly evicting pages needed again raises the fault rate. Thrashing means fault handling dominates useful progress, not simply that RAM is full.

One burst of faults does not prove thrashing. If a phase switch first touches three new pages and then reuses them in three available frames, the first three references fault and the later references hit; progress resumes after the locality is loaded. Thrashing instead keeps evicting pages that the active locality needs again. Controls include adding frames when possible, reducing multiprogramming, and using working-set or page-fault-frequency signals.

Exam traps and reliable repairs

  • Page fault means illegal address: check legality and residency separately.

  • TLB miss means page fault: inspect the page-table entry.

  • Offset changes after page-in: preserve the offset.

  • Execution continues with the next instruction: restart the faulting instruction.

  • FIFO hit refreshes age: it does not in basic FIFO.

  • Fault count equals replacement count: empty-frame faults count too.

  • 8 ms = 8,000 ns: it equals 8,000,000 ns.

  • Dirty and clean victims cost the same: add write-back only when the model states it.

Try these before reading the answers:

  1. With 4 KiB pages, split VA 20,000.

  2. If its page maps to frame 6, find the physical address.

  3. What follows from resident=no, legal=yes?

  4. What follows from resident=yes, write=no on a write?

  5. Find EAT for 100 ns, total fault time 8 ms, and p=10^-6.

Answers: (1) VPN 4, offset 3,616; (2) 6 x 4,096 + 3,616 = 28,192; (3) page-fault path; (4) protection fault; (5) about 108 ns.

Stable drills include address splitting, handler order, absence versus protection failure, replacement traces, EAT conversion, victim cost and locality pressure.

The short version and the next step

Demand paging loads a legal page when referenced but absent. Equal page and frame sizes preserve the offset. A recoverable fault saves state, loads the page, updates the mapping and restarts the instruction. Replacement is needed only without a free frame. Rare faults matter because milliseconds are millions of nanoseconds. As a check, rebuild VPN 3, offset 1,284, frame 9, physical address 38,148, then recover 9 faults, 3 hits and EAT of about 108 ns without looking back. Next, use GATE Guidance by Sanchit Sir or the placement-focused CS Fundamentals course for structured study.