Difficulty: Intermediate
What is virtual memory? Explain demand paging and the step-by-step handling of a page fault, and compute the effective access time with page faults.
Virtual memory is arguably the most elegant trick in operating systems. The problem it solves: programs want a large, private, contiguous memory, but physical RAM is limited, shared and fragmented. Virtual memory gives each process the illusion of a huge address space, larger than actual RAM, by using disk as the backing store and keeping in RAM only the parts currently needed. The analogy is a desk and a filing cabinet. You keep on the desk only the papers you are working on now; everything else is in the cabinet and you fetch it when needed. The desk is RAM, the cabinet is disk, and you, the OS, take care of the shuffling.
Its benefits are several. Programs can be larger than physical memory. More processes fit in memory at once because each loads only a fraction, raising CPU utilization. Each process has its own isolated address space, so one cannot touch another's memory. Sharing is simple, since two processes can map the same frame, and startup is faster as the program is not loaded fully.
The mechanism is demand paging: pages are loaded into memory only when they are first accessed, not at process start. Each page table entry has a valid-invalid (present) bit. If the bit is valid, the page is in memory. If invalid, either the address is illegal or the page is legal but currently on disk.
When the CPU references a page that is not present, the hardware raises a page fault trap. The handling steps are as follows. First, the MMU traps to the kernel. Second, the kernel checks an internal table to see whether the reference was legal; if not, the process gets a segmentation fault and is terminated. Third, if legal, the OS finds a free frame; if none is free, it runs a page replacement algorithm to choose a victim, writing it to disk first if its dirty bit is set. Fourth, the OS schedules a disk read to bring the required page into that frame; the process is moved to the Waiting state and another process runs. Fifth, when the I/O completes, the OS updates the page table (frame number, valid bit set) and the TLB. Sixth, the process moves back to Ready, and when scheduled, the faulting instruction is restarted from scratch as if nothing had happened. That restartability of instructions is a hardware requirement.
Performance matters greatly, so here is the classic calculation. Let p be the page fault rate, memory access time 200 ns, and page fault service time 8 milliseconds (8,000,000 ns). EAT = (1 - p) x 200 + p x 8,000,000. If p = 1/1000, then EAT = 0.999 x 200 + 0.001 x 8,000,000 = 199.8 + 8,000 = 8,199.8 ns, a slowdown by a factor of about 41. To keep degradation under 10 percent (EAT at most 220 ns), we need 200 + 7,999,800p <= 220, so p <= 20 / 7,999,800, approximately 2.5 x 10^-6, or fewer than one fault per 400,000 accesses. This is why locality of reference is essential: programs tend to reuse the same pages, so faults are rare.
Modern systems add optimizations: copy-on-write for fork, memory-mapped files, and prefetching. Distinguish a minor page fault, where the page is already in memory but not mapped (cheap), from a major page fault, which requires disk I/O (expensive). The interview takeaway: virtual memory is a policy layered on paging that uses locality to make small RAM appear large.
virtual memory, demand paging, page fault, swap, valid-invalid bit