Page Replacement Algorithms: Evicting Data from Memory

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.