page replacement

Picture a small desk that can hold only six open books at a time. You are studying and you need a seventh book, but the desk is full. Before you can lay the new one down, you must pick one of the six already there and put it back on the shelf. Computer memory works the same way: physical RAM holds only so many pages, and when a process touches a page that is not in memory (a page fault) but every frame is already taken, the operating system must choose one resident page to throw out so the wanted page has somewhere to go. That choosing-and-evicting step is page replacement.

Here is the mechanism in plain steps. A page fault occurs and the OS looks for a free frame. If one exists, fine — load the page and continue. If none is free, the OS runs a page-replacement algorithm to pick a victim page. It writes the victim back to the backing store only if the victim was modified (otherwise the on-disk copy is already correct and the write is skipped), marks the victim's page-table entry invalid, reads the desired page into the now-free frame, updates the page table, and restarts the faulting instruction. So in the worst case one fault can cost two disk operations: one to write the victim out and one to read the new page in.

Why it matters: page replacement is the heart of how virtual memory pretends a machine has more RAM than it really does. It only works because programs show locality — they reuse a small set of pages for a while — so a good algorithm can evict the pages least likely to be needed soon and keep the busy ones resident. The whole game is to make that guess well, because every wrong guess is an expensive trip to disk.