Virtual Memory & Demand Paging

In the early days of computing, if you had 4GB of RAM, the absolute maximum size of a program you could run was 4GB. Virtual Memory completely changed this.

Virtual Memory is a technique that allows the execution of processes that are not completely in memory. One major advantage of this scheme is that programs can be substantially larger than physical memory. Furthermore, it abstracts main memory into a massive, uniform array of storage, separating logical memory as viewed by the user from physical memory.

1. Demand Paging

Virtual memory is commonly implemented using Demand Paging.

Instead of loading an entire 50GB video game into RAM when you double-click the icon, a demand-paging system is lazy. It only loads pages into memory exactly when they are demanded during execution.

How it works:

1. When a process starts, its Page Table is created, but all entries are marked as invalid (meaning the pages are currently sitting on the hard disk, not in RAM).
2. The CPU begins executing the first instruction. It requests Page 0.
3. The hardware looks at the Page Table, sees that Page 0 is invalid, and triggers a Page Fault trap to the operating system.
4. The OS pauses the process, finds an empty frame in physical RAM, reads Page 0 from the hard disk into the RAM frame, updates the Page Table to mark it as valid, and then restarts the CPU instruction.

Because of demand paging, you can theoretically run a 100GB application on a machine with only 8GB of RAM. The OS will just constantly shuttle pages back and forth between the RAM and the hard disk.

2. The Page Replacement Problem

What happens if a Page Fault occurs, but the physical RAM is completely full? There are no free frames available to load the required page from the disk.

The OS must perform Page Replacement:

1. Find the location of the desired page on the disk.
2. Find a victim frame currently in RAM.
3. Write the victim frame out to the disk (if it was modified).
4. Read the desired page into the newly freed frame.
5. Update the page and frame tables.
6. Restart the user process.

Because disk I/O is incredibly slow, choosing the wrong victim frame (e.g., kicking out a page that the CPU is going to need again in 2 milliseconds) will cause severe performance degradation. This necessitates intelligent Page Replacement Algorithms, which we will cover in the next chapter.