Skip to main content

Page fault; allocation and replacement

Short answer

A page fault occurs when a referenced page is not in memory; the OS loads it, possibly replacing a page. Frame allocation methods include equal and proportional. For reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, FIFO causes 15 page faults, LRU 12, and Optimal 9.

What do you mean by page fault? Explain page allocation and page replacement algorithms with numerical example.

Page fault

A page fault is the trap generated when a process references a page that is not in main memory. The OS locates the page on disk, finds a free frame (or selects a victim page by a replacement algorithm), reads the page into it, updates the page table and restarts the instruction.

Page (frame) allocation

Decides how many frames each process gets from the total available.

  • Equal allocation: m frames divided equally among n processes (m/n each).
  • Proportional allocation: frames in proportion to process size. For process size s_i and total S: a_i = (s_i / S) × m. Example: m = 62 frames, sizes 10 and 127 pages: a₁ = 10/137 × 62 ≈ 4, a₂ = 127/137 × 62 ≈ 57.
  • Priority allocation: more frames to high-priority processes.
  • Global vs local replacement: global lets a process take a frame from any process; local only from its own frames.

Page replacement algorithms

When no frame is free, a victim page is chosen.

  • FIFO: replace the oldest page. Simple, can show Belady's anomaly.
  • Optimal: replace the page not used for the longest future time; best but not implementable.
  • LRU: replace the page unused for the longest past time; good approximation of optimal.
  • LFU/NFU, second chance (clock), aging are other methods.

Numerical example

Reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 frames (* = fault).

FIFO

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
F2   - 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
F3   - - 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
     * * * *   * * * * * *     * *     * * *

FIFO = 15 faults.

LRU

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
F2   - 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
F3   - - 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
     * * * *   *   * * * *     *   *   *

LRU = 12 faults.

Optimal

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
F2   - 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
F3   - - 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
     * * * *   *   *     *     *       *

Optimal = 9 faults.

Summary: FIFO 15, LRU 12, Optimal 9 page faults.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Operating System chapter 4 questions →