Paging and Segmentation

Here’s a clean, exam-oriented explanation of Paging and Segmentation with just enough depth to score well:

🔹 Paging

Definition

Paging is a memory management technique where:

Logical memory → divided into fixed-size pages

Physical memory → divided into frames (same size as pages)

A page can be loaded into any free frame.

Address Structure

Logical address =
👉 Page Number (p) + Offset (d)

Page number → used to find frame via page table

Offset → exact location inside the page

Advantages

Eliminates external fragmentation

Efficient use of memory

Simple allocation process

Disadvantages

Internal fragmentation (last page may not be full)

Page table consumes memory

Slight delay due to address translation

🔹 Segmentation

Definition

Segmentation divides memory based on logical parts of a program, such as:

Code

Data

Stack

Each segment has variable size.

Address Structure

Logical address =
👉 Segment Number (s) + Offset (d)

Segment number → index in segment table

Each entry contains:

Base (starting address)

Limit (length of segment)

Advantages

Reflects real program structure

Supports modular programming

Easier debugging and protection

Disadvantages

External fragmentation

More complex than paging

Paging vs Segmentation

Feature	Paging	Segmentation
Size of blocks	Fixed	Variable
Basis	Physical memory	Logical structure
Fragmentation	Internal	External
Table used	Page table	Segment table
User visibility	Invisible	Visible

Simple Analogy

Paging → Cutting a book into equal pages and storing anywhere

Segmentation → Dividing a book into chapters (different sizes)

Final Point

Modern operating systems often use a combination of both (segmented paging) to achieve:

Efficiency (paging)

Logical organization (segmentation)

Virtual Memory:

🔹 Virtual Memory

Virtual memory is a memory management technique that allows a computer to run programs larger than its physical RAM by using a portion of secondary storage (like a hard disk or SSD) as an extension of main memory.

Key Idea

Instead of loading the entire program into RAM:

Only the required parts are loaded

The rest stays on disk and is brought into memory when needed

How it Works

Programs are divided into pages (in paging systems)

RAM holds only some pages

When a needed page is not in RAM → page fault occurs

The operating system loads that page from disk into memory

Important Concept: Page Fault

A page fault happens when:

The CPU tries to access data not currently in RAM

OS fetches it from secondary storage

👉 Too many page faults can slow down the system (called thrashing)

Advantages

Allows execution of large programs

Better memory utilization

Supports multiprogramming (many programs at once)

Reduces need for large physical RAM

Disadvantages

Slower than RAM (disk access is slower)

Excessive page faults reduce performance

Requires complex management

Demand Paging and Page Replacement Algorithms (FIFO, LRU, Optimal)

In an operating system that uses paging, a page replacement algorithm is needed when a page fault occurs and no free page frame is available. In this case, one of the existing pages in memory must be replaced with the new page.

🔹 Demand Paging

Definition

Demand paging is a technique in virtual memory where:

Pages are loaded into memory only when they are needed (on demand)

Unused pages remain on disk

Working Steps

CPU requests a page

If page is in memory → Hit ✅

If not → Page Fault ❌

OS loads the required page from disk into RAM

If memory is full → a page must be replaced

Advantages

Reduces memory usage

Faster program start

Efficient for large programs

Disadvantages

Page fault overhead

Can lead to thrashing (too many faults)

🔹 Page Replacement Algorithms

When memory is full, the OS must decide which page to remove.

1️⃣ FIFO (First-In, First-Out)

Idea

Remove the page that was loaded first

Example

Pages in order: A → B → C
👉 Replace A first

✅ Pros

Simple to implement

Cons

May remove frequently used pages

Suffers from Belady’s Anomaly (more frames → more faults)

2️⃣ LRU (Least Recently Used)

Idea

Replace the page that has not been used for the longest time

Example

If A was used long ago and B recently → replace A

Pros

Better performance than FIFO

Based on actual usage

Cons

Requires tracking usage history

More complex

3️⃣ Optimal Page Replacement

Idea

Replace the page that will not be used for the longest time in future

Example

If page C won’t be used for a long time → replace C

Pros

Gives minimum number of page faults (best possible)

Cons

Not practical (future knowledge required)

Used only for comparison and analysis

Comparison Table

Algorithm	Basis	Performance	Complexity	Practical Use
FIFO	Oldest page	Low	Simple	Yes
LRU	Least recently used	Medium	Moderate	Yes
Optimal	Future knowledge	Best	High	No (theoretical)

Key Terms

Page Fault → Page not found in memory

Hit → Page found in memory

Thrashing → Excessive page faults causing slowdown

Simple Analogy

FIFO → Queue (first person leaves first)

LRU → Remove the least recently used item

Optimal → Remove what you won’t need in future (if you could predict)