High yield ●●●

🧱 Memory Management

Why it matters: Paging arithmetic (page table size, bits in an address, TLB access time) is among the most predictable numerical questions in OS.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.

Formulas

Address split
virtual address bits = page number bits + offset bits; offset bits = log₂(page size)
Number of pages / frames
virtual size ÷ page size; physical size ÷ page size
Page table size
(number of pages) × (entry size)
Entries per page (multilevel)
page size ÷ entry size, so a level uses log₂(that) bits
Inverted page table size
(number of frames) × (entry size)
EMAT, 1-level paging with TLB
h(t + m) + (1 − h)(t + 2m)
EMAT, k-level paging with TLB
h(t + m) + (1 − h)(t + (k + 1)m)
Average internal fragmentation
≈ page size / 2 per process

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Page table size or number of bits in the page-table entry
Pages × entry size, where an entry holds frame number plus valid, dirty and protection bits.
★★★
Multilevel paging: bits per level / number of levels
Make each table fit one page: entries per page gives the bits for that level.
★★★
Effective access time with TLB (and page-fault terms)
Weight the hit and miss paths; count memory accesses for the walk.
★★★
First/best/worst fit placement and fragmentation
Place each request in order; best fit may leave small unusable holes.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

11 real questions from the official GATE CSE papers (2016 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

11 questions · 0 correct of 0 attempted · marks 0 / 18

Year:
GATE 2025 CS1 · Q14MCQ1 mark
Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
GATE 2025 CS2 · Q58NAT2 marks
A computer system supports a logical address space of 232 bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a b-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of b is ______.
GATE 2024 CS2 · Q24MSQ1 mark
Which of the following tasks is/are the responsibility/responsibilities of the memory management unit (MMU) in a system with paging-based memory management?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q62NAT2 marks
Consider a memory management system that uses a page size of 2 KB. Assume that both the physical and virtual addresses start from 0. Assume that the pages 0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and 0, respectively. The physical address (in decimal format) corresponding to the virtual address 2500 (in decimal format) is ______.
GATE 2024 CS2 · Q64NAT2 marks
Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each. Assume 1 KB = 210 bytes. The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry. An active process in this system accesses 2000 unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let X denote the minimum and Y denote the maximum number of pages across the two levels of the page table of the process. The value of X + Y is ______.
GATE 2023 · Q58NAT2 marks
Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes. The value of L is ______.
GATE 2022 · Q38MCQ2 marks
Which one of the following statements is FALSE?
GATE 2021 Set 1 · Q11MSQ1 mark
In the context of operating systems, which of the following statements is/are correct with respect to paging?

One or more options may be correct. Select all that apply, then submit.

GATE 2020 · Q11MCQ1 mark
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
GATE 2019 Set 2 · Q33MCQ2 marks
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?
GATE 2016 Set 1 · Q47NAT2 marks
Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ______ megabytes.

Common traps

The page-table entry has more than the frame number: valid, reference, dirty and protection bits.
In EMAT problems say whether the TLB lookup time is added on a hit and on a miss: both.
The offset bits depend on the page size only, not on the memory size.
Internal fragmentation belongs to paging and fixed partitions; external to segmentation and variable partitions.