Demand paging in Operating Systems - Deep Dive

Overview - Demand paging

What is it?

Demand paging is a memory management technique used by operating systems where pages of a program are loaded into physical memory only when they are needed, rather than all at once. This means that the system waits until a program tries to use a page before bringing it from disk into RAM. It helps save memory and speeds up program startup by avoiding loading unnecessary data. If a needed page is not in memory, a page fault occurs, triggering the system to load that page.

Why it matters

Without demand paging, programs would need to load all their data into memory before running, which wastes memory and slows down the system, especially when many programs run at once. Demand paging allows computers to run larger programs than the physical memory alone would allow and improves overall system efficiency. It makes multitasking smoother and reduces waiting times for users.

Where it fits

Before learning demand paging, you should understand basic memory concepts like RAM, virtual memory, and paging. After mastering demand paging, you can explore advanced topics like page replacement algorithms, thrashing, and memory management optimization techniques.

Mental Model

Core Idea

Demand paging loads only the parts of a program into memory when they are actually needed, saving space and time.

Think of it like...

It's like reading a book where you only open and read the pages you need instead of carrying the entire book everywhere.

┌───────────────┐       ┌───────────────┐
│ Program tries │──────▶│ Is page in    │
│ to access a   │       │ memory?       │
└───────────────┘       └───────────────┘
          │Yes                      │No
          ▼                         ▼
┌───────────────┐       ┌───────────────┐
│ Use page from │       │ Page fault:   │
│ memory       │       │ Load page from│
└───────────────┘       │ disk to memory│
                        └───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding virtual memory basics

Concept: Virtual memory allows programs to use more memory than physically available by using disk space as extra memory.

Virtual memory creates an illusion that each program has its own large, continuous memory space. The operating system divides this space into fixed-size blocks called pages. These pages can be stored either in physical RAM or on disk. This setup helps run large programs and multiple programs simultaneously.

Result

Programs can run without worrying about physical memory limits, and the system can manage memory more flexibly.

Understanding virtual memory is essential because demand paging relies on this concept to decide when and how to load pages.

2

Foundation

What is paging in memory management

Concept: Paging breaks memory into fixed-size blocks called pages to simplify memory allocation and management.

Instead of allocating memory in one big chunk, the OS divides memory into pages (usually 4KB each). Programs are also divided into pages. This allows the OS to load, unload, or move pages independently, making memory use more efficient and flexible.

Result

Memory can be shared, reused, and managed in smaller pieces, reducing waste and fragmentation.

Paging sets the stage for demand paging by enabling selective loading of program parts.

3

Intermediate

How demand paging works in practice

🤔Before reading on: do you think demand paging loads pages before or after a program tries to use them? Commit to your answer.

Concept: Demand paging loads pages only when a program tries to access them, triggering a page fault if the page is not in memory.

When a program accesses a page, the OS checks if it's in RAM. If yes, the program continues. If not, a page fault occurs. The OS then pauses the program, loads the needed page from disk into RAM, updates the page table, and resumes the program. This process repeats for each new page accessed.

Result

Only necessary pages are loaded, reducing memory use and speeding up program start.

Knowing that pages load on demand explains why programs can start quickly and use less memory initially.

4

Intermediate

Page fault handling and its impact

🤔Before reading on: do you think page faults slow down or speed up program execution? Commit to your answer.

Concept: Page faults are normal but cause delays because the OS must load data from slower disk storage.

A page fault happens when a program tries to access a page not in RAM. The OS must stop the program, find a free frame in RAM (possibly evicting another page), load the needed page from disk, update memory tables, and then resume the program. This process takes time, so frequent page faults can slow down programs.

Result

Programs run efficiently if page faults are rare; too many cause slowdowns called thrashing.

Understanding page faults helps explain performance trade-offs in demand paging systems.

5

Intermediate

Role of page replacement algorithms

🤔Before reading on: do you think the OS randomly chooses pages to remove or uses a strategy? Commit to your answer.

Concept: When memory is full, the OS uses algorithms to decide which page to remove to make space for new pages.

Since RAM is limited, the OS must pick pages to evict when loading new ones. Common strategies include Least Recently Used (LRU), First-In-First-Out (FIFO), and Optimal replacement. These algorithms aim to minimize future page faults by removing pages unlikely to be used soon.

Result

Effective page replacement improves system speed and responsiveness.

Knowing replacement strategies reveals how OS balances memory use and program speed.

6

Advanced

Thrashing: when demand paging backfires

🤔Before reading on: do you think more paging always improves performance? Commit to your answer.

Concept: Thrashing occurs when excessive page faults cause the system to spend most time swapping pages instead of running programs.

If too many programs run or memory is too small, the OS keeps loading and unloading pages rapidly. This constant swapping slows down the system drastically. Detecting thrashing involves monitoring page fault rates, and solutions include reducing running programs or increasing memory.

Result

Thrashing severely degrades performance and user experience.

Recognizing thrashing helps in tuning system resources and workload for better performance.

7

Expert

Optimizations and hardware support for demand paging

🤔Before reading on: do you think demand paging is handled entirely by software or involves hardware? Commit to your answer.

Concept: Modern CPUs and OSes use hardware features like the Memory Management Unit (MMU) and Translation Lookaside Buffer (TLB) to speed up demand paging.

The MMU helps translate virtual addresses to physical addresses and detects page faults quickly. The TLB caches recent translations to avoid repeated lookups. Some systems use prefetching to guess which pages will be needed soon and load them in advance. These optimizations reduce the overhead of demand paging and improve performance.

Result

Demand paging becomes efficient enough for everyday use without noticeable delays.

Understanding hardware support reveals why demand paging is practical and fast on modern computers.

Under the Hood

Demand paging works by using a page table that tracks which pages are in physical memory and which are on disk. When a program accesses a virtual address, the CPU consults the page table via the MMU. If the page is not present, a page fault interrupt triggers the OS to pause the program, find or free a physical frame, load the page from disk into RAM, update the page table, and then resume the program. The TLB caches recent address translations to speed this process. This mechanism allows the OS to manage memory dynamically and efficiently.

Why designed this way?

Demand paging was designed to overcome the limitations of limited physical memory and to allow programs to run without loading their entire code and data upfront. Early computers had very limited RAM, so loading everything was impractical. Alternatives like loading entire programs or swapping whole processes were inefficient. Demand paging strikes a balance by loading only what is needed, improving responsiveness and memory use.

┌───────────────┐
│ CPU requests  │
│ virtual addr  │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ MMU checks    │
│ page table    │
└──────┬────────┘
       │
   ┌───┴─────┐
   │ Present? │
   └───┬─────┘
       │Yes          No
       ▼             ▼
┌───────────────┐  ┌───────────────┐
│ Access page   │  │ Page fault    │
│ in RAM       │  │ interrupt     │
└───────────────┘  └──────┬────────┘
                          │
                          ▼
                ┌─────────────────────┐
                │ OS loads page from  │
                │ disk to RAM, updates │
                │ page table          │
                └─────────┬───────────┘
                          │
                          ▼
                ┌─────────────────────┐
                │ Resume program with  │
                │ page now in memory   │
                └─────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does demand paging mean all pages are loaded before program starts? Commit yes or no.

Common Belief: Demand paging loads all program pages into memory before execution begins.

Reality: Demand paging loads pages only when the program tries to access them, not all at once.

Why it matters: Believing all pages load upfront leads to misunderstanding memory savings and startup speed benefits of demand paging.

Quick: Do page faults always indicate a problem? Commit yes or no.

Common Belief: Page faults are errors or failures that harm program execution.

Reality: Page faults are normal and expected events in demand paging that trigger loading needed pages.

Why it matters: Misinterpreting page faults as errors can cause confusion and misdiagnosis of system behavior.

Quick: Is demand paging always faster than loading all pages? Commit yes or no.

Common Belief: Demand paging always improves program speed compared to loading all pages at once.

Reality: Demand paging speeds startup but can slow execution if many page faults occur, especially under memory pressure.

Why it matters: Ignoring this can lead to poor system tuning and unexpected slowdowns.

Quick: Does the OS randomly choose pages to evict when memory is full? Commit yes or no.

Common Belief: The OS randomly removes pages from memory when it needs space.

Reality: The OS uses specific algorithms to choose pages that minimize future faults, not random eviction.

Why it matters: Assuming randomness overlooks the importance of page replacement strategies in system performance.

Expert Zone

1

Some modern systems combine demand paging with prefetching to reduce page faults by guessing future page needs.

2

The interaction between TLB caching and page faults can cause subtle performance issues if not managed carefully.

3

Shared pages between processes (like shared libraries) complicate demand paging but improve memory efficiency.

When NOT to use

Demand paging is less effective in real-time systems where predictable timing is critical, as page faults cause unpredictable delays. In such cases, systems often use locked memory or preload all needed pages. Also, embedded systems with limited storage may avoid demand paging due to complexity.

Production Patterns

In production, demand paging is combined with sophisticated page replacement algorithms and monitoring tools to detect thrashing. Operating systems tune page sizes and prefetching heuristics based on workload. Cloud environments use demand paging to optimize memory use across many virtual machines.

Connections

Cache memory

Both demand paging and cache memory use the principle of loading data only when needed to speed up access.

Understanding demand paging helps grasp how caches reduce access time by storing frequently used data closer to the processor.

Just-in-time (JIT) compilation

Demand paging and JIT both delay work until it is necessary, optimizing resource use and performance.

Recognizing this shared strategy across memory and code execution reveals a common theme of efficiency in computing.

Inventory management in supply chains

Demand paging is like ordering inventory only when customers request it, avoiding overstock and waste.

This cross-domain link shows how demand-driven strategies optimize resources in both computing and business.

Common Pitfalls

#1 Loading all program pages into memory at startup defeats demand paging benefits.

Wrong approach:

OS loads entire program into RAM before execution, ignoring page faults.

Correct approach:

OS loads pages only when accessed, handling page faults to bring pages from disk.

Root cause:

Misunderstanding that demand paging means selective loading rather than full upfront loading.

#2 Ignoring page faults as normal events leads to misdiagnosing system slowdowns.

Wrong approach:

Treat page faults as errors and try to disable or ignore them.

Correct approach:

Recognize page faults as part of normal operation and optimize system to minimize their impact.

Root cause:

Confusing page faults with errors due to lack of understanding of demand paging mechanism.

#3 Using inefficient page replacement algorithms causes excessive page faults and thrashing.

Wrong approach:

Evict pages randomly without considering usage patterns.

Correct approach:

Use algorithms like LRU or Optimal to choose pages to evict based on recent or predicted use.

Root cause:

Underestimating the importance of intelligent page replacement in demand paging performance.

Key Takeaways

Demand paging loads program pages into memory only when they are needed, saving memory and speeding startup.

Page faults are normal triggers that cause the operating system to load missing pages from disk.

Effective page replacement algorithms are crucial to maintain system performance and avoid thrashing.

Hardware features like the MMU and TLB support demand paging by speeding address translation and fault handling.

Understanding demand paging helps optimize memory use and system responsiveness in modern computing.