Memory management and paging MCQs from the KnowledgeGate question bank
Memory management is where Operating Systems turns quantitative. The examiners test whether you can reason about fit strategies, size a page table from address widths, count the bits in a TLB tag, and compute an effective access time under a hit ratio. Below are 12 solved MCQs from KnowledgeGate's published question bank, all GATE previous-year questions with the year noted. Attempt each before reading the answer; the explanation is short by design, just enough to fix the method. Every question links to its exact solved page in the memory management module, so you can rebuild any concept from the ground up when an answer feels shaky.
Allocation basics and fit strategies
Q1. Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to statically linked libraries? *(GATE 2003, see the solved page)*
(a) Smaller sizes of executable files
(b) Lesser overall page fault rate in the system
(c) Faster program startup
(d) Existing programs need not be re-linked to use newer library versions
Answer: (c) Faster program startup.
Dynamic linking resolves symbols and maps the shared library at load or run time, which adds startup work rather than removing it. The other three are genuine wins: one on-disk copy shrinks executables, shared pages lower the system-wide fault rate, and programs pick up a new library version without re-linking.
Q2. A new process is allocated memory when no existing hole fits exactly, so a smaller hole is left over. Which statement is TRUE? *(GATE 2020, see the solved page)*
(a) The hole created by first fit is always larger than that by next fit
(b) The hole created by worst fit is always larger than that by first fit
(c) The hole created by best fit is never larger than that by first fit
(d) The hole created by next fit is never larger than that by best fit
Answer: (c).
Best fit always chooses the smallest hole that can hold the process, so the leftover it creates can never exceed the leftover first fit would create for the same request. The "always" claims in (a) and (b) fail because first fit and worst fit depend on scan order and can go either way.
Q3. A 1000 KB memory uses variable partitions with no compaction and currently has two partitions of 200 KB and 260 KB. What is the smallest allocation request (in KB) that could be denied? *(GATE 1996, see the solved page)*
(a) 151
(b) 181
(c) 231
(d) 541
Answer: (b) 181.
Free memory is 1000 − 200 − 260 = 540 KB, and with two used partitions it splits into at most three holes. By the pigeonhole principle at least one hole is 540/3 = 180 KB or larger, so any 180 KB request fits somewhere; the smallest request that could be denied by fragmentation is therefore 181 KB.
Q4. Six partitions of 200, 400, 600, 500, 300 and 250 KB are allotted to four processes of 357, 210, 468 and 491 KB, in that order, using best fit. Which partitions are NOT allotted to any process? *(GATE 2015, see the solved page)*
(a) 200 KB and 300 KB
(b) 200 KB and 250 KB
(c) 250 KB and 300 KB
(d) 300 KB and 400 KB
Answer: (a) 200 KB and 300 KB.
Best fit picks the smallest sufficient partition each time: 357 takes 400, 210 takes 250, 468 takes 500, and 491 takes 600. That leaves 200 and 300 unused. The trick is to place processes strictly in the given order and recompute the smallest fit after each allocation.
Paging and the TLB
Q5. A machine has 64 MB physical memory and a 32-bit virtual address, with a 4 KB page size. What is the approximate size of a single-level page table? *(GATE 2001, see the solved page)*
(a) 16 MB
(b) 8 MB
(c) 2 MB
(d) 24 MB
Answer: (c) 2 MB.
A 32-bit space with 4 KB (2^12) pages has 2^32 / 2^12 = 2^20 pages, so the table needs about a million entries. With roughly 2 bytes per entry (the frame number for 64 MB needs 14 bits), the table is close to 2^20 × 2 bytes = 2 MB.
Q6. In a system with 32-bit virtual addresses and 1 KB pages, single-level page tables are impractical because of *(GATE 2003, see the solved page)*
(a) large internal fragmentation
(b) large external fragmentation
(c) the large memory overhead in maintaining page tables
(d) the large computation overhead in translation
Answer: (c) the large memory overhead.
With 1 KB (2^10) pages the space has 2^22 pages, and at 4 bytes per entry that is a 16 MB page table per process, most of it for pages a process never touches. Multi-level or inverted page tables exist precisely to avoid allocating this whole flat table.
Q7. What is the essential content of each entry in a page table? *(GATE 2009, see the solved page)*
(a) Virtual page number
(b) Page frame number
(c) Both virtual page number and page frame number
(d) Access right information
Answer: (b) Page frame number.
The virtual page number is the index into the table, so it is implicit and never stored inside the entry. What each entry must carry is the physical frame number it maps to; protection and valid bits are useful extras, but the frame number is the one essential field.
Q8. A CPU generates 32-bit virtual addresses with a 4 KB page size. Its TLB holds 128 entries and is 4-way set associative. What is the minimum TLB tag size? *(GATE 2006, see the solved page)*
(a) 11 bits
(b) 13 bits
(c) 15 bits
(d) 20 bits
Answer: (c) 15 bits.
A 4 KB page needs a 12-bit offset. With 128 entries at 4-way associativity there are 128/4 = 32 sets, needing a 5-bit index. The tag is what remains of the 32-bit address after offset and index: 32 − 12 − 5 = 15 bits.
Q9. A paging scheme uses a TLB. A TLB access takes 10 ns and a main memory access 50 ns. With a 90% hit ratio and no page faults, what is the effective access time? *(GATE 2008, see the solved page)*
(a) 54 ns
(b) 60 ns
(c) 65 ns
(d) 75 ns
Answer: (c) 65 ns.
On a hit you pay TLB plus one memory access: 10 + 50 = 60 ns. On a miss you pay TLB plus a page-table read plus the data read: 10 + 50 + 50 = 110 ns. The effective time is 0.9 × 60 + 0.1 × 110 = 54 + 11 = 65 ns.
Q10. With a 32-bit virtual address, 30-bit physical address, 4 KB page size and 32-bit page table entries, what is the maximum number of bits available for protection and other information in each entry? *(GATE 2004, see the solved page)*
(a) 2
(b) 10
(c) 12
(d) 14
Answer: (d) 14.
A 4 KB page needs a 12-bit offset, so the physical frame number occupies 30 − 12 = 18 bits. Each 32-bit entry therefore has 32 − 18 = 14 bits left over for valid, dirty, protection and other status flags.
Demand paging and virtual memory
Q11. If an instruction takes i microseconds and a page fault adds j microseconds, and a page fault occurs on average every k instructions, the effective instruction time is *(GATE 1998, see the solved page)*
(a) i + j/k
(b) i + j × k
(c) (i + j)/k
(d) (i + j) × k
Answer: (a) i + j/k.
Every instruction costs i, and the fault penalty j is incurred once per k instructions, so its amortised cost per instruction is j/k. Add the two and the effective time is i + j/k. The distractors either multiply the rare penalty in fully or divide the base cost, both of which misplace the averaging.
Q12. Which of the following statements about virtual memory is false? *(GATE 2001, see the solved page)*
(a) It translates a program's address space into physical memory addresses
(b) It lets a program exceed the size of primary memory
(c) It increases the degree of multiprogramming
(d) It reduces context-switching overhead
Answer: (d) It reduces context-switching overhead.
Virtual memory does the first three: it maps address spaces, lets programs run larger than RAM by paging to disk, and packs more processes into memory to raise multiprogramming. It does nothing to shrink context-switch cost; if anything, address-space switching and TLB flushes add to it.
Where these 12 fit in your preparation
The set tracks the way memory management is examined: contiguous allocation and fit strategies (Q1-Q4), the paging arithmetic of page-table size, TLB tags and effective access time (Q5-Q10), and the demand-paging and virtual-memory concepts that sit on top (Q11-Q12). If the numericals cost you time, the fix is to always write down the offset, index and frame-number bit-widths first, before touching the options.
For the theory behind every answer, work through the memory management learn module and its PYQ sets, and see how the OS syllabus fits together in our Operating Systems for GATE breakdown. GATE aspirants get the full sequence inside GATE Guidance by Sanchit Sir; NET aspirants can start from the NET CS category page. Solve, review your misses, and return to the set a week later.