OSOperating Systems Learning StudioGuided notes + mapped practice
Question BankExam KitKnowledge Graph

Chapter 4

Page Replacement and Segmentation

Compare FIFO, Optimal, LRU, Second-Chance/Clock, NRU and contrast paging with segmentation.

Estimated time: 34 min

When RAM is full, replacement decides which page to remove; segmentation uses variable-sized logical parts.

Algorithm comparison and Belady's anomaly are high-value exam targets.

Replacement Strategies

From notes

Clear explanation

FIFO evicts oldest page, LRU evicts least recently used, Clock approximates LRU using reference bits, Optimal evicts farthest future use.

What it really means

Good replacement predicts what you will not need soon.

Key takeaway

Locality-aware policies usually reduce faults.

Segmentation Contrast

From notes

Clear explanation

Segmentation divides program by logical modules (code/data/stack) with variable sizes and independent protection.

What it really means

Segments follow how humans think about programs; pages follow hardware-friendly uniform blocks.

Key takeaway

Segmentation improves logical organization; paging improves allocation mechanics.

FIFO, LRU, Optimal: How to Decide Victim

Added clarity

Clear explanation

FIFO removes oldest loaded page, LRU removes least recently used page, and Optimal removes page used farthest in future.

What it really means

Victim page choice is a prediction problem: oldest history, recent history, or perfect future knowledge.

Example

For reference string 7,0,1,2,... with 3 frames, FIFO and LRU can produce different fault counts even with same inputs.

Key takeaway

Always show frame table step-by-step; final count alone is not enough.

Clock Algorithm Logic

Added clarity

Clear explanation

Clock keeps circular pointer over frames; if reference bit is 0, frame is replaced, otherwise bit is cleared and pointer moves forward until a 0-bit frame is found.

What it really means

Frames get a second chance before eviction.

Example

A recently touched page with bit=1 survives first pass; untouched page with bit=0 is selected as victim.

Key takeaway

Clock approximates LRU with simpler bookkeeping.

  • - Assuming FIFO always improves with more frames
  • - Using LRU without proper recent-use tracking
  • - Treating segmentation and paging as identical
  • - Optimal is benchmark, not practical
  • - FIFO can show Belady's anomaly
  • - LRU approximates locality principle
  • - Paging fixed-size, segmentation variable-size logical units
Page fault rate = (Number of page faults / Total references) x 100%

Exam lens for this topic

What evaluators usually expect in structured exam answers.

Must-use keywords

  • - FIFO
  • - LRU
  • - Optimal
  • - Belady's anomaly
  • - Segmentation

Answer flow

  • - Write algorithm replacement rule first
  • - Draw frame table row-by-row for reference string
  • - Count page faults and compute fault rate
  • - Compare result with one other algorithm

Diagram expectations

  • - Frame progression table

Repeated pattern: Reference string based page-fault numericals are asked repeatedly.

Practice Questions

  • Compute page faults for FIFO and Optimal with 3 frames for given reference string.

    Source: Winter 2023 Q4(C)

    Answer focus: Correct frame updates and fault counting.

  • Compute page faults for Optimal with 4 frames for long reference string.

    Source: Winter 2024 Q4(C) OR

    Answer focus: Future-look replacement correctness.

Practice from papers (end-of-topic set)

These paper questions map directly to this topic. Solve now, then compare your structure with linked topics.

Question Bank Linked Here

Open all questions

How to answer linked exam questions

Full question bank

Extra clarity files

These are clearly marked additions, separate from source notes.

Topic relation map

Prerequisites

Next topics

Related topics