Page Replacement Algorithms: Evicting Data from Memory
A page replacement algorithm is a bouncer for your RAM. When memory is full and a new page is needed, it decides which existing page to evict to disk. This is crucial in virtual memory systems.
Why it exists
Physical RAM is a finite, fast resource. Virtual memory creates the illusion of having much more memory than is physically present by using slower disk space as an overflow. Page replacement algorithms are the mechanism that manages this overflow, making virtual memory practical. Without them, an application larger than RAM simply couldn't run.
The mental model
Imagine your desk is your computer's RAM—fast to access but limited in space. The file cabinet is your disk—vast but slow. When your desk is full and you need a new document from the cabinet, you must decide which current document to put back. A page replacement algorithm is your strategy for choosing which document to file away. A bad strategy means you're constantly running back and forth to the cabinet.
How it works
When a program requests a piece of data (a "page") that isn't in physical memory, a "page fault" occurs. The operating system must then load the required page from the disk into RAM. If RAM is already full, the page replacement algorithm is invoked. It analyzes the pages currently in memory and selects a "victim" page to be written to disk (if modified) or simply overwritten. This frees up a memory frame for the new page. The choice of which page to evict is the entire job of the algorithm.
When to use it
This is not a tool you choose to use, but a fundamental, automatic component of modern operating systems (like Windows, macOS, Linux) that use virtual memory. It's always running behind the scenes whenever the total memory demand of running processes exceeds the available physical RAM.
When not to use it
In systems with no virtual memory, such as some simple embedded systems or microcontrollers, there is no concept of paging data to disk, so these algorithms aren't needed. Also, if a system has enough RAM to hold all running processes simultaneously, the algorithm remains idle as no pages need to be evicted.
One canonical example
A web server running a database and a web framework has its physical RAM completely filled. A user request triggers a new, temporary analysis process that needs memory. The OS detects a page fault and sees no free memory frames. The page replacement algorithm runs, decides a page belonging to an idle part of the web framework is the best candidate for eviction, swaps it to disk, and loads the new analysis process's page into the now-free space.
Interview question
When does an operating system primarily invoke a page replacement algorithm?
- a.When the operating system needs to allocate additional virtual memory space to a running application.
- b.When a program requests a page not in physical memory, and RAM is full.Correct
- c.When the CPU cache misses a requested data block and needs to fetch it from main memory.
- d.When a program attempts to access a memory address that is outside its virtual memory range.
Why? this is the answer
A page replacement algorithm is triggered when a program requests a page that isn't in physical RAM (a page fault) AND there's no free physical memory available, necessitating the eviction of an existing page. Option D describes a segmentation fault, which is a different memory error.
Just read this? Test yourself on what you have been reading.
Read the original → en.wikipedia.org
- #operating systems
- #virtual memory
- #memory management
- #architecture
Put your scrolling time to good use
Learn one idea, try a quiz and save useful cards for revision. Tezvyn makes it easy to learn and stay current in your tech field, a few minutes at a time.
The iPhone app is on the way
We are building it. Until it lands, nothing here is held back from you: every interview card, your saved cards, streaks and the job board all work in Safari, plus hundreds of free practice quizzes of thirty questions each. Sign in and it all carries over to the app the day it arrives.
Want it as an icon? Tap Share at the bottom of Safari, then Add to Home Screen. It opens full screen and the cards you have read stay available offline.
We are hiring for this. Every open role lists the topics its interview covers, so you can prepare for the real thing rather than guessing.
See open roles