Virtual memory interview questions, with answers
Virtual memory lets programs use more memory than the machine has and isolates them from each other, and it is a favourite interview topic because it ties together hardware, the page table and the disk. Page replacement problems, where you count faults for a reference string, are the most common numerical question.
The answers below cover what virtual memory is, what happens on a page fault, demand paging, the replacement algorithms, how LRU is approximated, copy-on-write and the dirty bit. Then take the free Operating Systems diagnostic — ten questions across every OS topic in the bank — to see which of these you can explain but not yet apply.
The questions, with answers
1.What is virtual memory, and why is it used?
In short: An abstraction giving each process a large private address space, with only the needed pages kept in physical memory.
Virtual memory separates the addresses a program uses from physical memory. Each process sees its own large, contiguous address space, while the operating system and memory management unit map its pages to physical frames and keep pages not currently needed on disk. This lets programs larger than physical memory run, lets more processes run at once since each needs only its active pages in memory, isolates processes from one another, and makes sharing easy, since the same frame can be mapped into several address spaces, as with shared libraries.
2.What happens when a page fault occurs?
In short: The hardware traps to the OS, which loads the missing page from disk into a frame, updates the page table and restarts the instruction.
When a process accesses a page whose page-table entry is marked invalid, the memory management unit raises a page fault trap. The operating system checks that the access is legal; if the address is outside the process's space, the process is terminated with a segmentation fault. Otherwise the OS finds a free frame, or chooses a victim page and writes it back if it is dirty, schedules a disk read of the needed page, and blocks the process meanwhile. When the read completes, it updates the page table, marks the entry valid, and restarts the faulting instruction as if nothing happened.
3.What is demand paging?
In short: Loading a page into memory only when it is first accessed, rather than loading the whole program at start.
With demand paging, a process starts with none or few of its pages in memory, and each page is loaded the first time it is touched, through a page fault. Pages that are never used, such as error-handling code, are never loaded, which saves memory and makes programs start faster. Performance depends on keeping the page-fault rate very low, because a fault costs milliseconds of disk time against nanoseconds for a memory access; locality of reference, the tendency of programs to reuse nearby addresses, is what makes this work in practice.
4.How do the FIFO, LRU and optimal page replacement algorithms differ?
In short: FIFO evicts the oldest-loaded page, LRU the least recently used one, and optimal the one not needed for the longest time.
When a page must be loaded and every frame is full, the replacement algorithm picks a victim. FIFO evicts the page that has been in memory longest, which is simple but may throw out a heavily used page. LRU evicts the page whose last use is furthest in the past, using the recent past to predict the near future, and usually performs well. Optimal, also called OPT or MIN, evicts the page whose next use is furthest in the future; it gives the fewest faults possible but needs future knowledge, so it serves only as a benchmark for comparing real algorithms.
5.How is LRU approximated in real operating systems?
In short: With a reference bit per page and the clock (second-chance) algorithm, since exact LRU needs costly bookkeeping on every access.
Exact LRU would require updating a timestamp or reordering a list on every memory reference, which is far too expensive. Instead, hardware sets a reference bit in the page-table entry whenever a page is used. The clock, or second-chance, algorithm arranges frames in a circle with a hand: at a fault, if the page under the hand has its reference bit set, the bit is cleared and the hand moves on, giving the page a second chance; the first page found with the bit clear is evicted. Enhanced versions also consider the dirty bit to prefer evicting clean pages.
6.What is copy-on-write?
In short: Sharing pages between processes until one writes, and only then copying the page that is written.
After fork(), parent and child would each need a full copy of the parent's memory, which is wasteful, especially when the child immediately calls exec(). With copy-on-write, both processes instead share the same physical pages, marked read-only. When either tries to write to a shared page, the write causes a fault, and the kernel then copies just that page, gives the writer its own copy with write permission, and resumes it. Only pages that are actually modified are ever copied, which makes process creation fast. The same technique is used for memory snapshots and in some file systems.
7.What is the dirty bit used for?
In short: It records that a page was modified since it was loaded, so only dirty pages are written back to disk when evicted.
Every page-table entry has a dirty, or modified, bit, which the hardware sets when the page is written. When the operating system evicts a page, a clean page can simply be dropped, because an identical copy already exists on disk or in the executable file, while a dirty page must first be written back to the swap area or file. Preferring clean victims therefore halves the disk work of a fault in many cases, and background writeback of dirty pages keeps a pool of clean pages ready to replace.
How the diagnostic asks it
One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 4 on virtual memory and 30 across Operating Systems.
With 3 frames, initially empty, how many page faults does least recently used (LRU) replacement cause for this reference string?
1, 2, 3, 1, 4, 2, 5, 1- 17correct
- 26
- 35
- 48
The first three references fault and fill the frames. 1 hits. 4 faults and evicts 2, the least recently used. 2 faults and evicts 3. 5 faults and evicts 1, used before 4 and 2. The final 1 faults and evicts 4. That is 7 faults. 6 is what FIFO gives on this string, since FIFO evicts 1, the oldest arrival, when 4 comes and so keeps 2. 5 is the optimal algorithm's count. 8 would mean the 1 at position four also faulted. LRU is usually good but not always better than FIFO.
Measure it
Reading answers tells you what’s true. A diagnostic tells you what you get wrong.
10 Operating Systems questions across its topics, easy to hard, about fifteen minutes. You get a readiness figure with the arithmetic shown, the topics you missed named, and a practice set sized for today. Free: 1 diagnostic a month and 15 problems a day. No card.