Demand paging, page faults and effective access time

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does the valid/invalid bit in a page-table entry tell? from Lesson 5.2.1
2. What does a TLB miss cost in single-level paging? from Lesson 5.2.2
3. What is the medium-term scheduler's job? from Lesson 1.1.2

1 · The Hook

A 500-page textbook, but today you only need chapter 3. You don't carry the whole book; you photocopy pages as you need them. Demand paging loads a page only when the program first touches it. Programs can be larger than RAM, more programs fit at once, and they start faster. The price: an occasional very slow page fault, which GATE turns into an effective-access-time question.

3 · Core Concept

Predict First — the answer

About 0.999 × 100 + 0.001 × 10,000,000 ≈ 10,100 ns: about 100 times slower than memory. Page faults must be very rare.

In plain words

Virtual memory lets a process use more memory than the RAM it actually has. Its pages live on disk, and only the ones in use are copied into frames. The page table's valid bit now means "this page is in memory". Touching a page that isn't in memory causes a page fault: the OS fetches it from disk, fixes the table, and runs the instruction again.

1. Demand paging

• Load a page only when it is first referenced (a "lazy" pager). Pure demand paging starts a process with no pages at all.
• Valid bit = 1: page in memory. Valid bit = 0: not in memory (or not part of the process).

2. What happens on a page fault

1. The access finds valid = 0 → trap to the OS.
2. The OS checks the reference: illegal → kill the process; legal but not in memory → continue.
3. Find a free frame (if none, choose a victim page to replace: Lesson 5.3.2).
4. Schedule a disk read of the page into the frame (the process waits; another runs).
5. When the read completes, update the page table (frame number, valid = 1).
6. Restart the instruction that caused the fault.

3. Effective access time with page faults

p = page-fault rate (0 ≤ p ≤ 1), ma = memory access time, s = page-fault service time: EAT = (1 − p) × ma + p × s. Example: ma = 100 ns, s = 10 ms = 10⁷ ns, p = 10⁻⁵ → 0.99999 × 100 + 10⁻⁵ × 10⁷ ≈ 200 ns (twice as slow as memory). To keep EAT ≤ 200 ns: 100 + p(10⁷ − 100) ≤ 200 → p ≤ about 10⁻⁵ (one fault per 100,000 accesses).

4. The dirty bit

When a victim page must be replaced, it is written back to disk only if it was modified (dirty bit = 1). So the service time depends on the victim: Average s = (fraction dirty) × s_dirty + (fraction clean) × s_clean. Example: 8 ms if clean, 20 ms if dirty, 70% dirty → 0.3 × 8 + 0.7 × 20 = 16.4 ms.

5. Copy-on-write

After fork(), parent and child share the parent's pages, marked read-only. Only when one of them writes to a page is that page copied. This makes fork() fast, especially when the child calls exec() at once.

4 · Visual

The six steps of handling a page fault. Step 4 is slow (milliseconds), so the process waits while another runs.

5 · Worked Examples

Example 1 Easy

ma = 200 ns, s = 8 ms, p = 0.001. EAT?

Solution

0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8000 = 8199.8 ns (≈ 8.2 µs).

Example 2 Medium

ma = 100 ns, s = 10 ms, and we want EAT ≤ 110 ns. Largest page-fault rate?

Solution

100 + p(10⁷ − 100) ≤ 110 → p ≤ 10 / 9,999,900 ≈ 1.0 × 10⁻⁶.

Example 3 GATE

Service time 8 ms if the victim is clean, 20 ms if dirty; 70% of victims are dirty; ma = 100 ns. Largest p with EAT ≤ 200 ns?

Solution

s = 16.4 ms = 16,400,000 ns. 100 + p(16,400,000 − 100) ≤ 200 → p ≤ 100 / 16,399,900 ≈ 6.1 × 10⁻⁶.

6 · GATE Traps

• Convert units: ms = 10⁶ ns.
• EAT formula weights the fault case with s (which already includes everything slow).
• A dirty victim adds a disk write before the read.
• An access to an illegal address is not served; the process is terminated.

7 · Memory Hook

"EAT = (1 − p)·ma + p·s; s is huge, so p must be tiny."

8 · Connect the Dots

Step 3 of a page fault needs a frame. When none is free, which page should be thrown out? The next lesson compares the replacement policies GATE asks about: FIFO, optimal and LRU, and a strange effect called Belady's anomaly.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — EAT

Memory access 100 ns, page-fault service time 10 ms, page-fault rate 10⁻⁵. Effective access time in ns (nearest integer)?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Dirty bit

Page-fault service takes 8 ms with a clean victim and 20 ms with a dirty one; 70% of victims are dirty. Average service time in ms?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Max fault rate

ma = 200 ns, s = 8 ms. Largest page-fault rate (in units of 10⁻⁶, 2 decimals) such that EAT ≤ 220 ns?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Steps

On a page fault, which step comes last?

1. (A) Restart the instruction that faulted
2. (B) Find a free frame
3. (C) Update the page table
4. (D) Read the page from disk

Q5 · MCQ · 1 mark(s) — Copy-on-write

Copy-on-write after fork() means:

1. (A) the parent is suspended
2. (B) the child cannot write
3. (C) pages are shared until one process writes to a page, which is then copied
4. (D) all pages are copied at fork time

10 · Rule Card

• Demand paging: load on first reference; valid bit = in memory.
• Page fault: trap → check → free frame (or victim) → disk read → update table → restart.
• EAT = (1 − p)·ma + p·s; ms = 10⁶ ns.
• Dirty victims must be written back; average s weighted by the dirty fraction.
• Copy-on-write makes fork() cheap.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

virtual memorydemand pagingpure demand pagingpage faultpage-fault handling stepspage-fault rateeffective access time with faultsdirty (modify) bitcopy-on-write