Calculating Page Table Size

Since we have a virtual address space of 2^32 and each page size is 2^12, we can store (2^32/2^12) = 2^20 pages. Since each entry into this page table has an address of size 4 bytes, then we have 2^20*4 = 4MB. So the page table takes up 4MB in memory.

My explanation uses elementary building blocks that helped me to understand. Note I am leveraging @Deepak Goyal's answer above since he provided clarity:

We were given a logical 32-bit address space (i.e. We have a 32 bit computer)

Consider a system with a 32-bit logical address space

• This means that every memory address can be 32 bits long.
• "A 32-bit entry can point to one of 2^32 physical page frames"[2], stated differently,
• "A 32-bit register can store 2^32 different values"

We were also told that

each page size is 4 KB

• 1 KB (kilobyte) = 1 x 1024 bytes = 2^10 bytes
• 4 x 1024 bytes = 2^2 x 2^10 bytes => 4 KB (i.e. 2^12 bytes)
• The size of each page is thus 4 KB (Kilobytes NOT kilobits).

As Depaak said, we calculate the number of pages in the page table with this formula:

Num_Pages_in_PgTable = Total_Possible_Logical_Address_Entries / page size 
Num_Pages_in_PgTable =         2^32                           /    2^12
Num_Pages_in_PgTable = 2^20 (i.e. 1 million) 

The authors go on to give the case where each entry in the page table takes 4 bytes. That means that the total size of the page table in physical memory will be 4MB:

Memory_Required_Per_Page = Size_of_Page_Entry_in_bytes x Num_Pages_in_PgTable
Memory_Required_Per_Page =           4                 x     2^20
Memory_Required_Per_Page =     4 MB (Megabytes)

So yes, each process would require at least 4MB of memory to run, in increments of 4MB.

Example

Now if a professor wanted to make the question a bit more challenging than the explanation from the book, they might ask about a 64-bit computer. Let's say they want memory in bits. To solve the question, we'd follow the same process, only being sure to convert MB to Mbits.

Let's step through this example.

Givens:

• Logical address space: 64-bit
• Page Size: 4KB
• Entry_Size_Per_Page: 4 bytes

Recall: A 64-bit entry can point to one of 2^64 physical page frames - Since Page size is 4 KB, then we still have 2^12 byte page sizes

• 1 KB (kilobyte) = 1 x 1024 bytes = 2^10 bytes
• Size of each page = 4 x 1024 bytes = 2^2 x 2^10 bytes = 2^12 bytes

How Many pages In Page Table?

`Num_Pages_in_PgTable = Total_Possible_Logical_Address_Entries / page size 
Num_Pages_in_PgTable =         2^64                            /    2^12
Num_Pages_in_PgTable =         2^52 
Num_Pages_in_PgTable =      2^2 x 2^50 
Num_Pages_in_PgTable =       4  x 2^50 `  

How Much Memory in BITS Per Page?

Memory_Required_Per_Page = Size_of_Page_Entry_in_bytes x Num_Pages_in_PgTable 
Memory_Required_Per_Page =   4 bytes x 8 bits/byte    x     2^52
Memory_Required_Per_Page =     32 bits                x   2^2 x 2^50
Memory_Required_Per_Page =     32 bits                x    4  x 2^50
Memory_Required_Per_Page =     128 Petabits

[2]: Operating System Concepts (9th Ed) - Gagne, Silberschatz, and Galvin

In 32 bit virtual address system we can have 2^32 unique address, since the page size given is 4KB = 2^12, we will need (2^32/2^12 = 2^20) entries in the page table, if each entry is 4Bytes then total size of the page table = 4 * 2^20 Bytes = 4MB