A system has 32-bit logical addresses and 4 KB pages. How many bits are the page number and offset, and how large is the page table?
4 KB = 2^12, so the offset is 12 bits and the page number is 32 - 12 = 20 bits. That gives 2^20 entries; at 4 bytes each, the page table is 4 MB per process.
Explain it simply
Step one is to find the offset bits from the page size, since the offset must be able to point to every byte within a page. Step two is that the remaining bits form the page number, and each possible page number needs a page table entry.
Example
Given: 32-bit addresses, page size 4 KB = 4096 = 2^12 bytes.
- Offset bits = 12.
- Page number bits = 32 - 12 = 20.
- Number of pages = 2^20 = 1,048,576 entries.
- If each entry is 4 bytes, page table size = 2^20 x 4 = 2^22 bytes = 4 MB.
Every process needs its own page table, so 100 processes would use 400 MB just for tables. That is why systems use multi-level page tables, which allocate table pages only for regions actually in use.
Also check the address space size: 2^32 bytes = 4 GB, which equals 2^20 pages x 4 KB.
If the page size were 8 KB (2^13), the offset would be 13 bits, the page number 19 bits, and the page table 2^19 x 4 = 2 MB. Bigger pages mean smaller tables, but more internal fragmentation.
What to say in the interview
"4 KB is 2^12, so the offset takes 12 bits and the page number 20. That means 2^20 entries; with 4-byte entries the table is 4 MB per process. Multi-level tables exist to avoid paying that cost for unused regions."
Common mistakes
- Computing the table size as 2^32 entries, forgetting to remove the offset bits.