Demand Paging & Page Faults
Scenario
How can you play a 100GB video game on a computer that only has 16GB of RAM? The OS is constantly playing a high-speed game of musical chairs with your memory.
Mental model
Demand paging is like streaming a movie on Netflix. You don't download the whole 2-hour movie before you hit play; you only download the scenes exactly when you are about to watch them.
Demand Paging ensures pages are only loaded from the disk into physical memory when the CPU actually requests them. If a requested page isn't in memory, a 'Page Fault' occurs, pausing the program while the OS fetches it.
Explanation
In traditional execution, a program's entire code and data had to be loaded into physical memory before it could run. This severely limited the size of programs and the number of applications that could run simultaneously. Demand paging revolutionized this by introducing the concept of 'lazy loading'. Under demand paging, a program begins execution with zero pages in memory. Pages are only brought in from the hard disk or SSD when the CPU actively attempts to access them.
To track which pages are actually in memory, the page table includes a 'Valid/Invalid' bit for every entry. When a page is present in RAM, the bit is set to valid. If the page is still sitting on the disk, the bit is set to invalid. When the CPU tries to access a memory address, the hardware checks the page table. If it sees an invalid bit, the hardware immediately pauses the running program and throws a special interrupt called a Page Fault.
A Page Fault is not a crash; it is an expected part of normal OS operations. When the Page Fault traps to the OS, the OS looks at its internal records to verify the memory access was legal. If it was legal, the OS locates the missing page on the disk. It then finds a free frame in physical memory, schedules a disk read to copy the page into that frame, and updates the page table to mark the bit as valid.
Once the disk read is complete, the OS reschedules the paused program, explicitly instructing the CPU to re-execute the exact instruction that caused the page fault. This time, the memory access succeeds because the page is physically present in RAM. The entire process is completely invisible to the application; as far as the program knows, it simply has access to a massive, continuous block of memory.
Key points
- Lazy Swapping: Pages are never loaded predictively in pure demand paging; they are strictly loaded on-demand, saving RAM and initial load times.
- Transparent to User: The application doesn't write error-handling code for page faults; the hardware and OS pause and resume the process seamlessly.
- Instruction Restart: Crucially, the CPU must be able to roll back its state and re-execute the exact instruction that caused the fault once the page is loaded.
Common mistakes
- Thinking a Page Fault is an error or crash: This is a common source of confusion.
- Assuming disk reads are fast enough to ignore: This is a common source of confusion.
Glossary
- lazy loading
- A technique where the system delays bringing parts of a program into memory until the exact moment they are actually needed, saving time and space.
- demand paging
- An operating system feature that loads pieces (pages) of a program into the main memory only when the processor specifically asks for them.
- physical memory
- The actual, physical RAM chips in your computer where running programs and active data are temporarily stored for fast access.
Recall questions
- What does the valid/invalid bit indicate in a page table entry?
- What is the very first step the OS takes when a Page Fault occurs?
- How does demand paging improve multi-programming?
Questions & answers
Which of the following is true about demand paging? A) All pages are loaded at startup B) Pages are loaded only when referenced C) It prevents external fragmentation entirely
B) Pages are loaded only when referenced
Approach: Demand paging is defined by its lazy loading nature—pages are brought into memory precisely upon the first fault triggered by referencing them.
What must the CPU do immediately after a page fault is serviced by the OS?
Restart the instruction that caused the page fault.
Approach: The instruction initially failed to execute because the data wasn't there. Once the OS fetches the data, the CPU must re-attempt that exact same instruction.
Continue learning
Previous: Paging & Page Tables
Next: Page Replacement: FIFO, LRU, Optimal
Next: Thrashing & Working Set