GATE2025_CS1_Q14

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?

✅ Final Answer:

The correct answer is option (A) 2²¹.

🔹 Short Answer:

The number of entries in a page table is determined by the number of pages in the logical address space. The logical address space size is 2³² bytes. The page size is 2048 bytes, which is 2¹¹ bytes. Therefore, the number of pages (and thus page table entries) is the logical address space size divided by the page size: 2³² / 2¹¹ = 2^(32-11) = 2²¹.

🔸 Long Answer:

To solve this problem, we need to understand how a logical address is structured in a demand paging system and how that structure determines the size of the page table.

Step 1: Understand the Key Concepts

• Logical Address: The address generated by the CPU. Its size determines the total virtual memory available to a process.
• Physical Address: The address in the main memory (RAM). Its size is irrelevant for calculating the number of page table entries.
• Page Size: The fixed-size block into which logical memory is divided.
• Page Table: A data structure used by the memory management unit (MMU) to map logical pages to physical frames. There is one entry in the page table for every page in the process's logical address space. [4]

The core principle is: Number of Page Table Entries = Number of Pages in Logical Address Space.

Step 2: Deconstruct the Logical Address

A logical address is split into two parts: a Page Number (p) and a Page Offset (d).

Step 3: Calculate the Size of the Page Offset

The page offset is used to locate a specific byte within a page. Its size in bits depends on the page size.

Page Size = 2048 bytes
Since 2048 = 2¹¹, we need 11 bits for the page offset (d).

Step 4: Calculate the Size of the Page Number

The total logical address is 32 bits. We subtract the bits used for the offset to find the bits used for the page number.

Bits for Page Number (p) = Total Logical Address Bits - Page Offset Bits
p = 32 - 11 = 21 bits

Step 5: Calculate the Number of Page Table Entries

The number of possible page numbers determines the number of entries required in the page table. With 21 bits for the page number, we can have 2²¹ unique pages.

Maximum Page Table Entries = 2^{(Number of bits for page number)}
= 2²¹

Thus, the page table will have a maximum of 2²¹ entries. The 20-bit physical address is extra information not needed for this specific calculation but would be relevant for determining the size of each page table entry.

Bibliography:
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley. (Chapter 9: Virtual Memory Management). [1, 3]
- "Paging in Operating System" - GeeksforGeeks. [4]

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.