Paging and Virtual Memory Interview Questions with Numericals
Last updated 2026-11-19
Paging and virtual memory produce the most predictable numericals in an operating systems paper: count page faults for a reference string, find the effective access time with a TLB, compute the page-table size, or split a virtual address into page number and offset. This page works every one of those in full, using the standard textbook reference string so you can check your own working against it.
The concept questions on this page (demand paging, thrashing, copy-on-write, inverted page tables) are the ones follow-up questions grow from. For allocation schemes before paging see memory management interview questions, and for the cache side of the same ideas see cache memory interview questions. For a preparation plan read how to crack an OS interview.
| Reference string used | 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames |
|---|---|
| Fault counts | FIFO 15, LRU 12, Optimal 9 |
| Also covered | Belady anomaly, TLB access time, multi-level page tables, thrashing |
Address arithmetic you should do without thinking
- Page size 2^k bytes means the offset is k bits. Virtual address bits minus k is the page number width.
- Number of page-table entries = 2^(page number bits). Table size = entries x entry size.
- Frame number comes from the page table. Physical address = frame number x page size + offset.
Paging and Virtual Memory Interview Questions with Numericals: questions with worked answers
1 What is paging and why does it remove external fragmentation?
easyPaging splits a process's logical address space into fixed-size pages and physical memory into frames of the same size. A page table maps each page number to a frame number, and the frames need not be contiguous. Because any free frame can hold any page, there are no unusable holes between allocations. Only internal fragmentation remains, in the last page of each process.
2 What is demand paging and what happens on a page fault?
easyDemand paging loads a page into memory only when it is first referenced. If the page table entry's valid bit says the page is not in memory, the hardware raises a page-fault trap. The OS checks that the reference is legal, finds a free frame (or selects a victim with a replacement algorithm, writing it back if its dirty bit is set), schedules a disk read of the page into that frame, updates the page table, and restarts the faulting instruction.
3 Numerical: A logical address has 16 bits and the page size is 1 KB. A page table maps page 3 to frame 7. Translate logical address 3172.
medium1 KB = 2^10, so the offset is 10 bits and the page number is 6 bits (64 pages). Page number = 3172 / 1024 = 3 (integer division), offset = 3172 - 3 x 1024 = 100. Page 3 maps to frame 7, so the physical address is 7 x 1024 + 100 = 7268.
4 Numerical: Find the page-table size for a 32-bit virtual address, 4 KB pages and 4-byte page-table entries. What if the address is 48 bits?
mediumFor 32 bits: offset 12 bits, page number 20 bits, so 2^20 = 1,048,576 entries x 4 bytes = 4 MB per process. For 48 bits with the same page size: page number is 36 bits, giving 2^36 entries x 4 bytes = 256 GB, impossible to keep as one flat table. That is why real systems use multi-level (four-level on x86-64) page tables, which allocate only the parts of the table actually in use.
5 Numerical: Count page faults with FIFO for the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 using 3 frames.
mediumFIFO evicts the page that has been in memory longest. Start empty. 7, 0, 1 are faults (3). Then 2 evicts 7 (4), 0 hits, 3 evicts 0 (5), 0 evicts 1 (6), 4 evicts 2 (7), 2 evicts 3 (8), 3 evicts 0 (9), 0 evicts 4 (10), 3 and 2 hit, 1 evicts 2 (11), 2 evicts 3 (12), 0 and 1 hit, 7 evicts 0 (13), 0 evicts 1 (14), 1 evicts 2 (15). Total faults = 15, hit ratio = 5 / 20 = 25 percent.
6 Numerical: Count page faults with LRU for the same reference string and 3 frames.
mediumLRU evicts the page unused for the longest time. 7, 0, 1 fault (3). 2 evicts 7 (4). 0 hits. 3 evicts 1 (5). 0 hits. 4 evicts 2 (6). 2 evicts 3 (7). 3 evicts 0 (8). 0 evicts 4 (9). 3 and 2 hit. 1 evicts 0 (10). 2 hits. 0 evicts 3 (11). 1 hits. 7 evicts 2 (12). 0 and 1 hit. Total faults = 12, hit ratio = 8 / 20 = 40 percent.
7 Numerical: Count page faults with the optimal algorithm for the same string and 3 frames.
mediumOptimal evicts the page whose next use is farthest in the future. 7, 0, 1 fault (3). 2 evicts 7 (4), since 7 is not needed until the end. 0 hits. 3 evicts 1 (5), whose next use is latest. 0 hits. 4 evicts 0 (6), since 2, 3 are needed sooner. 2 and 3 hit. 0 evicts 4 (7), never used again. 3 and 2 hit. 1 evicts 3 (8). 2, 0, 1 hit. 7 evicts 2 (9). 0 and 1 hit. Total faults = 9. Optimal is the lower bound but cannot be implemented because it needs future knowledge; it is used to benchmark others.
8 What is Belady's anomaly? Show it with an example.
mediumFor some algorithms, notably FIFO, giving a process more frames can increase page faults. With the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO produces 9 faults with 3 frames but 10 faults with 4 frames. Stack algorithms such as LRU and optimal never show the anomaly, because the set of pages held with n frames is always a subset of those held with n + 1 frames.
9 How is LRU implemented in practice? Mention the clock algorithm.
mediumExact LRU needs a timestamp per access or a stack of pages updated on every reference, which is too costly in hardware. Systems approximate it using a reference bit. The clock (second chance) algorithm keeps frames in a circular list with a pointer. To pick a victim, it checks the bit under the pointer: if 1, it clears it and advances; if 0, that page is replaced. A page referenced recently thus survives one full sweep.
10 Numerical: Memory access is 100 ns, TLB lookup is 10 ns, TLB hit ratio is 90 percent. Find the effective access time.
mediumHit: 10 + 100 = 110 ns. Miss: 10 + 100 (page-table entry) + 100 (data) = 210 ns. EAT = 0.9 x 110 + 0.1 x 210 = 99 + 21 = 120 ns. Note the usual textbook convention; some questions treat the TLB lookup as negligible and give 0.9 x 100 + 0.1 x 200 = 110 ns, so state which one you use.
11 Numerical: Memory access time is 200 ns, average page-fault service time is 8 ms, and the page-fault rate is 1 in 1000 accesses. Find the effective access time and the maximum fault rate for under 10 percent slowdown.
mediumConvert 8 ms to 8,000,000 ns. EAT = (1 - p) x 200 + p x 8,000,000 with p = 0.001, which is 199.8 + 8000 = 8199.8 ns, about 8.2 microseconds, a slowdown of 41 times. For under 10 percent slowdown EAT must be at most 220 ns: 200 + p x (8,000,000 - 200) <= 220, so p <= 20 / 7,999,800, approximately 0.0000025, one fault in about 400,000 accesses. Page faults must be extremely rare.
12 What is thrashing and how do you control it?
mediumThrashing means the system spends most of its time swapping pages in and out rather than executing, because the combined working sets of the running processes exceed physical memory. CPU utilisation drops, and a naive scheduler then adds more processes, making it worse. Remedies are the working-set model (give each process enough frames for its recent working set, otherwise suspend it), page-fault-frequency control (add frames when the fault rate is too high, remove when too low), local replacement, and lowering the degree of multiprogramming.
13 What is the working-set model?
mediumThe working set WS(t, delta) is the set of distinct pages referenced in the most recent delta references. If the sum of working-set sizes of all processes exceeds the number of frames, the OS suspends a process to avoid thrashing. It rests on locality: programs reuse a small set of pages for a while before moving to another. Choosing delta is the difficulty, since too small misses part of the locality and too large overlaps several localities.
14 What is a multi-level page table and why is it used?
mediumA multi-level scheme pages the page table itself. A 32-bit address with 4 KB pages may split as 10 bits for the outer index, 10 for the inner index and 12 for the offset. The outer table has 1024 entries and each points to an inner table of 1024 entries, but inner tables for unused regions are never allocated. A small process therefore needs only a few KB for tables instead of 4 MB, at the cost of one extra memory access per level on a TLB miss.
15 What is an inverted page table?
hardInstead of one table per process with an entry per virtual page, an inverted table has one entry per physical frame, holding the process ID and virtual page number that occupy it. Its size depends on physical memory, not virtual address space, which saves memory for large address spaces. The drawback is that lookup requires searching, so it is combined with a hash table, and sharing pages between processes is harder.
16 What is copy-on-write and how does fork use it?
hardAfter fork() the parent and child initially share the same physical pages, all marked read-only. When either writes to a page, the protection fault makes the kernel copy that single page, give the writer its own copy and mark both as writable. Pages never written are never copied. This makes fork cheap, especially when the child calls exec straight away, as a shell does. See processes and threads.
17 Compare local and global page replacement.
hardWith global replacement a faulting process can take a frame from any process, so a high-priority process can grow, and utilisation is better, but one process's behaviour affects others' fault rates and a thrashing process can steal frames. With local replacement a process chooses only among its own frames, giving predictable performance, but frames may stay idle in one process while another thrashes. Linux effectively uses global replacement with per-process limits and an LRU approximation of active and inactive lists.
Frequently asked questions
What is the difference between a page fault and a TLB miss?
A TLB miss only means the translation is not cached; the hardware or OS walks the page table and usually finds it. A page fault means the page is not in physical memory, so a disk read is needed. A page fault is millions of times slower.
Why does the optimal algorithm have the fewest page faults?
Evicting the page whose next use is farthest away delays the next fault on the evicted page as long as possible, so no other policy can do better. It is a theoretical benchmark since the future reference string is unknown.
Does a bigger page size always reduce page faults?
Not always. Larger pages bring in more neighbouring data per fault, which helps programs with spatial locality, but they also waste memory on internal fragmentation and hold unneeded data, so fewer frames fit in RAM.
What is the dirty bit used for?
It records that a page has been modified since loading. A replaced page with the dirty bit clear need not be written back to disk, saving half of the page-fault service time.
Related guides
- Memory Management Interview Questions with Numericals
- Operating Systems Interview Questions with Worked Answers
- Process and Thread Interview Questions with fork() Output Problems
- Cache Memory and Computer Organization Interview Questions with Numericals
- Computer Architecture Interview Questions with Numericals
- File System Interview Questions: Inodes, Allocation and Disk Scheduling
More in CS Fundamentals Interview Questions
- Process and Thread Interview Questions with fork() Output Problems
- Process Synchronization Interview Questions: Semaphores, Mutex and Classic Problems
- Redis Interview Questions and Answers
- REST API Interview Questions and Answers
- Routing Protocols Interview Questions: RIP, OSPF, BGP and Shortest Path Examples
- SDLC and Agile Interview Questions
- Shell Scripting Interview Questions with Bash Examples
- SOLID Principles Interview Questions with Examples
- System Design Interview Questions for Freshers
- System Design Interview Questions with Worked Designs
- TCP vs UDP Interview Questions with Socket Code and Numericals
- TCP/IP Interview Questions: Handshake, Congestion Control and Numericals